數(shù)據(jù)挖掘十大算法之CART詳解

CART生成

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

CART算法由以下兩步組成：

決策樹生成：基于訓練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大；

決策樹剪枝：用驗證數(shù)據(jù)集對已生成的樹進行剪枝并選擇最優(yōu)子樹，這時損失函數(shù)最小作為剪枝的標準。

CART決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。CART決策樹既可以用于分類也可以用于回歸。本文我們僅討論用于分類的CART。對分類樹而言，CART用Gini系數(shù)最小化準則來進行特征選擇，生成二叉樹。 CART生成算法如下：

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

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

設結(jié)點的訓練數(shù)據(jù)集為D，計算現(xiàn)有特征對該數(shù)據(jù)集的Gini系數(shù)。此時，對每一個特征A，對其可能取的每個值a，根據(jù)樣本點對A=a的測試為“是”或 “否”將D分割成D1和D2兩部分，計算A=a時的Gini系數(shù)。

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

對兩個子結(jié)點遞歸地調(diào)用步驟l~2，直至滿足停止條件。

生成CART決策樹。

算法停止計算的條件是結(jié)點中的樣本個數(shù)小于預定閾值，或樣本集的Gini系數(shù)小于預定閾值（樣本基本屬于同一類），或者沒有更多特征。

一個具體的例子

下面來看一個具體的例子。我們使用《數(shù)據(jù)挖掘十大算法之決策樹詳解（1）》中圖4-6所示的數(shù)據(jù)集來作為示例，為了便于后面的敘述，我們將其再列出如下：

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

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

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

{married} | {single,divorced}

{single} | {married,divorced}

{divorced} | {single,married}

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

對比計算結(jié)果，根據(jù)婚姻狀況屬性來劃分根節(jié)點時取Gini系數(shù)增益最大的分組作為劃分結(jié)果，也就是{married} | {single,divorced}。

最后考慮年收入屬性，我們發(fā)現(xiàn)它是一個連續(xù)的數(shù)值類型。我們在前面的文章里已經(jīng)專門介紹過如何應對這種類型的數(shù)據(jù)劃分了。對此還不是很清楚的朋友可以參考之前的文章，這里不再贅述。

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

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

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

接下來，采用同樣的方法，分別計算剩下屬性，其中根節(jié)點的Gini系數(shù)為（此時是否拖欠貸款的各有3個records） 

與前面的計算過程類似，對于是否有房屬性，可得 

對于年收入屬性則有：

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

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

C4.5采用信息增益率來作為分支特征的選擇標準，而CART則采用Gini系數(shù)；

C4.5不一定是二叉樹，但CART一定是二叉樹。

決策樹很容易發(fā)生過擬合，也就是由于對train數(shù)據(jù)集適應得太好，反而在test數(shù)據(jù)集上表現(xiàn)得不好。這個時候我們要么是通過閾值控制終止條件避免樹形結(jié)構(gòu)分支過細，要么就是通過對已經(jīng)形成的決策樹進行剪枝來避免過擬合。另外一個克服過擬合的手段就是基于Bootstrap的思想建立隨機森林（Random Forest）。