一個(gè)小故事

zenRRan二十出頭了，到了婚配的年齡啦。又因?yàn)榧沂敲T(mén)望族，所以一堆人搶著想來(lái)應(yīng)聘配偶的職位。但是zenRRan比較挑剔，必須達(dá)到他的要求才能有機(jī)會(huì)成為他的另一半，要求為：

1. 性別女，非女性不要

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

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

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

3.性格要溫柔賢惠

聽(tīng)到這些，又走了一些人，最后留下的極為最后的應(yīng)聘候選人。

上述過(guò)程可以用樹(shù)來(lái)表示：

像上面的這樣的二叉樹(shù)狀決策在我們生活中很常見(jiàn)，而這樣的選擇方法就是決策樹(shù)。機(jī)器學(xué)習(xí)的方法就是通過(guò)平時(shí)生活中的點(diǎn)點(diǎn)滴滴經(jīng)驗(yàn)轉(zhuǎn)化而來(lái)的。

建立決策樹(shù)的邏輯

正如上述樹(shù)狀圖所示，我們最終會(huì)通過(guò)特征：

性別，身高，性格

得到了4種分類(lèi)結(jié)果，都存在于葉子節(jié)點(diǎn)。

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

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

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

然后，對(duì)葉子節(jié)點(diǎn)（那些還想繼續(xù)分類(lèi)的節(jié)點(diǎn)們）繼續(xù)進(jìn)行上述的流程。

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

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

信息熵

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

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

公式為：

注：p為一個(gè)類(lèi)的占比

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

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

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

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

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

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

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

為什么都占比一樣的時(shí)候信息熵最大呢？也就是說(shuō)最不穩(wěn)定呢？因?yàn)楫?dāng)每個(gè)事物都占比一樣的時(shí)候，一個(gè)小事物進(jìn)來(lái)，不清楚它到底屬于哪一類(lèi)；如果只有一類(lèi)事物或者一類(lèi)事物居多數(shù)，那么也就比較明確該屬于哪類(lèi)，也就穩(wěn)定，確定了。

那么怎么用呢？

我們通過(guò)計(jì)算機(jī)分類(lèi)，因?yàn)橛泻芏喾N分類(lèi)情況，不是每一次分類(lèi)都是直接將同一類(lèi)分到一個(gè)類(lèi)別里，而是將該分好的兩個(gè)類(lèi)的信息熵總和最小為依據(jù)，不斷地通過(guò)暴力尋找最佳選擇。然后遞歸進(jìn)行對(duì)分好類(lèi)的數(shù)據(jù)進(jìn)行再分類(lèi)。

基尼系數(shù)

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

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

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

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

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

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

代碼實(shí)現(xiàn)

再重說(shuō)下流程：

通過(guò)對(duì)每個(gè)特征進(jìn)行嘗試分類(lèi)，記錄當(dāng)前分類(lèi)最小的信息熵（或基尼系數(shù)）的特征為當(dāng)前分類(lèi)結(jié)果。

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

X為二維平面的數(shù)據(jù)點(diǎn)，Y為類(lèi)別。

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

信息熵函數(shù)：

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

二者使用一個(gè)即可。

下面是一個(gè)分類(lèi)核心的流程：

文字描述為：

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

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

分類(lèi)代碼：

分類(lèi)效果流程圖：

決策樹(shù)第一層分類(lèi)結(jié)果為：

當(dāng)前線(xiàn)為最佳值，1維的數(shù)據(jù)就是分過(guò)的，但是沒(méi)有當(dāng)前的值好，也就沒(méi)顯示。

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

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

批判性思維看決策樹(shù)

看到上述的分類(lèi)結(jié)果，其實(shí)你心里也想到了決策樹(shù)的缺點(diǎn)了，就是分類(lèi)總是橫平豎直的，不能是曲線(xiàn)。

比如

該四個(gè)數(shù)據(jù)的分類(lèi)最佳理想條件下應(yīng)該為上述紫色線(xiàn)條，但是決策樹(shù)的結(jié)果為;

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

明明應(yīng)該屬于藍(lán)色點(diǎn)的，但是被劃分到紅色點(diǎn)里。

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

另一個(gè)問(wèn)題是，決策樹(shù)的學(xué)習(xí)問(wèn)題，從上述代碼實(shí)現(xiàn)過(guò)程能夠看出來(lái)，可以說(shuō)是暴力求解了。

責(zé)任編輯：lq