1. 什么是決策樹
決策樹是基于樹結(jié)構(gòu)進(jìn)行決策铡买。決策樹學(xué)習(xí)的目的是產(chǎn)生一棵泛化能力強(qiáng)框都，處理未見示例能力強(qiáng)的決策樹搬素。
基本流程遵循分而治之。
決策樹的基本算法
2.劃分選擇
2.1 信息增益
信息熵
 = -\sum_{k=1}^{|y|} p_klog_2p_k)
pk 表示D中k類占的比例
Ent（D）越小表示純度越高
信息增益
 =Ent(D) - \sum_{v=1}{V}\frac{|Dv|}{|D|}Ent(D^v))
ID3
信息增益準(zhǔn)則對(duì)可取數(shù)目較多的屬性有所偏好
信息增益越大意味著使用屬性a來進(jìn)行劃分所獲得純度提升越大
2.2增益率
 = \frac{Gain(D,a)}{IV(a)} )
=-\sum_{v=1}^Vlog_2\frac{|Dv|}{|D|})
在增益率準(zhǔn)則對(duì)取值數(shù)目較少的屬性有所偏好
C4.5使用啟發(fā)式魏保，先從候選劃分屬性中找出信息增益高于平均水平的屬性熬尺，再從中選擇增益率最高的
2.3 基尼指數(shù)
基尼指數(shù)越小純度越高，反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個(gè)樣本其類別不一樣的概率谓罗。
屬性a的基尼指數(shù)
 = \sum_{v=1}{V}\frac{Dv}{D}Gini(D^v))
3. 剪枝處理
對(duì)付過擬合
3.1 預(yù)剪枝
在決策樹的生成過程中粱哼，對(duì)每個(gè)節(jié)點(diǎn)在劃分前進(jìn)行估計(jì)，若當(dāng)前節(jié)點(diǎn)的劃分不能帶來決策樹泛化能性能的提升則停止劃分并將當(dāng)前節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)檩咱。
預(yù)剪枝可能造成欠擬合
3.2 后剪枝
從訓(xùn)練集生成一棵完整的決策樹揭措，然后自底向上的對(duì)非葉節(jié)點(diǎn)進(jìn)行考察，若將該節(jié)點(diǎn)對(duì)應(yīng)的字?jǐn)?shù)替換為葉節(jié)點(diǎn)能帶來決策樹泛化能力提升刻蚯，則將該子樹替換為葉節(jié)點(diǎn)绊含。
后剪枝欠擬合風(fēng)險(xiǎn)很小，泛化性能往往優(yōu)于預(yù)剪枝
4.連續(xù)和缺失值
采用二分法對(duì)連續(xù)值進(jìn)行處理
讓同一個(gè)樣本以不同的概率進(jìn)入不同的子節(jié)點(diǎn)
