機器學習實戰之決策樹（三）

正方形代表判斷模塊(decision block) ，橢圓代表終止模塊（terminating block），表示已經得到結論，可以終止運動。

決策樹的優勢在於數據形式容易理解。決策樹的很多任務都是為了數據中所蘊含的知識信息。決策樹可以使用不熟悉的數據集合，並從中提取出一系列規則，機器學習演算法最終將使用這些機器從數據集中創造的規則。

3.1決策樹的構造

優點：計算複雜度不高，輸出結果易於理解，對中間值的缺失不敏感，可以處理不相關特徵數據。

缺點：可能會產生過度匹配的問題。

適用數據類型：數值型和標稱型。

1.先討論數學上如何使用資訊理論劃分數據集；

2.編寫代碼將理論應用到具體的數據集上；

3.編寫代碼構建決策樹；

創建分支的偽代碼函數createBranch()

檢測數據集中的每個子項是否屬於同一分類：n If so return 類標籤 ：n Elsen 尋找劃分數據集的最好特徵n 劃分數據集n 創建分支節點n for 每個劃分的子集n 調用函數createBranch 並增加返回結果到分支節點中n return 分子節點n

上面的偽代碼createBranch是一個遞歸函數，在倒數第二行直接調用它子集、

決策樹一般流程

1. 收集數據：可以直接使用任何方法
2. 準備數據：構造演算法只適用於標稱型數據，因此數值型數據必須離散化。
3. 分析數據：可以使用任何方法，構造完樹以後，我們應該檢查圖形是否符合預期。
4. 訓練演算法：構造數的數據結構。
5. 測試演算法：使用經驗樹計算錯誤概率
6. 使用演算法：此步驟可以適應於任何監督學習演算法，而使用決策樹可以更好的理解數據的內在含義。

本次我們使用ID3演算法來劃分數據集。每次劃分數據集的時我們只選取一個特徵值。

決策樹學習採用的是自頂向下的遞歸方法，其基本思想是以信息熵為度量構造一棵熵值下降最快的樹，到葉子節點處的熵值為零，此時每個葉節點中的實例都屬於同一類。

3.1.1 信息增益

劃分數據集的大原則是 ：將無序的數據變得有序。

組織雜亂無章數據的一種方法就是使用資訊理論度量信息，資訊理論是量化處理信息的分支科學。

在劃分數據集之前之後的信息發生的變化稱之為信息增益，知道如何計算信息增益，我們就可以計算每個特徵的值劃分數據集獲得的信息增益，獲得信息增益最高的特徵就是最好的選擇。

集合信息的度量方式稱之為 香農熵。

熵

熵是資訊理論中的概念，用來表示集合的無序程度，熵越大表示集合越混亂，反之則表示集合越有序。熵的計算公式為：

E = -P * log2P

熵定義為信息的期望值。那什麼是信息呢？如果待分類的事務可能劃分在多個分類之中，負荷xi的信息定義為：

其中，p(xi)是選擇分類的概率。

為了計算熵，我們需要計算所有類別的

其中n是分類的數目。

接下來我們將使用pythoon計算信息熵，去度量數據集的無序程度，創建名為trees.py的文件。

from math import lognndef calcShannonEnt(dataSet):n #計算數據集中實例的總數n numEntries = len(dataSet)n #創建一個數據字典n labelCounts = {}n n for featVec in dataSet:n #取鍵值最後一列的數值的最後一個字元串n currentLabel = featVec[-1]n #鍵值不存在就使當前鍵加入字典n if currentLabel not in labelCounts.keys():n labelCounts[currentLabel] = 0n labelCounts[currentLabel] += 1n shannonEnt = 0.0n for key in labelCounts:n prob = float(labelCounts[key])/numEntriesn #以2為底求對數n shannonEnt -= prob * log(prob,2)n return shannonEntn

我們輸入 一個數據來測試一下。

In [65]: import treesnnIn [67]: reload(trees)nOut[67]: <module trees from trees.py>nnIn [69]: def createDatSet():n ...: dataSet = [[1,1,yes],n ...: [1,1,yes],n ...: [1,0,no],n ...: [0,1,no],n ...: [0,1,no]]n ...: labels = [no surfacing,flippers]n ...: return dataSet,labelsn ...:nnIn [70]: myDat,labels = trees.createDatSet()nnIn [71]: myDatnOut[71]: [[1, 1, yes], [1, 1, yes], [1, 0, no], [0, 1, no], [0, 1, no]]nnIn [72]: trees.calcShannonEnt(myDat)nOut[72]: 0.9709505944546686n

熵越高，混合的數據就越多。

我們可以向數據集中添加更多的分類，以此來觀測熵是如何變化的。

In [95]: myDat[0][-1]=maybennIn [96]: myDatnOut[96]: [[1, 1, maybe], [1, 1, yes], [1, 0, no], [0, 1, no], [0, 1, no]]nnIn [97]: trees.calcShannonEnt(myDat)nOut[97]: 1.3709505944546687n

3.1.2 劃分數據集

分類演算法除了要度量數據集的無序程度（信息熵），還需要劃分數據集，度量劃分數據集的熵。以便於判斷當前是否正確劃分了數據集。

我們隊每個特徵劃分一次數據集的結果計算一次信息熵，然後去判斷按照哪個特徵劃分數據集是最好的劃分方式。

代碼 ： 按照給定的特徵劃分數據集

#dataSet:待劃分的數據集n#axis劃分數據集的特徵n#特徵的返回值ndef splitDataSet(dataSet,axis,value):n #創建新的list對象n retDataSet=[]n for featVec in dataSet:n if featVec[axis] == value:n reducedFeatVec = featVec[:axis]n reducedFeatVec.extend(featVec[axis+1：])n retDataSet.append(reducedFeatVec)n return retDataSetn

上述代碼append和extend方法，區別如下：

In [18]: a = [1,2,3]nnIn [19]: b = [4,5,6]nnIn [20]: a.append(b)nnIn [21]: anOut[21]: [1, 2, 3, [4, 5, 6]]nnIn [22]: a = [1,2,3]nnIn [23]: b = [4,5,6]nnIn [24]: a.extend(b)nnIn [25]: anOut[25]: [1, 2, 3, 4, 5, 6]n

測試一下劃分數據集的代碼：

In [35]: reload(trees)nOut[35]: <module trees from trees.py>nnIn [36]: myDat,labels = trees.createDatSet()nnIn [37]: myDatnOut[37]: [[1, 1, yes], [1, 1, yes], [1, 0, no], [0, 1, no], [0, 1, no]]nnIn [38]: trees.splitDataSet(myDat,0,1)nOut[38]: [[1, yes], [1, yes], [0, no]]nnIn [39]: trees.splitDataSet(myDat,0,0)nOut[39]: [[1, no], [1, no]]n

記下來我們會遍歷整個數據集，循環計算香農熵和splitDataSet()函數，找到最好的特徵劃分方式。熵計算會得出如何劃分數據集是最好的數據組織方式。

def choooseBestFeatureToSplit(dataSet):n numFeatures = len(dataSet[0]) -1n baseEntropy = calcShannonEnt(dataSet)n bestInfoGain = 0.0n beatFeature =-1n for i in range(numFeatures):n #創建唯一的分類標籤列表n #取dataSet的第i個數據的第i個數據，並寫入列表n featList = [example[i] for example in dataSet]n #將列表的數據集合在一起，並去重n uniqueVals = set(featList)n newEntropy = 0.0n #計算每種劃分方式的信息熵n for value in uniqueVals:n subDataSet = splitDataSet(dataSet,i,value)n prob = len(subDataSet)/float(len(dataSet))n newEntropy += prob * calcShannonEnt(subDataSet)n infoGain = baseEntropy - newEntropyn #計算好信息熵增益n if (infoGain > bestInfoGain):n bestInfoGain = infoGainn bestFeature = in return bestFeaturen

上述代碼實現選取特徵，劃分數據集，計算出最好的劃分數據集的特徵。

在函數的調用的數據中滿足一定的要求：

（1） 數據必須是一種由列表元素組成的列表，且所有的列表元素具有相同的數據長度。

（2） 數據最後一列或每個實例的最後一個元素是當前實例的類別標籤。

測試代碼：

In [179]: reload(trees)nnIn [179]: Out[179]: <module trees from trees.py>nnIn [180]: trees.choooseBestFeatureToSplit(myDat)nOut[180]: 0nnIn [181]: myDatnOut[181]: [[1, 1, yes], [1, 1, yes], [1, 0, no], [0, 1, no], [0, 1, no]]n

根據上述的結果，第0個特徵就是最好的用於劃分數據集的特徵。

3.1.3 遞歸構建決策樹

目前我們已經給出了從數據集構造決策樹演算法所需要的子功能模塊，工作原理如下：

得到原始數據集，然後基於最好的屬性值劃分數據集，由於特徵值可能多於兩個，因此可能存在大於兩個分支的數據集劃分。第一次劃分之後，數據將被鄉下傳遞到樹分支的下一個節點，在這個節點上，可以再次劃分數據。因此我們可以使用遞歸的原理來處理數據。

遞歸結束的條件是：程序遍歷完所有劃分數據集的屬性，或者每個分支下的所有的實例都具有相同的分類。如果所有實例具有相同的分類，則得到一個葉子節點或者終止塊。

在代碼最前面，輸入

import operator

並輸入以下代碼

# 得出次數最多的分類名稱ndef majorityCnt(classList):n classCount = {}n for vote in classList:n if vote not in classCount.keys():n calssCount[vote] = 0n classCount[vote] +=1n sortedClassConnt = sorted(calssCount.iteritems(),key=operator.itemgetter(1),reverse=True)n return sortedClassConnt[0][0]n

函數使用分類名稱的列表，然後創創建鍵值為classList中唯一值得數據字典，字典對象存儲了classList中每個類標籤出現的頻率，利用operator操作鍵值排序字典，返回出現次數最多的分類名稱。

下面給出創建樹的代碼：

def createTree(dataSet,labels):n classList = [example[-1] for example in dataSet]n #類別完全相同則停止繼續劃分n if classList.count(classList[0]) ==len(classList):n return classList[0]n #遍歷完所有的特徵時返回出現次數最多的類別n if len(dataSet[0]) == 1:n return majorityCnt(classList)n bestFeat = chooseBestFeatureToSplit(dataSet)n bestFeatLabel = labels[bestFeat]n myTree = {bestFeatLabel:{}}n del(labels[bestFeat])n #得到列表包含的所有屬性n featValues = [example[bestFeat] for example in dataSet]n uniqueVals = set(featValues)n for value in uniqueVals:n subLabels = labels[:]n myTree[bestFeatLabel][value] = createTree(splitDataSetn (dataSet,bestFeat,value),subLabels)n return myTreen

執行以下命令，測試代碼：

In [185]: reload(trees)nOut[185]: <module trees from trees.py>nnIn [186]: myDat,labels=trees.createDataSet()nnIn [187]: myTree=trees.createTree(myDat,labels)nnIn [188]: myTreenOut[188]: {no surfacing: {0: no, 1: {flippers: {0: no, 1: yes}}}}n

3.2 在python中使用matplotlib註解繪製樹形圖

由於字典的表示形式不好理解，所以我們使用matplotlib這個庫來創建樹形圖。

給出的字典形式並不容易理解。決策樹的優點就是直觀易於理解。

於是我們自己繪製樹形圖。

3.2.1 Matplotlib 註解

由於字典的表示形式不好理解，所以我們使用matplotlib這個庫來創建樹形圖。

Matplotlib 提供了一個工具annotations，它可以在數據圖形上添加文本註解。註解同城用於解釋數據的內容。

在計算機科學中，圖是一種數據結構，用於表示數學上的概念。

接下來我們創建新的treePlotter.py文件

3-5 使用文本註解繪製樹節點

#定義文本框和箭頭格式ndecisionNode = dict(boxstyle = "sawtooth", fc = "0.8")nleafNode = dict(boxstyle = "round4", fc = "0.8")narrow_args = dict(arrowstyle = "<-")nn#繪製帶箭頭的註解,createPlot.ax1是一個全局變數ndef plotNode(nodeTxt,centerPt,parentPt,nodeType):n createPlot.ax1.annotate(nodeTxt,xy = parentPt,xycoords = "axes fraction",n xytext = centerPt,textcoords = "axes fraction",va = "center",n ha = "center",bbox = nodeType ,arrowprops = arrow_args)nn#創建新圖形並清空繪圖區，在繪圖區繪製決策節點和葉節點ndef createPlot():n fig = plt.figure(1,facecolor = white)n fig.clf()n #createPlot.ax1是全局變數n createPlot.ax1 = plt.subplot(111,frameon = False)n plotNode(decisionNodes,(0.5,0.1),(0.1,0.5),decisionNode)n plotNode(leafNodes,(0.8,0.1),(0.3,0.8),leafNode)n plt.show()n

測試一下代碼：

In [6]: import treePlotternnIn [7]: reload(treePlotter)nOut[7]: <module treePlotter from treePlotter.py>n

3.2.2 構造註解樹

構造完整的一棵樹，我們還需要知道，如何放置樹節點，需要知道有多少個葉節點，便於確定x軸的長度，需要知道樹多少層，便於正確確定y軸的高度。

獲取葉節點的數目和樹的層數

def getNumLeafs(myTree):n numLeafs = 0n firstStr = myTree.keys()[0]n secondDict = myTree[firstStr]n for key in secondDict.keys():n #type()函數,測試節點的數據類型是否為字典n if type(secondDict[key]).__name__ ==dict:n numLeafs += getNumLeafs(secondDict[key])n else:n numLeafs += 1n return numLeafs nn#計算遍歷過程中的遇到判斷節點的個數 ndef getTreeDepth(myTree):n maxDepth = 0n firstStr = myTree.keys()[0]n secondDict = myTree[firstStr]n for key in secondDict.keys():n if type(secondDict[key]).__name__ ==dict:n thisDepth = 1 + getTreeDepth(secondDict[key])n else:n thisDepth = 1n #如果達到子節點，則從遞歸調用中返回n if thisDepth > maxDepth: n maxDepth = thisDepthn return maxDepthn nn#我們為了便於測試，把這個樹信息先存儲進去ndef retrieveTree(i):n listOfTrees = [{no surfacing: {0: no, 1: {flippers: {0: no, 1: yes}}}},n {no surfacing: {0: no, 1: {flippers: {0: {head:{0: no, 1: yes}}, 1: no}}}}] n return listOfTrees[i]n

測試代碼：

In [39]: import treePlotternnIn [40]: reload(treePlotter)nOut[40]: <module treePlotter from treePlotter.py>nnIn [41]: myTree = treePlotter.retrieveTree(1)nnIn [42]: treePlotter.getTreeDepth(myTree)nOut[42]: 2nnIn [43]: treePlotter.getNumLeafs(myTree)nOut[43]: 3n

我們繼續將下面的代碼添加到treePlotter.py中。

# plotTree函數nndef plotMidText(cntrPt,parentPt,txtString):n xMid = (parentPt[0] - cntrPt[0])/2.0 + cntrPt[0]n yMid = (parentPt[1] - cntrPt[1])/2.0 + cntrPt[1]n createPlot.ax1.text(xMid,yMid,txtString)nnn全局變數plotTree.tatolW存儲樹的寬度n全局變數plotTree.tatolD存儲樹的高度nplotTree.xOff和plotTree.yOff追蹤已經繪製的節點位置n ndef plotTree(myTree,parentPt,nodeTxt):n #計算寬與高n numLeafs = getNumLeafs(myTree)n depth = getTreeDepth(myTree)n firstStr = myTree.keys()[0]n cntrPt = (plotTree.xOff+(1.0+float(numLeafs))/2.0/plotTree.totalW,plotTree.yOff)n #標記子節點屬性值n plotMidText(cntrPt,parentPt,nodeTxt)n plotNode(firstStr,cntrPt,parentPt,decisionNode)n secondDict = myTree[firstStr]n #減少y偏移n plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalDn for key in secondDict.keys():n if type(secondDict[key]).__name__ ==dict:n plotTree(secondDict[key],cntrPt,str(key))n else:n plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalWn plotNode(secondDict[key],(plotTree.xOff,plotTree.yOff),cntrPt,leafNode)n plotMidText((plotTree.xOff,plotTree.yOff),cntrPt,str(key))n plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalDn#這個是真正的繪製，上邊是邏輯的繪製ndef createPlot(inTree):n fig = plt.figure(1, facecolor=white)n fig.clf()n axprops = dict(xticks=[], yticks=[])n createPlot.ax1 = plt.subplot(111, frameon=False)tn plotTree.totalW = float(getNumLeafs(inTree))n plotTree.totalD = float(getTreeDepth(inTree))n plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;n plotTree(inTree, (0.5,1.0), )n plt.show()n

繼續測試代碼：

In [5]: import treePlotternnIn [6]: reload(treePlotter)nOut[6]: <module treePlotter from treePlotter.pyc>nnIn [7]: myTree = treePlotter.retrieveTree(0)nIn [8]: treePlotter.createPlot(myTree)n

我們來變更一下字典來測試代碼

In [10]: myTree[no surfacing][3] = maybennIn [11]: myTreenOut[11]: {no surfacing: {0: no, 1: {flippers: {0: no, 1: yes}}, 3: maybe}}nnIn [12]: treePlotter.createPlot(myTree)n

3.3 測試演算法： 使用決策樹執行分類

在trees.py中，添加下面的代碼

#使用決策樹的分類函數ndef classify(inputTree,featLabels,testVec):n firstStr = inputTree.keys()[0]n secondDict = inputTree[firstStr]n #將標籤字元串轉換為索引n featIndex = featLabels.index(firstStr)n for key in secondDict.keys():n if testVec[featIndex] == key:n if type(secondDict[key]).__name__ == dict:n classLabel = classify(secondDict[key],featLabels,testVec)n else:n classLabel = secondDict[key]n return classLabel n

我們來測試代碼

In [11]: import treesnnIn [12]: reload(trees)nOut[12]: <module trees from trees.pyc>nnIn [14]: myDat,labels = trees.createDataSet()nnIn [15]: labelsnOut[15]: [no surfacing, flippers]nnIn [16]: myTree = treePlotter.retrieveTree(0)nnIn [17]: myTreenOut[17]: {no surfacing: {0: no, 1: {flippers: {0: no, 1: yes}}}}nnIn [18]: trees.classify(myTree,labels,[1,1])nOut[18]: yesnnIn [19]: trees.classify(myTree,labels,[1,0])nOut[19]: non

將此結果與之前的圖做比較，不難發現，結果相符。

3.3.2 使用演算法 ：決策樹的存儲

構造決策樹是一個很耗時的事情，如果數據集很大，將會非常耗時間。為此，我們調用python模塊的pickle序列化對象。序列化對象可以在磁碟上保存文件，並在需要的時候讀取出來。

#使用pickle模塊存儲決策樹ndef storeTree(inputTree,filename) :n import picklen fw = open(filename, w)n pickle.dump(inputTree,fw)n fw.closen ndef grabTree(filename):n import picklen fr = open(filename)n return pickle.load(fr)n

測試代碼：

In [22]: reload(trees)nOut[22]: <module trees from trees.py>nnIn [23]: trees.storeTree(myTree,rE:MLML_source_codemliaCh03classifierStorage.txt)nnIn [24]: trees.grabTree(rE:MLML_source_codemliaCh03classifierStorage.txt)nOut[24]: {no surfacing: {0: no, 1: {flippers: {0: no, 1: yes}}}}n

通過上面的代碼，我們可以對數據分類時重新學習一遍。

3.4 示例：使用決策樹預測隱形眼鏡類型

眼科醫生是如何判斷患者需要佩戴的鏡片類型的。

由於前面已經寫好了演算法模塊：

我們載入本地的數據集之後，可以直接測試代碼：

In [5]: import treesnnIn [6]: reload(trees)nOut[6]: <module trees from trees.pyc>nnIn [8]: import treePlottersnnIn [9]: reload(treePlotters)nOut[9]: <module treePlotters from treePlotters.pyc>nnIn [11]: fr = open(rE:MLML_source_codemliaCh03lenses.txt)nnIn [12]: lenses = [inst.strip().split(t) for inst in fr.readlines()]nnIn [13]: lensesLabels = [age,prescript,astigmatic,tearRate]nnIn [14]: lensesTree = trees.createTree(lenses,lensesLabels)nnIn [15]: lensesTreenOut[15]:n{tearRate: {normal: {astigmatic: {no: {age: {pre: soft,npresbyopic: {prescript: {hyper: soft, myope: no lenses}},nyoung: soft}},nyes: {prescript: {hyper: {age: {pre: no lenses,npresbyopic: no lenses,nyoung: hard}},nmyope: hard}}}},nreduced: no lenses}}nnIn [17]: treePlotters.createPlot(lensesTree)n

最終得到上面這個圖，可是這些匹配選項可能太多了，我們將這些問題稱之為過度匹配。

為了減少這個問題，我們可以裁剪決策樹，去掉一些不必要的子節點。
推薦閱讀：