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

董躍華，　劉力

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

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

董躍華，劉力

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

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

ID3算法；多值偏向；權衡因子；決策樹；權重

0　引言

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

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

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

1　基本理論

1.1ID3算法

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

其中：

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

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

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

對應的信息增益公式（1）也將改進為：

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

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

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

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

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

1.3λ相關系數(shù)

統(tǒng)計學中通常使用相關系數(shù)作為衡量變量之間密切相關程度的評價標準.由于被考量的變量存在不同的特性，因此變量對應表示的相關系數(shù)也存在多個種類，例如可用λ系數(shù)測定兩個定類數(shù)據(jù)之間的密切相關程度，可用γ系數(shù)和皮斯爾曼等級相關系數(shù)測量兩個定序數(shù)據(jù)之間的密切相關程度，可用ρ相關系數(shù)測量兩個普通變量之間的密切相關程度［11］.

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

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

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

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

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

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

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

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

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

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

2.2DTWF算法的提出

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

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

通過引入權衡因子WF（Ap）對ID3算法公式（1）進行改進從而得到DTWF算法，DTWF算法對應的信息增益公式為：

2.3DTWF算法偽代碼

算法：DTWF（D，attribute_list）

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

輸出：一棵DTWF決策樹.

DTWF算法偽代碼為：

DTWF（D，attribute_list）

｛

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

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

return N作為葉節(jié)點，并將N標記為類C；

if attribut_list為空then

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

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

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

then

｛

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

令Ap的權衡因子WF（Ap）=DT_λ（Ap）；

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

｝

Else//此時屬性Ap無多值偏向的趨勢，該屬性的屬性劃分權重不需要被權衡因子進行權衡操作

令屬性Ap的權衡因子WF（Ap）=0；

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

標記節(jié)點N為splitting_attribute；

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

｛

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

if Di為空then

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

else｛

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

｝

｝

｝

3　實驗及結果分析

3.1實驗說明及評價標準

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

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

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

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

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

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

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

3.2DTWF算法的實例驗證與分析

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

3.2.1ID3算法及其對應生成的決策樹

1）計算各個條件屬性的信息增益

則相應屬性的信息增益為：

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

Gain（是否商務人士）=Info（D）-Info是否商務人士（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算法生成的決策樹

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

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

圖1　ID3算法生成的決策樹

3.2.2DTWF算法及其對應生成的決策樹

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

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

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

2）計算屬性Ap的權衡因子WF（Ap）

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

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

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

3）DTWF算法生成的決策樹

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

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

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

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

3.2.3DTWF算法的實例分析與總結

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

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

3.3實驗驗證及分析

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

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

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

從表3的實驗結果中可看出：

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

表3　實驗結果

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

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

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

3.3.2算法時間復雜度的分析比較

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

3.3.3決策樹生成時間的比較

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

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

從表4的實驗結果中可看出：

1）從整體上看，ID3算法、文獻［6］算法、文獻［9］算法和DTWF算法構建?；ㄙM時間相差不大.

2）本文提出的DTWF算法在計算量上要略微復雜些，因此在構建決策樹模型時，DTWF算法所花費的時間略多于其它算法.

3.4實驗結論

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

4　結束語

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

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

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

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

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

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

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

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

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

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

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

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

［12］朱顥東.ID3算法的改進和簡化［J］.上海交通大學學報，2010（7）: 883-886.

［13］喻金平，黃細妹，李康順.基于一種新的屬性選擇標準的 ID3改進算法［J］.計算機應用研究，2012，29（8）:2895-2898.

［14］解亞萍.基于統(tǒng)計相關系數(shù)的數(shù)據(jù)離散化方法［J］.計算機應用，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］.微計算機應用，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

國家自然科學基金資助項目（71061008）

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