基于均衡系數(shù)的決策樹優(yōu)化算法

董躍華　劉　力

1(江西理工大學(xué)信息工程學(xué)院　江西 贛州 341000)2(江西理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系　江西 贛州 341000)

?

基于均衡系數(shù)的決策樹優(yōu)化算法

董躍華1劉力2

1(江西理工大學(xué)信息工程學(xué)院江西 贛州 341000)2(江西理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系江西 贛州 341000)

摘要針對(duì)ID3算法多值偏向及誤分類代價(jià)被忽視的問題，結(jié)合屬性相似度和代價(jià)敏感學(xué)習(xí)，提出基于均衡系數(shù)的決策樹優(yōu)化算法。該算法既克服了多值偏向，又考慮了誤分類代價(jià)問題。首先引進(jìn)屬性相似度和性價(jià)比值兩者的均衡系數(shù)，對(duì)ID3算法進(jìn)行改進(jìn)；然后運(yùn)用麥克勞林公式對(duì)ID3算法進(jìn)行公式簡化；最后將算法改進(jìn)和公式簡化相結(jié)合，得到基于均衡系數(shù)的決策樹優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明，基于均衡系數(shù)的決策樹優(yōu)化算法，既能夠提高分類精度，縮短決策樹生成時(shí)間，又能考慮代價(jià)問題并降低誤分類代價(jià)，還能克服多值偏向問題。

關(guān)鍵詞ID3算法屬性相似度代價(jià)敏感學(xué)習(xí)決策樹均衡系數(shù)

0引言

數(shù)據(jù)分類是數(shù)據(jù)挖掘中重要的研究方法之一，其中有決策樹分類器、貝葉斯分類器等基本技術(shù)。目前各類決策樹算法中，ID3算法的影響最大，但I(xiàn)D3算法存在多值偏向等問題。針對(duì)ID3算法的多值偏向問題，自Quinlan提出C4.5算法[1]以來，許多學(xué)者進(jìn)行相關(guān)的改進(jìn)工作：文獻(xiàn)[2]根據(jù)概率統(tǒng)計(jì)中條件概率的大小劃分屬性；文獻(xiàn)[3,4]選取關(guān)聯(lián)度值最大的屬性作為分裂屬性；文獻(xiàn)[5-8]將粗糙集理論中的屬性重要度或?qū)傩砸蕾嚩茸鳛檫x擇分裂屬性的標(biāo)準(zhǔn)；文獻(xiàn)[9,10]將屬性相似度作為選擇分裂屬性的標(biāo)準(zhǔn)。在一定程度上，文獻(xiàn)[2-10]引入新的屬性分裂標(biāo)準(zhǔn)雖能克服多值偏向，但新的選擇標(biāo)準(zhǔn)意味著會(huì)涉及統(tǒng)計(jì)學(xué)、粗糙集等其他領(lǐng)域知識(shí)，因?yàn)槠洳煌谛畔㈧乩碚摰挠?jì)算方式，所以在分類準(zhǔn)確率上會(huì)低于ID3算法。

針對(duì)ID3算法忽視因誤分類而產(chǎn)生的代價(jià)問題，除了近來一些學(xué)者將誤分類代價(jià)最小化作為分類效果新的衡量標(biāo)準(zhǔn)，并提出代價(jià)敏感學(xué)習(xí)CSL(Cost-Sensitive Learning)[11]之外，相關(guān)學(xué)者也進(jìn)行了一些研究工作：文獻(xiàn)[12]在CSL的基礎(chǔ)上，提出基于誤分類代價(jià)和測試代價(jià)的決策樹算法，該算法雖考慮了代價(jià)問題，但卻忽視屬性自身的分類能力；文獻(xiàn)[13,14]在文獻(xiàn)[12]的基礎(chǔ)上進(jìn)行改進(jìn)，提出了基于代價(jià)問題與信息熵公式相結(jié)合的決策樹算法，該算法雖兼顧了代價(jià)問題和屬性自身的分類能力，但仍存在多值偏向問題。

本文在文獻(xiàn)[9]和文獻(xiàn)[14]的基礎(chǔ)上,結(jié)合屬性相似度和代價(jià)敏感學(xué)習(xí)，提出了基于均衡系數(shù)的決策樹優(yōu)化算法，通過引入屬性相似度和性價(jià)比值兩者的均衡系數(shù)，對(duì)ID3算法改進(jìn)。實(shí)驗(yàn)結(jié)果表明，基于均衡系數(shù)的決策樹優(yōu)化算法，能夠克服多值偏向問題，提高分類精度，兼顧代價(jià)問題并降低誤分類代價(jià)。

1ID3算法

1.1ID3算法的基本思想

設(shè)訓(xùn)練集S有s個(gè)樣本，將訓(xùn)練集分成m個(gè)類，第i類的實(shí)例個(gè)數(shù)為si。選擇屬性Ai劃分訓(xùn)練集S，設(shè)屬性Ai有屬性值{S1，S2，…，Sj，…，Sk}，Sj中屬于第i類的訓(xùn)練實(shí)例個(gè)數(shù)為sij，則得到劃分屬性Ai的信息增益為[15]：

Gain(Ai,S)=Info(S)-InfoAi(S)

(1)

其中：

(2)

(3)

(4)

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

1.2ID3算法的缺陷

ID3算法雖是常用的分類算法，但其仍存在一些缺陷：

(1) 信息熵的計(jì)算方式使ID3算法的屬性選擇容易偏向于取值較多的屬性，但有較多屬性值的屬性不一定是當(dāng)前最佳分裂屬性；

(2) 分類過程中存在誤分類情況，而ID3算法卻忽視了因誤分類而產(chǎn)生的代價(jià)問題[16]；

(3) 數(shù)據(jù)集中樣本數(shù)增多時(shí)，算法對(duì)應(yīng)計(jì)算量的增長幅度變大。

針對(duì)ID3算法的缺陷，可在多值偏向、誤分類代價(jià)、信息熵公式簡化方面對(duì)ID3算法進(jìn)行改進(jìn)。

2ID3算法相關(guān)的改進(jìn)研究

針對(duì)多值偏向、誤分類代價(jià)、信息熵公式簡化這3個(gè)方面，相關(guān)專家學(xué)者對(duì)ID3算法進(jìn)行改進(jìn)并分別提出3種改進(jìn)算法。本文的主要工作即為：通過研究3種改進(jìn)算法的優(yōu)缺點(diǎn)，尋找一種新的改進(jìn)算法，使新的改進(jìn)算法在繼承3種改進(jìn)算法優(yōu)點(diǎn)的同時(shí)，也要克服其不足之處。

2.1針對(duì)多值偏向的ID3算法改進(jìn)

文獻(xiàn)[9]提出基于屬性相似度的決策樹改進(jìn)算法，并表明將屬性相似度作為屬性選取標(biāo)準(zhǔn)可克服多值偏向問題。

2.1.1基于屬性相似度的決策樹改進(jìn)算法的原理

文獻(xiàn)[9]中參照知識(shí)粒度[17]的定義將條件屬性Ai與決策屬性D的屬性相似度定義為：

(5)

其中Ai為條件屬性集合C中的元素，C為：C={A1,A2,…,Ai,…,An}，D為決策屬性集合：D={D1,D2,…,Dm}。元素fi，j表示屬性Ai中屬于Dj類樣本個(gè)數(shù)，可用m+1行n+1列矩陣表示，矩陣中第j行第n+1列表示決策屬性Dj的總樣本個(gè)數(shù)，第m+1行第i列表示屬性Ai的總樣本個(gè)數(shù)。

式(5)中屬性相似度值S(D,Ai)的大小表示條件屬性Ai與決策屬性D之間相似度程度的大小。

2.1.2基于屬性相似度的決策樹改進(jìn)算法的不足

(1) 因?qū)傩韵嗨贫让撾x信息熵理論而導(dǎo)致其在分類準(zhǔn)確率上低于ID3算法。

(2) 未考慮因誤分類而產(chǎn)生的代價(jià)問題。

2.2針對(duì)誤分類代價(jià)的ID3算法改進(jìn)

文獻(xiàn)[14]提出一種基于代價(jià)敏感學(xué)習(xí)的決策樹改進(jìn)算法，該算法將信息熵理論與代價(jià)敏感學(xué)習(xí)相結(jié)合，在繼承ID3算法較高分類準(zhǔn)確率的同時(shí)，也考慮了誤分類代價(jià)問題。

2.2.1基于代價(jià)敏感學(xué)習(xí)的決策樹改進(jìn)算法的原理

若選擇Ai作為分裂屬性且當(dāng)前決策樹結(jié)點(diǎn)Node為正例結(jié)點(diǎn)，裂后有n個(gè)子屬性{S1,S2,…,Si,…,Sn}，對(duì)應(yīng)n個(gè)子節(jié)點(diǎn)(Node1,Node2,…,Nodei,…,Noden,),子結(jié)點(diǎn)Nodei包含xi個(gè)正例和yi個(gè)反例，令前r個(gè)子結(jié)點(diǎn)為正例結(jié)點(diǎn)，后(n-r)個(gè)子結(jié)點(diǎn)為反例結(jié)點(diǎn)[18]。屬性Ai的代價(jià)性能比值Cost_ratio(Ai)定義為[19]：

(6)

其中，Cost(Ai)為Ai未分裂時(shí)當(dāng)前結(jié)點(diǎn)Node的誤分類代價(jià)；FP為錯(cuò)誤正例造成的誤分類代價(jià)，F(xiàn)N為錯(cuò)誤反例所造成的誤分類代價(jià)，T_Cost(Ai)為獲取屬性Ai信息時(shí)所需付出的測試代價(jià)，分母加1是為防止某個(gè)屬性測試代價(jià)為0時(shí)而導(dǎo)致計(jì)算錯(cuò)誤出現(xiàn)。

2.2.2基于代價(jià)敏感學(xué)習(xí)的決策樹改進(jìn)算法的不足

該算法仍存在公式計(jì)算量較為龐大的問題以及多值偏向的問題。

2.3針對(duì)信息熵公式簡化的ID3算法改進(jìn)

文獻(xiàn)[20,21]通過運(yùn)用等價(jià)無窮小的方式，令I(lǐng)D3算法公式中的log對(duì)數(shù)運(yùn)算轉(zhuǎn)變?yōu)樗膭t運(yùn)算，以達(dá)到簡化信息熵公式的目的。

2.3.1信息熵公式簡化的原理

含拉格朗日型余項(xiàng)的麥克勞林公式定義為[22]：

(7)

由此得到近似公式：

(8)

由此可得：

(9)

當(dāng)x趨向于0時(shí)，可得等價(jià)無窮小變換：

ln(1+x)～x

2.3.2等價(jià)無窮小簡化信息熵公式的不足

當(dāng)自變量必須趨向于0時(shí)，才可使用等價(jià)無窮小進(jìn)行等價(jià)變換。當(dāng)自變量不趨向于0時(shí)，使用等價(jià)無窮小變換會(huì)導(dǎo)致簡化后的公式比原信息熵公式的精度低。

3基于均衡系數(shù)的決策樹優(yōu)化算法

3.1基于均衡系數(shù)的決策樹優(yōu)化算法的思路

3.1.1改進(jìn)基于屬性相似度和代價(jià)敏感學(xué)習(xí)決策樹算法的不足

基于屬性相似度的決策樹改進(jìn)算法可克服多值偏向問題；基于代價(jià)敏感學(xué)習(xí)的決策樹改進(jìn)算法可克服因脫離信息熵理論而導(dǎo)致分類準(zhǔn)確率低下的問題，也能克服誤分類代價(jià)被忽略的問題，因而將兩種決策樹改進(jìn)算法相結(jié)合可彌補(bǔ)兩者自身的不足。本文通過運(yùn)用等效電阻原理，將文獻(xiàn)[9]的屬性相似度和文獻(xiàn)[14]的代價(jià)性能比值相結(jié)合得到新的指標(biāo)系數(shù)——均衡系數(shù)，均衡系數(shù)能夠同時(shí)繼承兩種決策樹改進(jìn)算法的優(yōu)勢(shì)，因而能夠同時(shí)兼顧多值偏向和誤分類代價(jià)被忽視問題。最后將均衡系數(shù)引入信息熵公式以完成對(duì)ID3算法的改進(jìn)。

3.1.2改進(jìn)等價(jià)無窮小簡化信息熵公式的不足

當(dāng)自變量不會(huì)趨向于0時(shí)，使用等價(jià)無窮小變換會(huì)導(dǎo)致簡化后的公式精度降低。信息熵公式的值的大小在0和1之間，因而在式(9)的基礎(chǔ)上可得：

當(dāng)x∈(0,1)時(shí)：

(10)

通過運(yùn)用公式(10)對(duì)信息熵公式中的對(duì)數(shù)運(yùn)算進(jìn)行近似轉(zhuǎn)換，以完成信息熵公式的簡化。

3.1.3DTEC算法

本文針對(duì)“多值偏向、誤分類代價(jià)被忽視問題”和“信息熵計(jì)算公式”兩個(gè)方面，將改進(jìn)基于屬性相似度和代價(jià)敏感學(xué)習(xí)決策樹算法的不足、改進(jìn)等價(jià)無窮小簡化信息熵公式的不足兩部分的工作相結(jié)合，分別對(duì)ID3算法進(jìn)行算法改進(jìn)和公式簡化，提出了基于均衡系數(shù)的決策樹優(yōu)化算法，簡稱DTEC算法。

3.2ID3算法的改進(jìn)

3.2.1均衡系數(shù)的引入1) 代價(jià)性能比值的改進(jìn)

誤分類代價(jià)為專家給的相對(duì)值，測試代價(jià)多以貨幣為單位，代價(jià)性能比值中分子與分母兩者的值域顯然不在同一范圍，這會(huì)導(dǎo)致比值不準(zhǔn)確并產(chǎn)生誤差。為克服該問題，可采用規(guī)范化方法對(duì)性能比值進(jìn)行改進(jìn)，將測試代價(jià)規(guī)范化至誤分類代價(jià)的取值區(qū)間，規(guī)范化后的測試代價(jià)為T_NewCost(Ai)：

(max[Cost(Ai)]-min[Cost(Ai)])+min[Cost(Ai)]

(11)

則改進(jìn)后的代價(jià)性能比值New_Cost_ratio(Ai)為：

(12)

式(12)中的分子和分母已處于同一數(shù)量級(jí)，可避免出現(xiàn)比值結(jié)果偏向分子和分母中數(shù)量級(jí)較大者的數(shù)量級(jí)偏向問題。

2) 均衡系數(shù)的引入

電路中有等效電阻原理：電阻R1和R2并聯(lián)，等價(jià)于串聯(lián)入等效電阻R′。電阻R1、R2、R′兩端電壓均為U，通過電流分別為IR1、IR2、IR′。由此可推導(dǎo)出如下關(guān)系：

(13)

屬性相似度和性價(jià)比值分別對(duì)應(yīng)電阻R1和R2，均衡系數(shù)對(duì)應(yīng)電阻R′，運(yùn)用等效電阻原理可將本文提出的均衡系數(shù)R(Ai)可定義為：

(14)

均衡系數(shù)R(Ai)的作用效果，等效于屬性相似度和性價(jià)比值兩者指標(biāo)盡可能取較優(yōu)值，同時(shí)令兩者共同作用的效果達(dá)到最優(yōu)值。

3.2.2引入均衡系數(shù)對(duì)ID3算法的改進(jìn)

均衡系數(shù)對(duì)ID3算法式(1)進(jìn)行改進(jìn)后，得到新的信息增益式(15)：

Gain(Ai,S)New=Gain(Ai,S)×R(Ai)

=[Info(S)-InfoAi(S)]×R(Ai)

(15)

令改進(jìn)后的信息增益Gain(Ai,S)new，作為屬性分裂的新標(biāo)準(zhǔn)。新的屬性分裂標(biāo)準(zhǔn)Gain(Ai,S)new既能克服ID3算法的多值偏向問題，又能使選擇的分裂屬性具有較小的誤分類代價(jià)。

3.2.3ID3算法改進(jìn)后的多值偏向分析1) ID3算法多值偏向分析

(16)

由此可知式(18)的恒成立是造成多向偏值問題的本質(zhì)，所以要解決多向偏值問題只要避免式(16)恒成立即可。

2) ID3算法被改進(jìn)后的多值偏向分析

(17)

(18)

3.3信息熵公式的簡化

將ID3算法的信息增益公式完全展開后，變形為式(19)：

(19)

式(19)中常數(shù)m為訓(xùn)練集類別數(shù)，Info(S)為一個(gè)定值，因此式(19)只保留后一項(xiàng)也不會(huì)影響最終比較結(jié)果，則取后一項(xiàng)可得式(20)：

(20)

從式(20)中可看出：對(duì)數(shù)運(yùn)算是計(jì)算中主要的耗時(shí)部分，因而消去對(duì)數(shù)運(yùn)算能夠降低計(jì)算量并提高計(jì)算效率。

sj中屬于第i類的訓(xùn)練實(shí)例個(gè)數(shù)為sij，pij是Sj中屬于第i類的概率，pij=sij/sj，且s1j+...+smj=sj，因此式(20)可進(jìn)行如下轉(zhuǎn)化：

近似式(10)比等價(jià)無窮小公式ln(1+x)≈x的精度要高。使用近似簡化式(10)可進(jìn)一步化簡為：

Gain(Ai)2

ln2和樣本個(gè)數(shù)s均為常數(shù)項(xiàng)，去掉后不影響結(jié)果的比較，將其去掉后進(jìn)一步簡化得到式(21)：

(21)

式(21)中的較為耗時(shí)的log對(duì)數(shù)運(yùn)算已消除，公式完全由加減乘除四種基本運(yùn)算組成，計(jì)算量降低且計(jì)算效率得到提高。

3.4DTEC算法的提出

DTEC算法包括均衡系數(shù)的引入、ID3算法改進(jìn)和ID3算法公式簡化三個(gè)部分的工作，將均衡系數(shù)式(14)、ID3算法改進(jìn)式(15)和ID3算法簡化式(21)相結(jié)合得到DTEC算法式(22)：

(22)

DTEC算法采用式(22)作為新的屬性選擇標(biāo)準(zhǔn)。DTEC算法既能克服多值偏向，考慮代價(jià)問題并降低誤分類代價(jià)，又能簡化ID3算法公式，降低計(jì)算量并提高計(jì)算效率。

3.5DTEC算法描述

輸入：訓(xùn)練樣本集S(樣本中的屬性值均進(jìn)行離散化操作),C為條件屬性集合，屬性Ai∈C；D為決策屬性集合。

輸出：DTEC決策樹。

步驟1計(jì)算條件屬性Ai與決策屬性D的屬性相似度值S(D,Ai)；

步驟2在屬性集合C中，計(jì)算屬性Ai對(duì)應(yīng)的代價(jià)性能比值New_Cost_ratio(Ai)′；

步驟3計(jì)算屬性Ai對(duì)應(yīng)屬性相似度和性價(jià)比值兩者的均衡系數(shù)R(Ai)；

步驟4引入均衡系數(shù)R(Ai)對(duì)ID3算法進(jìn)行改進(jìn)，得到屬性分裂標(biāo)準(zhǔn)Gain(Ai,S)New；

步驟5利用麥克勞林展開式對(duì)ID3算法公式進(jìn)行簡化，得到屬性分裂標(biāo)準(zhǔn)Gain(Ai)3；

步驟7按照式(22)分別計(jì)算各個(gè)屬性對(duì)應(yīng)的熵值，選取熵值最大的屬性作為決策樹的根節(jié)點(diǎn)，對(duì)樣本元組進(jìn)行分類。對(duì)分類后形成的子集，用遞歸的方法，計(jì)算熵值并按照熵值的大小進(jìn)行屬性分裂，直到DTEC決策樹構(gòu)建完成。

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

4.1實(shí)驗(yàn)環(huán)境

4.1.1實(shí)驗(yàn)采用工具

1) 實(shí)驗(yàn)采用的數(shù)據(jù)集

本實(shí)驗(yàn)在標(biāo)準(zhǔn)數(shù)據(jù)集UCI上進(jìn)行，采用UCI提供的若干個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集(如表1所示)進(jìn)行數(shù)據(jù)分析。

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

2) 實(shí)驗(yàn)采用的實(shí)例訓(xùn)練集

采用商務(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)行劃分。

表2　商務(wù)購車顧客數(shù)據(jù)庫訓(xùn)練集D

3) 實(shí)驗(yàn)采用平臺(tái)

本實(shí)驗(yàn)采用WEKA平臺(tái)，WEKA是一款免費(fèi)且基于JAVA環(huán)境下開源的機(jī)器學(xué)習(xí)以及數(shù)據(jù)挖掘軟件。由于WEKA屬于開源軟件，WEKA中的ID3算法位于weka.classifiers.trees包中，因此改進(jìn)后的ID3算法只要符合其接口規(guī)范，就可以將新算法嵌入到WEKA中并調(diào)試運(yùn)行。

本實(shí)驗(yàn)將ID3的WEKA源代碼導(dǎo)入NetBeans IDE 8.0 RC中并添加DTEC算法源代碼，然后在NetBeans IDE 8.0 RC中分別編譯ID3算法和DTEC算法程序。

4) 實(shí)驗(yàn)采用設(shè)備配置

實(shí)驗(yàn)所采用計(jì)算機(jī)配置為：CPU為酷睿i5 2300系列，主頻為2.8GHz，內(nèi)存為4G，操作系統(tǒng)為Win 7。

5) 實(shí)驗(yàn)采用仿真軟件

本實(shí)驗(yàn)將Matlab 2012a作為繪圖仿真軟件。

4.1.2實(shí)驗(yàn)初始條件

(1) 將表1數(shù)據(jù)集中2/3的樣本作為訓(xùn)練集，1/3的樣本作為測試集，采用文獻(xiàn)[24]中的方法對(duì)數(shù)據(jù)集中連續(xù)性屬性進(jìn)行離散化操作。

(2) 令各個(gè)數(shù)據(jù)集處在相同的軟硬件環(huán)境下，并使各個(gè)數(shù)據(jù)集的測試代價(jià)都相同。

(3) 分類準(zhǔn)確率實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

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

(23)

其中s為總的樣本個(gè)數(shù)，m為分類類別個(gè)數(shù)，si為訓(xùn)練集中屬于第i類的實(shí)例個(gè)數(shù)。

(4) 誤分類代價(jià)實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

評(píng)定標(biāo)準(zhǔn)：使用誤分類代價(jià)比值w進(jìn)行評(píng)價(jià)。誤分類代價(jià)比值w定義為：

(24)

其中，Cost表示誤分類代價(jià)，T_Cost表示測試代價(jià)，誤分類代價(jià)比值w越大，表明在一個(gè)基本單位內(nèi)的測試代價(jià)，所均分到的誤分類代價(jià)越大。同時(shí)表明當(dāng)誤分類代價(jià)作為分類效果的衡量標(biāo)準(zhǔn)時(shí)，分類效果較差；當(dāng)誤分類代價(jià)比值w較小時(shí)，則說明分類效果較好。

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

以訓(xùn)練集D為例，根據(jù)式(1)計(jì)算ID3算法信息增益，根據(jù)式(22)計(jì)算DTEC算法的信息增益，根據(jù)式(21)計(jì)算ID3算法公式簡化后的信息增益，最后按照決策樹建樹規(guī)則，構(gòu)建各自的決策樹，分別如圖1、圖2、圖3所示。

圖1　原ID3算法生成的決策樹

圖2　DTEC算法生成的決策樹

圖3　在原ID3基礎(chǔ)上公式簡化后生成的決策樹

圖1、圖2、圖3綜合分析發(fā)現(xiàn)：

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

(2) 比較圖1和圖3。由圖3可看出，ID3算法公式簡化后生成的決策樹與原ID3算法生成的決策樹完全一致。表明本文中對(duì)原ID3算法進(jìn)行近似轉(zhuǎn)化的簡化公式精度較高，能夠與原ID3算法生成的決策樹基本保持一致。

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

4.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算法、C4.5算法、文獻(xiàn)[9]算法、文獻(xiàn)[14]算法和DTEC算法構(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、表4所示。

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

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

從表3、表4的實(shí)驗(yàn)結(jié)果中可看出:相比于ID3算法、文獻(xiàn)[14]算法、C4.5算法、文獻(xiàn)[9]算法，DTEC算法具有較高的分類準(zhǔn)確率和較少的平均葉子節(jié)點(diǎn)數(shù)，并降低了構(gòu)建決策樹的復(fù)雜度。

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

采用實(shí)例表1中提供訓(xùn)練集D，分別對(duì)ID3算法、文獻(xiàn)[14]算法、C4.5算法、文獻(xiàn)[9]算法和DTEC算法進(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　五種算法生成決策樹的時(shí)間對(duì)比

圖4中橫坐標(biāo)表示訓(xùn)練集樣本的取值個(gè)數(shù)，縱坐標(biāo)表示構(gòu)建決策樹所花費(fèi)的時(shí)間。

從圖4中可看出:(1) 樣本個(gè)數(shù)偏少時(shí)，五種算法花費(fèi)時(shí)間相差不大。(2) 從整體上看文獻(xiàn)[14]算法，所花費(fèi)的時(shí)間與ID3算法的時(shí)間基本相同。(3) 當(dāng)樣本個(gè)數(shù)相同時(shí)，DTEC算法構(gòu)建決策樹所花費(fèi)的時(shí)間最少。(4) 當(dāng)樣本個(gè)數(shù)達(dá)到一定數(shù)量時(shí)，DTEC算法所節(jié)省的時(shí)間隨著樣本個(gè)數(shù)遞增而變多，這表明：在構(gòu)建大規(guī)模數(shù)據(jù)集的決策樹時(shí)，使用DTEC算法能夠節(jié)約更多的時(shí)間。

4.3.3 誤分類代價(jià)的比較

以表3、表4中五種算法作為考察對(duì)象，讓每種算法按其自身的分裂屬性原則建立決策樹，最后比較它們各自產(chǎn)生的誤分類代價(jià)比值。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5　各個(gè)數(shù)據(jù)集下誤分類代價(jià)比值的對(duì)比

圖5中橫坐標(biāo)表示各個(gè)數(shù)據(jù)集以及它們的名稱，縱坐標(biāo)表示各個(gè)算法在不同數(shù)據(jù)集上的誤分類代價(jià)比值。

從圖5中可看出:(1)文獻(xiàn)[14]算法比ID3算法、C4.5算法、文獻(xiàn)[9]算法的誤分類代價(jià)比值都要小，當(dāng)誤分類代價(jià)作為分類效果的衡量標(biāo)準(zhǔn)時(shí)，文獻(xiàn)[14]算法分類效果較好。(2)DTEC算法比ID3算法、C4.5算法、文獻(xiàn)[9]算法的誤分類代價(jià)比值都要小，但與文獻(xiàn)[14]算法的誤分類代價(jià)比值相差不大，當(dāng)誤分類代價(jià)作為分類效果的衡量標(biāo)準(zhǔn)時(shí)，DTEC算法與文獻(xiàn)[14]算法分類效果近似。

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

結(jié)合圖1、圖2和圖3可看出：(1) 本文提出的DETC算法能夠克服多值偏向問題；(2) DETC算法中對(duì)ID3算法公式簡化的部分，并未降低原ID3算法公式的精度，DETC算法生成的決策樹與原ID3算法生成的決策樹基本保持一致。

結(jié)合表3、表4、圖4和圖5中可看出：(1) 文獻(xiàn)[9]算法和C4.5算法雖然分類精度較高，決策樹建立時(shí)間較少，但未考慮誤分類代價(jià)問題，當(dāng)誤分類代價(jià)作為分類效果的衡量標(biāo)準(zhǔn)時(shí)，分類效果較差；(2) 文獻(xiàn)[14]算法誤分類代價(jià)比值較小，雖當(dāng)誤分類代價(jià)作為分類效果的衡量標(biāo)準(zhǔn)時(shí)，分類效果較好，但分類精度低，決策樹建立時(shí)間較長，此外文獻(xiàn)[14]算法仍存在多值偏向問題；(3) 本文提出DTEC算法，繼承了以上各個(gè)算法的長處，實(shí)驗(yàn)結(jié)果分析表明：本文的優(yōu)化算法具有較高的分類精度，較少的平均葉子節(jié)點(diǎn)數(shù)；具有較少的決策樹建立時(shí)間；考慮了代價(jià)問題并具有較低的誤分類代價(jià)比值；此外還能克服ID3算法的多值偏向問題。

5結(jié)語

針對(duì)ID3算法不足之處，結(jié)合屬性相似度和代價(jià)敏感學(xué)習(xí)提出了DTEC算法。首先，運(yùn)用等效電阻原理得到屬性相似度和性價(jià)比值兩者的均衡系數(shù)，引入的均衡系數(shù)同時(shí)兼顧兩者，使屬性相似度和代價(jià)敏感學(xué)習(xí)的性價(jià)比值均較大；然后，通過引入均衡系數(shù)對(duì)原ID3算法進(jìn)行改進(jìn)，既克服了多值偏向問題，又兼顧了代價(jià)問題；再運(yùn)用麥克勞林公式對(duì)ID3算法公式進(jìn)行簡化，降低計(jì)算量并提高計(jì)算效率；最后將ID3算法的改進(jìn)工作和簡化工作相結(jié)合，得到DTEC算法。實(shí)驗(yàn)結(jié)果表明，本文提出的DTEC算法較之其他改進(jìn)算法，不僅克服了多值偏向問題，還能考慮代價(jià)問題并降低誤分類代價(jià)，此外還具有較高的分類精度和較短的決策樹建立時(shí)間。

參考文獻(xiàn)

[1] 朱明.數(shù)據(jù)挖掘[M].中國科學(xué)技術(shù)大學(xué)出版社,2002:67-68.

[2] 李世娟,馬驥,白鷺.基于改進(jìn)ID3算法的決策樹構(gòu)建[J].沈陽大學(xué)學(xué)報(bào):自然科學(xué)版,2009,21(6):23-25.

[3] 韓松來,張輝,周華平.基于關(guān)聯(lián)度函數(shù)的決策樹分類算法[J].計(jì)算機(jī)應(yīng)用,2005,25(11):2655-2657.

[4] Jin C,Delin L,Fenxiang M.An improved ID3 decision tree algorithm[C]//Computer Science & Education,2009.ICCSE’09.4th International Conference on.IEEE,2009:127-130.

[5] 陶榮,張永勝,杜宏保.基于粗集論中屬性依賴度的ID3改進(jìn)算法[J].河南科技大學(xué)學(xué)報(bào):自然科學(xué)版,2010,31(1):42-45.

[6] 朱顥東,鐘勇.ID3算法的優(yōu)化[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2010,38(5):9-12.

[7] 朱顥東.ID3算法的改進(jìn)和簡化[J].上海交通大學(xué)學(xué)報(bào),2010,44(7):883-886.

[8] 黃宇達(dá),范太華.決策樹ID3算法的分析與優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(8):3089-3093.

[9] 陸秋,程小輝.基于屬性相似度的決策樹算法[J].計(jì)算機(jī)工程,2009,35(6):82-84.

[10] Luo H,Chen Y,Zhang W.An Improved ID3 Algorithm Based on Attribute Importance-Weighted[C]//Database Technology and Applications (DBTA),2010 2nd International Workshop on.IEEE,2010:1-4.

[11] 黃小猛.異構(gòu)代價(jià)敏感決策樹與隨機(jī)森林核心技術(shù)[D].廣西師范大學(xué),2013.

[12] Qin Z,Zhang S,Zhang C.Cost-sensitive decision trees with multiple cost scales[M]//AI 2004:Advances in Artificial Intelligence.Springer Berlin Heidelberg,2005:380-390.

[13] 覃澤,韋建忠.CSL中測試屬性選擇方法[J].微計(jì)算機(jī)信息,2008,24(6):288-289.

[14] 劉星毅.基于性價(jià)比的分裂屬性選擇方法[J].計(jì)算機(jī)應(yīng)用,2009,29(3):839-842.

[15] 陳英,馬仲兵,黃敏.優(yōu)化的C4.5決策樹算法[J].軟件,2013,34(2):61-64.

[16] 劉春英.基于關(guān)聯(lián)度的代價(jià)敏感決策樹生成方法[J].長春工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2013,34(2):218-222.

[17] 馬福民,張騰飛.一種基于知識(shí)粒度的啟發(fā)式屬性約簡算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(36):31-33.

[18] 孟光勝.基于關(guān)聯(lián)度和代價(jià)敏感學(xué)習(xí)的決策樹生成法[J].科學(xué)技術(shù)與工程,2013,13(5):1196-1199.

[19] 阮曉宏,黃小猛,袁鼎榮,等.基于異構(gòu)代價(jià)敏感決策樹的分類器算法[J].計(jì)算機(jī)科學(xué),2013,40(11A):140-142.

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

[21] 謝妞妞,劉於勛.決策樹屬性選擇標(biāo)準(zhǔn)的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(34):115-118.

[22] 同濟(jì)大學(xué)數(shù)學(xué)系.高等數(shù)學(xué):上冊(cè)[M].6版.北京:高等教育出版社,2007.

[23] 張春麗,張磊.一種基于修正信息增益的ID3算法[J].計(jì)算機(jī)工程與科學(xué),2008,30(11):46-47,94.

[24] Hu X,Cercone N.Data mining via discretization,generalization and rough set feature selection[J].Knowledge and Information Systems,1999,1(1):33-60.

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

收稿日期：2014-12-07。董躍華，副教授，主研領(lǐng)域：數(shù)據(jù)挖掘，軟件工程，軟件測試。劉力，碩士生。

中圖分類號(hào)TP301.6

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.07.061

DECISION TREE OPTIMISATION ALGORITHM BASED ON EQUILIBRIUM COEFFICIENT

Dong Yuehua1Liu Li2

1(SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou341000,Jiangxi,China)2(DepartmentofComputerScienceandTechnology,JiangxiUniversityofScienceandTechnology,Ganzhou341000,Jiangxi,China)

AbstractFor the problems of ID3 algorithm in neglecting multi-value bias and misclassification cost, by combining the attribute similarity and cost sensitive learning we proposed an equilibrium coefficient-based decision tree optimisation algorithm. The algorithm solves the problem of multi-value bias and takes in to account the misclassification cost simultaneously. First, we introduced the equilibrium coefficient between attribute similarity and the value of performance to price ratio to improve ID3 algorithm. Then we used McLaughlin formula to carry out formula simplification on ID3 algorithm. Finally, we got the equilibrium coefficient-based decision tree optimisation algorithm by combining the algorithm improvement and formula simplification. Experimental results showed that the decision tree optimisation algorithm based on equilibrium coefficient can improve the classification accuracy, shorten the time of decision tree generation, and consider the cost problem as well as reduce misclassification cost. Moreover, it can also overcome the problem of multi-value bias.

KeywordsID3 algorithmAttribute similarityCost sensitive learningDecision treeEquilibrium coefficient