python編寫(xiě)分類決策樹(shù)的代碼

更新時(shí)間：2017年12月21日 11:48:44 作者：開(kāi)貳錘

這篇文章主要為大家詳細(xì)介紹了python編寫(xiě)分類決策樹(shù)的代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

決策樹(shù)通常在機(jī)器學(xué)習(xí)中用于分類。

優(yōu)點(diǎn)：計(jì)算復(fù)雜度不高，輸出結(jié)果易于理解，對(duì)中間值缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。
缺點(diǎn)：可能會(huì)產(chǎn)生過(guò)度匹配問(wèn)題。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型。

1.信息增益

劃分?jǐn)?shù)據(jù)集的目的是：將無(wú)序的數(shù)據(jù)變得更加有序。組織雜亂無(wú)章數(shù)據(jù)的一種方法就是使用信息論度量信息。通常采用信息增益，信息增益是指數(shù)據(jù)劃分前后信息熵的減少值。信息越無(wú)序信息熵越大，獲得信息增益最高的特征就是最好的選擇。
熵定義為信息的期望，符號(hào)xi的信息定義為：

其中p(xi)為該分類的概率。
熵，即信息的期望值為：

計(jì)算信息熵的代碼如下：

def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {}
  for featVec in dataSet:
    currentLabel = featVec[-1]
    if currentLabel not in labelCounts:
      labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
  shannonEnt = 0
  for key in labelCounts:
    shannonEnt = shannonEnt - (labelCounts[key]/numEntries)*math.log2(labelCounts[key]/numEntries)
  return shannonEnt

可以根據(jù)信息熵，按照獲取最大信息增益的方法劃分?jǐn)?shù)據(jù)集。

2.劃分?jǐn)?shù)據(jù)集

劃分?jǐn)?shù)據(jù)集就是將所有符合要求的元素抽出來(lái)。

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

3.選擇最好的數(shù)據(jù)集劃分方式

信息增益是熵的減少或者是信息無(wú)序度的減少。

def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1
  bestInfoGain = 0
  bestFeature = -1
  baseEntropy = calcShannonEnt(dataSet)
  for i in range(numFeatures):
    allValue = [example[i] for example in dataSet]#列表推倒，創(chuàng)建新的列表
    allValue = set(allValue)#最快得到列表中唯一元素值的方法
    newEntropy = 0
    for value in allValue:
      splitset = splitDataSet(dataSet,i,value)
      newEntropy = newEntropy + len(splitset)/len(dataSet)*calcShannonEnt(splitset)
    infoGain = baseEntropy - newEntropy
    if infoGain > bestInfoGain:
      bestInfoGain = infoGain
      bestFeature = i
  return bestFeature

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

結(jié)束條件為：程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，或每個(gè)分支下的所有實(shí)例都具有相同的分類。
當(dāng)數(shù)據(jù)集已經(jīng)處理了所有屬性，但是類標(biāo)簽還不唯一時(shí)，采用多數(shù)表決的方式?jīng)Q定葉子節(jié)點(diǎn)的類型。

def majorityCnt(classList):
 classCount = {}
 for value in classList:
  if value not in classCount: classCount[value] = 0
  classCount[value] += 1
 classCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
 return classCount[0][0]

生成決策樹(shù)：

def createTree(dataSet,labels):
 classList = [example[-1] for example in dataSet]
 labelsCopy = labels[:]
 if classList.count(classList[0]) == len(classList):
  return classList[0]
 if len(dataSet[0]) == 1:
  return majorityCnt(classList)
 bestFeature = chooseBestFeatureToSplit(dataSet)
 bestLabel = labelsCopy[bestFeature]
 myTree = {bestLabel:{}}
 featureValues = [example[bestFeature] for example in dataSet]
 featureValues = set(featureValues)
 del(labelsCopy[bestFeature])
 for value in featureValues:
  subLabels = labelsCopy[:]
  myTree[bestLabel][value] = createTree(splitDataSet(dataSet,bestFeature,value),subLabels)
 return myTree

5.測(cè)試算法——使用決策樹(shù)分類

同樣采用遞歸的方式得到分類結(jié)果。

def classify(inputTree,featLabels,testVec):
 currentFeat = list(inputTree.keys())[0]
 secondTree = inputTree[currentFeat]
 try:
  featureIndex = featLabels.index(currentFeat)
 except ValueError as err:
  print('yes')
 try:
  for value in secondTree.keys():
   if value == testVec[featureIndex]:
    if type(secondTree[value]).__name__ == 'dict':
     classLabel = classify(secondTree[value],featLabels,testVec)
    else:
     classLabel = secondTree[value]
  return classLabel
 except AttributeError:
  print(secondTree)

6.完整代碼如下

import numpy as np
import math
import operator
def createDataSet():
 dataSet = [[1,1,'yes'],
    [1,1,'yes'],
    [1,0,'no'],
    [0,1,'no'],
    [0,1,'no'],]
 label = ['no surfacing','flippers']
 return dataSet,label

def calcShannonEnt(dataSet):
 numEntries = len(dataSet)
 labelCounts = {}
 for featVec in dataSet:
  currentLabel = featVec[-1]
  if currentLabel not in labelCounts:
   labelCounts[currentLabel] = 0
  labelCounts[currentLabel] += 1
 shannonEnt = 0
 for key in labelCounts:
  shannonEnt = shannonEnt - (labelCounts[key]/numEntries)*math.log2(labelCounts[key]/numEntries)
 return shannonEnt


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

def chooseBestFeatureToSplit(dataSet):
 numFeatures = len(dataSet[0]) - 1
 bestInfoGain = 0
 bestFeature = -1
 baseEntropy = calcShannonEnt(dataSet)
 for i in range(numFeatures):
  allValue = [example[i] for example in dataSet]
  allValue = set(allValue)
  newEntropy = 0
  for value in allValue:
   splitset = splitDataSet(dataSet,i,value)
   newEntropy = newEntropy + len(splitset)/len(dataSet)*calcShannonEnt(splitset)
  infoGain = baseEntropy - newEntropy
  if infoGain > bestInfoGain:
   bestInfoGain = infoGain
   bestFeature = i
 return bestFeature

def majorityCnt(classList):
 classCount = {}
 for value in classList:
  if value not in classCount: classCount[value] = 0
  classCount[value] += 1
 classCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
 return classCount[0][0]   

def createTree(dataSet,labels):
 classList = [example[-1] for example in dataSet]
 labelsCopy = labels[:]
 if classList.count(classList[0]) == len(classList):
  return classList[0]
 if len(dataSet[0]) == 1:
  return majorityCnt(classList)
 bestFeature = chooseBestFeatureToSplit(dataSet)
 bestLabel = labelsCopy[bestFeature]
 myTree = {bestLabel:{}}
 featureValues = [example[bestFeature] for example in dataSet]
 featureValues = set(featureValues)
 del(labelsCopy[bestFeature])
 for value in featureValues:
  subLabels = labelsCopy[:]
  myTree[bestLabel][value] = createTree(splitDataSet(dataSet,bestFeature,value),subLabels)
 return myTree


def classify(inputTree,featLabels,testVec):
 currentFeat = list(inputTree.keys())[0]
 secondTree = inputTree[currentFeat]
 try:
  featureIndex = featLabels.index(currentFeat)
 except ValueError as err:
  print('yes')
 try:
  for value in secondTree.keys():
   if value == testVec[featureIndex]:
    if type(secondTree[value]).__name__ == 'dict':
     classLabel = classify(secondTree[value],featLabels,testVec)
    else:
     classLabel = secondTree[value]
  return classLabel
 except AttributeError:
  print(secondTree)

if __name__ == "__main__":
 dataset,label = createDataSet()
 myTree = createTree(dataset,label)
 a = [1,1]
 print(classify(myTree,label,a))

7.編程技巧

extend與append的區(qū)別

 newVec.extend(featVec[axis+1:])
 retDataset.append(newVec)

extend([])，是將列表中的每個(gè)元素依次加入新列表中
append()是將括號(hào)中的內(nèi)容當(dāng)做一項(xiàng)加入到新列表中

列表推到

創(chuàng)建新列表的方式

allValue = [example[i] for example in dataSet]

提取列表中唯一的元素

allValue = set(allValue)

列表/元組排序,sorted()函數(shù)

classCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

列表的復(fù)制

labelsCopy = labels[:]

代碼及數(shù)據(jù)集下載：決策樹(shù)

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

您可能感興趣的文章:

最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

python編寫(xiě)分類決策樹(shù)的代碼

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具