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

更新時(shí)間：2017年11月01日 10:40:18 作者：嗜血的草

這篇文章主要為大家詳細(xì)介紹了機(jī)器學(xué)習(xí)python實(shí)戰(zhàn)之決策樹的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

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

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

一、信息增益

　　劃分?jǐn)?shù)據(jù)集的原則是：將無(wú)序的數(shù)據(jù)變的有序。在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)生的變化稱為信息增益。知道如何計(jì)算信息增益，我們就可以計(jì)算根據(jù)每個(gè)特征劃分?jǐn)?shù)據(jù)集獲得的信息增益，選擇信息增益最高的特征就是最好的選擇。首先我們先來(lái)明確一下信息的定義：符號(hào)xi的信息定義為 l(xi)=-log2 p(xi)，p(xi)為選擇該類的概率。那么信息源的熵H=-∑p(xi)·log2 p(xi)。根據(jù)這個(gè)公式我們下面編寫代碼計(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。我們可以先用一個(gè)簡(jiǎn)單的例子來(lái)測(cè)試一下

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)我們?cè)黾訑?shù)據(jù)的類別時(shí)，熵會(huì)增加。這里更改后的數(shù)據(jù)集的類別有三種‘yes'、‘no'、‘maybe'，也就是說(shuō)數(shù)據(jù)越混亂，熵就越大。

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

def splitDataSet(dataSet,axis,value):
 retDataSet = []
 for featVec in dataSet:
  if featVec[axis] == value:
   reducedfeatVec = featVec[:axis]
   reducedfeatVec.extend(featVec[axis+1:])
   retDataSet.append(reducedfeatVec)
 return retDataSet

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

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

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

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

def choosebestfeatureToSplit(dataSet):
 Numfeatures = len(dataSet)-1
 BaseShannonEnt = calcShannonEnt(dataSet)
 bestInfoGain=0.0
 bestfeature = -1
 for i in range(Numfeatures):
  featlist = [example[i] for example in dataSet]
  featSet = set(featlist)
  newEntropy = 0.0
  for value in featSet:
   subDataSet = splitDataSet(dataSet,i,value)
   prob = len(subDataSet)/len(dataSet)
   newEntropy += prob*calcShannonEnt(subDataSet) 
  infoGain = BaseShannonEnt-newEntropy
  if infoGain>bestInfoGain:
   bestInfoGain=infoGain
   bestfeature = i
 return bestfeature

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

接下來(lái)開始遞歸構(gòu)建決策樹，我們需要在構(gòu)建前計(jì)算列的數(shù)目，查看算法是否使用了所有的屬性。這個(gè)函數(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é)果，我們看起來(lái)并不直觀，所以我們接下來(lái)用matplotlib注解繪制樹形圖。matplotlib提供了一個(gè)注解工具annotations，它可以在數(shù)據(jù)圖形上添加文本注釋。我們先來(lái)測(cè)試一下這個(gè)注解工具的使用。

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()

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

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

測(cè)試結(jié)果如下

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

可以看出樹的深度確實(shí)是有兩層，葉節(jié)點(diǎn)的數(shù)目是3。接下來(lái)我們給出繪制決策樹圖的關(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()

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: