决策树-基于不同算法的决策树模型对比
? ? ? ?決策樹是一個樹結構（可以是二叉樹或非二叉樹），其每個非葉節點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節點存放一個輸出類別。使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。
決策樹學習通常包含這幾個方面：特征選擇、決策樹生成、決策樹剪枝、缺失值/異常值處理、決策樹集成學習。
決策樹-特征屬性選擇劃分
決策樹-缺失值和連續值處理及屬性劃分
決策樹-不同的決策樹模型對比
決策樹-避免過擬合預剪枝和后剪枝對比區別
決策樹-算法小結及常見問題
? ??
本節目錄
ID3算法
C4.5算法的改進
CART分類樹算法
ID3算法
ID3算法就是用信息增益大小來判斷當前節點應該用什么特征來構建決策樹，用計算出的信息增益最大的特征來建立決策樹的當前節點。
決策樹ID3算法的不足：
ID3算法雖然提出了新思路，但是還是有很多值得改進的地方。
ID3 算法的作者昆蘭基于上述不足，對ID3算法做了改進，這就是C4.5算法，也許你會問，為什么不叫ID4，ID5之類的名字呢?那是因為決策樹太火爆，他的ID3一出來，別人二次創新，很快就占了ID4， ID5，所以他另辟蹊徑，取名C4.0算法，后來的進化版為C4.5算法。
?
C4.5算法的改進
ID3算法有四個主要的不足，
（1）不能處理連續特征；
（2）使用信息增益作為標準容易偏向于取值較多的特征；
（3）缺失值處理問題；
（4）過擬合問題；
昆蘭在C4.5算法中改進了上述4個問題。
（1）對于第一個問題，不能處理連續特征?C4.5的思路是將連續的特征離散化。
比如m個樣本的連續特征A有m個，從小到大排列為a1，a2，...，am個，則C4.5取相鄰兩樣本值的中位數，一共取得m-1個劃分點，其中第i個劃分點Ti表示Ti表示為（ai+ai+1）/ 2?。
對于這m-1個點，分別計算以該點作為二元分類點時的信息增益。選擇信息增益最大的點作為該連續特征的二元離散分類點。
比如取到的增益最大的點為at,則小于at的值為類別1，大于at的值為類別2，這樣我們就做到了連續特征的離散化。要注意的是，與離散屬性不同的是，如果當前節點為連續屬性，則該屬性后面還可以參與子節點的產生選擇過程。
?
（2）對于第二個問題，信息增益作為標準容易偏向于取值較多的特征的問題
我們引入一個信息增益比的變量IR(X,Y)，它是信息增益和特征熵的比值。表達式如下：
其中D為樣本特征輸出的集合，A為樣本特征，對于特征熵HA(D),?表達式如下：
其中n為特征A的類別數，?Di為特征A的第i個取值對應的樣本個數。D為樣本個數。特征數越多的特征對應的特征熵越大，它作為分母，可以校正信息增益容易偏向于取值較多的特征的問題。
?
（3）對于第三個缺失值處理的問題
主要需要解決的是兩個問題，一是在樣本某些特征缺失的情況下選擇劃分的屬性，二是選定了劃分屬性，對于在該屬性上缺失特征的樣本的處理。
對于第一個子問題，對于某一個有缺失特征值的特征A。C4.5的思路是將數據分成兩部分，對每個樣本設置一個權重（初始可以都為1），然后劃分數據，一部分是有特征值A的數據D1，另一部分是沒有特征A的數據D2. 然后對于沒有缺失特征A的數據集D1來和對應的A特征的各個特征值一起計算加權重后的信息增益比，最后乘上一個系數，這個系數是無特征A缺失的樣本加權后所占加權總樣本的比例。
對于第二個子問題，可以將缺失特征的樣本同時劃分入所有的子節點，不過將該樣本的權重按各個子節點樣本的數量比例來分配。比如缺失特征A的樣本a之前權重為1，特征A有3個特征值A1,A2,A3。 3個特征值對應的無缺失A特征的樣本個數為2,3,4.則a同時劃分入A1，A2，A3。對應權重調節為2/9,3/9, 4/9。
?
（4）對于第4個問題，C4.5引入了正則化系數進行初步的剪枝。具體方法這里不討論。下篇講CART的時候會詳細討論剪枝的思路。
除了上面的4點，C4.5和ID3的思路區別不大。
?
決策樹C4.5算法的不足與思考
這4個問題在CART樹里面部分加以了改進。所以目前如果不考慮集成學習話，在普通的決策樹算法里，CART算法算是比較優的算法了，scikit-learn的決策樹使用的也是CART算法。
我們講到了決策樹里ID3算法，和ID3算法的改進版C4.5算法。對于C4.5算法，我們也提到了它的不足，比如模型是用較為復雜的熵來度量，使用了相對較為復雜的多叉樹，只能處理分類不能處理回歸等。對于這些問題， CART算法大部分做了改進。
CART算法也就是我們下面的重點了。由于CART算法可以做回歸，也可以做分類，我們分別加以介紹，先從CART分類樹算法開始，重點比較和C4.5算法的不同點。接著介紹CART回歸樹算法，重點介紹和CART分類樹的不同點。然后我們討論CART樹的建樹算法和剪枝算法，最后總結決策樹算法的優缺點。
?
CART分類樹算法
我們知道，在ID3算法中我們使用了信息增益來選擇特征，信息增益大的優先選擇。在C4.5算法中，采用了信息增益比來選擇特征，以減少信息增益容易選擇特征值多的特征的問題。
但是無論是ID3還是C4.5,都是基于信息論的熵模型的，這里面會涉及大量的對數運算。（多叉樹問題，在CART中只構建二叉樹）能不能簡化模型同時也不至于完全丟失熵模型的優點呢？有！CART分類樹算法使用基尼系數來代替信息增益比，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特征越好。這和信息增益(比)是相反的。
具體的，在分類問題中，假設有K個類別，第k個類別的概率為pk, 則基尼系數的表達式為：
如果是二類分類問題，計算就更加簡單了，如果屬于第一個樣本輸出的概率是p，則基尼系數的表達式為：
對于個給定的樣本D,假設有K個類別, 第k個類別的數量為Ck,則樣本D的基尼系數表達式為：
特別的，對于樣本D,如果根據特征A的某個值a,把D分成D1和D2兩部分，則在特征A的條件下，D的基尼系數表達式為：
大家可以比較下基尼系數表達式和熵模型的表達式，二次運算是不是比對數簡單很多？尤其是二類分類的計算，更加簡單。但是簡單歸簡單，和熵模型的度量方式比，基尼系數對應的誤差有多大呢？對于二類分類，基尼系數和熵之半的曲線如下：
從上圖可以看出，基尼系數和熵之半的曲線非常接近，僅僅在45度角附近誤差稍大。因此，基尼系數可以做為熵模型的一個近似替代。而CART分類樹算法就是使用的基尼系數來選擇決策樹的特征。
同時，為了進一步簡化，CART分類樹算法每次僅僅對某個特征的值進行二分，而不是多分，這樣CART分類樹算法建立起來的是二叉樹，而不是多叉樹。這樣一可以進一步簡化基尼系數的計算，二可以建立一個更加優雅的二叉樹模型。
?
CART分類樹算法對于連續特征和離散特征處理的改進
對于CART分類樹連續值的處理問題，其思想和C4.5是相同的，都是將連續的特征離散化。唯一的區別在于在選擇劃分點時的度量方式不同，C4.5使用的是信息增益，則CART分類樹使用的是基尼系數。
具體的思路如下，比如m個樣本的連續特征A有m個，從小到大排列為a1,a2,...,am,則CART算法取相鄰兩樣本值的中位數，一共取得m-1個劃分點，其中第i個劃分點Ti表示Ti表示為：( ai+ai+1 ) / 2
對于這m-1個點，分別計算以該點作為二元分類點時的基尼系數。選擇基尼系數最小的點作為該連續特征的二元離散分類點。比如取到的基尼系數最小的點為at,則小于at的值為類別1，大于at的值為類別2，這樣我們就做到了連續特征的離散化。要注意的是，與離散屬性不同的是，如果當前節點為連續屬性，則該屬性后面還可以參與子節點的產生選擇過程。
對于CART分類樹離散值的處理問題，采用的思路是不停的二分離散特征。
回憶下ID3或者C4.5，如果某個特征A被選取建立決策樹節點，如果它有A1,A2,A3三種類別，我們會在決策樹上一下建立一個三叉的節點。這樣導致決策樹是多叉樹。但是CART分類樹使用的方法不同，他采用的是不停的二分，還是這個例子，CART分類樹會考慮把A分成{A1}和{A2,A3}，{A2}和{A1,A3}?，{A3}和{A1,A2}三種情況，找到基尼系數最小的組合，比如{A2}和{A1,A3},然后建立二叉樹節點，一個節點是A2對應的樣本，另一個節點是{A1,A3}對應的節點。從描述可以看出，如果離散特征A有n個取值，則可能的組合有n(n-1)/2種。同時，由于這次沒有把特征A的取值完全分開，后面我們還有機會在子節點繼續選擇到特征A來劃分A1和A3。這和ID3或者C4.5不同，在ID3或者C4.5的一棵子樹中，離散特征只會參與一次節點的建立。
?
CART分類樹建立算法的具體流程
上面介紹了CART算法的一些和C4.5不同之處，下面我們看看CART分類樹建立算法的具體流程，之所以加上了建立，是因為CART樹算法還有獨立的剪枝算法這一塊，算法輸入是訓練集D，基尼系數的閾值，樣本個數閾值，輸出是決策樹T。
我們的算法從根節點開始，用訓練集遞歸的建立CART樹。
1) 對于當前節點的數據集為D，如果樣本個數小于閾值或者沒有特征，則返回決策子樹，當前節點停止遞歸。
2) 計算樣本集D的基尼系數，如果基尼系數小于閾值，則返回決策樹子樹，當前節點停止遞歸。
3) 計算當前節點現有的各個特征的各個特征值對數據集D的基尼系數，缺失值的處理方法和上篇的C4.5算法里描述的相同。
4) 在計算出來的各個特征的各個特征值對數據集D的基尼系數中，選擇基尼系數最小的特征A和對應的特征值a。根據這個最優特征和最優特征值，把數據集劃分成兩部分D1和D2，同時建立當前節點的左右節點，做節點的數據集D為D1，右節點的數據集D為D2.
5) 對左右的子節點遞歸的調用1-4步，生成決策樹。
對于生成的決策樹做預測的時候，假如測試集里的樣本A落到了某個葉子節點，而節點里有多個訓練樣本。則對于A的類別預測采用的是這個葉子節點里概率最大的類別。
?
CART回歸樹建立算法的具體流程
CART回歸樹和CART分類樹的建立算法大部分是類似的，所以這里我們只討論CART回歸樹和CART分類樹的建立算法不同的地方。
首先，我們要明白，什么是回歸樹，什么是分類樹。兩者的區別在于樣本輸出，如果樣本輸出是離散值，那么這是一顆分類樹。如果果樣本輸出是連續值，那么這是一顆回歸樹。
除了概念的不同，CART回歸樹和CART分類樹的建立和預測的區別主要有下面兩點：
1)連續值的處理方法不同
2)決策樹建立后做預測的方式不同。
?對于連續值的處理，我們知道CART分類樹采用的是用基尼系數的大小來度量特征的各個劃分點的優劣情況。這比較適合分類模型，但是對于回歸模型，我們使用了常見的均方差的度量方式，CART回歸樹的度量目標是，對于任意劃分特征A，對應的任意劃分點s兩邊劃分成的數據集D1和D2，求出使D1和D2各自集合的均方差最小，同時D1和D2的均方差之和最小所對應的特征和特征值劃分點。
其中，c1為D1數據集的樣本輸出均值，c2為D2數據集的樣本輸出均值。
對于決策樹建立后做預測的方式，上面講到了CART分類樹采用葉子節點里概率最大的類別作為當前節點的預測類別。而回歸樹輸出不是類別，它采用的是用最終葉子的均值或者中位數來預測輸出結果。
除了上面提到了以外，CART回歸樹和CART分類樹的建立算法和預測沒有什么區別。
?
CART樹算法的剪枝
CART回歸樹和CART分類樹的剪枝策略除了在度量損失的時候一個使用均方差，一個使用基尼系數，算法基本完全一樣，這里我們一起來講。
由于決策時算法很容易對訓練集過擬合，而導致泛化能力差，為了解決這個問題，我們需要對CART樹進行剪枝，即類似于線性回歸的正則化，來增加決策樹的返回能力。但是，有很多的剪枝方法，我們應該這么選擇呢？CART采用的辦法是后剪枝法，即先生成決策樹，然后產生所有可能的剪枝后的CART樹，然后使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝策略。
也就是說，CART樹的剪枝算法可以概括為兩步，第一步是從原始決策樹生成各種剪枝效果的決策樹，第二部是用交叉驗證來檢驗剪枝后的預測能力，選擇泛化預測能力最好的剪枝后的數作為最終的CART樹。
首先我們看看剪枝的損失函數度量，在剪枝的過程中，對于任意的一刻子樹T，其損失函數為：
其中，α為正則化參數，這和線性回歸的正則化一樣。C(Tt)為訓練數據的預測誤差，分類樹是用基尼系數度量，回歸樹是均方差度量。|Tt|是子樹T的葉子節點的數量。
當α=0時，即沒有正則化，原始的生成的CART樹即為最優子樹。當α=∞時，即正則化強度達到最大，此時由原始的生成的CART樹的根節點組成的單節點樹為最優子樹。當然，這是兩種極端情況。一般來說，α越大，則剪枝剪的越厲害，生成的最優子樹相比原生決策樹就越偏小。對于固定的α，一定存在使損失函數Cα(T)最小的唯一子樹。
?
上面我們對CART算法做了一個詳細的介紹，CART算法相比C4.5算法的分類方法，采用了簡化的二叉樹模型，同時特征選擇采用了近似的基尼系數來簡化計算。當然CART樹最大的好處是還可以做回歸模型，這個C4.5沒有。下表給出了ID3，C4.5和CART的一個比較總結。希望可以幫助大家理解。
看起來CART算法高大上，那么CART算法還有沒有什么缺點呢？有！主要的缺點我認為如下：
1）應該大家有注意到，無論是ID3, C4.5還是CART,在做特征選擇的時候都是選擇最優的一個特征來做分類決策，但是大多數，分類決策不應該是由某一個特征決定的，而是應該由一組特征決定的。這樣絕息到的決策樹更加準確。
這個決策樹叫做多變量決策樹(multi-variate decision tree)。在選擇最優特征的時候，多變量決策樹不是選擇某一個最優特征，而是選擇最優的一個特征線性組合來做決策。這個算法的代表是OC1，這里不多介紹。
2）如果樣本發生一點點的改動，就會導致樹結構的劇烈改變。這個可以通過集成學習里面的隨機森林之類的方法解決。
?
?
?
總結
以上是生活随笔為你收集整理的决策树-基于不同算法的决策树模型对比的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 决策树-特征属性选择划分
- 下一篇： 决策树-缺失值和连续值处理及属性划分