CART決策樹的兩種改進及應用

張 亮，寧 芊

（四川大學 電子信息學院，四川 成都610065）

0 引 言

在決策樹算法中，分類與回歸樹CART-（classification and regression trees）算法是一種十分有效的非參數分類和回歸方法［1］。CART 選擇具有最小GINI系數值的屬性作為分裂屬性［2］，并按照節點的分裂屬性，采用二元遞歸分割的方式把每個內部節點分割成兩個子節點，遞歸形成一棵結構簡潔的二叉樹。但CART 算法存在以下不足：一方面，選取內部節點的分裂屬性時，對于連續型描述屬性，CART 算法將計算該屬性的每個分割點的GINI系數，再選擇具有最小GINI系數的分割點作為該屬性的分割閾值，如果屬性集中連續屬性個數很多且連續屬性的不同取值也很多，采用這種方式建立的決策樹計算量會很大；另一方面，決策樹在選擇葉節點的類別標號時，以-“多數表決”的方式選擇葉節點中樣本數占最多的類別標識葉節點［3］，雖然在多數情況下，“多數表決”是一個不錯的選擇，但這會屏蔽小類屬數據對分類結果的表決。針對CART 算法這兩方面的不足，本文將Fayyad邊界點判定原理［4］應用于CART算法，并基于關鍵度度量［5］選擇葉節點的類別標號，有效減少了處理連續型描述屬性的計算量，提高了決策樹的生成效率，在樣本集主類類屬分布不均，小類屬樣本并不是稀有樣本的情況下，使小類屬樣本得到了表達，提高了決策樹的分類準確率。

1 CART算法原理

CART 算法采用最小GINI系數選擇內部節點的分裂屬性［6］。根據類別屬性的取值是離散值還是連續值，CART算法生成的決策樹可以相應地分為分類樹和回歸樹［7］。本文將CART 算法用于分類問題的研究，因此采用的是分類樹，形成分類樹的步驟如下：

步驟1 計算屬性集中各屬性的GINI系數，選取GINI系數最小的屬性作為根節點的分裂屬性。對連續屬性，需計算其分割閾值，按分割閾值將其離散化，并計算其GINI系數；對離散屬性，需將樣本集按照該離散屬性取值的可能子集進行劃分 （全集和空集除外），如該離散屬性有n 個取值，則其有效子集有2n－2個，然后選擇GINI系數最小的子集作為該離散型屬性的劃分方式，該最小GINI系數作為該離散屬性的GINI系數。

GINI系數度量樣本劃分或訓練樣本集的不純度，不純度越小表明樣本的 “純凈度”越高［8］。

GINI系數的計算：

（1）假設整個樣本集為S，類別集為 ｛C1，C2，…，Cn｝，總共分為n類，每個類對應一個樣本子集Si（1≤i≤n）。令｜S｜為樣本集S 的樣本數，｜Ci｜為樣本集S 中屬于類Ci的樣本數，則樣本集的GINI系數定義如下

其中，pi＝｜Ci｜／｜S｜為樣本集中樣本屬于類Ci的概率。

（2）在只有二元分裂的時候，對于訓練樣本集S 中的屬性A 將S 分成的子集S1和S2，則給定劃分S 的GINI系數如下公式

其中，｜SK｜／｜S｜為第k （k＝1，2）個子集占整個樣本集的權值，為在屬性A 上劃分樣本集S 的GINI系數。

步驟2 若分裂屬性是連續屬性，樣本集按照在該屬性上的取值，分成＜＝T 和＞T 的兩部分，T 為該連續屬性的分割閾值；若分裂屬性是離散屬性，樣本集按照在該屬性上的取值是否包含在該離散屬性具有最小GINI系數的真子集中，分成兩部分。

步驟3 對根節點的分裂屬性對應的兩個樣本子集S1和S2，采用與步驟1相同的方法遞歸地建立樹的子節點。如此循環下去，直至所有子節點中的樣本屬于同一類別或沒有可以選作分裂屬性的屬性為止。

步驟4 對生成的決策樹進行剪枝。

對于某個連續型屬性Ac，假設在某個節點上的樣本集S的樣本數量為total，CART算法將對該連續屬性作如下處理：

（1）將該節點上的所有樣本按照連續型描述屬性Ac的具體數值，由小到大進行排序，得到屬性值序列 ｛A1c，A2c，…，Atotalc｝。

（2）在取值序列中生成total－1個分割點。第i（0＜i＜total）個分割點的取值設置為Vi＝ （Aic＋A（i＋1）c）／2，它可以將節點上的樣本集劃分為S1＝ ｛s｜s∈S，Ac（S）≤Vi｝和S2＝ ｛s｜s∈S，Ac（S）＞Vi｝兩個子集，Ac（S）為樣本s在屬性Ac上的取值。

（3）計算total－1 個分割點的GINI系數，選擇GINI系數最小的分割點來劃分樣本集。

2 CART算法選取連續屬性分割閾值的改進

在上述對連續型描述屬性的離散化過程中，CART 算法要計算每個分割點的GINI系數，而每個連續型描述屬性的分割點為節點的樣本數目減1。若樣本集的樣本數很多、連續型描述屬性很多、且決策樹的節點數也很多時，如在本文的故障診斷項目中，待分類樣本數在5000以上，屬性個數在60以上。隨著樣本維數的增高，算法的計算量也隨之增大，構建決策樹的效率就會降低。文獻 ［4，9］將“Fayyad邊界點判定原理”用于改進C4.5算法的連續型描述屬性的分割閾值的選擇，由于熵和GINI系數相似，都刻畫了樣本集的純凈度：熵和GINI系數越小，樣本集越純凈。因此本文將其用于CART 算法，對CART 算法中選擇連續型描述屬性的分割閾值的計算復雜性問題提出了一些改進。

2.1 Fayyad邊界點判定原理

定義1 邊界點［9］：屬性A 中的一個值T 是一個邊界點，當且僅當在按屬性A 的值升序排列的樣本集中，存在兩個樣本s1，s2∈S具有不同的類，使得A（s1）＜T＜A（s2），且不存在任何的樣本s∈S，使A（s1）＜A（s）＜A（s2）。S為樣本集，A（s）表示樣本s的屬性A 的取值。

定理1 Fayyad邊界點判定定理［9］：若T 使得E（A，T；S）最小，則T 是一個邊界點。其中，A 為屬性，S 為樣本集，E 為在屬性A 上劃分樣本集S的平均信息量，也稱平均類熵，T 為屬性A 的閾值點。該定理表明，對連續屬性A，使得樣本集合的平均類熵達到最小值的T，總是處于排序后的樣本序列中兩個相鄰異類樣本之間，也即使得樣本集合的平均類熵達到最小值的T 是屬性A 的一個分界點。

2.2 熵和GINI系數

熵刻畫了任意樣本集的純度，熵值越小子集劃分的純度越高［10］，識別其中元組分類所需要的平均信息量就越小。熵的計算公式如下所示式中：pi——樣本集S中樣本屬于類Ci的概率。

對某一連續型描述屬性A 的一個分割點T，劃分樣本集S 的平均類熵為

式中：S1——樣本集S 在屬性A 上取值小于等于T 的子集，S2——大于T 的子集。

在同一二元分裂的情況下，熵和GINI系數的關系如圖1所示。由圖可知：熵和GINI系數在同一二元分裂中變化趨勢相同，熵越小，GINI系數也越小。

圖1 熵和GINI系數的關系

2.3 Fayyad邊界點判定原理用于CART算法

比較熵理論和GINI系數可知，熵越小，樣本集越純凈，GINI系數也越小。因此，根據Fayyad邊界點判定定理：對連續型描述屬性A，使GINI系數達到最小值的分割閾值T，也總是處于樣本集按屬性A 的值升序排列后的屬性A 的邊界點處。

在CART 算法中，選取連續型描述屬性的分割閾值時，不需要計算每個分割點的GINI系數，只要計算分界點的GINI系數即可，GINI系數最小的分界點即為該屬性的閾值點。為了保持與CART 的一致性，這里邊界點選為排序后相鄰不同類別的屬性值的平均值。

采用改進的CART 算法，當需要離散化的屬性的值越多，而樣本所屬類別越少時，算法的計算效率提高得越明顯；只有在出現最不理想情況時，即每個屬性值對應一個類別，改進算法運算次數與未改進算法才會相同，不會降低算法的計算效率［4］。

3 CART算法選擇葉節點類標號的改進

決策樹在選擇葉節點的類別標號時，對葉節點的樣本集采取 “多數表決”的方式，即選擇多數類作為葉節點的類別標號。但在實際應用中，“多數表決”并不是所有情況都應遵循的唯一準則。本文針對樣本集的主類類屬分布不平衡時，小類屬樣本無法表達的情況，利用關鍵度度量進行改進。與關鍵度有關的幾個定義如下：

定義2 類屬分散度：第j個葉節點中的類別i 的樣本數占子樹總的樣本集中類別i的樣本數的比重

定義3 類屬決策度：第j個葉節點中的類別i的樣本數占葉節點j的總的樣本數的比重

定義4 關鍵度：其值為類屬分散度和類屬決策度之積

為了克服偏類樣本集中多數類的數量優勢，給小類屬提供機會展示自己的數據特征，改進的CART 算法在選擇葉節點的類別標號時，選取關鍵度最大的類別標號，而不是選擇多數類的類別標號。

4 改進算法核心部分流程

圖2和圖3分別為選擇內部節點的分裂屬性的流程和利用關鍵度度量選擇葉節點的類標號的流程，本文主要研究CART 算法選擇連續型描述屬性分割閾值的改進方法，因此，圖2主要針對連續型描述屬性。

圖2 選擇內部分裂屬性的流程

圖3 選擇葉節點類標號的流程

5 實驗結果及分析

本文 實 驗 在Microsoft Visual Studio 2010 平 臺 上 進行，算法實現使用C＃語言。實驗由兩個部分組成：①改進的CART 算法在多樣本數，高維度，多類別的故障診斷項目上的應用；②在從標準數據集UCI中采集的部分數據上驗證改進的CART 算法的計算效率和分類準確率，實驗以CPU 耗時的長短來衡量算法的計算效率的高低。

實驗采用10折交叉驗證法［11］驗證決策樹的分類準確率和計算效率。將原始樣本集均分成10組，每組樣本都包含每類樣本的十分之一，將每個樣本子集輪流做一次測試集，其余的9 組樣本子集作為訓練集，這樣進行10 次實驗，取10次實驗的平均分類準確率和CPU 耗時。分類準確率為測試集中被正確分類的樣本數占測試集總樣本數的比例。

實驗1采用某故障診斷系統的樣本集，該樣本集共包括5620個樣本，每個樣本有64個連續屬性和1個類別屬性，共分為10類。實驗1用到的樣本數據情況見表1。

表1 實驗1樣本數據情況

實驗1對改進的CART 算法和傳統的CART 算法在該故障診斷系統中的計算效率和準確率進行了對比，因為該故障診斷系統10個類別的樣本幾乎均勻分布，不存在主類類屬分布不平衡的情況，表2結果表明：在該應用中，改進前后的CART 算法的分類準確率相當，由于改進的CART 算法簡化了連續屬性選取分割閾值的方法，所以改進后的算法的計算時間縮短了約45%。

表2 實驗1的結果

實驗2采用標準數據集UCI中的10組樣本集對改進前后的CART 算法的分類準確率和建樹效率進行對比，實驗2用到的樣本情況見表3。表中用＊標注的4個樣本集主類類屬分布不平衡，這4 個樣本集的各類樣本分布情況見表4。

表3 實驗2使用的樣本集

表4 實驗2主類類屬分布不均的樣本情況

實驗2的結果見表5。實驗2表明：①在主類類屬分布不平衡的4個樣本集中運用改進的CART 算法，生成決策樹的效率得到了提高，分類準確率也略有提高；②對不存在主類類屬分布不平衡的樣本集，生成決策樹的效率提高了，分類準確率與未改進算法的準確率相當。

表5 實驗2的結果

實驗1和實驗2的結果表明：①利用Fayyad邊界點原理改進CART 算法選取連續屬性分割閾值的方法，可以有效提高決策樹的生成效率，減少計算量；②對于樣本集主類類屬分布不平衡的情況，利用關鍵度度量選取葉節點的類標號，而不是采取 “多數表決”的方式，可以提高分類準確率，使在數量上占少數但并不是稀有的類別可以在分類中得到表現。

6 結束語

結合Fayyad邊界點判定原理對CART 算法選取連續屬性的分割閾值的方法進行了改進，減少了該算法的計算量，提高了決策樹的生成效率。在具有多個連續型描述屬性的故障診斷系統中，這一改進具有很好的應用價值。因此，“Fayyad 邊界點判定原理”也適用于改進CART 算法選取連續型描述屬性分割閾值的方法。結合關鍵度度量改進了CART 算法選取葉節點類標號的方法，這一改進提高了主類類屬分布不平衡的樣本集的分類準確率。在部分小樣本集上，如本文實驗2的第3個樣本集，改進前后的算法的準確率都偏低，這是CART 算法的自身缺陷，我們將進一步對小樣本集結合其它的分類算法，如SVM 算法，提高小樣本集的分類準確率，這將是我們下一步的研究方向。

［1］CHEN Huilin，XIA Daoxun.Applied research on data mining based on CART decision tree algorithm ［J］.Coal Technology，2011，30 （10）：164－166 （in Chinese）.［陳輝林，夏道勛.基于CART 決策樹數據挖掘算法的應用研究 ［J］.煤炭技術，2011，30 （10）：164－166.］

［2］ZHANG Beilei.Application of CART algorithm in the analysis of students’achievement ［D］.Hefei：Anhui University，2009 （in Chinese）.［張蓓蕾.CART 算法在學生成績分析中的應用研究 ［D］.合肥：安徽大學，2009.］

［3］SHAO Fengjing，YU Zhongqing， WANG Jinlong，et al.Principle and algorithm of data mining ［M］.2nd ed.Beijing：Science and Technology Press，2009 （in Chinese）. ［邵峰晶，于忠清，王金龍，等.數據挖掘原理與算法 ［M］.第二版.北京：科學出版社，2009.］

［4］YAO Yafu，XING Liutao.Improvement of C4.5decision tree continuous attributes segmentation threshold algorithm and its application［J］.Journal of Central South University （Science and Technology），2011，42（12）：3772－3776（in Chinese）. ［姚亞夫，邢留濤.決策樹C4.5連續屬性分割閾值算法改進及其應用［J］.中南大學學報（自然科學版），2011，42（12）：3772－3776.］

［5］LV Xiaoyan，LIU Chunhuang，ZHU Jiansheng.Improved algorithm of decision tree based on key decision factor and its applications in railway transportation［J］.Journal of the China Railway Society，2011，33 （9）：62－67 （in Chinese）. ［呂曉艷，劉春煌，朱建生.基于關鍵度度量的決策樹算法改進及其在鐵路運輸中的應用［J］.鐵道學報，2011，33 （9）：62－67.］

［6］LIU Chunying.A method of generating cost－sensitive decision tree based on correlation degree ［J］.Journal of Changchun University of Technology （Natural Science Edition），2013，34（2）：218－222 （in Chinese）.［劉春英.基于關聯度的代價敏感決策樹生成方法 ［J］.長春工業大學學報 （自然科學版），2013，34 （2）：218－222.］

［7］ZHANG Nan.Application and research in the identification of latent customers based on improved CART algorithm ［D］.Tianjin：Hebei University of Technology，2008 （in Chinese）.［張楠.改進的CART 算法在潛在客戶識別中的應用研究［D］.天津：河北工業大學，2008.］

［8］SUN Xizhou.The application and research of data mining classification technology in fitness club management system ［D］.Qingdao：Ocean University of China，2011 （in Chinese）.［孫喜洲.數據挖掘分類技術在健身會所管理系統中的應用研究［D］.青島：中國海洋大學，2011.］

［9］QIAO Zengwei，SUN Weixiang.Two improvements to C4.5 algorithm ［J］.Journal of Jiangsu Polytechnic University，2008，20（4）：56－59（in Chinese）.［喬增偉，孫衛祥.C4.5算法的兩點改進［J］.江蘇工業學院學報，2008，20 （4）：56－59.］

［10］LI Ruping.Research of decision tree classification algorithm in data mining ［J］.Journal of East China Institute of Technology （Science and Technology），2010，33 （2）：192－196 （in Chinese）.［李如平.數據挖掘中決策樹分類算法的研究 ［J］.東華理工大學學報（自然科學版），2010，33 （2）：192－196.］

［11］TIAN Jing，AI Tinghua，DING Shaojun.Grid pattern recognition in road networks based on C4.5algorithm ［J］.Journal of Surveying and Mapping，2012，41 （1）：121－126 （in Chinese）.［田晶，艾廷華，丁紹軍.基于C4.5算法的道路網網格模式識別 ［J］.測繪學報，2012，41 （1）：121－126.］