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

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

0 引 言

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

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

1 決策樹基礎(chǔ)

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

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

1.1 決策表

決策表可表示為4元組

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

(1)

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

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

1.2 基于信息熵的決策樹算法

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

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

(2)

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

(3)

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

(4)

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

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

(5)

其中

(6)

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

1.3 基于屬性依賴度的決策樹算法

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

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

(7)

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

(8)

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

(9)

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

2 基于屬性純度的決策樹歸納算法

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

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

2.1 三層純度與屬性純度

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

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

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

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

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

(2) {c}i關(guān)于Dj是絕對不純的，若 {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的識別程度，及對應(yīng)分類決策 {c}i→Dj的可信度。這一度量能夠有效支撐相關(guān)的定性理解。顯然， Pure{c}i(Dj)∈[0,1]。

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

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

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

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

定義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的識別能力。

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

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

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

圖1 純度

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

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

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

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 基于屬性純度的決策樹算法

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

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

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

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

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

算法1： DP算法

輸入： 一個決策表DT

輸出： 決策樹

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

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

(4) else

(6) end if

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

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

(12) 返回決策樹。

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

3 實例分析

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

表1 實例決策

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

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

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

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

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

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

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

對此，一個屬性應(yīng)具有4種底層純度，向上最大取樣后還有兩種中層純度，最終再向上集成出一種高層純度(即屬性純度)。以表2關(guān)注到屬性純度，進(jìn)行相關(guān)特性選擇輸出決策樹。5個條件屬性的純度為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 實例決策表的三層純度

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

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

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

4 數(shù)據(jù)實驗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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