每日消息!CART樹算法詳解 基于訓(xùn)練數(shù)據(jù)集生成的CART算法

算法步驟

(資料圖片)

CART假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點(diǎn)特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價(jià)于遞歸地二分每個(gè)特征，將輸入空間即特征空間劃分為有限個(gè)單元，并在這些單元上確定預(yù)測(cè)的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。

CART算法由以下兩步組成：

決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大； 決策樹剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，這時(shí)損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。CART決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。CART決策樹既可以用于分類也可以用于回歸。本文我們僅討論用于分類的CART。對(duì)分類樹而言，CART用Gini系數(shù)最小化準(zhǔn)則來進(jìn)行特征選擇，生成二叉樹。 CART生成算法如下：

輸入：訓(xùn)練數(shù)據(jù)集D，停止計(jì)算的條件： 輸出：CART決策樹。

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

設(shè)結(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為D，計(jì)算現(xiàn)有特征對(duì)該數(shù)據(jù)集的Gini系數(shù)。此時(shí)，對(duì)每一個(gè)特征A，對(duì)其可能取的每個(gè)值a，根據(jù)樣本點(diǎn)對(duì)A=a的測(cè)試為“是”或 “否”將D分割成D1和D2兩部分，計(jì)算A=a時(shí)的Gini系數(shù)。 在所有可能的特征A以及它們所有可能的切分點(diǎn)a中，選擇Gini系數(shù)最小的特征及其對(duì)應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(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)中去。 對(duì)兩個(gè)子結(jié)點(diǎn)遞歸地調(diào)用步驟l~2，直至滿足停止條件。 生成CART決策樹。 算法停止計(jì)算的條件是結(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閾值，或樣本集的Gini系數(shù)小于預(yù)定閾值（樣本基本屬于同一類），或者沒有更多特征。

Gini指數(shù)的計(jì)算

其實(shí)gini指數(shù)最早應(yīng)用在經(jīng)濟(jì)學(xué)中，主要用來衡量收入分配公平度的指標(biāo)。在決策樹算CART算法中用gini指數(shù)來衡量數(shù)據(jù)的不純度或者不確定性，同時(shí)用gini指數(shù)來決定類別變量的最優(yōu)二分值得切分問題。

在分類問題中，假設(shè)有K個(gè)類，樣本點(diǎn)屬于第k類的概率為Pk，則概率分布的gini指數(shù)的定義為：

如果樣本集合D根據(jù)某個(gè)特征A被分割為D1，D2兩個(gè)部分，那么在特征A的條件下，集合D的gini指數(shù)的定義為： gini指數(shù)Gini(D,A)表示特征A不同分組的數(shù)據(jù)集D的不確定性。gini指數(shù)值越大，樣本集合的不確定性也就越大，這一點(diǎn)與熵的概念比較類似。

所以在此，基于以上的理論，我們可以通過gini指數(shù)來確定某個(gè)特征的最優(yōu)切分點(diǎn)(也即只需要確保切分后某點(diǎn)的gini指數(shù)值最小)，這就是決策樹CART算法中類別變量切分的關(guān)鍵所在。是不是對(duì)于決策樹的CART算法有點(diǎn)小理解啦！其實(shí)，這里可以進(jìn)一步拓展到我們對(duì)于類別變量的粗分類應(yīng)用上來。比如我某個(gè)特征變量下有20多個(gè)分組，現(xiàn)在我只想要5個(gè)大類，如何將這個(gè)20多個(gè)類合并為5個(gè)大類，如何分類最優(yōu)，以及如何找到最優(yōu)的分類。這些建模初期的數(shù)據(jù)預(yù)處理問題其實(shí)我們都可以用gini指數(shù)來解決。

例子

首先對(duì)數(shù)據(jù)集非類標(biāo)號(hào)屬性{是否有房，婚姻狀況，年收入}分別計(jì)算它們的Gini系數(shù)增益，取Gini系數(shù)增益值最大的屬性作為決策樹的根節(jié)點(diǎn)屬性。根節(jié)點(diǎn)的Gini系數(shù)

Gini(是否拖欠貸款)=1?(3/10)^2?(7/10)^2=0.42

當(dāng)根據(jù)是否有房來進(jìn)行劃分時(shí)，Gini系數(shù)增益計(jì)算過程為

Gini(左子節(jié)點(diǎn))=1?(0/3)^2?(3/3)^2=0

Gini(右子節(jié)點(diǎn))=1?(3/7)^2?(4/7)^2=0.4898

Δ{是否有房}=0.42?710×0.4898?310×0=0.077

若按婚姻狀況屬性來劃分，屬性婚姻狀況有三個(gè)可能的取值{married，single，divorced}，分別計(jì)算劃分后的

{married} | {single,divorced}{single} | {married,divorced}{divorced} | {single,married}

的Gini系數(shù)增益。 當(dāng)分組為{married} | {single,divorced}時(shí)，Sl表示婚姻狀況取值為married的分組，Sr表示婚姻狀況取值為single或者divorced的分組

Δ{婚姻狀況}=0.42?4/10×0?6/10×[1?(3/6)^2?(3/6)^2]=0.12

當(dāng)分組為{single} | {married,divorced}時(shí)， Δ{婚姻狀況}=0.42?4/10×0.5?6/10×[1?(1/6^)2?(5/6)^2]=0.053

當(dāng)分組為{divorced} | {single,married}時(shí)， Δ{婚姻狀況}=0.42?2/10×0.5?8/10×[1?(2/8)^2?(6/8)^2]=0.02

對(duì)比計(jì)算結(jié)果，根據(jù)婚姻狀況屬性來劃分根節(jié)點(diǎn)時(shí)取Gini系數(shù)增益最大的分組作為劃分結(jié)果，也就是{married} | {single,divorced}。 最后考慮年收入屬性，我們發(fā)現(xiàn)它是一個(gè)連續(xù)的數(shù)值類型。我們?cè)谇懊娴奈恼吕镆呀?jīng)專門介紹過如何應(yīng)對(duì)這種類型的數(shù)據(jù)劃分了。對(duì)此還不是很清楚的朋友可以參考之前的文章，這里不再贅述。

對(duì)于年收入屬性為數(shù)值型屬性，首先需要對(duì)數(shù)據(jù)按升序排序，然后從小到大依次用相鄰值的中間值作為分隔將樣本劃分為兩組。例如當(dāng)面對(duì)年收入為60和70這兩個(gè)值時(shí)，我們算得其中間值為65。倘若以中間值65作為分割點(diǎn)。Sl作為年收入小于65的樣本，Sr表示年收入大于等于65的樣本，于是則得Gini系數(shù)增益為

Δ(年收入)=0.42?1/10×0?9/10×[1?(6/9)^2?(3/9)^2]=0.02

其他值的計(jì)算同理可得，我們不再逐一給出計(jì)算過程，僅列出結(jié)果如下（最終我們?nèi)∑渲惺沟迷鲆孀畲蠡哪莻€(gè)二分準(zhǔn)則來作為構(gòu)建二叉樹的準(zhǔn)則）：

注意，這與我們之前在《數(shù)據(jù)挖掘十大算法之決策樹詳解（1）》中得到的結(jié)果是一致的。最大化增益等價(jià)于最小化子女結(jié)點(diǎn)的不純性度量（Gini系數(shù)）的加權(quán)平均值，之前的表里我們列出的是Gini系數(shù)的加權(quán)平均值，現(xiàn)在的表里給出的是Gini系數(shù)增益。現(xiàn)在我們希望最大化Gini系數(shù)的增益。根據(jù)計(jì)算知道，三個(gè)屬性劃分根節(jié)點(diǎn)的增益最大的有兩個(gè)：年收入屬性和婚姻狀況，他們的增益都為0.12。此時(shí)，選取首先出現(xiàn)的屬性作為第一次劃分。

接下來，采用同樣的方法，分別計(jì)算剩下屬性，其中根節(jié)點(diǎn)的Gini系數(shù)為（此時(shí)是否拖欠貸款的各有3個(gè)records） Gini(是否拖欠貸款)=1?(3/6)^2?(3/6)^2=0.5

與前面的計(jì)算過程類似，對(duì)于是否有房屬性，可得 Δ{是否有房}=0.5?4/6×[1?(3/4)^2?(1/4)^2]?2/6×0=0.25

對(duì)于年收入屬性則有：

最后我們構(gòu)建的CART如下圖所示：

最后我們總結(jié)一下，CART和C4.5的主要區(qū)別：

C4.5采用信息增益率來作為分支特征的選擇標(biāo)準(zhǔn)，而CART則采用Gini系數(shù)；C4.5不一定是二叉樹，但CART一定是二叉樹。

關(guān)于過擬合以及剪枝

決策樹很容易發(fā)生過擬合，也就是由于對(duì)train數(shù)據(jù)集適應(yīng)得太好，反而在test數(shù)據(jù)集上表現(xiàn)得不好。這個(gè)時(shí)候我們要么是通過閾值控制終止條件避免樹形結(jié)構(gòu)分支過細(xì)，要么就是通過對(duì)已經(jīng)形成的決策樹進(jìn)行剪枝來避免過擬合。另外一個(gè)克服過擬合的手段就是基于Bootstrap的思想建立隨機(jī)森林（Random Forest）。關(guān)于剪枝的內(nèi)容可以參考文獻(xiàn)【2】以了解更多，如果有機(jī)會(huì)我也可能在后續(xù)的文章里討論它。

參考文獻(xiàn)

【1】Wu, X., Kumar, V., Quinlan, J.R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G.J., Ng, A., Liu, B., Philip, S.Y. and Zhou, Z.H., 2008. Top 10 algorithms in data mining. Knowledge and information systems, 14(1), pp.1-37. (http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf） 【2】李航，統(tǒng)計(jì)學(xué)習(xí)方法，清華大學(xué)出版社