python機器學習理論與實戰(zhàn)（二）決策樹

更新時間：2018年01月19日 11:38:15 作者：marvin521

這篇文章主要介紹了python機器學習理論與實戰(zhàn)第二篇，決策樹的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下

決策樹也是有監(jiān)督機器學習方法。電影《無恥混蛋》里有一幕游戲，在德軍小酒館里有幾個人在玩20問題游戲，游戲規(guī)則是一個設迷者在紙牌中抽出一個目標（可以是人，也可以是物），而猜謎者可以提問題，設迷者只能回答是或者不是，在幾個問題（最多二十個問題）之后，猜謎者通過逐步縮小范圍就準確的找到了答案。這就類似于決策樹的工作原理。（圖一）是一個判斷郵件類別的工作方式，可以看出判別方法很簡單，基本都是閾值判斷，關鍵是如何構(gòu)建決策樹，也就是如何訓練一個決策樹。

（圖一）

構(gòu)建決策樹的偽代碼如下：

Check if every item in the dataset is in the same class:
    If so return the class label
    Else 
      find the best feature to split the data
       split the dataset 
       create a branch node
       for each split
          call create Branch and add the result to the branch node

      return branch node

原則只有一個，盡量使得每個節(jié)點的樣本標簽盡可能少，注意上面?zhèn)未a中一句說：find the best feature to split the data，那么如何find thebest feature?一般有個準則就是盡量使得分支之后節(jié)點的類別純一些，也就是分的準確一些。如（圖二）中所示，從海洋中撈取的5個動物，我們要判斷他們是否是魚，先用哪個特征？

（圖二）

為了提高識別精度，我們是先用“離開陸地能否存活”還是“是否有蹼”來判斷？我們必須要有一個衡量準則，常用的有信息論、基尼純度等，這里使用前者。我們的目標就是選擇使得分割后數(shù)據(jù)集的標簽信息增益最大的那個特征，信息增益就是原始數(shù)據(jù)集標簽基熵減去分割后的數(shù)據(jù)集標簽熵，換句話說，信息增益大就是熵變小，使得數(shù)據(jù)集更有序。熵的計算如（公式一）所示：

有了指導原則，那就進入代碼實戰(zhàn)階段，先來看看熵的計算代碼：

def calcShannonEnt(dataSet): 
  numEntries = len(dataSet) 
  labelCounts = {} 
  for featVec in dataSet: #the the number of unique elements and their occurance 
    currentLabel = featVec[-1] 
    if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 
    labelCounts[currentLabel] += 1 #收集所有類別的數(shù)目，創(chuàng)建字典 
  shannonEnt = 0.0 
  for key in labelCounts: 
    prob = float(labelCounts[key])/numEntries 
    shannonEnt -= prob * log(prob,2) #log base 2 計算熵 
  return shannonEnt

有了熵的計算代碼，接下來看依照信息增益變大的原則選擇特征的代碼：

def splitDataSet(dataSet, axis, value): 
  retDataSet = [] 
  for featVec in dataSet: 
    if featVec[axis] == value: 
      reducedFeatVec = featVec[:axis]   #chop out axis used for splitting 
      reducedFeatVec.extend(featVec[axis+1:]) 
      retDataSet.append(reducedFeatVec) 
  return retDataSet 
   
def chooseBestFeatureToSplit(dataSet): 
  numFeatures = len(dataSet[0]) - 1   #the last column is used for the labels 
  baseEntropy = calcShannonEnt(dataSet) 
  bestInfoGain = 0.0; bestFeature = -1 
  for i in range(numFeatures):    #iterate over all the features 
    featList = [example[i] for example in dataSet]#create a list of all the examples of this feature 
    uniqueVals = set(featList)    #get a set of unique values 
    newEntropy = 0.0 
    for value in uniqueVals: 
      subDataSet = splitDataSet(dataSet, i, value) 
      prob = len(subDataSet)/float(len(dataSet)) 
      newEntropy += prob * calcShannonEnt(subDataSet)    
    infoGain = baseEntropy - newEntropy   #calculate the info gain; ie reduction in entropy 
    if (infoGain > bestInfoGain):    #compare this to the best gain so far  #選擇信息增益最大的代碼在此 
      bestInfoGain = infoGain     #if better than current best, set to best 
      bestFeature = i 
  return bestFeature           #returns an integer

從最后一個if可以看出，選擇使得信息增益最大的特征作為分割特征，現(xiàn)在有了特征分割準則，繼續(xù)進入一下個環(huán)節(jié)，如何構(gòu)建決策樹，其實就是依照最上面的偽代碼寫下去，采用遞歸的思想依次分割下去，直到執(zhí)行完成就構(gòu)建了決策樹。代碼如下：

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] 
 
def createTree(dataSet,labels): 
  classList = [example[-1] for example in dataSet] 
  if classList.count(classList[0]) == len(classList):  
    return classList[0]#stop splitting when all of the classes are equal 
  if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet 
    return majorityCnt(classList) 
  bestFeat = chooseBestFeatureToSplit(dataSet) 
  bestFeatLabel = labels[bestFeat] 
  myTree = {bestFeatLabel:{}} 
  del(labels[bestFeat]) 
  featValues = [example[bestFeat] for example in dataSet] 
  uniqueVals = set(featValues) 
  for value in uniqueVals: 
    subLabels = labels[:]    #copy all of labels, so trees don't mess up existing labels 
    myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) 
  return myTree

用圖二的樣本構(gòu)建的決策樹如（圖三）所示：

（圖三）

有了決策樹，就可以用它做分類咯，分類代碼如下：

def classify(inputTree,featLabels,testVec): 
  firstStr = inputTree.keys()[0] 
  secondDict = inputTree[firstStr] 
  featIndex = featLabels.index(firstStr) 
  key = testVec[featIndex] 
  valueOfFeat = secondDict[key] 
  if isinstance(valueOfFeat, dict):  
    classLabel = classify(valueOfFeat, featLabels, testVec) 
  else: classLabel = valueOfFeat 
  return classLabel

最后給出序列化決策樹（把決策樹模型保存在硬盤上）的代碼：

def storeTree(inputTree,filename): 
  import pickle 
  fw = open(filename,'w') 
  pickle.dump(inputTree,fw) 
  fw.close() 
   
def grabTree(filename): 
  import pickle 
  fr = open(filename) 
  return pickle.load(fr)

優(yōu)點：檢測速度快

缺點：容易過擬合，可以采用修剪的方式來盡量避免

參考文獻：machine learning in action

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: