1-1 基本流程

決策樹是一個有監(jiān)督分類與回歸算法。
決策樹的生成只考慮局部最優(yōu)，相對的，決策樹剪枝則考慮全局最優(yōu)。

一、概念：

決策樹：是一種樹形結(jié)構(gòu)，其中每個內(nèi)部節(jié)點表示一個屬性上的判斷，每個分支代表一個判斷結(jié)果的輸出，最后每個葉節(jié)點代表一種分類結(jié)果，本質(zhì)是一顆由多個判斷節(jié)點組成的樹。

二、劃分依據(jù)：

①熵

物理學(xué)上，熵 Entropy 是“混亂” 程度的量度。
系統(tǒng)越有序，熵值越低；系統(tǒng)越混亂或者分散，熵值越高
信息理論：
1、當(dāng)系統(tǒng)的有序狀態(tài)一致時，數(shù)據(jù)越集中的地方熵值越小，數(shù)據(jù)越分散的地方熵值越大。這是從信息的完整性上進(jìn)行的描述。
2、當(dāng)數(shù)據(jù)量一致時，系統(tǒng)越有序，熵值越低；系統(tǒng)越混亂或者分散，熵值越高。這是從信息的有序性上進(jìn)行的描述。

假如事件A的分類劃分是（A1,A2,…,An），每部分發(fā)生的概率是(p1,p2,…,pn)，那信息熵定義為公式如下：
$$Ent(A)=?\sum _{k=1}^n{p}_{k}lo{g}_2{p}_k$$
二分法：
如果有32個球隊，準(zhǔn)確的信息量應(yīng)該是：
H = -（p1 * logp1 + p2 * logp2 + … + p32 * logp32），其中 p1, …, p32 分
別是這 32 支球隊奪冠的概率。當(dāng)每支球隊奪冠概率相等都是 1/32 的時：H = -（32 * 1/32 * log1/32） = 5 每個事件概率相同時，熵最大，這件事越不確定。

②特征選擇–信息增益及增益率

信息增益：以某特征劃分?jǐn)?shù)據(jù)集前后的熵的差值。熵可以表示樣本集合的不確定性，熵越大，樣本的不確定性就越大。因此可以使用劃分前后集合熵的差值來衡量使用當(dāng)前特征對于樣本集合D劃分效果的好壞。
信息增益 = entroy(前) - entroy(后)
信息增益公式如下：
D：為樣本集
Ent(D):整體熵
a:離散型屬性
v: 是a屬性里可能的取值節(jié)點
D^v：第v個分支節(jié)點包含了D中所有在屬性a上取值為a^v的樣本

信息增益越大，熵被消除，不確定性越小，應(yīng)作為最優(yōu)特征
$$Gain(D,a)=Ent(D)?\sum _{v=1}^v\frac{D^v}{D}Ent(D^v)$$
增益率：增益比率度量是用前面的增益度量Gain(S，A)和所分離信息度量SplitInformation(如上例的性別，活躍度等)的比值來共同定義的。

公式如下：
$$GainRatio(S_A,A)=\frac{Gain(S_A,A)}{SplitInformation(S_A,A)}$$
$$SplitInformation(S_A,A)=?\sum _{m\in M}\frac{|S_{Am}|}{|S_A|}log\frac{S_{A}m}{S_A}$$

例子：
如下圖，第一列為論壇號碼，第二列為性別，第三列為活躍度，最后一列用戶是否流失

其中Positive為正樣本（ 已流失） ， Negative為負(fù)樣本
（ 未流失） ， 下面的數(shù)值為不同劃分下對應(yīng)的人數(shù)。可得到三個熵：
整體熵：
$$E(S)=?\frac{5}{15}lo{g}_2(\frac{5}{15})?\frac{10}{15}lo{g}_2(\frac{10}{15})=0.9182$$
性別熵：
$$E(g_1)=?\frac{3}{8}lo{g}_2(\frac{3}{8})?\frac{5}{8}lo{g}_2(\frac{5}{8})=0.9543$$
$$E(g_2)=?\frac{2}{7}lo{g}_2(\frac{2}{7})?\frac{5}{7}lo{g}_2(\frac{5}{7})=0.8631$$
性別信息增益：
$$IGain(S,g)=E(s)?\frac{8}{15}E(g_1)?\frac{7}{15}E(g_2)=0.0064$$
活躍度熵：
E(a1) = 0
E(a2) = 0.7219
E(a3) = 0

活躍度信息增益：
$$IGain(S,g)=E(s)?\frac{6}{15}E(a_1)?\frac{5}{15}E(a_2)?\frac{4}{15}E(a_3)=0.6776$$
活躍度的信息增益比性別的信息增益大，也就是說，活躍度對用戶流失的影響比性別大。
在做特征選擇或者數(shù)據(jù)分析的時候， 我們應(yīng)該重點考察活躍度這個指標(biāo)。

③基尼值和基尼指數(shù)

基尼值Gini（D）：從數(shù)據(jù)集D中隨機抽取兩個樣本，起類別標(biāo)記不一致的概率，故，Gini
（D）值越小，數(shù)據(jù)集D的純度越高。
基尼系數(shù)公式如下：
$$Gini(D)=1?\sum _{k=1}^{|y|}{p}_k^2$$
基尼指數(shù)Gini_index（D）：一般，選擇使劃分后基尼系數(shù)最小的屬性作為最優(yōu)化分屬性
基尼指數(shù)公式如下：
$$Gini\_index(D,a)=\sum _{v=1}^v\frac{|D^v|}{|D|}Gini(D^v)$$
基尼增益：
$$Gini(D,a)=Gini(D)?\sum _{v=1}^v\frac{|D^v|}{|D|}Gini(D^v)$$
例題：

總結(jié)如下：

類型拖欠不拖欠匯總

整體	3	7	10
有房	0	3	3
沒房	3	4	7
單身	2	2	4
結(jié)婚	0	4	4
離婚	1	1	2

1，對數(shù)據(jù)集非類標(biāo)號屬性{是否有房，婚姻狀況，年收入}分別計算它們的Gini系數(shù)增益，取Gini系數(shù)增益值最大的屬性作為決策樹的根節(jié)點屬性。

2、根節(jié)點的Gini系數(shù)為：
Gini(是否拖欠貸款)
$$Gini(D)=1?(\frac{3}{10}{)}^2?(\frac{7}{10}{)}^2=0.42$$
3， 當(dāng)根據(jù)是否有房來進(jìn)行劃分時， Gini系數(shù)增益計算過程為 ：
Gini(左子節(jié)點)=
$$Gini(y)=1?(\frac{0}{3}{)}^2?(\frac{3}{3}{)}^2=0$$
Gini(右子節(jié)點)=
$$Gini(n)=1?(\frac{3}{7}{)}^2?(\frac{4}{7}{)}^2=0.4898$$
｛ 是否有房｝=
$$Gini(D)?\frac{3}{10}Gini(y)?\frac{7}{10}Gini(n)=0.42?\frac{3}{10}?0?\frac{7}{10}?0.4898=0.077$$
4， 若按婚姻狀況屬性來劃分， 屬性婚姻狀況有三個可能的取值{married，
single， divorced}， 分別計算劃分后的Gini系數(shù)增益。
分組為{married} | {single,divorced}時

類型拖欠不拖欠匯總

整體	3	7	10
有房	0	3	3
沒房	3	4	7
結(jié)婚	0	4	4
單身,離婚	3	3	6

｛ 婚姻狀況｝=
$$0.42?\frac{4}{10}?0?\frac{6}{10}?[1?(\frac{3}{6}{)}^2?(\frac{3}{6}{)}^2]=0.12$$
當(dāng)分組為{single} | {married,divorced}時

類型拖欠不拖欠匯總

整體	3	7	10
有房	0	3	3
沒房	3	4	7
單身	2	2	4
離婚，結(jié)婚	1	5	6

｛ 婚姻狀況｝=
$$0.42?\frac{4}{10}?0.5?\frac{6}{10}?[1?(\frac{1}{6}{)}^2?(\frac{5}{6}{)}^2]=0.053$$
當(dāng)分組為{divorced} | {single,married}時

類型拖欠不拖欠匯總

整體	3	7	10
有房	0	3	3
沒房	3	4	7
離婚	1	1	2
單身，結(jié)婚	2	6	8

｛ 婚姻狀況｝= $$0.42?\frac{2}{10}?0.5?\frac{8}{10}?[1?(\frac{2}{8}{)}^2?(\frac{6}{8}{)}^2]=0.053$$
對比計算結(jié)果，根據(jù)婚姻狀況屬性來劃分根節(jié)點時取Gini系數(shù)增益最大的分組作為劃分結(jié)果即
{married} | {single,divorced}

小結(jié)：
決策樹的生成：通常使用信息增益最大，信息增益比最大和基尼指數(shù)最小作為最優(yōu)特征，從根節(jié)點開始，遞歸的產(chǎn)生決策樹。相當(dāng)于用信息增益或其他準(zhǔn)則不斷地選取局部最優(yōu)的特征，或?qū)⒂?xùn)練集分割為能夠基本正確分了的子集

一，決策樹構(gòu)建的基本步驟如下：

開始講所有記錄看作一個節(jié)點

遍歷每個變量的每一種分割方式，找到最好的分割點

分割成兩個節(jié)點N1和N2

對N1和N2分別繼續(xù)執(zhí)行2-3步，直到每個節(jié)點足夠“純”為止。
[Source]https://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html

二，決策樹的變量可以有兩種：
1） 數(shù)字型（Numeric）：變量類型是整數(shù)或浮點數(shù)，如前面例子中的“年收入”。用“>=”，
“>”,“<”或“<=”作為分割條件（排序后，利用已有的分割情況，可以優(yōu)化分割算法的時間復(fù)雜度）。
2） 名稱型（Nominal）：類似編程語言中的枚舉類型，變量只能重有限的選項中選取，比如前面例子中的“婚姻情況”，只能是“單身”，“已婚”或“離婚”，使用“=”來分割。

三，如何評估分割點的好壞？
如果一個分割點可以將當(dāng)前的所有節(jié)點分為兩類，使得每一類都很“純”，也就是同一類的記錄較多，那么就是一個好分割點。
比如上面的例子，“擁有房產(chǎn)”，可以將記錄分成了兩類，“是”的節(jié)點全部都可以償還債務(wù)，非常
“純”；“否”的節(jié)點，可以償還貸款和無法償還貸款的人都有，不是很“純”，但是兩個節(jié)點加起來的純度之和與原始節(jié)點的純度之差最大，所以按照這種方法分割。構(gòu)建決策樹采用貪心算法，只考慮當(dāng)前純度差最大的情況作為分割點。

常見的決策樹類型：

1-2 常見決策樹類型及剪枝

1為什么要剪枝

• 隨著樹的增長， 在訓(xùn)練樣集上的精度是單調(diào)上升的，然而在獨立的測試樣例上測出的精度先上升后下降。
• 原因1： 噪聲、 樣本沖突， 即錯誤的樣本數(shù)據(jù)。
• 原因2： 特征即屬性不能完全作為分類標(biāo)準(zhǔn)。
• 原因3： 巧合的規(guī)律性， 數(shù)據(jù)量不夠大。

2常用的剪枝方法

1.1 預(yù)剪枝：
（1）每一個結(jié)點所包含的最小樣本數(shù)目，例如10，則該結(jié)點總樣本數(shù)小于10時，則不
再分；
（2）指定樹的高度或者深度，例如樹的最大深度為4；
（3）指定結(jié)點的熵小于某個值，不再劃分。隨著樹的增長， 在訓(xùn)練樣集上的精度是調(diào)上升的， 然而在獨立的測試樣例上測出的精度先上升后下降。

1.2 后剪枝：
后剪枝，在已生成過擬合決策樹上進(jìn)行剪枝，可以得到簡化版的剪枝決策樹。
主要有四種：
（1）REP-錯誤率降低剪枝
（2）PEP-悲觀剪枝
（3）CCP-代價復(fù)雜度剪枝
（4）MEP-最小錯誤剪枝

結(jié)論：
決策樹的剪枝，由于生成的決策樹存在過擬合問題，需要對它進(jìn)行剪枝，以簡化學(xué)到的決策樹。決策樹的剪枝，往往從已生成的樹上剪掉一些葉節(jié)點或葉節(jié)點以上的子樹，并將其父節(jié)點或根節(jié)點作為新的葉節(jié)點，從而簡化生成的決策樹模型。

ID3不能剪枝
C4.5和CRAT都可以剪枝

總結(jié)

以上是生活随笔為你收集整理的机器学习之决策树算法详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。