建立決策樹的邏輯

一個小故事

zenRRan二十出頭了，到了婚配的年齡啦。又因為家是名門望族，所以一堆人搶著想來應聘配偶的職位。但是zenRRan比較挑剔，必須達到他的要求才能有機會成為他的另一半，要求為：

1. 性別女，非女性不要

于是刷刷刷走了一半人，剩下的全部為女性。

2.身高必須要在150-165cm

于是又走了一堆人，剩下的為160-165cm之間的女生。

3.性格要溫柔賢惠

聽到這些，又走了一些人，最后留下的極為最后的應聘候選人。

上述過程可以用樹來表示：

像上面的這樣的二叉樹狀決策在我們生活中很常見，而這樣的選擇方法就是決策樹。機器學習的方法就是通過平時生活中的點點滴滴經(jīng)驗轉(zhuǎn)化而來的。

建立決策樹的邏輯

正如上述樹狀圖所示，我們最終會通過特征：

性別，身高，性格

得到了4種分類結(jié)果，都存在于葉子節(jié)點。

非女生，身高不符合的女生，身高符合性格不符合的女生，都符合的最佳候選人。

現(xiàn)在我們來回想下上面的建立決策的流程：

首先在一群給定數(shù)據(jù)（應聘者）中，我們先通過一個特征（性別）來進行二分類。當然選取這個特征也是根據(jù)實際情況而定的，比如zenRRan選取第一個條件為性別的原因是，來的男的太多了，比例占的有點大，所以先給他分成類放到一邊，剩下的更加好分類而已。

然后，對葉子節(jié)點（那些還想繼續(xù)分類的節(jié)點們）繼續(xù)進行上述的流程。

那么怎么選取特征作為當前的分類依據(jù)呢？有兩種方法：

信息熵和基尼系數(shù)。

信息熵

熵這個概念想必大家都不陌生，熵用來表示數(shù)據(jù)的確定性程度。研究一個詞，就要從他的來源說起，熵，來自熱動力學，表示原子或者一個事物的穩(wěn)定程度，溫度越高，原子越活躍，越不穩(wěn)定；反而溫度越低，就越穩(wěn)定，越保持不動。所以慢慢的這個概念被用到各個方向，也就有了新的定義詞匯，但是它的本意沒變，就是穩(wěn)定程度大小的表示。

那么在決策樹里面，我們用的是一種熵，信息熵，來表示類別的穩(wěn)定程度。

公式為：

注：p為一個類的占比

什么意思呢？具體用數(shù)字表示下：

比如一個分類結(jié)果由三個類組成，占比為1/3 1/31/3，那么它們的信息熵為:

如果占比為1/10 2/10 7/10，那么它的信息熵為：

那再舉一個極端情況，也就是我們想要得到的類，只包含一種情況，其他的比例為0，那么比如占比情況為：1 0 0，那么它的信息熵為：

我們會發(fā)現(xiàn)一個分類結(jié)果里，里面的類別比例越是接近，信息熵也就越大，反之越是趨向于一個值，越是小，會達到0。

如果將所有的情況考慮在內(nèi)的話，就能繪成一個圖（為了好畫，以該分好的類別里有兩種事物為例）：

我們會發(fā)現(xiàn)，當占比為0.5的時候，也就是另一個事物的占比也是0.5的時候信息熵最高，當傾向于一個事物的時候，信息熵最小，無限接近并達到0。

為什么都占比一樣的時候信息熵最大呢？也就是說最不穩(wěn)定呢？因為當每個事物都占比一樣的時候，一個小事物進來，不清楚它到底屬于哪一類；如果只有一類事物或者一類事物居多數(shù)，那么也就比較明確該屬于哪類，也就穩(wěn)定，確定了。

那么怎么用呢？

我們通過計算機分類，因為有很多種分類情況，不是每一次分類都是直接將同一類分到一個類別里，而是將該分好的兩個類的信息熵總和最小為依據(jù)，不斷地通過暴力尋找最佳選擇。然后遞歸進行對分好類的數(shù)據(jù)進行再分類。

基尼系數(shù)

基尼系數(shù)和信息熵在這里具有同樣的性質(zhì)。先看看它的公式：

公式看不出什么特色之處，就繼續(xù)用數(shù)字展示下：

比如依然是三分類，類別占比為1/3 1/3 1/3，基尼系數(shù)為:

類別占比為1/10 2/10 7/10，基尼系數(shù)為：

如果是極端情況下占比為1 0 0，那么基尼系數(shù)為;

我們根據(jù)公式其實就能看出來，平方的函數(shù)為凸函數(shù)，而該公式在都相等的時候值最大。

代碼實現(xiàn)

再重說下流程：

通過對每個特征進行嘗試分類，記錄當前分類最小的信息熵（或基尼系數(shù)）的特征為當前分類結(jié)果。

選取一些點，初始化數(shù)據(jù)：

X為二維平面的數(shù)據(jù)點，Y為類別。

數(shù)據(jù)點分布情況：

信息熵函數(shù)：

基尼系數(shù)函數(shù)：

二者使用一個即可。

下面是一個分類核心的流程：

文字描述為：

對數(shù)據(jù)點的特征0維進行嘗試分類，先按照0維數(shù)據(jù)排序，然后取每相鄰的中點值，然后以0維該值分界線，處于分界線兩側(cè)的數(shù)據(jù)分別求信息熵（或基尼系數(shù)），如果比之前的小，這就保存該值和當前維度。然后選取第1維進行相同操作，最終的最小信息熵（或基尼系數(shù)）最小對應的值為本次分類的結(jié)果。

但是這個僅僅是一層分類，如果還子節(jié)點還有要分類的數(shù)據(jù)，繼續(xù)上述操作即可。

分類代碼：

分類效果流程圖：

決策樹第一層分類結(jié)果為：

當前線為最佳值，1維的數(shù)據(jù)就是分過的，但是沒有當前的值好，也就沒顯示。

現(xiàn)在已經(jīng)分出了兩類，左邊的紅色和右邊的綠色+藍色。那么還要對上述的右邊進行分類，獲取該數(shù)據(jù)，并且繼續(xù)進行分類，分類流程圖為：

最終得出的分類結(jié)果為上述兩條線。其中粉色為第一層分類，紫色為第二層分類。

批判性思維看決策樹

看到上述的分類結(jié)果，其實你心里也想到了決策樹的缺點了，就是分類總是橫平豎直的，不能是曲線。

比如

該四個數(shù)據(jù)的分類最佳理想條件下應該為上述紫色線條，但是決策樹的結(jié)果為;

如果存在數(shù)據(jù)在：

明明應該屬于藍色點的，但是被劃分到紅色點里。

所以可以看出，決策樹對數(shù)據(jù)的要求是是苛刻的。

另一個問題是，決策樹的學習問題，從上述代碼實現(xiàn)過程能夠看出來，可以說是暴力求解了。

責任編輯：lq