一陨界、什么是決策樹
所謂決策樹巡揍，就是一個(gè)類似于流程圖的樹形結(jié)構(gòu)，樹內(nèi)部的每一個(gè)節(jié)點(diǎn)代表的是對一個(gè)特征的測試菌瘪，樹的分支代表該特征的每一個(gè)測試結(jié)果腮敌，而樹的每一個(gè)葉子節(jié)點(diǎn)代表一個(gè)類別。樹的最高層是就是根節(jié)點(diǎn)俏扩。下圖即為一個(gè)決策樹的示意描述糜工，內(nèi)部節(jié)點(diǎn)用矩形表示，葉子節(jié)點(diǎn)用橢圓表示录淡。
二捌木、決策樹的優(yōu)缺點(diǎn)
1、優(yōu)點(diǎn)
a) 計(jì)算簡單嫉戚，易于理解
b) 適應(yīng)不同的數(shù)據(jù)類型（包括類別數(shù)據(jù)刨裆，數(shù)值數(shù)據(jù)，未歸一化的和混合的數(shù)據(jù)）
c) 比較適合處理有缺失屬性的樣本
d) 通過分裂的順序給數(shù)據(jù)特征賦不同的重要性
e) 能夠處理不相關(guān)的特征
f) 在相對短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且結(jié)果良好的結(jié)果
g) 決策樹構(gòu)成了其他算法的基礎(chǔ)（如boosting和隨機(jī)數(shù)）
2彬檀、缺點(diǎn)
a) 容易發(fā)生過擬合（隨機(jī)森林可以很大程度上減少過擬合）帆啃；
b) 忽略了數(shù)據(jù)之間的相關(guān)性；
c) 對于那些窍帝，各類別樣本數(shù)量不一致的數(shù)據(jù)努潘，在決策樹中，信息增益的結(jié)果偏向于那些具有更多數(shù)值的特征（只要使用了信息增益，都有這個(gè)特點(diǎn)疯坤，如RF）
三报慕、算法的計(jì)算過程
第一步，特征選擇：
特征選擇是指從訓(xùn)練數(shù)據(jù)中眾多的特征中選擇一個(gè)特征作為當(dāng)前節(jié)點(diǎn)的分裂標(biāo)準(zhǔn)贴膘，如何選擇特征有著很多不同量化評估標(biāo)準(zhǔn)標(biāo)準(zhǔn)卖子，從而衍生出不同的決策樹算法略号。
問題：根節(jié)點(diǎn)的選擇該用哪個(gè)特征呢刑峡？即如何確定一個(gè)判斷節(jié)點(diǎn)是最好的？
例如上面那個(gè)丈母娘是否滿意女婿的決策樹玄柠，有的丈母娘覺得年齡大自己女兒太多不行突梦，有的覺得一定要買房才可以，所以判斷的節(jié)點(diǎn)先后很重要羽利，一系列下來才能做出自己的抉擇宫患。
答：熵、GINI系數(shù)
特征挑選方法——信息增益法：信息增益既可以用熵也可以用GINI系數(shù)來計(jì)算
選擇具有最高信息增益的特征作為測試特征这弧，利用該特征對節(jié)點(diǎn)樣本進(jìn)行劃分子集娃闲，會使得各子集中不同類別樣本的混合程度最低，在各子集中對樣本劃分所需的信息（熵）最少
信息增益=信息熵-條件熵匾浪，即信息增益代表了在一個(gè)條件下皇帮，信息復(fù)雜度（不確定性）減少的程度。如果選擇一個(gè)特征后蛋辈，信息增益最大（信息不確定性減少的程度最大）属拾，那么我們就選取這個(gè)特征。
舉例：
可以求得隨機(jī)變量X（嫁與不嫁）的信息熵為：
嫁的個(gè)數(shù)為6個(gè)冷溶，占1/2渐白，那么信息熵為-1/2log1/2-1/2log1/2 = -log1/2=0.301
現(xiàn)在假如我知道了一個(gè)男生的身高信息。
身高有三個(gè)可能的取值{矮逞频，中纯衍，高}
矮包括{1,2,3,5,6,11,12}，嫁的個(gè)數(shù)為1個(gè)苗胀，不嫁的個(gè)數(shù)為6個(gè)
中包括{8,9} 襟诸，嫁的個(gè)數(shù)為2個(gè)，不嫁的個(gè)數(shù)為0個(gè)
高包括{4,7,10}柒巫，嫁的個(gè)數(shù)為3個(gè)励堡，不嫁的個(gè)數(shù)為0個(gè)
先回憶一下條件熵的公式如下：
我們先求出公式對應(yīng)的:
H(Y|X = 矮) = -1/7log1/7-6/7log6/7=0.178
H(Y|X=中) = -1log1-0 = 0
H(Y|X=高） = -1log1-0=0
p(X = 矮) = 7/12,p(X =中) = 2/12,p(X=高) = 3/12
則可以得出條件熵為：
7/120.178+2/120+3/12*0 = 0.103
那么我們知道信息熵與條件熵相減就是我們的信息增益，為
0.301-0.103=0.198
所以我們可以得出我們在知道了身高這個(gè)信息之后堡掏，信息增益是0.198
以此類推应结，每個(gè)節(jié)點(diǎn)都可以算出他的信息增益，在全部算出之后對比，可以得出信息增益最大的節(jié)點(diǎn)是哪個(gè)鹅龄，那么就可以選出接下來的節(jié)點(diǎn)了揩慕。
GINI系數(shù)同理，只是和熵的算法不一致扮休，原理相同迎卤。
ps：上面舉例的數(shù)據(jù)是離散型的，如果是連續(xù)型的數(shù)據(jù)玷坠，那么必須進(jìn)行離散化哦
第二步蜗搔，決策樹生成：
根據(jù)選擇的特征評估標(biāo)準(zhǔn)，從上至下遞歸地生成子節(jié)點(diǎn)八堡，直到數(shù)據(jù)集不可分則停止決策樹停止生長樟凄。 樹結(jié)構(gòu)來說，遞歸結(jié)構(gòu)是最容易理解的方式兄渺。
步驟如下：
- 從根節(jié)點(diǎn)出發(fā)缝龄，根節(jié)點(diǎn)包括所有的訓(xùn)練樣本。
- 一個(gè)節(jié)點(diǎn)（包括根節(jié)點(diǎn)）挂谍，若節(jié)點(diǎn)內(nèi)所有樣本均屬于同一類別叔壤，那么將該節(jié)點(diǎn)就成為葉節(jié)點(diǎn)，并將該節(jié)點(diǎn)標(biāo)記為樣本個(gè)數(shù)最多的類別口叙。
- 否則利用采用信息增益法來選擇用于對樣本進(jìn)行劃分的特征炼绘，該特征即為測試特征，特征的每一個(gè)值都對應(yīng)著從該節(jié)點(diǎn)產(chǎn)生的一個(gè)分支及被劃分的一個(gè)子集庐扫。
- 遞歸上述劃分子集及產(chǎn)生葉節(jié)點(diǎn)的過程饭望，這樣每一個(gè)子集都會產(chǎn)生一個(gè)決策（子）樹，直到所有節(jié)點(diǎn)變成葉節(jié)點(diǎn)形庭。
- 遞歸操作的停止條件就是：
（1）一個(gè)節(jié)點(diǎn)中所有的樣本均為同一類別铅辞，那么產(chǎn)生葉節(jié)點(diǎn)
（2）沒有特征可以用來對該節(jié)點(diǎn)樣本進(jìn)行劃分。此時(shí)也強(qiáng)制產(chǎn)生葉節(jié)點(diǎn)萨醒，該節(jié)點(diǎn)的類別為樣本個(gè)數(shù)最多的類別
（3）沒有樣本能滿足剩余特征的取值斟珊，即對應(yīng)的樣本為空。此時(shí)也強(qiáng)制產(chǎn)生葉節(jié)點(diǎn)富纸，該節(jié)點(diǎn)的類別為樣本個(gè)數(shù)最多的類別
第三步囤踩，剪枝：
由于噪聲等因素的影響，會使得樣本某些特征的取值與樣本自身的類別不相匹配的情況晓褪，基于這些數(shù)據(jù)生成的決策樹的某些枝葉會產(chǎn)生一些錯(cuò)誤堵漱；尤其是在決策樹靠近枝葉的末端，由于樣本變少涣仿，這種無關(guān)因素的干擾就會突顯出來勤庐；由此產(chǎn)生的決策樹可能存在過擬合的現(xiàn)象示惊。樹枝修剪就是通過統(tǒng)計(jì)學(xué)的方法刪除不可靠的分支，使得整個(gè)決策樹的分類速度和分類精度得到提高愉镰。
為什么要剪枝：決策樹過擬合風(fēng)險(xiǎn)很大米罚，理論上可以完全分得開數(shù)據(jù)
想象一下，如果樹足夠龐大丈探，每個(gè)葉子節(jié)點(diǎn)不就一個(gè)數(shù)據(jù)了嘛
剪枝策略：預(yù)剪枝录择，后剪枝
樹枝修剪包括預(yù)剪枝和后剪枝兩種方法：
（1）預(yù)剪枝：邊建立決策樹邊進(jìn)行剪枝的操作（更實(shí)用）
在決策樹生成分支的過程，除了要進(jìn)行基礎(chǔ)規(guī)則的判斷外碗降，還需要利用統(tǒng)計(jì)學(xué)的方法對即將分支的節(jié)點(diǎn)進(jìn)行判斷隘竭，比如統(tǒng)計(jì)χ2或統(tǒng)計(jì)信息增益，如果分支后使得子集的樣本統(tǒng)計(jì)特性不滿足規(guī)定的閾值遗锣，則停止分支货裹；但是閾值如何選取才合理是比較困難的。
（2）后剪枝：當(dāng)建立完決策樹后來進(jìn)行剪枝操作
在決策樹充分生長后精偿，修剪掉多余的分支。根據(jù)每個(gè)分支的分類錯(cuò)誤率及每個(gè)分支的權(quán)重赋兵，計(jì)算該節(jié)點(diǎn)不修剪時(shí)預(yù)期分類錯(cuò)誤率笔咽；對于每個(gè)非葉節(jié)點(diǎn)，計(jì)算該節(jié)點(diǎn)被修剪后的分類錯(cuò)誤率霹期，如果修剪后分類錯(cuò)誤率變大叶组，即放棄修剪；否則將該節(jié)點(diǎn)強(qiáng)制為葉節(jié)點(diǎn)历造，并標(biāo)記類別甩十。產(chǎn)生一系列修剪過的決策樹候選之后，利用測試數(shù)據(jù)（未參與建模的數(shù)據(jù)）對各候選決策樹的分類準(zhǔn)確性進(jìn)行評價(jià)吭产，保留分類錯(cuò)誤率最小的決策樹侣监。
四、基礎(chǔ)算法
1臣淤、ID3
（1）簡述
ID3算法是最早提出的一種決策樹算法橄霉，ID3算法的核心是在決策樹各個(gè)節(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則來選擇特征，遞歸的構(gòu)建決策樹邑蒋。具體方法是：從根節(jié)點(diǎn)開始姓蜂，對節(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為節(jié)點(diǎn)的特征医吊，由該特征的不同取值建立子節(jié)點(diǎn)：再對子節(jié)點(diǎn)遞歸的調(diào)用以上方法钱慢，構(gòu)建決策樹：直到所有的特征信息增益均很小或沒有特征可以選擇為止。
（2）優(yōu)點(diǎn)
a) 假設(shè)空間包含所有的決策樹卿堂，搜索空間完整束莫。
b) 健壯性好，不受噪聲影響。
c) 可以訓(xùn)練缺少屬性值的實(shí)例麦箍。
（3）缺點(diǎn)
a) ID3只考慮分類型的特征漓藕，沒有考慮連續(xù)特征，比如長度挟裂，密度都是連續(xù)值享钞，無法在ID3運(yùn)用。這大大限制了ID3的用途诀蓉。
b) ID3算法對于缺失值沒有進(jìn)行考慮栗竖。
c) 沒有考慮過擬合的問題。
d) ID3算法在選擇根節(jié)點(diǎn)和各內(nèi)部節(jié)點(diǎn)中的分支屬性時(shí)渠啤，采用信息增益作為評價(jià)標(biāo)準(zhǔn)狐肢。信息增益的缺點(diǎn)是傾向于選擇取值較多的屬性，在有些情況下這類屬性可能不會提供太多有價(jià)值的信息沥曹。
e) 劃分過程會由于子集規(guī)模過小而造成統(tǒng)計(jì)特征不充分而停止份名。
2、C4.5
（1）簡述
C4.5算法與ID3算法決策樹的生成過程相似妓美，C4.5算法對ID3算法進(jìn)行了改進(jìn)僵腺。它是用信息增益率（比）來 選擇特征。
（2）優(yōu)點(diǎn)
a) C4.5是ID3的改進(jìn)壶栋，采用信息增益率進(jìn)行特征選擇辰如。
b) 為了處理連續(xù)值，C4.5采用單點(diǎn)離散化的思想贵试，用信息增益率來進(jìn)行連續(xù)值特征的屬性值選擇琉兜。
（3）缺點(diǎn)
a) C4.5時(shí)間耗費(fèi)大
b) C4.5沒解決回歸問題
3、CART
（1）簡述
使用CART（分類回歸樹）來解決回歸問題毙玻，CART是一顆二叉樹豌蟋，哪怕某個(gè)特征有多類（年齡有青年，中年淆珊，老年）夺饲，也是進(jìn)行二分叉（青年一個(gè)叉，中年老年一個(gè)叉）再繼續(xù)分下去施符。
而之后樹相關(guān)的集成算法如隨機(jī)森林往声，GDBT，XGBoost中的弱分類器用的都是CART戳吝。
關(guān)于分類問題浩销，CART和ID3, C4.5的思想是一樣的，用損失函數(shù)來劃分特征听哭，選擇特征劃分的屬性值慢洋。只是ID3塘雳，C4.5用的是信息增益，CART用的是基尼指數(shù)普筹。
（2）優(yōu)點(diǎn)
a) 可以處理連續(xù)型屬性
b) 將信息增益改為信息增益比败明，以解決偏向取值較多的屬性的問題
（3）缺點(diǎn)
a) C4.5在ID3的基礎(chǔ)上進(jìn)行了改進(jìn)，如選擇信息增益率作為損失函數(shù)太防，采用單點(diǎn)離散化對連續(xù)型特征進(jìn)行處理妻顶，但是不能處理回歸問題。
b) CART對于分類問題選用基尼指數(shù)作為損失函數(shù)蜒车，對于回歸問題使用平方誤差作為損失函數(shù)讳嘱，一個(gè)結(jié)點(diǎn)里的預(yù)測值采用的是這個(gè)結(jié)點(diǎn)里數(shù)據(jù)結(jié)果的平均數(shù)（比如房價(jià)）。
這三類算法都是貪心算法酿愧，找到的是局部最優(yōu)分裂方法沥潭。
總結(jié)一個(gè)表：看該如何選擇以上算法？
