什么是決策樹？

在談?wù)摏Q策樹之前，先說說什么樹吧。
樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點組成一個具有層次關(guān)系的集合。
我們稱樹的頂點1為根結(jié)點，樹的最底端為葉子結(jié)點，其他都稱為樹節(jié)點（內(nèi)部節(jié)點）

樹.png

決策樹.jpg

決策樹的構(gòu)造

優(yōu)點： 計算復(fù)雜度不高，輸出結(jié)果易于理解，對中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。
缺點： 可能會產(chǎn)生過度匹配問題。

決策樹的一般流程：

1. 收集數(shù)據(jù)： 可以使用任何方法
2. 準(zhǔn)備數(shù)據(jù)： 樹構(gòu)造算法只適用于標(biāo)稱型數(shù)據(jù)，因此數(shù)值型數(shù)據(jù)必須離散化
3. 分析數(shù)據(jù)： 可以使用任何方法，構(gòu)造樹完成之后，我們應(yīng)該檢查圖形是否符合預(yù)期
4. 訓(xùn)練算法： 構(gòu)造樹的數(shù)據(jù)結(jié)構(gòu)
5. 測試算法： 使用經(jīng)驗樹計算錯誤率
6. 使用算法： 此步驟可以適用于任何監(jiān)督學(xué)習(xí)算法，而使用決策樹可以更好的理解數(shù)據(jù)的內(nèi)在含義

信息增益

什么是信息增益呢？在劃分?jǐn)?shù)據(jù)集之后信息發(fā)生的變化稱為信息增益，知道如何計算信息增益，我們就可以計算每個特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。

（1）香農(nóng)熵

在可以評測哪個數(shù)據(jù)劃分方式是最好的數(shù)據(jù)劃分之前，我們必須學(xué)習(xí)如何計算信息增益。集合信息的度量方式稱為香農(nóng)熵或者簡稱為熵(entropy)，這個名字來源于信息論之父克勞德·香農(nóng)。

如果看不明白什么是信息增益和熵，請不要著急，因為他們自誕生的那一天起，就注定會令世人十分費解。克勞德·香農(nóng)寫完信息論之后，約翰·馮·諾依曼建議使用"熵"這個術(shù)語，因為大家都不知道它是什么意思。

熵定義為信息的期望值。在信息論與概率統(tǒng)計中，熵是表示隨機變量不確定性的度量。如果待分類的事物可能劃分在多個分類之中，則符號xi的信息定義為 ：

機器學(xué)習(xí)：決策樹

其中p(xi)是選擇該分類的概率。有人可能會問，信息為啥這樣定義啊？答曰：前輩得出的結(jié)論。這就跟1+1等于2一樣，記住并且會用即可。上述式中的對數(shù)以2為底，也可以e為底(自然對數(shù))。

通過上式，我們可以得到所有類別的信息。為了計算熵，我們需要計算所有類別所有可能值包含的信息期望值(數(shù)學(xué)期望)，通過下面的公式得到：

機器學(xué)習(xí)：決策樹

期中n是分類的數(shù)目。熵越大，隨機變量的不確定性就越大。

當(dāng)熵中的概率由數(shù)據(jù)估計(特別是最大似然估計)得到時，所對應(yīng)的熵稱為經(jīng)驗熵(empirical entropy)。什么叫由數(shù)據(jù)估計？比如有10個數(shù)據(jù)，一共有兩個類別，A類和B類。其中有7個數(shù)據(jù)屬于A類，則該A類的概率即為十分之七。其中有3個數(shù)據(jù)屬于B類，則該B類的概率即為十分之三。淺顯的解釋就是，這概率是我們根據(jù)數(shù)據(jù)數(shù)出來的。我們定義貸款申請樣本數(shù)據(jù)表中的數(shù)據(jù)為訓(xùn)練數(shù)據(jù)集D，則訓(xùn)練數(shù)據(jù)集D的經(jīng)驗熵為H(D)，|D|表示其樣本容量，及樣本個數(shù)。設(shè)有K個類Ck, = 1,2,3,...,K,|Ck|為屬于類Ck的樣本個數(shù)，因此經(jīng)驗熵公式就可以寫為 ：

機器學(xué)習(xí)：決策樹

機器學(xué)習(xí)：決策樹

希望通過所給的訓(xùn)練數(shù)據(jù)學(xué)習(xí)一個貸款申請的決策樹，用于對未來的貸款申請進行分類，即當(dāng)新的客戶提出貸款申請時，根據(jù)申請人的特征利用決策樹決定是否批準(zhǔn)貸款申請。

特征選擇就是決定用哪個特征來劃分特征空間。比如，我們通過上述數(shù)據(jù)表得到兩個可能的決策樹，分別由兩個不同特征的根結(jié)點構(gòu)成。

機器學(xué)習(xí)：決策樹

根據(jù)此公式計算經(jīng)驗熵H(D)，分析貸款申請樣本數(shù)據(jù)表中的數(shù)據(jù)。最終分類結(jié)果只有兩類，即放貸和不放貸。根據(jù)表中的數(shù)據(jù)統(tǒng)計可知，在15個數(shù)據(jù)中，9個數(shù)據(jù)的結(jié)果為放貸，6個數(shù)據(jù)的結(jié)果為不放貸。所以數(shù)據(jù)集D的經(jīng)驗熵H(D)為：

機器學(xué)習(xí)：決策樹

經(jīng)過計算可知，數(shù)據(jù)集D的經(jīng)驗熵H(D)的值為0.971。

信息增益

在上面，我們已經(jīng)說過，如何選擇特征，需要看信息增益。也就是說，信息增益是相對于特征而言的，信息增益越大，特征對最終的分類結(jié)果影響也就越大，我們就應(yīng)該選擇對最終分類結(jié)果影響最大的那個特征作為我們的分類特征。

在講解信息增益定義之前，我們還需要明確一個概念，條件熵。

熵我們知道是什么，條件熵又是個什么鬼？條件熵H(Y|X)表示在已知隨機變量X的條件下隨機變量Y的不確定性，隨機變量X給定的條件下隨機變量Y的條件熵(conditional entropy)H(Y|X)，定義為X給定條件下Y的條件概率分布的熵對X的數(shù)學(xué)期望：

機器學(xué)習(xí)：決策樹

這里，

機器學(xué)習(xí)：決策樹

同理，當(dāng)條件熵中的概率由數(shù)據(jù)估計(特別是極大似然估計)得到時，所對應(yīng)的條件熵稱為條件經(jīng)驗熵(empirical conditional entropy)。

明確了條件熵和經(jīng)驗條件熵的概念。接下來，讓我們說說信息增益。前面也提到了，信息增益是相對于特征而言的。所以，特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗熵H(D)與特征A給定條件下D的經(jīng)驗條件熵H(D|A)之差，即：

機器學(xué)習(xí)：決策樹

一般地，熵H(D)與條件熵H(D|A)之差稱為互信息(mutual information)。決策樹學(xué)習(xí)中的信息增益等價于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。

設(shè)特征A有n個不同的取值{a1,a2,···,an}，根據(jù)特征A的取值將D劃分為n個子集{D1,D2，···,Dn}，|Di|為Di的樣本個數(shù)。記子集Di中屬于Ck的樣本的集合為Dik，即Dik = Di ∩ Ck，|Dik|為Dik的樣本個數(shù)。于是經(jīng)驗條件熵的公式可以些為：

機器學(xué)習(xí)：決策樹

說了這么多概念性的東西，沒有聽懂也沒有關(guān)系，舉幾個例子，再回來看一下概念，就懂了。

以貸款申請樣本數(shù)據(jù)表為例進行說明?？聪履挲g這一列的數(shù)據(jù)，也就是特征A1，一共有三個類別，分別是：青年、中年和老年。我們只看年齡是青年的數(shù)據(jù)，年齡是青年的數(shù)據(jù)一共有5個，所以年齡是青年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率是十五分之五，也就是三分之一。同理，年齡是中年和老年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率也都是三分之一?，F(xiàn)在我們只看年齡是青年的數(shù)據(jù)的最終得到貸款的概率為五分之二，因為在五個數(shù)據(jù)中，只有兩個數(shù)據(jù)顯示拿到了最終的貸款，同理，年齡是中年和老年的數(shù)據(jù)最終得到貸款的概率分別為五分之三、五分之四。所以計算年齡的信息增益，過程如下：

機器學(xué)習(xí)：決策樹

同理，計算其余特征的信息增益g(D,A2)、g(D,A3)和g(D,A4)。分別為：

機器學(xué)習(xí)：決策樹

機器學(xué)習(xí)：決策樹

機器學(xué)習(xí)：決策樹

最后，比較特征的信息增益，由于特征A3(有自己的房子)的信息增益值最大，所以選擇A3作為最優(yōu)特征。

寫在最后：感謝崔嘉華老師的無私指導(dǎo)和分享。