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

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

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

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

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

5、看決策樹(shù)算法的基本思想算法：generatedecisiontree(d/attributelist)tgjgij|練數(shù)據(jù)記錄 d 生成一棵決策樹(shù). 輸入：o數(shù)據(jù)記錄d ,包含類(lèi)標(biāo)的訓(xùn)練數(shù)據(jù)集；o屬性列表attributelist，候選屬性集，用于在內(nèi)部結(jié)點(diǎn)中作判斷的屬性o屬性選擇方法attributeselectionmethodo，選擇最佳分類(lèi)屬性的方法. 輸出：一棵決策樹(shù). 過(guò)程：1. 構(gòu)造一個(gè)節(jié)點(diǎn)n ;2. 如果數(shù)據(jù)記錄d中的所有記錄的類(lèi)標(biāo)都相同(記為c類(lèi))：則將節(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中類(lèi)標(biāo)最多的類(lèi), 并返回結(jié)點(diǎn)

6、n;4. 調(diào)用 attributeselectionmethod(d,attributelist)選擇最佳的分裂準(zhǔn)則 splitcriteri on;5. 將節(jié)點(diǎn)n標(biāo)記為最佳分裂準(zhǔn)則splitcriterion;6. 如果分裂屬性取值是離散的，并且允許決策樹(shù)進(jìn)行多叉分裂：從屬性列 表中減去分裂屬性 z attributelsit -= splitattribute;7. 對(duì)分裂屬性的每一個(gè)取值j：記d中滿(mǎn)足j的記錄集合為dj;如果dj為空: 貝噺建一個(gè)葉子結(jié)點(diǎn)f ,標(biāo)記為d中類(lèi)標(biāo)最多的類(lèi)，并且把結(jié)點(diǎn)f掛在n下；8. 否則：遞歸調(diào)用 generatedecisiontree(djzattribu

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

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

9、= (d中屬于ci類(lèi)的集合的記錄個(gè)數(shù)/|d|)。info(d)表示將數(shù)據(jù)集d不同的類(lèi) 分開(kāi)需要的信息量。如果了解信息論，就會(huì)知道上面的信息info實(shí)際上就是信息論中的爛entropy ,爛表示的是不確走度的度量，如果某個(gè)數(shù)據(jù)集的類(lèi)別的不確定程度越高，則其爛就越大。比如我們將一個(gè)立方體a拋向空中，記落地時(shí)著地的面為flz fl的取值為1,234,5,6,fl 的爛 entropy(fl)=-(l/6*log(l/6)+.+l/6*log(l/6)=-l*log(l/6)=2.58 ;現(xiàn)在我 們把立方體a換為正四面體b ,記落地時(shí)著地的面為f2 , f2的取值為1,234 , f2的entropy

10、(l/4*log(l/4)+l/4*log(l/4)+l/4*log(l/4)+l/4*log(l/4) =-log (1/4)=2 ;如果我們?cè)贀Q成一個(gè)球c ,記落地時(shí)著地的面為f3 ,顯然不管怎么扔著地都 是同一個(gè)面,即代的取值為，故其爛entropy(f3)=-l*log=0。可以看到面數(shù)越 多，爛值也越大，而當(dāng)只有一個(gè)面的球時(shí)，爛值為0 ,此時(shí)表示不確走程度為0 ,也就 是著地時(shí)向下的面是確定的。有了上面關(guān)于爛的簡(jiǎn)單理解，我們接著講信息增益。假設(shè)我們選擇屬性r作為分裂屬性, 數(shù)據(jù)集d中，r有k個(gè)不同的取值v1,v2，,vk,于是可將d根據(jù)r的值分成k組d 1q2，,dk,按r進(jìn)行分裂后

11、，將數(shù)據(jù)集d不同的類(lèi)分開(kāi)還需要的信息量為：k d； iiuf°r (q)=若苗 x infod：)信息增益的定義為分裂前后，兩個(gè)信息量只差：gain(r) = info(d) 一 infor(d)信息增益gain(r)表示屬性r給分類(lèi)帶來(lái)的信息量，我們尋找gain最大的屬性，就能 使分類(lèi)盡可能的純，即最可能的把不同的類(lèi)分開(kāi)。不過(guò)我們發(fā)現(xiàn)對(duì)所以的屬性info(d) 都是一樣的，所以求最大的gain可以轉(zhuǎn)化為求最小的infor(d)e這里引入info(d)只 是為了說(shuō)明背后的原理,方便理解,實(shí)現(xiàn)時(shí)我們不需要計(jì)算info(d)。舉一個(gè)例子，數(shù)據(jù)集d如下:記錄id年齡輸入層次學(xué)生信用等級(jí)是否

12、購(gòu)買(mǎi)電腦1青少年咼否一般否2青少年咼否良好否3中年高否_般是4老年中否一般是5老年低是一般是6老年低是良好否7中年低是良好是8青少年中否一般否9青少年低是一般是10老年屮是一般是11青少年中是良好是12中年中否良好是13中年高是一般是14老年中否良好否這個(gè)數(shù)據(jù)集是根據(jù)一個(gè)人的年齡、收入、是否學(xué)生以及信用等級(jí)來(lái)確定他是否會(huì)購(gòu)買(mǎi)電 腦,即最后一列堤否購(gòu)買(mǎi)電腦是類(lèi)標(biāo)。現(xiàn)在我們用信息增益選出最最佳的分類(lèi)屬性, 計(jì)算按年齡分裂后的信息量:5?2 3-44-。-3-() = 77x(-xl°g2-xl°g2)+x(-xlog2)+77x(-xlog2-xl°g2)= 0-69

13、4x irjjl 1丄jj整個(gè)式子由三項(xiàng)累加而成，第一項(xiàng)為青少年，14條記錄中有5條為青少年，其中2 （占2/5 ）條購(gòu)買(mǎi)電腦，3 （占3/5 ）條不購(gòu)買(mǎi)電腦。第二項(xiàng)為中年，第三項(xiàng)為老年。類(lèi)似的,x(厶4有:+ ax(-|xlogj-|xlogi)+ -lx(-|xlog-axlogi)=0.9：14661斗 44info± (d) = 0.789 , info電加注(d) = 0.892可以得出info年齡(d)最小，即以年齡分裂后，分得的結(jié)果中類(lèi)標(biāo)最純，此時(shí)已年齡作為根結(jié)點(diǎn)的測(cè)試屬性,根據(jù)青少年、中年、老年分為三個(gè)分支：年齡中年詢(xún)?nèi)雽?嘆lx1 竺 4(?高否一般否高良好-s-中

14、否般否低是般是中呈良好育少年it、j p中否般是低是般是低定巳子中是般中否老年高般是詆是良好呈中否良好是高a般是注意,年齡這個(gè)屬性用過(guò)后，之后的操作就不需要年齡了，即把年齡從attributelist 中刪掉。往后就按照同樣的方法，構(gòu)建d1q2q3對(duì)應(yīng)的決策子樹(shù)。id3算法使用的就 是基于信息增益的選擇屬性方法。增益比率(gain ratio )信息增益選擇方法有一個(gè)很大的缺陷，它總是會(huì)傾向于選擇屬性值多的屬性，如果我們?cè)谏厦娴臄?shù)據(jù)記錄中加一個(gè)姓名屬性,假設(shè)14條記錄中的每個(gè)人姓名不同，那么信息增益就會(huì)選擇姓名作為最佳屬性,因?yàn)榘葱彰至押?每個(gè)組只包含一條記錄,而每個(gè) 記錄只屬于一類(lèi)(要么購(gòu)

15、買(mǎi)電腦要么不購(gòu)買(mǎi))，因此純度最高,以姓名作為測(cè)試分裂的結(jié)點(diǎn)下面有14個(gè)分支。但是這樣的分類(lèi)沒(méi)有意義，它沒(méi)有任何泛化能力。增益比率對(duì)此進(jìn)行了改進(jìn),它引入一個(gè)分裂信息:splitinfor(d) = -yj-i11d11d增益比率定義為信息增益與分裂信息的比率:gamratior)=gain(r)splitlnfap (d)我們找gainratio最大的屬性作為最佳分裂屬性。如果一個(gè)屬性的取值很多，那么spl itlnfor(d)會(huì)大，從而使gainratio(r)變小。不過(guò)增益比率也有缺點(diǎn)，splitlnfo(d)可 能取0 ,此時(shí)沒(méi)有計(jì)算意義；且當(dāng)splitlnfo(d)趨向于0時(shí)，gainr

16、atio(r)的值變得不 可信，改進(jìn)的措施就是在分母加一個(gè)平滑,這里加一個(gè)所有分裂信息的平均值：gauiratio(r) =splitlnfod') + splitho? (d)基尼指數(shù)(gini index )基尼指數(shù)是另夕種數(shù)據(jù)的不純度的度量方法,其定義如下:gini(d) = 1 -工i-i其中的m仍然表示數(shù)據(jù)集d中類(lèi)別c的個(gè)數(shù)，pi表示d中任意一個(gè)記錄屬于ci的概 率，計(jì)算時(shí)pi二(d中屬于ci類(lèi)的集合的記錄個(gè)數(shù)/|d|)。如果所有的記錄都屬于同一個(gè) 類(lèi)中，則 pl=l , gini(d)=0 ,此時(shí)不純度最低。在 cart(classification and regression tree)算法中利用基尼指數(shù)構(gòu)造二叉決策樹(shù)，對(duì)每個(gè)屬性都會(huì)枚舉其屬性的非空真 子集，以屬性r分裂后的基尼系數(shù)為：ginir (d)=i