數(shù)據(jù)挖掘(6)：決策樹分類算法

1、數(shù)據(jù)挖掘（6）：決策樹分類算法2015/08/29 IT技術(shù)數(shù)據(jù)挖掘分享到：5 Gopher China 2015 上海大會(huì) R語言基礎(chǔ) 去哪兒前端沙龍分享第三期 Qnext前端交互沙龍?jiān)某鎏帲篺engfenggirl（也愛數(shù)據(jù)挖掘）從這篇開始，我將介紹分類問題，主要介紹決策樹算法、樸素貝葉斯、支持向量機(jī)、BP神經(jīng)網(wǎng)絡(luò)、懶惰學(xué)習(xí)算法、隨機(jī)森林與自適應(yīng)增強(qiáng)算法、分類模型選擇和結(jié)果評價(jià)。總共7篇，歡迎關(guān)注和交流。這篇先介紹分類問題的一些基本知識，然后主要講述決策樹算法的原理、實(shí)現(xiàn)，最后利用決策樹算法做一個(gè)泰坦尼克號船員生存預(yù)測應(yīng)用。一、分類基本介紹物以類聚，人以群分，分類問題只古以來就出現(xiàn)我們的

2、生活中。分類是數(shù)據(jù)挖掘中一個(gè)重要的分支，在各方面都有著廣泛的應(yīng)用，如醫(yī)學(xué)疾病判別、垃圾郵件過濾、垃圾短信攔截、客戶分析等等。分類問題可以分為兩類： 歸類：歸類是指對離散數(shù)據(jù)的分類，比如對根據(jù)一個(gè)人的筆跡判別這個(gè)是男還是女，這里的類別只有兩個(gè)，類別是離散的集合空間男，女的。 預(yù)測：預(yù)測是指對連續(xù)數(shù)據(jù)的分類，比如預(yù)測明天8點(diǎn)天氣的濕度情況，天氣的濕度在隨時(shí)變化，8點(diǎn)時(shí)的天氣是一個(gè)具體值，它不屬于某個(gè)有限集合空間。預(yù)測也叫回歸分析，在金融領(lǐng)域有著廣泛應(yīng)用。雖然對離散數(shù)據(jù)和連續(xù)數(shù)據(jù)的處理方式有所不同，但其實(shí)他們之間相互轉(zhuǎn)化，比如我們可以根據(jù)比較的某個(gè)特征值判斷，如果值大于0.5就認(rèn)定為男性，小于等于0

3、.5就認(rèn)為是女性，這樣就轉(zhuǎn)化為連續(xù)處理方式；將天氣濕度值分段處理也就轉(zhuǎn)化為離散數(shù)據(jù)。數(shù)據(jù)分類分兩個(gè)步驟：1. 構(gòu)造模型，利用訓(xùn)練數(shù)據(jù)集訓(xùn)練分類器；2. 利用建好的分類器模型對測試數(shù)據(jù)進(jìn)行分類。好的分類器具有很好的泛化能力，即它不僅在訓(xùn)練數(shù)據(jù)集上能達(dá)到很高的正確率，而且能在未見過得測試數(shù)據(jù)集也能達(dá)到較高的正確率。如果一個(gè)分類器只是在訓(xùn)練數(shù)據(jù)上表現(xiàn)優(yōu)秀，但在測試數(shù)據(jù)上表現(xiàn)稀爛，這個(gè)分類器就已經(jīng)過擬合了，它只是把訓(xùn)練數(shù)據(jù)記下來了，并沒有抓到整個(gè)數(shù)據(jù)空間的特征。二、決策樹分類決策樹算法借助于樹的分支結(jié)構(gòu)實(shí)現(xiàn)分類。下圖是一個(gè)決策樹的示例，樹的內(nèi)部結(jié)點(diǎn)表示對某個(gè)屬性的判斷，該結(jié)點(diǎn)的分支是對應(yīng)的判斷結(jié)果；葉

4、子結(jié)點(diǎn)代表一個(gè)類標(biāo)。上表是一個(gè)預(yù)測一個(gè)人是否會(huì)購買購買電腦的決策樹，利用這棵樹，我們可以對新記錄進(jìn)行分類，從根節(jié)點(diǎn)（年齡）開始，如果某個(gè)人的年齡為中年，我們就直接判斷這個(gè)人會(huì)買電腦，如果是青少年，則需要進(jìn)一步判斷是否是學(xué)生；如果是老年則需要進(jìn)一步判斷其信用等級，直到葉子結(jié)點(diǎn)可以判定記錄的類別。決策樹算法有一個(gè)好處，那就是它可以產(chǎn)生人能直接理解的規(guī)則，這是貝葉斯、神經(jīng)網(wǎng)絡(luò)等算法沒有的特性；決策樹的準(zhǔn)確率也比較高，而且不需要了解背景知識就可以進(jìn)行分類，是一個(gè)非常有效的算法。決策樹算法有很多變種，包括ID3、C4.5、C5.0、CART等，但其基礎(chǔ)都是類似的。下面來看看決策樹算法的基本思想： 算法：

5、GenerateDecisionTree(D,attributeList)根據(jù)訓(xùn)練數(shù)據(jù)記錄D生成一棵決策樹. 輸入：o 數(shù)據(jù)記錄D，包含類標(biāo)的訓(xùn)練數(shù)據(jù)集;o 屬性列表attributeList，候選屬性集，用于在內(nèi)部結(jié)點(diǎn)中作判斷的屬性.o 屬性選擇方法AttributeSelectionMethod()，選擇最佳分類屬性的方法. 輸出：一棵決策樹. 過程：1. 構(gòu)造一個(gè)節(jié)點(diǎn)N；2. 如果數(shù)據(jù)記錄D中的所有記錄的類標(biāo)都相同（記為C類）：則將節(jié)點(diǎn)N作為葉子節(jié)點(diǎn)標(biāo)記為C，并返回結(jié)點(diǎn)N；3. 如果屬性列表為空：則將節(jié)點(diǎn)N作為葉子結(jié)點(diǎn)標(biāo)記為D中類標(biāo)最多的類，并返回結(jié)點(diǎn)N；4. 調(diào)用AttributeSe

6、lectionMethod(D,attributeList)選擇最佳的分裂準(zhǔn)則splitCriterion;5. 將節(jié)點(diǎn)N標(biāo)記為最佳分裂準(zhǔn)則splitCriterion;6. 如果分裂屬性取值是離散的，并且允許決策樹進(jìn)行多叉分裂：從屬性列表中減去分裂屬性，attributeLsit -= splitAttribute;7. 對分裂屬性的每一個(gè)取值j:記D中滿足j的記錄集合為Dj;如果Dj為空：則新建一個(gè)葉子結(jié)點(diǎn)F，標(biāo)記為D中類標(biāo)最多的類，并且把結(jié)點(diǎn)F掛在N下;8. 否則：遞歸調(diào)用GenerateDecisionTree(Dj,attributeList)得到子樹結(jié)點(diǎn)Nj，將Nj掛在N下;9.

7、返回結(jié)點(diǎn)N;算法的1、2、3步驟都很顯然，第4步的最佳屬性選擇函數(shù)會(huì)在后面專門介紹，現(xiàn)在只有知道它能找到一個(gè)準(zhǔn)則，使得根據(jù)判斷結(jié)點(diǎn)得到的子樹的類別盡可能的純，這里的純就是只含有一個(gè)類標(biāo)；第5步根據(jù)分裂準(zhǔn)則設(shè)置結(jié)點(diǎn)N的測試表達(dá)式。在第6步中，對應(yīng)構(gòu)建多叉決策樹時(shí)，離散的屬性在結(jié)點(diǎn)N及其子樹中只用一次，用過之后就從可用屬性列表中刪掉。比如前面的圖中，利用屬性選擇函數(shù)，確定的最佳分裂屬性是年齡，年齡有三個(gè)取值，每一個(gè)取值對應(yīng)一個(gè)分支，后面不會(huì)再用到年齡這個(gè)屬性。算法的時(shí)間復(fù)雜度是O(k*|D|*log(|D|)，k為屬性個(gè)數(shù)，|D|為記錄集D的記錄數(shù)。三、屬性選擇方法屬性選擇方法總是選擇最好的屬性最

8、為分裂屬性，即讓每個(gè)分支的記錄的類別盡可能純。它將所有屬性列表的屬性進(jìn)行按某個(gè)標(biāo)準(zhǔn)排序，從而選出最好的屬性。屬性選擇方法很多，這里我介紹三個(gè)常用的方法：信息增益（Information gain）、增益比率（gain ratio）、基尼指數(shù)（Gini index）。 信息增益（Information gain）信息增益基于香濃的信息論，它找出的屬性R具有這樣的特點(diǎn)：以屬性R分裂前后的信息增益比其他屬性最大。這里信息的定義如下：其中的m表示數(shù)據(jù)集D中類別C的個(gè)數(shù)，Pi表示D中任意一個(gè)記錄屬于Ci的概率，計(jì)算時(shí)Pi=(D中屬于Ci類的集合的記錄個(gè)數(shù)/|D|)。Info(D)表示將數(shù)據(jù)集D不同的類分

9、開需要的信息量。如果了解信息論，就會(huì)知道上面的信息Info實(shí)際上就是信息論中的熵Entropy，熵表示的是不確定度的度量，如果某個(gè)數(shù)據(jù)集的類別的不確定程度越高，則其熵就越大。比如我們將一個(gè)立方體A拋向空中，記落地時(shí)著地的面為f1，f1的取值為1,2,3,4,5,6，f1的熵entropy(f1)=-(1/6*log(1/6)+1/6*log(1/6)=-1*log(1/6)=2.58；現(xiàn)在我們把立方體A換為正四面體B，記落地時(shí)著地的面為f2，f2的取值為1,2,3,4，f2的熵entropy(1)=-（1/4*log(1/4)+1/4*log(1/4)+1/4*log(1/4)+1/4*log

10、(1/4) =-log(1/4)=2；如果我們再換成一個(gè)球C，記落地時(shí)著地的面為f3，顯然不管怎么扔著地都是同一個(gè)面，即f3的取值為1，故其熵entropy(f3)=-1*log(1)=0?？梢钥吹矫鏀?shù)越多，熵值也越大，而當(dāng)只有一個(gè)面的球時(shí)，熵值為0，此時(shí)表示不確定程度為0，也就是著地時(shí)向下的面是確定的。有了上面關(guān)于熵的簡單理解，我們接著講信息增益。假設(shè)我們選擇屬性R作為分裂屬性，數(shù)據(jù)集D中，R有k個(gè)不同的取值V1,V2,Vk，于是可將D根據(jù)R的值分成k組D1,D2,Dk，按R進(jìn)行分裂后，將數(shù)據(jù)集D不同的類分開還需要的信息量為：信息增益的定義為分裂前后，兩個(gè)信息量只差：信息增益Gain(R)表

11、示屬性R給分類帶來的信息量，我們尋找Gain最大的屬性，就能使分類盡可能的純，即最可能的把不同的類分開。不過我們發(fā)現(xiàn)對所以的屬性Info(D)都是一樣的，所以求最大的Gain可以轉(zhuǎn)化為求最小的InfoR(D)。這里引入Info(D)只是為了說明背后的原理，方便理解，實(shí)現(xiàn)時(shí)我們不需要計(jì)算Info(D)。舉一個(gè)例子，數(shù)據(jù)集D如下：記錄ID年齡輸入層次學(xué)生信用等級是否購買電腦1青少年高否一般否2青少年高否良好否3中年高否一般是4老年中否一般是5老年低是一般是6老年低是良好否7中年低是良好是8青少年中否一般否9青少年低是一般是10老年中是一般是11青少年中是良好是12中年中否良好是13中年高是一般是1

12、4老年中否良好否這個(gè)數(shù)據(jù)集是根據(jù)一個(gè)人的年齡、收入、是否學(xué)生以及信用等級來確定他是否會(huì)購買電腦，即最后一列“是否購買電腦”是類標(biāo)?，F(xiàn)在我們用信息增益選出最最佳的分類屬性，計(jì)算按年齡分裂后的信息量：整個(gè)式子由三項(xiàng)累加而成，第一項(xiàng)為青少年，14條記錄中有5條為青少年，其中2（占2/5）條購買電腦，3（占3/5）條不購買電腦。第二項(xiàng)為中年，第三項(xiàng)為老年。類似的，有：可以得出Info年齡(D)最小，即以年齡分裂后，分得的結(jié)果中類標(biāo)最純，此時(shí)已年齡作為根結(jié)點(diǎn)的測試屬性，根據(jù)青少年、中年、老年分為三個(gè)分支：注意，年齡這個(gè)屬性用過后，之后的操作就不需要年齡了，即把年齡從attributeList中刪掉。往后

13、就按照同樣的方法，構(gòu)建D1,D2,D3對應(yīng)的決策子樹。ID3算法使用的就是基于信息增益的選擇屬性方法。 增益比率（gain ratio）信息增益選擇方法有一個(gè)很大的缺陷，它總是會(huì)傾向于選擇屬性值多的屬性，如果我們在上面的數(shù)據(jù)記錄中加一個(gè)姓名屬性，假設(shè)14條記錄中的每個(gè)人姓名不同，那么信息增益就會(huì)選擇姓名作為最佳屬性，因?yàn)榘葱彰至押螅總€(gè)組只包含一條記錄，而每個(gè)記錄只屬于一類（要么購買電腦要么不購買），因此純度最高，以姓名作為測試分裂的結(jié)點(diǎn)下面有14個(gè)分支。但是這樣的分類沒有意義，它沒有任何泛化能力。增益比率對此進(jìn)行了改進(jìn)，它引入一個(gè)分裂信息：增益比率定義為信息增益與分裂信息的比率：我們找Ga

14、inRatio最大的屬性作為最佳分裂屬性。如果一個(gè)屬性的取值很多，那么SplitInfoR(D)會(huì)大，從而使GainRatio(R)變小。不過增益比率也有缺點(diǎn)，SplitInfo(D)可能取0，此時(shí)沒有計(jì)算意義；且當(dāng)SplitInfo(D)趨向于0時(shí)，GainRatio(R)的值變得不可信，改進(jìn)的措施就是在分母加一個(gè)平滑，這里加一個(gè)所有分裂信息的平均值： 基尼指數(shù)（Gini index）基尼指數(shù)是另外一種數(shù)據(jù)的不純度的度量方法，其定義如下：其中的m仍然表示數(shù)據(jù)集D中類別C的個(gè)數(shù)，Pi表示D中任意一個(gè)記錄屬于Ci的概率，計(jì)算時(shí)Pi=(D中屬于Ci類的集合的記錄個(gè)數(shù)/|D|)。如果所有的記錄都屬于同一個(gè)類中，則P1=1，Gini(D)=0，此時(shí)不純度最低。在CART(Classification and Regression Tree)算法中利用基尼指數(shù)構(gòu)造二叉決策樹，對每個(gè)屬性都會(huì)枚舉其屬性