pythonで決定木を実装する

本文では、Pythonで決定木を実現する具体的なコードを共有し、皆様の参考にしました。具体的な内容は以下の通りです。

アルゴリズムの長所と短所：

利点：計算複雑度が低く、出力結果が理解しやすく、中間値の欠如に敏感ではありません。関連しない特徴データを処理できます。

欠点：過度なマッチング問題が発生する可能性があります。

適用可能なデータタイプ：数値型と名前型

アルゴリズムの思想：

1.決定木構築の全体思想：

決定木は単純にif-elseの構造は同じですが、結果は根から葉までの判断と選択を続けることができる決定木を生成しますが、ここでのif-elseは、私たちが設定するものではないので、私たちはコンピュータがこの方法に基づいて私たちが必要とする決定木を得られるようにする方法を提供する必要があります。この方法の重点は、これらの多くの特徴から価値のある特徴を選び出し、根から葉に向かって最も良い順序で選ぶことです。これが完了すると、再帰的に決定木を構築することができます。

2.情報增益

データセットを分割する最大の原則は、無序なデータをより整然としたものにすることです。これが情報の有序・無序の問題に関連しているため、情報エントロピーに自然と考えることができます。ここでは、計算に使用するのは情報エントロピーです（別の方法はジニ不純度です）。以下の公式によります：

データが必要とする条件：

1 データはリストの要素で構成されるリストで、すべての列の要素は同じデータ長さを持つ必要があります。
2 データの最後の列または各インスタンスの最後の要素は、現在のインスタンスのカテゴリラベルであるべきです。

関数：

calcShannonEnt(dataSet)

データセットのシャノンエントロピーを計算します。二つのステップで行います。まず、頻度を計算し、次に公式に基づいてシャノンエントロピーを計算します。

splitDataSet(dataSet, aixs, value)

データセットを分割し、X[aixs] == valueを満たす値を一つの集合にまとめ、分割された集合を返します（分割に使用されたaixs属性は除いて、必要ではありません）。

chooseBestFeature(dataSet)

属性の最も良いものを選んで分類を行い、考え方は非常にシンプルで、各属性に対して分類を行い、どれが良いかを確認します。ここでは、リスト内のユニークな要素を選択するためにsetを使用しており、これは非常に高速な方法です。

majorityCnt(classList)

因為我們遞迴構建決策樹是根據屬性的消耗進行計算的，所以可能會存在最後屬性用完了，但是分類還沒有算完，這時候就會採用多數決的方式計算節點分類

createTree(dataSet, labels)

基於遞迴構建決策樹。這裡的label更多是對於分類特徵的名稱，為了更好看和後面的理解。

#coding=utf-8
import operator
from math import log
import time
def createDataSet():
  dataSet=[[1,1,'yes'],
      [1,1,'yes'],
      [1,0,'no'],
      [0,1,'no'],
      [0,1,'no']]
  labels = ['no surfaceing','flippers']
  return dataSet, labels
#计算香农熵
def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {}
  for feaVec in dataSet:
    currentLabel = feaVec[-1]
    if currentLabel not in labelCounts:
      labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
  shannonEnt = 0.0
  for key in labelCounts:
    prob = float(labelCounts[key])/numEntries
    shannonEnt -= * log(prob, 2)
  return shannonEnt
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
def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1#因为数据集的最后一项是标签
  baseEntropy = calcShannonEnt(dataSet)
  bestInfoGain = 0.0
  bestFeature = -1
  for i in range(numFeatures):
    featList = [example[i] for example in dataSet]
    uniqueVals = set(featList)
    newEntropy = 0.0
    for value in uniqueVals:
      subDataSet = splitDataSet(dataSet, i, value)
      prob = len(subDataSet) / float(len(dataSet))
      newEntropy += * calcShannonEnt(subDataSet)
    infoGain = baseEntropy -newEntropy
    if infoGain > bestInfoGain:
      bestInfoGain = infoGain
      bestFeature = i
  return bestFeature
#因为我们递归构建决策树是根据属性的消耗进行计算的，所以可能会存在最后属性用完了，但是分类
#还是没有算完，这时候就会采用多数表决的方式计算节点分类
def majorityCnt(classList):
  classCount = {}
  for vote in classList:
    if vote not in classCount.keys():
      classCount[vote] = 0
    classCount[vote] += 1
  return max(classCount)     
def createTree(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)
  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[:]# 元のリストの内容を変更しないようにコピーしました
    myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, "","")) 
                    (bestFeat, value), subLabels)
  return myTree
def main():
  data, label = createDataSet()
  t1 = time.clock()
  myTree = createTree(data, label)
  t2 = time.clock()
  print myTree
  print 'execute for ', t2-t1
if __name__=='__main__':
  main()

これで本文のすべての内容が終わりました。皆様の学習に役立つことを願っています。また、呐喊チュートリアルを多くの皆様に支持していただけると嬉しいです。

声明：本文の内容はインターネットから取得しており、著作権者に帰属します。インターネットユーザーが自発的に貢献し、自己でアップロードしたものであり、本サイトは所有権を有しません。また、人工編集もなく、関連する法的責任も負いません。著作権侵害の疑いがある場合は、メールを送信してください：notice#oldtoolbag.com（メールを送信する際、#を@に変更してください。報告を行い、関連する証拠を提供してください。一旦確認がとりたいとされると、本サイトは即座に侵害疑いのコンテンツを削除します。）