數據挖掘十大經典算法--CART: 分類與回歸樹
一、決策樹的類型 術語分類和回歸樹 (CART) 包含了上述兩種決策樹, 最先由Breiman 等提出.分類樹和回歸樹有些共同點和不同點—例如處理在何處分裂的問題。
在數據挖掘中，決策樹主要有兩種類型:
分類樹 的輸出是樣本的類標。
回歸樹 的輸出是一個實數 (例如房子的價格，病人呆在醫院的時間等)。
</span>
分類回歸樹(CART,Classification And Regression Tree)也屬于一種決策樹，之前我們介紹了基于ID3和C4.5算法的決策樹。這里只介紹CART是怎樣用于分類的。
分類回歸樹是一棵二叉樹，且每個非葉子節點都有兩個孩子，所以對于第一棵子樹其葉子節點數比非葉子節點數多1。
CART與ID3區別：
CART中用于選擇變量的不純性度量是Gini指數；
如果目標變量是標稱的，并且是具有兩個以上的類別，則CART可能考慮將目標類別合并成兩個超類別（雙化）；
如果目標變量是連續的，則CART算法找出一組基于樹的回歸方程來預測目標變量。
二、構建決策樹
構建決策樹時通常采用自上而下的方法，在每一步選擇一個最好的屬性來分裂。 "最好" 的定義是使得子節點中的訓練集盡量的純。不同的算法使用不同的指標來定義"最好"。本部分介紹一中最常見的指標。
有4中不同的不純度量可以用來發現CART模型的劃分，取決于目標變量的類型，對于分類的目標變量，可以選擇GINI，雙化或有序雙化；
對于連續的目標變量，可以使用最小二乘偏差（LSD）或最小絕對偏差（LAD）。
下面我們只講GINI指數。
GINI指數：
1、是一種不等性度量；
2、通常用來度量收入不平衡，可以用來度量任何不均勻分布；
3、是介于0~1之間的數，0-完全相等，1-完全不相等；
4、總體內包含的類別越雜亂，GINI指數就越大（跟熵的概念很相似）
CART分析步驟
1、從根節點t=1開始，從所有可能候選S集合中搜索使不純性降低最大的劃分S*，然后，使用劃分S*將節點1（t=1）劃分成兩個節點t=2和t=3；
2、在t=2和t=3上分別重復劃分搜索過程。
基尼不純度指標
在CART算法中, 基尼不純度表示一個隨機選中的樣本在子集中被分錯的可能性。基尼不純度為這個樣本被選中的概率乘以它被分錯的概率。當一個節點中所有樣本都是一個類時，基尼不純度為零。
假設y的可能取值為{1, 2, ..., m},令fi是樣本被賦予i的概率，則基尼指數可以通過如下計算：
例如：
上例是屬性有8個，每個屬性又有多少離散的值可取。在決策樹的每一個節點上我們可以按任一個屬性的任一個值進行劃分。比如最開始我們按：
1）表面覆蓋為毛發和非毛發
2）表面覆蓋為鱗片和非鱗片
3）體溫為恒溫和非恒溫
等等產生當前節點的左右兩個孩子。下面我們按GINI指數劃分有：
GINI指數
總體內包含的類別越雜亂，GINI指數就越大（跟熵的概念很相似）。比如體溫為恒溫時包含哺乳類5個、鳥類2個，則：
體溫為非恒溫時包含爬行類3個、魚類3個、兩棲類2個,則
所以如果按照“體溫為恒溫和非恒溫”進行劃分的話，我們得到GINI的增益（類比信息增益）：
最好的劃分就是使得GINI_Gain最小的劃分。
終止條件
一個節點產生左右孩子后，遞歸地對左右孩子進行劃分即可產生分類回歸樹。這里的終止條件是什么？什么時候節點就可以停止分裂了？直觀的情況，當節點包含的數據記錄都屬于同一個類別時就可以終止分裂了。這只是一個特例，更一般的情況我們計算χ2值來判斷分類條件和類別的相關程度，當χ2很小時說明分類條件和類別是獨立的，即按照該分類條件進行分類是沒有道理的，此時節點停止分裂。注意這里的“分類條件”是指按照GINI_Gain最小原則得到的“分類條件”。
假如在構造分類回歸樹的第一步我們得到的“分類條件”是：體溫為恒溫和非恒溫。此時：
三、剪枝
決策樹為什么(WHY)要剪枝？原因是避免決策樹過擬合(Overfitting)樣本。前面的算法生成的決策樹非常詳細并且龐大，每個屬性都被詳細地加以考慮，決策樹的樹葉節點所覆蓋的訓練樣本都是“純”的。因此用這個決策樹來對訓練樣本進行分類的話，你會發現對于訓練樣本而言，這個樹表現完好，誤差率極低且能夠正確得對訓練樣本集中的樣本進行分類。訓練樣本中的錯誤數據也會被決策樹學習，成為決策樹的部分，但是對于測試數據的表現就沒有想象的那么好，或者極差，這就是所謂的過擬合(Overfitting)問題。Quinlan教授試驗，在數據集中，過擬合的決策樹的錯誤率比經過簡化的決策樹的錯誤率要高。
怎么剪枝
現在問題就在于，如何(HOW)在原生的過擬合決策樹的基礎上，生成簡化版的決策樹？可以通過剪枝的方法來簡化過擬合的決策樹。
剪枝可以分為兩種：預剪枝(Pre-Pruning)和后剪枝(Post-Pruning),下面我們來詳細學習下這兩種方法：
PrePrune：預剪枝，及早的停止樹增長，方法可以參考見上面樹停止增長的方法。
PostPrune：后剪枝，在已生成過擬合決策樹上進行剪枝，可以得到簡化版的剪枝決策樹。
其實剪枝的準則是如何確定決策樹的規模，可以參考的剪枝思路有以下幾個：
1：使用訓練集合(Training Set）和驗證集合(Validation Set)，來評估剪枝方法在修剪結點上的效用
2：使用所有的訓練集合進行訓練，但是用統計測試來估計修剪特定結點是否會改善訓練集合外的數據的評估性能，如使用Chi-Square（Quinlan，1986）測試來進一步擴展結點是否能改善整個分類數據的性能，還是僅僅改善了當前訓練集合數據上的性能。
3：使用明確的標準來衡量訓練樣例和決策樹的復雜度，當編碼長度最小時，停止樹增長，如MDL(Minimum Description Length)準則。
1、Reduced-Error Pruning(REP,錯誤率降低剪枝）
該剪枝方法考慮將書上的每個節點作為修剪的候選對象，決定是否修剪這個結點有如下步驟組成：
1：刪除以此結點為根的子樹
2：使其成為葉子結點
3：賦予該結點關聯的訓練數據的最常見分類
4：當修剪后的樹對于驗證集合的性能不會比原來的樹差時，才真正刪除該結點
因為訓練集合的過擬合，使得驗證集合數據能夠對其進行修正，反復進行上面的操作，從底向上的處理結點，刪除那些能夠最大限度的提高驗證集合的精度的結點，直到進一步修剪有害為止(有害是指修剪會減低驗證集合的精度)
REP是最簡單的后剪枝方法之一，不過在數據量比較少的情況下，REP方法趨于過擬合而較少使用。這是因為訓練數據集合中的特性在剪枝過程中被忽略，所以在驗證數據集合比訓練數據集合小的多時，要注意這個問題。
盡管REP有這個缺點，不過REP仍然作為一種基準來評價其它剪枝算法的性能。它對于兩階段決策樹學習方法的優點和缺點提供了了一個很好的學習思路。由于驗證集合沒有參與決策樹的創建，所以用REP剪枝后的決策樹對于測試樣例的偏差要好很多，能夠解決一定程度的過擬合問題。
2、Pessimistic Error Pruning(PEP，悲觀剪枝）
先計算規則在它應用的訓練樣例上的精度，然后假定此估計精度為二項式分布，并計算它的標準差。對于給定的置信區間，采用下界估計作為規則性能的度量。這樣做的結果，是對于大的數據集合，該剪枝策略能夠非常接近觀察精度，隨著數據集合的減小，離觀察精度越來越遠。該剪枝方法盡管不是統計有效的，但是在實踐中有效。
PEP為了提高對測試集合的預測可靠性，PEP對誤差估計增加了連續性校正(Continuity Correction)。PEP方法認為，如果：
成立，則Tt應該被剪枝，
上式中：
其中，e(t)為結點t出的誤差；i為覆蓋Tt的葉子結點；Nt為子樹Tt的葉子樹；n(t)為在結點t處的訓練集合數量。PEP采用自頂向下的方式，如果某個非葉子結點符合上面的不等式，就裁剪掉該葉子結點。該算法被認為是當前決策樹后剪枝算法中經度比較高的算法之一，但是餓存在有缺陷。首先，PEP算法是唯一使用Top-Down剪枝策略，這種策略會導致與先剪枝出現同樣的問題，將該結點的某子節點不需要被剪枝時被剪掉；另外PEP方法會有剪枝失敗的情況出現。
雖然PEP方法存在一些局限性，但是在實際應用中表現出了較高的精度,。兩外PEP方法不需要分離訓練集合和驗證機和，對于數據量比較少的情況比較有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因為在剪枝過程中，樹中的每顆子樹最多需要訪問一次，在最壞的情況下，它的計算時間復雜度也只和非剪枝樹的非葉子節點數目成線性關系。
Cost-Complexity Pruning(CCP、代價復雜度)
CCP方法包含兩個步驟：
1：從原始決策樹T0開始生成一個子樹序列{T0、T1、T2、...、Tn},其中Ti+1是從Ti總產生，Tn為根節點
2：從子樹序列中，根據樹的真實誤差估計選擇最佳決策樹。
對于分類回歸樹中的每一個非葉子節點計算它的表面誤差率增益值α。
是子樹中包含的葉子節點個數;
是節點t的誤差代價，如果該節點被剪枝;
r(t)是節點t的誤差率;
p(t)是節點t上的數據占所有數據的比例。
是子樹Tt的誤差代價，如果該節點不被剪枝。它等于子樹Tt上所有葉子節點的誤差代價之和。
比如有個非葉子節點t4如圖所示：
比如有個非葉子節點t4如圖所示：
已知所有的數據總共有60條，則節點t4的節點誤差代價為：
子樹誤差代價為：
以t4為根節點的子樹上葉子節點有3個，最終：
找到α值最小的非葉子節點，令其左右孩子為NULL。當多個非葉子節點的α值同時達到最小時，取最大的進行剪枝。
來自： http://blog.csdn.net//u011067360/article/details/24871801