python機器學習之決策樹分類詳解

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

這篇文章主要介紹了python機器學習之決策樹分類，具有一定的參考價值，感興趣的小伙伴們可以參考一下

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

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

那么如何通過訓練數(shù)據(jù)來得到這樣的決策樹呢？

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

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

p(xi)代表數(shù)據(jù)被分在i類的概率，可以通過計算數(shù)據(jù)集中i類的個數(shù)與總的數(shù)據(jù)個數(shù)之比得到，計算香農(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

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

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

首先編寫一個根據(jù)給定特征劃分數(shù)據(jù)集的函數(shù)：

#劃分數(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ù)集中能夠最好劃分數(shù)據(jù)的那個特征，它的原理是計算經(jīng)過每一個特征軸劃分后的數(shù)據(jù)的信息增益，信息增益越大，代表通過該特征軸劃分是最優(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        #計算信息增益，信息增益最大，就是最好的劃分 
    if infoGain>bestInfoGain: 
      bestInfoGain=infoGain 
      bestFeature=i 
  return bestFeature

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

首先編寫一個在類別向量中找出類別最多的那一類：

#計算類型列表中，類型最多的類型 
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)建決策樹：

#根據(jù)訓練數(shù)據(jù)創(chuàng)建樹 
def createTree(dataSet,labels): 
  myLabels=labels[:] 
  classList=[example[-1] for example in dataSet] #類別 
  if classList.count(classList[0])==len(classList):#數(shù)據(jù)集中都是同類 
    return classList[0] 
  if len(dataSet[0])==1:#訓練集中只有一個數(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'}}}}

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

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

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

訓練出決策樹之后，我們就可以根據(jù)根據(jù)決策樹來對新的測試數(shù)據(jù)進行分類。

分類代碼如下：

#根據(jù)決策樹分類 
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

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

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

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

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

測試代碼如下：

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é)果：