軟聚類節(jié)點分裂層次模型

羅森林， 孫志鵬， 潘麗敏

(北京理工大學(xué) 信息與電子學(xué)院，北京 100081)

分類決策樹算法，如ID3[1]、CART[2]和C4.5[3]，訓(xùn)練速度快，輸出結(jié)果可解釋性強，在實際生產(chǎn)生活中有廣泛的應(yīng)用. 但傳統(tǒng)的節(jié)點分裂方法和判定方法，生成的模型存在結(jié)構(gòu)冗余且過擬合等問題，限制了決策樹算法判定效果的進一步提升，解決上述問題對于提高決策樹性能具有重要的意義.

優(yōu)化決策樹節(jié)點分裂算法是提升決策樹算法判定效果的有效途徑. Deng等[4]對分裂屬性添加了懲罰項，在保證分類精度同時降低了屬性冗余度. Chandra等[5]DCM節(jié)點分裂方法，提高了分裂子節(jié)點中樣本純度，簡化了樹的結(jié)構(gòu). Hu等[6]將香農(nóng)信息熵和優(yōu)勢粗糙集相結(jié)合，提出了排序互信息(rank mutual information，RMI)方法用于進行節(jié)點分裂，有效增強了決策樹對次序類別數(shù)據(jù)的判別效果. 陳建凱等[7]優(yōu)化了排序互信息計算方法，大大提高了決策樹生成效率. 引入隨機選擇方法[8]或Tsallis信息熵[9]可以一定程度上緩解由于分裂算法貪心思想導(dǎo)致的局部最優(yōu)解問題，提高模型效果.

此外采用組合模型方法也可以提升決策樹判定效果. 利用bagging[10]或boosting[11]方法將多個決策樹結(jié)合起來構(gòu)成組合模型，可以克服單個樹的過擬合問題. 采用模型樹(logistic model tree，LMT)方法[12]，用邏輯回歸模型替代決策樹葉子節(jié)點，可以一定程度上緩解決策樹不穩(wěn)定且容易過擬合的問題.

通過優(yōu)化節(jié)點分裂算法或改變樹形結(jié)構(gòu)的方式，可以有效地提升決策樹算法效果，但是忽略了兩個問題：①節(jié)點分裂每次在部分屬性上采用線性方法實現(xiàn)，限制了對樣本子空間的劃分方式，需要多次分裂才能處理復(fù)雜的非線性分類問題，增加了模型結(jié)構(gòu)的復(fù)雜度；②決策樹采用硬分裂方法劃分樣本空間，由于決策樹本身的樹形結(jié)構(gòu)，若上層節(jié)點劃分出現(xiàn)錯誤，極易對最終判定結(jié)果產(chǎn)生影響，即存在誤差遷移問題.

針對上述問題，本文提出了一種軟聚類節(jié)點分裂層次模型(soft clustering node split hierarchical model，SCNSHM). 通過軟聚類節(jié)點分裂方法對樣本空間高效劃分，有效精簡模型結(jié)構(gòu)，采用層次結(jié)構(gòu)判別方法，將所有葉子節(jié)點處決策模型輸出結(jié)果加權(quán)求和對新樣本進行類別預(yù)測，有效緩解了決策樹的誤差遷移問題. 多組實驗結(jié)果表明，本文提出的SCNSHM方法具備最高的F1值，且模型結(jié)構(gòu)更為精簡，泛化能力強.

1 算法原理

SCNSHM包括軟聚類節(jié)點分裂、決策模型構(gòu)建和層次結(jié)構(gòu)判別3個部分. 其中軟聚類節(jié)點分裂和決策模型構(gòu)建用于訓(xùn)練層次結(jié)構(gòu)模型，層次結(jié)構(gòu)判別用于計算樣本類別概率，原理如圖1所示. 首先采用軟聚類節(jié)點分裂算法替代傳統(tǒng)決策樹的節(jié)點分裂算法構(gòu)建樹形結(jié)構(gòu)，然后在樹形結(jié)構(gòu)的各個葉子節(jié)點處分別訓(xùn)練決策模型完成層次結(jié)構(gòu)模型構(gòu)建，最后根據(jù)生成的層次結(jié)構(gòu)模型，采用層次結(jié)構(gòu)判別方法完成對新樣本類別概率預(yù)測.

1.1 軟聚類節(jié)點分裂

傳統(tǒng)決策樹在處理復(fù)雜非線性分類問題時，樹形結(jié)構(gòu)生成效率低下，存在結(jié)構(gòu)冗余，容易造成模型過擬合. 使用聚類分析和支持向量機相結(jié)合的方法可有效提高分類準(zhǔn)確性，降低訓(xùn)練復(fù)雜度[13]. 軟聚類節(jié)點分裂方法結(jié)合了k-means和支持向量機(support vector machine，SVM)算法，學(xué)習(xí)過程中可以實現(xiàn)高效的非線性節(jié)點分裂，k-means聚類結(jié)果為SVM提供偽標(biāo)簽，對原數(shù)據(jù)中的標(biāo)簽噪聲及錯分樣本進行修正.

軟聚類節(jié)點分裂方法首先依據(jù)數(shù)據(jù)本身固有特點，利用k-means方法將數(shù)據(jù)聚攏成不同特點的聚類簇.k-means對數(shù)據(jù)的相似性大小度量計算公式如下：

(1)

式中:qik為第i個樣本的第k維屬性；qjk為數(shù)據(jù)集中第j個樣本的第k維屬性；dij為兩樣本間的歐式距離.

k-means只能將單個樣本隸屬于某個聚類簇，交界附近的樣本容易被強行劃分為某一聚類簇，這個問題通過計算樣本屬于不同聚類簇的概率來解決.

樣本屬于不同聚類簇的概率通過SVM方法計算. 假定訓(xùn)練集為

{(X1,y1),(X2,y2),…,(XN,yN)}.

然后采用SVM計算樣本屬于不同聚類類別概率.

SVM是一種最大化間隔分類器，目標(biāo)是尋找可以分隔不同類別樣本的分類超平面，同時該超平面滿足最大化樣本和超平面間隔的限制條件. 對于任意兩個聚類類別構(gòu)建SVM判定模型：

(2)

(3)

式中‖X-X′‖2表示兩個向量之間的歐式距離，σ可以表示為

(4)

(5)

1.2 決策模型構(gòu)建

根據(jù)生成的樹形結(jié)構(gòu)，在各個葉子節(jié)點處分別構(gòu)建決策模型，可以在保證判別效果的同時，生成精簡的層次結(jié)構(gòu)模型，如圖2所示.

葉子節(jié)點處決策模型均采用全訓(xùn)練集通過邏輯回歸算法訓(xùn)練獲得，訓(xùn)練過程中注意每個訓(xùn)練樣本權(quán)重不同，結(jié)果表示當(dāng)前節(jié)點下訓(xùn)練樣本屬于不同樣本子空間的概率，如圖2中樣本Xi，在頂層根節(jié)點處軟聚類節(jié)點分裂算法輸出結(jié)果為g1(Xi,W)、g2(Xi,W)、g3(Xi,W)，分別表示樣本Xi屬于3個不同葉子節(jié)點的概率. 樣本添加權(quán)重后的邏輯回歸損失函數(shù)可以表示為

(1-yi)lg(1-hθ(Xi))].

(6)

其中β(Xi)表示樣本權(quán)重大小，如圖2中左側(cè)葉子節(jié)點處樣本Xi權(quán)重為

β(Xi)=g1(Xi,W).

(7)

hθ(Xi)為需要構(gòu)建的決策模型即

hθ(Xi)=1/[1+exp(-θTXi)].

(8)

式中θ即為所求的邏輯回歸決策模型中的權(quán)重系數(shù).

最后依次對各個葉子節(jié)點構(gòu)建決策模型的損失函數(shù)進行優(yōu)化，完成層次結(jié)構(gòu)模型的構(gòu)建.

1.3 層次結(jié)構(gòu)判別

層次結(jié)構(gòu)判別從葉子節(jié)點出發(fā)，采用沿著層次結(jié)構(gòu)模型向上計算的方式實現(xiàn)對新樣本的預(yù)測. 如圖3所示，在給定新樣本Xj時，決策模型中輸出其在不同葉子節(jié)點樣本子空間下的為正樣本的概率Pi(Xj,θi),i=1,2,3，非葉子節(jié)點輸出結(jié)果衡量相應(yīng)決策模型預(yù)測概率在最終預(yù)測結(jié)果中所占比重大?。篻i(Xj,W),i=1,2,3. 決策模型輸出預(yù)測概率與根節(jié)點軟聚類分裂方法輸出結(jié)果相乘求和,

2 實驗及分析

2.1 實驗?zāi)康?/h3>

近年來機器學(xué)習(xí)方法被廣泛應(yīng)用到Ⅱ型糖尿病患病診斷中，Ⅱ型糖尿病患病與個體身體指標(biāo)密切相關(guān)，其患病診斷是一個典型的復(fù)雜非線性分類問題，因此為了驗證本文提出算法SCNSHM的判定效果，所有對比實驗均在 Ⅱ 型糖尿病診斷應(yīng)用上進行.

對比實驗在兩個數(shù)據(jù)集上實現(xiàn)，分別將SCNSHM與CART、C4.5和ID3決策樹算法判定效果進行對比分析，說明SCNSHM在保證模型分類效果基礎(chǔ)上可以有效精簡模型結(jié)構(gòu).

2.2 評價指標(biāo)

通過對比SCNSHM方法與其他決策樹算法在糖尿病數(shù)據(jù)上的分類效果，驗證方法的有效性. 其中分類效果采用F1-measure值作為評價指標(biāo)為

(10)

式中:R為正樣本召回率;P為正樣本的準(zhǔn)確率，其計算公式分別如下:

R=tp/N+,

(11)

(12)

式中：tp為預(yù)測正確的正樣本個數(shù)；fp為預(yù)測錯誤的負(fù)樣本個數(shù)；N+為真實正樣本個數(shù).

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

實驗數(shù)據(jù)為兩組糖尿病數(shù)據(jù)，兩組實驗數(shù)據(jù)均包括性別(SEX)、年齡(AGE)、身高(HEIGHT)、體重(WEIGHT)、腰圍(WAIST)、總膽固醇(CHOL)、甘油三脂(TG)、收縮壓(SBP)、舒張壓(DBP)、高密度脂蛋白(HDL)、空腹血糖(GLU)和負(fù)荷后血糖(OGTT)共12維屬性，其中負(fù)荷后血糖屬性為標(biāo)簽，負(fù)荷后血糖異常為正樣本，負(fù)荷后血糖正常為負(fù)樣本. 實驗數(shù)據(jù)數(shù)據(jù)集1來源于美國國家健康與營養(yǎng)體檢調(diào)查(national health and nutrition examination survey,NHANES)公開數(shù)據(jù)庫，共6 497例樣本，其中正樣本1 186例，負(fù)樣本5 311例；數(shù)據(jù)集2來源于北京醫(yī)院老年研究所健康體檢數(shù)據(jù)，共7 917例樣本，其中正樣本1 943例，負(fù)樣本5 974例.

2.4 實驗過程

實驗將數(shù)據(jù)集隨機均分為5份，選取其中4份作為訓(xùn)練集，采用5折交叉驗證方法進行參數(shù)選擇. 同時為了避免隨機選擇訓(xùn)練集對實驗結(jié)果的影響，依次將5份數(shù)據(jù)分別作為測試集，其余數(shù)據(jù)作為訓(xùn)練集，利用參數(shù)選擇獲得的最優(yōu)參數(shù)構(gòu)建判定模型，并在測試集上測試模型判定效果.

模型超參數(shù)均采用網(wǎng)格搜索法系統(tǒng)地遍歷多種參數(shù)組合，通過5折交叉驗證獲得最佳效果. 其中數(shù)據(jù)集1上SCNSHM方法參數(shù)為k-means聚類個數(shù)4，SVM判別模型參數(shù)C=0.1、γ=10；數(shù)據(jù)集2上k-means聚類個數(shù)5，SVM判別模型參數(shù)C=100、γ=100.

2.5 實驗結(jié)果及分析

表1展示了兩個數(shù)據(jù)集上對比實驗結(jié)果，表2展示了在數(shù)據(jù)集1上，SCNSHM方法和CART方法所構(gòu)建模型的最終判別規(guī)則. 實驗結(jié)果顯示，SCNSHM方法的判別效果在兩個數(shù)據(jù)集的測試集上均為最佳，數(shù)據(jù)集1測試集上SCNSHM方法的F1值為0.53，比CART、ID3和C4.5的分別大15%、15%、6%；數(shù)據(jù)集2測試集上SCNSHM方法的F1值為0.38，比CART、ID3和C4.5的分別大27%、12%、8%. 在保證準(zhǔn)確率的同時，SCNSHM方法顯著提高了召回率，可以篩查出更多的糖尿病患病人群. 在模型結(jié)構(gòu)方面，SCNSHM方法構(gòu)建的模型均具有最精簡的結(jié)構(gòu)(其中數(shù)據(jù)集1上SCNSHM方法構(gòu)建模型深度為2，葉子結(jié)點有4個；數(shù)據(jù)集2上SCNSHM方法構(gòu)建模型深度為2，葉子結(jié)點有5個，與3個對比算法相比，明顯精簡了模型結(jié)構(gòu)). 觀察表2所展示的判別規(guī)則也可發(fā)現(xiàn)，SCNSHM方法構(gòu)建的判別規(guī)則獨立性更高，分裂間隔更大且更精簡. 在相同算力情況下，訓(xùn)練過程的耗時增加主要由SVM的二次時間復(fù)雜度造成，但在模型的測試過程，其計算時間將僅由規(guī)則集的復(fù)雜度決定. 由此可知，SCNSHM方法在訓(xùn)練過程中，軟聚類節(jié)點分裂將一定程度上提高模型訓(xùn)練的時間成本，但在測試及應(yīng)用過程中，模型相較對比算法具有更快的判別速度.

表1 對比實驗結(jié)果Tab.1 Results of contrast experiment

注：F1為F1-measure值；L為模型結(jié)構(gòu)深度；n為模型葉子結(jié)點個數(shù)

表2 NHANES數(shù)據(jù)集模型復(fù)雜度對比Tab.2 Comparisons of model complexity on NHANES dataset

注：規(guī)則按照符合該條規(guī)則的樣本數(shù)量排序

SCNSHM方法具有最高的F1值且模型結(jié)構(gòu)最精簡，在各個葉子節(jié)點處構(gòu)建決策模型，采用層次結(jié)構(gòu)判別方法，將不同葉子節(jié)點輸出判別概率加權(quán)求和，即使上層節(jié)點出現(xiàn)判別錯誤時，仍然可以通過其他葉子節(jié)點的輸出結(jié)果進行補償，因此可以有效避免出現(xiàn)誤差遷移問題，有效提高模型判別效果.

3 結(jié) 論

本文提出的SCNSHM方法通過軟聚類方法進行節(jié)點分裂，在葉子節(jié)點構(gòu)建決策模型，并利用層次結(jié)構(gòu)判別方法對樣本進行加權(quán)預(yù)測，克服了決策樹算法結(jié)構(gòu)冗余、誤差遷移的問題. 具體來說，首先利用k-means對樣本進行聚類，以聚類類別為偽標(biāo)簽構(gòu)建SVM模型進行分類，構(gòu)建層次結(jié)構(gòu)模型，然后依據(jù)所得層次結(jié)構(gòu)模型，計算樣本權(quán)值，在葉子節(jié)點處訓(xùn)練邏輯回歸模型，完成判定模型的構(gòu)建，最后利用層次結(jié)構(gòu)判別方法實現(xiàn)對新樣本的預(yù)測. 經(jīng)過實驗表明，SCNSHM相比于CART、ID3和C4.5算法，在更精簡的結(jié)構(gòu)上實現(xiàn)了更好的分類效果.