第第頁(yè)基于分類規(guī)則的C4_5決策樹(shù)改進(jìn)算法_李孝偉

２０１３年１２月第３４卷第１２期

計(jì)算機(jī)工程與設(shè)計(jì)

ＣＯＭＰＵＴＥＲＥＮＧＩＮＥＥＲＩＮＧＡＮＤＤＥＳＩＧＮ

Ｄｅｃ．２０１３

Ｖｏｌ．３４Ｎｏ．１２

基于分類規(guī)則的Ｃ４．５決策樹(shù)改進(jìn)算法

李孝偉，陳福才，李邵梅

（）國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南鄭州４５０００２

４３２２

計(jì)算機(jī)工程與設(shè)計(jì)

２０１３年

樣本策略，如：支持向量機(jī)的決策只與決策邊界的支持向量有關(guān)，重點(diǎn)選擇此類樣本；Ｃ４．５決策樹(shù)建樹(shù)的重點(diǎn)是最優(yōu)特征值樣本的選取，在縮減樣本提取分類規(guī)則時(shí)，則以樣本是否能很好的反映類內(nèi)特征取值的情況來(lái)進(jìn)行取舍。縮減樣本可以起到降低分類算法的計(jì)算代價(jià)，加快訓(xùn)練速

４］

，還能有效地精簡(jiǎn)訓(xùn)練集，度，避免出現(xiàn)“過(guò)擬合”現(xiàn)象［

去除相似、冗余、重復(fù)的信息以及噪聲樣本。此外，對(duì)于數(shù)據(jù)集不大的情況，由于Ｃ４．５對(duì)于初始訓(xùn)練樣本的依賴性比較大，若初始訓(xùn)練樣本不能很好地表征各特征的取值，可能使得訓(xùn)練結(jié)果不理想，此時(shí)若采用選擇樣本提取分類規(guī)則的策略，提取盡量最優(yōu)的分類規(guī)則以提高訓(xùn)練精度對(duì)于Ｃ４．５決策樹(shù)而言也具有重要意義。

５］

劉鵬等［根據(jù)決策樹(shù)易產(chǎn)生碎片問(wèn)題，提出了一種合

圖１簡(jiǎn)單的決策樹(shù)模型

１．１Ｃ４．５決策樹(shù)的形成

假定訓(xùn)練數(shù)據(jù)集中包含ｍ類別，分別為Ｔ＝｛ｔ１，，。訓(xùn)練數(shù)據(jù)集中某屬性Ａ可能有（，ｔ．．．ｔａａ．．ａ２，ｍ｝１，２，ｋ），，共ｋ種取值，根據(jù)屬性Ａ的劃分為Ｔ′＝｛ｔ′ｔ′．．．ｔ′１，２，ｒ｝其他屬性類似于屬性Ａ。根據(jù)訓(xùn)練集可得其理想劃分的信息熵為

ｍ

并分類效果差分枝的Ｒ－Ｃ４．５模型。該模型未設(shè)置連續(xù)屬性

［］

一對(duì)多”處理和缺失值處理。ＫｅｍａｌＰｏｌａｔ等６將Ｃ４．５和“

分類模型相結(jié)合應(yīng)用于多類分類問(wèn)題，取得了很好的效果。

［］

ＨａｎＪｉｎｔｉ等７將Ｃ４．５和模糊數(shù)學(xué)相結(jié)合，提出了一種處－ｇ８］理范圍輸入的方法。姚亞夫等［根據(jù)Ｆａｄ連續(xù)值取值的ｙｙ

最佳分割點(diǎn)總在邊界點(diǎn)處得原理，只在連續(xù)屬性分界點(diǎn)處的少數(shù)幾個(gè)分割點(diǎn)中選擇最佳分割閾值，構(gòu)造了Ｃ４．５分類器，一定程度上提升了Ｃ４．５處理連續(xù)屬性的性能。周劍鋒

９］等［提出了一種改進(jìn)的信息熵的計(jì)算方法，通過(guò)減少計(jì)算１０］

根據(jù)函數(shù)的復(fù)雜度，提高就決策樹(shù)的構(gòu)建速度。楊哲等［

Ｈ（Ｔ）＝－∑ｐ（ｔｌｏｔｇｉ）２ｉ）ｐ（

ｉ＝１

ｍ

）（１

（。其中ｐ（ｔ＝ｉ）ｉ／ｉ）∑ｉ＝１

以屬性Ａ對(duì)訓(xùn)練集劃分獲得的信息熵為

ｒ

Ｔ′）＝ＨＡ（

＝

信息增益率的不確定性，采用Ｍａｎｔａｒａｓ范式距離來(lái)度量屬性劃分與真實(shí)劃分的距離，有效避免了增益率的不確定性?，F(xiàn)有的改進(jìn)算法在減少?zèng)Q策樹(shù)的計(jì)算復(fù)雜度、特征的優(yōu)化處理、增益率問(wèn)題上都有很多的優(yōu)化。但是對(duì)Ｃ４．５決策樹(shù)的局部最優(yōu)解、大數(shù)據(jù)處理的依賴主存問(wèn)題和效率問(wèn)題一直沒(méi)有得到很好的解決。

基于上述問(wèn)題，本文利用多次抽樣選擇最優(yōu)分類規(guī)則并對(duì)Ｃ４．５決策樹(shù)算法進(jìn)行優(yōu)化和改進(jìn)，提出了基于分類規(guī)則的Ｃ４．５決策樹(shù)改進(jìn)算法。實(shí)驗(yàn)結(jié)果表明，利用改進(jìn)后的算法處理小樣本數(shù)據(jù)時(shí)正確率與Ｃ４．５算法相當(dāng)；而在處理大樣本數(shù)據(jù)的識(shí)別分類時(shí)，運(yùn)算效率和精度的提高比較顯著。

ｉ＝１ｒ

ｔ′）Ｈ（ｔ′）∑ｐ（

ｉ

ｉｍ

ｉ

ｊ

ｉ

２

ｉ＝１

ｔ′）ｔ｜ｔ′）ｌｏｔ｜ｔ′）－∑ｐ（ｇｐ（（）∑ｐ（

ｊ

ｉ

ｊ＝１

ｒ

ｍ

Ｔ′）＝－∑∑ｐ（ｔ′ｔｔ′ｌｏｔｔ′ＨＡ（ｇｉ）ｉ）２ｉ）ｐ（ｐ（ｊ｜ｊ｜

ｉ＝１ｊ＝１

Ｔ｜Ｔ′）＝Ｈ（

其中ｐ（ｔ′′′∑ｉ）＝ｉ／（ｉ

ｉ＝１ｒ

）（２

），ｐ（ｔ′ｉ）＝ｊ｜ｔ

′ｔ′ｉ∩ｉ。ｊ／表示劃分Ｔｔｔ′′中屬于ｔ′ｉ）ｉ的樣本，在理想劃分ｐ（ｊ｜中屬于子集ｔｊ的概率。由此可得屬性Ａ對(duì)于訓(xùn)練集劃分的信息增益為

ＨＧＴ′）＝Ｈ（Ｔ）Ｔ′）－ＨＡ（ａｉｎ（

屬性Ａ的分割信息熵為

ｒ

）（３

１Ｃ４．５決策樹(shù)介紹

決策樹(shù)作為傳統(tǒng)的機(jī)器學(xué)習(xí)算法，其用于分類識(shí)別的主要步驟同其他分類算法一致，主要是：一是利用訓(xùn)練數(shù)據(jù)構(gòu)建分類模型，二是利用建立的分類模型對(duì)待識(shí)別樣本數(shù)據(jù)集進(jìn)行分類。其中主要工作是第一步，對(duì)于決策樹(shù)分類算法而言是建立用于分類的決策樹(shù)模型。圖１所示是一個(gè)簡(jiǎn)單的決策樹(shù)分類模型，其主要功能是實(shí)現(xiàn)根據(jù)天氣情況來(lái)決定是否去戶外活動(dòng)

。

Ｈ（Ｔ′）＝－∑ｐ（ｔ′ｌｏｔ′ｇｉ）２ｉ）ｐ（

ｉ＝１

）（４

）、式（）可得屬性Ａ的信息增益率為由式（３４／ａｔｉｏ（Ｔ′）＝ＨＧＴ′）Ｈ（Ｔ′）Ｒａｉｎ（

＝

（））（

Ｈ（Ｔ′）

（）５

同理可計(jì)算其他屬性的信息增益率。通過(guò)計(jì)算所有屬性的信息增益率，選出具有最大信息增益率值的屬性作為決策樹(shù)的根節(jié)點(diǎn)。然后，以同樣的方法確定決策樹(shù)各層的

第３４卷第１２期

李孝偉，陳福才，李邵梅：基于分類規(guī)則的Ｃ４．５決策樹(shù)改進(jìn)算法

４３２３

節(jié)點(diǎn)，計(jì)算方法同以上步驟。１．２Ｃ４．５決策樹(shù)的剪枝

征對(duì)應(yīng)的劃分與理想劃分之間的相似度。

Ｃ４．５采用的信息增益率如下

Ｃ４．５決策樹(shù)的剪枝策略采用的是后剪枝的方法。后剪枝策略首先需要構(gòu)造完整的決策樹(shù)，允許決策樹(shù)過(guò)度擬合訓(xùn)練數(shù)據(jù)，然后對(duì)那些置信度不夠的子樹(shù)節(jié)點(diǎn)用葉節(jié)點(diǎn)來(lái)替代。

Ｃ４．５決策樹(shù)對(duì)ＩＤ３算法做了改進(jìn)，取得了不錯(cuò)的效——局部最果。但是Ｃ４．５自身仍存在著決策樹(shù)的共性問(wèn)題—）可以看出，當(dāng)分母為零時(shí)，分子必優(yōu)解。此外，從式（５然為零，這時(shí)增益率的計(jì)算就出現(xiàn)了問(wèn)題，這就是增益率帶來(lái)的不確定性問(wèn)題。大樣本數(shù)據(jù)條件下，減?。茫矗禌Q策樹(shù)的運(yùn)算復(fù)雜度也是一個(gè)問(wèn)題。

Ｒａｔｉｏ（Ｔ′）＝

＝

（））（

ＨＴ′）Ｈ（Ｔ）Ｈ（Ｔ，Ｔ′）Ｔ′）（Ｈ（

ＨＴ′（）１０

）與式（比較式（９１０）可得：Ｈ（Ｔ′）＝０時(shí)，Ｈ（Ｔ′，）不會(huì)出現(xiàn)式（９１０）的０∶０的情況，此時(shí)Ｔ）≠０，式（

可以解決增益率帶來(lái)的不確定性問(wèn)題。式（９）是由Ｍａｎｔ－ａｒａｓ范式距離而得來(lái)的，故其能很好的表征兩個(gè)劃分之間的相似度。劃分相似度方法能有效克服信息增益率方法的缺陷，算法的穩(wěn)定性好，其構(gòu)建的決策樹(shù)規(guī)模更小，分類速度更快。

ｑ

２基于分類規(guī)則選取的Ｃ４．５決策樹(shù)改進(jìn)算法

本文針對(duì)的主要是大樣本條件下的分類識(shí)別和Ｃ４．５決策樹(shù)與初始訓(xùn)練集相關(guān)性較大等問(wèn)題。運(yùn)用多次抽樣選出最優(yōu)分類規(guī)則，以縮減算法的運(yùn)算復(fù)雜度，提高訓(xùn)練精度。在Ｃ４．５最優(yōu)特征選擇上以劃分相似度作為選擇標(biāo)準(zhǔn)。２．１最優(yōu)特征選擇

由熵函數(shù)的上凸性及詹森不等式有：

ｑ

ｉ＝１ｑ

ｏｇｙ∑ｐｌ

ｉ

ｉ

≤

ｌｏｏｇｇｉｉ，在計(jì)算信息熵的時(shí)候，由于ｌｉｉ計(jì)算ｙｙ∑ｐ∑ｐ

ｉ＝１

ｉ＝１

ｑ

ｑ

結(jié)果與ｌｏｏｇｇｉｉ的計(jì)算結(jié)果相差不大，用ｌｉｉ來(lái)ｙｙ∑ｐ∑ｐ

ｉ＝１

ｉ＝１

ｑ

近似代替

本文對(duì)Ｍａｎｔａｒａｓ范式距離進(jìn)行相應(yīng)的簡(jiǎn)化，以減少算法的復(fù)雜度和時(shí)間消耗。Ｍａｎｔａｒａｓ范式距離是在各特征中選擇與類別劃分距離最近的特征作為當(dāng)前節(jié)點(diǎn)的測(cè)試條件，用最短距離劃分的辦法來(lái)構(gòu)建決策樹(shù)。根據(jù)樣本集Ｔ的理，想劃分Ｔ＝｛和以屬性Ａ作為測(cè)試條件所得ｔｔ．．．ｔ１，２，ｍ｝，，則劃分Ｔ的劃分Ｔ′＝｛ｔ′ｔ′．．．ｔ′′對(duì)于理想劃分Ｔ１，２，ｒ｝的條件熵可以由式（２）得到。而理想劃分Ｔ對(duì)于劃分Ｔ′的條件熵為

ｍ

ｒ

ｉ＝１

ｏｇｙ∑ｐｌ

ｉ

ｉ

。這樣式（）可以簡(jiǎn)化為９

（））（

ｄ（Ｔ′，Ｔ）＝

Ｈ（Ｔ′，Ｔ）

ｍ

２

ｒ

２ｌｏｔｏｔ′＋ｌｇｇ２ｉ）２ｉ）ｐ（ｐ（∑∑ｉ＝１ｉ＝１

≈－

ＨＴ′Ｔｍ

２

ｒ

２

ｌｏｔｔ′ｇ２ｉ）ｉ）ｐ（ｐ（（）∑∑ｉ＝１ｉ＝１

（，）ｄＴ′Ｔ≈－

ＨＴ′Ｔ（）１１

）將多次對(duì)數(shù)運(yùn)算簡(jiǎn)化為一次，在一定程度上式（１１減?。茫矗禌Q策樹(shù)建樹(shù)的復(fù)雜度。２．２分類規(guī)則的選取

）／）（６Ｈ（Ｔ′｜Ｔ）＝－∑∑ｐ（ｔ′ｔｌｏｔ′ｔｔｇｉ，２（ｉ，ｐ（ｐ（ｊ）ｊ）ｊ）

ｊ＝１ｉ＝１

劃分Ｔ′與理想劃分Ｔ的聯(lián)合熵為

ｍ

ｒ

本文采用的樣本選擇方法主要是多次提取樣本進(jìn)行決

）（７

策樹(shù)的擬合，生成相對(duì)較優(yōu)的決策樹(shù)，將較大量的樣本通過(guò)隨機(jī)有放回的抽樣，生成多個(gè)訓(xùn)練集，利用這些訓(xùn)練集的訓(xùn)練結(jié)果回溯生成最優(yōu)的分類規(guī)則。

具體步驟如下：

第一步，對(duì)給定的數(shù)據(jù)集選擇合適的訓(xùn)練樣本數(shù)據(jù)，選擇的標(biāo)準(zhǔn)是綜合考慮訓(xùn)練時(shí)間和迭代次數(shù)。如果選擇的的數(shù)據(jù)較小，會(huì)造成較多的迭代次數(shù)，否則會(huì)造成較多的訓(xùn)練時(shí)間。

第二步，針對(duì)選定的訓(xùn)練樣本，通過(guò)實(shí)驗(yàn)確定抽樣迭代次數(shù)Ｌ，理論上Ｌ越大越好，但Ｌ越大，處理時(shí)間也會(huì)

Ｈ（Ｔ′，Ｔ）＝－∑∑ｐ（ｔ′ｔｌｏｔ′ｔｇｉ，２ｉ，ｐ（ｊ）ｊ）

ｊ＝１ｉ＝１

因此，劃分Ｔａｎｔａｒａｓ范式距離為′與理想劃分Ｔ的Ｍ

（））（

Ｄ（Ｔ′，Ｔ）＝

ＨＴ′Ｔ）＋Ｈ（），得到＝Ｈ（Ｔ｜Ｔ′Ｔ′

（）８

由熵的強(qiáng)可加性，即Ｈ（Ｔ′，Ｔ）＝Ｈ（Ｔ′｜Ｔ）＋Ｈ（Ｔ）

（，）），））（（（

Ｄ（Ｔ′，Ｔ）＝ＨＴ′Ｔ

＝２－

令

（））（

ＨＴ′Ｔ（））（

ｄ（Ｔ′，Ｔ）＝

ＨＴ′Ｔ（）９

隨之增加，Ｌ值的確定依據(jù)是當(dāng)Ｌ增加時(shí)，對(duì)訓(xùn)練樣本的精度提升不再產(chǎn)生影響或是影響很小。

第三步，針對(duì)Ｌ次訓(xùn)練結(jié)果產(chǎn)生的Ｌ個(gè)決策樹(shù)形成的

定義１劃分相似度ｄ（Ｔ′，Ｔ）。劃分相似度表示為特

４３２４

計(jì)算機(jī)工程與設(shè)計(jì)

２０１３年

分類規(guī)則進(jìn)行離散取值特征和連續(xù)取值特征的處理。具體方法如下：

對(duì)于離散數(shù)值特征：統(tǒng)計(jì)Ｌ個(gè)規(guī)則內(nèi)，各個(gè)取值出現(xiàn)的次數(shù)，選取出現(xiàn)次數(shù)多的作為新規(guī)則內(nèi)該類別此特征的取值，以此方法建立此類特征的特征取值空間。

對(duì)于連續(xù)取值特征：每一類的連續(xù)取值特征都有相應(yīng)的區(qū)間上限和下限，選?。檀我?guī)則內(nèi)的全部上限和下限的算術(shù)平均作為新規(guī)則內(nèi)該類別特征的取值上限和下限。

通過(guò)上述過(guò)程，每迭代一次，形成一個(gè)決策樹(shù)的分類規(guī)則，相應(yīng)的每一類別都對(duì)應(yīng)其具體的特征取值，最優(yōu)的分類規(guī)則則是通過(guò)多次建樹(shù)形成的分類規(guī)則回溯得到，通過(guò)最優(yōu)的分類規(guī)則可以建立最優(yōu)的決策樹(shù)。２．３剪枝策略

回歸、聚類、關(guān)聯(lián)規(guī)則等多種機(jī)器學(xué)習(xí)算法，并能夠?qū)崿F(xiàn)交互式界面上的可視化。

本文選用ＵＣＩ機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)（ｍａｃｈｉｎｅｌｅａｒｎｉｎｒｅ－ｇ）中的Ｎ、Ｍ、ＢｏｓｉｔｏｒｕｒｓｅｒＤａｔａｂａｓｅａｉｃ０４、Ｌｅｔｔｅｒａｎｋｐｙｙｇ、ＰＭａｒｋｅｔｉｎｏｓｔｕｒｅＲｅｃｏｎｓｔｒｕｃｔｉｏｎ等５個(gè)數(shù)據(jù)集來(lái)進(jìn)行實(shí)ｇ驗(yàn)。選擇的數(shù)據(jù)集特征維數(shù)都不高，便于運(yùn)用Ｃ４．５算法。各個(gè)數(shù)據(jù)集的大小和特征情況見(jiàn)表１。

表１數(shù)據(jù)集樣本個(gè)數(shù)和特征個(gè)數(shù)

數(shù)據(jù)集ＮｕｒｓｅｒＤａｔａｂａｓｅｙ

Ｍａｉｃ０４ｇＬｅｔｔｅｒＢａｎｋＭａｒｋｅｔｉｎｇＰｏｓｔｕｒｅＲｅｃｏｎｓｔｒｕｃｔｉｏｎ

樣本１２，９６０１９，０２０２０，０００４８，８４２１６４，８６０

特征８１１１７１４８

訓(xùn)練集６，４８０９，５１０１０，０００２０，０００５０，０００

本文擬采取的剪枝策略與ＣＡＲＴ算法類似。首先讓決策樹(shù)充分的生長(zhǎng)，使得葉節(jié)點(diǎn)有最小的不純度為止，然后，對(duì)所有相鄰的成對(duì)葉節(jié)點(diǎn)，考慮是否消去他們。標(biāo)準(zhǔn)是如果消去他們使得不純度增加的很小，就執(zhí)行消去。這里的不純度采用Ｇｉｎｉ不純度，多類分類問(wèn)題的不純度定義為

３．２實(shí)驗(yàn)結(jié)果及分析

本文實(shí)驗(yàn)采用的硬件環(huán)境是：ＣＰＵＣｏｒｅ２Ｐ９６００，內(nèi)存４２．６６Ｇ．Ｇ，硬盤(pán)５００Ｇ，Ｗｉｎｄｏｗ７操作系統(tǒng)。實(shí)驗(yàn)首先采用不同的抽樣次數(shù)來(lái)確定最終的抽樣次數(shù)。然后在選定抽樣次數(shù)下于Ｃ４．５算法進(jìn)行比較。

圖２為數(shù)據(jù)集ＢａｎｋＭａｒｋｅｔｉｎｇ不同抽樣次數(shù)的正確率對(duì)比。由圖中可以看出在抽樣次數(shù)比較少的情況下，本文算法不如Ｃ４．５算法。隨著抽樣次數(shù)的增加，本文算法的優(yōu)勢(shì)逐漸體現(xiàn)出來(lái)，當(dāng)抽樣次數(shù)增加到一定數(shù)值時(shí)，算法的性能也趨于平穩(wěn)。由圖中可以看出，當(dāng)抽樣次數(shù)為１２和１５時(shí)，算法性能差別很小，故選擇１２為最終抽樣次數(shù)

。

ｉｍＮ）＝ｐ（

ｗ）Ｐ（ｗ）＝１－∑Ｐ∑Ｐ（

ｉ

ｊ

ｉｊ≠

ｊ

２

）（１２ｗｊ）（

其中Ｐ（是節(jié)點(diǎn)Ｎ處屬于ｗｗｊ）ｊ類樣本數(shù)占總樣本數(shù)的比例。顯然如果所有樣本都屬于一類，則不純度為０，否則就是一個(gè)大于０的正值。

２．４基于分類規(guī)則選取的Ｃ４．５決策樹(shù)改進(jìn)算法

本文提出的基于分類規(guī)則選取的Ｃ４．５決策樹(shù)改進(jìn)算法（ｉｍｒｏｖｅｄＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅａｌｏｒｉｔｈｍｂａｓｅｄｏｎｃｌａｓｓｉｆｉｃａ－ｐｇ，），在訓(xùn)練階段以第一節(jié)提出分ｔｉｏｎｒｕｌｅｓｓｅｌｅｃｔｉｏｎＣＲＣ４．５類規(guī)則選取策略，在構(gòu)建決策樹(shù)選取最優(yōu)特征上以第二節(jié)提出的劃分相似度為基礎(chǔ)建立Ｃ４．５決策樹(shù)。具體算法流程如下：

（）運(yùn)用劃分相似度對(duì)訓(xùn)練樣本各特征進(jìn)行排序，選１

擇有最大劃分相似度的特征作為根節(jié)點(diǎn)，以后節(jié)點(diǎn)以此類推；

（）選定訓(xùn)練樣本數(shù)目，并對(duì)對(duì)樣本進(jìn)行有放回的多２

次抽樣，運(yùn)用劃分相似度訓(xùn)練分類規(guī)則，取多次抽樣下分類規(guī)則中最優(yōu)的特征值回溯作為最終分類規(guī)則；

）根據(jù)最優(yōu)的分類規(guī)則建立最優(yōu)的決策樹(shù)，并對(duì)測(cè)（３

試集進(jìn)行測(cè)試，最后輸出分類模型。

３實(shí)驗(yàn)及分析

３．１實(shí)驗(yàn)平臺(tái)和數(shù)據(jù)集介紹

圖２不同抽樣次數(shù)下算法性能比較

經(jīng)過(guò)實(shí)驗(yàn)，各數(shù)據(jù)集下訓(xùn)練集樣本迭代次數(shù)見(jiàn)表２。Ｃ４．５算法和本文算法的模型建立時(shí)間和分類正確率對(duì)比如圖３、圖４所示。其中，Ｃ４．５采用多次次迭代交叉驗(yàn)證的方法。

本文采用Ｗｅｋａ平臺(tái)對(duì)改進(jìn)的算法和Ｃ４．５算法進(jìn)行對(duì)比測(cè)試。Ｗｅｋａ是由新西蘭大學(xué)Ｗｉｔｔｅｎ教授等人基于Ｊａｖａ編程開(kāi)發(fā)的開(kāi)源工作平臺(tái)，它集合了包括對(duì)數(shù)據(jù)進(jìn)行分類、

第３４卷第１２期

李孝偉，陳福才，李邵梅：基于分類規(guī)則的Ｃ４．５決策樹(shù)改進(jìn)算法

４３２５

表２不同數(shù)據(jù)集抽樣次數(shù)

數(shù)據(jù)集ＮｕｒｓｅｒＤａｔａｂａｓｅｙ

Ｍａｉｃ０４ｇＬｅｔｔｅｒＢａｎｋＭａｒｋｅｔｉｎｇＰｏｓｔｕｒｅＲｅｃｏｎｓｔｒｕｃｔｉｏｎ

抽樣次數(shù)

８８１０１２２

０

練集相關(guān)性大以及信息增益率帶來(lái)的不確定問(wèn)題，提出了基于分類規(guī)則選取的Ｃ４．５決策樹(shù)改進(jìn)算法。分類規(guī)則選取上以多次抽樣訓(xùn)練的分類規(guī)則為基礎(chǔ)形成最優(yōu)分類規(guī)則，實(shí)驗(yàn)表明在選取的最優(yōu)分類規(guī)則下測(cè)試的精度同未進(jìn)行分類規(guī)則選擇的訓(xùn)練集測(cè)試精度有明顯提升。對(duì)于大樣本而言，訓(xùn)練時(shí)間也有明顯的縮短。在Ｃ４．５決策樹(shù)的特征選擇上以提出的劃分相似度為基準(zhǔn)，克服了信息增益率的不穩(wěn)定性，并且依據(jù)熵函數(shù)的上凸性，簡(jiǎn)化了熵的運(yùn)算，也帶來(lái)了運(yùn)算量的減少。目前，本文提出的分類規(guī)則選取策略針對(duì)分類規(guī)則較復(fù)雜的情況還沒(méi)有進(jìn)一步的論證實(shí)驗(yàn)；此外劃分相似度的優(yōu)越性還缺乏有效的理論證明，這些都需要進(jìn)一步的研究。

［］Ｈ，７ａｎＪｉｎｔｉＧｕＹｕｉａ．Ｓｔｕｄｏｎｈａｎｄｉｎｒａｎｉｎｕｔｓｍｅｔｈｏｄｓｏｎｇｊｙｇｇｐ

／Ｃ４．５ａｌｏｒｉｔｈｍ［Ｃ］／ＣｏｍｕｔｅｒＳｃｉｅｎｃｅｅｃｈｎｏｌｏａｎｄＡ－Ｔ－ｇｐｇｙｐ，ｌｉｃａｔｉｏｎｓ２００９：４７４９．－ｐ

［］ＹＡＯ８Ｙａｆｕ，ＸＩＮＧＬｉｕｔａｏ．ＩｍｒｏｖｅｍｅｎｔｏｆＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅｐ

ｃｏｎｔｉｎｕｏｕｓａｔｔｒｉｂｕｔｅｓｓｅｍｅｎｔａｔｉｏｎｔｈｒｅｓｈｏｌｄａｌｏｒｉｔｈｍａｎｄｉｔｓｇｇ］ａｌｉｃａｔｉｏｎ［Ｊ．ＪｏｕｒｎａｌｏｆＣｅｎｔｒａｌＳｏｕｔｈＵｎｉｖｅｒｓｉｔｏｆＴｅｃｈ－ｐｐｙ）：）姚亞夫，刑ｎｏｌｏ２０１１，４２（１２３７７２３７７６（ｉｎＣｈｉｎｅｓｅ．［－ｇｙ，］留濤．決策樹(shù)Ｃ４．５連續(xù)屬性分割閾值算法改進(jìn)及其應(yīng)用［Ｊ．）：］中南大學(xué)學(xué)報(bào)，２０１１，４２（１２３７７２３７７６．－

４結(jié)束語(yǔ)

本文是基于Ｃ４．５決策樹(shù)在處理較大樣本的不足、與訓(xùn)

（下轉(zhuǎn)第４３３０頁(yè)）

４３３０

計(jì)算機(jī)工程與設(shè)計(jì)

２０１３年

（）萬(wàn)燕，劉偉．基于低質(zhì)量圖片的兩級(jí)車牌字ｉｎＣｈｉｎｅｓｅ．［］：符識(shí)別算法［Ｊ．計(jì)算機(jī)應(yīng)用與軟件，２０１２，２９（１１）２８１］２８４．－

［，ＧＡＯ１２］ＹＡＮＧＬｕｎｂｉａｏＹｉｎｉ．Ｐｒｉｎｃｉｌｅａｎｄａｌｉｃａｔｉｏｎｏｆｇｙｐｐｐ

：ｆｕｚｚｍａｔｈｅｍａｔｉｃｓ［Ｍ］．ＧｕａｎｚｈｏｕＳｏｕｔｈＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｇｙ，２）楊綸標(biāo)，ｏｆＴｅｃｈｎｏｌｏＰｒｅｓｓ００６：３９４０（ｉｎＣｈｉｎｅｓｅ．［－ｇｙ高英儀．模糊數(shù)學(xué)原理及應(yīng)用［Ｍ］．廣州：華南理工大學(xué)出］版社，２００６：３９４０．－

［］ＱＵ，，，１３ＦｕｈｅｎＣＵＩＧｕａｎｃａｉＬＩＹａｎｆａｎｅｔａｌ．Ｆｕｚｚｃｌｕｓｔｅ－ｇｇｇｙ

：Ｎｒｉｎａｌｏｒｉｔｈｍａｎｄｉｔｓａｌｉｃａｔｉｏｎ［Ｍ］．ＨｕｎａｎａｔｉｏｎａｌＤｅ－ｇｇｐｐ