決策樹(shù)是一種簡(jiǎn)單高效并且具有強(qiáng)解釋性的模型，廣泛應(yīng)用于數(shù)據(jù)分析領(lǐng)域。其本質(zhì)是一顆由多個(gè)判斷節(jié)點(diǎn)組成的樹(shù)，如：
在使用模型進(jìn)行預(yù)測(cè)時(shí)，根據(jù)輸入?yún)?shù)依次在各個(gè)判斷節(jié)點(diǎn)進(jìn)行判斷游走，最后到葉子節(jié)點(diǎn)即為預(yù)測(cè)結(jié)果。
如何構(gòu)造決策樹(shù)決策樹(shù)算法的核心是通過(guò)對(duì)數(shù)據(jù)的學(xué)習(xí)，選定判斷節(jié)點(diǎn)，構(gòu)造一顆合適的決策樹(shù)。
假設(shè)我們從用戶(hù)行為日志中整理出如下數(shù)據(jù)：
原始數(shù)據(jù)
我們的目的是要利用這些數(shù)據(jù)，訓(xùn)練決策樹(shù)模型，模型訓(xùn)練好后，我們就可以通過(guò)任意給定的用戶(hù)來(lái)源網(wǎng)站、位置、是否閱讀過(guò) FAQ、瀏覽網(wǎng)頁(yè)數(shù)信息，預(yù)測(cè)該用戶(hù)是否會(huì)進(jìn)行付費(fèi)以及付費(fèi)類(lèi)型，供運(yùn)營(yíng)使用。
選擇合適的拆分條件我們知道決策樹(shù)是由一個(gè)個(gè)判斷節(jié)點(diǎn)組成，每經(jīng)過(guò)一個(gè)判斷節(jié)點(diǎn)數(shù)據(jù)就會(huì)被拆分一次。上面數(shù)據(jù)中有4種屬性，每種屬性下面有多種值，我們可以按位置是否來(lái)自「浙江」進(jìn)行拆分，拆分結(jié)果為：
按是否來(lái)自「浙江」拆分結(jié)果
我們「拍腦袋」進(jìn)行了一次拆分，到底這么拆分合不合適，是不是最佳，我們需要量化指標(biāo)來(lái)進(jìn)行評(píng)價(jià)，在決策樹(shù)算法中，我們通過(guò) 基尼不純度 或者 熵 來(lái)對(duì)一個(gè)集合進(jìn)行的有序程度進(jìn)行量化，然后引入 信息增益 概念對(duì)一次拆分進(jìn)行量化評(píng)價(jià)。下面依次介紹。
基尼不純度基尼不純度是指將來(lái)自集合中的某種結(jié)果隨機(jī)應(yīng)用于集合中某一數(shù)據(jù)項(xiàng)的預(yù)期誤差率。如何集合中的每一個(gè)數(shù)據(jù)項(xiàng)都屬于同一分類(lèi)，那么推測(cè)的結(jié)果總會(huì)是正確的，因此誤差率是 0；如果有 4 種可能的結(jié)果均勻分布在集合內(nèi)，出錯(cuò)可能性是75%，基尼不純度為 0.75。該值越高，說(shuō)明拆分的越不理想，如果該值為 0，說(shuō)明完美拆分。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;
}
熵是信息論中的概念，用來(lái)表示集合的無(wú)序程度，熵越大表示集合越混亂，反之則表示集合越有序。熵的計(jì)算公式為：
E = -P * log 2 P
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á)峰值的過(guò)程相對(duì)慢一些。因此熵對(duì)混亂集合的「判罰」往往更重一些。通常情況下，熵的使用更加頻繁。
信息增益假設(shè)集合 U，一次拆分后變?yōu)榱藘蓚€(gè)集合 u 1 和 u 2 ，則有：
信息增益 = E(U) - (P u1 x E(u 1 ) P u2 x E(u 2 ))
E 可以是基尼不純度或熵。
使用 P u1 和 P u2 是為了得到拆分后兩個(gè)集合基尼不純度或熵的加權(quán)平均，其中 :
P u1 = Size(u1) / Size(U)
P u2 = Size(u2) / Size(U)
信息增益越大，說(shuō)明整個(gè)集合從無(wú)序到有序的速度越快，本次拆分越有效。
構(gòu)造決策樹(shù)我們已經(jīng)可以通過(guò)信息增益量化一次拆分的結(jié)果好壞，下一步就是構(gòu)造決策樹(shù)，主要步驟如下：
遍歷每個(gè)決策條件（如：位置、來(lái)源網(wǎng)站），對(duì)結(jié)果集進(jìn)行拆分
計(jì)算該決策條件下，所有可能的拆分情況的信息增益，信息增益最大的拆分為本次最優(yōu)拆分
遞歸執(zhí)行1、2兩步，直至信息增益<=0
執(zhí)行完上述步驟后，就構(gòu)造出了一顆決策樹(shù)，如圖：
決策樹(shù)
決策樹(shù)剪枝為什么要剪枝
訓(xùn)練出得決策樹(shù)存在過(guò)度擬合現(xiàn)象——決策樹(shù)過(guò)于針對(duì)訓(xùn)練的數(shù)據(jù)，專(zhuān)門(mén)針對(duì)訓(xùn)練集創(chuàng)建出來(lái)的分支，其熵值可能會(huì)比真實(shí)情況有所降低。
如何剪枝
人工設(shè)置一個(gè)信息增益的閥值，自下而上遍歷決策樹(shù)，將信息增益低于該閥值的拆分進(jìn)行合并
處理缺失數(shù)據(jù)決策樹(shù)模型還有一個(gè)很大的優(yōu)勢(shì)，就是可以容忍缺失數(shù)據(jù)。如果決策樹(shù)中某個(gè)條件缺失，可以按一定的權(quán)重分配繼續(xù)往以后的分支走，最終的結(jié)果可能有多個(gè)，每個(gè)結(jié)果又一定的概率，即：
最終結(jié)果=某個(gè)分支的結(jié)果 x 該分支的權(quán)重(該分支下的結(jié)果數(shù)/總結(jié)果數(shù))
處理數(shù)值型數(shù)據(jù)決策樹(shù)主要解決分類(lèi)問(wèn)題（結(jié)果是離散數(shù)據(jù)），如果結(jié)果是數(shù)字，不會(huì)考慮這樣的事實(shí)：有些數(shù)字相差很近，有些數(shù)字相差很遠(yuǎn)。為了解決這個(gè)問(wèn)題，可以用方差來(lái)代替熵或基尼不純度。
結(jié)語(yǔ)本文簡(jiǎn)單介紹了決策樹(shù)算法，該算法雖然簡(jiǎn)單，但是在很多場(chǎng)景能取得非常好的效果，值得讀者一試。另外，從決策樹(shù)發(fā)展出了更為高級(jí)復(fù)雜的 隨機(jī)森林 ，如果有興趣讀者可以去深入了解。
聯(lián)系客服
