決策樹-ID3，C4.5，CART

決策樹

直觀上，決策樹是一個(gè)樹結(jié)構(gòu)，從根節(jié)點(diǎn)開始，測試待分類項(xiàng)中相應(yīng)的特征屬性（每次只測一個(gè)特征維度），并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點(diǎn)，將葉子節(jié)點(diǎn)存放的類別作為決策結(jié)果

西瓜書里的圖

在挑西瓜模型中，首先判斷紋理這一特征維度，分成了3個(gè)數(shù)據(jù)集，其中模糊紋理這一波直接是葉子節(jié)點(diǎn)，存放決策結(jié)果。

而從數(shù)據(jù)的特征空間角度，決策樹則是把整個(gè)特征空間劃分成了若干個(gè)超立方體。就像魔方

可以是均分空間

更多的是不均分的空間

每一個(gè)小塊，是一個(gè)空間劃分R_{j}，也是樹中的一個(gè)葉子節(jié)點(diǎn)，存放著決策結(jié)果y_{j}。
如果是回歸樹，則葉子結(jié)點(diǎn)存放回歸結(jié)果c_{j}

現(xiàn)在的問題是，就挑西瓜模型來說，應(yīng)該選用哪個(gè)特征作為優(yōu)先特征作根節(jié)點(diǎn)呢？
當(dāng)然是越重要的，越能區(qū)分西瓜好壞的特征越優(yōu)先選擇了。

決策樹的一般流程是：
1，對(duì)于數(shù)據(jù)集D(X,Y),按照某種方法選擇對(duì)于當(dāng)前數(shù)據(jù)集最重要的特征。
2，按照這個(gè)特征中值的不同劃分為對(duì)應(yīng)數(shù)量的子數(shù)據(jù)集D_{i}(X,Y)。
3，如果D_{i}(X,Y)中有的子數(shù)據(jù)集只包含一類數(shù)據(jù)或者類別相對(duì)比較純，則該數(shù)據(jù)集就可以當(dāng)作葉子節(jié)點(diǎn)。對(duì)于其他子數(shù)據(jù)集，分別重復(fù)1，2步。直到到達(dá)規(guī)定的最大輪數(shù)（樹最大深度）或者用完了所有特征或者特征空間已經(jīng)完美分割。
4，最后，得到分類函數(shù)：
f(X_{i})=\sum_{j=1}^{k}y_{j}I(X_{i}\in R_{j})
假設(shè)最終有k個(gè)劃分空間（葉子節(jié)點(diǎn)）

決策樹挑選特征的算法主要有3個(gè)：

ID3

大致流程

ID3就是使用信息增益來挑選特征的決策樹算法。
具體地
1，計(jì)算當(dāng)前數(shù)據(jù)集D_{i}的熵H(X)
2，分別計(jì)算當(dāng)前可用特征下D的條件熵 H(X|Ai)
3，分別計(jì)算不同特征的信息增益 I(X,Ai)=H(X)-H(X|Ai)，取最大者作為所挑選特征，如果最大的I也小于閾值，則終止
例如上篇中襪子位置問題，就應(yīng)該選擇襪子顏色特征作為第一個(gè)特征，這樣甚至不再需要后續(xù)特征就能分好。

缺點(diǎn)

ID3算法，簡單明了易理解，但有如下缺點(diǎn)：
1，只能處理離散特征，不能處理連續(xù)特征
2，未考慮過擬合的處理
3，未對(duì)缺失值做處理
4，算法傾向于優(yōu)先選擇取值較多的特征，他認(rèn)為取值越多的特征，信息增益越大，條件熵越小。如果一個(gè)特征A1有10個(gè)取值，A2只有2個(gè)取值，即使價(jià)值相似，ID3也更傾向于選擇A1.解釋一下原因：
從條件熵公式可以看出：
\begin{alignedat}{2} H(X|Y) &= -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i|y_i) \\ &= \sum\limits_{j=1}^{n}p(y_j)H(X|y_j) \end{alignedat}
當(dāng)特征取值越多，
即n越大，則每個(gè)p(y_{j})則相對(duì)會(huì)越小。
同時(shí)，n越大，則每個(gè)取值下樣本量就會(huì)少。樣本量少則分布更容易不平均從而導(dǎo)致H(X|y_j)相對(duì)變小，這個(gè)變小會(huì)導(dǎo)致雖然n大，累加次數(shù)多，但不能彌補(bǔ)p(y_{j})和H(X|y_j)的雙重減小。從而導(dǎo)致條件熵減小，信息增益變大
極端情況下，如果n=樣本量，即該特征每個(gè)值都對(duì)應(yīng)了唯一一個(gè)樣本，則H(X|Y)=\sum_{j=1}^{n}\frac{1}{n}0=0,信息增益最大，但是卻毫無意義。
詳見此處

C4.5

大致流程

為了解決上述問題，提出了本算法。
最主要的是，解決了問題4:引入信息增益比替代信息增益
I_R(D,A) = \frac{I(A,D)}{H_A(D)}
H_A(D) = -\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}
即，每個(gè)信息增益，比上數(shù)據(jù)集在該特征上的熵。

問題1:連續(xù)特征作二元離散。在選取切分值的時(shí)候，計(jì)算每個(gè)切分值上的信息增益。取最大。
問題2:剪枝
問題3:缺失值

缺點(diǎn)

1，剪枝需優(yōu)化
2，多叉樹不如二叉樹效率高
3，只能分類不能回歸
4，熵模型需要計(jì)算對(duì)數(shù)，耗時(shí)

CART

思想：無限二分
即每次按照特征把數(shù)據(jù)分成兩部分

一般流程

1，分類
CART樹相對(duì)于C4.5的關(guān)鍵改變是用基尼指數(shù)替代了信息增益比
Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2
對(duì)于數(shù)據(jù)集D，有k個(gè)類別，每個(gè)類別有C_k個(gè)樣本,則
Gini(D) = 1-\sum\limits_{k=1}^{K}(\frac{|C_k|}{|D|})^2
如果是二類分類問題，計(jì)算就更加簡單了，如果屬于第一個(gè)樣本輸出的概率是p，則基尼指數(shù)的表達(dá)式為：
Gini(p) = 2p(1-p)
對(duì)于數(shù)據(jù)集D,如果根據(jù)特征A的某個(gè)值a,把D分成D1和D2兩部分，則在特征A的條件下，D的基尼指數(shù)表達(dá)式為：
Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)
注意這個(gè)式子，很像條件熵的公式。
所以，特征A下D的基尼指數(shù)可以認(rèn)為是條件基尼指數(shù)Gini(D|A)
這樣，選取最優(yōu)特征以及特征切分時(shí)，應(yīng)該挑條件基尼指數(shù)最小（信息增益最大對(duì)應(yīng)著條件熵最?。┑哪且唤M。
這里基尼指數(shù)有一點(diǎn)比較特別，是它會(huì)根據(jù)特征的一個(gè)值把數(shù)據(jù)分成兩部分，而不像ID3，C4.5一樣特征有多少值就把數(shù)據(jù)分成幾部分，即把多叉樹改變成了二叉樹

由于CART每次只把數(shù)據(jù)分成兩部分，
那么，對(duì)于特征值多于兩個(gè)的離散特征來說，應(yīng)該如何劃分?jǐn)?shù)據(jù)？粗暴，直接窮盡所有組合，尋找基尼指數(shù)最小的組合。所以，后續(xù)，還會(huì)用到該特征
對(duì)于連續(xù)的特征，則像C4.5一樣作離散化，在所有二元切分中找到基尼指數(shù)最小的切分，把特征做成二元離散的。同樣，后續(xù)還會(huì)用到該特征
注意到，ID3和C4.5的離散特征只會(huì)參與一次特征選擇，而CART則不是。

2，回歸
回歸預(yù)測的是連續(xù)值，訓(xùn)練數(shù)據(jù)的Y肯定也是連續(xù)值。
無限二分依然有效，只不過不適用基尼指數(shù)了，而是使用和方差
例如對(duì)于一個(gè)已經(jīng)劃分好的特征空間，回歸樹返回的值是對(duì)應(yīng)的結(jié)果劃分塊中所有樣本值的均值或中位數(shù)
而如何訓(xùn)練這個(gè)劃分？
優(yōu)化如下式子
\underbrace{min}_{A,s}\Bigg[\underbrace{min}_{c_1}\sum\limits_{x_i \in D_1(A,s)}(y_i - c_1)^2 + \underbrace{min}_{c_2}\sum\limits_{x_i \in D_2(A,s)}(y_i - c_2)^2\Bigg]
其中，A是特征，s是該特征的一個(gè)切分值，D1，D2是按照特征A的切分值s切分后的兩個(gè)數(shù)據(jù)集，c1，c2分別是D1，D2內(nèi)樣本值的均值。
中括號(hào)內(nèi)是固定A后，尋找最優(yōu)s
中括號(hào)外是尋找最優(yōu)的A

剪枝

剪枝非常重要。
CART樹的剪枝是后剪枝，即建完樹后再剪枝
對(duì)于一棵樹T，其損失函數(shù)：
C_\alpha(T)=C(T)+\alpha|T|
C(T)是這棵樹的預(yù)測誤差，可以是對(duì)每個(gè)葉子里數(shù)據(jù)的基尼指數(shù)（或方差）作加權(quán)求和
|T|是樹的葉子節(jié)點(diǎn)數(shù)

觀察這個(gè)公式
當(dāng)\alpha=0時(shí)，樹最大，葉子最多，最容易過擬合
當(dāng)\alpha=+\infty 時(shí)，樹最小，縮成了一個(gè)根節(jié)點(diǎn)

對(duì)于一棵樹T，設(shè)t是其一個(gè)非葉子節(jié)點(diǎn) T_t是以t為根節(jié)點(diǎn)的子樹,則：
C_{\alpha}(t) = C(t) + \alpha
C_{\alpha}(T_t) = C(T_t) + \alpha|T_t|
分別表示t節(jié)點(diǎn)的損失和T_t子樹的損失
我們令 C_{\alpha}(t) = C_{\alpha}(T_t)可得
\alpha_t = \frac{C(t)-C(T_t)}{|T_t|-1}
這表示什么？
這表示如果當(dāng)前剪枝設(shè)定的 \alpha = \alpha_t 時(shí)，
T_t這棵子樹可以剪掉并用t代替，而不會(huì)帶來更大的損失
而如果當(dāng)前剪枝設(shè)定的 \alpha > \alpha_t 時(shí)
C_{\alpha}(t) < C_{\alpha}(T_t)
這表示必須要剪掉T_t這棵子樹，因?yàn)椴坏梢越档蛽p失，還可以縮小樹規(guī)模，一舉兩得。

所以，如果我們遍歷所有t，獲取所有\alpha_t 然后對(duì)其升序排序得到
(\alpha_{t0},\alpha_{t1}...\alpha_{tn})
所以，隨著我們逐個(gè)設(shè)置\alpha=\alpha_{ti} ,i=0,1,2...n
就會(huì)得到一個(gè)個(gè)剪枝過后的T
(T_{c0},T_{c1},...T_{cn})
這么多T，那個(gè)是最好的？
用個(gè)新的數(shù)據(jù)集測測就OK了，誰高選誰

參考
劉建平博客-決策樹
統(tǒng)計(jì)學(xué)習(xí)方法-李航

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 博客園：http://www.cnblogs.com/wxquare/p/5379970.html ID3（多叉樹...
    閆阿佳閱讀 2,171評(píng)論 0贊 0
  • 優(yōu)缺點(diǎn)和適用范圍： 優(yōu)點(diǎn)： 計(jì)算不那么費(fèi)時(shí) 便于人類的理解 可處理非相關(guān)特征 缺點(diǎn)： 容易過擬合（關(guān)于如何盡量避免...
    Athenaearl閱讀 805評(píng)論 0贊 5
  • 決策樹 決策樹是一種基本的分類和回歸方法.決策樹顧名思義,模型可以表示為樹型結(jié)構(gòu),可以認(rèn)為是if-then的集合,...
    七八音閱讀 983評(píng)論 0贊 1
  • 決策樹是機(jī)器學(xué)習(xí)中非常經(jīng)典的一類學(xué)習(xí)算法，它通過樹的結(jié)構(gòu)，利用樹的分支來表示對(duì)樣本特征的判斷規(guī)則，從樹的葉子節(jié)點(diǎn)所...
    arrnos閱讀 6,018評(píng)論 0贊 3
  • 決策樹理論在決策樹理論中，有這樣一句話，“用較少的東西，照樣可以做很好的事情。越是小的決策樹，越優(yōu)于大的決策樹”。...
    制杖灶灶閱讀 6,056評(píng)論 0贊 25

友情鏈接更多精彩內(nèi)容