基于代表性數據的決策樹集成

（太原理工大學 計算機與軟件學院， 太原 030024）

摘 要：

為了獲得更好的決策樹集成效果，在理論分析的基礎上從數據的角度提出了一種基于代表性數據的決策樹集成方法。該方法使用圍繞中心點的劃分(PAM)算法從原始訓練集中提取出代表性訓練集，由該代表性訓練集來訓練出多個決策樹分類器，并由此建立決策樹集成模型。該方法能選取盡可能少的代表性數據來訓練出盡可能好的決策樹集成模型。實驗結果表明，該方法使用更少的代表性數據能獲得比Bagging和Boosting還要高的決策樹集成精度。

關鍵詞：代表性數據； 決策樹； 聚類； 圍繞中心點的劃分； 集成學習； Bagging； Boosting

中圖分類號：TP301.6文獻標志碼：A

文章編號：10013695(2009)04124103

Ensemble of decision trees based on representative data

LI Haifang， DING Zhoufang， WANG Liqun

（College of Computer Software， Taiyuan University of Technology， Taiyuan 030024， China）

Abstract:

To generate better ensemble output of decision trees， based on the theoretic analysis， this paper put forward a method used for ensemble of decision trees with representative data from the data point of view .This method extracted representative data via partition around medoids (PAM) algorithm from the original training set at first， then it trained a number of decision trees with the help of the representative data and built a ensemble model with the trained decision trees. This method could select the less representative data and trained the better ensemble model of decision trees. The experiment results show that this method can obtain higher ensemble precision of decision trees than Bagging or Boosting furthermore it uses less representative training set.

Key words：representative data; decision tree; cluster; PAM; ensemble learning; Bagging; Boosting

在原始數據集中的數據通常有以下特點：不完整性，缺少屬性值或僅包含聚集數據；不一致性，原始數據的來源不同，數據定義缺乏統一的標準而導致系統間數據內涵不一致；有噪聲，數據中存在異常、錯誤值或孤立點；冗余性，通常是由數據集成所造成的數據記錄或屬性的重復。由于這些特點，許多原始數據在學習算法的訓練階段并不都是有用的。近年來一些研究人員認為， 在產生決策樹前盡量減少訓練數據量比在決策樹產生后再簡化決策樹更能夠提高決策樹的性能[1~6]。

聚類是指按照事物的某些屬性，將物理或抽象對象的集合分組成為由類似的對象組成的若干個類，使得在同一個聚類（簇）中的對象盡可能地彼此相似，不同聚類（簇）中的對象盡可能地彼此相異。

基于原始數據存在的缺陷及聚類的性質和作用，本文提出了基于代表性數據的決策樹集成方法。該方法利用聚類算法從原始樣本數據中提取一些代表性樣本，刪除冗余數據、相似數據和噪聲數據，從而減少訓練數據并提高訓練數據的質量，進而改進單個決策樹的性能[1~3]。集成多個改善性能后的決策樹應能夠得到比集成直接用原始數據所訓練出的多個決策樹要更好的集成效果。

1 決策樹的性能與訓練數據間的關系

Oates等人[4]研究了訓練集的大小與決策樹復雜性之間的關系。其研究表明訓練數據的增加經常會造成決策樹大小的線性增加， 但這種增加并沒有都帶來決策樹分類準確性的提高。Sebban等人[5]研究了訓練集的質量和大小與決策樹的性能，包括訓練出的決策樹模型的復雜性與泛化精度之間的關系，并從理論上論證了可以在不影響分類精度的前提下通過減少訓練數據來減小決策樹。

文獻[5]從理論上分析了決策樹的大小及泛化能力與訓練數據間的關系。為了簡單起見，Sebban等人僅考慮C4.5算法在二分類上的情形，對于多分類問題也可以此原理進行同樣的分析。為了估算當訓練數據增加時某個分裂后子樹的修剪概率，將決策樹的一個節點0分裂成兩個節點1和2。為了保證每個可能的樣本集都以相同的概率產生，這里假定訓練集是從相關的總數據集 Ω中通過簡單隨機取樣生成的。

令 πij為節點j中類別i的數據個數占 Ω中總個數的相對比例。令 θ0=min(π1#8226;；π2#8226;)/π#8226;#8226;為節點0上的分類錯誤率， θ1=min(π11;π21)/π#8226;1和 θ2=min(π12;π22)/π#8226;2分別為節點1和2上的分類錯誤率。不失一般性，這里假設 π1#8226;＞π2#8226;，即類別1在節點0中占絕大多數。因此，θ0=π2#8226;/π#8226;#8226;，于是分裂后子節點的平均錯誤率為

θ=θ1×π#8226;1/π#8226;#8226;+θ2×π#8226;2/π#8226;#8226;=[min(π11;π21)+min(π12;π22)]/π#8226;#8226;(1)

從式（1）可知θ的取值與π11和π21的大小及π12和π22的大小有關，所以θ的取值有且僅有以下四種可能：

a）當min(π11;π21)=π11，min(π12;π22)=π12時，π11+π12＜π21+π22，即 π1#8226;＜π2#8226;，與假設π1#8226;＞π2#8226;相矛盾，故該情形在假設前提下不存在。

b)當min(π11;π21)=π21，min(π12;π22)=π12時，θ=(π21+π12)/π#8226;#8226;，而θ0=π2#8226;/π#8226;#8226;=(π21+π22)/π#8226;#8226;＞(π21+π12)/π#8226;#8226;=θ。

c)當 min(π11;π21)=π11，min(π12;π22)=π22時，θ=(π11+π22)/π#8226;#8226;，而θ0=π2#8226;/π#8226;#8226;=(π21+π22)/π#8226;#8226;＞(π11+π22)/π#8226;#8226;=θ。

d)當 min(π11;π21)=π21，min(π12;π22)=π22時，θ=(π21+π22)/π#8226;#8226;，而θ0=π2#8226;/π#8226;#8226;=(π21+π22)/π#8226;#8226;=θ。

從以上分析可以看出，分裂后的平均錯誤率小于或等于未分裂時節點0上的錯誤率，即θ≤θ0。這說明如果在分裂后的節點1中擁有的數據個數最多的類別與節點2中擁有數據個數最多的類別不相同，則使得分裂后的平均錯誤率要低于分裂前的錯誤率；反之，如果在分裂后的節點1中擁有的數據個數最多的類別與節點2中擁有數據個數最多的類別相同，則分裂后的平均錯誤率與分裂前的錯誤率相等。

設N為訓練樣本中所含數據的總個數，Nij為節點j上類別i所含樣本數據的個數，pj為節點j上的經驗風險。在C4.5算法中一個子樹被修剪當且僅當

[N#8226;1/N(p1+1.96p1×(1-p1)/N#8226;1)+N#8226;2/N(p2+1.96p2×(1-p2)/N#8226;2)]＞(p0+1.96p0×(1-p0)/N)(N#8226;1/N×p1+N#8226;2/N×p2-p0)+1.96(N#8226;1/Np1×(1-p1)/N#8226;1+N#8226;2/Np2×(1-p2)/N#8226;2-p0×(1-p0)/N)＞0PN1+1.96×PN2＞0(2)

而在式(2)中左邊的第二項

PN2=N#8226;1/Np1×(1-p1)/N#8226;1+N#8226;2/Np2×(1-p2)/N#8226;2-p0×(1-p0)/N=1/N[N#8226;1/Np1×(1-p1)+N#8226;2/Np2×(1-p2)-p0×(1-p0)](3)

從式(3)可以看出，當N→∞時，PN2→0。式(2)中PN1+1.96×PN2的符號取決于PN1=N#8226;1/N×p1+N#8226;2/N×p2-p0，于是有以下兩種情況：

a)Ω中，當在節點1和2上含有樣本多的類別不相同時，分裂后的平均錯誤率小于分裂前節點0的錯誤率，即θ＜θ0并且PN1=N#8226;1/N×p1+N#8226;2/N×p2-p0→π#8226;1×π21+π#8226;2×π12-π2#8226;或PN1=N#8226;1/N×p1+N#8226;2/N×p2-p0→π#8226;1×π11+π#8226;2×π22-π2#8226;，而π#8226;1×π21+π#8226;2×π12-π2#8226;＜0且π#8226;1×π11+π#8226;2×π22-π2#8226;＜0。由式(2)和(3)可知PN1＞0，所以在這種情形下，修剪概率趨于0，即不修剪由訓練數據訓練出的決策樹。在這種情形下隨著訓練集大小N的增加由C4.5生成的決策樹的大小隨之增加。

b）Ω中，當在節點0、1和2上含有樣本數據多的類別相同時，分裂后的平均錯誤率等于分裂前節點0的錯誤率，即θ=θ0，并且PN1=N#8226;1/N×p1+N#8226;2/N×p2-p0的值也在0附近波動。因此在這種情形下，隨著訓練集大小N的增加由C4.5生成的決策樹的大小也隨之增加，并且分類錯誤率保持不變。

綜上所述，當訓練集的大小隨機減小時，決策樹的大小也隨之減小，并且還可以保持分類精度不變。這樣就可以通過減少訓練數據來改善決策樹的性能。

2 基于代表性數據的決策樹集成

既然當訓練集的大小適當地減少時，可以提高單個決策樹的性能，那么可以提出如下設想：當訓練集的大小按某種策略減少時，可以提高多個決策樹集成的性能。

2.1 代表性數據的選取

John提出了RobustC4.5算法，該算法通過反復地訓練決策樹分類器和刪除被當前決策樹誤分類的實例來減少訓練數據，并提高決策樹C4.5的性能[5]。Brodley等人提出了CF算法，該算法通過一致過濾器來識別并刪除誤分類的訓練數據，即先構建多個分類器，并使用它們來識別誤分類的訓練數據，當且僅當所有的分類器都誤分類了某個訓練數據時，該訓練數據才被從訓練集中刪除[5]。Sebban 等人[5]提出了使用原型選擇算法來減少原始數據而提高后剪枝決策樹的性能。

為了通過盡可能少的訓練集來構建性能盡可能好的決策樹分類模型，本文在選擇合適的訓練集時使用聚類的方法來對原始訓練集進行聚類，然后將聚類后的各個簇的中心點作為新的訓練集。

假設原始訓練集為S，S中含有N個數據，即S={S1，S2，S3，…，SN}，從S中選取K(0

輸入 代表性數據的個數K和原始數據集S。

輸出 代表性數據集Sr。

從S中任意選擇K個數據對象作為初始的簇中心點來構成初始的Sr；

repeat

指派每個剩余的數據對象給離它最近的中心點所代表的簇；

repeat

選擇一個未被選擇的中心點Oi；

repeat

選擇一個未被選擇過的非中心點對象Oh；

計算用Oh代替Oi的總代價并記錄在R中；

until所有的非中心點都被選擇過；

until 所有的中心點都被選擇過；

if在Ｒ中的所有非中心點代替所有中心點后計算出的總代價有小于0存在;

then找出Ｒ中的用非中心點替代中心點后代價最小的一個，并用該非中心點替代對應的中心點，形成一個新的Ｋ個中心點的集合Sr；

until沒有再發生簇的重新分配，即Ｒ中所記錄的所有數均大于0。

每當重新分配聚類中心點即用非中心點數據來代替中心點數據時，替換的總代價即所有非中心點對象由于用非中心點數據來代替中心點數據所產生的代價之和將被計算。如果計算出的總代價是負的，那么Oi可以被Oh替代；如果計算出的總代價是正的，則當前的中心點Oi被認為是可接受的，在本次迭代中不發生變化。 總代價的計算式為TCih=∑nj=1 Cjih。其中：Cjih表示Oj在Oi被Oh代替后產生的代價。

判定一個非代表數據Oh是否是當前一個代表數據Oi的替代，對每一個非代表性數據Oj來說存在四種情況，所以Cjih的計算也存在以下四種情形：

a）Oj當前隸屬于中心點數據Oi所代表的聚類，如果Oi被Oh所代替作為中心點，且Oj離Om最近，i≠m，那么Oj被重新分配給Om所代表的聚類。此時Cjih=d(j，m)-d(j，i)。

b)Oj當前隸屬于中心點數據Oi所代表的聚類，如果Oi被Oh代替作為一個中心點，且Oj離Oh最近，那么Oj被重新分配給Oh所代表的聚類。此時Cjih=d(j，h)-d(j，i)。

c)Oj當前隸屬于中心點數據Om所代表的聚類，i≠m，如果Oi被Oh代替作為一個中心點，而Oj依然離Om最近，那么Oj仍重新分配給Om所代表的聚類。此時Cjih=0。

d)Oj當前隸屬于中心點Om所代表的聚類，i≠m，如果Oi被Oh代替作為一個中心點，且Oj離Oh最近，那么Oi被重新分配給Oh。Cjih=d(j，h)-d(j，m)。

其中：Oi和Om是兩個原代表性數據。Oh將替換Oi作為新的代表性數據。上述距離的計算采用歐式距離計算公式d(x，y)=[∑ni=1|xi-yi|2]1/2。

2.2 RDDTE

基于以上設想和分析，本文提出了基于代表性數據的決策樹集成方法，并將該方法命名為RDDTE(representative data based decisiontree ensemble)。RDDTE方法分為四步完成：a)通過聚類算法PAM來獲取原始數據中的代表性數據即聚類后各個簇的中心所對應的數據；b)將聚類獲得的代表性數據作為訓練數據來訓練多個決策樹分類器；c)利用某種集成方法來建立集成模型[7~12];d)用測試數據來測試所建立的決策樹集成模型。RDDTE方法的具體描述如下：

輸入：訓練集S1，測試集S2，決策樹算法 D， 用于集成的決策樹個數 T， 基集成方法 E，PAM 算法C，代表性數據的個數 K。

輸出：集成輸出 EO。

從原始訓練集S1中獲取代表性數據Sr=C(K，S1)

 訓練多個個體決策樹分類器;

for i=1 to t{

Di=D(Sr)}

利用已訓練出的多個決策樹分類器來構建集成模型 EM=E(Di)(i=1，2，…，T);

運用測試集來測試所得到的集成模型EO=EM(S2)。

3 實驗

為了驗證本文所提出的基于代表性數據的決策樹集成方法，在Weka內核的基礎上實現了RDDTE算法。本實驗中代表性數據的個數K是關鍵參數，若K太小，則代表性數據的個數太少，以至于訓練數據太少而使得訓練不充分，反而達不到很好的效果；若K太大，則沒有意義。經過多次實驗，選定K值為原始數據個數的0.8倍左右，部分為0.9倍左右。當然該值應根據原始數據的具體情況而定。本實驗分別使用目前最為流行的集成學習算法Bagging和Boosting作為基本集成方法，并選擇決策樹分類算法C4.5作為集成學習時的基學習器。同時訓練出20個C4.5決策樹用于建立集成模型。之所以設定T=20，是因為Bauer等人[12]在研究集成學習時是使用20個基本學習器。最后將該方法在UCI數據集上進行了測試，在對集成模型進行測試時使用十折交叉驗證法，當然如果有單獨的測試數據會更好。

3.1 數據集

本實驗所使用的數據集全部來自UCI數據庫[13]，在這里選擇16個數據集，這些數據集的詳細情況如表 1 所示。

表1 實驗中所使用的UCI數據集

3.2 實驗結果與分析

在這16個數據集上應用算法Bagging、Boosting和RDDTE。在此選擇Bagging算法中袋的大小等于原始數據集的大小。在上述配置參數和數據集下，實驗結果如表 2 和 3 所示。其中表 2表示Bagging和RDDTE(使用Bagging作為基集成方法)在訓練數據量和集成分類精度上的比較；表 3表示Boosting和RDDTE(使用Boosting作為基集成方法)在訓練數據量和集成分類精度上的比較。

表2和3都表明RDDTE方法要明顯地比Bagging和Boosting方法的集成精度高，而且使用更少的訓練數據。其中從表 2可以看出，RDDTE方法在glass、breast cancer、heartstatlog、sonar、wine、zoo、lymphography、monk2這8個數據集上的集成精度明顯高于Bagging，尤其是在glass數據集上要高出近5%，并且所使用的訓練集都要比Bagging少10%~20%左右。在labor和balancescale兩個數據集上，RDDTE和Bagging的集成精度相當，但是卻使用了比Bagging更少的訓練數據，即僅使用了80%~90%左右的原始訓練數據卻獲得了與全部原始數據相當的精度。從表 3可以看出，RDDTE方法在glass、autos、wine、heartstatlog、cleveland14heartdisease、monk2、hungarian14heartdisease這7個數據集上使用了比原始訓練集要少10%~20%左右的代表性訓練集，但是集成精度明顯高于使用全部原始訓練集的Boosting；而在soybeansmall、badges、hepatitis3個數據集上RDDTE的集成精度與Boosting的集成精度接近，但是RDDTE在這3個數據集上所使用的訓練數據的個數卻要比Boosting少10%~20%左右。

4 結束語

本文提出了一種基于代表性數據的決策樹集成學習方法。實驗證明該方法可以使用較原始訓練數據少的代表性數據來取得更好的集成效果，因此該方法可以作為通過盡可能少的數據來獲得盡可能好的集成學習效果的一種實現方法。

進一步的工作包括對該方法進行完善和改進，以及進行深入的理論上的分析和嚴格論證，在回歸任務、神經網絡等其他一些學習方法和其他集成學習方法上進行評測。

參考文獻：

[1]田劍， 胡月明， 王長委， 等. 聚類支持下決策樹模型在耕地評價中的應用[J]. 農業工程學報， 2007， 23 (12):58 62.

[2]饒秀琪，張國基.基于KPCA 的決策樹方法及其應用[J].計算機工程與設計，2007，28(7):16121613.

[3]DURKIN J，蔡競峰，蔡自興.決策樹技術及其當前研究方向[J].控制工程， 2005，12(1):1521.

[4]OATES T ，JENSEN D. The effects of training set size on decision tree complexity[C]// Proc of the 14th International Conference on Machine Learning . Nashville， Tennessee:[s.n.]， 1997:379390.

[5]SEBBAN M， NOCK R， CHAUCHAT J H， et al. Impact of learning set quality and size on decision tree performances [J]. IJCSS，2000，1(1) :85105.

[6]BRODLEY C E ， FRIEDL M A. Identifying and eliminating mislabeled training instances [C]//Proc of the 13th National Conference on Artificial Intelligence. 1996:799805.

[7]周志華，陳世福.神經網絡集成[J].計算機學報， 2002， 25(1):18.

[8]ZHOU Zhihua， WU Jianxin， TANG Wei. Ensembling neural networks: many could be better than all[J]. Artificial Intelligence， 2002， 137(12): 239263.

[9]ZHOU Zhihua， WU Jianxin，JIANG Yuan， et al. Genetic algorithm based selective neural network ensemble[C]//Proc of the 17th International Joint Conference on Artificial Intelligence. Seattle， WA:[s.n.]， 2001:797802.

[10]DIETTERICH T G. Ensemble methods in machine learning[C]//Proc of the 1st International Workshop on Multiple Classifier Systems. 2000:115.

[11]BREIMAN L. Bagging predictors[J]. Machine Learning，1996，24(2):123140.

[12]BAUER E， KOHAV R. An empirical comparison of voting classification algorithms: Bagging， Boosting， and variants[J].Machine Learning， 1999，36 (12):105139.

[13]BLAKE C， KEOGH E， MERZ C J. UCI repository of machine learning databases[D]. Irvine: Department of Information and Computer Science， University of California， 1998.