python機(jī)器學(xué)習(xí)之決策樹(shù)分類(lèi)詳解

更新時(shí)間：2017年12月20日 10:13:52 作者：Jeffrey_Cui

這篇文章主要介紹了python機(jī)器學(xué)習(xí)之決策樹(shù)分類(lèi)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

決策樹(shù)分類(lèi)與上一篇博客k近鄰分類(lèi)的最大的區(qū)別就在于，k近鄰是沒(méi)有訓(xùn)練過(guò)程的，而決策樹(shù)是通過(guò)對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分析，從而構(gòu)造決策樹(shù)，通過(guò)決策樹(shù)來(lái)對(duì)測(cè)試數(shù)據(jù)進(jìn)行分類(lèi)，同樣是屬于監(jiān)督學(xué)習(xí)的范疇。決策樹(shù)的結(jié)果類(lèi)似如下圖：

圖中方形方框代表葉節(jié)點(diǎn)，帶圓邊的方框代表決策節(jié)點(diǎn)，決策節(jié)點(diǎn)與葉節(jié)點(diǎn)的不同之處就是決策節(jié)點(diǎn)還需要通過(guò)判斷該節(jié)點(diǎn)的狀態(tài)來(lái)進(jìn)一步分類(lèi)。

那么如何通過(guò)訓(xùn)練數(shù)據(jù)來(lái)得到這樣的決策樹(shù)呢？

這里涉及要信息論中一個(gè)很重要的信息度量方式，香農(nóng)熵。通過(guò)香農(nóng)熵可以計(jì)算信息增益。

香農(nóng)熵的計(jì)算公式如下：

p(xi)代表數(shù)據(jù)被分在i類(lèi)的概率，可以通過(guò)計(jì)算數(shù)據(jù)集中i類(lèi)的個(gè)數(shù)與總的數(shù)據(jù)個(gè)數(shù)之比得到，計(jì)算香農(nóng)熵的python代碼如下：

from math import log 


def calcShannonEnt(dataSet): 
  numEntries=len(dataSet) 
  labelCounts={} 
  for featVec in dataSet: 
    currentLabel=featVec[-1] 
    if currentLabel not in labelCounts.keys(): 
      labelCounts[currentLabel]=0 
    labelCounts[currentLabel]+=1 
  shannonEnt=0.0 
  for key in labelCounts: 
    prob=float(labelCounts[key])/numEntries 
    shannonEnt-=prob*log(prob,2) 
  return shannonEnt

一般來(lái)說(shuō)，數(shù)據(jù)集中，不同的類(lèi)別越多，即信息量越大，那么熵值越大，通過(guò)計(jì)算熵，就可以知道選擇哪一個(gè)特征能夠最好的分開(kāi)數(shù)據(jù)，這個(gè)特征就是一個(gè)決策節(jié)點(diǎn)。

下面就可以根據(jù)訓(xùn)練數(shù)據(jù)開(kāi)始構(gòu)造決策樹(shù)。

首先編寫(xiě)一個(gè)根據(jù)給定特征劃分?jǐn)?shù)據(jù)集的函數(shù)：

#劃分?jǐn)?shù)據(jù)集，返回第axis軸為value值的數(shù)據(jù)集 
def splitDataSet(dataset,axis,value): 
  retDataSet=[] 
  for featVec in dataset: 
    if featVec[axis]==value: 
      reducedFeatVec=featVec[:] 
      del(reducedFeatVec[axis]) 
      retDataSet.append(reducedFeatVec) 
  return retDataSet

下面找出數(shù)據(jù)集中能夠最好劃分?jǐn)?shù)據(jù)的那個(gè)特征，它的原理是計(jì)算經(jīng)過(guò)每一個(gè)特征軸劃分后的數(shù)據(jù)的信息增益，信息增益越大，代表通過(guò)該特征軸劃分是最優(yōu)的。

#選擇最好的數(shù)據(jù)集劃分方式，返回最佳的軸 
def chooseBestFeatureToSplit(dataset): 
  numFeatures=len(dataset[0])-1 
  baseEntrypy=calcShannonEnt(dataset) 
  bestInfoGain=0.0 
  bestFeature=-1 
  for i in range(numFeatures): 
    featList=[example[i] for example in dataset] 
    uniqueVals=set(featList) 
    newEntrypy=0.0 
    for value in uniqueVals: 
      subDataSet=splitDataSet(dataset,i,value) 
      prob=len(subDataSet)/float(len(dataset)) 
      newEntrypy+=prob*calcShannonEnt(subDataSet) 
    infoGain=baseEntrypy-newEntrypy        #計(jì)算信息增益，信息增益最大，就是最好的劃分 
    if infoGain>bestInfoGain: 
      bestInfoGain=infoGain 
      bestFeature=i 
  return bestFeature

找出最優(yōu)的劃分軸之后，便可以通過(guò)遞歸來(lái)構(gòu)建決策樹(shù)，遞歸有兩個(gè)終止條件，第一個(gè)是程序遍歷完所有劃分?jǐn)?shù)據(jù)集的特征軸，第二個(gè)是每個(gè)分支下的所有實(shí)例都有相同的分類(lèi)。那么，這里有一個(gè)問(wèn)題，就是當(dāng)遍歷完所有數(shù)據(jù)集時(shí)，分出來(lái)的數(shù)據(jù)還不是同一類(lèi)別，這種時(shí)候，一般選取類(lèi)別最多的作為該葉節(jié)點(diǎn)的分類(lèi)。

首先編寫(xiě)一個(gè)在類(lèi)別向量中找出類(lèi)別最多的那一類(lèi)：

#計(jì)算類(lèi)型列表中，類(lèi)型最多的類(lèi)型 
def majorityCnt(classList): 
  classCount={} 
  for vote in classList: 
    if vote not in classCount.keys(): 
      classCount[vote]=0 
    classCount[vote]+=1 
  sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True) 
  return sortedClassCount[0][0]

遞歸創(chuàng)建決策樹(shù)：

#根據(jù)訓(xùn)練數(shù)據(jù)創(chuàng)建樹(shù) 
def createTree(dataSet,labels): 
  myLabels=labels[:] 
  classList=[example[-1] for example in dataSet] #類(lèi)別 
  if classList.count(classList[0])==len(classList):#數(shù)據(jù)集中都是同類(lèi) 
    return classList[0] 
  if len(dataSet[0])==1:#訓(xùn)練集中只有一個(gè)數(shù)據(jù) 
    return majorityCnt(classList) 
  bestFeat=chooseBestFeatureToSplit(dataSet) 
  bestFeatLabel=myLabels[bestFeat] 
  myTree={bestFeatLabel:{}} 
  del(myLabels[bestFeat]) 
  featValue=[example[bestFeat] for example in dataSet] 
  uniqueVal=set(featValue) 
  for value in uniqueVal: 
    subLabels=myLabels[:] 
    myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels) 
  return myTree

將上述代碼保存到tree.py中，在命令窗口輸入以下代碼：

>>> dataSet=[[1,1,'yes'], 
       [1,1,'yes'], 
       [1,0,'no'], 
       [0,1,'no'], 
       [0,1,'no']] 
>>> labels=['no sufacing','flippers'] 
>>> tree.createTree(dataSet,labels) 
{'no sufacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

就得到了決策樹(shù)的結(jié)構(gòu)，可以畫(huà)出樹(shù)的結(jié)構(gòu)圖

上面數(shù)據(jù)的實(shí)際意義是通過(guò)生物特征，來(lái)判斷是否屬于魚(yú)類(lèi)，第一列數(shù)據(jù)中1代表在水中可以生存，0代表在水中不可以生存。第二列中1代表有腳蹼，0代表沒(méi)有腳蹼。yes是魚(yú)類(lèi)，no不是魚(yú)類(lèi)。label是訓(xùn)練數(shù)據(jù)中每一列代表的意義。那么通過(guò)訓(xùn)練數(shù)據(jù)我們就構(gòu)造出了決策樹(shù)，由圖可知，我們首先可以根據(jù)第一列特征，即在水中是否可以生存來(lái)進(jìn)行第一步判斷，不可以生存的肯定不是魚(yú)類(lèi)，可以生存的還要看是否有腳蹼，有腳蹼的才是魚(yú)類(lèi)。

不難看出，決策樹(shù)最大的優(yōu)勢(shì)就是它的數(shù)據(jù)形式易于理解，分類(lèi)方式直觀。

訓(xùn)練出決策樹(shù)之后，我們就可以根據(jù)根據(jù)決策樹(shù)來(lái)對(duì)新的測(cè)試數(shù)據(jù)進(jìn)行分類(lèi)。

分類(lèi)代碼如下：

#根據(jù)決策樹(shù)分類(lèi) 
def classify(inputTree,featLabels,testVec): 
  firstStr=inputTree.keys()[0] 
  secondDict=inputTree[firstStr] 
  featIndex=featLabels.index(firstStr) 
  for key in secondDict.keys(): 
    if testVec[featIndex]==key: 
      if type(secondDict[key]).__name__=='dict': 
        classLabel=classify(secondDict[key],featLabels,testVec) 
      else: 
        classLabel=secondDict[key] 
  return classLabel

這里有一個(gè)通過(guò)決策數(shù)算法進(jìn)行分類(lèi)的一個(gè)實(shí)例，眼科醫(yī)生是如何判斷患者需要佩戴隱形眼鏡的類(lèi)型的。

判斷的結(jié)果有三種，硬材料，軟材料和不適合佩戴。

訓(xùn)練數(shù)據(jù)采用隱形眼鏡數(shù)據(jù)集，數(shù)據(jù)集來(lái)自UCI數(shù)據(jù)庫(kù)，它包含了很多患者眼部狀況的觀察條件以及醫(yī)生推薦的眼鏡類(lèi)型。

數(shù)據(jù)集如下：

測(cè)試代碼如下：

def example(): 
  fr=open('lenses.txt') 
  lenses=[inst.strip().split('\t') for inst in fr.readlines()] 
  lensesLabels=['age','prescript','astigmatic','tearRate'] 
  lensesTree=createTree(lenses,lensesLabels) 
  return lensesTree

結(jié)果：