董躍華，　劉力

（江西理工大學(xué)信息工程學(xué)院，江西 贛州341000）

基于權(quán)衡因子的決策樹優(yōu)化算法

董躍華，劉力

（江西理工大學(xué)信息工程學(xué)院，江西 贛州341000）

通過分析ID3算法的多值偏向問題和傳統(tǒng)ID3改進(jìn)算法中出現(xiàn)的主觀性等問題，提出了一種基于權(quán)衡因子的決策樹優(yōu)化算法.該優(yōu)化算法通過引入能夠反映屬性之間相互依賴關(guān)系的權(quán)衡因子，對(duì)取值個(gè)數(shù)最多的屬性的劃分權(quán)重重新進(jìn)行權(quán)衡，以完成對(duì)ID3算法的改進(jìn).實(shí)例驗(yàn)證和標(biāo)準(zhǔn)數(shù)據(jù)集UCI上的實(shí)驗(yàn)結(jié)果表明，當(dāng)數(shù)據(jù)集中屬性的取值個(gè)數(shù)不相同時(shí)，優(yōu)化后的ID3算法能夠解決多值偏向問題，在構(gòu)建決策樹的過程中，優(yōu)化后的ID3算法既能提高平均分類準(zhǔn)確率，又能減少平均葉子節(jié)點(diǎn)數(shù).

ID3算法；多值偏向；權(quán)衡因子；決策樹；權(quán)重

0　引言

數(shù)據(jù)分類是數(shù)據(jù)挖掘中重要的組成部分之一［1］，其中包含有決策樹分類器、貝葉斯分類器、遺傳算法、粗糙集和模糊邏輯等基本技術(shù)［2］.決策樹算法由于其分類精度高、生成的模式簡單、算法易理解等特點(diǎn)而得到廣泛應(yīng)用.眾多決策樹算法中，ID3算法的影響力最大［3］.

由于ID3算法采用信息熵的計(jì)算方式來選擇分裂屬性，易導(dǎo)致其產(chǎn)生多值偏向問題［4］.針對(duì)ID3算法的多值偏向問題，很多學(xué)者進(jìn)行了相關(guān)的改進(jìn)工作：文獻(xiàn)［5-8］引入用戶興趣度參數(shù)，用戶興趣度參數(shù)在一定程度上雖能克服多值偏向問題，但該參數(shù)的選取主要依靠用戶豐富的先驗(yàn)知識(shí)和領(lǐng)域知識(shí)；文獻(xiàn)［9-10］在文獻(xiàn)［6］的基礎(chǔ)上進(jìn)行改進(jìn)，引入灰色關(guān)聯(lián)度代替用戶興趣度參數(shù)，雖在克服多值偏向問題上取得一定成效，但由于實(shí)際操作中易出現(xiàn)灰度較低或?qū)傩匀≈祩€(gè)數(shù)較多等情況而導(dǎo)致難以界定其范圍.

本文引入統(tǒng)計(jì)學(xué)中的 λ相關(guān)系數(shù)［11］，其公式完全由加、減、除基本運(yùn)算組成，因此λ相關(guān)系數(shù)不僅可獲得屬性之間的相互依賴關(guān)系，且計(jì)算量較小.本文結(jié)合λ相關(guān)系數(shù)，在文獻(xiàn)［6］的基礎(chǔ)上提出基于權(quán)衡因子的決策樹優(yōu)化算法.優(yōu)化的ID3算法在選取分裂屬性時(shí)，因其以信息熵理論為基礎(chǔ)從而繼承原ID3算法較高的分類精度.用權(quán)衡因子替代用戶興趣度，既能克服多值偏向問題，又能避免選取的主觀參數(shù)對(duì)決策結(jié)果造成影響.實(shí)驗(yàn)結(jié)果表明，在數(shù)據(jù)集存在多值偏向的趨勢時(shí)，基于權(quán)衡因子的決策樹優(yōu)化算法，既能夠克服多值偏向問題，又能提高分類精度，減少葉子節(jié)點(diǎn)數(shù).

1　基本理論

1.1ID3算法

設(shè)訓(xùn)練集S有s個(gè)樣本，將訓(xùn)練集分成m個(gè)類，第i類的實(shí)例個(gè)數(shù)為si.選擇屬性Ap劃分訓(xùn)練集S，設(shè)屬性Ap有屬性值｛S1，S2，…，Sj，…，Sk｝，Sj中屬于第i類的訓(xùn)練實(shí)例個(gè)數(shù)為sij，則得到劃分屬性Ap的信息增益為［2］：

其中：

其中，pi是 S中屬于第 i類的概率，pi=si/s；pij為 sj中第i類樣本的概率，pij=sij/sj；

1.2基于用戶興趣度參數(shù)的ID3改進(jìn)算法

信息熵的計(jì)算方式使得ID3算法的分裂屬性的選擇容易偏向于取值較多的屬性，但擁有較多屬性值的屬性不一定是當(dāng)前最佳分裂屬性，因而就造成了ID3算法的多值偏向問題.文獻(xiàn)［6］為克服多值偏向問題，在信息熵公式中引入用戶興趣度α（0≤α≤1），將子元組的劃分權(quán)重加上α，則子元組對(duì)應(yīng)需要的期望信息量公式（3）修改為［6］：

對(duì)應(yīng)的信息增益公式（1）也將改進(jìn)為：

基于用戶興趣度參數(shù)的ID3改進(jìn)算法是以公式（6）作為分裂屬性的選擇標(biāo)準(zhǔn)，同時(shí)該算法也存在一些不足之處：

1）由于用戶興趣度參數(shù)α的值需要由用戶根據(jù)先驗(yàn)知識(shí)或者領(lǐng)域知識(shí)來確定，因此基于用戶興趣度參數(shù)的ID3改進(jìn)算法帶有很強(qiáng)的專業(yè)領(lǐng)域性，易給用戶造成跨領(lǐng)域知識(shí)的學(xué)習(xí)負(fù)擔(dān)［12］.

2）當(dāng)大部分屬性數(shù)據(jù)規(guī)模較大且個(gè)別屬性數(shù)據(jù)規(guī)模較小時(shí)，人們?nèi)粢驅(qū)傩缘恼J(rèn)識(shí)不夠深刻而令給出的用戶興趣度不能正確反應(yīng)屬性自身的重要性時(shí)，則會(huì)導(dǎo)致出現(xiàn)大數(shù)據(jù)掩蓋小數(shù)據(jù)的情況［13］.

3）用戶興趣度由于是主觀給出的劃分權(quán)重參數(shù)，因此在一定程度上人為因素會(huì)影響最終的決策結(jié)果.

4）屬性的用戶興趣度參數(shù)只有在經(jīng)過大量實(shí)驗(yàn)和反復(fù)驗(yàn)證之后才能被正確的給出.

1.3λ相關(guān)系數(shù)

統(tǒng)計(jì)學(xué)中通常使用相關(guān)系數(shù)作為衡量變量之間密切相關(guān)程度的評(píng)價(jià)標(biāo)準(zhǔn).由于被考量的變量存在不同的特性，因此變量對(duì)應(yīng)表示的相關(guān)系數(shù)也存在多個(gè)種類，例如可用λ系數(shù)測定兩個(gè)定類數(shù)據(jù)之間的密切相關(guān)程度，可用γ系數(shù)和皮斯?fàn)柭燃?jí)相關(guān)系數(shù)測量兩個(gè)定序數(shù)據(jù)之間的密切相關(guān)程度，可用ρ相關(guān)系數(shù)測量兩個(gè)普通變量之間的密切相關(guān)程度［11］.

其中，ρ相關(guān)系數(shù)的應(yīng)用面較為廣泛且限制條件較少，但其計(jì)算量較大.本文主要研究λ相關(guān)系數(shù)，相比較于ρ相關(guān)系數(shù)，λ相關(guān)系數(shù)也能評(píng)價(jià)變量之間的相關(guān)性且其計(jì)算量較小.λxy相關(guān)系數(shù)主要適用的情況為：在兩個(gè)定類變量中，另外又分為自變量和因變量.其中，x代表自變量，共有n個(gè)值；y代表因變量，共有m個(gè)值，則λxy相關(guān)系數(shù)對(duì)應(yīng)的計(jì)算公式為［14］:

當(dāng)自變量x取第i個(gè)值時(shí)，它與因變量y中m個(gè)值對(duì)應(yīng)m個(gè)樣本頻數(shù)，在m個(gè)頻數(shù)中取最大值即為max_numx（i）；maxy為變量y的m個(gè)值中樣本頻數(shù)的最大值；Total為樣本總數(shù)目.

λxy相關(guān)系數(shù)的絕對(duì)值越大，則表示變量x和y之間線性關(guān)系緊密相關(guān)程度越大；λxy相關(guān)系數(shù)的絕對(duì)值越小，則表示變量x和y之間線性關(guān)系緊密相關(guān)程度越?。沪藊y相關(guān)系數(shù)的絕對(duì)值為0時(shí)，稱x和y不相關(guān).

2　基于權(quán)衡因子的決策樹優(yōu)化算法

本文首先將λ相關(guān)系數(shù)引入到ID3決策樹算法的研究領(lǐng)域中，提出基于ID3決策樹算法的λ相關(guān)系數(shù)——DT_λ相關(guān)系數(shù)；然后再結(jié)合DT_λ相關(guān)系數(shù)得到屬性的權(quán)衡因子；最后通過引入權(quán)衡因子對(duì)ID3算法進(jìn)行改進(jìn)，提出了基于權(quán)衡因子的決策樹優(yōu)化算 （Optimized algorithm of decision tree based on weighting factor）簡稱DTWF算法.

2.1DT_λ相關(guān)系數(shù)的引入

借鑒統(tǒng)計(jì)學(xué)中λ相關(guān)系數(shù)的定義，將變量間的λ相關(guān)系數(shù)引入到ID3算法中，使其成為定義條件屬性與決策屬性之間緊密相關(guān)程度的性能指標(biāo)，從而得到基于ID3決策樹的λ相關(guān)系數(shù)——DT_λ相關(guān)系數(shù).

設(shè)有知識(shí)表達(dá)系統(tǒng)I=（U，R，V，f），其中R=C∪D且C∪D=?，設(shè)C為條件屬性集C=｛A1，A2，…，Ap，…，An｝，D為決策類集合：D=｛D1，D2，…Di，…，Dm｝.其中，屬性Ap有屬性值｛S1，S2，…，Sj，…，Sk｝，k為Ap的屬性取值個(gè)數(shù)，Sj中屬于第i類的訓(xùn)練實(shí)例個(gè)數(shù)為sij，由此得到Ap的DT_λ矩陣.矩陣中第n+1行第j列表示決策屬性Di的總樣本個(gè)數(shù)，第i行第m+1列表示屬性Ap的總樣本個(gè)數(shù).

則屬性Ap與決策類D的相關(guān)系數(shù)DT_λ（Ap）定義為：

其中，max（si，1，si，2，…，si，m）表示條件屬性 Ap對(duì)應(yīng)決策屬性集合D中最多的樣本數(shù)，max（sn+1，1，sn+1，2，…，sn+1，m）表示訓(xùn)練集中，最多數(shù)的樣本屬于某一類的樣本數(shù)，因此DT_λ（Ap）中的分子不大于分母，即DT_λ（Ap）∈［0，1）.DT_λ（Ap）的值是ID3決策樹中衡量條件屬性與決策類之間相關(guān)性大小的指標(biāo)，DT_λ（Ap）的值越大，則條件屬性與決策類之間的相關(guān)程度越大.當(dāng)DT_λ（Ap）=0時(shí)，則條件屬性與決策類之間完全不相關(guān).

2.2DTWF算法的提出

ID3算法的主要缺陷在于其多值偏向問題，為克服該問題，Quinlan在提ID3算法后，又提出C4.5算法.C4.5算法雖在一定程度上能克服多值偏向問題，但又會(huì)出現(xiàn)C4.5算法少值偏向問題.良好的ID3改進(jìn)方法是既不偏向多值，又不少偏向少值，而DTWF算法的改進(jìn)工作正是以此為目標(biāo).

本文提出DTWF算法的改進(jìn)過程為：首先，根據(jù)信息增益公式（1）計(jì)算出每個(gè)條件屬性的信息增益值，然后再從條件屬性集C中挑選出信息增益值最大的屬性Ap和屬性取值個(gè)數(shù)最多的屬性Aq；最后比較屬性Ap和屬性Aq.若屬性Ap和屬性Aq為同一屬性，則表明在選擇分裂屬性的標(biāo)準(zhǔn)已偏向?qū)傩匀≈祩€(gè)數(shù)最多的屬性，即已經(jīng)產(chǎn)生了多值偏向問題，此時(shí)需要采用權(quán)衡因子對(duì)屬性Aq的劃分權(quán)重進(jìn)行重新權(quán)衡，以克服多值偏向問題；若屬性Aq和屬性Aq不為同一屬性，表明選擇屬性Ap作為分裂屬性不會(huì)出現(xiàn)多值偏向問題.因此可將屬性Ap的權(quán)衡因子WF（Ap）定義為：

通過引入權(quán)衡因子WF（Ap）對(duì)ID3算法公式（1）進(jìn)行改進(jìn)從而得到DTWF算法，DTWF算法對(duì)應(yīng)的信息增益公式為：

2.3DTWF算法偽代碼

算法：DTWF（D，attribute_list）

輸入：訓(xùn)練元組為D，屬性均已完成離散化操作，候選屬性集合為attribute_list.

輸出：一棵DTWF決策樹.

DTWF算法偽代碼為：

DTWF（D，attribute_list）

｛

創(chuàng)建節(jié)點(diǎn)N；

if D中所有子元組均屬于同一個(gè)類C then

return N作為葉節(jié)點(diǎn)，并將N標(biāo)記為類C；

if attribut_list為空then

return N作為葉節(jié)點(diǎn)，標(biāo)記為D中的多數(shù)類；//由該節(jié)點(diǎn)中樣本個(gè)數(shù)最多的類表示該節(jié)點(diǎn)的類別性質(zhì).

根據(jù)式（4）計(jì)算attribute_list中每個(gè)屬性的信息增益，并選擇出信息增益值最大的屬性Ap和取值個(gè)數(shù)最多的屬性Aq；

if Ap==Aq//此時(shí)屬性Ap具有多值偏向的趨勢，需要用權(quán)衡因子WF（Ap）重新權(quán)衡該屬性的屬性劃分權(quán)重

then

｛

根據(jù)式（8）計(jì)算屬性Ap與決策類D之間的相關(guān)系數(shù)DT_λ（Ap）；

令A(yù)p的權(quán)衡因子WF（Ap）=DT_λ（Ap）；

根據(jù)式（10）重新計(jì)算屬性Ap的信息增益；

｝

Else//此時(shí)屬性Ap無多值偏向的趨勢，該屬性的屬性劃分權(quán)重不需要被權(quán)衡因子進(jìn)行權(quán)衡操作

令屬性Ap的權(quán)衡因子WF（Ap）=0；

將使用公式（10）計(jì)算后的屬性Ap的新信息增益與其它候選屬性的信息增益進(jìn)行重新比較，并從中選取信息增益值最大的屬性作為分裂屬性splitting_attribute；

標(biāo)記節(jié)點(diǎn)N為splitting_attribute；

for each splitting_attribute中屬性值 Sj//根據(jù)splitting_attribute的屬性取值Sj劃分訓(xùn)練元組D

｛

由節(jié)點(diǎn)N分出splitting_attribute中一個(gè)屬性值為Sj的分枝，設(shè)Di是D中splitting_attr-ibute=Sj的數(shù)據(jù)元組集合；//進(jìn)行一次劃分

if Di為空then

由節(jié)點(diǎn)N分出分一個(gè)樹葉，標(biāo)記為D中的多數(shù)類；//由該節(jié)點(diǎn)中樣本個(gè)數(shù)最多的類代表該節(jié)點(diǎn)的類別性質(zhì)

else｛

由節(jié)點(diǎn)N分出分一個(gè)由 DTWF（Di，attribute_list減去splitting_attribute）返回的節(jié)點(diǎn)；

｝

｝

｝

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

3.1實(shí)驗(yàn)說明及評(píng)價(jià)標(biāo)準(zhǔn)

選取UCI上的6組標(biāo)準(zhǔn)數(shù)據(jù)集（如表1）進(jìn)行實(shí)驗(yàn)數(shù)據(jù)分析，其中前3組數(shù)據(jù)集的屬性取值個(gè)數(shù)相同，后3組數(shù)據(jù)集的屬性取值個(gè)數(shù)不相同.數(shù)據(jù)集中2/3樣本作為訓(xùn)練集，1/3作為測試集.采用文獻(xiàn)［15］方法對(duì)數(shù)據(jù)集中的連續(xù)性屬性進(jìn)行離散化操作.

表1　數(shù)據(jù)集

采用商務(wù)購車顧客數(shù)據(jù)庫（如表2）作為訓(xùn)練集D，對(duì)數(shù)據(jù)進(jìn)行選取、預(yù)處理和轉(zhuǎn)換操作后得到樣本集合，該集合包含4個(gè)條件屬性：喜歡的季節(jié)（含4個(gè)屬性值：春天、夏天、秋天、冬天）、是否商務(wù)人士（含2個(gè)屬性值：是、否）、收入（含3個(gè)屬性值：高、中、低）、駕車水平（含2個(gè)屬性值：良好、一般）.樣本集合根據(jù)類別屬性“是否買車”（含有2個(gè)屬性值：買、不買）進(jìn)行劃分.

本實(shí)驗(yàn)采用WEKA平臺(tái)，實(shí)驗(yàn)使用的計(jì)算機(jī)配置：CPU為酷睿i5 2300系列，主頻為2.8 GHz，內(nèi)存為4 GB，操作系統(tǒng)為win 7，仿真軟件為Matlab R2012a.

分類準(zhǔn)確率是分類問題中常用的評(píng)價(jià)標(biāo)準(zhǔn)，能體現(xiàn)出分類器對(duì)數(shù)據(jù)集的分類性能［16］.分類準(zhǔn)確率指分類器中被正確分類的樣本個(gè)數(shù)在總的檢驗(yàn)集中所占比例，其公式為［2］：

其中，s為總的樣本個(gè)數(shù)；TP表示分類器預(yù)測為正時(shí)，真實(shí)類別為正的樣本個(gè)數(shù)；FP表示分類器預(yù)測為正時(shí)，真實(shí)類別為負(fù)的樣本個(gè)數(shù)；TN表示分類器預(yù)測為負(fù)時(shí)，真實(shí)類別為負(fù)的樣本個(gè)數(shù)；FN表示分類器預(yù)測為負(fù)時(shí)，真實(shí)類別為負(fù)的樣本個(gè)數(shù).

表2　顧客數(shù)據(jù)庫訓(xùn)練集D

3.2DTWF算法的實(shí)例驗(yàn)證與分析

以訓(xùn)練集D為例，根據(jù)公式（1）計(jì)算ID3算法信息增益，根據(jù)公式（10）計(jì)算DTWF算法的信息增益.

3.2.1ID3算法及其對(duì)應(yīng)生成的決策樹

1）計(jì)算各個(gè)條件屬性的信息增益

則相應(yīng)屬性的信息增益為：

Gain（喜歡的季節(jié)）=Info（D）-Info駕車水平（D）= 0.946-0.546=0.400

Gain（是否商務(wù)人士）=Info（D）-Info是否商務(wù)人士（D）= 0.946-0.796=0.150

Gain（收入）=Info（D）-Info收入（D）=0.946-0.591= 0.355

Gain（駕車水平）=Info（D）-Info駕車水平（D）=0.946-0.796=0.150

2）ID3算法生成的決策樹

由以上各個(gè)屬性的信息增益結(jié)果比較可知：Gain（喜歡的季節(jié)）＞Gain（收入）>Gain（是否商務(wù)人士）=Gain（駕車水平）

因此，依照ID3算法分裂節(jié)點(diǎn)的原則將“喜歡的季節(jié)”屬性作為決策樹的根節(jié)點(diǎn)，對(duì)樣本元組進(jìn)行分類.對(duì)分類后形成的子集，用遞歸的方法對(duì)其計(jì)算熵值并進(jìn)行分裂屬性的選擇，最終的得到的決策樹如圖1所示.

圖1　ID3算法生成的決策樹

3.2.2DTWF算法及其對(duì)應(yīng)生成的決策樹

首先根據(jù)ID3算法公式（1）計(jì)算每個(gè)條件屬性的信息增益，并從中選出信息增益值最大的屬性Ap；其次再找出屬性取值個(gè)數(shù)最多的屬性Aq；然后比較屬性Ap和屬性Aq是否相同，并根據(jù)比較結(jié)果計(jì)算出的權(quán)衡因子，最后根據(jù)公式（10）計(jì)算出在DTWF算法下屬性Ap的信息增益.

1）信息增益值最大的屬性Ap與屬性取值個(gè)數(shù)最多的屬性Aq之間的比較.

訓(xùn)練集D中信息增益值最大的屬性為：A1“喜歡的季節(jié)”，而屬性取值個(gè)數(shù)最多的屬性為：Aq“喜歡的季節(jié)”，屬性A1和屬性Aq為同一屬性，則屬性A1具有多值偏向的趨勢，因此需要使用權(quán)衡因子對(duì)屬性A1的信息增益重新進(jìn)行權(quán)衡.

2）計(jì)算屬性Ap的權(quán)衡因子WF（Ap）

屬性A1與決策類D所對(duì)應(yīng)的DT_λ系數(shù)矩陣為：

根據(jù)公式（8）可得屬性A1的DT_λ（A1）值：

因此屬性A1的權(quán)衡因子WF（A1）=DT_λ（A1）= 1/2，屬性A1經(jīng)過權(quán)衡因子權(quán)衡后得到新的信息增益為：

3）DTWF算法生成的決策樹

將新屬性增益Gain（A1）new與其他屬性的信息增益進(jìn)行比較可知：

Gain（收入）＞Gain（是否商務(wù)人士）=Gain（駕車水平）＞Gain（喜歡的季節(jié)）

因此將“收入”作為DTWF算法生成的決策樹的根節(jié)點(diǎn)，對(duì)樣本元組進(jìn)行分類.對(duì)分類后形成的子集，用遞歸的基于權(quán)衡因子的方法對(duì)其計(jì)算熵值并進(jìn)行分裂屬性的選擇，最終的得到DTWF算法生成的決策樹如圖2所示.

圖2　D TWF算法生成的決策樹

3.2.3DTWF算法的實(shí)例分析與總結(jié)

1）由圖1和圖2對(duì)比發(fā)現(xiàn)：在訓(xùn)練集D中，屬性“喜歡的季節(jié)”屬性值個(gè)數(shù)最多，ID3算法多值偏向的特點(diǎn)使其成為決策樹的根節(jié)點(diǎn).“喜歡的季節(jié)”是一種主觀想法，不是購車的決定性因素，而在現(xiàn)實(shí)生活中，“收入”在一定程度上更能決定顧客是否購車.圖2可看出，DTWF算法令“喜歡的季節(jié)”屬性離決策樹根結(jié)點(diǎn)的距離變遠(yuǎn)，降低其重要性；令“收入”屬性作為決策樹根結(jié)點(diǎn)，提高其重要性，符合實(shí)際情況，因此DTWF算法在一定程度上克服了多值偏向問題.

2）在決策樹的構(gòu)建過程中，區(qū)別于用戶興趣度算法中用戶經(jīng)驗(yàn)的主觀參與，DTWF算法中的權(quán)衡因子是由訓(xùn)練集中屬性之間客觀的關(guān)系計(jì)算得到，因而權(quán)衡因子在一定程度上因無較多主觀的參與或干擾從而避免了決策結(jié)果受用戶主觀思想的影響.

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

3.3.1分類準(zhǔn)確率和葉子節(jié)點(diǎn)數(shù)的比較

在表2提供的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)數(shù)據(jù)測試，每一個(gè)數(shù)據(jù)集上進(jìn)行10次試驗(yàn).在分類準(zhǔn)確率的實(shí)驗(yàn)結(jié)果中，去掉最大數(shù)據(jù)和最小數(shù)據(jù)，再求出平均分類準(zhǔn)確率作為最終實(shí)驗(yàn)數(shù)據(jù)，可使實(shí)驗(yàn)結(jié)果具有普遍性.

將每一個(gè)數(shù)據(jù)集分成10個(gè)數(shù)據(jù)組，每個(gè)數(shù)據(jù)組中分別用ID3算法、文獻(xiàn)［10］算法和DTWF算法構(gòu)建決策樹，每個(gè)數(shù)據(jù)組上均構(gòu)建10次.在葉子節(jié)點(diǎn)數(shù)的實(shí)驗(yàn)結(jié)果中，去掉最大數(shù)據(jù)和最小數(shù)據(jù)，再求出平均葉子節(jié)點(diǎn)數(shù)作為該數(shù)據(jù)組的最終數(shù)據(jù).每個(gè)數(shù)據(jù)集里以數(shù)據(jù)組為最小單位進(jìn)行類似操作，求出其平均葉子節(jié)點(diǎn)數(shù)作為該數(shù)據(jù)集的最終實(shí)驗(yàn)數(shù)據(jù).實(shí)驗(yàn)結(jié)果如表3：

從表3的實(shí)驗(yàn)結(jié)果中可看出：

1）在葉子節(jié)點(diǎn)數(shù)方面，ID3算法與文獻(xiàn) ［6］算法、文獻(xiàn)［9］算法實(shí)驗(yàn)所得結(jié)果近似.

表3　實(shí)驗(yàn)結(jié)果

2）在分類準(zhǔn)確率方面，文獻(xiàn)［9］算法要優(yōu)于文獻(xiàn)［6］算法與ID3算法，而文獻(xiàn)［6］算法與ID3算法實(shí)驗(yàn)所得結(jié)果近似.

3）當(dāng)前3個(gè)數(shù)據(jù)集中屬性取值個(gè)數(shù)相同時(shí)，DTWF算法與ID3算法在分類準(zhǔn)確率和葉子節(jié)點(diǎn)數(shù)兩個(gè)方面進(jìn)行實(shí)驗(yàn)所的結(jié)果完全相同.產(chǎn)生這樣結(jié)果的原因是：數(shù)據(jù)集中屬性取值個(gè)數(shù)都相同，即不存在屬性取值個(gè)數(shù)最多的屬性，也不會(huì)產(chǎn)生多值偏向問題，因此無需使用權(quán)衡因子對(duì)某屬性的劃分權(quán)重進(jìn)行權(quán)衡.

4）當(dāng)后3個(gè)數(shù)據(jù)集中屬性取值個(gè)數(shù)不相同時(shí)，DTWF算法具有較高的平均分類準(zhǔn)確率和較少的平均葉子節(jié)點(diǎn)數(shù).

3.3.2算法時(shí)間復(fù)雜度的分析比較

傳統(tǒng)的ID3決策樹構(gòu)造方法，在構(gòu)造每一層結(jié)點(diǎn)的時(shí)候，都需要對(duì)訓(xùn)練數(shù)據(jù)掃描一次，因此其時(shí)間復(fù)雜度為：O（n×s×log2s）.文獻(xiàn)［6］算法、文獻(xiàn)［9］算法和本文提出的DTWF算法均在信息熵公式的基礎(chǔ)上，通過采用改變子元組劃分權(quán)重的方式，對(duì)ID3算法改進(jìn).因而文獻(xiàn)［6］算法、文獻(xiàn)［9］算法和本文提出的DTWF算法在復(fù)雜度數(shù)量級(jí)上還是不變，其時(shí)間復(fù)雜度也為：O（n×s×log2s）.

3.3.3決策樹生成時(shí)間的比較

在表2提供的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)數(shù)據(jù)測試，分別對(duì)ID3算法、文獻(xiàn)［6］算法、文獻(xiàn)［9］算法和DTWF算法進(jìn)行10次計(jì)算時(shí)間的測試，在實(shí)驗(yàn)結(jié)果中去掉最大數(shù)據(jù)和最小數(shù)據(jù)，再求出平均時(shí)間作為構(gòu)建決策樹模型所花費(fèi)的時(shí)間，實(shí)驗(yàn)結(jié)果如表4.

表4　算法建模速度比較/ms

從表4的實(shí)驗(yàn)結(jié)果中可看出：

1）從整體上看，ID3算法、文獻(xiàn)［6］算法、文獻(xiàn)［9］算法和DTWF算法構(gòu)建模花費(fèi)時(shí)間相差不大.

2）本文提出的DTWF算法在計(jì)算量上要略微復(fù)雜些，因此在構(gòu)建決策樹模型時(shí)，DTWF算法所花費(fèi)的時(shí)間略多于其它算法.

3.4實(shí)驗(yàn)結(jié)論

結(jié)合圖1、圖2、表3和表4可看出：①本文提出的DTWF算法可以克服多值偏向問題.②相比于ID3算法，文獻(xiàn)［6］的改進(jìn)算法雖能克服多值偏向問題，但在分類準(zhǔn)確率和葉子節(jié)點(diǎn)數(shù)這兩個(gè)方面沒有明顯改進(jìn)，改進(jìn)后ID3算法的效率未得到提高；②在時(shí)間復(fù)雜度上的數(shù)量級(jí)上，DTWF算法和ID3算法保持一致；在計(jì)算量上，DTWF算法要比其它三種算法要略微復(fù)雜些，因此DTWF算法決策樹建模所花費(fèi)的時(shí)間略多于其它算法；從整體上看，DTWF算法與其它算法構(gòu)建?；ㄙM(fèi)時(shí)間相差不大.④當(dāng)數(shù)據(jù)集中屬性取值個(gè)數(shù)相同時(shí)，即不存在多值偏向的趨勢時(shí)，本文提出DTWF算法與ID3算法相同；當(dāng)數(shù)據(jù)集中屬性取值個(gè)數(shù)不相同時(shí)，即存在多值偏向的趨勢時(shí)，與ID3算法、文獻(xiàn)［6］算法和文獻(xiàn)［9］算法相比較，本文提出DTWF算法具有較高的分類準(zhǔn)確率，在算法生成決策樹規(guī)模上，DTWF算法也要優(yōu)于其它算法，因?yàn)镈TWF算法具有更少的葉子節(jié)點(diǎn)數(shù)，此外還能克服ID3算法的多值偏向問題.

4　結(jié)束語

本文結(jié)合λ相關(guān)系數(shù)提出了DTWF算法，根據(jù)屬性之間的依賴關(guān)系得到屬性的權(quán)衡因子，通過用權(quán)衡因子代替依賴先驗(yàn)知識(shí)的用戶興趣度參數(shù)，以克服ID3算法的多值偏向問題.DTWF算法首先通過判斷數(shù)據(jù)集是否存在多值偏向趨勢，繼而客觀地計(jì)算出屬性的權(quán)衡因子；然后再根據(jù)得到的權(quán)衡因子對(duì)某屬性的子元組劃分權(quán)重進(jìn)行重新權(quán)衡，并將用DTWF算法得到的新信息增益與其它屬性的信息增益進(jìn)行重新比較；最后從中選取具有最大信息增益值的屬性作為分裂屬性.DTWF算法既不受屬性取值個(gè)數(shù)的影響，也不要求用戶需要先驗(yàn)知識(shí)或領(lǐng)域知識(shí)，又能避免決策結(jié)果受到主觀因素的干擾和影響.實(shí)驗(yàn)結(jié)果分析表明，相比于原ID3算法以及文獻(xiàn)［6］基于用戶興趣度的改進(jìn)算法，當(dāng)數(shù)據(jù)集中存在多值偏向的趨勢時(shí)，DTWF算法具有更高的平均分類精確度和較少的平均葉子節(jié)點(diǎn)數(shù).UCI上大部分?jǐn)?shù)據(jù)集的屬性取值個(gè)數(shù)基本不相同，屬性取值個(gè)數(shù)相同的情況占少數(shù)，因此在大部分情況下，DTWF算法要優(yōu)于ID3算法和文獻(xiàn)［6］算法及其相關(guān)類似改進(jìn)算法.

［1］朱明.數(shù)據(jù)挖掘［M］.中國科學(xué)技術(shù)大學(xué)出版社，2002：67-68.

［2］韓家煒，堪博.數(shù)據(jù)挖掘概念與技術(shù)［M］.2版.機(jī)械工業(yè)出版社，2007:188-189.

［3］Quinlan J R.Induction of decision trees［J］.Machine learning，1986，1（1）:81-106.

［4］王苗，柴瑞敏.一種改進(jìn)的決策樹分類屬性選擇方法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（8）:127-129.

［5］王永梅，胡學(xué)鋼.決策樹中ID3算法的研究［J］.安徽大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，35（3）:71-75.

［6］曲開社，成文麗，王俊紅.ID3算法的一種改進(jìn)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2003，39（25）:104-107.

［7］劉建粉，史永昌.基于用戶興趣分類優(yōu)化的聚類模型仿真［J］.微電子學(xué)與計(jì)算機(jī)，2014，31（5）:171-174.

［8］王永梅，肖中新.改進(jìn)決策樹算法在水環(huán)境質(zhì)量評(píng)價(jià)中的應(yīng)用［J］.合肥學(xué)院學(xué)報(bào)（自然科學(xué)版），2014，24（1）:35-39.

［9］葉明全，胡學(xué)鋼.一種基于灰色關(guān)聯(lián)度的決策樹改進(jìn)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（32）:171-173.

［10］王建偉，王鑫，許憲東，等.改進(jìn)的ID3算法在遠(yuǎn)程教學(xué)系統(tǒng)中的應(yīng)用［J］.黑龍江工程學(xué)院學(xué)報(bào)，2014，28（1）：67-70.

［11］梁前德.統(tǒng)計(jì)學(xué)［M］.2版.北京:高等教育出版社，2008.

［12］朱顥東.ID3算法的改進(jìn)和簡化［J］.上海交通大學(xué)學(xué)報(bào)，2010（7）: 883-886.

［13］喻金平，黃細(xì)妹，李康順.基于一種新的屬性選擇標(biāo)準(zhǔn)的 ID3改進(jìn)算法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（8）:2895-2898.

［14］解亞萍.基于統(tǒng)計(jì)相關(guān)系數(shù)的數(shù)據(jù)離散化方法［J］.計(jì)算機(jī)應(yīng)用，2011，31（5）:1409-1412.

［15］Hu X，Cercone N.Data mining via generalization，Discrimination and rough set feature selection［J］.Knowledge and Information System:An International Journal，1999，1（1）:21-27.

［16］武麗芬.改進(jìn)的決策樹算法在文理分科中的應(yīng)用研究［J］.微計(jì)算機(jī)應(yīng)用，2011，32（8）:7-12.

Optimized algorithm of decision tree based on weighting factor

DONG Yuehua，LIU Li
（School of Information Engineering，JiangxiUniversity of Science and Technology，Ganzhou 341000，China）

Through the analysis of the issues ofmultivalue bias in the ID3 algorithm and subjectivity of the optimized traditional ID3 algorithm，an improved algorithm of decision tree based on weighting factor is put forward.The new algorithm introduces the weight factor that reflects the mutual relationship between the attributes.The ID3 algorithm is improved by redistricting the weight of attributes which hasmost values.The experiments on UCIdata sets show that the optimization ID3 algorithm can overcomemultivalue bias when the values of different attributes in data set are not the same.This algorithm not only improves the accuracy of average classification，but also reduces the number of average leaf nodes in the process of constructing a decision tree.

ID3 algorithm；multivalue bias；weighting factor；decision tree；weight

TP301.6

A

2095-3046（2015）05-0090-08

10.13265/j.cnki.jxlgdxxb.2015.05.016

2015-04-13

國家自然科學(xué)基金資助項(xiàng)目（71061008）

董躍華（1964-），女，副教授，主要從事數(shù)據(jù)挖掘、軟件工程、軟件測試等方面研究，E-mail：4490367@qq.com.