轉自https://www.cnblogs.com/wxquare/p/5379970.html，增加了少量内容
決策樹模型在監督學習中非常常見，可用于分類（二分類、多分類）和回歸。雖然将多棵弱決策樹的Bagging、Random Forest、Boosting等tree ensembel 模型更為常見，但是“完全生長”決策樹因為其簡單直覺，具有很強的解釋性，也有廣泛的應用，而且決策樹是tree ensemble 的基礎，值得好好了解。一般而言一棵“完全生長”的決策樹包含，特征選擇、決策樹建構、剪枝三個過程，這篇文章主要是簡單梳理比較ID3、C4.5、CART算法。《統計學習方法》中有比較詳細的介紹。
一、決策樹的優點和缺點（轉自：http://blog.csdn.net/gamer_gyt/article/details/51226904）
優點
1：了解和解釋起來簡單，且決策樹模型可以想象
2：需要準備的資料量不大，而其他的技術往往需要很大的資料集，需要建立虛拟變量，去除不完整的資料，但是該算法對于丢失的資料不能進行準确的預測
3：決策樹算法的時間複雜度(即預測資料)是用于訓練決策樹的資料點的對數
4：能夠處理數字和資料的類别（需要做相應的轉變），而其他算法分析的資料集往往是隻有一種類型的變量
5：能夠處理多輸出的問題
6：使用白盒模型，如果給定的情況是在一個模型中觀察到的，該條件的解釋很容易解釋的布爾邏輯，相比之下，在一個黑盒子模型（例如人工神經網絡），結果可能更難以解釋
7：可能使用統計檢驗來驗證模型，這是為了驗證模型的可靠性
8：從資料結果來看，它執行的效果很好，雖然它的假設有點違反真實模型
缺點：
1：決策樹算法學習者可以建立複雜的樹，但是沒有推廣依據，這就是所謂的過拟合，為了避免這種問題，出現了剪枝的概念，即設定一個葉子結點所需要的最小數目或者設定樹的最大深度
2：決策樹的結果可能是不穩定的，因為在資料中一個很小的變化可能導緻生成一個完全不同的樹，這個問題可以通過使用內建決策樹來解決
3：衆所周知，學習一惡搞最優決策樹的問題是NP——得到幾方面完全的優越性，甚至是一些簡單的概念。是以，實際決策樹學習算法是基于啟發式算法，如貪婪算法，尋求在每個節點上的局部最優決策。這樣的算法不能保證傳回全局最優決策樹。這可以減輕訓練多棵樹的合奏學習者，在那裡的功能和樣本随機抽樣更換。
4：這裡有一些概念是很難的了解的，因為決策樹本身并不難很輕易的表達它們，比如說異或校驗或複用的問題。
5：決策樹學習者很可能在某些類占主導地位時建立有有偏異的樹，是以建議用平衡的資料訓練決策樹
二、ID3算法
ID3由Ross Quinlan在1986年提出。ID3決策樹可以有多個分支，但是不能處理特征值為連續的情況。決策樹是一種貪心算法，每次選取的分割資料的特征都是目前的最佳選擇，并不關心是否達到最優。在ID3中，每次根據“最大資訊熵增益”選取目前最佳的特征來分割資料，并按照該特征的所有取值來切分，也就是說如果一個特征有4種取值，資料将被切分4份，一旦按某特征切分後，該特征在之後的算法執行中，将不再起作用，是以有觀點認為這種切分方式過于迅速。ID3算法十分簡單，核心是根據“最大資訊熵增益”原則選擇劃分目前資料集的最好特征，資訊熵是資訊論裡面的概念，是資訊的度量方式，不确定度越大或者說越混亂，熵就越大。在建立決策樹的過程中，根據特征屬性劃分資料，使得原本“混亂”的資料的熵(混亂度)減少，按照不同特征劃分資料熵減少的程度會不一樣。在ID3中選擇熵減少程度最大的特征來劃分資料（貪心），也就是“最大資訊熵增益”原則。下面是計算公式，建議看連結計算資訊上增益的執行個體。
三、C4.5算法
C4.5是Ross Quinlan在1993年在ID3的基礎上改進而提出的。針對ID3采用的資訊增益度量存在一個缺點，它一般會優先選擇有較多屬性值的Feature,因為屬性值多的Feature會有相對較大的資訊增益(資訊增益反映的給定一個條件以後不确定性減少的程度,必然是分得越細的資料集确定性更高,也就是條件熵越小,資訊增益越大)。當一個屬性的可取值數目較多時，那麼可能在這個屬性對應的可取值下的樣本隻有一個或者是很少個，那麼這個時候它的資訊增益是非常高的，這個時候純度很高，ID3決策樹會認為這個屬性很适合劃分，但是較多取值的屬性來進行劃分帶來的問題是它的泛化能力比較弱，不能夠對新樣本進行有效的預測。為了避免這個不足，C4.5中是用資訊增益比率(gain ratio)來作為選擇分支的準則。資訊增益比率通過引入一個被稱作分裂資訊(Split information)的項來懲罰取值較多的Feature，在候選屬性中選擇基尼系數最小的屬性作為最優劃分屬性。除此之外，C4.5還彌補了ID3中不能處理特征屬性值連續的問題。但是，對連續屬性值需要掃描排序，會使C4.5性能下降，有興趣可以參考部落格
Split information為屬性A的在D資訊熵（注意不是Di）。
五、CART算法
CART（Classification and Regression tree）分類回歸樹由L.Breiman,J.Friedman,R.Olshen和C.Stone于1984年提出。ID3中根據屬性值分割資料，之後該特征不會再起作用，這種快速切割的方式會影響算法的準确率。CART是一棵二叉樹，采用二進制切分法，每次把資料切成兩份，分别進入左子樹、右子樹。而且每個非葉子節點都有兩個孩子，是以CART的葉子節點比非葉子多1。相比ID3和C4.5，CART應用要多一些，既可以用于分類也可以用于回歸。CART分類時，使用基尼指數（Gini）來選擇最好的資料分割的特征，gini描述的是純度，與資訊熵的含義相似。CART中每一次疊代都會降低GINI系數。當CART是分類樹時，采用GINI值作為節點分裂的依據；當CART是回歸樹時，采用樣本的最小方差作為節點分裂的依據。下圖顯示資訊熵增益的一半，Gini指數，分類誤差率三種評價名額非常接近。回歸時使用均方差作為loss function。基尼系數的計算與資訊熵增益的方式非常類似，公式如下
六、分類樹 VS 回歸樹
提到決策樹算法，很多想到的就是上面提到的ID3、C4.5、CART分類決策樹。其實決策樹分為分類樹和回歸樹，前者用于分類，如晴天/陰天/雨天、使用者性别、郵件是否是垃圾郵件，後者用于預測實數值，如明天的溫度、使用者的年齡等。
作為對比，先說分類樹，我們知道ID3、C4.5分類樹在每次分枝時，是窮舉每一個特征屬性的每一個門檻值，找到使得按照feature<=門檻值，和feature>門檻值分成的兩個分枝的熵最大的feature和門檻值。以性别為例，按照該标準分枝得到兩個新節點，用同樣方法繼續分枝直到所有人都被分入性别唯一的葉子節點，或達到預設的終止條件，若最終葉子節點中的性别不唯一，則以多數人的性别作為該葉子節點的性别。
回歸樹總體流程也是類似，不過在每個節點（不一定是葉子節點）都會得一個預測值，以年齡為例，該預測值等于屬于這個節點的所有人年齡的平均值。分枝時窮舉每一個feature的每個門檻值找最好的分割點，但衡量最好的标準不再是最大熵，而是最小化均方差--即（每個人的年齡-預測年齡）^2 的總和 / N，或者說是每個人的預測誤差平方和 除以 N。這很好了解，被預測出錯的人數越多，錯的越離譜，均方差就越大，通過最小化均方差能夠找到最靠譜的分枝依據。分枝直到每個葉子節點上人的年齡都唯一（這太難了）或者達到預設的終止條件（如葉子個數上限），若最終葉子節點上人的年齡不唯一，則以該節點上所有人的平均年齡做為該葉子節點的預測年齡。
七，其他總結
決策樹再選擇特征值的計算（資訊熵、資訊增益比）都不能得到全局最小（大），但是決策樹類善于解決非線性問題。
ID3，C4.5隻能處理分類問題。C4.5能處理連續性資料，将連續性資料轉化為離散型資料。
ID3，C4.5再疊代建立樹節點時，每個特征隻能出現一次，但CART可以出現多次，這也是為什麼CART能夠進行回歸。