基于屬性純度的決策樹(shù)歸納算法

姚岳松，張賢勇+，陳 帥，鄧 切

(1.四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，四川 成都 610066；2.四川師范大學(xué) 智能信息與量子信息研究所,四川 成都 610066)

0 引 言

決策樹(shù)模型是基于規(guī)則的分類方法的典型代表，廣泛應(yīng)用于醫(yī)療、社會(huì)學(xué)、金融等領(lǐng)域[1-6]。決策樹(shù)通常有兩類構(gòu)造算法。一類是基于信息熵的算法，例如經(jīng)典的ID3算法[7]和C4.5算法[8]，以及C4.5的改進(jìn)算法[9-11]、ID3的改進(jìn)算法[12]。粗糙集理論能夠進(jìn)行規(guī)則提取與知識(shí)獲取，其中的屬性重要度是依賴性推理的核心度量[13]。由此，基于屬性依賴度的特征選擇提供了決策樹(shù)構(gòu)造的另外一類方法，即基于粗糙集的算法[14-16]。

屬性依賴度來(lái)源于下近似集成的分類正域[13]，由于要求條件粒完全包含于決策類，使得基于粗糙集的決策樹(shù)模型抗噪能力不強(qiáng)。實(shí)際數(shù)據(jù)環(huán)境下，條件粒存在不協(xié)調(diào)于決策類的情況，從而基于粗糙集的決策樹(shù)模型通常需要結(jié)合信息熵函數(shù)。關(guān)于特征選擇的節(jié)點(diǎn)度量函數(shù)，信息熵刻畫(huà)不確定性結(jié)構(gòu)的信息，屬性依賴度與粒度推理的代數(shù)表示有關(guān)；兩種機(jī)制的異質(zhì)性降低了分類效果。對(duì)于分類精度而言，屬性依賴度源于分類正域的定性特征，其本質(zhì)是分類精度的定性和絕對(duì)度量。因此，本文首先提出了一種定量的分類準(zhǔn)確度指標(biāo)——屬性純度，而相關(guān)的特征選擇對(duì)分類精度也是有效的。進(jìn)而，基于屬性依賴度與屬性純度的同質(zhì)異態(tài)性，采用“屬性依賴度優(yōu)先、屬性純度補(bǔ)充”的二級(jí)選擇策略，建立一種新的決策樹(shù)歸納算法，改進(jìn)基于粗糙集的決策樹(shù)算法。

1 決策樹(shù)基礎(chǔ)

機(jī)器學(xué)習(xí)中，決策樹(shù)根源于決策表的形式化結(jié)構(gòu)。決策表是以行和列的形式描述決策規(guī)則和知識(shí)信息的表，可以推導(dǎo)出決策規(guī)則并可對(duì)數(shù)據(jù)進(jìn)行分類。決策樹(shù)采用一種樹(shù)形結(jié)構(gòu)表示，每一個(gè)屬性上的測(cè)試(該屬性也可稱為分裂屬性或分裂點(diǎn))用內(nèi)部節(jié)點(diǎn)表征，一個(gè)測(cè)試輸出在樹(shù)中表示為分支，而分支上的葉節(jié)點(diǎn)包含一種類別。決策樹(shù)是一種決策分析的圖解方法，本質(zhì)上是一種監(jiān)督學(xué)習(xí)形成的分類器，直觀表示決策表中的決策規(guī)則與分類結(jié)果。

屬性序列將決策表中的樣本劃分為集族，最終條件粒隸屬于相關(guān)的決策類，將該過(guò)程稱為決策樹(shù)構(gòu)造。由此可見(jiàn)，決策樹(shù)構(gòu)造與條件屬性的特征選擇直接相關(guān)，而相關(guān)的優(yōu)化準(zhǔn)則關(guān)聯(lián)于屬性重要性程度指標(biāo)，不同的度量函數(shù)衍生出相應(yīng)的決策樹(shù)歸納算法并決定著分類效果。下面基于決策表回顧兩種基本的決策樹(shù)算法，其中屬性度量主要涉及信息熵與屬性依賴度。

1.1 決策表

決策表可表示為4元組

DT=(U,AT=C∪D,{Va|a∈AT},{Ia|a∈AT})

(1)

其中，U是一個(gè)非空的且有限的論域，AT是一個(gè)非空的且有限的屬性集合(含不相交的條件屬性集C與決策屬性集D)，Va是屬性a∈AT在決策表中所對(duì)應(yīng)的值域，信息函數(shù)Ia∶U→Va呈現(xiàn)出關(guān)于屬性a對(duì)象x的唯一數(shù)值Ia(x)。

決策表分析側(cè)重于規(guī)則提取和依賴性推理。在這方面，主要涉及到?jīng)Q策分類和條件分類以及粒結(jié)構(gòu)之間的交互關(guān)系，下面給出符號(hào)性的對(duì)應(yīng)陳述(‖代表集合的基數(shù))。由決策屬性集D形成的劃分設(shè)為U/D={D1,D2,…,Dm}， 其具有m個(gè)決策類Dj(j=1,2,…,m)。 條件屬性子集A?C導(dǎo)出的等價(jià)劃分為U/A={A1,A2,…,AN}， 其具有N個(gè)條件粒Ai(i=1,2,…,N)， [x]A代表著包含x的條件粒。當(dāng)粒Ai中的元素隸屬于不同決策類，則稱為不協(xié)調(diào)，該情況引發(fā)著決策表的協(xié)調(diào)性與不協(xié)調(diào)性[13]。

1.2 基于信息熵的決策樹(shù)算法

信息熵起源于信息的相關(guān)理論，表征和刻畫(huà)系統(tǒng)的不確定性。以此可構(gòu)造經(jīng)典的決策樹(shù)歸納算法，包括ID3[7]、C4.5[8]。

定義1[7]決策分類U/D的信息熵定義為

(2)

其中，Pj=|Dj|/|U| 表示第j個(gè)決策類的概率。條件屬性子集A形成的劃分U/A的信息度量定義為

(3)

Gain(A)=info(D)-info(A)

(4)

基于式(4)，ID3算法構(gòu)造決策樹(shù)的核心思想在于先計(jì)算單個(gè)條件屬性的信息增益，具有最大信息增益的屬性作為檢測(cè)屬性，最后通過(guò)序列遞歸完成分類過(guò)程。而ID3算法存在屬性偏移、不能處理連續(xù)型數(shù)據(jù)、精度低等缺點(diǎn)。針對(duì)ID3的上述問(wèn)題，在ID3算法的基礎(chǔ)上建立了另一種基于信息熵的決策樹(shù)歸納算法(C4.5算法)。

定義2[8]條件屬性集A對(duì)應(yīng)的信息增益率定義為

(5)

其中

(6)

對(duì)于屬性優(yōu)選，C4.5算法主要采用式(5)的信息增益率，其將信息增益規(guī)范化。從而，C4.5算法減少了屬性偏移帶來(lái)的影響，該模型的分類結(jié)果更好。同時(shí)，C4.5算法可以離散化連續(xù)屬性，為后續(xù)的?；治雠c知識(shí)獲取奠定基礎(chǔ)。

1.3 基于屬性依賴度的決策樹(shù)算法

在粗糙集理論中，屬性依賴度是關(guān)于近似推理的一個(gè)基礎(chǔ)概念，用于描述條件、決策粒化之間的派生關(guān)聯(lián)關(guān)系。由此，以屬性依賴度為基礎(chǔ)的相關(guān)決策樹(shù)算法可以被提出。

定義3[13]決策類Dj基于條件屬性子集A的上下近似定義為

(7)

決策分類U/D關(guān)于A的分類正域與屬性依賴度分別定義為

(8)

γA(D)=|POSA(D)|/|U|

(9)

在粗糙集中，上近似和下近似分別從兩個(gè)方向?qū)Q策類進(jìn)行近似逼近，可進(jìn)行分類的樣本包含于分類正域中，具有定性特征；進(jìn)而，屬性依賴度表征了相關(guān)的分類能力，但其量化形式主要對(duì)應(yīng)于定性實(shí)質(zhì)。基于粗糙集的決策樹(shù)歸納算法(簡(jiǎn)記為RS)[17]，主要是通過(guò)選擇依賴度最大的屬性作為決策樹(shù)的分裂節(jié)點(diǎn)。但如果后續(xù)條件屬性的依賴度都為0，則替代采用ID3、C4.5中的信息增益與信息增益率作為檢測(cè)屬性的度量函數(shù)。經(jīng)過(guò)反復(fù)迭代，直至葉節(jié)點(diǎn)屬于一個(gè)決策類或所有條件屬性都成為分裂節(jié)點(diǎn)。

2 基于屬性純度的決策樹(shù)歸納算法

信息熵刻畫(huà)粒結(jié)構(gòu)的不確定性信息，屬性依賴度是對(duì)知識(shí)的代數(shù)推理進(jìn)行描述。因此，基于屬性依賴度的決策樹(shù)算法在分類能力的表達(dá)上具有優(yōu)勢(shì)。但是，條件?；粎f(xié)調(diào)于決策?；驑颖驹肼曈绊?，條件粒存在不歸屬于任意決策類的情況；在這種不協(xié)調(diào)的情況下，基于粗糙集的決策樹(shù)算法一般復(fù)合使用信息熵的特征選擇。機(jī)制準(zhǔn)則不同的兩種度量結(jié)合會(huì)導(dǎo)致分類效果的下降。對(duì)此，接下來(lái)將發(fā)掘一個(gè)關(guān)于分類精度的度量——屬性純度，當(dāng)依賴度的特征選擇失效時(shí)對(duì)其補(bǔ)充確定分裂節(jié)點(diǎn)，使得該類決策樹(shù)算法不再受限于度量函數(shù)的復(fù)合使用并具有較好的分類能力。鑒于此，決策表DT中單屬性c∈C及其誘導(dǎo)的知識(shí)劃分假設(shè)為

U/{c}={{c}1,{c}2,…,{c}n}

2.1 三層純度與屬性純度

定義4 若?Dj∈U/D使得{c}i?Dj， 則條件粒 {c}i∈U/{c} 稱為絕對(duì)純的。若?{c}i∈U/{c} 是絕對(duì)純的，則條件屬性c稱為絕對(duì)純的。

命題1：條件屬性c是絕對(duì)純的，當(dāng)且僅當(dāng)γ{c}(D)=1。

條件?；蜎Q策?；g的交疊派生關(guān)系是知識(shí)推理、識(shí)別分類的粒計(jì)算底層機(jī)制，而絕對(duì)純性直接代表相關(guān)的識(shí)別過(guò)程。換句話說(shuō)，粒 {c}i是絕對(duì)純的，其完全包含于一個(gè)對(duì)應(yīng)的決策類Dj， 可被完全識(shí)別。條件屬性c是絕對(duì)純的，該屬性生成的所有粒結(jié)構(gòu)都可以被相應(yīng)的決策類識(shí)別；對(duì)此，屬性依賴度達(dá)到最大數(shù)值，即γ{c}(D)=1。 但這種定性識(shí)別下的純性可能是理論上的，即條件屬性通常意義下都不是絕對(duì)純的；為此，需要定量的純性測(cè)度來(lái)描述識(shí)別精度，從而表征γ{c}(D)<1的一般情況與γ{c}(D)=0的特殊情況。下面提出條件粒關(guān)于決策類的純度概念。

定義5 給定條件粒 {c}i∈U/{c} 與決策類Dj∈U/D。

(1) {c}i關(guān)于Dj是絕對(duì)純的，若 {c}i?Dj；

(2) {c}i關(guān)于Dj是絕對(duì)不純的，若 {c}i∩Dj=?；

(3) {c}i關(guān)于Dj是近似純的，若 {c}i∩Dj≠?且 {c}i?Dj。

特別地， {c}i關(guān)于Dj的純度定義為

(10)

粒 {c}i和決策類Dj的交互重合部分占 {c}i的比值稱為純度，代表粒 {c}i被決策類Dj的識(shí)別程度，及對(duì)應(yīng)分類決策 {c}i→Dj的可信度。這一度量能夠有效支撐相關(guān)的定性理解。顯然， Pure{c}i(Dj)∈[0,1]。

(1)若Pure{c}i(Dj)=1， 則 {c}i關(guān)于Dj是絕對(duì)純的；

(2)若Pure{c}i(Dj)=0， 則 {c}i關(guān)于Dj是絕對(duì)不純的；

(3)若Pure{c}i(Dj)∈(0,1)， 則 {c}i關(guān)于Dj是近似純的。

定義5提供的條件粒與決策類的純性可以描述定義4的條件屬性的純性及相關(guān)概念。例如，條件屬性c是絕對(duì)純的，當(dāng)且僅當(dāng)?{c}i∈U/{c}， ?Dj∈U/D， 使得 {c}i關(guān)于Dj是絕對(duì)純的；此外，還可以基于條件分類U/{c} 來(lái)定義并刻畫(huà)條件屬性c的近似純性。特別地，定義5提供的純度為后續(xù)屬性度量構(gòu)建奠定了基礎(chǔ)。下面，基于決策表的三層粒結(jié)構(gòu)[18]實(shí)施三層構(gòu)建來(lái)定義三層純度，包括決策樹(shù)需要的屬性純度。

定義6 粒 {c}i關(guān)于決策屬性D的純度定義為

(11)

其中，屬性c關(guān)于決策屬性D的純度定義為

(12)

命題2：三層純度具有如下集成關(guān)系

(13)

鑒于決策表的三層粒結(jié)構(gòu)[18]，式(10)～式(12)建立了三層純度體系，而式(13)則反映了三層純度之間的相互集成關(guān)系。

(1)純度Pure{c}i(Dj) 位于微觀底層 ({c}i,Dj)， 表征 {c}i關(guān)于Dj的識(shí)別能力。

(3)純度Pure{c}(D) 位于宏觀高層 (U/{c},U/D)， 統(tǒng)計(jì)求和n個(gè)中層純度Pure{c}i(D)(i=1,2,…,n) 以達(dá)到集成目的，用以表示U/{c} 關(guān)于U/D的識(shí)別性。

最終得到的純度Pure{c}(D) 通過(guò)量化屬性c關(guān)于決策類U/D的識(shí)別能力，從而建立了一種分類識(shí)別的機(jī)制。對(duì)此，該高層純度可以重新定義為“屬性純度”以反映其對(duì)條件屬性的直接選擇功能，即可作為決策樹(shù)歸納算法中分裂節(jié)點(diǎn)的相關(guān)度量函數(shù)，以保障模型的分類精度。后一節(jié)中，屬性純度直接作為決策樹(shù)歸納算法中的節(jié)點(diǎn)度量函數(shù)，并取得較好的分類效能。

對(duì)于上述三層純度和屬性純度，用一個(gè)示意圖對(duì)相關(guān)構(gòu)造和意義進(jìn)行深入分析、解釋。如圖1所示，中間含有豎線的長(zhǎng)方形表示非空有限的論域U， 對(duì)稱的左右兩個(gè)正方形代表決策屬性形成的兩個(gè)決策類U/D={D1,D2}。 3個(gè)不同的陰影橫帶表示U/{c}={{c}1,{c}2,{c}3} 的3個(gè)條件粒。

圖1 純度

(1) {c}1,{c}2,{c}3與D1,D2均相交，微觀底層 ({c}i,Dj) 共有6個(gè)純度。其中粒和粒交疊最大者是{c}2∩D2，但和{c}2的比率不大(由于{c}2和D1也有重疊部分)，該純度反映粒{c}2識(shí)別能力不強(qiáng)。相反，{c}1∩D1和{c}1的比值近似1，表明粒{c}1中樣本絕大多數(shù)也在D1中，故該高純度值對(duì)應(yīng)相應(yīng)的高分類識(shí)別能力，也表征決策規(guī)則{c}1→D1的高精確度。

(2)在中觀中層({c}i,U/D)的極大統(tǒng)計(jì)中，{c}1,{c}2,{c}3分別與D1,D2,D1產(chǎn)生最大純度，故獲得圖中標(biāo)識(shí)的3個(gè)純度

(3)在宏觀高層(U/{c},U/D)中，把上述中層統(tǒng)計(jì)量“加和”集成得到

Purec(D)=Pure{c}1(D)+Pure{c}2(D)+Pure{c}3(D)=
Pure{c}1(D1)+Pure{c}2(D2)+Pure{c}3(D1)

該純度描述基于條件分類U/{c}={{c}1,{c}2,{c}3}與決策分類U/D={D1,D2}的系統(tǒng)分類性能，故表征屬性c關(guān)聯(lián)于數(shù)據(jù)分類的重要性程度。

2.2 基于屬性純度的決策樹(shù)算法

命題3： Pure{c}(D)≤n， Purec(D)=n?γc(D)=1。

屬性純度以n為上確界，命題3反映了該上確界的等價(jià)條件。屬性依賴度的最大值和屬性純度的最大值有著對(duì)應(yīng)關(guān)系，說(shuō)明二者之間的關(guān)聯(lián)性。

下面分析闡述信息熵、屬性依賴度和屬性純度之間的機(jī)制關(guān)系，從而為提出合理的決策樹(shù)算法奠定基礎(chǔ)。就公式而言，信息熵描述不確定性信息，屬性依賴度和屬性純度則是知識(shí)的代數(shù)推理，故體系機(jī)制上是不同的，稱為異質(zhì)的。關(guān)聯(lián)于分類模型的精度追求，重點(diǎn)剖析后兩者。屬性依賴度是對(duì)正域的定性描述，是定性分析度量；對(duì)比地，屬性純度統(tǒng)計(jì)集成于三層純度的定量識(shí)別性，是定量分析度量。因此，屬性依賴度和屬性純度是同質(zhì)異態(tài)的，并有著最值關(guān)聯(lián)性(命題3)，二者和信息函數(shù)是異質(zhì)的。由此機(jī)制，下面構(gòu)建一個(gè)合理的決策樹(shù)算法，即DP(dependency-purity)算法。針對(duì)依賴度保障分類精度的主體作用，DP算法以“先屬性依賴度定性、后屬性純度定量”的二級(jí)選擇策略將屬性排序，實(shí)施特性選擇過(guò)程。DP算法有著分類能力上的優(yōu)勢(shì)。

(1)和RS算法類似，DP算法先用屬性依賴度定性優(yōu)選條件屬性，依賴度數(shù)值均為0時(shí)則引入同質(zhì)的屬性純度補(bǔ)充，這確保了對(duì)分類能力的一致追求，故體現(xiàn)出有效性。

(2)和C4.5算法對(duì)比而言，DP算法使用的二級(jí)度量函數(shù)都持續(xù)且一致地追求分類精度，故比C4.5算法更有分類能力上的優(yōu)勢(shì)。

算法1： DP算法

輸入： 一個(gè)決策表DT

輸出： 決策樹(shù)

(1) ?c∈C， 計(jì)算γ{c}(D);

(2) if ?γ{c}(D)≠0 then

(4) else

(6) end if

(7) 分裂節(jié)點(diǎn)在DT中誘導(dǎo)出知識(shí)分類

U/{c}={{c}1,{c}2,…,{c}n};

(8) for ?{c}i∈U/{c}

(9) 分別取 {c}i中的樣本將DT分割為子決策表

DT1,DT2,…,DTn;

(10) end for

(11) 對(duì)于決策表DT1,DT2,…,DTn， 遞歸地進(jìn)行第 (2)～ (10) 步， 直到所有條件屬性都被檢測(cè)或者樣本均包含于同一個(gè)類為止。

(12) 返回決策樹(shù)。

DP算法先使用屬性依賴度從知識(shí)?；治龅慕嵌榷ㄐ员Ｕ蠜Q策樹(shù)的分類精度，發(fā)生不協(xié)調(diào)的問(wèn)題時(shí)，再通過(guò)屬性純度維持知識(shí)推理的過(guò)程及分類效果。具體而言，步驟(1)～步驟(3)計(jì)算所有屬性的依賴度，通過(guò)數(shù)值排序，選擇具有最大值的屬性作為決策樹(shù)的分裂節(jié)點(diǎn)，使得決策樹(shù)模型結(jié)構(gòu)簡(jiǎn)單且精度較高。若出現(xiàn)不協(xié)調(diào)情況，依賴度數(shù)值均為0，步驟(4)～步驟(6)計(jì)算所有屬性的屬性純度，選擇具有最大值的屬性作為決策樹(shù)的分裂節(jié)點(diǎn)，避免使用異質(zhì)的信息函數(shù)降低模型的分類效能。步驟(1)～步驟(6)實(shí)現(xiàn)了節(jié)點(diǎn)的二級(jí)選擇，后面的過(guò)程與傳統(tǒng)的決策樹(shù)構(gòu)造方法一致，步驟(7)～步驟(11)用優(yōu)選的分裂屬性將決策表分割成多個(gè)子表，通過(guò)對(duì)這些子決策表遞歸前面的操作流程，最后得到一個(gè)決策樹(shù)模型。

3 實(shí)例分析

這里提供一個(gè)實(shí)例決策表，見(jiàn)表1。其中D表示1個(gè)決策屬性，并具有5個(gè)條件屬性和15個(gè)樣本。使用3種決策樹(shù)歸納算法構(gòu)造決策樹(shù)，即基于信息熵的算法C4.5[8]、基于粗糙集的算法RS[17]以及本文的算法DP，相關(guān)樹(shù)形結(jié)構(gòu)如圖2所示。下面闡述對(duì)應(yīng)算法的實(shí)施過(guò)程并分析相應(yīng)結(jié)果。

表1 實(shí)例決策

首先考慮C4.5算法。每個(gè)屬性的信息增益率為gainratio(c1)=0.0292，gainratio(c2)=0.1088，gainratio(c3)=0.1686，gainratio(c4)=0.0292，gainratio(c5)=0.0850。

屬性c3有著最大的信息增益率數(shù)值，故選為第一個(gè)節(jié)點(diǎn)。通過(guò)該屬性決策表可分為兩個(gè)子表，遞歸過(guò)程，最終如圖2(a)的決策樹(shù)模型即可得到。從圖2(a)中可以看到，屬性c4在被選為分裂點(diǎn)后，因?yàn)間ainratio(c1)=0.0248，gainratio(c2)=0，gainratio(c5)=0.0728。

圖2 3種算法構(gòu)造生成的決策樹(shù)

c5具有最大的信息增益率，將c5作為下一個(gè)分裂節(jié)點(diǎn)。關(guān)于最終結(jié)果，所建決策樹(shù)的葉子數(shù)為8，其中只包含一個(gè)樣本的葉節(jié)點(diǎn)個(gè)數(shù)為5。

分析RS算法。 ?i∈{1,2,3,4,5}，γ{ci}(D)=0， 每一個(gè)條件屬性的依賴度值為0，出現(xiàn)不協(xié)調(diào)性。此時(shí)，需要轉(zhuǎn)為求助信息增益率。因此，該算法和基于信息熵的算法有著相同的樹(shù)形結(jié)構(gòu)，如圖2(a)所示。這體現(xiàn)RS算法以屬性依賴度為度量函數(shù)的缺陷。

最后解釋DP算法。先計(jì)算出三層純度值，見(jiàn)表2。而條件屬性是二分類的 (n=2)， 決策類也是二分結(jié)構(gòu) (m=2)

D1={x1,x2,…,x7}，D2={x8,x9,…,x15}。

對(duì)此，一個(gè)屬性應(yīng)具有4種底層純度，向上最大取樣后還有兩種中層純度，最終再向上集成出一種高層純度(即屬性純度)。以表2關(guān)注到屬性純度，進(jìn)行相關(guān)特性選擇輸出決策樹(shù)。5個(gè)條件屬性的純度為Pure{c1}(D)=1.2500，Pure{c2}(D)=1.4000，Pure{c3}(D)=1.5000，Pure{c4}(D)=1.2500，Pure{c5}(D)=1.3933。

表2 實(shí)例決策表的三層純度

選擇具有最大純度的屬性c3作為第一個(gè)分裂節(jié)點(diǎn)。對(duì)分裂后的子表進(jìn)行類似的遞歸操作，即可輸出一個(gè)如圖2(b)的決策樹(shù)。該模型的葉子數(shù)為7，其中只包含一個(gè)樣本的葉節(jié)點(diǎn)個(gè)數(shù)為3。

針對(duì)圖2(a)和圖2(b)兩個(gè)模型之間的差異，可以體現(xiàn)DP算法的改進(jìn)性。而DP算法的構(gòu)建流程中，在屬性c4作為分裂節(jié)點(diǎn)后，具有最大純度的c2將作為下一個(gè)分裂節(jié)點(diǎn)，因?yàn)镻ure{c1}(D)=1.2143，Pure{c2}(D)=1.3333，Pure{c5}(D)=1.3000。

這個(gè)過(guò)程與上述C4.5算法、RS算法中的 “c4后選c5” 有所不同。對(duì)比C4.5算法、RS算法，DP算法生成的決策樹(shù)葉子數(shù)從8減少為7，只含有一個(gè)樣本分類的葉節(jié)點(diǎn)個(gè)數(shù)也相應(yīng)從5降低為3。由此可知，DP算法構(gòu)建的模型結(jié)構(gòu)更簡(jiǎn)單；由于不同的分類規(guī)則有更多的樣本支持，故DP算法的決策分類能力也得到提升?？傊纠Y(jié)果表明，DP算法比C4.5算法、RS算法更加優(yōu)越。

4 數(shù)據(jù)實(shí)驗(yàn)

這里依托UCI數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)實(shí)驗(yàn)，實(shí)施C4.5算法[8]、RS算法[17]、DP算法、ID3的改進(jìn)算法(NID3)[12]來(lái)構(gòu)建4種決策樹(shù)，并通過(guò)對(duì)比分析來(lái)驗(yàn)證DP算法的有效性與優(yōu)越性。

這里采用UCI機(jī)器學(xué)習(xí)庫(kù)[19]中的7個(gè)連續(xù)型數(shù)據(jù)集，相關(guān)的決策表信息見(jiàn)表3。所有的數(shù)據(jù)集都只具有一個(gè)決策屬性；部分?jǐn)?shù)據(jù)有缺失值，這里刪除具有缺失值的對(duì)應(yīng)樣本；而FM數(shù)據(jù)集一共有60種決策分類，主要截取前4個(gè)決策類中的樣本實(shí)施實(shí)驗(yàn)；采用C4.5算法[8]對(duì)7個(gè)數(shù)據(jù)集進(jìn)行離散化預(yù)處理。

表3 7個(gè)UCI數(shù)據(jù)集的決策表信息

針對(duì)每種數(shù)據(jù)集，分別采用C4.5算法、RS算法、DP算法、NID3算法來(lái)構(gòu)建4種決策樹(shù)模型，并主要采用準(zhǔn)確度與葉子數(shù)兩類評(píng)估指標(biāo)。此外，把7個(gè)數(shù)據(jù)集的結(jié)果進(jìn)行統(tǒng)計(jì)，提供準(zhǔn)確度與葉子數(shù)的算術(shù)平均值。相關(guān)決策樹(shù)結(jié)果見(jiàn)表4。針對(duì)同一數(shù)據(jù)集，記號(hào)*標(biāo)識(shí)獲得一致決策樹(shù)結(jié)構(gòu)的算法，而記號(hào)**標(biāo)識(shí)4種算法中的相關(guān)最優(yōu)值。為形象分析，表4中的準(zhǔn)確度與葉子數(shù)還分別用圖3、圖4標(biāo)識(shí)出來(lái)。

基于表4及圖3、圖4的結(jié)果，可以從準(zhǔn)確度與葉子數(shù)兩個(gè)角度來(lái)對(duì)比分析C4.5算法、RS算法、DP算法、NID3算法。在Iris數(shù)據(jù)集中，4種算法生成的決策樹(shù)的結(jié)構(gòu)是完全相同的；此外，在Wine數(shù)據(jù)集中RS算法與DP算法也給出一致結(jié)構(gòu)。關(guān)于分類準(zhǔn)確度：

圖3 4種決策樹(shù)算法的準(zhǔn)確度對(duì)比

圖4 4種決策樹(shù)算法的葉子數(shù)對(duì)比

表4 4種決策樹(shù)算法關(guān)于準(zhǔn)確度與葉子數(shù)的實(shí)驗(yàn)結(jié)果

(1)對(duì)于Glass數(shù)據(jù)集， DP算法具有明顯優(yōu)勢(shì)，即顯著優(yōu)于C4.5算法、 RS算法、 NID3算法。對(duì)于FM， DP算法的分類準(zhǔn)確度最高，且顯著優(yōu)于NID3算法；

(2)對(duì)于Iris、Wine，RS算法具有最優(yōu)化準(zhǔn)確度，DP算法與RS算法具有一致決策樹(shù)結(jié)構(gòu)從而具有一致分類能力。同時(shí)， DP算法取得第二的優(yōu)勢(shì)，且與最優(yōu)的RS算法非常接近；

(3)對(duì)于剩余的BCC、ILPD、Wpbc，NID3算法具有最優(yōu)的準(zhǔn)確度，此時(shí)DP算法取得第二的優(yōu)勢(shì)。同時(shí)， DP

算法結(jié)果與NID3算法的差距并不明顯，但卻明顯優(yōu)于C4.5算法、 RS算法。

關(guān)于葉子數(shù)：

(1)對(duì)于Iris、Wine，DP算法是最優(yōu)的(或共同最優(yōu))；

(2)對(duì)于Glass，RS算法取得最優(yōu)葉子數(shù)，而DP算法具有一個(gè)中間的葉子數(shù)且與RS算法結(jié)果靠近；

(3)對(duì)于FM，C4.5算法取得最優(yōu)葉子數(shù)， DP算法取得第二優(yōu)且與C4.5算法結(jié)果很接近；

(4)對(duì)于BCC、ILPD、Wpbc，NID3算法具有最小的葉子數(shù)，但DP算法的結(jié)果也是靠近NID3算法的。

最后從表4的平均統(tǒng)計(jì)來(lái)看， DP算法的分類精度比較顯著地優(yōu)于C4.5、RS、NID3；此外，DP算法的葉子數(shù)處于第二優(yōu)的位置，即其略遜于RS算法的最優(yōu)值但優(yōu)于剩余的C4.5與NID3。綜上結(jié)果與分析可見(jiàn)， DP算法是有效的，總體上具有比C4.5算法、 RS算法、 NID3算法更好的決策樹(shù)分類結(jié)果。

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

剖析基于依賴度的決策樹(shù)歸納算法存在的不協(xié)調(diào)與度量轉(zhuǎn)換問(wèn)題，提出屬性純度并由此構(gòu)建決策樹(shù)歸納算法DP。首先，屬性純度來(lái)源于識(shí)別刻畫(huà)與三層構(gòu)建，其與經(jīng)典決策樹(shù)分裂屬性度量函數(shù)既有聯(lián)系又有區(qū)別。信息函數(shù)描述?；Y(jié)構(gòu)的不確定信息，主要采用信息觀點(diǎn)；屬性依賴度與屬性純度直接從代數(shù)角度表征識(shí)別精度，但分別關(guān)聯(lián)于定性區(qū)域與定量統(tǒng)計(jì)；可見(jiàn)，屬性依賴度與屬性純度異質(zhì)于信息熵，而兩者具有不同的定性定量形態(tài)，即兩者是同質(zhì)異態(tài)的。由此度量機(jī)制， DP算法具有先屬性依賴度后屬性純度的二級(jí)聯(lián)動(dòng)機(jī)制，有效改進(jìn)了C4.5與RS兩種存在的決策樹(shù)歸納算法。實(shí)例分析與數(shù)據(jù)實(shí)驗(yàn)均驗(yàn)證了DP算法的有效性與改進(jìn)性。屬性純度以及三層純度還值得深入研究， DP算法也值得廣泛推廣以獲取實(shí)際應(yīng)用效能。