分類(lèi)算法之決策樹(shù)
一、原理
決策樹(shù)是一種非參數(shù)的監(jiān)督學(xué)習(xí)方法，它主要用于分類(lèi)和回歸。決策樹(shù)的目的是構(gòu)造一種模型，使之能夠從樣本數(shù)據(jù)的特征屬性中，通過(guò)學(xué)習(xí)簡(jiǎn)單的決策規(guī)則——IF THEN，從而預(yù)測(cè)目標(biāo)變量的值。
二、重要概念
不確定性函數(shù)I：是事件U發(fā)生概率p的單調(diào)遞減函數(shù)
信息熵：當(dāng)事件U有多種可能情況時(shí)，多個(gè)不確定性函數(shù)I的平均不確定性即為信息熵，信息熵是事物混亂性的度量標(biāo)準(zhǔn)。
其中S是樣本集合，p(ui)表示S中第i類(lèi)樣本的比例
三、有哪些決策樹(shù)算法
目前常用的決策樹(shù)的算法包括ID3（Iterative Dichotomiser 3）、C4.5和CART（Classification And Regression Tree）。前兩種算法主要應(yīng)用的是基于信息熵的方法，而第三種應(yīng)用的是基尼系數(shù)的方法。
1.?ID3算法（基礎(chǔ)）
核心思想：前面我們提到過(guò)信息熵，表示樣本分布的混亂程度，如果我們能夠找到一個(gè)屬性對(duì)其進(jìn)行分類(lèi)，例如根據(jù)顏色，將水果分成兩個(gè)樣本集，那么這兩個(gè)樣本的信息熵加權(quán)求和之后，總的熵會(huì)減小，即逐漸變?yōu)橛兄刃颍敲催@個(gè)信息熵減小的值我們稱(chēng)為信息增益(Information Gain)，決策樹(shù)的核心思想就是每次找到信息增益最大的屬性進(jìn)行節(jié)點(diǎn)分裂。
該式表示，總樣本集D在經(jīng)過(guò)對(duì)A屬性進(jìn)行分類(lèi)后的信息增益。因此我們?cè)贒內(nèi)遍歷所有屬性，選擇信息增益最大的那個(gè)特征屬性進(jìn)行分類(lèi)。在下次迭代循環(huán)中，我們只需對(duì)上次分類(lèi)剩下的樣本集合計(jì)算信息增益，如此循環(huán)，直至不能再分類(lèi)為止。
缺陷：ID3應(yīng)用的是信息增益的方法，因此會(huì)更傾向選擇那些包括很多種類(lèi)的特征屬性，即哪個(gè)屬性A中的n多，那么這個(gè)A的信息增益就可能更大。我們可以這樣理解：如果有一個(gè)屬性，可以將原樣本分為N類(lèi)，每個(gè)類(lèi)別中只有1個(gè)樣本，那么每個(gè)類(lèi)別中的熵就是最小值0，這樣加權(quán)求和后，信息增益就是最大的了。我們應(yīng)該避免出現(xiàn)這樣的情況。
2.C4.5算法
它與ID3算法的作者是同一個(gè)人，我們可以將C4.5理解為ID3的擴(kuò)展。針對(duì)ID3的缺陷，C4.5使用信息增益率這一準(zhǔn)則來(lái)衡量混亂度（也叫非純度），即：
其中，SI(D, A)表示分裂信息值，它的定義為：
后續(xù)類(lèi)似于ID3，再選擇信息增益率最大的那個(gè)特征屬性作為分類(lèi)屬性。
3.CART算法
CART算法是由Breiman等人首先提出，與前兩者的最明顯的兩個(gè)區(qū)別：
① CART依據(jù)的是基尼系數(shù)，而非信息增益或信息增益率。
針對(duì)特征屬性A，分類(lèi)后的基尼指數(shù)為：
核心思想：選擇基尼指數(shù)最小的那個(gè)特征屬性作為分類(lèi)屬性。
② CART樹(shù)必為二叉樹(shù)，它包括分類(lèi)樹(shù)和回歸樹(shù)兩種。
分類(lèi)樹(shù)的算法：
對(duì)于二分類(lèi)屬性，我們直接選擇基尼系數(shù)最小的那個(gè)屬性作為分類(lèi)屬性。如果特征屬性A中有多于2個(gè)的值，即n>2，這時(shí)我們就需要一個(gè)閾值β，它把D分割成了D和D兩個(gè)部分，不同的β得到不同的D和D，我們重新設(shè)D的樣本數(shù)為L(zhǎng)，D的樣本數(shù)為R，因此有L+R=N。
進(jìn)一步，求基尼系數(shù)的最小值，可以轉(zhuǎn)變?yōu)榍笙率降?b>SG最大值：
回歸樹(shù)的算法：
兩者的不同之處是，分類(lèi)樹(shù)的樣本輸出（即響應(yīng)值）是類(lèi)別，屬于離散值，如判斷蘑菇是有毒還是無(wú)毒，周末去看電影還是不去。而回歸樹(shù)的樣本輸出是數(shù)值的形式，屬于連續(xù)值，比如給某人發(fā)放房屋貸款的數(shù)額就是具體的數(shù)值，可以是0到120萬(wàn)元之間的任意值。為了得到回歸樹(shù)，我們就需要把適合分類(lèi)的非純度度量參數(shù)換成適合回歸的非純度度量參數(shù)。因此我們將均方誤差替代基尼系數(shù)：
式中N表示D集合的樣本數(shù)量，y和r分別為第i個(gè)樣本的輸出值和預(yù)測(cè)值。如果我們把樣本的預(yù)測(cè)值用樣本輸出值的平均來(lái)替代，則轉(zhuǎn)化為：
如果針對(duì)于某個(gè)屬性A，我們把集合D劃分為s個(gè)部分，則劃分后的均方誤差為：
類(lèi)似于信息增益，上兩式求差值后，即為劃分后的誤差減小：
我們尋求的是最大化的誤差減小，又因?yàn)镃ART是二叉樹(shù)，所以轉(zhuǎn)化為：
問(wèn)題最后轉(zhuǎn)化為求方括號(hào)內(nèi)的△LLS最大值：
到這里，我們總結(jié)一下CART分類(lèi)樹(shù)和回歸樹(shù)：
Ⅰ. 特征為類(lèi)的分類(lèi)樹(shù)：
① 對(duì)于兩類(lèi)問(wèn)題，即樣本的分類(lèi)（響應(yīng)值）只有兩種情況：響應(yīng)值為0和1，按照特征屬性的類(lèi)別的樣本響應(yīng)值為1的數(shù)量的多少進(jìn)行排序。例如我們采集20個(gè)樣本來(lái)構(gòu)建是否踢球分類(lèi)樹(shù)，設(shè)出去踢球的響應(yīng)值為1，不踢球的響應(yīng)值為0，直接帶入公式計(jì)算SG值。
② 對(duì)于非兩類(lèi)問(wèn)題，采用的是層次聚類(lèi)的方法。如一共有14個(gè)樣本，按照由小至大的順序?yàn)椋篴bcdefghijklmn，第一次分叉為：a|bcdefghijklmn，豎線“|”的左側(cè)被劃分到左分支，右側(cè)被劃分到右分支，帶入公式計(jì)算SG值，然后第二次分叉：ab|cdefghijklmn，同理帶入公式計(jì)算SG值，，以此類(lèi)推，得到這13次分叉的最大值，該種分叉方式即為最佳的分叉方式，其中閾值β為分叉的次數(shù)。
Ⅱ. 特征為數(shù)值的分類(lèi)樹(shù)：
由于特征屬性是用數(shù)值進(jìn)行表示，我們就按照數(shù)值的大小順序排序，求出相鄰兩值間的平均數(shù)，根據(jù)此數(shù)值，按照上面非兩類(lèi)的問(wèn)題進(jìn)行計(jì)算。
Ⅲ. 特征為類(lèi)的回歸樹(shù)：
計(jì)算每種特征屬性各個(gè)種類(lèi)的平均樣本響應(yīng)值，按照該值的大小進(jìn)行排序，然后依次帶入公式計(jì)算△LLG值，求最大值。
Ⅳ. 特征為數(shù)值的回歸樹(shù)：
該種情況與特征為數(shù)值的分類(lèi)樹(shù)相同，就按照數(shù)值的大小順序依次帶入公式計(jì)算△LLG值，求最大值。
四、訓(xùn)練決策樹(shù)的四個(gè)問(wèn)題
Q1：如何處理異常數(shù)據(jù)？
Q2：某些樣本缺失了某個(gè)特征屬性，但該特征屬性又是最佳分叉屬性，那么如何對(duì)該樣本進(jìn)行分叉呢？
解決辦法：
一種是直接把該樣本刪除掉；
一種是用各種算法估計(jì)該樣本的缺失屬性值；
一種是用另一個(gè)特征屬性來(lái)替代最佳分叉屬性，該特征屬性被稱(chēng)為替代分叉屬性。因此在計(jì)算最佳分叉屬性的同時(shí)，還要計(jì)算該特征屬性的替代分叉屬性，以防止最佳分叉屬性缺失的情況。
Q3：如何避免過(guò)擬合問(wèn)題？
由于決策樹(shù)的建立完全是依賴于訓(xùn)練樣本，因此該決策樹(shù)對(duì)該樣本能夠產(chǎn)生完全一致的擬合效果。但這樣的決策樹(shù)對(duì)于預(yù)測(cè)樣本來(lái)說(shuō)過(guò)于復(fù)雜，對(duì)預(yù)測(cè)樣本的分類(lèi)效果也不夠精確。這種現(xiàn)象就稱(chēng)為過(guò)擬合。
將復(fù)雜的決策樹(shù)進(jìn)行簡(jiǎn)化的過(guò)程稱(chēng)為剪枝，它的目的是去掉一些節(jié)點(diǎn)，包括葉節(jié)點(diǎn)和中間節(jié)點(diǎn)。剪枝常用的方法有預(yù)剪枝和后剪枝兩種。預(yù)剪枝是在構(gòu)建決策樹(shù)的過(guò)程中，提前終止決策樹(shù)的生長(zhǎng)，從而避免過(guò)多的節(jié)點(diǎn)的產(chǎn)生。該方法雖然簡(jiǎn)單但實(shí)用性不強(qiáng)，因?yàn)槲覀兒茈y精確的判斷何時(shí)終止樹(shù)的生長(zhǎng)。后剪枝就是在決策樹(shù)構(gòu)建完后再去掉一些節(jié)點(diǎn)。常見(jiàn)后剪枝方法有四種：悲觀錯(cuò)誤剪枝（PEP）、最小錯(cuò)誤剪枝（MEP）、代價(jià)復(fù)雜度剪枝（CCP）和基于錯(cuò)誤的剪枝（EBP）。
Q4：如何選擇訓(xùn)練集和測(cè)試集？
一般會(huì)采取Cross-Validation法（交叉驗(yàn)證）：比如一共有10組數(shù)據(jù)：
第一次. ?1到9做訓(xùn)練數(shù)據(jù)， 10做測(cè)試數(shù)據(jù)
第二次. ?2到10做訓(xùn)練數(shù)據(jù)，1做測(cè)試數(shù)據(jù)
第三次. 1，3到10做訓(xùn)練數(shù)據(jù)，2做測(cè)試數(shù)據(jù)，以此類(lèi)推
做10次，然后大平均錯(cuò)誤率。這樣稱(chēng)為?10 folds Cross-Validation。
比如?3 folds Cross-Validation 指的是數(shù)據(jù)分3份，2份做訓(xùn)練，1份做測(cè)試。?
以上
個(gè)人總結(jié)，歡迎交流~
ps：更多內(nèi)容，可以關(guān)注公眾號(hào)【bigdata_x】對(duì)話框回復(fù)“見(jiàn)面禮”，獲取免費(fèi)的大數(shù)據(jù)學(xué)習(xí)資源。
樹(shù)立人生目標(biāo)的四個(gè)建議：
1.找到自己想要什么
2.直面恐懼成長(zhǎng)得更快
3.尋找?guī)椭鷦e人的機(jī)會(huì)
4.按照理想中的標(biāo)準(zhǔn)行事
