基于隨機(jī)化屬性選擇和決策樹的組合分類器

馬　源

(福州大學(xué) 物理與信息工程學(xué)院，福州　350108)

?

基于隨機(jī)化屬性選擇和決策樹的組合分類器

馬源

(福州大學(xué) 物理與信息工程學(xué)院，福州350108)

摘要：針對決策樹泛化能力差，容易產(chǎn)生過擬合問題，提出基于隨機(jī)化屬性選擇和決策樹組合分類器。首先運(yùn)用隨機(jī)化鄰域?qū)傩约s減產(chǎn)生多個(gè)分類較高的屬性子集；其次每個(gè)屬性子集作為分類回歸樹(CART)的輸入，訓(xùn)練多個(gè)基分類器；最后對得到的多個(gè)分類精度結(jié)果進(jìn)行投票融合的方式獲得最后的分類結(jié)果。實(shí)驗(yàn)表明，提出的隨機(jī)屬性選擇和決策樹集成算法有效性。

關(guān)鍵詞：過擬合；隨機(jī)化；決策樹；分類器；融合

0引言

經(jīng)典粗糙集理論[1]是波蘭華沙理工大學(xué)教授Pawlak1982年，在研究不完整和不精確知識(shí)的表達(dá)時(shí)提出的。粗糙集有以下優(yōu)點(diǎn)：能夠客觀地挖掘出數(shù)據(jù)內(nèi)部的消息，也就是可以找到數(shù)據(jù)的本質(zhì)信息；可以將數(shù)據(jù)通過一定的原則進(jìn)行提煉，得到數(shù)據(jù)的內(nèi)涵信息。由于上述作用，粗糙集理論在數(shù)據(jù)挖掘中得到廣泛應(yīng)用，鄰域粗糙集[2]是為了解決經(jīng)典粗糙集便于處理數(shù)值型屬性的數(shù)據(jù)集合而提出的。鄰域粗糙集約減可以對樣本數(shù)據(jù)集進(jìn)行屬性選擇，選擇出分類能力強(qiáng)的屬性，達(dá)到去噪和降維的功能，從而減少分類計(jì)算復(fù)雜度，提高分類效果。

決策樹[3]是一種非常適合數(shù)據(jù)挖掘的算法。相比較神經(jīng)網(wǎng)絡(luò)、貝葉斯、支持向量機(jī)等分類器，其主要優(yōu)點(diǎn)是模型具有可解釋性，容易被人們所理解，且構(gòu)建速度快。同時(shí)決策樹生成算法不需要附加信息，例如數(shù)據(jù)和類別分布的先驗(yàn)知識(shí)。然而其主要缺點(diǎn)是分類結(jié)果準(zhǔn)確率不高，容易產(chǎn)生過擬合問題，當(dāng)數(shù)據(jù)集中的屬性過多，用決策樹分類容易出現(xiàn)結(jié)構(gòu)性差等問題。

目前，數(shù)據(jù)挖掘主要的研究方向由單一的方法逐漸發(fā)展成為多種方法結(jié)合。粗糙集在化簡訓(xùn)練樣本，消除冗余信息，處理大數(shù)據(jù)量的時(shí)候具有一定優(yōu)勢。但粗糙集分類精度不高，往往結(jié)果不太穩(wěn)定。研究表明[4]粗糙集和決策樹具有很高的優(yōu)勢互補(bǔ)性，因此可以將兩者結(jié)合。在實(shí)際應(yīng)用中，粗糙集理論結(jié)合決策樹分類器發(fā)揮兩者的優(yōu)越性，取得了較好的效果。

針對決策樹構(gòu)造中存在抗噪聲能力差、選擇最優(yōu)屬性困難的問題，文獻(xiàn)[5]提出一種基于變精度粗糙集模型的決策樹構(gòu)建。文獻(xiàn)[6]提出一種鄰域粗糙集快速約減算法，從中選擇最大屬性重要度的屬性加入約減集合中，直到所有剩余屬性重要度為0，并將此應(yīng)用在CART分類器上驗(yàn)證了該約減算法的可以提高分類效果。然而實(shí)際數(shù)據(jù)中約減是種NP問題，存在多個(gè)保持原始樣本數(shù)據(jù)具有區(qū)分能力的屬性子集，因此為了盡可能利用不同子空間的分類能力，文獻(xiàn)[7]提出WADF方法和文獻(xiàn)[8]提出一種隨機(jī)屬性約減算法尋求多個(gè)約減。本文將鄰域粗糙集隨機(jī)屬性選擇與CART決策樹相結(jié)合，設(shè)計(jì)出一種集成學(xué)習(xí)分類器。通過隨機(jī)化鄰域約減產(chǎn)生的多個(gè)約減，作為CART的輸入，最后對分類結(jié)果進(jìn)行加權(quán)投票的方式融合不同的結(jié)果做出決策，提高泛化能力和減少過擬合問題。從實(shí)驗(yàn)數(shù)據(jù)測試結(jié)果可以看出，本文提出方法的有效性。

1鄰域粗糙集模型基本概念

鄰域粗糙集模型不需要像經(jīng)典粗糙集事先要屬性離散化，它可以對數(shù)值形屬性直接處理，直接用于知識(shí)約減。下面介紹鄰域粗糙集模型相關(guān)概念[1]。

定理1給定實(shí)數(shù)空間Ω上的非空有限集合U={x1,x2,…xn}，對于?xi的鄰域δ定義為：δ(xi)={x|x∈U,Δ(x,xi)≤δ}，其中δ≥0，Δ(x,xi)為距離函數(shù)，表示x與xi之間的距離。常見的距離計(jì)算函數(shù)例如：曼哈頓距離函數(shù)、歐式距離函數(shù)等。

定理2假設(shè)有一鄰域決策系統(tǒng)NDS=(U,A,D)，其中U為全部樣本構(gòu)成的集合，A為樣本的屬性子集，D為分類決策屬性。決策屬性D將U劃分為N個(gè)等價(jià)類(x1,x2,…xN)，?B∈A，D關(guān)于B的上下近似定義為：

定理3決策屬性D對于條件屬性B的依賴度定義為：

其中PosB(D)為決策鄰域決策系統(tǒng)的下近似。

定理4屬性重要度定義為：條件屬性對決策屬性的影響程度，若屬性a∈B，那么條件屬性a對于決策屬性D的重要度公式為：

Sig(a,B,D)=γB(D)-γB-{a}(D)

定理5對于決策系統(tǒng)NDS=(U,A,D)，B∈A，a∈B，如果滿足：

(1)γB(D)=γA(D)

(2)?a∈B:γB-{a}(D)<γB(D)

則稱B是一個(gè)屬性約減。

2CART分類算法

2.1CART分類算法簡介

CART是在給定輸入隨機(jī)變量X條件下輸出隨機(jī)變量Y的條件概率分布的方法，假設(shè)決策樹是二叉樹，內(nèi)部節(jié)點(diǎn)特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價(jià)于遞歸地二分每個(gè)特征，將輸入空間即特征空間劃分為有限個(gè)單元，并在這些單元上確定預(yù)測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。CART主要由決策樹生成和決策樹剪枝組成[9]。

2.2CART決策樹生成

CART決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。構(gòu)建回歸樹和分類樹采用不同的準(zhǔn)則，對回歸樹用平方誤差最小準(zhǔn)則，對分類樹用基尼系數(shù)最小化準(zhǔn)則，進(jìn)行特征選擇，生成二叉樹。由于篇幅有限，只介紹分類樹的生成。

分類樹用基尼指數(shù)選擇最優(yōu)特征，基尼系數(shù)計(jì)算公式為：

其中，K為樣本類的個(gè)數(shù)，pk為樣本點(diǎn)屬于第k類的概率。

假設(shè)訓(xùn)練數(shù)據(jù)集為D，根據(jù)訓(xùn)練數(shù)據(jù)集，從根節(jié)點(diǎn)開始，遞歸地對每個(gè)節(jié)點(diǎn)進(jìn)行以下操作，構(gòu)建二叉決策樹：

1)計(jì)算現(xiàn)有特征對該數(shù)據(jù)集的基尼系數(shù)，對于每個(gè)特征A，對其可能取的每個(gè)值a，根據(jù)樣本點(diǎn)對A=a的測試為“是”或“否”將D分割成D1和D2兩部分，計(jì)算A=a的基尼系數(shù)。

2)在所有可能的特征A以及它們所有可能的切分點(diǎn)a中，選擇基尼系數(shù)最小的特征極其對應(yīng)的切分點(diǎn)作為最有特征與最優(yōu)切分點(diǎn)。依最優(yōu)特征與最優(yōu)切分點(diǎn)，從現(xiàn)節(jié)點(diǎn)生成兩個(gè)子節(jié)點(diǎn)，將訓(xùn)練數(shù)據(jù)集依特征分配到兩個(gè)子節(jié)點(diǎn)中去。

3)對2個(gè)子節(jié)點(diǎn)遞歸地調(diào)用1)和2)，直至滿足停止條件。

4)生成CART決策樹。

算法停止計(jì)算的條件是節(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閥值，或樣本集的基尼系數(shù)小于預(yù)定閥值，或者沒有更多特征。

2.3CART決策樹剪枝

當(dāng)決策樹生成時(shí)，需要從完全生長的決策樹的底端剪去一些子樹，目的是為了使決策樹變小，模型變簡單，減少過擬合問題，從而能夠?qū)ξ粗獢?shù)據(jù)有更準(zhǔn)確的預(yù)測。CART剪枝算法首先從生成算法產(chǎn)生的決策樹T0底端開始不斷剪枝，知道T0的根節(jié)點(diǎn)，形成一個(gè)子樹序列{T0,T1,…,Tn}；然后通過交叉驗(yàn)證在獨(dú)立的驗(yàn)證數(shù)據(jù)集上對子樹序列進(jìn)行測試，從而選擇最優(yōu)子樹。CART剪枝算法如下：

1)設(shè)k=0，T=T0。

2)設(shè)a=+∞。

4)自上而下地訪問內(nèi)部節(jié)點(diǎn)t，如果有g(shù)(t)=a，進(jìn)行剪枝，并對葉節(jié)點(diǎn)t以多數(shù)表決法決定其類，得到樹T。

5)設(shè)k=k+1，ak=a，Tk=T。

6)如果T不是由根節(jié)點(diǎn)單獨(dú)構(gòu)成的樹，則回到步驟4)

7)采用交叉驗(yàn)證法在子樹序列T0,T1,…,Tn中選取最優(yōu)子樹Ta。

3基于隨機(jī)屬性選擇和決策樹的集成學(xué)習(xí)分類器

3.1基本思想

本文提出的集成學(xué)習(xí)分類器結(jié)構(gòu)圖如圖1所示。給定一個(gè)鄰域決策系統(tǒng)NDS=(U,A,D)，多次運(yùn)用鄰域隨機(jī)化屬性約減算法可以得到多個(gè)屬性約簡子集(a1,a2,…an)，每個(gè)約減子集作為CART分類器的輸入，采用十字交叉驗(yàn)證得到一組決策，最后對每組決策通過加權(quán)投票的方式最終可以得到每個(gè)樣本的類標(biāo)號。

圖1　結(jié)構(gòu)圖Fig.1　Structure chart

3.2算法描述

本文提出的一種隨機(jī)屬性選擇和CART的集成學(xué)習(xí)分類器，利用鄰域隨機(jī)化屬性產(chǎn)生多個(gè)約減的屬性子集，從而產(chǎn)生對樣本數(shù)據(jù)進(jìn)行特征選擇的多個(gè)子集，具體過程如算法1所示，然后利用CART進(jìn)行分類學(xué)習(xí)。本文采用了10折交叉驗(yàn)證方法，在對每一個(gè)子集進(jìn)行分類學(xué)習(xí)時(shí)，將該子集劃分為10等份，利用其中的9份作為訓(xùn)練集用于構(gòu)建一個(gè)CART分類器，剩余的1份作為測試集進(jìn)行測試。在10折交叉驗(yàn)證之后，該子集將會(huì)產(chǎn)生一個(gè)決策輸出，同理對于剩下的子集采用同種方法，每個(gè)子集產(chǎn)生的決策輸出最后通過投票融合的方法最終決策輸出。具體算法如算法2。

算法1(基于鄰域粗糙集隨機(jī)化屬性約減)：

輸入：NDS=(U,A,D)，參數(shù)δ和隨機(jī)數(shù)N

輸出：約減reduce={a1,a2,…an}

1)屬性約減初始化reduce為空集

2)對任意的ai∈A-reduce計(jì)算屬性ai的重要度SIG(ai,reduce,D)

3)選擇ak，ak為屬性集{A-reduce}中重要度SIG(ai,reduce,D)前F個(gè)最大中的一個(gè)

4)如果SIG(ai,reduce,D)>0，則reduce∪ak→reduce

5)回到第二步

6)否則返回約減reduce，約減完成。

算法2(基于鄰域粗糙集隨機(jī)化屬性約減和決策樹的集成學(xué)習(xí))：

輸入：原始數(shù)據(jù)集通過約減的屬性集{a1,a2,…an}

輸出：驗(yàn)證集上的分類正確率

步驟：

1)初始化

①讀入原始數(shù)據(jù)集{a1,a2,…an}

2)For(iin 1∶10)

①將原始數(shù)據(jù)集{a1,a2,…an}中的每個(gè)子集劃分成10等份

②在訓(xùn)練集上運(yùn)行CART創(chuàng)建分類器

③在測試集上執(zhí)行分類預(yù)測

3)對于每個(gè)子集的預(yù)測采用投票，輸出分類正確率

3.3時(shí)間復(fù)雜度分析

鄰域隨機(jī)屬性約減在選定隨機(jī)數(shù)F后，每次運(yùn)行即可以得到1個(gè)隨機(jī)化約減。這個(gè)算法的時(shí)間復(fù)雜度為(2n-k)(k+1)×(k+1)×mlogm/2，其中n和m分別為樣本和特征的數(shù)據(jù)，k為約減中屬性的個(gè)數(shù)。約減后的各個(gè)屬性子集作為CART分類器的輸入，設(shè)約減后的數(shù)據(jù)集維數(shù)為m*，訓(xùn)練樣本個(gè)數(shù)為n*。在構(gòu)建CART樹的過程中，訓(xùn)練1個(gè)不進(jìn)行剪枝的樹，訓(xùn)練每一個(gè)基分類器的計(jì)算時(shí)間小于O(m*n*(logn*)2)，對于k個(gè)基分類器的時(shí)間復(fù)雜度近似為O(km*n*(logn*)2)，本實(shí)驗(yàn)采用10折交叉驗(yàn)證，需運(yùn)行CART算法10次，最終k個(gè)基分類器的時(shí)間復(fù)雜度約為10×O(km*n*(logn*)2)。

在進(jìn)行實(shí)驗(yàn)時(shí)，我們設(shè)置運(yùn)行隨機(jī)屬性約減算法10次，這樣將會(huì)產(chǎn)生10個(gè)約減結(jié)果，然后利用CART分類器學(xué)習(xí)。實(shí)驗(yàn)表明，提出的集成學(xué)習(xí)運(yùn)行時(shí)間上是可以接受的，算法具有較好的擴(kuò)展性。

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

4.1實(shí)驗(yàn)數(shù)據(jù)與方法

從UCI數(shù)據(jù)庫中下載4個(gè)數(shù)據(jù)集，分別是zoo、heart 、wdbc、soy、wine、wpbc數(shù)據(jù)集描述如表1所示。算法采用matlab2014a實(shí)現(xiàn)

表1　數(shù)據(jù)描述

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

在分類學(xué)習(xí)之前對數(shù)據(jù)進(jìn)行了預(yù)處理，首先剔除缺省值和無關(guān)屬性，然后歸一化處理，使得每個(gè)屬性的取值在[0,1]之間。本文提出的設(shè)計(jì)方法分類精度如表2所示。

表2　提出方法的分類精度

為了進(jìn)一步說明本設(shè)計(jì)的優(yōu)越性，比較本文提出的設(shè)計(jì)方法和基于快速約減的貪心算法的CART、使用原始特征的CART的分類精度，比較結(jié)果如圖2所示。3種分類方法在6個(gè)不同數(shù)據(jù)集分類準(zhǔn)確度的平均值柱狀圖如圖3所示。

圖2　3種分類方法比較Fig.2　Comparison of classification among three methods

圖3　3種分類方法平均值比較Fig.3　Comparison of average classification among three methods

從實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)提出基于隨機(jī)屬性選擇和決策樹的組合分類器可以較大的提高CART分類器的準(zhǔn)確度，準(zhǔn)確度優(yōu)于基于快速約減的貪心算法的CART分類器。從繪出的分類曲線可以看出，快速貪心約減算法并不完全可以使CART分類效果提高，在有些數(shù)據(jù)集上分類效果差于直接使用原始數(shù)據(jù)集的CART。從平均值柱狀圖可以看出，提出的方法在6個(gè)數(shù)據(jù)集的平均準(zhǔn)確度相比較直接使用原始數(shù)據(jù)集的CART提高了4.93%，比基于快速約減算法的CART提高了4.95%。

5結(jié)語

目前CART決策樹分類穩(wěn)定性差，易產(chǎn)生過擬合，分類精度有待提高。本文提出的基于隨機(jī)屬性選擇和決策樹的組合分類器，首先利用鄰域粗糙集的隨機(jī)屬性選擇方法，得到多個(gè)保持原始樣本數(shù)據(jù)具有區(qū)分能力的屬性子集，在不同屬性集上分別構(gòu)建CART決策樹，最后通過加權(quán)融合的方法得到判決。通過實(shí)驗(yàn)結(jié)果表明可以較大改善CART分類器準(zhǔn)確度不高和過擬合問題，以后將使用此方法應(yīng)用到實(shí)際數(shù)據(jù)中。

參考文獻(xiàn)：

[1] 楊啟賢.粗糙集及其應(yīng)用簡介[J].貴州師范大學(xué)學(xué)報(bào)(自然科學(xué)版),1988,6(2):4-9.

[2] HU Q,YU D,XIE Z.Neighborhood classifiers[J]. Expert Systems with Applications,2008,34(2):866-876.

[3] PONKIYA P.A Review on Tree Based Incremental Classification[J].International Journal of Computer Science and Information Technologies,2014,5(1):306-309.

[4] PAL P,MOTWANI D.The Based on Rough Set Theory Development of Decision Tree after Redundant Dimensional Reduction[C]// Advanced Computing & Communication Technologies (ACCT), 2015 Fifth International Conference on IEEE, 2015:278-282.

[5] WANG F.Improved Algorithm of Decision Trees Construction Based on Variable Precision Rough Set[J].Computer & Digital Engineering, 2013，41(3):337-339.

[6] 胡清華,于達(dá)仁,謝宗霞.基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡[J].軟件學(xué)報(bào),2008,19(3):640-64.

[7] WU Q X,BELL D,MCGINNITY M.Multiknowledge for decision making[J].Knowledge & Information Systems, 2005,7(2):246-266.

[8] 朱鵬飛,胡清華,于達(dá)仁.基于隨機(jī)化屬性選擇和鄰域覆蓋約簡的集成學(xué)習(xí)[J].電子學(xué)報(bào),2012,40(2):273-279.

[9] 李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京:清華大學(xué)出版社,2012:67-73.

文章編號：1004—5570(2016)01-0098-05

收稿日期：2015-08-12

作者簡介：馬源(1991-)，男，碩士研究生，研究方向：數(shù)據(jù)挖掘，圖像處理與通信，E-mail：251394667@qq.com.

中圖分類號：TP391.4

文獻(xiàn)標(biāo)識(shí)碼：A

Ensemble classifier based on randomized attribute selection and decision tree

MA Yuan

(Institute of Physics and Information Engineering,Fuzhou University,Fuzhou,Fujian 350108,China)

Abstract:Aiming at the problems of poor generalization ability and easy to overfitting in decision tree.We introduce an ensemble classifier based on randomized attribute selection and combination of decision tree.Firstly,multiple subsets with higher accuracy are produced by use of randomization adjacent attribute reduction;Secondly each attribute subset as classification and regression tree’s input;Finally the final classification result is obtained by multiple classification results fusion.The experiment result shows that the proposed random attribute selection and decision tree integration algorithm is effective.

Key words:overfitting；randomization;decision tree;classifier; fusion