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

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

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

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

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

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

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

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

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

9、開需要的信息量。如果了解信息論，就會知道上面的信息Info實際上就是信息論中的熵Entropy，熵表示的是不確定度的度量，如果某個數(shù)據(jù)集的類別的不確定程度越高，則其熵就越大。比如我們將一個立方體A拋向空中，記落地時著地的面為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，記落地時著地的面為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；如果我們再換成一個球C，記落地時著地的面為f3，顯然不管怎么扔著地都是同一個面，即f3的取值為1，故其熵entropy(f3)=-1*log(1)=0?？梢钥吹矫鏀?shù)越多，熵值也越大，而當只有一個面的球時，熵值為0，此時表示不確定程度為0，也就是著地時向下的面是確定的。有了上面關于熵的簡單理解，我們接著講信息增益。假設我們選擇屬性R作為分裂屬性，數(shù)據(jù)集D中，R有k個不同的取值V1,V2,Vk，于是可將D根據(jù)R的值分成k組D1,D2,Dk，按R進行分裂后，將數(shù)據(jù)集D不同的類分開還需要的信息量為：信息增益的定義為分裂前后，兩個信息量只差：信息增益Gain(R)表

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

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

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

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