CART決策樹的兩種改進(jìn)及應(yīng)用

張 亮，寧 芊

（四川大學(xué) 電子信息學(xué)院，四川 成都610065）

0 引 言

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

1 CART算法原理

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

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

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

GINI系數(shù)的計(jì)算：

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

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

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

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

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

步驟3 對(duì)根節(jié)點(diǎn)的分裂屬性對(duì)應(yīng)的兩個(gè)樣本子集S1和S2，采用與步驟1相同的方法遞歸地建立樹的子節(jié)點(diǎn)。如此循環(huán)下去，直至所有子節(jié)點(diǎn)中的樣本屬于同一類別或沒有可以選作分裂屬性的屬性為止。

步驟4 對(duì)生成的決策樹進(jìn)行剪枝。

對(duì)于某個(gè)連續(xù)型屬性Ac，假設(shè)在某個(gè)節(jié)點(diǎn)上的樣本集S的樣本數(shù)量為total，CART算法將對(duì)該連續(xù)屬性作如下處理：

（1）將該節(jié)點(diǎn)上的所有樣本按照連續(xù)型描述屬性Ac的具體數(shù)值，由小到大進(jìn)行排序，得到屬性值序列 ｛A1c，A2c，…，Atotalc｝。

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

（3）計(jì)算total－1 個(gè)分割點(diǎn)的GINI系數(shù)，選擇GINI系數(shù)最小的分割點(diǎn)來(lái)劃分樣本集。

2 CART算法選取連續(xù)屬性分割閾值的改進(jìn)

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

2.1 Fayyad邊界點(diǎn)判定原理

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

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

2.2 熵和GINI系數(shù)

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

對(duì)某一連續(xù)型描述屬性A 的一個(gè)分割點(diǎn)T，劃分樣本集S 的平均類熵為

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

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

圖1 熵和GINI系數(shù)的關(guān)系

2.3 Fayyad邊界點(diǎn)判定原理用于CART算法

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

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

采用改進(jìn)的CART 算法，當(dāng)需要離散化的屬性的值越多，而樣本所屬類別越少時(shí)，算法的計(jì)算效率提高得越明顯；只有在出現(xiàn)最不理想情況時(shí)，即每個(gè)屬性值對(duì)應(yīng)一個(gè)類別，改進(jìn)算法運(yùn)算次數(shù)與未改進(jìn)算法才會(huì)相同，不會(huì)降低算法的計(jì)算效率［4］。

3 CART算法選擇葉節(jié)點(diǎn)類標(biāo)號(hào)的改進(jìn)

決策樹在選擇葉節(jié)點(diǎn)的類別標(biāo)號(hào)時(shí)，對(duì)葉節(jié)點(diǎn)的樣本集采取 “多數(shù)表決”的方式，即選擇多數(shù)類作為葉節(jié)點(diǎn)的類別標(biāo)號(hào)。但在實(shí)際應(yīng)用中，“多數(shù)表決”并不是所有情況都應(yīng)遵循的唯一準(zhǔn)則。本文針對(duì)樣本集的主類類屬分布不平衡時(shí)，小類屬樣本無(wú)法表達(dá)的情況，利用關(guān)鍵度度量進(jìn)行改進(jìn)。與關(guān)鍵度有關(guān)的幾個(gè)定義如下：

定義2 類屬分散度：第j個(gè)葉節(jié)點(diǎn)中的類別i 的樣本數(shù)占子樹總的樣本集中類別i的樣本數(shù)的比重

定義3 類屬?zèng)Q策度：第j個(gè)葉節(jié)點(diǎn)中的類別i的樣本數(shù)占葉節(jié)點(diǎn)j的總的樣本數(shù)的比重

定義4 關(guān)鍵度：其值為類屬分散度和類屬?zèng)Q策度之積

為了克服偏類樣本集中多數(shù)類的數(shù)量?jī)?yōu)勢(shì)，給小類屬提供機(jī)會(huì)展示自己的數(shù)據(jù)特征，改進(jìn)的CART 算法在選擇葉節(jié)點(diǎn)的類別標(biāo)號(hào)時(shí)，選取關(guān)鍵度最大的類別標(biāo)號(hào)，而不是選擇多數(shù)類的類別標(biāo)號(hào)。

4 改進(jìn)算法核心部分流程

圖2和圖3分別為選擇內(nèi)部節(jié)點(diǎn)的分裂屬性的流程和利用關(guān)鍵度度量選擇葉節(jié)點(diǎn)的類標(biāo)號(hào)的流程，本文主要研究CART 算法選擇連續(xù)型描述屬性分割閾值的改進(jìn)方法，因此，圖2主要針對(duì)連續(xù)型描述屬性。

圖2 選擇內(nèi)部分裂屬性的流程

圖3 選擇葉節(jié)點(diǎn)類標(biāo)號(hào)的流程

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

本文 實(shí) 驗(yàn) 在Microsoft Visual Studio 2010 平 臺(tái) 上 進(jìn)行，算法實(shí)現(xiàn)使用C＃語(yǔ)言。實(shí)驗(yàn)由兩個(gè)部分組成：①改進(jìn)的CART 算法在多樣本數(shù)，高維度，多類別的故障診斷項(xiàng)目上的應(yīng)用；②在從標(biāo)準(zhǔn)數(shù)據(jù)集UCI中采集的部分?jǐn)?shù)據(jù)上驗(yàn)證改進(jìn)的CART 算法的計(jì)算效率和分類準(zhǔn)確率，實(shí)驗(yàn)以CPU 耗時(shí)的長(zhǎng)短來(lái)衡量算法的計(jì)算效率的高低。

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

實(shí)驗(yàn)1采用某故障診斷系統(tǒng)的樣本集，該樣本集共包括5620個(gè)樣本，每個(gè)樣本有64個(gè)連續(xù)屬性和1個(gè)類別屬性，共分為10類。實(shí)驗(yàn)1用到的樣本數(shù)據(jù)情況見表1。

表1 實(shí)驗(yàn)1樣本數(shù)據(jù)情況

實(shí)驗(yàn)1對(duì)改進(jìn)的CART 算法和傳統(tǒng)的CART 算法在該故障診斷系統(tǒng)中的計(jì)算效率和準(zhǔn)確率進(jìn)行了對(duì)比，因?yàn)樵摴收显\斷系統(tǒng)10個(gè)類別的樣本幾乎均勻分布，不存在主類類屬分布不平衡的情況，表2結(jié)果表明：在該應(yīng)用中，改進(jìn)前后的CART 算法的分類準(zhǔn)確率相當(dāng)，由于改進(jìn)的CART 算法簡(jiǎn)化了連續(xù)屬性選取分割閾值的方法，所以改進(jìn)后的算法的計(jì)算時(shí)間縮短了約45%。

表2 實(shí)驗(yàn)1的結(jié)果

實(shí)驗(yàn)2采用標(biāo)準(zhǔn)數(shù)據(jù)集UCI中的10組樣本集對(duì)改進(jìn)前后的CART 算法的分類準(zhǔn)確率和建樹效率進(jìn)行對(duì)比，實(shí)驗(yàn)2用到的樣本情況見表3。表中用＊標(biāo)注的4個(gè)樣本集主類類屬分布不平衡，這4 個(gè)樣本集的各類樣本分布情況見表4。

表3 實(shí)驗(yàn)2使用的樣本集

表4 實(shí)驗(yàn)2主類類屬分布不均的樣本情況

實(shí)驗(yàn)2的結(jié)果見表5。實(shí)驗(yàn)2表明：①在主類類屬分布不平衡的4個(gè)樣本集中運(yùn)用改進(jìn)的CART 算法，生成決策樹的效率得到了提高，分類準(zhǔn)確率也略有提高；②對(duì)不存在主類類屬分布不平衡的樣本集，生成決策樹的效率提高了，分類準(zhǔn)確率與未改進(jìn)算法的準(zhǔn)確率相當(dāng)。

表5 實(shí)驗(yàn)2的結(jié)果

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

6 結(jié)束語(yǔ)

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

［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 決策樹數(shù)據(jù)挖掘算法的應(yīng)用研究 ［J］.煤炭技術(shù)，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 算法在學(xué)生成績(jī)分析中的應(yīng)用研究 ［D］.合肥：安徽大學(xué)，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）. ［邵峰晶，于忠清，王金龍，等.數(shù)據(jù)挖掘原理與算法 ［M］.第二版.北京：科學(xué)出版社，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連續(xù)屬性分割閾值算法改進(jìn)及其應(yīng)用［J］.中南大學(xué)學(xué)報(bào)（自然科學(xué)版），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）. ［呂曉艷，劉春煌，朱建生.基于關(guān)鍵度度量的決策樹算法改進(jìn)及其在鐵路運(yùn)輸中的應(yīng)用［J］.鐵道學(xué)報(bào)，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）.［劉春英.基于關(guān)聯(lián)度的代價(jià)敏感決策樹生成方法 ［J］.長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào) （自然科學(xué)版），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）.［張楠.改進(jìn)的CART 算法在潛在客戶識(shí)別中的應(yīng)用研究［D］.天津：河北工業(yè)大學(xué)，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）.［孫喜洲.數(shù)據(jù)挖掘分類技術(shù)在健身會(huì)所管理系統(tǒng)中的應(yīng)用研究［D］.青島：中國(guó)海洋大學(xué)，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）.［喬增偉，孫衛(wèi)祥.C4.5算法的兩點(diǎn)改進(jìn)［J］.江蘇工業(yè)學(xué)院學(xué)報(bào)，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）.［李如平.數(shù)據(jù)挖掘中決策樹分類算法的研究 ［J］.東華理工大學(xué)學(xué)報(bào)（自然科學(xué)版），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算法的道路網(wǎng)網(wǎng)格模式識(shí)別 ［J］.測(cè)繪學(xué)報(bào)，2012，41 （1）：121－126.］