定義：
一顆[決策樹]包含一個(gè)根節(jié)點(diǎn)、若干個(gè)內(nèi)部節(jié)點(diǎn)和若干個(gè)葉節(jié)點(diǎn)；
葉節(jié)點(diǎn)：對應(yīng)決策結(jié)果，即樣本的label
根 + 內(nèi)部節(jié)點(diǎn)：對應(yīng)一個(gè)分割[數(shù)據(jù)集]方法，根據(jù)該方法將節(jié)點(diǎn)對應(yīng)的數(shù)據(jù)集劃分到子節(jié)點(diǎn)中。
根到葉節(jié)點(diǎn)的路徑：對應(yīng)一個(gè)判定序列

image.png

流程：
和遞歸算法類似，先確定退出條件（設(shè)置葉節(jié)點(diǎn)）：

image.png

該節(jié)點(diǎn)中數(shù)據(jù)集的label相同
屬性集為空集，或者數(shù)據(jù)集的屬性值相同
該節(jié)點(diǎn)的數(shù)據(jù)集為空集
條件1：label都相同了，直接將葉節(jié)點(diǎn)標(biāo)記為該label即可
條件2：有數(shù)據(jù)，但無法根據(jù)屬性繼續(xù)劃分。該葉節(jié)點(diǎn)label少數(shù)服從多數(shù)
條件3：無數(shù)據(jù)，根據(jù)父節(jié)點(diǎn)的樣本label 少數(shù)服從多數(shù)
每次遞歸最核心的問題是 選取怎樣劃分規(guī)則，來劃分當(dāng)前節(jié)點(diǎn)對應(yīng)的數(shù)據(jù)集

信息熵：
本質(zhì)：越混亂（隨機(jī)事件越不確定），信息量越大

image.png

信息增率
存在一個(gè)badcase: 若每個(gè)樣本在屬性A上取值都不同，此時(shí)，根據(jù)該屬性A劃分，信息增益最大。但這樣泛化性太差

4.3 剪枝處理

目標(biāo)：降低過擬合，提高泛化性。

方式：根據(jù)在驗(yàn)證集上表現(xiàn)判斷是否剪枝。

4.3.1 預(yù)剪枝

思想：在處理非葉節(jié)點(diǎn)時(shí)，判斷劃分該節(jié)點(diǎn)能否帶來性能提升，有提升則劃分，沒有則不劃分。

優(yōu)點(diǎn)：只用一次建樹，速度快

缺點(diǎn)：存在欠擬合風(fēng)險(xiǎn)

image.png

后剪枝
思想：先生成決策樹，從底向上判斷是否要將非葉節(jié)點(diǎn)替換為葉節(jié)點(diǎn)。
優(yōu)點(diǎn)：相比預(yù)剪枝，會保留更多枝，學(xué)習(xí)更充分
缺點(diǎn)：訓(xùn)練開銷大