基于相關(guān)系數(shù)的決策樹優(yōu)化算法*

董躍華,劉 力

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

基于相關(guān)系數(shù)的決策樹優(yōu)化算法*

董躍華,劉 力

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

通過(guò)分析ID3算法的基本原理及其多值偏向問(wèn)題，提出了一種基于相關(guān)系數(shù)的決策樹優(yōu)化算法。首先通過(guò)引進(jìn)相關(guān)系數(shù)對(duì)ID3算法進(jìn)行改進(jìn)，從而克服其多值偏向問(wèn)題，然后運(yùn)用數(shù)學(xué)中泰勒公式和麥克勞林公式的性質(zhì)，對(duì)信息增益公式進(jìn)行近似簡(jiǎn)化。通過(guò)具體數(shù)據(jù)的實(shí)例驗(yàn)證，說(shuō)明優(yōu)化后的ID3算法能夠解決多值偏向問(wèn)題。標(biāo)準(zhǔn)數(shù)據(jù)集UCI上的實(shí)驗(yàn)結(jié)果表明，在構(gòu)建決策樹的過(guò)程中，既提高了平均分類準(zhǔn)確率，又降低了構(gòu)建決策樹的復(fù)雜度，從而還縮短了決策樹的生成時(shí)間，當(dāng)數(shù)據(jù)集中的樣本數(shù)較大時(shí)，優(yōu)化后的ID3算法的效率得到了明顯的提高。

ID3算法；相關(guān)系數(shù)；決策樹；泰勒公式；信息增益

1 引言

數(shù)據(jù)挖掘是指從大量數(shù)據(jù)中挖掘知識(shí)的過(guò)程，是一種新的高級(jí)數(shù)據(jù)分析技術(shù)[1]。數(shù)據(jù)分類是數(shù)據(jù)挖掘中重要的研究方法之一[2]，其中有決策樹分類器、貝葉斯分類器等基本技術(shù)。20世紀(jì)80年代初期，機(jī)器學(xué)習(xí)研究者Quinlan J R[3]提出了一種新的決策樹分類算法，即ID3算法。在各類決策樹算法中，ID3算法的影響力最大。

然而ID3算法也存在一些缺陷[4]：(1)信息熵的計(jì)算方式易使ID3算法產(chǎn)生多值偏向問(wèn)題；(2)數(shù)據(jù)集樣本個(gè)數(shù)的增多使算法對(duì)應(yīng)計(jì)算量的增幅變大；(3)訓(xùn)練集的增減變化會(huì)影響算法對(duì)應(yīng)決策樹的生成。

針對(duì)ID3算法的多值偏向問(wèn)題，自Quinlan J R提出C4.5算法[5]以來(lái)，許多學(xué)者進(jìn)行相關(guān)改進(jìn)工作：文獻(xiàn)[6～9]將用戶興趣度參數(shù)引入信息熵公式，雖在一定程度上能解決多值偏向問(wèn)題，但該參數(shù)需要用戶具有豐富的先驗(yàn)知識(shí)和領(lǐng)域知識(shí)以及需要在進(jìn)行大量的實(shí)驗(yàn)后才能給出；文獻(xiàn)[10]通過(guò)引入單調(diào)遞減的修正函數(shù)對(duì)信息熵值進(jìn)行修正，以達(dá)到對(duì)ID3算法進(jìn)行改進(jìn)的目的，但修正函數(shù)是人為主觀選取的，因此在一定程度上會(huì)影響決策結(jié)果的正確性和客觀性；文獻(xiàn)[11]將概率統(tǒng)計(jì)中的相關(guān)系數(shù)概念引入決策樹中，將條件屬性和決策樹屬性之間的相關(guān)系數(shù)值作為選擇分裂屬性的標(biāo)準(zhǔn)。條件屬性和決策屬性之間的相關(guān)系數(shù)越大，表明該條件屬性和決策屬性之間的相關(guān)性程度越高、聯(lián)系越緊密，該條件屬性對(duì)分類的重要性越大[12]，但因?yàn)槠涿撾x信息熵理論的計(jì)算方式，所以在分類準(zhǔn)確率上會(huì)低于ID3算法；文獻(xiàn)[13]在用戶興趣度參數(shù)的研究基礎(chǔ)上，使用灰色關(guān)聯(lián)度取代用戶興趣度，雖在一定程度上能克服多值偏向問(wèn)題，但若實(shí)際操作中出現(xiàn)灰度較低或?qū)傩匀≈祩€(gè)數(shù)較多等情況，則難以界定灰色關(guān)聯(lián)度的范圍。

本文在文獻(xiàn)[10，11]的基礎(chǔ)上,結(jié)合修正函數(shù)的修正思想和相關(guān)系數(shù)，提出了基于相關(guān)系數(shù)的決策樹優(yōu)化算法。區(qū)別于文獻(xiàn)[10]中對(duì)信息熵值的修正，本文通過(guò)引入相關(guān)系數(shù)對(duì)劃分子元組的期望信息量進(jìn)行修正，以完成對(duì)ID3算法的改進(jìn)。另外，通過(guò)利用泰勒公式和麥克勞林公式得到近似轉(zhuǎn)化公式，以完成對(duì)信息熵公式的近似簡(jiǎn)化，簡(jiǎn)化后的公式已完全消除了復(fù)雜的對(duì)數(shù)運(yùn)算，從而提高了信息熵公式的計(jì)算效率。實(shí)驗(yàn)結(jié)果表明，基于相關(guān)系數(shù)的決策樹優(yōu)化算法，既能夠克服多值偏向問(wèn)題，提高分類精度，又能降低決策樹的生成時(shí)間。

2 理論基礎(chǔ)

2.1 ID3算法[14]

設(shè)訓(xùn)練集S有s個(gè)樣本，將訓(xùn)練集分成m個(gè)類，第i類的實(shí)例個(gè)數(shù)為si，ID3算法基于信息熵計(jì)算的計(jì)算公式定義為：

(1)

其中,pi是S中屬于第i類的概率，pi=si/s。

若選擇屬性A劃分訓(xùn)練集S，設(shè)屬性A有屬性值{s1，s2，…，sk}，則sj中屬于第i類的訓(xùn)練實(shí)例個(gè)數(shù)為sij，則有：

(2)

其中s1j+…+smj=sj。

(3)

其中，pij為sj中第i類樣本的概率，pij=sij/sj。

從而得到劃分屬性A的信息增益為：

Gain(A,S)=Info(S)-InfoA(S)

(4)

2.2 相關(guān)系數(shù)

2.2.1 相關(guān)系數(shù)的定義[15]

則隨機(jī)變量X與Y的相關(guān)系數(shù)ρxy定義為：

(5)

其中，D(X)和D(Y)分別為X和Y的方差。

2.2.2 相關(guān)系數(shù)的含義[15]

用X的線性函數(shù)a+bX來(lái)近似表示Y，以均方誤差e來(lái)衡量以a+bX近似表示Y的好壞程度。其中，

2abE(X)-2aE(Y)

(6)

而e的值越小，則表示a+bX與Y的近似程度越大。因此，給a、b賦值，使e取最小值。令e分別求關(guān)于a、b的偏導(dǎo)數(shù)，并使它們等于零，則有：

解得：

將a0、b0代入式(6)得:

(7)

2.3 ID3算法公式簡(jiǎn)化的理論基礎(chǔ)

本文通過(guò)運(yùn)用泰勒公式和麥克勞林公式對(duì)信息熵計(jì)算公式進(jìn)行近似轉(zhuǎn)換，以達(dá)到簡(jiǎn)化ID3算法公式的目的。

2.3.1 泰勒中值定理[16]

如果函數(shù)f(x)在含有x0的某個(gè)開(kāi)區(qū)間(a,b)內(nèi)具有直到(n+1)階的導(dǎo)數(shù)，則對(duì)于任意x∈(a,b)，有:

(8)

其中ξ是x0與x之間的某個(gè)值。

2.3.2 麥克勞林公式[16]

(9)

由此得到近似公式:

(10)

由此可得:

(11)

因此有:

(12)

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

(13)

3 基于相關(guān)系數(shù)的決策樹優(yōu)化算法

3.1 ID3決策樹優(yōu)化算法的實(shí)現(xiàn)方案

本文針對(duì)“多值偏向問(wèn)題”和“信息熵計(jì)算公式”兩個(gè)方面，分別對(duì)ID3算法進(jìn)行算法改進(jìn)和公式簡(jiǎn)化，提出了基于相關(guān)系數(shù)的決策樹優(yōu)化算法DTCC(Optimized algorithm of Decision Tree based on Correlation Coefficient)，DTCC算法由ID3算法改進(jìn)和ID3算法公式簡(jiǎn)化兩部分組成。

(1)ID3算法改進(jìn)。用戶興趣度之類的主觀參數(shù)主要取決于用戶的先驗(yàn)知識(shí)和相關(guān)領(lǐng)域知識(shí)，決策結(jié)果更傾向于用戶的主觀思維。為避免此類主觀參數(shù)不具說(shuō)服力，本文引入概率統(tǒng)計(jì)中的相關(guān)系數(shù)對(duì)ID3算法進(jìn)行改進(jìn)。相關(guān)系數(shù)客觀反映條件屬性和決策屬性之間的相關(guān)程度，使分裂屬性的選擇不受屬性取值個(gè)數(shù)的影響，從而克服其多值偏向的缺陷，還因無(wú)較多主觀的參與或干擾從而避免了決策結(jié)果受用戶主觀思想的影響。

(2)ID3算法公式簡(jiǎn)化。本文在泰勒公式和麥克勞林公式的基礎(chǔ)上得到近似轉(zhuǎn)換公式，通過(guò)利用近似轉(zhuǎn)換公式對(duì)信息熵公式進(jìn)行近似簡(jiǎn)化。簡(jiǎn)化后的公式以信息熵理論為基礎(chǔ)，因而保留了較高的分類精度，又能消除信息熵公式中復(fù)雜的對(duì)數(shù)運(yùn)算，提高算法計(jì)算效率。

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

ID3算法對(duì)屬性進(jìn)行分類時(shí)，通常以信息增益值作為屬性選擇度量，將具有最大增益值的屬性作為最優(yōu)分裂屬性。ID3算法造成多值偏向問(wèn)題的本質(zhì)是：信息熵的計(jì)算特點(diǎn)會(huì)使屬性的重要性程度與屬性的取值個(gè)數(shù)成正比，但通常取值個(gè)數(shù)較多的屬性不一定是最優(yōu)分裂屬性，最終可能會(huì)導(dǎo)致做出不適合實(shí)際情況的決策，為此本文引進(jìn)相關(guān)系數(shù)對(duì)ID3算法進(jìn)行改進(jìn)。

3.2.1 屬性之間相關(guān)系數(shù)的引入

假設(shè)訓(xùn)練集S由r個(gè)條件屬性和一個(gè)決策屬性Y構(gòu)成,將r個(gè)條件屬性字段看成隨機(jī)變量Xp(p=1,2,…,r),決策屬性看成隨機(jī)變量Y,則某個(gè)屬性的屬性值分布即為某個(gè)隨機(jī)變量的取值分布,令隨機(jī)變量Xp的取值為xq(q=1,2,…,k),則Xp取到各個(gè)值的概率P{Xp=xq}=pq(q=1,2,…,k)稱為隨機(jī)變量Xp的概率分布，此時(shí)可將訓(xùn)練集S轉(zhuǎn)變成若干個(gè)隨機(jī)變量的集合。

借鑒定義1和定義2,將變量間的相關(guān)系數(shù)引進(jìn)到ID3算法中，使其成為重新定義條件屬性與決策屬性之間緊密相關(guān)程度的性能指標(biāo)。令k、m分別為隨機(jī)變量Xi與Y的取值個(gè)數(shù),則隨機(jī)變量Xp(i=1,2,…,r)與Y的協(xié)方差為:

其中,pq t為(q=1,2,…,k;t=1,2,…,m)為Xp和Y的聯(lián)合概率分布。Xp和Y的聯(lián)合概率分布如表1所示。

Table 1 Joint probability distribution of Xp and Y表1 (Xp,Y)的聯(lián)合概率分布

重新定義隨機(jī)變量Xp與Y的相關(guān)系數(shù)為:

(14)

令:

(15)

從公式(15)中可看出0≤ωp≤1，而ωp成為了衡量條件屬性集Xp與決策屬性Y之間緊密相關(guān)程度的一種度量標(biāo)準(zhǔn)。

當(dāng)ωp較大時(shí)，說(shuō)明Xp與Y屬性之間聯(lián)系的緊密程度較高；當(dāng)ωp較小時(shí)，說(shuō)明Xp、Y屬性之間聯(lián)系的緊密程度較低；當(dāng)ωp=1時(shí)，稱Xp和Y屬性之間以概率1存在著緊密的聯(lián)系；當(dāng)ωp=0時(shí)，稱Xp和Y屬性之間沒(méi)有聯(lián)系。

3.2.2 引入相關(guān)系數(shù)對(duì)ID3算法進(jìn)行改進(jìn)

相關(guān)系數(shù)對(duì)ID3算法公式(4)進(jìn)行改進(jìn)后，得到新的信息增益公式(16)：

(16)

屬性相關(guān)系數(shù)客觀反映條件屬性和決策屬性之間聯(lián)系的緊密程度，且不受屬性取值個(gè)數(shù)的影響。

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

(1)ID3算法多值偏向分析。

假設(shè)存在一個(gè)屬性值個(gè)數(shù)較多且重要性低的條件屬性B，則條件屬性B與決策屬性Y之間聯(lián)系的緊密程度必然低，其相關(guān)系數(shù)ωB較小；存在一個(gè)屬性值個(gè)數(shù)較少且重要性高的條件屬性A，則條件屬性A與決策屬性Y之間聯(lián)系的緊密程度必然高，其相關(guān)系數(shù)ωA較大。相對(duì)于決策屬性Y，條件屬性A的重要性高于條件屬性B，因此很顯然有：ωA>ωB。

從文獻(xiàn)[10]中可知：由于信息熵的計(jì)算特點(diǎn)，它會(huì)偏向于屬性取值個(gè)數(shù)多的屬性,文獻(xiàn)[17]也證明在該情況下的公式(17)恒成立。

Gain(A,S)≤Gain(B,S)

(17)

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

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

ID3算法被改進(jìn)后，比較信息增益Gain(A,S)′和信息增益Gain(B,S)′兩者之間的大小關(guān)系：

若Gain(A,S)′≤Gain(B,S)′恒成立，說(shuō)明該算法有多值偏向問(wèn)題；若能避免其恒成立，則說(shuō)明該算法能克服多值偏向問(wèn)題。

將公式(17)進(jìn)一步等價(jià)推導(dǎo)可得：

Gain(A,S)≤Gain(B,S)?

Info(S)-InfoA(S)≤Info(S)-InfoB(S)?

InfoA(S)≥InfoB(S)

(18)

由公式(16)可得算法改進(jìn)后，屬性A和屬性B的子元組期望信息分別為：

和

從公式(18)中可知：公式(17)恒成立等價(jià)于InfoA(S)≥InfoB(S)恒成立。但是，因?yàn)樵诟髯缘淖釉M期望信息中分別乘以1/ωA和1/ωB，且由ωA>ωB可得1/ωA<1/ωB，所以可避免公式(19)的恒成立。

(19)

由公式(19)進(jìn)一步可推導(dǎo)出如下等價(jià)關(guān)系:

?

Gain(A,S)′≤Gain(B,S)′

(20)

從公式(20)中可知：能夠避免公式(19)的恒成立，即等價(jià)于避免Gain(A,S)′≤Gain(B,S)′的恒成立。能夠避免Gain(A,S)′≤Gain(B,S)′的恒成立，則表明多向偏值問(wèn)題已經(jīng)得到解決。

因此，采用公式(16)作為新的屬性選擇標(biāo)準(zhǔn)作，能夠降低屬性取值個(gè)數(shù)較多且重要性低的屬性的重要程度,克服了ID3算法多值偏向的缺陷。

3.3 ID3算法的公式簡(jiǎn)化

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

(21)

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

(22)

從公式(22)中可看出：對(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，因此公式(22)可進(jìn)行如下轉(zhuǎn)化：

使用近似簡(jiǎn)化公式(13)可進(jìn)一步化簡(jiǎn)為：

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

(23)

從公式(23)中可看出:公式中已完全消除復(fù)雜的log對(duì)數(shù)運(yùn)算，只需對(duì)函數(shù)進(jìn)行有限次數(shù)的加、減、乘、除四種基本運(yùn)算即可，計(jì)算效率得到很大提高。

3.4 DTCC算法的提出

DTCC算法包括ID3算法改進(jìn)和ID3算法公式簡(jiǎn)化兩個(gè)部分的工作，將ID3算法改進(jìn)公式(16)和ID3算法簡(jiǎn)化公式(23)相結(jié)合得到DTCC算法公式(24)：

(24)

DTCC算法采用公式(24)作為新的屬性選擇標(biāo)準(zhǔn)。DTCC算法既能克服多值偏向，又能簡(jiǎn)化ID3算法公式，降低計(jì)算量并提高計(jì)算效率。

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

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

本實(shí)驗(yàn)在標(biāo)準(zhǔn)數(shù)據(jù)集UCI上進(jìn)行，采用UCI提供的若干個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集(如表2所示)進(jìn)行數(shù)據(jù)分析。數(shù)據(jù)集中2/3樣本作為訓(xùn)練集，1/3作為測(cè)試集。采用文獻(xiàn)[18]中的方法先對(duì)數(shù)據(jù)集中的連續(xù)性屬性進(jìn)行離散化操作。

Table 2 Dataset表2 數(shù)據(jù)集

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

Table 3 Dataset D of the customer database表3 顧客數(shù)據(jù)庫(kù)訓(xùn)練集D

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

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

(25)

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

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

以訓(xùn)練集D為例，先計(jì)算出各個(gè)條件屬性與決策屬性的相關(guān)系數(shù)，然后再根據(jù)公式(4)計(jì)算ID3算法信息增益，根據(jù)公式(24)計(jì)算DTCC算法的信息增益，根據(jù)公式(23)計(jì)算ID3算法公式簡(jiǎn)化后的信息增益，最后按照決策樹建樹規(guī)則，構(gòu)建各自的決策樹，分別如圖1～圖3所示。

4.2.1 相關(guān)系數(shù)的計(jì)算

(1)條件屬性“喜歡的季節(jié)”與決策屬性“是否買車”之間相關(guān)系數(shù)的計(jì)算。

條件屬性“喜歡的季節(jié)”X1與決策屬性“是否買車”Y的聯(lián)合分布律如表4所示。

Table 4 Joint probability distribution of X1and Y表4 X1與Y的聯(lián)合概率分布

通過(guò)表4中數(shù)據(jù)計(jì)算可得：

(2)條件屬性“是否商務(wù)人士”與決策屬性“是否買車”之間相關(guān)系數(shù)的計(jì)算。

條件屬性“是否商務(wù)人士”X2與決策屬性“是否買車”Y的聯(lián)合分布律如表5所示。

Table 5 Joint probability distribution of X2 and Y表5 X2與Y的聯(lián)合概率分布

通過(guò)表5中數(shù)據(jù)計(jì)算可得：

(3)條件屬性“收入”與決策屬性“是否買車”之間相關(guān)系數(shù)的計(jì)算。

條件屬性“收入”X3與決策屬性“是否買車”Y的聯(lián)合分布律如表6所示。

Table 6 Joint probability distribution of X3and Y表6 X3與Y的聯(lián)合概率分布

通過(guò)表6中數(shù)據(jù)計(jì)算可得：

(4)條件屬性“駕車水平”與決策屬性“是否買車”之間相關(guān)系數(shù)的計(jì)算。

條件屬性“駕車水平”X4與決策屬性“是否買車”Y的聯(lián)合分布律如表7所示。

Table 7 Joint probability distribution of X4and Y表7 X4與Y的聯(lián)合概率分布

通過(guò)表7中數(shù)據(jù)計(jì)算可得：

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

首先計(jì)算屬性的期望需求:

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

其次，由計(jì)算結(jié)果比較可知：

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

Figure 1 Decision tree produced by the ID3 algorithm

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

DTCC算法公式為：

表1中實(shí)例有兩個(gè)類，即m=2，則公式(20)可變形為：

按照變形后的公式分別計(jì)算屬性的信息增益：

Gain(X1=喜歡的季節(jié))′=

Gain(X2=是否商務(wù)人士)′=

Gain(X3=收入)′=

Gain(X4=駕車水平)′=

比較結(jié)果可知：

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

Figure 2 Decision tree produced by the DTCC algorithm圖2 DTCC算法生成的決策樹

4.2.4 只進(jìn)行簡(jiǎn)化操作后的ID3算法及其對(duì)應(yīng)生成的決策樹

簡(jiǎn)化后的ID3算法公式為：

表1中實(shí)例有兩個(gè)類，即m=2，則公式(19)可變形為：

按照變形后的公式分別計(jì)算屬性的信息增益：

Gain(喜歡的季節(jié))3=

Gain(是否商務(wù)人士)3=

Gain(收入)3=

比較計(jì)算結(jié)果可知：

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

Figure 3 Decision tree produced by the ID3 algorithm with its simplified formula

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

通過(guò)將圖1～圖3進(jìn)行綜合對(duì)比發(fā)現(xiàn)：

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

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

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

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

在表2提供的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)數(shù)據(jù)測(cè)試，每一個(gè)數(shù)據(jù)集上進(jìn)行10次實(shí)驗(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)[10]算法、文獻(xiàn)[11]算法和DTCC算法構(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é)果如表8和表9所示。

Table 8 The first part of the experimental results表8 實(shí)驗(yàn)結(jié)果1

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

Table 9 The second part of the experimental results表9 實(shí)驗(yàn)結(jié)果2

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

采用實(shí)例表3中提供的訓(xùn)練集D，分別對(duì)ID3算法、文獻(xiàn)[10]算法、C4.5算法、文獻(xiàn)[11]算法和DTCC算法進(jìn)行10次計(jì)算時(shí)間的測(cè)試,在實(shí)驗(yàn)結(jié)果中去掉最大數(shù)據(jù)和最小數(shù)據(jù)，再求出平均時(shí)間作為構(gòu)建決策樹所花費(fèi)的時(shí)間。實(shí)驗(yàn)結(jié)果如圖4所示。圖4中橫坐標(biāo)表示訓(xùn)練集樣本的取值個(gè)數(shù)，縱坐標(biāo)表示構(gòu)建決策樹所花費(fèi)的時(shí)間。

Figure 4 Time comparison of building the decision tree among the five kinds of algorithms

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

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

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

結(jié)合表8、表9、圖4可看出：(1)文獻(xiàn)[10]算法和C4.5算法雖然分類精度較高，但決策樹建立時(shí)間較長(zhǎng)。(2)文獻(xiàn)[11]算法決策樹建立時(shí)間較短，但分類精度較低。(3)本文提出DTCC算法，繼承了以上各算法的長(zhǎng)處，實(shí)驗(yàn)結(jié)果分析表明：DTCC算法具有較高的分類精度；平均葉子節(jié)點(diǎn)數(shù)較少，使構(gòu)造的決策樹有較低的復(fù)雜性，因而使決策樹建立時(shí)間較少；此外還能克服ID3算法的多值偏向問(wèn)題。

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

本文通過(guò)引進(jìn)概率論中相關(guān)系數(shù)的概念，基于相關(guān)系數(shù)提出了一種新的決策樹優(yōu)化算法——DTCC算法，相關(guān)系數(shù)能夠客觀反映條件屬性和決策屬性之間聯(lián)系的緊密程度，既不受屬性取值個(gè)數(shù)的影響，且不需要用戶提供先驗(yàn)知識(shí)或領(lǐng)域知識(shí)，又能避免因?yàn)橹饔^的人為因素所受到的干擾和影響。本文用相關(guān)系數(shù)代替依靠先驗(yàn)知識(shí)的用戶興趣度之類的權(quán)值參數(shù)，以克服ID3算法的多值偏向問(wèn)題。再利用泰勒公式和麥克勞林展開(kāi)公式得到近似公式，以完成對(duì)信息增益公式的近似轉(zhuǎn)換，這樣既保證簡(jiǎn)化后的算法保留較高的精度，且以信息熵計(jì)算為基礎(chǔ)，又能夠消除函數(shù)中復(fù)雜的對(duì)數(shù)運(yùn)算，提高算法執(zhí)行效率。

實(shí)驗(yàn)結(jié)果分析表明，相比于原ID3算法以及ID3相關(guān)的改進(jìn)算法，DTCC算法具有更高的平均分類精確度，較低的決策樹構(gòu)建復(fù)雜度，更少的決策樹生成時(shí)間。當(dāng)數(shù)據(jù)集的樣本數(shù)偏大時(shí)，DTCC算法的效率和性能能夠得到明顯的提高。

[1] Ji Xi-yu,Han Qiu-ming,Li Wei,et al.Data mining technology application examples[M].Beijing:Mechanical Industry Press,2009.(in Chinese)

[2] Chen An, Chen Ning, Zhou Long-xiang, et al.Data mining technologies and application[M].Beijing:Science Press,2006.(in Chinese)

[3] Quinlan J R. Induction of decision trees[J]. Machine Learning,1986,1(1):81-106.

[4] Wang Miao,Chai Rui-min.An improved decision tree classification attribute selection method[J] .Computer Engineering and Applications,2010,46(8):127-129.(in Chinese)

[5] Li Xiao-wei,Chen Fu-cai, Li Shao-mei. Improved C4.5 decision tree algorithm based on classification rules[J]. Computer Engineering and Design,2013,34(12):4321-4325.(in Chinese)

[6] Wang Yong-mei,Hu Xue-gang.Research of ID3 algorithm in decision tree[J]. Journal of Anhui University (Natural Science Edition),2011,35(3):71-75.(in Chinese)

[7] Wang Yong-mei,Hu Xue-gang.Improved decision tree algorithm based on user-interest and MID3[J].Computer Engineering and Applications,2011,47(27):155-157.(in Chinese)

[8] Liu Yu-xun,Xie Niu-niu. Improved ID3 algorithm[C]∥Proc of the 3rd IEEE International Conference on Computer Science and Information Technology (ICCSIT 2010),2010:465-468.

[9] Qu Kai-she,Cheng Wen-li,Wang Jun-hong. Improved algorithm based on ID3[J].Computer Engineering and Applications,2003,39(25):104-107.(in Chinese)

[10] Zhang Chun-li,Zhang Lei.A new ID3 algorithm based on revised information gain[J]. Computer Engineering & Science,2008,30(11):46-47.(in Chinese)

[11] Zhao Xiang,Qi Yun-song,Liu Tong-ming.Application of covariace and correlativity coefficient to the designing of decision trees[J].Journal of East China Shipbuilding Institute (Natural Science Edition),2003,17(5):57-60.(in Chinese)

[12] Zhang Ming-wei,Wang Bo,Zhang Bin,et al.Weighted naive Bayes classification algorithm based on correlation coefficients[J].Journal of Northeastern University(Natural Science),2008,29(7):952-955.(in Chinese)

[13] Ye Ming-quan,Hu Xue-gang.One improve decision tree algorithm based on grey relation degree[J].Computer Engineering and Applications,2007,43(32):171-173.(in Chinese)

[14] Huang Yu-da,Fan Tai-hua.ID3 algorithm for decision tree analysis and optimization[J]. Computer Engineering and Design,2012,33(8):3089-3093.(in Chinese)

[15] Sheng Zhou,Xie Shi-qian,Pan Cheng-yi.probabitity theory and mathematical statistics[M]. Beijing:Higher Education Press,2008.(in Chinese)

[16] Department of Mathematics’ Tongji University.Mathematics:Volume One[M]. Beijing:Higher Education Press,2007.(in Chinese)

[17] Han Song-lai, Zhang Hui, Zhou Hua-ping. Decision tree classification algorithm based on correlate degree function[J].Computer Application,2005,25(11):2655-2657.(in Chinese)

[18] 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.

[19] Huang Yu-da, Wang Yi-ran. Decision tree classification based on naive Bayesian and ID3 Algorithm[J]. Computer Engineering,2012,38(14):41-47.(in Chinese)

附中文參考文獻(xiàn)：

[1] 紀(jì)希禹,韓秋明,李微,等. 數(shù)據(jù)挖掘技術(shù)應(yīng)用實(shí)例[M].北京:機(jī)械工業(yè)出版社,2009.

[2] 陳安,陳寧,周龍?bào)J,等. 數(shù)據(jù)挖掘技術(shù)及應(yīng)用[M]. 北京:科學(xué)出版社,2006.

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

[5] 李孝偉,陳福才,李邵梅. 基于分類規(guī)則的 C4. 5 決策樹改進(jìn)算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2013,34(12):4321-4325.

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

[7] 王永梅,胡學(xué)鋼. 基于用戶興趣度和 MID3 決策樹改進(jìn)方法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(27):155-157.

[9] 曲開(kāi)社,成文麗,王俊紅.ID3 算法的一種改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2003,39(25):104-107.

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

[11] 趙翔,祁云嵩,劉同明. 協(xié)方差及相關(guān)系數(shù)在決策樹構(gòu)造中的應(yīng)用[J]. 華東船舶工業(yè)學(xué)院學(xué)報(bào)(自然科學(xué)版),2003,17(5):57-60.

[12] 張明衛(wèi),王波,張斌,等. 基于相關(guān)系數(shù)的加權(quán)樸素貝葉斯分類算法[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,29(7):952-955.

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

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

[15] 盛驟,謝式千,潘承毅. 概率論與數(shù)理統(tǒng)計(jì)[M].北京:高等教育出版社,2008.

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

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

[19] 黃宇達(dá),王迤冉. 基于樸素貝葉斯與 ID3 算法的決策樹分類[J]. 計(jì)算機(jī)工程,2012,38(14):41-47.

董躍華(1964-),女,河北樂(lè)亭人,副教授，研究方向?yàn)閿?shù)據(jù)挖掘、軟件工程和軟件測(cè)試。E-mail:4490367@qq.com

DONG Yue-hua,born in 1964,associate professor,her research interests include data mining, software engineering, and software testing.

劉力(1990-),男,湖北黃岡人，碩士生，研究方向?yàn)閿?shù)據(jù)挖掘。E-mail:931667596@qq.com

LIU Li,born in 1990,MS candidate,his research interest includes data mining.

An optimized algorithm of decision tree based on correlation coefficients

DONG Yue-hua,LIU Li

(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou 341000,China)

Aiming at the problem of multi-value bias in ID3 algorithm, we propose an optimized algorithm of decision tree based on correlation coefficients. Firstly, the correlation coefficients between the attributes are introduced to improve the ID3 algorithm, and in turn the multi-value bias problem is overcome. Then the properties of Taylor formula and Maclaurin formula are adopted to simplify the information gain formula. The concrete data of examples prove that the optimized ID3 algorithm can overcome multi-value bias problem. Experiments on the standard UCI data sets show that the optimized algorithm of decision tree not only improves the accuracy of average classification, but also reduces the complexity in building decision trees and thus reduces the generation time of decision trees. Besides, the efficiency of the optimized ID3 algorithm increases significantly for large scale samples.

ID3 algorithm;correlation coefficient;decision tree;Taylor formula;information gain

1007-130X(2015)09-1783-11

2014-08-25;

2014-12-29

TP301.6

A

10.3969/j.issn.1007-130X.2015.09.030

通信地址：341000 江西省贛州市章貢區(qū)紅旗大道86號(hào)江西理工大學(xué)信息工程學(xué)院

Address:School of Information Engineering,Jiangxi University of Science and Technology，86 Hongqi Avenue,Zhanggong District,Ganzhou 341000,Jiangxi,P.R.China