前言
決策樹是一種簡單高效并且具有強(qiáng)解釋性的模型蹈丸，廣泛應(yīng)用于數(shù)據(jù)分析領(lǐng)域套媚。其本質(zhì)是一顆由多個(gè)判斷節(jié)點(diǎn)組成的樹，如：
在使用模型進(jìn)行預(yù)測時(shí)扮碧，根據(jù)輸入?yún)?shù)依次在各個(gè)判斷節(jié)點(diǎn)進(jìn)行判斷游走趟章，最后到葉子節(jié)點(diǎn)即為預(yù)測結(jié)果。
如何構(gòu)造決策樹
決策樹算法的核心是通過對數(shù)據(jù)的學(xué)習(xí)慎王，選定判斷節(jié)點(diǎn)蚓土，構(gòu)造一顆合適的決策樹。
假設(shè)我們從用戶行為日志中整理出如下數(shù)據(jù)：
我們的目的是要利用這些數(shù)據(jù)赖淤，訓(xùn)練決策樹模型蜀漆，模型訓(xùn)練好后，我們就可以通過任意給定的用戶來源網(wǎng)站咱旱、位置确丢、是否閱讀過 FAQ绷耍、瀏覽網(wǎng)頁數(shù)信息，預(yù)測該用戶是否會進(jìn)行付費(fèi)以及付費(fèi)類型鲜侥，供運(yùn)營使用褂始。
選擇合適的拆分條件
我們知道決策樹是由一個(gè)個(gè)判斷節(jié)點(diǎn)組成，每經(jīng)過一個(gè)判斷節(jié)點(diǎn)數(shù)據(jù)就會被拆分一次描函。上面數(shù)據(jù)中有4種屬性崎苗，每種屬性下面有多種值，我們可以按位置是否來自「浙江」進(jìn)行拆分舀寓，拆分結(jié)果為：
我們「拍腦袋」進(jìn)行了一次拆分胆数，到底這么拆分合不合適，是不是最佳互墓，我們需要量化指標(biāo)來進(jìn)行評價(jià)必尼，在決策樹算法中，我們通過基尼不純度或者熵來對一個(gè)集合進(jìn)行的有序程度進(jìn)行量化篡撵，然后引入信息增益概念對一次拆分進(jìn)行量化評價(jià)判莉。下面依次介紹。
基尼不純度
基尼不純度是指將來自集合中的某種結(jié)果隨機(jī)應(yīng)用于集合中某一數(shù)據(jù)項(xiàng)的預(yù)期誤差率酸休。如何集合中的每一個(gè)數(shù)據(jù)項(xiàng)都屬于同一分類骂租，那么推測的結(jié)果總會是正確的，因此誤差率是 0斑司；如果有 4 種可能的結(jié)果均勻分布在集合內(nèi)渗饮，出錯(cuò)可能性是75%，基尼不純度為 0.75宿刮。該值越高互站，說明拆分的越不理想，如果該值為 0僵缺，說明完美拆分胡桃。java 實(shí)現(xiàn)代碼如下：
public static float getCiniimpurity(String[] rows){
float total = rows.length;
//將[a,a,b,c]轉(zhuǎn)化成[2,1,1]
Integer[] uniqueRows = getUniqueRows(rows);
float score = 0.0f;
for(int k1=0;k1<uniqueRows.length;k1++){
float p1 = uniqueRows[k1]/total;
for(int k2=0;k2<uniqueRows.length;k2++){
if(k2 == k1) continue;
float p2 = uniqueRows[k2]/total;
score += p1 * p2;
}
}
return score;
}
熵
熵是信息論中的概念，用來表示集合的無序程度磕潮，熵越大表示集合越混亂翠胰，反之則表示集合越有序。熵的計(jì)算公式為：
E = -P * log2P
java 代碼實(shí)現(xiàn)如下：
public static double getEntropy(String[] rows){
float total = rows.length;
//將[a,a,b,c]轉(zhuǎn)化成[2,1,1]
Integer[] uniqueRows = getUniqueRows(rows);
double ent = 0.0;
for(int i=0;i<uniqueRows.length;i++){
float p = uniqueRows[i]/total;
ent = ent - p * (Math.log(p)/Math.log(2));
}
return ent;
}
基尼不純度與熵對比
兩者主要區(qū)別在于自脯，熵到達(dá)峰值的過程相對慢一些之景。因此熵對混亂集合的「判罰」往往更重一些。通常情況下膏潮，熵的使用更加頻繁锻狗。
信息增益
假設(shè)集合 U，一次拆分后變?yōu)榱藘蓚€(gè)集合 u1 和 u2 ，則有：
信息增益 = E(U) - (Pu1 x E(u1) + Pu2 x E(u2))
E 可以是基尼不純度或熵轻纪。
使用 Pu1 和 Pu2 是為了得到拆分后兩個(gè)集合基尼不純度或熵的加權(quán)平均油额，其中 :
- Pu1 = Size(u1) / Size(U)
- Pu2 = Size(u2) / Size(U)
信息增益越大，說明整個(gè)集合從無序到有序的速度越快刻帚，本次拆分越有效潦嘶。
構(gòu)造決策樹
我們已經(jīng)可以通過信息增益量化一次拆分的結(jié)果好壞，下一步就是構(gòu)造決策樹我擂，主要步驟如下：
- 遍歷每個(gè)決策條件（如：位置衬以、來源網(wǎng)站）缓艳，對結(jié)果集進(jìn)行拆分
- 計(jì)算該決策條件下校摩，所有可能的拆分情況的信息增益，信息增益最大的拆分為本次最優(yōu)拆分
- 遞歸執(zhí)行1阶淘、2兩步衙吩，直至信息增益<=0
執(zhí)行完上述步驟后，就構(gòu)造出了一顆決策樹溪窒，如圖：
決策樹剪枝
為什么要剪枝
訓(xùn)練出得決策樹存在過度擬合現(xiàn)象——決策樹過于針對訓(xùn)練的數(shù)據(jù)坤塞，專門針對訓(xùn)練集創(chuàng)建出來的分支，其熵值可能會比真實(shí)情況有所降低澈蚌。
如何剪枝
人工設(shè)置一個(gè)信息增益的閥值摹芙，自下而上遍歷決策樹，將信息增益低于該閥值的拆分進(jìn)行合并
處理缺失數(shù)據(jù)
決策樹模型還有一個(gè)很大的優(yōu)勢宛瞄，就是可以容忍缺失數(shù)據(jù)浮禾。如果決策樹中某個(gè)條件缺失，可以按一定的權(quán)重分配繼續(xù)往以后的分支走份汗，最終的結(jié)果可能有多個(gè)盈电，每個(gè)結(jié)果又一定的概率，即：
最終結(jié)果=某個(gè)分支的結(jié)果 x 該分支的權(quán)重(該分支下的結(jié)果數(shù)/總結(jié)果數(shù))
處理數(shù)值型數(shù)據(jù)
決策樹主要解決分類問題（結(jié)果是離散數(shù)據(jù)）杯活，如果結(jié)果是數(shù)字匆帚，不會考慮這樣的事實(shí)：有些數(shù)字相差很近，有些數(shù)字相差很遠(yuǎn)旁钧。為了解決這個(gè)問題吸重，可以用方差來代替熵或基尼不純度。
結(jié)語
本文簡單介紹了決策樹算法歪今，該算法雖然簡單嚎幸，但是在很多場景能取得非常好的效果，值得讀者一試彤委。另外鞭铆，從決策樹發(fā)展出了更為高級復(fù)雜的隨機(jī)森林，如果有興趣讀者可以去深入了解。
