【机器学习入门】(4) 决策树算法理论：算法原理、信息熵、信息增益、预剪枝、后剪枝、算法选择
各位同學好，今天我向大家介紹一下python機器學習中的決策樹算法的基本原理。內容主要有：
(1) 概念理解；(2) 信息熵；(3) 信息增益；(4) 算法選擇；(5) 預剪枝和后剪枝。
python決策樹算法案例實戰在下一篇文章中介紹。那我們開始吧。
【機器學習】(5) 決策樹算法實戰：sklearn實現決策樹，實例應用（沉船幸存者預測）附python完整代碼及數據集
1. 決策樹概念
通過不斷的劃分條件來進行分類，決策樹最關鍵的是找出那些對結果影響最大的條件，放到前面。
我舉個列子來幫助大家理解，我現在給我女兒介紹了一個相親對象，她根據下面這張決策樹圖來進行選擇。比如年齡是女兒擇偶更看中的，那就該把年齡這個因素放在最前面，這樣可以節省查找次數。收入高的話就去見，中等的話還要考慮工作怎么樣。
???????決策樹通過歷史數據，找出數據集中對結果影響最大的特征，再找第二個影響最大的特征。若新來一個數，只要根據我們已經建立起的決策樹進行歸類即可。
2. 決策樹的信息熵
? ? ? ? 用來表示隨機數據不確定性的度量，信息熵越大，表示這組數據越不穩定，而信息熵越小，則數據越穩定、越接近、越類似。
????????信息熵公式：??
H(x)表示信息熵，P(F1,F2,…) 表示數據在整個數據集中出現的概率。
我舉個例子幫助大家理解：
A = [1,1,1,1,1,1,1,1,2,2]? ? ?#1出現了8次，2出現了2次
B = [1,2,3,4,5,6,7,8,9,10]
此時計算A、B的信息熵：
B的信息熵比A大得多，因此數據A更加穩定，若將A和B放到決策樹中考慮信息熵，A熵更小更穩定，放到最前面判斷。
????????我們看一下??曲線再來理解一下信息熵公式。首先，公式中的P(i)永遠是在0-1之間的，因此??是一個負數，因此在整個式子前面填一個負號，使結果H(x)為正。P(i)概率越大，log越小，信息熵越小，P(i)概率越小，信息熵越大，越不穩定。
3. 信息增益
表示特征x使得值y的不確定性減小的程度。信息增益越大，表示對不確定性的減少就越多，越能更清晰地分類。
特征A對訓練集D的信息增益記作?，定義為：集合D的信息熵H(D)與特征A給定條件下D的經驗條件熵??之差。
特征A對事件D的信息增益：?
A條件下D的信息熵記作H(D|A)，A特征中可能有N種值(A1,A2,..)
特征A條件下D的信息熵：??
下面我用一個例子（貸款案例的信息增益）來幫助大家理解：
數據集中，有年齡、工作、房子、信譽等4個特征來判斷是否應該給這個用戶貸款。在決策樹中，將哪個特性放在最前面判斷，哪個特性放到最后面，需要通過計算信息增益來決定。
首先計算年齡對能否貸款的信息增益
A = 年齡，A1 = 青年，A2 = 中年，A3 = 老年，D = 貸款
年齡對貸款的信息增益為：
?
在能否貸款的這個集合中，有9個人能貸款，6個人不能貸款，計算其信息熵
貸款的信息熵：
?
在年齡這個特征下，15個人中有5個青年，5個中年，5個老年
在年齡特征下貸款的信息熵：
以青年為例，15個人中有5個青年，其中3個能貸款，2個不能貸款
年齡對貸款的信息增益是:
H(貸款|年齡) =
同理，是否有工作的信息增益為0.32；是否有房的信息增益為0.42；信貸情況的信息增益為0.363。建立決策樹時根據信息增益從大到小排序，先考慮有沒有房，再考慮信貸情況，再考慮有沒有工作，最后考慮年齡。
4. 決策樹算法選擇
4.1 ID3
????????方法介紹：采用信息增益來進行決策樹的創建，盡管效果不錯，但是他會選擇分支更多的屬性，會導致過擬合，一般不采用此方法。
如果有一組特征都是相互獨立的，如B=[1,2,3,4,5,6,7,8,9,10]，
計算信息增益：?
A1代表數字1，出現概率為1/10，在1的條件下出現數字1的概率為1/1
因此??
????????該方法會導致分支多的屬性的信息增益很大，導致決策樹不準確，比如上個貸款案例中，如果將第一列ID，即1-15這幾個序列數，當作特征去計算，得到的信息增益會特別大，在建立決策樹時，把序列這一列放到決策樹最前面，然而實際上，序列這一列是對結果沒有絲毫影響的。
4.2 C4.5
由于ID3方法會導致過度擬合，因此我們通過對分支過多的情況進行懲罰，引入信息增益比gr。
信息增益比 = 某特征的信息增益 / 某特征的信息熵
如果某特征分類特別多，會導致信息熵非常大，從而信息增益會變得非常大，對它進行懲罰，進行有效抑制。
4.3 CART
????????C4.5方法盡管能較好地構建決策樹算法，但在計算時需要不斷求對數log，對算法的效率有一定影響。在CART算法中采用基尼系數(Gini)來進行分類，Gini系數是一種與信息熵類似的做特征選擇的方式。基尼系數越大說明數據越復雜越混亂，越小說明越平均越集中。
????????基尼系數通常用于描述一個國家財富分配情況，超過0.4說明貧富差距很大，0.3左右說明財富分配水平均勻。
基尼系數公式：?
?代表某一個特征中每一個值出現的概率
上個例子中的年齡的基尼系數是：Gini(年齡) = 1 – (5/15)^2 - (5/15)^2 - (5/15)^2
在建立決策樹時，基尼系數越小的，就把它放在最前面。
5. 預剪枝和后剪枝
????????樹的層級和葉子節點不能過于復雜，如果過于復雜，會導致過擬合現象（過擬合：訓練時得分很高，測試時得分很低）。預剪枝和后剪枝都是為了防止決策樹太復雜的手段
5.1 預剪枝
????????在決策樹的建立過程中不斷調節來達到最優，可以調節的條件有：
（1）樹的深度：在決策樹建立過程中，發現深度超過指定的值，那么就不再分了。
（2）葉子節點個數：在決策樹建立過程中，發現葉子節點個數超過指定的值，那么就不再分了。
（3）葉子節點樣本數：如果某個葉子結點的個數已經低于指定的值，那么就不再分了。
（4）信息增益量或Gini系數：計算信息增益量或Gini系數，如果小于指定的值，那就不再分了。
優點：預剪枝可以有效降低過擬合現象，在決策樹建立過程中進行調節，因此顯著減少了訓練時間和測試時間；預剪枝效率比后剪枝高。
缺點：預剪枝是通過限制一些建樹的條件來實現的，這種方式容易導致欠擬合現象：模型訓練的不夠好。
5.2 后剪枝
在決策樹建立完成之后再進行的，根據以下公式：
C = gini(或信息增益)*sample(樣本數) + a*葉子節點個數
C表示損失，C越大，損失越多。通過剪枝前后的損失對比，選擇損失小的值，考慮是否剪枝。
a是自己調節的，a越大，葉子節點個數越多，損失越大。因此a值越大，偏向于葉子節點少的，a越小，偏向于葉子節點多的。
優點：通常比預剪枝保留更多的分支，因此欠擬合風險比預剪枝要小。
缺點：但因為后剪枝是再數建立完成之后再自底向上對所有非葉子節點進行注意考察，因此訓練時間開銷比預剪枝要大。
總結
以上是生活随笔為你收集整理的【机器学习入门】(4) 决策树算法理论：算法原理、信息熵、信息增益、预剪枝、后剪枝、算法选择的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【机器学习入门】(3) 朴素贝叶斯算法：
- 下一篇： 【机器学习入门】(5) 决策树算法实战：