又黄又猛一区,欧洲一区午夜,亚洲一区二区综合

關(guān)于經(jīng)典決策樹算法ID3、C4.5及CART樹的部分細(xì)節(jié)梳理。

決策樹

決策樹可以從兩個(gè)視角理解。

If-Then規(guī)則的集合
定義在特征空間與類空間上的條件概率分布

algo-decision-tree-conditional-probability

經(jīng)典決策樹對(duì)比

經(jīng)典決策樹有ID3、C4.5以及CART樹，其功能和學(xué)習(xí)過程各有異同，簡(jiǎn)單對(duì)比。

算法	分裂標(biāo)準(zhǔn)	樹類型	特征類型	缺失	剪枝	任務(wù)
ID3	信息增益	多叉	離散	No	無剪枝	分類
C4.5	信息增益比	多叉	離散/連續(xù)	Yes	有剪枝	分類
CART	基尼系數(shù)	二叉	離散/連續(xù)	Yes	有剪枝	分類/回歸

一些其它差異

C4.5優(yōu)化ID3，主要體現(xiàn)在節(jié)點(diǎn)分支計(jì)算方式，解決ID3偏向取值較多的屬性
特征使用，多分的ID3和C4.5分類變量只使用一次，CART可多次使用
CART回歸任務(wù)，用平方誤差最小準(zhǔn)則選特征，用樣本點(diǎn)均值做回歸預(yù)測(cè)值

C4.5如何處理連續(xù)特征

連續(xù)值不再有限，不能直接取其可能取值劃分，可采用二分法(bi-partition)。給定樣本集 $D$ 和連續(xù)屬性 $a$ ，其有 $n$ 個(gè)不同取值，從小到大排序得 $\{a^1, a^2, \dots, a^n\}$ ，則劃分點(diǎn)可以依次選取測(cè)試

$T_a=\big\{\frac{a^i + a^{i+1}}{2}|1\le i\le n-1\big\}$

注意，與離散屬性不同，若當(dāng)前節(jié)點(diǎn)劃分屬性為連續(xù)特征，該屬性還可作其為后代節(jié)點(diǎn)的劃分屬性。

如何剪枝

一般分為預(yù)剪枝和后剪枝兩種。

預(yù)剪枝：決策樹生成過程中，在節(jié)點(diǎn)劃分前評(píng)估，若當(dāng)前節(jié)點(diǎn)劃分不能帶來泛化性能提升，則停止劃分并將當(dāng)前節(jié)點(diǎn)標(biāo)記為葉子節(jié)點(diǎn)
后剪枝：對(duì)完全生長(zhǎng)的決策樹，自底向上對(duì)非葉子節(jié)點(diǎn)考察，若將節(jié)點(diǎn)對(duì)應(yīng)子樹替換為葉子節(jié)點(diǎn)能帶來泛化性能提升，則將子樹替換為葉子節(jié)點(diǎn)

預(yù)剪枝降低過擬合風(fēng)險(xiǎn)，基于“貪心思想”，也會(huì)帶來欠擬合的風(fēng)險(xiǎn)；后剪枝欠擬合風(fēng)險(xiǎn)小，但訓(xùn)練時(shí)間開銷比未剪枝或預(yù)剪枝大的多。

如何處理缺失值

在XGBoost里，做法是這樣的。在每個(gè)節(jié)點(diǎn)上都會(huì)將含缺失值樣本往左右分支各倒流一次，然后計(jì)算對(duì)Objective的影響，選效果好的方向，作為缺失值應(yīng)該流向的方向。

比如特征A(A>0或A<=0或A=null)，那么首先忽略含缺失值樣本，正常樣本導(dǎo)流到到左子樹與右子樹；將含缺失值樣本導(dǎo)向左子樹，計(jì)算Objective_L；將含缺失值樣本導(dǎo)向右子樹，計(jì)算Objective_R。選擇Objective較小的方向，作為缺失值應(yīng)該分流的方向。