劉振宇，宋曉瑩

(1. 東北大學(xué) 軟件中心，遼寧 沈陽 110819; 2. 大連東軟信息學(xué)院 網(wǎng)絡(luò)安全與計算技術(shù)重點實驗室，遼寧 大連 116023)

決策樹是一種常見的歸納式學(xué)習(xí)方法，可用于分類和回歸問題.與其他機器學(xué)習(xí)模型相比，決策樹具有泛化錯誤率低、可解釋性強、參數(shù)少、生成速度快、能夠應(yīng)對冗余屬性以及具有相當(dāng)不錯的抗噪能力等優(yōu)點.雖然決策樹算法出現(xiàn)比較早，但至今仍然是研究熱點之一[1-2]，并在知識發(fā)現(xiàn)、模式識別等領(lǐng)域有著廣泛的應(yīng)用[3-4].

在分類問題中，用于預(yù)測的屬性可能分屬于不同的數(shù)據(jù)類型，例如，實數(shù)型、整型、布爾型、枚舉型、字符串型等.按照其是否存在有序性，這些屬性可歸為數(shù)值型屬性和分類型屬性兩個大類.像“身高”、“年齡”一樣的屬性可采用實數(shù)或整數(shù)表示，屬于數(shù)值型屬性.像“學(xué)生專業(yè)”、“興趣愛好”等屬性，雖然可以使用整數(shù)枚舉或字符串等表示，但由于其屬性值之間的無序性，這些屬性屬于分類型屬性.特別地，布爾型的屬性既可視為數(shù)值型又可以視為分類型.

經(jīng)典的決策樹算法，例如C4.5[5]，屬于單變量決策樹.算法劃分一個結(jié)點時，采用窮舉的方式搜索能夠使當(dāng)前結(jié)點不純度下降最大的屬性.如果被選中的是分類型屬性，當(dāng)前結(jié)點按照分類型屬性的屬性值個數(shù)分成多個子結(jié)點，當(dāng)前結(jié)點中的樣本依據(jù)其屬性值進入相應(yīng)子結(jié)點.如果被選中的是數(shù)值型屬性，還需要搜索一個合適的劃分點進行2路劃分，當(dāng)前結(jié)點中每個樣本按照式(1)劃分到左右兩個子結(jié)點之中.

xl≤θl.

(1)

式中：xl表示待劃分樣本在屬性Al上的取值；θl為劃分點.在這種劃分方式下，數(shù)值屬性空間中的劃分超平面與坐標(biāo)軸平行.為此，單變量決策樹也稱軸平行決策樹.

另一經(jīng)典單變量決策樹算法CART[6]生成二叉樹，主要為數(shù)值型數(shù)據(jù)的分類和回歸問題而設(shè)計.當(dāng)面對具備三個或以上屬性值的分類型屬性時，CART算法需要依據(jù)GINI指數(shù)下降程度，將多個屬性值聚合為兩組.甚至有些機器學(xué)習(xí)框架中提供的CART組件根本不支持分類型屬性.

與單變量決策樹相對應(yīng)的是多變量決策樹，這些決策樹在劃分結(jié)點時需要聯(lián)合多個預(yù)測屬性.如果聯(lián)合多個預(yù)測屬性的方式是線性組合，結(jié)點中的樣本將依據(jù)式(2)劃分到左右兩個子結(jié)點之中.

(2)

式中，al和p分別表示第l個屬性的系數(shù)和預(yù)測屬性的個數(shù).在確定了連同θ在內(nèi)的p+1個系數(shù)后，就唯一確定了劃分超平面，這個超平面不一定平行于某個坐標(biāo)軸.因此，這種多變量決策樹也稱為斜決策樹.由于斜劃分的備選超平面范圍遠(yuǎn)遠(yuǎn)大于軸平行劃分，因此，普遍認(rèn)為，面對同樣的數(shù)據(jù)集合，斜劃分往往能夠產(chǎn)生更小的決策樹，從而得到更好的泛化性能，但需要付出較大的計算代價.

在近幾十年中大量的斜劃分方法被提出.CART-LC[6]是CART的斜劃分版本，它采用爬山法，隨機擾動各個屬性在空間中的系數(shù)，以確定分割超平面.SADT[7]使用模擬退火算法搜索超平面，以避免陷入局部最優(yōu)解.OC1[8]結(jié)合了CART-LC和SADT的思想.FDT[9]是使用線性判別分析方法構(gòu)建的斜決策樹，受FDA(Fisher’s discriminant analysis)方法限制，F(xiàn)DT僅能應(yīng)用于二分類問題.在文獻(xiàn)[10]中，作者分別嘗試DFA、稀疏線性判別分析以及嶺回歸三種方法確定結(jié)點劃分的超平面.文獻(xiàn)[11]中的HHCART，首先求得原始數(shù)據(jù)的特征向量，然后將數(shù)據(jù)映射至新的坐標(biāo)空間，最后在新空間中搜索最佳軸平行劃分超平面(相當(dāng)于原始空間的斜超平面).文獻(xiàn)[12]中的分類器結(jié)合了神經(jīng)網(wǎng)絡(luò)和決策森林，其中決策森林中的樹采用 MPSVM方法產(chǎn)生斜劃分超平面.

在以上回顧的多變量決策樹算法中，所采用的方法均不支持分類型屬性.這使得處理帶有分類型屬性的數(shù)據(jù)時，要通過CRIMCOORD[13]，OneHot Encoder等方法將分類型屬性轉(zhuǎn)換為一個或多個數(shù)值型屬性.這種轉(zhuǎn)換可能為分類問題帶來新的偏差，從而降低模型的泛化能力.

為解決分類型屬性之間以及分類型屬性與數(shù)值型屬性之間無法聯(lián)合在一起進行決策樹結(jié)點劃分的問題，本文提出一種基于距離尺度的、加權(quán)聚類的結(jié)點劃分方法.通過定義樣本集合在分類型屬性上的中心以及樣本到中心的距離，能夠使分類型屬性像數(shù)值型屬性一樣參與聚類過程.實驗結(jié)果表明，該劃分方法產(chǎn)生的決策樹在分類型數(shù)據(jù)以及混合型數(shù)據(jù)上，均具備很好的泛化能力.

1 相關(guān)算法

本文提出的算法需要使用Relief-F算法為屬性加權(quán)，使用改進后的k-means算法劃分結(jié)點.

1.1 Relief-F算法

Relief-F算法是著名的特征(屬性)選擇算法Relief在多分類問題上的改進，算法根據(jù)各個屬性與類別的相關(guān)性賦予每個屬性不同的權(quán)重.計算屬性A的權(quán)重時，從訓(xùn)練集中隨機選擇一個樣本R，然后從和R同類的樣本中尋找最近鄰樣本H，稱為猜中近鄰，從和R不同類的樣本中尋找最近鄰樣本M，稱為猜錯近鄰.如果R和H在屬性A上的距離小于R和M的距離，則說明該屬性對區(qū)分同類和不同類的最近鄰是有益的，應(yīng)該增加該屬性的權(quán)重；反之，說明該屬性對區(qū)分同類和不同類的最近鄰起負(fù)面作用，應(yīng)該降低該屬性的權(quán)重.

Relief-F算法需要進行m次抽樣，為每個抽取的樣本，在每個類中尋找knn個最近鄰，按照公式(3)計算屬性A的權(quán)重:

(3)

式中:p(C)表示類別C樣本在全體樣本中占的比例;Mj(C)表示類別C中與R距離最近的第j個鄰居;diff(A,R1,R2)表示樣本R1和R2在屬性A上的距離，該距離通過式(4)計算得出.在尋找最近鄰和計算權(quán)重的步驟中都需要使用這個距離.

(4)

1.2 k-means,k-modes和k-prototypes算法

k-means算法是一種基于樣本到原型距離評價尺度的聚類算法，其思想為:設(shè)p個數(shù)值屬性的樣本集D包含n個樣本，需要被聚成k簇C1,C2,…，Ck，首先隨機選擇一些樣本作為初始的k個簇的中心μ1,μ2,…，μk；然后對于每個樣本xi，使用式(5)計算該樣本的簇標(biāo)簽:

(5)

式中，‖xi-μj‖為歐氏距離.所有樣本得到簇標(biāo)簽后，使用式(6)更新每個簇中心:

(6)

重復(fù)計算式(5)和式(6)，直到達(dá)到預(yù)設(shè)的循環(huán)次數(shù)或者式(7)表示的平方誤差收斂至局部最優(yōu)解.

(7)

k-means算法僅能應(yīng)用在數(shù)值屬性數(shù)據(jù)集，文獻(xiàn)[14]中的k-modes和k-prototypes算法分別是k-means算法在分類型屬性數(shù)據(jù)集和混合型數(shù)據(jù)集上的變體.k-modes處理分類型屬性數(shù)據(jù)集時，每個簇的中心由相應(yīng)簇內(nèi)樣本在分類屬性上的眾數(shù)來表示，計算樣本與簇中心在某個分類型屬性上的距離時，使用公式(4)相應(yīng)的部分.k-prototypes處理混合型屬性數(shù)據(jù)集時，相當(dāng)于使用k-means算法中的方式處理數(shù)值屬性子集，使用k-modes算法中的方式處理分類型屬性子集.樣本xi與簇心μj的距離dis(xi,μj)采用公式(8)計算:

dis(xi,μj)=(1-γ)·dis_n(xi,μj)+
γ·dis_c(xi,μj).

(8)

式中:dis_n(xi,μj)和dis_c(xi,μj)分別代表數(shù)值屬性子集和分類屬性子集的距離;γ是一個0到1之間的實數(shù)，用于調(diào)整公式中兩項的占比.

2 本文算法(CMDT)

2.1 加權(quán)聚類劃分方法

本文提出的結(jié)點劃分方法不僅要聯(lián)合多個變量，而且要對結(jié)點進行多路劃分，這種多路劃分可以看作是多次2路劃分的組合.本文采用聚類算法k-means作為基本的劃分方法.這樣做是由于以下四個方面的原因:其一，多路劃分生成的樹模型較淺，容易被解釋；其二，直接面向k分類問題使用k路劃分，不必糾結(jié)于多分類問題到二分類問題的轉(zhuǎn)換；其三，由于屬性空間中距離相近的點(樣本)有很大的幾率屬于同一類別，使得在不使用窮盡搜索的情況下，仍能使得結(jié)點劃分后不純度得到很大的下降；其四，k-means算法簡單高效，使得結(jié)點劃分的速度接近軸平行劃分方法，而明顯優(yōu)于大部分斜劃分方法.

簡單地應(yīng)用k-means算法進行結(jié)點劃分也存在一些問題，畢竟k-means算法是一種無監(jiān)督學(xué)習(xí)算法，它不會考慮分類問題中各個預(yù)測屬性與分類目標(biāo)屬性的相關(guān)性.在計算樣本到簇中心距離時，平等地看待全部預(yù)測屬性，即使聚類結(jié)果在某個聚類效果評價指標(biāo)上得到了較高的分?jǐn)?shù)(例如式(7)收斂到了最小值)，但這不等于得到了一個好的結(jié)點劃分結(jié)果. 特別是在面對存在大量不相關(guān)屬性的數(shù)據(jù)集時，平等看待全部預(yù)測屬性的做法，會減弱“樣本到簇心距離”與“分類目標(biāo)屬性”的相關(guān)性，進而產(chǎn)生與目標(biāo)偏離的結(jié)點劃分結(jié)果，最終導(dǎo)致生成的決策樹泛化能力差、結(jié)構(gòu)復(fù)雜(結(jié)點多).解決這一問題的一個方法就是對屬性加權(quán).如果能夠給予與分類目標(biāo)強相關(guān)的預(yù)測屬性較大的權(quán)重，放大該屬性對距離的貢獻(xiàn)，反之，則給予較小的權(quán)重，減小弱相關(guān)和不相關(guān)屬性對距離的貢獻(xiàn)，這樣便使k-means算法的優(yōu)化目標(biāo)與結(jié)點劃分的目標(biāo)趨向一致.

為了說明屬性加權(quán)對于分類問題的作用，使用數(shù)據(jù)集iris進行了簡單的實驗，iris數(shù)據(jù)集的150個樣本來自三個類別，每個類別50個樣本.直接使用k-means算法聚類，錯分樣本10個，具體的結(jié)果如表1所示.

表1 iris屬性未加權(quán)的聚類結(jié)果

然后，調(diào)用Relief-F算法得到4個屬性的權(quán)重，分別為0.09，0.14，0.34和0.39.k-means聚類過程中，按照式(9)計算樣本與簇心的加權(quán)歐氏距離.錯分樣本6個，具體結(jié)果如表2所示.

(9)

表2 iris屬性加權(quán)的聚類結(jié)果

綜上，提出的結(jié)點劃分方法可簡單描述為屬性加權(quán)和聚類兩個步驟，具體流程如算法1所示.本文提出的決策樹算法CMDT與大部分決策樹算法一樣，采用自頂向下、遞歸的方式生長決策樹，split用于結(jié)點劃分，待樹停止生長后，使用悲觀剪枝算法對樹進行后剪枝操作，以避免過擬合現(xiàn)象的出現(xiàn).

算法1:split

輸入:當(dāng)前結(jié)點的數(shù)據(jù)集合D.

輸出:將D劃分C1,C2,…,Ck，各簇的中心μ1，μ2，μk，以及各屬性的權(quán)重w.

1.使用D中樣本類別數(shù)量作為分簇的數(shù)量k.

2.將D作為輸入，調(diào)用Relief-F得到w.

3.在w中找到最大權(quán)重存入變量wmax，剔除權(quán)值小于β·wmax的屬性，β∈[0,1]，默認(rèn)值為0.2.

4.使用D中各類別樣本的中心初始μ1，μ2，…，μk.

5.For 1 toImaxDo

6. 依照距離最近原則劃分樣本，形成C1,C2,…,Ck.

7. 重新計算μ1，μ2,…,μk.

8. If各簇中心μ1，μ2,…，μk與前一輪迭代時無明顯變化Then Break For

9.End For

10.ReturnC1,C2,…,Ck，μ1，μ2,…，μk以及w.

2.2 分類屬性

2.1節(jié)所闡述的結(jié)點劃分方法可以直接應(yīng)用在數(shù)值屬性上.對于分類型屬性來說，在屬性加權(quán)部分仍然可以使用Relief-F算法，在聚類步驟需要定義簇心的表示方法以及樣本到簇心距離的計算方法.1.2節(jié)提及的k-modes算法滿足這樣的要求.k-modes算法是k-means在分類型屬性的變體，它使用分類型屬性的眾數(shù)mode代替數(shù)值型屬性的均值mean，計算樣本到簇中心距離時，分類屬性上采用相同值取0，不同值取1的方式.然而，這種方式計算出的距離不夠精確, 并且當(dāng)某個屬性出現(xiàn)多個眾數(shù)時, 不同的眾數(shù)選擇可能得到完全相反的結(jié)論[15].

下面使用一個例子來說明這個問題:假設(shè)由A和B兩個分類型屬性描述的兩個簇C1和C2都包含10個樣本，樣本的統(tǒng)計分布如表3所示.

表3 屬性值分布

簇C1中，90%的樣本在A上的值為a1，而C2中，只有40%的樣本在A上的值為a1，a1在兩個簇中都是眾數(shù)，這使得在判斷某個樣本距離C1和C2誰更近時，屬性A沒有任何作用.屬性B在C1和C2中分別存在2個眾數(shù).假設(shè)存在樣本q=(a1,b1)，如果為C1選擇簇心μ1=(a1,b1)，為C2選擇簇心μ2=(a1,b3)，得到q與μ1的距離為0，q與μ2的距離為1，得到q屬于C1的結(jié)論；如果為C1選擇簇心μ1=(a1,b2)，為C2選擇簇心μ2=(a1,b1)，得到q與μ1的距離為1，q與μ2的距離為0，則得到q屬于C2的結(jié)論.

針對使用各個屬性的眾數(shù)表示簇中心帶來的計算距離不夠精確、存在二義性等問題，受到文獻(xiàn)[15]中k-summary算法的啟發(fā)，本文使用每個分類屬性值的概率分布估計來定義簇心的表示方法及樣本到簇心距離的計算方法，供結(jié)點劃分時使用.

定義1設(shè)包含p個分類型屬性，n個樣本的數(shù)據(jù)集D分為k簇，簇Cj中第l個屬性Al有d個不同取值ω1,ω2,…，ωd，令Cj,xl表示第l個屬性上取值為xl的樣本子集，xl∈{ω1,ω2,…,ωd},條件概率被估計為

(10)

定義Sj,l為Cj中關(guān)于Al的各個屬性值的匯總:

Sj,l={P(ω1|j),P(ω2|j),…,P(ωd|j)}.

(11)

定義2使用Sj,l代替眾數(shù)，定義簇Cj的中心μj為由各個屬性的Sj,l組成的向量:

μj=(Sj,1,Sj,2,…,Sj,p).

(12)

定義3定義diff(Al,ω,Sj,l)為屬性值ω與Sj,l的距離:

(13)

定義4在已知屬性權(quán)重向量w的情況下，樣本xi與簇心μj的加權(quán)距離為

(14)

在之前的例子中，假設(shè)所有屬性的權(quán)重均為1，依據(jù)式(14)，樣本q=(a1,b1)與表3中C1和C2中心距離分別為0.7=0.1+0.6和1.2=0.6+0.6，說明q與簇C1更接近，這符合人們的直觀感覺.

對于只包括分類型屬性的數(shù)據(jù)集，僅僅是將split的第4,7步驟中計算簇心的公式由計算均值改為計算式(12)，第6步驟中計算樣本到簇心距離的計算公式由式(14)代替式(9).對于混合類型的數(shù)據(jù)集，簇心向量由兩部分構(gòu)成：一部分是數(shù)值屬性的均值；一部分如式(12)所示的匯總信息.計算樣本到簇心距離時，使用加權(quán)歐氏距離計算數(shù)值屬性部分dis_n，使用式(14)計算分類屬性部分dis_c，再使用式(8)將兩部分結(jié)合.確定式(8)系數(shù)γ時，以GINI指數(shù)作為評價指標(biāo)，在{0.1,0.2,…,0.9}中選擇使GINI指數(shù)下降最大的值.

3 實驗結(jié)果與分析

本節(jié)將通過兩部分實驗來驗證提出算法.第一部分實驗用于說明在帶有分類型屬性的數(shù)據(jù)集上，屬性加權(quán)、聚類以及使用屬性值分布匯總代替眾數(shù)的有效性；第二部分實驗是與經(jīng)典決策樹算法比較泛化正確率和結(jié)點數(shù)量.

3.1 數(shù)據(jù)集

表4展示了實驗使用的10個數(shù)據(jù)集，這些數(shù)據(jù)集源于UCI[16].其中，序號1～5為純分類型屬性數(shù)據(jù)集，6～10為混合型數(shù)據(jù)集.表4“屬性數(shù)”一列中，混合型數(shù)據(jù)集的屬性數(shù)以“數(shù)值型屬性數(shù)+分類型屬性數(shù)”的形式給出.另外，原始數(shù)據(jù)集Abalone是29分類問題，本文將其視為3分類問題，原始類別1～8歸為第1類，9和10歸為第2類，其余類別歸為第3類.

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

3.2 對比不同的劃分方法

為了驗證屬性加權(quán)、聚類以及特殊處理分類型屬性的作用，實現(xiàn)了8個不同的結(jié)點劃分方法產(chǎn)生決策樹(見表5).算法0不進行聚類，直接使用各個類別的中心作為錨點，分類型屬性使用眾數(shù)代替數(shù)值屬性的均值作為錨點向量的分量，計算樣本到錨點距離時，各個屬性上的距離使用式(4)計算得出并求和；算法1與算法0的不同之處是，使用Relief-F計算每個屬性的權(quán)重，刪除小于最大權(quán)重1/5的屬性后，樣本和錨點距離使用權(quán)重向量和式(4)計算得到的距離向量的點積；算法2與算法0的區(qū)別在于加入了聚類過程，k-modes算法用于分類數(shù)據(jù)集，k-prototypes算法用于混合型數(shù)據(jù)集；算法3結(jié)合了算法1和算法2；算法4～7分別對應(yīng)算法0～3，分類型屬性上關(guān)于簇心和樣本到簇心距離計算采用2.2節(jié)描述的方法.算法7就是本文提出的算法.實驗中生成的決策樹均采用最小父母數(shù)為5的預(yù)剪枝策略，并對生成的決策樹使用悲觀剪枝算法進行剪枝操作.實驗報告的正確率為10次10折交叉驗證的平均值.

表5展現(xiàn)了8個算法在10個數(shù)據(jù)集上的正確率，每行中最好的正確率被加粗.在10個數(shù)據(jù)集中，除了CMC和Zoo外，算法7都獲得了最好的準(zhǔn)確率，相比算法0正確率平均高出11.08%.分別考慮3個方面的改善:算法1,3,5,7比算法0,2,4,6平均高出5.19%，這是屬性加權(quán)帶來的改善；算法2,3,6,7比算法0,1,4,5平均高出4.27%，這是聚類帶來的改善；算法4～7比算法0～3平均高出1.31%，這是樣本屬性值統(tǒng)計分布代替眾數(shù)的改善.特別地，算法4相比于算法0有所下降，這說明同時聯(lián)合多個分類型屬性對結(jié)點進行劃分時，在沒有結(jié)合聚類以及屬性加權(quán)的情況下，詳細(xì)地統(tǒng)計各個類別在每個屬性上屬性值的樣本分布反而不如簡單地統(tǒng)計各個類別在每個屬性上的眾數(shù).

表5 對比不同劃分方法的正確率

3.3 與其他決策樹對比

為了驗證提出算法的能力，選擇流行機器學(xué)習(xí)工具Weka和Scikit-learn中的決策樹進行對比，Weka中的J48是對C4.5的實現(xiàn)，Scikit-learn中的決策樹模型在默認(rèn)情況下是CART算法的優(yōu)化.同樣的10次10折交叉驗證被使用，實驗報告平均正確率和結(jié)點數(shù)量.

表6展示了實驗結(jié)果，最好的結(jié)果被加粗顯示.正確率方面，本文算法在10個數(shù)據(jù)集上獲得了77.79%的平均正確率，分別比其他兩個算法高2.93%和0.41%.模型結(jié)構(gòu)復(fù)雜度方面，本文算法平均結(jié)點數(shù)量略小于C4.5，而遠(yuǎn)小于CART.

表6 CMDT與C4.5和CART對比

4 結(jié) 語

針對絕大部分多變量決策樹只能聯(lián)合數(shù)值型屬性，而不能直接為帶有分類型屬性數(shù)據(jù)集進行分類的問題，提出一種可聯(lián)合多種類型屬性的多變量決策樹算法.該方法使用基于距離的聚類算法劃分決策樹中非葉結(jié)點，快速生成決策樹；通過為屬性加權(quán)的方式代替經(jīng)典決策樹算法中使用不純度指標(biāo)進行啟發(fā)搜索的過程；使用樣本屬性值分布統(tǒng)計來定義簇心表示及距離計算，使得分類型屬性能以與數(shù)值型屬性相似的方式參與加權(quán)聚類.實驗結(jié)果表明，本文提出的算法具備比經(jīng)典決策樹更好的泛化正確率，以及更簡潔的結(jié)構(gòu).