『壹』 決策樹之CART演算法
一、基本概念
1.cart使用基尼系數作為劃分標准。基尼系數越小，則不純度越低，區分的越徹底。
2.假設有k個類別，第k個類別的概率為 ,則基尼系數表達式為：
Gini(p)= (1- )=1-
3.對於樣本D，如果根據特徵A 的值把樣本分為D1,D2兩部分，則在特徵A條件下，D的基尼系數
Gini(D,A)= Gini(D1)+ Gini(D2)
4.CART建立起來的是二叉樹，如果特徵A有A1,A2，A3三個類別，CART會考慮把A分成{A1},{A2 ,A3}兩組，或者是其他兩種情況。由於這次A並沒有完全分開，所以下次還有機會在子節點把A2,A3分開.
5.對於連續值的切分.假如有1 2 3 4 5 那麼cart會有4個切分點 [1.5 2.5 3.5 4.5]
二.實例推導樹的建立過程
1.假設我有以下源數據
序號 天氣 周末 促銷 銷量
1 壞 是 是 高
2 壞 是 是 高
3 壞 是 是 高
4 壞 否 是 高
5 壞 是 是 高
6 壞 否 是 高
7 壞 是 否 高
8 好 是 是 高
9 好 是 否 高
10 好 是 是 高
11 好 是 是 高
12 好 是 是 高
13 好 是 是 高
14 壞 是 是 低
15 好 否 是 高
16 好 否 是 高
17 好 否 是 高
18 好 否 是 高
19 好 否 否 高
20 壞 否 否 低
21 壞 否 是 低
22 壞 否 是 低
23 壞 否 是 低
24 壞 否 否 低
25 壞 是 否 低
26 好 否 是 低
27 好 否 是 低
28 壞 否 否 低
29 壞 否 否 低
30 好 否 否 低
31 壞 是 否 低
32 好 否 是 低
33 好 否 否 低
34 好 否 否 低
該數據集有三個特徵 天氣 周末 促銷
2.為了簡化建立樹的過程,我將忽略基尼系數與樣本個數閥值
2.1 首先計算各個特徵值對數據集的基尼系數,公式見---- 基本概念.3
Gini(D|天氣)=17/34*(1-(11/17)^2-(6/17)^2)+17/34*(1-(7/17)^2-(10/17)^2)=0.4706
Gini(D|周末)=20/34*(1-(7/20)^2-(13/20)^2)+14/34*(1-(11/14)^2-(3/14)^2)=0.4063
Gini(D|促銷)=12/34*(1-(9/12)^2-(3/12)^2)+22/34*(1-(7/22)^2-(15/22)^2)=0.4131
周末的基尼系數最小，這也符合我們的一般認識
2.2 第一個分列特徵選擇周末。此時數據集按照是否周末分成兩個。
Gini(周末|天氣)=0.2679
Gini(周末|促銷)=0.2714
Gini(非周末|天氣)=0.3505
Gini(非周末|促銷)=0.3875
此時，周末應該以天氣作為劃分，非周末也是以天氣作為劃分，下面放個圖
三、CART樹對於連續特徵的處理
假如特徵A為連續型變數，則把特徵A按照從小到大進行排序，取相鄰兩點的平均值為切分點，計算基尼系數。則基尼系數最小的點為切分點，大於切分點的為一類，小於切分點的為另一類。舉例：特徵A的值為 1，2，3，4，5，6 目標變數是高、低、高、低、高、低。則1.5處的基尼系數為 (1/6)*(1-1^2)+(5/6)*(1-(2/5)^2-(3/5)^2)=0.4 2.5處的基尼系數為 (2/6)*(1-(1/2)^2-(1/2)^2)+(4/6)*(1-(2/4)^2-(2/4)^2)=0.5 3.5處的基尼系數為 (3/6)*(1-(1/3)^2-(2/3)^2)+(3/6)*(1-(1/3)^2-(2/3)^2)=0.44 4.5處的基尼系數為 (4/6)*(1-(2/4)^2-(2/4)^2)+(2/6)*(1-(1/2)^2-(1/2)^2)=0.5 5.5處的基尼系數為 (5/6)*(1-(2/5)^2-(3/5)^2)+(1/6)*(1-1^2)=0.4 結論： 1.5和5.5處的基尼系數最小，可以把1分為一類，2-6分為另一類。或者6分為一類，1-5另一類。
四、關於回歸樹
1.回歸樹和分類樹的區別在於輸出值類型不同。分類樹輸出的是離散值，回歸樹輸出的是連續值。
2.和分類樹使用基尼系數不同，回歸樹使用和均方差來度量最佳分隔點。假設有1 2 3 4 5 6 六個數。假設3.5處把數據分開最合適，那麼(1-2)^2+(2-2)^2+(3-2)^2+(4-5)^2+(5-5)^2+(6-5)^2在所有分割點中取得最小值。2，5為各自數據段的平均值。
3.回歸樹採用最後葉子的平均值或者中值作為輸出結果
『貳』 GBDT —— 梯度提升決策樹
GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一種迭代的決策樹演算法，該演算法由多棵決策樹組成，所有樹的結論累加起來做最終答案。它在被提出之初就和SVM一起被認為是泛化能力較強的演算法。
GBDT中的樹是回歸樹（不是分類樹），GBDT用來做回歸預測，調整後也可以用於分類。
GBDT主要由三個概念組成：Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage (演算法的一個重要演進分枝，目前大部分源碼都按該版本實現）。搞定這三個概念後就能明白GBDT是如何工作的。
提起決策樹（DT, Decision Tree) 絕大部分人首先想到的就是C4.5分類決策樹。但如果一開始就把GBDT中的樹想成分類樹，那就錯了。千萬不要以為GBDT是很多棵分類樹。決策樹分為兩大類，回歸樹和分類樹。前者用於預測實數值，如明天的溫度、用戶的年齡、網頁的相關程度；後者用於分類標簽值，如晴天/陰天/霧/雨、用戶性別、網頁是否是垃圾頁面。這里要強調的是，前者的結果加減是有意義的，如10歲+5歲-3歲=12歲，後者則無意義，如男+男+女=到底是男是女？GBDT的核心在於累加所有樹的結果作為最終結果，就像前面對年齡的累加（-3是加負3），而分類樹的結果顯然是沒辦法累加的，所以 GBDT中的樹都是回歸樹，不是分類樹 ，這點對理解GBDT相當重要（盡管GBDT調整後也可用於分類但不代表GBDT的樹是分類樹）。
回歸樹總體流程類似於分類樹，區別在於，回歸樹的每一個節點都會得一個預測值，以年齡為例，該預測值等於屬於這個節點的所有人年齡的平均值。分枝時窮舉每一個feature的每個閾值找最好的分割點，但衡量最好的標准不再是最大熵，而是最小化平方誤差。也就是被預測出錯的人數越多，錯的越離譜，平方誤差就越大，通過最小化平方誤差能夠找到最可靠的分枝依據。分枝直到每個葉子節點上人的年齡都唯一或者達到預設的終止條件(如葉子個數上限)， 若最終葉子節點上人的年齡不唯一，則以該節點上所有人的平均年齡做為該葉子節點的預測年齡。
回歸樹演算法如下圖（截圖來自《統計學習方法》5.5.1 CART生成）：
梯度提升（Gradient boosting）是一種用於回歸、分類和排序任務的機器學習技術 [1] ，屬於Boosting演算法族的一部分。Boosting是一族可將弱學習器提升為強學習器的演算法，屬於集成學習（ensemble learning）的范疇。Boosting方法基於這樣一種思想：對於一個復雜任務來說，將多個專家的判斷進行適當的綜合所得出的判斷，要比其中任何一個專家單獨的判斷要好。通俗地說，就是「三個臭皮匠頂個諸葛亮」的道理。梯度提升同其他boosting方法一樣，通過集成（ensemble）多個弱學習器，通常是決策樹，來構建最終的預測模型。
Boosting、bagging和stacking是集成學習的三種主要方法。不同於bagging方法，boosting方法通過分步迭代（stage-wise）的方式來構建模型，在迭代的每一步構建的弱學習器都是為了彌補已有模型的不足。Boosting族演算法的著名代表是AdaBoost，AdaBoost演算法通過給已有模型預測錯誤的樣本更高的權重，使得先前的學習器做錯的訓練樣本在後續受到更多的關注的方式來彌補已有模型的不足。與AdaBoost演算法不同，梯度提升方法在迭代的每一步構建一個能夠沿著梯度最陡的方向降低損失（steepest-descent）的學習器來彌補已有模型的不足。經典的AdaBoost演算法只能處理採用指數損失函數的二分類學習任務 [2] ，而梯度提升方法通過設置不同的可微損失函數可以處理各類學習任務（多分類、回歸、Ranking等），應用范圍大大擴展。另一方面，AdaBoost演算法對異常點（outlier）比較敏感，而梯度提升演算法通過引入bagging思想、加入正則項等方法能夠有效地抵禦訓練數據中的噪音，具有更好的健壯性。這也是為什麼梯度提升演算法（尤其是採用決策樹作為弱學習器的GBDT演算法）如此流行的原因，
提升樹是迭代多棵回歸樹來共同決策。當採用平方誤差損失函數時，每一棵回歸樹學習的是之前所有樹的結論和殘差，擬合得到一個當前的殘差回歸樹，殘差的意義如公式：殘差 = 真實值 - 預測值 。提升樹即是整個迭代過程生成的回歸樹的累加。 GBDT的核心就在於，每一棵樹學的是之前所有樹結論和的殘差，這個殘差就是一個加預測值後能得真實值的累加量。
提升樹利用 加法模型和前向分步演算法 實現學習的優化過程。當損失函數時平方損失和指數損失函數時，每一步的優化很簡單，如平方損失函數學習殘差回歸樹。
提升方法其實是一個比adaboost概念更大的演算法，因為adaboost可以表示為boosting的前向分布演算法(Forward stagewise additive modeling)的一個特例，boosting最終可以表示為：
其中的w是權重，Φ是弱分類器(回歸器)的集合,其實就是一個加法模型(即基函數的線性組合)
前向分布演算法 實際上是一個貪心的演算法，也就是在每一步求解弱分類器Φ(m)和其參數w(m)的時候不去修改之前已經求好的分類器和參數：
OK，這也就是提升方法（之前向分布演算法）的大致結構了，可以看到其中存在變數的部分其實就是極小化損失函數 這關鍵的一步了，如何選擇損失函數決定了演算法的最終效果(名字)……這一步你可以看出演算法的「趨勢」，以後再單獨把「趨勢」拿出來說吧，因為我感覺理解演算法的關鍵之一就是理解演算法公式的「趨勢」
不同的損失函數和極小化損失函數方法決定了boosting的最終效果，我們現在來說幾個常見的boosting：
廣義上來講，所謂的Gradient Boosting 其實就是在更新的時候選擇梯度下降的方向來保證最後的結果最好，一些書上講的「殘差」 方法其實就是L2Boosting吧，因為它所定義的殘差其實就是L2Boosting的Derivative，接下來我們著重講一下弱回歸器(不知道叫啥了，自己編的)是決策樹的情況，也就是GBDT。
GBDT演算法可以看成是由K棵樹組成的加法模型：
解這一優化問題，可以用前向分布演算法（forward stagewise algorithm）。因為學習的是加法模型，如果能夠從前往後，每一步只學習一個基函數及其系數（結構），逐步逼近優化目標函數，那麼就可以簡化復雜度。這一學習過程稱之為Boosting。具體地，我們從一個常量預測開始，每次學習一個新的函數，過程如下：
舉個例子，參考自一篇博客, 該博客舉出的例子較直觀地展現出多棵決策樹線性求和過程以及殘差的意義。
還是年齡預測，簡單起見訓練集只有4個人，A,B,C,D，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學生；C,D分別是應屆畢業生和工作兩年的員工。如果是用一棵傳統的回歸決策樹來訓練，會得到如下圖1所示結果：
現在我們使用GBDT來做這件事，由於數據太少，我們限定葉子節點做多有兩個，即每棵樹都只有一個分枝，並且限定只學兩棵樹。我們會得到如下圖2所示結果：
在第一棵樹分枝和圖1一樣，由於A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預測值。此時計算殘差 （殘差的意思就是： A的預測值 + A的殘差 = A的實際值） ，所以A的殘差就是16-15=1（注意，A的預測值是指前面所有樹累加的和，這里前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來作為A的預測值）。進而得到A,B,C,D的殘差分別為-1,1，-1,1。然後我們拿殘差替代A,B,C,D的原值，到第二棵樹去學習，如果我們的預測值和它們的殘差相等，則只需把第二棵樹的結論累加到第一棵樹上就能得到真實年齡了。這里的數據顯然是我可以做的，第二棵樹只有兩個值1和-1，直接分成兩個節點。此時所有人的殘差都是0，即每個人都得到了真實的預測值。
換句話說，現在A,B,C,D的預測值都和真實年齡一致了。Perfect!：
A: 14歲高一學生，購物較少，經常問學長問題；預測年齡A = 15 – 1 = 14
B: 16歲高三學生；購物較少，經常被學弟問問題；預測年齡B = 15 + 1 = 16
C: 24歲應屆畢業生；購物較多，經常問師兄問題；預測年齡C = 25 – 1 = 24
D: 26歲工作兩年員工；購物較多，經常被師弟問問題；預測年齡D = 25 + 1 = 26
那麼哪裡體現了Gradient呢？其實回到第一棵樹結束時想一想，無論此時的cost function是什麼，是均方差還是均差，只要它以誤差作為衡量標准，殘差向量(-1, 1, -1, 1)都是它的全局最優方向，這就是Gradient。
講到這里我們已經把GBDT最核心的概念、運算過程講完了！沒錯就是這么簡單。
該例子很直觀的能看到，預測值等於所有樹值得累加，如A的預測值 = 樹1左節點 值 15 + 樹2左節點 -1 = 14。
因此，給定當前模型 fm-1(x)，只需要簡單的擬合當前模型的殘差。現將回歸問題的提升樹演算法敘述如下：
答案是過擬合。過擬合是指為了讓訓練集精度更高，學到了很多」僅在訓練集上成立的規律「，導致換一個數據集當前規律就不適用了。其實只要允許一棵樹的葉子節點足夠多，訓練集總是能訓練到100%准確率的（大不了最後一個葉子上只有一個instance)。在訓練精度和實際精度（或測試精度）之間，後者才是我們想要真正得到的。
我們發現圖1為了達到100%精度使用了3個feature（上網時長、時段、網購金額），其中分枝「上網時長>1.1h」 很顯然已經過擬合了，這個數據集上A,B也許恰好A每天上網1.09h, B上網1.05小時，但用上網時間是不是>1.1小時來判斷所有人的年齡很顯然是有悖常識的；
相對來說圖2的boosting雖然用了兩棵樹 ，但其實只用了2個feature就搞定了，後一個feature是問答比例，顯然圖2的依據更靠譜。（當然，這里是LZ故意做的數據，所以才能靠譜得如此狗血。實際中靠譜不靠譜總是相對的） Boosting的最大好處在於，每一步的殘差計算其實變相地增大了分錯instance的權重，而已經分對的instance則都趨向於0。這樣後面的樹就能越來越專注那些前面被分錯的instance。就像我們做互聯網，總是先解決60%用戶的需求湊合著，再解決35%用戶的需求，最後才關注那5%人的需求，這樣就能逐漸把產品做好，因為不同類型用戶需求可能完全不同，需要分別獨立分析。如果反過來做，或者剛上來就一定要做到盡善盡美，往往最終會竹籃打水一場空。
Shrinkage（縮減）的思想認為，每次走一小步逐漸逼近結果的效果，要比每次邁一大步很快逼近結果的方式更容易避免過擬合。即它不完全信任每一個棵殘差樹，它認為每棵樹只學到了真理的一小部分，累加的時候只累加一小部分，通過多學幾棵樹彌補不足。用方程來看更清晰，即
沒用Shrinkage時：（yi表示第i棵樹上y的預測值， y(1~i)表示前i棵樹y的綜合預測值）
y(i+1) = 殘差(y1~yi)， 其中： 殘差(y1~yi) = y真實值 - y(1 ~ i)
y(1 ~ i) = SUM(y1, ..., yi)
Shrinkage不改變第一個方程，只把第二個方程改為：
y(1 ~ i) = y(1 ~ i-1) + step * yi
即Shrinkage仍然以殘差作為學習目標，但對於殘差學習出來的結果，只累加一小部分（step 殘差）逐步逼近目標，step一般都比較小，如0.01~0.001（注意該step非gradient的step），導致各個樹的殘差是漸變的而不是陡變的。直覺上這也很好理解，不像直接用殘差一步修復誤差，而是只修復一點點，其實就是把大步切成了很多小步。 本質上，Shrinkage為每棵樹設置了一個weight，累加時要乘以這個weight，但和Gradient並沒有關系 *。 這個weight就是step。就像Adaboost一樣，Shrinkage能減少過擬合發生也是經驗證明的，目前還沒有看到從理論的證明。
該版本GBDT幾乎可用於所有回歸問題（線性/非線性），相對logistic regression僅能用於線性回歸，GBDT的適用面非常廣。亦可用於二分類問題（設定閾值，大於閾值為正例，反之為負例）。
參考資料：
http://blog.csdn.net/w28971023/article/details/8240756
http://blog.csdn.net/dark_scope/article/details/24863289
https://www.jianshu.com/p/005a4e6ac775
https://www.zybuluo.com/yxd/note/611571
『叄』 決策樹演算法-原理篇
關於決策樹演算法，我打算分兩篇來講，一篇講思想原理，另一篇直接擼碼來分析演算法。本篇為原理篇。
通過閱讀這篇文章，你可以學到：
1、決策樹的本質
2、決策樹的構造過程
3、決策樹的優化方向
決策樹根據使用目的分為：分類樹和回歸樹，其本質上是一樣的。本文只講分類樹。
決策樹，根據名字來解釋就是，使用樹型結構來模擬決策。
用圖形表示就是下面這樣。
其中橢圓形代表：特徵或屬性。長方形代表：類別結果。
面對一堆數據（含有特徵和類別），決策樹就是根據這些特徵（橢圓形）來給數據歸類（長方形）
例如，信用貸款問題，我根據《神奇動物在哪裡》的劇情給銀行造了個決策樹模型，如下圖：
然而，決定是否貸款可以根據很多特徵，然麻雞銀行選擇了：（1）是否房產價值>100w；（2）是否有其他值錢的抵押物；（3）月收入>10k；（4）是否結婚；這四個特徵，來決定是否給予貸款。
先不管是否合理，但可以肯定的是，決策樹做了特徵選擇工作，即選擇出類別區分度高的特徵。
由此可見， 決策樹其實是一種特徵選擇方法。 （特徵選擇有多種，決策樹屬於嵌入型特徵選擇，以後或許會講到，先給個圖）即選擇區分度高的特徵子集。
那麼， 從特徵選擇角度來看決策樹，決策樹就是嵌入型特徵選擇技術
同時，決策樹也是機器學習中經典分類器演算法，通過決策路徑，最終能確定實例屬於哪一類別。
那麼， 從分類器角度來看決策樹，決策樹就是樹型結構的分類模型
從人工智慧知識表示法角度來看，決策樹類似於if-then的產生式表示法。
那麼， 從知識表示角度來看決策樹，決策樹就是if-then規則的集合
由上面的例子可知，麻雞銀行通過決策樹模型來決定給哪些人貸款，這樣決定貸款的流程就是固定的，而不由人的主觀情感來決定。
那麼， 從使用者角度來看決策樹，決策樹就是規范流程的方法
最後我們再來看看決策樹的本質是什麼已經不重要了。
決策樹好像是一種思想，而通過應用在分類任務中從而成就了「決策樹演算法」。
下面內容還是繼續講解用於分類的「決策樹演算法」。
前面講了決策樹是一種 特徵選擇技術 。
既然決策樹就是一種特徵選擇的方法，那麼經典決策樹演算法其實就是使用了不同的特徵選擇方案。
如：
（1）ID3：使用信息增益作為特徵選擇
（2）C4.5：使用信息增益率作為特徵選擇
（3）CART：使用GINI系數作為特徵選擇
具體選擇的方法網上一大把，在這里我提供幾個鏈接，不細講。
但，不僅僅如此。
決策樹作為嵌入型特徵選擇技術結合了特徵選擇和分類演算法，根據特徵選擇如何生成分類模型也是決策樹的一部分。
其生成過程基本如下：
根據這三個步驟，可以確定決策樹由：（1）特徵選擇；（2）生成方法；（3）剪枝，組成。
決策樹中學習演算法與特徵選擇的關系如下圖所示：
原始特徵集合T：就是包含收集到的原始數據所有的特徵，例如：麻瓜銀行收集到與是否具有償還能力的所有特徵，如：是否結婚、是否擁有100w的房產、是否擁有汽車、是否有小孩、月收入是否>10k等等。
中間的虛線框就是特徵選擇過程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系數。
其中評價指標（如：信息增益）就是對特徵的要求，特徵需要滿足這種條件（一般是某個閾值），才能被選擇，而這一選擇過程嵌入在學習演算法中，最終被選擇的特徵子集也歸到學習演算法中去。
這就是抽象的決策樹生成過程，不論哪種演算法都是將這一抽象過程的具體化。
其具體演算法我將留在下一篇文章來講解。
而決策樹的剪枝，其實用得不是很多，因為很多情況下隨機森林能解決決策樹帶來的過擬合問題，因此在這里也不講了。
決策樹的優化主要也是圍繞決策樹生成過程的三個步驟來進行優化的。
樹型結構，可想而知，演算法效率決定於樹的深度，優化這方面主要從特徵選擇方向上優化。
提高分類性能是最重要的優化目標，其主要也是特徵選擇。
面對過擬合問題，一般使用剪枝來優化，如：李國和基於決策樹生成及剪枝的數據集優化及其應用。
同時，決策樹有很多不足，如：多值偏向、計算效率低下、對數據空缺較為敏感等，這方面的優化也有很多，大部分也是特徵選擇方向，如：陳沛玲使用粗糙集進行特徵降維。
由此，決策樹的優化方向大多都是特徵選擇方向，像ID3、C4.5、CART都是基於特徵選擇進行優化。
參考文獻
統計學習方法-李航
特徵選擇方法綜述-李郅琴
決策樹分類演算法優化研究_陳沛玲
基於決策樹生成及剪枝的數據集優化及其應用-李國和
『肆』 決策樹的原理及演算法
決策樹基本上就是把我們以前的經驗總結出來。我給你准備了一個打籃球的訓練集。如果我們要出門打籃球，一般會根據「天氣」、「溫度」、「濕度」、「刮風」這幾個條件來判斷，最後得到結果：去打籃球？還是不去？
上面這個圖就是一棵典型的決策樹。我們在做決策樹的時候，會經歷兩個階段：構造和剪枝。
構造就是生成一棵完整的決策樹。簡單來說，構造的過程就是選擇什麼屬性作為節點的過程，那麼在構造過程中，會存在三種節點：
根節點：就是樹的最頂端，最開始的那個節點。在上圖中，「天氣」就是一個根節點；
內部節點：就是樹中間的那些節點，比如說「溫度」、「濕度」、「刮風」；
葉節點：就是樹最底部的節點，也就是決策結果。
剪枝就是給決策樹瘦身，防止過擬合。分為「預剪枝」（Pre-Pruning）和「後剪枝」（Post-Pruning）。
預剪枝是在決策樹構造時就進行剪枝。方法是在構造的過程中對節點進行評估，如果對某個節點進行劃分，在驗證集中不能帶來准確性的提升，那麼對這個節點進行劃分就沒有意義，這時就會把當前節點作為葉節點，不對其進行劃分。
後剪枝就是在生成決策樹之後再進行剪枝，通常會從決策樹的葉節點開始，逐層向上對每個節點進行評估。如果剪掉這個節點子樹，與保留該節點子樹在分類准確性上差別不大，或者剪掉該節點子樹，能在驗證集中帶來准確性的提升，那麼就可以把該節點子樹進行剪枝。
1是欠擬合，3是過擬合，都會導致分類錯誤。
造成過擬合的原因之一就是因為訓練集中樣本量較小。如果決策樹選擇的屬性過多，構造出來的決策樹一定能夠「完美」地把訓練集中的樣本分類，但是這樣就會把訓練集中一些數據的特點當成所有數據的特點，但這個特點不一定是全部數據的特點，這就使得這個決策樹在真實的數據分類中出現錯誤，也就是模型的「泛化能力」差。
p(i|t) 代表了節點 t 為分類 i 的概率，其中 log2 為取以 2 為底的對數。這里我們不是來介紹公式的，而是說存在一種度量，它能幫我們反映出來這個信息的不確定度。當不確定性越大時，它所包含的信息量也就越大，信息熵也就越高。
ID3 演算法計算的是信息增益，信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計算公式，是父親節點的信息熵減去所有子節點的信息熵。
公式中 D 是父親節點，Di 是子節點，Gain(D,a) 中的 a 作為 D 節點的屬性選擇。
因為 ID3 在計算的時候，傾向於選擇取值多的屬性。為了避免這個問題，C4.5 採用信息增益率的方式來選擇屬性。信息增益率 = 信息增益 / 屬性熵，具體的計算公式這里省略。
當屬性有很多值的時候，相當於被劃分成了許多份，雖然信息增益變大了，但是對於 C4.5 來說，屬性熵也會變大，所以整體的信息增益率並不大。
ID3 構造決策樹的時候，容易產生過擬合的情況。在 C4.5 中，會在決策樹構造之後採用悲觀剪枝（PEP），這樣可以提升決策樹的泛化能力。
悲觀剪枝是後剪枝技術中的一種，通過遞歸估算每個內部節點的分類錯誤率，比較剪枝前後這個節點的分類錯誤率來決定是否對其進行剪枝。這種剪枝方法不再需要一個單獨的測試數據集。
C4.5 可以處理連續屬性的情況，對連續的屬性進行離散化的處理。比如打籃球存在的「濕度」屬性，不按照「高、中」劃分，而是按照濕度值進行計算，那麼濕度取什麼值都有可能。該怎麼選擇這個閾值呢，C4.5 選擇具有最高信息增益的劃分所對應的閾值。
針對數據集不完整的情況，C4.5 也可以進行處理。
暫無
請你用下面的例子來模擬下決策樹的流程，假設好蘋果的數據如下，請用 ID3 演算法來給出好蘋果的決策樹。
「紅」的信息增益為：1「大」的信息增益為：0
因此選擇「紅」的作為根節點，「大」沒有用，剪枝。
數據分析實戰45講.17 丨決策樹（上）：要不要去打籃球？決策樹來告訴你
『伍』 決策樹（Decision Tree）
通俗來說，決策樹分類的思想類似於找對象。現想像一個女孩的母親要給這個女孩介紹男朋友，於是有了下面的對話：
女兒：多大年紀了？
母親：26。
女兒：長的帥不帥？
母親：挺帥的。
女兒：收入高不？
母親：不算很高，中等情況。
女兒：是公務員不？
母親：是，在稅務局上班呢。
女兒：那好，我去見見。
這個女孩的決策過程就是典型的分類樹決策。相當於通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見。假設這個女孩對男人的要求是：30歲以下、長相中等以上並且是高收入者或中等以上收入的公務員，圖1表示了女孩的決策邏輯。
如果你作為一個女生，你會優先考慮哪個條件：長相？收入？還是年齡。在考慮年齡條件時使用25歲為劃分點，還是35歲為劃分點。有這么多條件，用哪個條件特徵先做if，哪個條件特徵後做if比較優呢？還有怎麼確定用特徵中的哪個數值作為劃分的標准。這就是決策樹機器學習演算法的關鍵了。
首先，我們需要熟悉資訊理論中熵的概念。熵度量了事物的不確定性，越不確定的事物，它的熵就越大。具體的，隨機變數X的熵的表達式如下：
如拋一枚硬幣為事件 ， ， ，
擲一枚骰子為事件 ， ，
，顯然擲骰子的不確定性比投硬幣的不確定性要高。
熟悉了單一變數的熵，很容易推廣到多個個變數的聯合熵，這里給出兩個變數X和Y的聯合熵表達式：
有了聯合熵，又可以得到條件熵的表達式H(X|Y)，條件熵類似於條件概率,它度量了我們在知道Y以後X剩下的不確定性。表達式：
我們剛才提到 度量了 的不確定性，條件熵 度量了我們在知道 以後 剩下的不確定性，那麼 呢？它度量了 在知道 以後不確定性減少程度，這個度量我們在資訊理論中稱為互信息，記為 。
信息熵 ，聯合熵 ，條件熵 ，互信息 之間的關系由圖2所示：
在決策樹的ID3演算法中，互信息 被稱為信息增益。ID3演算法就是用信息增益來判斷當前節點應該用什麼特徵來構建決策樹。信息增益大，則越適合用來分類。
下面我們用SNS社區中不真實賬號檢測的例子說明如何使用ID3演算法構造決策樹。為了簡單起見，我們假設訓練集合包含10個元素：
設L、F、H和D表示日誌密度、好友密度、是否使用真實頭像和賬號是否真實，下面計算各屬性的信息增益：
因此日誌密度的信息增益是0.276。用同樣方法得到H和F的信息增益分別為0.033和0.553。因為F具有最大的信息增益，所以第一次分裂選擇F為分裂屬性，分裂後的結果圖3表示：
在上圖的基礎上，再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。
但是ID3演算法中還存在著一些不足之處：
1.ID3沒有考慮連續特徵，比如長度，密度都是連續值，無法在ID3運用。這大大限制了ID3的用途。
2.ID3採用信息增益大的特徵優先建立決策樹的節點。很快就被人發現，在相同條件下，取值比較多的特徵比取值少的特徵信息增益大。比如一個變數有2個值，各為 ，另一個變數為3個值，各為 ，其實他們都是完全不確定的變數，但是取3個值的比取2個值的信息增益大。（信息增益反映的給定一個條件以後不確定性減少的程度,必然是分得越細的數據集確定性更高,也就是條件熵越小,信息增益越大）如河校正這個問題呢？為了解決這些問題我們有了C4.5演算法。
對於第一個問題，不能處理連續特徵， C4.5的思路是將連續的特徵離散化。比如m個樣本的連續特徵A有m個，從小到大排列為 。則C4.5取相鄰兩樣本值的平均數，一共取得m-1個劃分點，其中第i個劃分點 表示為： 。對於這m-1個點，分別計算以該點作為二元分類點時的信息增益。選擇信息增益最大的點作為該連續特徵的二元離散分類點。比如取到的增益最大的點為 ，取大於 為類別1，小於 為類別2。這樣我們就做到了連續特徵的離散化。
對於第二個問題，信息增益作為標准容易偏向於取值較多的特徵。C4.5中提出了信息增益比：
即特徵 的對數據集 的信息增益與特徵 信息熵的比，信息增益比越大的特徵和劃分點，分類效果越好。某特徵中值得種類越多，特徵對應的特徵熵越大，它作為分母，可以校正信息增益導致的問題。
回到上面的例子：
同樣可得： ， 。
因為F具有最大的信息增益比，所以第一次分裂選擇F為分裂屬性，分裂後的結果圖3表示。
再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。
看完上述材料，我們知道在ID3演算法中我們使用了信息增益來選擇特徵，信息增益大的優先選擇。在C4.5演算法中，採用了信息增益比來選擇特徵，以減少信息增益容易選擇特徵值種類多的特徵的問題。但是無論是ID3還是C4.5,都是基於資訊理論的熵模型的，這裡面會涉及大量的對數運算。能不能簡化模型同時也不至於完全丟失熵模型的優點呢？有！CART分類樹演算法使用基尼系數來代替信息增益比，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特徵越好。這和信息增益(比)是相反的。
在分類問題中，假設有 個類別，第 個類別的概率為 ,則基尼系數為：
對於給定的樣本 ，假設有 個類別，第 個類別的數量為 ，則樣本的基尼系數為:
特別的，對於樣本D,如果根據特徵A的某個值a,把D分成D1和D2兩部分，則在特徵A的條件下，D的基尼系數為：
回到上面的例子：
同理得： ， 。
因為L具有最小的基尼系數，所以第一次分裂選擇L為分裂屬性。
再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。
小夥伴們如果覺得文章還行的請點個贊呦！！同時覺得文章哪裡有問題的可以評論一下 謝謝你！
『陸』 機器學習系列（三十六）——回歸決策樹與決策樹總結
回歸決策樹樹是用於回歸的決策樹模型，回歸決策樹主要指CART演算法， 同樣也為二叉樹結構。以兩個特徵預測輸出的回歸問題為例，回歸樹的原理是將特徵平面劃分成若干單元，每一個劃分租派耐單元都對應一個特定的輸出。因為每個結點都是yes和no的判斷，所以劃分的邊界是平行於坐標軸的。對於測試數據，我們只要將特徵按照決策過程將其歸到某個單元，便得到對應的回歸輸出值。
如上圖所示的劃分和相應的回歸樹，如果現在新來一個數據的特徵是(6,7.5)，按照回歸樹，它對應的回歸結果就是C5。節點的劃分的過程也就是樹的建立過程，每劃分一次，隨即確定劃分單元對應的輸出，也就多了一個結點。當根據相應的約束條件終止劃分的時候，最終每個單元的輸出也就確定了，輸出也就是葉結點。這看似和分類樹差不多，實則有很大的區別。劃分點的尋找和輸出值的確定羨慎是回歸決策樹的兩個核心弊春問題。
一個輸入空間的劃分的誤差是用真實值和劃分區域的預測值的最小二乘來衡量的：
其中， 是每個劃分單元的預測值，這個預測值是該單元內每個樣本點的值的某種組合，比如可取均值：
（輸入特徵空間劃分為 ）
那麼求解最優劃分即是求解最優化問題：
其中， 和 是每次劃分形成的兩個區域。
關於該最優化問題的求解這里不再介紹，下面直接使用skleaen中的決策回歸樹來看一下決策樹的回歸效果，數據集使用Boston房價數據：
不進行調參的話，可以看到在測試集上R方是0.59，顯然這是不太好的結果，但是一個有趣的現象是，在訓練集上：
R方值是1.0，也就是在訓練集上決策樹預測的回歸結果完全吻合毫無偏差，這顯然是過擬合。這個例子也說明了決策樹演算法是非常容易產生過擬合的，當然我們可以通過調參來緩解過擬合。
下面繪制學習曲線來直觀看一下決策樹回歸模型的表現，首先繪制基於MSE的學習曲線：
學習曲線如下：
再繪制基於R方的學習曲線：
上面兩種都是在默認情況下也就是不進行決策樹深度和葉子節點個數等條件的限製得到的結果。發現在訓練集上，如果不進行限制，可以做到0偏差，這是明顯的過擬合。接下來調節參數再繪制學習曲線，為節約篇幅，只調節決策樹深度這一個參數，而且只繪制基於R方的學習曲線：
max_depth=1時
max_depth=3時
max_depth=5時
隨著深度的增加，模型復雜度越來越高，過擬合現象也越來越明顯，可以測試，當max_depth=20時，在訓練集上又為一條y=1的無偏差直線。有興趣的仍然可以修改其它參數繪制學習曲線。
決策樹的局限性：
使用本系列上篇文章中的鳶尾花數據，來看一下決策樹對個別數據敏感會導致的結果，在本系列上篇文章中，使用信息熵劃分，其餘參數默認情況下繪制的決策邊界是：
接著我們刪除索引為138的數據，再來繪制決策邊界：
發現此時的決策邊界已經完全不同了，而這僅僅只是一個數據點的影響。
綜上我們知道決策樹實際是一種不夠穩定的演算法，它的表現極度依賴調參和數據，不過雖然決策樹本身不是一種高效的機器學習演算法，但是它們基於集成學習的組合——隨機森林(RF)卻是一個很魯棒的機器學習演算法，這將在下篇開始介紹。