本文僅作網(wǎng)絡(luò)筆記用寻狂，不定時完善。
決策樹根據(jù)輸出的不同蔗蹋，分為回歸樹和分類樹事期，但兩種樹的學(xué)習(xí)過程并無特別大的不同，都是分為兩步：
- 決策樹生成
- 決策樹剪枝
1纸颜、特征選擇方法
- 熵：隨機變量X的熵被定義為：
其中p(x)=Pr(X=x)是X的密度函數(shù)兽泣。熵度量了隨機變量X的不確定性程度，如8種均勻可能需要log28=3個字節(jié)來存儲胁孙。
- 聯(lián)合熵 和 條件熵：
兩個隨機變量的聯(lián)合熵被定義為：
條件熵被定義為：
另外可以證明：
- 信息增益(互信息)：互信息是一個隨機變量包含另一個隨機變量信息量的度量唠倦，也是在給定另一隨機變量知識的條件下称鳞，原隨機變量不確定度的縮減量。
注意到互信息(信息增益)關(guān)于X和Y是對稱的稠鼻，即H(X)-H(X|Y)=H(Y)-H(Y|X)冈止。而且它與相對熵存在如下等價關(guān)系：
但是信息增益傾向于選擇取值較多的特征，比如：有10個樣本候齿，特征A有10個取值熙暴，每個取值有一個樣本，這時分支節(jié)點的純度達到最大慌盯，相應(yīng)的信息增益最大周霉，利用信息增益對特征進行選擇，結(jié)果更可能選擇這樣的特征A亚皂。但這樣的特征無法對新樣本進行有效的預(yù)測俱箱。
- 信息增益比：
需要注意的是，增益率對可取值較少的特征有偏好灭必，所以C4.5算法并不是直接選擇增益率最大的特征進行劃分狞谱，而是先從候選屬性中找出信息增益高于平均水平的屬性，再從中選擇信息增益率最高的禁漓。
- 基尼指數(shù)（Gini impurity）
要注意這里的GINI不純度(并不是GINI系數(shù))跟衅，它可以看作是熵的一種近似：
因為當(dāng)p(x)趨近于1時有
還有一個優(yōu)勢就是計算簡單，不用特殊考慮p(x)=0的情況播歼。在CART樹中与斤，屬性a的GINI指數(shù)定義為：
MSE(適合回歸樹)
MAE(mean absolute error)
2、決策樹生成
對于一顆決策樹荚恶，我們在生成每個節(jié)點時，要自動決策三件事：
- 選擇哪個特征用于分枝
- 特征的劃分點（用于二叉樹）
- 樹的拓撲（形狀）
在回歸樹中磷支，令
則每一步是一個最小化問題：
3谒撼、決策樹剪枝
根據(jù)”偏差-方差分解定理“，模型的泛化誤差可以分解為偏差雾狈、方差和噪聲之和廓潜。決策樹在生成的時候完全照顧到了偏差，所以在剪枝階段我們要認真考慮模型的偏差善榛。
- 損失函數(shù)
損失函數(shù)要兼顧預(yù)測誤差和模型復(fù)雜度（節(jié)點個數(shù)）
設(shè)樹T的葉節(jié)點個數(shù)為|T|辩蛋，t是樹T的葉節(jié)點，該葉節(jié)點有N_t個樣本點移盆，其中k類的樣本點有$N_{tk}$個悼院，H_t(T)為葉結(jié)點t上的經(jīng)驗熵，alpha >=0為參數(shù)咒循，則決策樹學(xué)習(xí)的損失函數(shù)可以定義為：
其中經(jīng)驗熵為
上述講的是C4.5決策樹据途，對于CART分類樹中的任意子樹绞愚，我們有：
其中C(T)是子樹的預(yù)測誤差，|T|是子樹葉結(jié)點個數(shù)颖医。
CART分類樹的剪枝主要考慮三點：
- 1位衩、樹的大小|T|，葉子節(jié)點個數(shù)
- 2熔萧、基于訓(xùn)練數(shù)據(jù)的預(yù)測誤差
- 3糖驴、基于測試數(shù)據(jù)的預(yù)測誤差
對于第1和第2點，我們可以自下而上找到一個最優(yōu)的子節(jié)點使得剪枝后損失函數(shù)得到最大的改善（有優(yōu)化的計算方法）佛致，此時也對應(yīng)著一個alpha贮缕，然后剪枝得到一顆子樹。不斷迭代上述過程晌杰，理論上會直接結(jié)束于原決策樹的根結(jié)點跷睦，但我們又不知道在這個中間怎么去停止，于是便有了第三點肋演。具體方法如下：
