以下內(nèi)容參考《機(jī)器學(xué)習(xí)》周志華（西瓜書）以及《機(jī)器學(xué)習(xí)公式詳解》datawhale（南瓜書）
什么是決策樹叠赦？
一般的，一棵決策樹包含一個(gè)根結(jié)點(diǎn)（包含樣本全集西疤，對(duì)應(yīng)于一個(gè)屬性測(cè)試）币绩，若干內(nèi)部節(jié)點(diǎn)（對(duì)應(yīng)于一個(gè)屬性測(cè)試）與若干葉節(jié)點(diǎn)（對(duì)應(yīng)于決策結(jié)果）。
從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑對(duì)應(yīng)一個(gè)判定測(cè)試序列瘸羡。如：
如何生成？
決策樹構(gòu)建的基本步驟如下：
1. 開始犹赖，所有記錄看作一個(gè)節(jié)點(diǎn)
2. 遍歷每個(gè)變量的每一種分割方式队他，找到最好的分割點(diǎn)
3. 分割成兩個(gè)節(jié)點(diǎn)N1和N2
4. 對(duì)N1和N2分別繼續(xù)執(zhí)行2-3步，直到每個(gè)節(jié)點(diǎn)足夠“純”為止峻村。
劃分選擇
信息熵：度量樣本集合純度最常用的一種指標(biāo)麸折，值越小，純度越高粘昨。
信息增益
對(duì)于屬性a的每個(gè)可能的分支節(jié)點(diǎn)v张肾，獲得的信息增益為：
(樣本數(shù)越多的分支節(jié)點(diǎn)的影響越大)芭析，信息增益越大，意味著這個(gè)劃分的純度提升越大吞瞪。
信息增益準(zhǔn)則（選擇最大的信息增益屬性）劃分舉例：ID3決策樹算法
由于類內(nèi)越純馁启，增益越大，可以發(fā)現(xiàn)信息增益準(zhǔn)則對(duì)可取數(shù)目較多的屬性有所偏好芍秆。
增益率
減少數(shù)目較多的屬性偏好进统。
定義增益率如下：
需要注意的是浪听，增益率準(zhǔn)則對(duì)可取值數(shù)目較少的屬性有所偏好螟碎。
增益率劃分舉例：C4.5決策樹算法。不過(guò)C4.5不是直接選擇增益率最大的候選劃分屬性迹栓，而是先從候選劃分屬性中找出信息增益水平高于平均水平的屬性掉分，再?gòu)闹羞x擇增益率最高的。
基尼系數(shù)
基尼系數(shù)越小克伊，數(shù)據(jù)集純度越高（反應(yīng)隨機(jī)抽取兩個(gè)樣本類別標(biāo)記不一致的概率）酥郭。
屬性a的基尼系數(shù)
基尼指數(shù)劃分：CART決策樹
剪枝處理
主動(dòng)去掉一些分支來(lái)降低過(guò)擬合風(fēng)險(xiǎn)。
預(yù)剪枝
劃分前估計(jì)愿吹，若當(dāng)前結(jié)點(diǎn)的劃分不能帶來(lái)決策樹泛化性能的提升不从，則停止劃分且當(dāng)前結(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)。
缺點(diǎn)：基于貪心犁跪，帶來(lái)欠擬合風(fēng)險(xiǎn)椿息。
有點(diǎn)：降低過(guò)擬合風(fēng)險(xiǎn)歹袁，減少開銷。
后剪枝
自底向上的對(duì)完整的樹的非葉節(jié)點(diǎn)進(jìn)行考察寝优，看替換為葉節(jié)點(diǎn)是否能帶來(lái)決策樹泛化性能的提升条舔。
缺點(diǎn)：開銷大。
優(yōu)點(diǎn)：欠擬合風(fēng)險(xiǎn)小乏矾。
連續(xù)與缺失值
連續(xù)值
連續(xù)屬性離散化（C4.5應(yīng)用）：兩個(gè)排序后相鄰連續(xù)值的中位數(shù)劃分為兩個(gè)區(qū)間孟抗。
缺失值
擴(kuò)展信息增益計(jì)算方式，講缺失樣本概率劃分到不同子節(jié)點(diǎn)中钻心。（C4.5應(yīng)用）
多變量決策樹
非葉節(jié)點(diǎn)對(duì)于屬性的線性組合進(jìn)行測(cè)試凄硼，如：
