決策樹-CART演算法
總第80篇
01前言：
02CART的生成：
決策樹的生成就是遞歸地構建二叉決策樹的過程。對回歸樹用平方差最小化準則，對分類樹用基尼指數最小化準則，進行特徵選擇，生成二叉樹。
分類樹與回歸樹的一個區別是：如果目標變數是離散型變數則用分類樹，如果目標變數是連續型變數則用回歸樹。
2.1回歸樹的生成
回歸樹是用於目標變數是連續型變數的情況下，假設X與Y分別為輸入和輸出變數，並且Y是連續型變數，給定數據即D={(x1,y1),(x2,y2),...(xn,yn)}，根據訓練數據集D生成決策樹。
前面說過，回歸樹的生成準則是平方差(總離差平方和：實際觀察值與一般水平即均值的離差總和)最小化準則，即預測誤差最小化，所以我們的目的就是找到一個分界點，以這個點作為分界線將訓練集D分成兩部分D1和D2，並且使數據集D1和D2中各自的平方差最小。然後然後再分別再D1和D2中找類似的分界點，繼續循環，直到滿足終止條件。
在具體找分解值的時候採用遍歷所有變數的方法，依次計算平方差，選擇平方差最小時對應的分解值。
2.2分類樹的生成
分類樹用基尼指數選擇最優特徵(與信息增益類似)，同時決定該特徵的最優二值切分點。
2.2.1基尼指數
分類問題中，假設有K個類，樣本點屬於第k類的概率為pk，則概率分布的基尼指數定義為：
對於二分類問題，若樣本點屬於第一類的概率為p，則概率分布的基尼指數為：Gini(p)=2p(1-p)。
對於樣本給定的集合D，其基尼指數為：Gini(D)=1-∑(Ck/D)*2，這裡Ck是D中屬於第k類的樣本子集，K是類的個數。
條件基尼指數：
上面公式表示在特徵A的條件下，集合D的基尼指數，其中D1和D2表示樣本集合D根據特徵A是否取某一個可能值a被分割成的兩部分。
基尼指數Gini(D)表示集合D的不確定性，基尼指數Gini(D,A)表示經A=a分割後集合D的不確定性。基尼指數數值越大，樣本集合的不確定性越大。
2.2.2演算法步驟
輸入：訓練數據集D，停止計算的條件
輸出：CART決策樹
根據訓練數據集，從根節點開始，遞歸地對每個結點進行以下操作，構建二叉決策樹：
設結點的訓練數據集為D，計算現有特徵對該數據集的基尼指數，此時，對每一個特徵A，對其可能取的每一個值a,根據樣本點A=a的測試為「是」或「否」將D分割成D1和D2兩部分，然後計算Gini(D,A)。
在所有可能的特徵A以及他們所有可能的切分點a中，選擇基尼指數最小的特徵及其對應的切分點作為最優特徵與最佳切分點。依最優特徵與最優切分點，從現結點生成兩個子節點，將訓練數據集依特徵分配到兩個子節點中去。
對兩個子節點遞歸調用.1，.2，直至滿足停止條件。
生成CART決策樹。
演算法停止計算的條件是結點中的樣本個數小於預定的閾值，或樣本集的基尼指數小於預定的閾值（樣本基本屬於同一類），或者沒有更多特徵。
03CART剪枝：
我們再前面那一章節提過剪枝是為了避免數據發生過擬合現象，而避免這種情況發生的方法就是使損失函數最小化。
先看看損失函數的公式：
在α已知得情況下，要使上面得Cα(T)最小，就需要使T最小，即子樹得葉節點數量最小；或者使訓練誤差最小，要使訓練誤差最小，就需要再引入新的特徵，這樣更會增加樹得複雜度。所以我們主要通過降低T來降低損失函數，而這主要是通過剪去一些不必要得枝得到得。
但是在具體剪得過程中，我們需要有一個評判標準用來判斷哪些枝可以剪，哪些使不可以剪得。而這個評判標準就是剪枝前後該樹得損失函數是否減少，如果減小，就對該枝進行剪枝。
具體地，從整數T0開始剪枝，對T0的任意內部節點t，以t為單結點樹(即該樹沒有葉節點)的損失函數是：Cα(t)=C(t)+α
以t為根節點的子樹Tt的損失函數是：Cα(Tt)=C(Tt)+αTt
當α=0或者充分小，有不等式：
當α繼續增大時，在某一α處會有：
當α再繼續增大時，在某一α處會有：
當下式成立時:
在這個時候，Tt與t有相同的損失函數值，而t的結點少，因此t比Tt更可取，對Tt進行剪枝。
為此，可以對T0中的每一內部節點t，計算g(t)=(C(t)-C(Tt))/(Tt-1)，該式表示剪枝後整體損失函數減少的程度。在T0中剪去g(t)最小的Tt,將得到的子樹作為T1，同時將最小的g(t)設為α1.T1為區間最小[α1,α2)的最優子數。如此剪枝下去，直至得到根節點，在這一過程中不斷增加α的值，產生新的區間。
在剪枝得到的子樹序列T0，T1，...，Tn中獨立驗證數據集，測試子樹序列的T0，T1，...，Tn中各顆子樹的平方誤差或基尼指數。平方誤差或基尼指數最小的決策樹被認為是最優的決策樹。
3.1演算法步驟：
輸入：CART演算法生成的決策樹T0
輸出：最優決策樹Tα
設k=0,T=T0
設α=+∞
自上而下地對各內部節點t計算C(Tt)，Tt以及g(t)，這裡，Tt表示以t為根節點的子樹，C(Tt)是對訓練數據的預測誤差。Tt是Tt的葉結點個數。
對g(t)=α的內部結點t進行剪枝，並對葉節點t以多數表決法決定其類得到樹T。
設k=k+1，αk=α,Tk=T。
如果Tk不是由根節點及兩個葉節點構成的樹，則回到步驟(3)；否則令Tk=Tn。
採用交叉驗證法在子樹序列T0，T1，...，Tn中選取最優子樹Tα。
PS時刻：
本次無代碼實現階段，日後補上。
TAG:張俊紅 |