機器學(xué)習(xí)-3：決策樹的構(gòu)建及應(yīng)用

1、_3：決策樹的構(gòu)建及應(yīng)章錄實驗背景在之前的實驗：我們了解到了K-近鄰算法是種需訓(xùn)練就可以拿來進(jìn)分類的算法，但缺點也很多，最的缺點就是法給出數(shù)據(jù)的內(nèi)在含義，今天我就來介紹種容易理解數(shù)據(jù)形式的分類算法決策樹算法。1.決策樹算法原理什么是決策樹嚴(yán)格定義上來說，分類決策樹模型是種描述對實例進(jìn)分類的樹形結(jié)構(gòu)。決策樹由結(jié)點和有向邊組成。結(jié)點有兩種類型：內(nèi)部結(jié)點和葉節(jié)點。內(nèi)部結(jié)點表個特征或?qū)傩?，葉節(jié)點表個類。通俗來說決策樹只有個功能判斷，通過不斷的判斷最終得出個結(jié)果，以相親為例我們將相親簡單的化為三個屬性的思考（對象不，富不富，美不美），實際上的相親遠(yuǎn)這復(fù)雜，很顯然，富美的對象乎沒有會拒絕。個新的對象放進(jìn)決

2、策樹判斷，這個對象是，富，不美，經(jīng)過3次判斷之后，得出的結(jié)論是去。這就是決策樹，當(dāng)然，這種海王決策樹不是我們特別需要的。決策樹的使更多傾向于專家系統(tǒng)中，以病情診斷為例，將以前們記錄的各種疾病以及這些疾病發(fā)時的癥狀記錄下來，于構(gòu)建決策樹，經(jīng)過這些疾病的訓(xùn)練后，當(dāng)病根據(jù)提輸體溫等各種信息后，這個病情決策樹就能判斷出患者得了哪種病。那么問題就來了，哪種屬性作為判斷的依據(jù)呢，或者說，哪種屬性作為判斷依據(jù)可以有最好的效果呢？如何構(gòu)建好的決策樹想要構(gòu)造好的決策樹，就得找到合適的屬性作為判斷依據(jù)，如何選擇合適的屬性呢，這引四個概念，濃熵，信息增益，信息增益率，基尼指數(shù)。1.2.1.熵，本質(zhì)是指個系統(tǒng)的“內(nèi)在

3、混亂程度”，濃熵也樣，這個詞來形容個事物的確定程度，濃熵越，事物的就越不確定，濃熵越，事物越確定。公式為：Ent（D）表熵，pk表k事件出現(xiàn)的概率，k=1y表共有y種事件以硬幣為例，枚硬幣拋出，正或反朝上的概率均為50%，此時熵為：-（1/2（log2（1/2）+1/2（log2（1/2）=1。很顯然，此時就是這個硬幣最不確定的時候，如果我們對硬幣作腳，讓其概率發(fā)變化，濃熵也會隨之變化。這就是硬幣概率變化導(dǎo)致熵的變化，當(dāng)然，這硬幣只有兩種結(jié)果，當(dāng)這兩種概率相等的時候熵最。當(dāng)事件越多，熵值就會越。1.2.2.在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)的變化稱為信息增益，計算公式為：Gain(D,a)表集合D中屬

4、性a的信息增益，Dv表屬性a有V種分，第v個節(jié)點包含了D在a屬性上取值為av的所有樣本。Gain（D,a)越，代表根據(jù)屬性a劃分獲得的“純度提升”越。1.2.3.雖然信息增益可以幫助我們選擇合適的劃分屬性，但他也有個很明顯的問題，那就是明顯偏好可取數(shù)較多的屬性，以硬幣為例，如果拋10次硬幣，5次朝上，5次朝下，如果以次數(shù)為屬性，可以發(fā)現(xiàn)，每次都只有個值即屬性是確定的，這樣信息增益就會變成1-0=1。所以我們引信息增益率IV(a)稱為屬性a的固有值，屬性a的可能取值越多，IV(a)的值通常就越，顯然，這種法也有個缺點，那就是偏好可取數(shù)較少的屬性，所以我們先挑選信息增益于平均平的屬性，再對其求信息

5、增益率，這樣就能得到合適的屬性。1.2.4.基尼指數(shù)是不同于信息增益和信息增益率的另套屬性，他來描述數(shù)據(jù)集的純度，反應(yīng)了隨機抽取兩個樣本，其類別標(biāo)記不致的概率，也就是基尼指數(shù)越，這個數(shù)據(jù)集的標(biāo)記越統(tǒng)公式為：給定數(shù)據(jù)集D，屬性a的基尼指數(shù)定義為：在候選屬性集合A中，選擇那個使得劃分后基尼指數(shù)最的屬性作為最有劃分屬性。如何優(yōu)化構(gòu)建完的決策樹盡管有多種法可以選擇合適的屬性來劃分?jǐn)?shù)據(jù)集，構(gòu)造決策樹，但根據(jù)訓(xùn)練數(shù)據(jù)集訓(xùn)練出來的決策樹也有很明顯的問題，那就是過度擬合訓(xùn)練數(shù)據(jù)，導(dǎo)致泛性下降。實際上，訓(xùn)練數(shù)據(jù)集不可能包含了世界上的所有情況，這就導(dǎo)致個新的樣例丟決策樹進(jìn)判斷，得出的結(jié)果有很可能不是我們想要的，因

6、為這種樣例決策樹沒有接觸過。這就需要我們對決策樹進(jìn)“剪枝”。1.3.1.顧名思義，預(yù)剪枝通過提前停樹的構(gòu)建對樹剪枝，主要法有4種：1.當(dāng)決策樹達(dá)到預(yù)設(shè)的度時就停決策樹的長。2.達(dá)到某個節(jié)點的實例具有相同的特征向量，即使這些實例不屬于同類，也可以停決策樹的長。（如同樣是頭疼，發(fā)熱，部分是感冒，部分是中暑，我們就認(rèn)為頭疼，發(fā)熱都是感冒）3.定義個閾值，當(dāng)達(dá)到某個節(jié)點的實例個數(shù)于閾值時就可以停決策樹的長。（這是為了防過度擬合訓(xùn)練數(shù)據(jù)，如頭疼的樣例有10個，頭疼發(fā)熱的樣例只有1個，那就需再發(fā)熱進(jìn)劃分）4.通過計算每次擴張對系統(tǒng)性能的增益，決定是否停決策樹的（提升系統(tǒng)性能就擴張，降低就砍掉這個屬性）法3

7、中有個很明顯的問題，這個閾值是我們事先規(guī)定的，但是如何確定這個閾值是值得討論的，如何控制好擬合-過擬合的平衡是這個地的難點。盡管預(yù)剪枝能降低過擬合風(fēng)險并且顯著減少訓(xùn)練時間和測試時間開銷。但因為他的“貪”導(dǎo)致可能會陷局部最優(yōu)，也就是法解決-低-更的情況，會困死在包上。同時因為限制分枝的展開，使得擬合風(fēng)險提（畢竟頭疼發(fā)熱的樣例哪怕只有例，如果是病毒的情況，這種也是需要注意的，預(yù)剪枝就可能會導(dǎo)致忽視這種問題）如圖所，預(yù)剪枝情況下是沒有上那棵完整的決策樹的，直接畫出下那棵剪枝后的決策樹。1.3.2.后剪枝先從訓(xùn)練集成棵完整的決策樹，然后底向上地對葉結(jié)點進(jìn)分析計算，若將該結(jié)點對應(yīng)的樹替換為葉結(jié)點能帶來決

8、策樹泛化性能提升，則將該樹替換為葉結(jié)點。如果沒有提升，保持不便的話，我們就保留。優(yōu)缺點都很明顯，保留更多的分使得擬合的風(fēng)險減，有夠分的情況下般也分過少的預(yù)剪枝泛化性更好；更優(yōu)秀的表現(xiàn)往往需要更多的付出，因為這種法是成完整的決策樹后，底向上進(jìn)剪枝，導(dǎo)致訓(xùn)練時間很長，開銷。后剪枝先成上那棵完整的決策樹，再對那棵決策樹進(jìn)剪枝。2.三種決策樹構(gòu)造原理解釋完后，我們來分別構(gòu)建基于信息增益，信息增益率，基尼指數(shù)的決策樹，先，我們需要計算濃熵，代碼如下：def calcShannonEnt(dataSet):#字典，存儲類別及個數(shù)#dataSet進(jìn)后為list形式，使變量featVec進(jìn)列表遍歷#取出列表最

9、后個標(biāo)簽if currentLabel not in labelCounts.keys(): #若標(biāo)簽不在字典中for key in labelCounts:#使關(guān)鍵字循環(huán)遍歷shannonEnt -= prob *log(prob,2)return shannonEnt#測試數(shù)據(jù)#公式求熵labels =no surfacing,flippers#change to discrete valuesreturn dataSet, labels基于信息增益構(gòu)造的決策樹（ID ）#按照給定的特征劃分?jǐn)?shù)據(jù)集def splitDataSet(dataSet, axis, value):retDataS

10、et =#存儲分割數(shù)據(jù)#list遍歷#如果數(shù)據(jù)集的value符合我們給定的axis#將該數(shù)據(jù)加reducedFeatVec#選擇最好的數(shù)據(jù)集劃分式(信息增益)def chooseBestFeatureToSplit1(dataSet):numFeatures =len(dataSet0) - 1#去除標(biāo)簽的特征數(shù)量baseEntropy =calcShannonEnt(dataSet) #得到濃熵#初始化參數(shù)#迭代所有特征featList =example for example in dataSet #創(chuàng)建列表存放特征樣例#刪除重復(fù)數(shù)據(jù)，獲取唯數(shù)據(jù)#0/1分類，遍歷for value in

11、uniqueVals:#0,1實例分別計算條件熵newEntropy +=prob *calcShannonEnt(subDataSet) #條件熵infoGain =baseEntropy - newEntropy #信息增益#選擇最的信息增益return bestFeature#返回特征下標(biāo)#找出出現(xiàn)次數(shù)最多的標(biāo)簽，于投票def majorityCnt(classList):classCountdef createTree(dataSet,labels):classList =example-1 for example in dataSet#-1表列表最后個if classList.cou

12、nt(classList0) =len(classList): #所有結(jié)果樣就需再次分類return classList0#返回結(jié)果if len(dataSet0) =1:#只剩下種結(jié)果時也需分類#返回出現(xiàn)次數(shù)最多的類return majorityCnt(classList)#使信息增益選擇最佳劃分式myTree =bestFeatLabel:myTreebestFeatLabelvalue =createTree(splitDataSet(dataSet, bestFeat, value),subLabels)return myTree這樣的決策樹明顯不夠直觀，我們加點繪制圖像。#獲取葉節(jié)點

13、if type(secondDictkey)._name_=dict:#測試節(jié)點是否為字典,如果不是，則是葉結(jié)點#獲取樹的深度if type(secondDictkey)._name_=dict:#test to see if the nodes are dictonaires, if not they are leaf nodesif thisDepth maxDepth: maxDepth =thisDepthreturn maxDepthdef plotNode(nodeTxt, centerPt, parentPt, nodeType):va=center, ha=center, bb

14、oxnodeType, arrowpropsarrow_args )def plotMidText(cntrPt, parentPt, txtString):xMid =(parentPt0-cntrPt0)/2.0 +cntrPt0yMid =(parentPt1-cntrPt1)/2.0 +cntrPt1createPlot.ax1.text(xMid, yMid, txtString, va=center, ha=center, rotation30)firstStr =myTree.keys()0 #the text label for this node should be this

15、cntrPt =(plotTree.xOff +(1.0 +float(numLeafs)/2.0/plotTree.totalW, plotTree.yOff)plotMidText(cntrPt, parentPt, nodeTxt)plotNode(firstStr, cntrPt, parentPt, decisionNode)secondDict =myTreefirstStrplotTree.yOff =plotTree.yOff - 1.0/plotTree.totalDfor key in secondDict.keys():if type(secondDictkey)._na

16、me_=dict:#test to see if the nodes are dictonaires, if not they are leaf nodesplotTree(secondDictkey,cntrPt,str(key)#recursionplotNode(secondDictkey, (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)plotMidText(plotTree.xOff, plotTree.yOff), cntrPt, str(key)def createPlot(inTree):fig =plt.figure(1,

17、facecolor=white)fig.clf()fig = plt.figure(1, facecolor=white)fig.clf()#createPlot(thisTree)基于信息增益率構(gòu)造的決策樹（C ）#去除標(biāo)簽的特征數(shù)量baseEntropy =calcShannonEnt(dataSet) #得到濃熵#初始化參數(shù)#獲取平均信息增益#統(tǒng)計數(shù)量featList =example for example in dataSet #創(chuàng)建列表存放特征樣例#刪除重復(fù)數(shù)據(jù)，獲取唯數(shù)據(jù)#0/1分類，遍歷for value in uniqueVals:#0,1實例分別計算條件熵subDataSe

18、t =splitDataSet(dataSet, j, value)prob =len(subDataSet)/float(len(dataSet)newEntropy +=prob *calcShannonEnt(subDataSet) #條件熵IV-=prob *log(prob,2)infoGain =baseEntropy - newEntropy #信息增益sum+=infoGainfor i in range(numFeatures):#迭代所有特征featList =example for example in dataSet #創(chuàng)建列表存放特征樣例#刪除重復(fù)數(shù)據(jù)，獲取唯數(shù)據(jù)IV

19、0.0#0/1分類，遍歷for value in uniqueVals:#0,1實例分別計算條件熵subDataSet =splitDataSet(dataSet, i, value)prob =len(subDataSet)/float(len(dataSet)newEntropy +=prob *calcShannonEnt(subDataSet) #條件熵IV-=prob *log(prob,2)infoGain =baseEntropy - newEntropy #信息增益if 0.0:infoGainration0.0else:#選擇最的信息增益率return bestFeature

20、#返回特征下標(biāo)C 4.5的代碼和ID 3很像，核區(qū)別只在于如何選擇信息收益于平均收益的情況下的信息增益率。微量數(shù)據(jù)下法看出明顯區(qū)別基于基尼指數(shù)構(gòu)造的決策樹（CART）#計算基尼指數(shù)def calcGini(dataset):for feat in uniqueFeat:bestFeature =-1for i in range(numFeatures):newEntropy =0.0for value in uniqueVals:# 通過不同的特征值劃分?jǐn)?shù)據(jù)集subDataSet =splitDataSet(dataSet, i, value)prob =len(subDataSet)/flo

21、at(len(dataSet)newEntropy +=prob calcGini(subDataSet)infoGini =newEntropyif(infoGini bestInfoGini): # 選擇最的基尼系數(shù)作為劃分依據(jù)bestInfoGini =infoGinireturn bestFeature #返回決策屬性的最佳索引微量數(shù)據(jù)下沒有區(qū)別。3.決策樹測試對于量的數(shù)據(jù)集，為了便存儲與復(fù)，我們需要保存在硬盤內(nèi)#存儲件#讀取件def loadTree(filename):fr =open(filename)return pickle.load(fr)if _name_ =_main_:fr=open(D:/vscode/python/.vscode/car.data ,r)dataSetinst.strip().spli