機(jī)器學(xué)習(xí)python實戰(zhàn)之決策樹

決策樹原理：從數(shù)據(jù)集中找出決定性的特征對數(shù)據(jù)集進(jìn)行迭代劃分，直到某個分支下的數(shù)據(jù)都屬于同一類型，或者已經(jīng)遍歷了所有劃分?jǐn)?shù)據(jù)集的特征，停止決策樹算法。

每次劃分?jǐn)?shù)據(jù)集的特征都有很多，那么我們怎么來選擇到底根據(jù)哪一個特征劃分?jǐn)?shù)據(jù)集呢？這里我們需要引入信息增益和信息熵的概念。

一、信息增益

劃分?jǐn)?shù)據(jù)集的原則是：將無序的數(shù)據(jù)變的有序。在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)生的變化稱為信息增益。知道如何計算信息增益，我們就可以計算根據(jù)每個特征劃分?jǐn)?shù)據(jù)集獲得的信息增益，選擇信息增益最高的特征就是最好的選擇。首先我們先來明確一下信息的定義：符號xi的信息定義為 l(xi)=-log2 p(xi)，p(xi)為選擇該類的概率。那么信息源的熵H=-∑p(xi)·log2 p(xi)。根據(jù)這個公式我們下面編寫代碼計算香農(nóng)熵

def calcShannonEnt(dataSet):
 NumEntries = len(dataSet)
 labelsCount = {}
 for i in dataSet:
  currentlabel = i[-1]
  if currentlabel not in labelsCount.keys():
   labelsCount[currentlabel]=0
  labelsCount[currentlabel]+=1
 ShannonEnt = 0.0
 for key in labelsCount:
  prob = labelsCount[key]/NumEntries
  ShannonEnt -= prob*log(prob,2)
 return ShannonEnt

上面的自定義函數(shù)我們需要在之前導(dǎo)入log方法，from math import log。 我們可以先用一個簡單的例子來測試一下    
def createdataSet():
 #dataSet = [['1','1','yes'],['1','0','no'],['0','1','no'],['0','0','no']]
 dataSet = [[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,0,'no']]
 labels = ['no surfacing','flippers']
 return dataSet,labels

這里的熵為0.811，當(dāng)我們增加數(shù)據(jù)的類別時，熵會增加。這里更改后的數(shù)據(jù)集的類別有三種‘yes'、‘no'、‘maybe'，也就是說數(shù)據(jù)越混亂，熵就越大。

分類算法出了需要計算信息熵，還需要劃分?jǐn)?shù)據(jù)集。決策樹算法中我們對根據(jù)每個特征劃分的數(shù)據(jù)集計算一次熵，然后判斷按照哪個特征劃分是最好的劃分方式。

axis表示劃分?jǐn)?shù)據(jù)集的特征，value表示特征的返回值。這里需要注意extend方法和append方法的區(qū)別。舉例來說明這個區(qū)別

下面我們測試一下劃分?jǐn)?shù)據(jù)集函數(shù)的結(jié)果：

axis=0，value=1，按myDat數(shù)據(jù)集的第0個特征向量是否等于1進(jìn)行劃分。

接下來我們將遍歷整個數(shù)據(jù)集，對每個劃分的數(shù)據(jù)集計算香農(nóng)熵，找到最好的特征劃分方式

信息增益是熵的減少或數(shù)據(jù)無序度的減少。最后比較所有特征中的信息增益，返回最好特征劃分的索引。函數(shù)測試結(jié)果為

接下來開始遞歸構(gòu)建決策樹，我們需要在構(gòu)建前計算列的數(shù)目，查看算法是否使用了所有的屬性。這個函數(shù)跟跟第二章的calssify0采用同樣的方法

def majorityCnt(classlist):
 ClassCount = {}
 for vote in classlist:
  if vote not in ClassCount.keys():
   ClassCount[vote]=0
  ClassCount[vote]+=1
 sortedClassCount = sorted(ClassCount.items(),key = operator.itemgetter(1),reverse = True)
 return sortedClassCount[0][0]
 
def createTrees(dataSet,labels):
 classList = [example[-1] for example in dataSet]
 if classList.count(classList[0]) == len(classList):
  return classList[0]
 if len(dataSet[0])==1:
  return majorityCnt(classList)
 bestfeature = choosebestfeatureToSplit(dataSet)
 bestfeatureLabel = labels[bestfeature]
 myTree = {bestfeatureLabel:{}}
 del(labels[bestfeature])
 featValue = [example[bestfeature] for example in dataSet]
 uniqueValue = set(featValue)
 for value in uniqueValue:
  subLabels = labels[:]
  myTree[bestfeatureLabel][value] = createTrees(splitDataSet(dataSet,bestfeature,value),subLabels)
 return myTree

最終決策樹得到的結(jié)果如下：

有了如上的結(jié)果，我們看起來并不直觀，所以我們接下來用matplotlib注解繪制樹形圖。matplotlib提供了一個注解工具annotations，它可以在數(shù)據(jù)圖形上添加文本注釋。我們先來測試一下這個注解工具的使用。

import matplotlib.pyplot as plt
decisionNode = dict(boxstyle = 'sawtooth',fc = '0.8')
leafNode = dict(boxstyle = 'sawtooth',fc = '0.8')
arrow_args = dict(arrowstyle = '<-')
 
def plotNode(nodeTxt,centerPt,parentPt,nodeType):
 createPlot.ax1.annotate(nodeTxt,xy = parentPt,xycoords = 'axes fraction',\
       xytext = centerPt,textcoords = 'axes fraction',\
       va = 'center',ha = 'center',bbox = nodeType,\
       arrowprops = arrow_args)
 
def createPlot():
 fig = plt.figure(1,facecolor = 'white')
 fig.clf()
 createPlot.ax1 = plt.subplot(111,frameon = False)
 plotNode('test1',(0.5,0.1),(0.1,0.5),decisionNode)
 plotNode('test2',(0.8,0.1),(0.3,0.8),leafNode)
 plt.show()

測試過這個小例子之后我們就要開始構(gòu)建注解樹了。雖然有xy坐標(biāo)，但在如何放置樹節(jié)點(diǎn)的時候我們會遇到一些麻煩。所以我們需要知道有多少個葉節(jié)點(diǎn)，樹的深度有多少層。下面的兩個函數(shù)就是為了得到葉節(jié)點(diǎn)數(shù)目和樹的深度，兩個函數(shù)有相同的結(jié)構(gòu)，從第一個關(guān)鍵字開始遍歷所有的子節(jié)點(diǎn)，使用type()函數(shù)判斷子節(jié)點(diǎn)是否為字典類型，若為字典類型，則可以認(rèn)為該子節(jié)點(diǎn)是一個判斷節(jié)點(diǎn)，然后遞歸調(diào)用函數(shù)getNumleafs()，使得函數(shù)遍歷整棵樹，并返回葉子節(jié)點(diǎn)數(shù)。第2個函數(shù)getTreeDepth()計算遍歷過程中遇到判斷節(jié)點(diǎn)的個數(shù)。該函數(shù)的終止條件是葉子節(jié)點(diǎn)，一旦到達(dá)葉子節(jié)點(diǎn)，則從遞歸調(diào)用中返回，并將計算樹深度的變量加一

def getNumleafs(myTree):
 numLeafs=0
 key_sorted= sorted(myTree.keys())
 firstStr = key_sorted[0]
 secondDict = myTree[firstStr]
 for key in secondDict.keys():
  if type(secondDict[key]).__name__=='dict':
   numLeafs+=getNumleafs(secondDict[key])
  else:
   numLeafs+=1
 return numLeafs
 
def getTreeDepth(myTree):
 maxdepth=0
 key_sorted= sorted(myTree.keys())
 firstStr = key_sorted[0]
 secondDict = myTree[firstStr]
 for key in secondDict.keys():
  if type(secondDict[key]).__name__ == 'dict':
   thedepth=1+getTreeDepth(secondDict[key])
  else:
   thedepth=1
  if thedepth>maxdepth:
   maxdepth=thedepth
 return maxdepth

測試結(jié)果如下

我們先給出最終的決策樹圖來驗證上述結(jié)果的正確性

可以看出樹的深度確實是有兩層，葉節(jié)點(diǎn)的數(shù)目是3。接下來我們給出繪制決策樹圖的關(guān)鍵函數(shù)，結(jié)果就得到上圖中決策樹。

def plotMidText(cntrPt,parentPt,txtString):
 xMid = (parentPt[0]-cntrPt[0])/2.0+cntrPt[0]
 yMid = (parentPt[1]-cntrPt[1])/2.0+cntrPt[1]
 createPlot.ax1.text(xMid,yMid,txtString)
 
def plotTree(myTree,parentPt,nodeTxt):
 numLeafs = getNumleafs(myTree)
 depth = getTreeDepth(myTree)
 key_sorted= sorted(myTree.keys())
 firstStr = key_sorted[0]
 cntrPt = (plotTree.xOff+(1.0+float(numLeafs))/2.0/plotTree.totalW,plotTree.yOff)
 plotMidText(cntrPt,parentPt,nodeTxt)
 plotNode(firstStr,cntrPt,parentPt,decisionNode)
 secondDict = myTree[firstStr]
 plotTree.yOff -= 1.0/plotTree.totalD
 for key in secondDict.keys():
  if type(secondDict[key]).__name__ == 'dict':
   plotTree(secondDict[key],cntrPt,str(key))
  else:
   plotTree.xOff+=1.0/plotTree.totalW
   plotNode(secondDict[key],(plotTree.xOff,plotTree.yOff),cntrPt,leafNode)
   plotMidText((plotTree.xOff,plotTree.yOff),cntrPt,str(key))
 plotTree.yOff+=1.0/plotTree.totalD
 
def createPlot(inTree):
 fig = plt.figure(1,facecolor = 'white')
 fig.clf()
 axprops = dict(xticks = [],yticks = [])
 createPlot.ax1 = plt.subplot(111,frameon = False,**axprops)
 plotTree.totalW = float(getNumleafs(inTree))
 plotTree.totalD = float(getTreeDepth(inTree))
 plotTree.xOff = -0.5/ plotTree.totalW; plotTree.yOff = 1.0
 plotTree(inTree,(0.5,1.0),'')
 plt.show()
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助