參考

https://blog.csdn.net/u012328159/article/details/79396893
https://blog.csdn.net/u012328159/article/details/79413610
https://www.cnblogs.com/fionacai/p/5894142.html

原理

決策樹常用來解決分類問題，是一種基本的分類與回歸方法。它遞歸每個特征的各種取值，將樣本切分為多個類，最后可以得到一個樹形結(jié)構(gòu)。

舉個例子：引用自這里的例子

一位母親在給女兒介紹對象時，有這么一段對話：
母親：給你介紹個對象。
女兒：年紀(jì)多大了？
母親：26。
女兒：長的帥不帥？
母親：挺帥的。
女兒：收入高不？
母親：不算很高，中等情況。
女兒：是公務(wù)員不？
母親：是，在稅務(wù)局上班呢。
女兒：那好，我去見見。

這個女生的決策過程就是典型的分類決策樹。相當(dāng)于對年齡、外貌、收入和是否公務(wù)員等特征將男人分為兩個類別：見或者不見。假設(shè)這個女生的決策邏輯如下：

1.png

在上面女兒的決策中，將男生根據(jù)不同的特征分為了兩類：見或者不見。但圖中的判斷順序取決于母親的詢問順序，有時候是不合理的，有可能女生開始判斷是公務(wù)員其它條件不管是什么都回去見呢。。：）

所以我們需要找到什么特征對女生的影響最大，先判斷影響大的，再去判斷影響小的。這樣引入下面的基本概念。

基礎(chǔ)概念

熵

熵表示隨機(jī)變量的不確定性度量。也就是說我們可以用熵去表示特征的不確定性。

熵的公式為:

屏幕快照 2018-04-12 21.40.49.png

屏幕快照 2018-04-12 21.44.24.png

解釋一下，在上面的例子中，集合A中一共有10個樣本，值取1有8個，取2有2個，那么p1為8/10，p2為2/10，熵為：
H(X) = - 8/10 * log(8/10) - 2/10 * log(2/10) = 0.5004024235381879

條件熵

條件熵表示在某個條件下隨機(jī)變量的不確定性度量。
以上面的集合A為例，當(dāng)變量小于1.5的時候，集合A中，所有的變量都為1。當(dāng)變量大于1.5的時候，所有的變量都為2。

當(dāng)變量小于1.5時，熵為: H(X | X < 1.5) = - 8/8 * log(8/8) = 0.0
當(dāng)變量大于1.5時，熵為: H(X | X > 1.5) = - 2/2 * log(2/2) = 0.0

將這兩個上相加，就是以1.5值作為條件劃分之后，新的數(shù)據(jù)集的熵值。 為0

信息增益

信息增益表示，當(dāng)數(shù)據(jù)集根據(jù)某個特征劃分之后，熵的變化大小。

在上面的例子中，在沒有條件(X> 1.5 或 X < 1.5)的時候熵為0.5004024235381879。在經(jīng)過條件的劃分后，新的熵值為0，那么信息增益就是舊值減去新值。g(D,A)=H(D)?H(D|A)= 0.5004024235381879 - 0 = 0.5004024235381879

這樣，如果有多個特征，分別計(jì)算根據(jù)各個特征作為條件后的熵值，并得到信息增益。我們選擇信息增益最大的特征作為影響最大的特征，先進(jìn)行分類判斷。

信息增益率

有時候特征數(shù)據(jù)不確定性比較大的時候，比如上面的集合B，這樣的數(shù)據(jù)計(jì)算出來的信息增益特別的大，因?yàn)椋瑢λM(jìn)行劃分后，每個分類里的值都是唯一的，熵都為0。這樣顯然不合理。

信息增益率 = 信息增益 / 原熵值

我們用信息增益率來代替信息增益，選取信息增益率最大的作為優(yōu)先劃分特征。

構(gòu)建樹的結(jié)束條件

遇到下面幾種情況，就停止繼續(xù)劃分節(jié)點(diǎn)：

1. 節(jié)點(diǎn)中所有樣本屬于同一類。
2. 該節(jié)點(diǎn)中所有樣本的屬性取值一致。
3. 樹的深度達(dá)到設(shè)定的閾值。
4. 該節(jié)點(diǎn)所含樣本值小于設(shè)定的父節(jié)點(diǎn)應(yīng)含觀測數(shù)的閾值。
5. 該節(jié)點(diǎn)的的子節(jié)點(diǎn)所按樣本數(shù)將小魚設(shè)定的閾值。
6. 沒有屬性能滿足設(shè)定的分裂準(zhǔn)則的閾值。

例子

def createDataSet():
    dataSet = [['youth', 'no', 'no', 1, 'refuse'],
               ['youth', 'no', 'no', '2', 'refuse'],
               ['youth', 'yes', 'no', '2', 'agree'],
               ['youth', 'yes', 'yes', 1, 'agree'],
               ['youth', 'no', 'no', 1, 'refuse'],
               ['mid', 'no', 'no', 1, 'refuse'],
               ['mid', 'no', 'no', '2', 'refuse'],
               ['mid', 'yes', 'yes', '2', 'agree'],
               ['mid', 'no', 'yes', '3', 'agree'],
               ['mid', 'no', 'yes', '3', 'agree'],
               ['elder', 'no', 'yes', '3', 'agree'],
               ['elder', 'no', 'yes', '2', 'agree'],
               ['elder', 'yes', 'no', '2', 'agree'],
               ['elder', 'yes', 'no', '3', 'agree'],
               ['elder', 'no', 'no', 1, 'refuse'],
               ]
    labels = ['age', 'working?', 'house?', 'credit_situation']
    return dataSet, labels

上面是銀行貸款的15個樣本數(shù)據(jù)，有4種特征，最后一列為是否同意貸款。是我們的分類類別。前面4個是年齡段、是否有工作、是否有房、信用等級。

下面的log計(jì)算，是以底為2計(jì)算的。之前的是以10為底。這個沒有關(guān)系

首先我們計(jì)算在沒有條件下，分類的熵情況，同意的情況有9次，不同意的情況有6次。則：
H(x) = - 9/15 * log(9/15) - 6/15 * log(6/15) = 0.9709505944546686

然后我們分別計(jì)算每個特征分類條件下的熵值：
以age為例：當(dāng)age取值為youth時，有5個樣本，同意的情況有2次，不同意3次，那么熵為：
H(x | age == youth) = - 3/5 * log(3/5) - 2/5 * log(2/5) = 0.9709505944546686
同理
H(x | age == mid) = - 3/5 * log(3/5) - 2/5 * log(2/5) = 0.9709505944546686
H(x | age == elder) = - 4/5 * log(4/5) - 1/5 * log(1/5) = 0.7219280948873623

那么
H(x | age) = H(x | age == youth) + H(x | age == mid) + H(x | age == elder) = 2.663829
信息增益g(x,age) = 0.9709505944546686 - 2.663829 = -1.692879 (負(fù)值代表劃分后不確定性更高了，一般不可取)
信息增益率(age) = g(x,age) / H(x | age) = -1.743527

繼續(xù)計(jì)算working、house、credit_situation：
g(x, working) = 0.000000
g(x, house) = 0.052655
g(x, credit_situation) = -0.669273

信息增益率(working) = 0.000000
信息增益率(house) = 0.054230
信息增益率(credit_situation) = -0.689297

無論是以信息增益 還是信息增益率，選取最大的作為最有影響的特征，house（是否有房）作為第一節(jié)點(diǎn)。

接著講house劃分為兩個數(shù)據(jù)集，繼續(xù)上面的步驟，再次計(jì)算信息增益或信息增益率，最終得到?jīng)Q策樹。

Unknown.png

當(dāng)我們進(jìn)行兩個迭代后，判斷house和working后，所有的樣本都在同一個類別下面了，就停止迭代。

連續(xù)值處理

當(dāng)我們的特征數(shù)據(jù)中存在連續(xù)值的時候，我們不能將每個值都當(dāng)做一個分類吧！！

常用的辦法就是二分法，也是C4.5中采用的策略，具體意思就是將確定一個值，將數(shù)據(jù)分為大于這個值和小于這個值的兩類。

如何確定這個值呢？

公式定理：

20180228135729007.jpeg

白話文就是，首先將連續(xù)值進(jìn)行排序，將排序后每兩個值中間的值作為劃分點(diǎn)，循環(huán)計(jì)算每個點(diǎn)劃分后，連續(xù)值的信息增益，選取信息增益最大的劃分點(diǎn)。

舉個簡單例子
連續(xù)值集合A [1,1,1,3,3,3,4] 排序后，計(jì)算劃分點(diǎn)的集合為[2, 3.5]

集合A熵值= H(x) =- 1/7 * log(1/7) - 3/7 * log(3/7) - 3/7 * log(3/7) = 1.0042424730540764

計(jì)算劃分點(diǎn)為2
當(dāng)x<2時，H(A| x<2) = - 3/3 * log(3/3) = 0
當(dāng)x>=2時，H(A | x>=2) = - 3/4 * log(3/4) - 1/4 * log(1/4) = 0.5623351446188083
熵為 = H(A| x<2) + H(A | x>=2) = 0.5623351446188083
信息增益 = g(A | 2為劃分點(diǎn)) = H(x) - H(A| 2為劃分點(diǎn)) = 0.44190732843526814

計(jì)算劃分點(diǎn)為3.5
當(dāng)x<3.5時，H(A | x < 3.5) = - 3/6 * log(3/6) - 3/6 * log(3/6) = 0.6931471805599453
當(dāng)x >= 3.5 時，H(A | x >= 3.5) = - 1/1 * log(1/1) = 0
熵為 = H(A| x< 3.5) + H(A | x>= 3.5) = 0.6931471805599453
信息增益 = g(A | 3.5為劃分點(diǎn)) = H(x) - H(A| 3.5為劃分點(diǎn)) = 0.31109529249413115

這樣相比當(dāng)劃分點(diǎn)為2的時候，信息增益比較大，將2作為劃分點(diǎn)。

思考：如果數(shù)據(jù)量比較大，那劃分點(diǎn)的數(shù)量會非常多，會不會比較慢，有沒有更好的方案？
如果想選擇多個劃分點(diǎn)，是否可以直接選擇剩下的信息增益低的特征。

缺省值處理

在實(shí)際情況中，數(shù)據(jù)總是會有缺失的，當(dāng)然也可以將這些特征給刪除掉，但有時候這樣也是不合理的。

下面引用參考文章中的例子：

20180301204809787.jpg

公式，文本的說法可以直接看參考文章。下面是我自己的白話文。。。

以色澤這個特征為例，
第一步，我們將缺失的值去掉，留下無缺失值的集合編號[2,3,4,6,7,8,9,10,11,12,14,15,16,17]。
第二步，計(jì)算這個無缺失值集合的信息增益。
H(x) = - 6/14 * log(6/14) - 8/14 * log(8/14) = 0.985
H(x | x = 青綠) = - 2/4 * log(2/4) - 2/4 * log(2/4) = 1
H(x | x = 烏黑) = - 4/6 * log(4/6) - 2/6 * log(2/6) = 0.918
H(x | x = 淺白) = - 0/4 * log(0/4) - 4/4 * log(4/4) = 0
g(x) = H(x) - (H(x | x = 青綠) * 4/14 + H(x | x = 烏黑) * 6/14 + H(x | x = 淺白) * 4/ 14) = 0.306

這樣分別計(jì)算每個特征的信息增益，選取信息增益最大的特征，作為根節(jié)點(diǎn)。

比較發(fā)現(xiàn)，“紋理”在所有屬性中的信息增益值最大，因此，“紋理”被選為劃分屬性，用于對根節(jié)點(diǎn)進(jìn)行劃分。劃分結(jié)果為：“紋理=稍糊”分支：{7,9,13,14,17}，“紋理=清晰”分支：{1,2,3,4,5,6,15}，“紋理=模糊”分支：{11,12,16}。

但是紋理的[8,10]是缺失的，改怎么處理？

將8和10兩個樣本，分別劃入每個分支中，給每個分支中的8和10的樣本設(shè)置權(quán)重，

20180302150552337.png

然后我們一這個新的分支集合，繼續(xù)執(zhí)行決策樹的構(gòu)造過程。
以紋理=稍糊為例：現(xiàn)在的集合是[7,8,9,10,13,14,17]

20180302152911787.png

再次技術(shù)色澤的信息增益，色澤無缺失集合為[7,8,9,10,14,17]，但是，8和10的權(quán)重不是1了，是之前計(jì)算的權(quán)重值 1/3。

不好描述 還是截圖吧。

屏幕快照 2018-04-17 下午1.52.44.png

這樣分別計(jì)算各個特征的信息增益，發(fā)現(xiàn)“敲聲”，信息增益最大，這樣得到了在稍糊分支上的特征劃分。

20180303105613522.png

繼續(xù)按照這規(guī)則遞歸下去，得到整顆樹：

20180303112711995.jpg

剪枝

如果以決策樹的定義，葉節(jié)點(diǎn)內(nèi)的所有的樣本都屬于同一個類的話，決策樹一般會非常龐大，而且可能分類效果也不好，產(chǎn)生過擬合的現(xiàn)象。所以需要對決策樹進(jìn)行剪枝

剪枝一般有兩種思路，預(yù)剪枝和后剪枝。

• 預(yù)剪枝，在決策樹開始構(gòu)造之前，預(yù)先定義一些參數(shù)，比如，樹深度，葉節(jié)點(diǎn)數(shù)量等，然后在構(gòu)造樹的過程中，瞞住條件參數(shù)，就可以停止繼續(xù)構(gòu)造了。
• 后剪枝，先將整顆樹構(gòu)造完畢，然后使用測試集測試在剪枝后的誤差和剪枝前的誤差，如果剪枝后誤差變小了，那么可以剪枝。

隨機(jī)森林

盡管有各種剪枝算法，一棵樹的效果肯定還是不如多顆樹，因此有了隨機(jī)森林，解決決策樹泛化能力弱的缺點(diǎn)。

這時就有了Bagging策略可以產(chǎn)生多個不同的數(shù)據(jù)集。

1. 在數(shù)據(jù)集不變的情況下，我們可以選擇ID3、C4.5、CART、SVM、LOGISTIC等算法作為不同的判斷條件，分別建立不同的樹。
2. 還可以更進(jìn)一步在數(shù)據(jù)集上做文章：
   • 樣本的隨機(jī)：從樣本集中隨機(jī)選取n個樣本。
   • 特征的隨機(jī)：從所有特征中，隨機(jī)選取k個特征。

這樣可以建立m個隨機(jī)的決策樹。

得到m個決策樹后，測試數(shù)據(jù)集分別進(jìn)入這m棵樹進(jìn)行分類，被分類到的次數(shù)越多，就是選那個分類。

調(diào)參：

1. 如何選取K，可以考慮有N個屬性，取K=根號N
2. 最大深度（不超過8層）
3. 棵數(shù)
4. 最小分裂樣本樹
5. 類別比例

決策樹的重要參數(shù)都是防止過擬合的. 有2個參數(shù)是關(guān)鍵，min_samples_leaf 這個sklearn的默認(rèn)值是1，經(jīng)驗(yàn)上必須大于100，如果一個節(jié)點(diǎn)都沒有100個樣本支持他的決策，一般都被認(rèn)為是過擬合；max_depth 這個參數(shù)控制樹的規(guī)模。決策樹是一個非常直觀的機(jī)器學(xué)習(xí)方法。一般我們都會把它的決策樹結(jié)構(gòu)打印出來觀察，如果深度太深對于我們的理解是有難度的。