人工智慧–CART演算法
人工智慧之CART演算法
前言：人工智慧機器學習有關演算法內容，請參見公眾號「科技優化生活」之前相關文章。人工智慧之機器學習主要有三大類:1)分類;2)回歸;3)聚類。今天我們重點探討一下CART演算法。^_^
繼上兩篇決策樹演算法之ID3演算法[參見人工智慧（41）]和ID3的改進演算法-C4.5演算法[參見人工智慧（42）]後，本文繼續討論另一種二分決策樹演算法-CART演算法。我們知道十大機器學習中決策樹演算法佔有兩席位置，即C4.5演算法和CART演算法，可見CART演算法的重要性。下面重點介紹CART演算法。
不同於ID3與C4.5，CART為一種二分決策樹，是滿二叉樹。CART演算法由Breiman等人在1984年提出，它採用與傳統統計學完全不同的方式構建預測準則，它是以二叉樹的形式給出，易於理解、使用和解釋。由CART模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測準則更加準確，且數據越複雜、變數越多，演算法的優越性就越顯著。
CART演算法既可用於分類也可用於回歸。CART演算法被稱為數據挖掘領域內里程碑式的演算法。
CART演算法概念:
CART(Classification andRegression Tree)分類回歸樹是一種決策樹構建演算法。CART是在給定輸入隨機變數X條件下輸出隨機變數Y的條件概率分布的學習方法。CART假設決策樹是二叉樹，內部結點特徵的取值為「是」和「否」，左分支是取值為「是」的分支，右分支是取值為「否」的分支。這樣的決策樹等價於遞歸地二分每個特徵，將輸入空間即特徵空間劃分為有限個單元，並在這些單元上確定預測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。
CART演算法既可以處理離散型問題，也可以處理連續型問題。這種演算法在處理連續型問題時，主要通過使用二元切分來處理連續型變數，即特徵值大於某個給定的值就走左子樹，或者就走右子樹。
CART演算法組成:
CART演算法組成如下：
1）決策樹生成：基於訓練數據集生成決策樹，生成的決策樹要盡量大；自上而下從根開始建立節點，在每個節點處要選擇一個最好（不同演算法使用不同指標來定義"最好"）的屬性來分裂，使得子節點中的訓練數據集盡量的純。
2）決策樹剪枝：用驗證數據集對已生成的樹進行剪枝並選擇最優子樹，這時損失函數最小作為剪枝的標準。這裡用代價複雜度剪枝CCP（Cost-Complexity Pruning）。
決策樹的生成就是通過遞歸地構建二叉決策樹的過程，對回歸樹用平方誤差最小化準則，對分類樹用基尼指數最小化準則，進行特徵選擇，生成二叉樹。
CART決策樹生成:
1）回歸樹生成
回歸樹採用均方誤差作為損失函數，樹生成時會遞歸的按最優特徵與最優特徵下的最優取值對空間進行劃分，直到滿足停止條件為止，停止條件可以人為設定，比如當切分後的損失減小值小於給定的閾值ε，則停止切分，生成葉節點。對於生成的回歸樹，每個葉節點的類別為落到該葉節點數據的標籤的均值。
回歸樹為一棵二叉樹，每次都是按特徵下的某個取值進行劃分，每一個內部節點都是做一個對應特徵的判斷，直至走到葉節點得到其類別，構建這棵樹的難點在於如何選取最優的切分特徵與切分特徵對應的切分變數。
回歸樹與模型樹既可以處理連續特徵也可以處理離散特徵。
回歸樹生成演算法如下：
輸入：訓練數據集 D={(x1,y1),(x2,y2),…,(xN,yN)}
輸出：回歸樹 T
1）求解選擇切分特徵 j 與切分特徵取值 s ，j 將訓練集 D 劃分為兩部分，R1 與R2 ，依照(j,s)切分後如下：
R1(j,s)= R2(j,s)=
c1=1N1∑xi∈R1yi c2=1N2∑xi∈R2yi
2）遍歷所有可能的解(j,s)，找到最優的 (j*,s*) ，最優的解使得對應損失最小，按照最優特徵(j*,s*)來切分即可。
Min { ∑ (yi–c1)^2 +∑ (yi–c2)^2 }
j,s xi∈R1 xi∈R2
3）遞歸調用 1)和2)，直到滿足停止條件。
4）返回決策樹 T。
回歸樹主要採用了分治策略，對於無法用唯一的全局線性回歸來優化的目標進行分而治之，進而取得比較準確的結果，但分段取均值並不是一個明智的選擇，可以考慮將葉節點設置為一個線性函數，這便是所謂的分段線性模型樹。實驗表明：模型樹效果比回歸樹的效果要好一些。模型樹只需在回歸樹的基礎上稍加修改即可，對於分到葉節點的數據，採用線性回歸的最小均方損失來計算該節點的損失。
2）分類樹生成
分類樹是CART中用來分類的，不同於 ID3 與 C4.5，CART分類樹採用基尼指數來選擇最優的切分特徵，而且每次都是二分。
基尼指數是一個類似與熵的概念，對於一個有 K 種狀態對應的概率為 p1,p2,…,pK的隨機變數 X ，其基尼指數Gini定義如下：
Gini(X)=∑pk(1?pk)=1?∑kp2k
k k
在已知特徵 A條件下集合 D 的基尼指數：
Gini(D,A)=（|D1|/|D|）*Gini(D1)+（|D2|/|D|）*Gini(D2)
Gini(D,A)取值越大，樣本的不確定性也越大，這一點與熵類似，所以選擇特徵 A 的標準是 Gini(D,A) 的取值越小越好。
分類樹生成演算法如下：
輸入：訓練數據集 D={(x1,y1),(x2,y2),…,(xN,yN)}，停止條件
輸出：分類樹 T
1）利用特徵 A 的取值 a 將數據分為兩部分，計算 A=a時的基尼係數：
Gini(D,A)=（|D1|/|D|）*Gini(D1)+（|D2|/|D|）*Gini(D2)
2）對整個數據集中所有的可能特徵 A 以及其可能取值 a 選取基尼係數最小的特徵 A* 與特徵下的取值 a*，來將數據集切分，將數據 D1、D2 分到兩個子節點中去。
3）對子節點遞歸調用 1)和2) ，直至滿足停止條件
4）返回 CART 樹 T
該演算法停止條件可以是節點中的樣本數不能小於給定閾值，或者樣本集的基尼係數小於給定閾值，或者沒有更多的特徵。
3）剪枝
CART需要對生成的樹進行剪枝，避免模型過度擬合訓練數據，剪枝時使用的損失函數如下：
Ca(T)=C(T)+a|T|
C(T)為樹T對訓練數據的誤差，可以用基尼係數或者均方損失來表示，a≥0代表一個權衡訓練數據損失C(T)與總節點數|T|的參數，Ca(T)代表了樹T的整體損失，對於固定的a，一定存在一個確定的使得Ca(T)最小的子樹，當a偏大時，|T|偏小，樹T的規模偏小，反之，樹T的規模偏大，Breiman等人採用遞歸的方法對CART進行剪枝，將a從小增大0=a0
剪枝演算法如下：
輸入：CART 生成樹 T0
輸出：剪枝後的最優樹 T*
1）設 k=0 ， T=T0 ，a=+∞
3) 自下而上的對內部節點 t 計算：
g(t)=[Ct?C(Tt)]/（|Tt|?1）
a=min(a,g(t))
4) 自上而下的訪問內部節點 t ，對最小的 g(t)=a進行剪枝，並對葉節點 t 以多數表決形式決定其類別，得到樹 T
5) k=k+1， ak=a，Tk=T
6) 如果 T 為非單節點樹，回到4)
7) 對於產生的子樹序列 分別計算損失，得到最優子樹 T*並返回.
剪枝後的樹便是所需要的CART決策樹。
CART優點:
1)可以生成可以理解的規則；
2)計算量相對來說不是很大；
3)可以處理連續和種類欄位；
4）決策樹可以清晰的顯示哪些欄位比較重要。
CART缺點:
1)對連續性的欄位比較難預測；
2)對有時間順序的數據，需要很多預處理的工作；
3）當類別太多時，錯誤可能就會增加的比較快；
4）一般的演算法分類的時候，只是根據一個欄位來分類。
CART應用場景：
CART演算法既可以處理離散型問題，也可以處理連續型問題。CART演算法是一種非常有趣且十分有效的非參數分類和回歸方法。它通過構建二叉樹達到預測目的。它已在統計、數據挖掘和機器學習領域中普遍使用，是一種應用廣泛的決策樹演算法。
結語:
CART模型最早由Breiman等人提出，它採用與傳統統計學完全不同的方式構建預測準則，它是以二叉樹形式給出，易於理解、使用和解釋。由CART模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測準則更加準確，且數據越複雜、變數越多，CART演算法優越性就越顯著。模型的關鍵是預測準則的構建。CART演算法在統計、數據挖掘和機器學習等領域得到廣泛應用。
------以往文章推薦------
TAG:科技優化生活 |