作者：程Sir

本文由 微信公眾號 程SIR說 授權(quán)發(fā)布，版權(quán)所有歸作者，轉(zhuǎn)載請聯(lián)系作者！

決策樹簡介

決策樹(Decision Tree)是一種簡單但是廣泛使用的分類器。通過訓(xùn)練數(shù)據(jù)構(gòu)建決策樹，可以高效的對未知的數(shù)據(jù)進(jìn)行分類。

決策數(shù)有兩大優(yōu)點(diǎn)：1)決策樹模型可以讀性好，具有描述性，有助于人工分析;2)效率高，決策樹只需要一次構(gòu)建，反復(fù)使用，每一次預(yù)測的最大計(jì)算次數(shù)不超過決策樹的深度。

決策樹的主要算法有ID3，C4.5，CART。其中C4.5是對于ID3的優(yōu)化。本周主要就是學(xué)習(xí)了ID3算法的過程，基于我自己編的一組數(shù)據(jù)：

基礎(chǔ)概念-信息熵

信息是個很抽象的概念。人們常常說信息很多，或者信息較少，但卻很難說清楚信息到底有多少。比如一本五十萬字的中文書到底有多少信息量。

直到1948年，香農(nóng)提出了“信息熵”的概念，才解決了對信息的量化度量問題。香農(nóng)從熱力學(xué)中借用過來的。熱力學(xué)中的熱熵是表示分子狀態(tài)混亂程度的物理量。香農(nóng)用信息熵的概念來描述信源的不確定度。

假如事件A的全概率劃分是(A1,A2,…,An)，每部分發(fā)生的概率是(p1,p2,…,pn)，那信息熵定義為：

構(gòu)造決策樹-樹根

構(gòu)造樹的基本想法是隨著樹深度的增加，節(jié)點(diǎn)的熵迅速地降低。熵降低的速度越快越好，因?yàn)檫@樣得到的樹的高度最矮。讓熵減小，就是說讓確定性增加，也就是越來越能夠做出判斷。

我們的例子中，最開始如果病人的任何特征都不看，根據(jù)歷史的數(shù)據(jù)，知道病人感冒的概率是1/2，過敏的概率1/6，腦震蕩概率1/3。此時的熵為：

E = -(1/2)×log(1/2)-(1/6)×log(1/6)-(1/3)×log(1/3)= 1.459

然后看特征，病人的特征有三個，癥狀、職業(yè)、性別，我們要選擇一個作為樹根，先把原始6個病人情況做成一張表：

癥狀為“打噴嚏”的有3人，2個感冒，1個過敏，因此打噴嚏時，2/3概率感冒，1/3概率過敏，0概率腦震蕩，此時熵為：

-(2/3)×log(2/3)-(1/3)×log(1/3)= 0.918

癥狀為“頭疼”的有3人，1個感冒，2個腦震蕩，因此頭疼時，1/3概率感冒，2/3概率腦震蕩，0概率過敏，此時熵為：

-(1/3)×log(1/3)-(2/3)×log(2/3)= 0.918

從整體看，一共6個人，3個打噴嚏，3個頭疼，因此，打噴嚏和頭疼的概率都是1/2

所以已知特征“癥狀”的情況，總系統(tǒng)的信息熵為0.918×1/2+0.918×1/2 = 0.918，

信息增益Gain(癥狀)=1.459-0.918= 0.541

再看“職業(yè)”這個特征：

職業(yè)為“護(hù)士”的有1人，1個感冒。因此職業(yè)為護(hù)士，1概率感冒，0概率其他病，熵為0

職業(yè)為“農(nóng)民”的有1人，1個過敏。因此職業(yè)為農(nóng)民，1概率過敏，0概率其他病，熵為0

職業(yè)為“工人”的有2人，1個感冒，1個腦震蕩。因此職業(yè)為工人，1/2概率感冒，1/2概率腦震蕩，0概率過敏，熵：

-(1/2)×log(1/2)-(1/2)×log(1/2)= 1

職業(yè)為“教師”的有2人，1個感冒，1個腦震蕩。因此職業(yè)為教師，1/2概率感冒，1/2概率腦震蕩，0概率過敏，熵：

-(1/2)×log(1/2)-(1/2)×log(1/2)= 1

從整體看，一共6個人，1護(hù)士，1農(nóng)民，2工人，2教師，因此護(hù)士和農(nóng)民的概率都是1/6，工人和教師概率都是1/3，所以已知特征“職業(yè)”的情況，總系統(tǒng)的信息熵為：

1/6 ×0 +1/6×0 +1/3×1+1/3×1=0.667，

信息增益Gain(職業(yè))=1.459-0.667= 0.792

再看“性別”這個特征:

性別為“男”有2人，1過敏，1腦震蕩，因此性別為男，1/2概率過敏，1/2概率腦震蕩，0概率感冒，熵為：

-(1/2)×log(1/2)-(1/2)×log(1/2)= 1

性別為“女”有4人，3個感冒，1個腦震蕩，因此性別為女，3/4概率感冒，1/4概率腦震蕩，熵為：

-(3/4)×log(3/4)-(1/4)×log(1/4)= 0.811

從整體看，一共6個人，2男4女，因此男概率1/3，女概率2/3，已知性別的情況下，總系統(tǒng)的信息熵為

1×1/3+0.811×2/3=0.874

信息增益Gain(性別)=1.459-0.874=0.585

可見“職業(yè)”讓總系統(tǒng)的信息熵下降的更快，決策樹的根就是職業(yè)，如下圖：

構(gòu)造決策樹-其他枝葉

構(gòu)造枝葉的方法和構(gòu)造樹根一樣，只是考慮的病人的范圍不同。

接下來確定N1，方法類似，現(xiàn)在只需要考慮職業(yè)為“工人”的這個子系統(tǒng)，還是列一個表：

先看癥狀這個特征:

癥狀為打噴嚏的沒有，熵為0

癥狀為頭疼的有2人，1人感冒，1人腦震蕩，因此“頭疼工人”里，1/2概率感冒，1/2概率腦震蕩，熵為：

-(1/2)×log(1/2)-(1/2)×log(1/2)= 1

總的系統(tǒng)信息熵為1，沒有任何變化

再看性別這個特征：

性別為男1人，是腦震蕩，因此“男工人”里，腦震蕩概率1，其他概率0，熵為0

性別為女1人，是感冒，因此“女工人”里，感冒概率1，其他概率0，熵為0

總的系統(tǒng)熵為0，把總系統(tǒng)熵一下降低為0

因此，N1就應(yīng)該選擇性別作為分支，然后分支的熵都為0了，也就都能確定病情了。

接下來確定N2，方法類似，現(xiàn)在只需要考慮職業(yè)為“教師”的這個子系統(tǒng)，還是列一個表：

每個分支的熵都為0，總系統(tǒng)的熵也就為0，決策樹構(gòu)造完畢，最終如圖：

判定規(guī)則

決策樹比較直觀，好理解，關(guān)鍵就在于構(gòu)造完成之后可以演變成一條一條的判定規(guī)則。本例中：

IF 職業(yè)為護(hù)士 THEN 感冒

IF 職業(yè)為農(nóng)民 THEN 過敏

IF 職業(yè)為工人，性別為男 THEN 腦震蕩

其他

• 構(gòu)造過程中，可能發(fā)生屬性用完還是沒有最終判定的情況(也就是葉子節(jié)點(diǎn)還是有很多可能性)，那么就選擇最大可能性的判定作為判定(選判定結(jié)果最多的)
• 連續(xù)型數(shù)據(jù)的屬性，ID3沒法處理(個人理解也可以預(yù)先進(jìn)行離散化操作，例如分段處理，然后在構(gòu)造決策樹)
• 決策樹還有一個非常重要的問題是過度擬合，因?yàn)槭?00%按照給定的訓(xùn)練數(shù)據(jù)構(gòu)造的樹，訓(xùn)練數(shù)據(jù)中的噪音數(shù)據(jù)等都生成了特定的分支，應(yīng)用的時候就會發(fā)生錯誤率很高的問題。對于決策樹，必須要進(jìn)行剪枝。

原文>>>

End.

轉(zhuǎn)載請注明來自36大數(shù)據(jù)（36dsj.com)：36大數(shù)據(jù) » 畫一棵樹用來決策