ID 3決定木Python実現

本博文の内容は主に「Machine Learning in Action」の中国語版「機械学習実戦」の小結を独学し、原書では呼び出したモジュールの関数についてあまり説明していないが、本文は総括と補充を行った.
アルゴリズムの原理
情報利得の評価基準に従って、現在の最適な特徴を選択してデータセットを分割し、最後に分割されたサブデータセットが1つのタイプのサンプルのみを含むか、またはすべての特徴を使い切るまで、最後にサブセットの多数のカテゴリが最もそのサブセットの最終カテゴリである(もちろんあってもよい).
じょうほうりとく
エントロピー(Entropy):情報の期待値エントロピーは玄の概念であり、人間の成長過程は実際にはエントロピーを下げる過程であり、人間が生まれたばかりのように、脳内のニューロンは互いに接続されており、年齢の増加に伴って相互に接続されたニューロンを絶えず遮断している.この過程は人類が自然の情報を絶えず総括し、精錬し、簡素化することにも理解できる.この過程はエントロピーの低下である.人が学習の苦痛を感じるのはたいていこの原因だ.
エントロピーの定義式
分類されないトランザクションが複数の分類に分割される可能性がある場合、シンボルxiの情報は、次のように定義される.
l(xi)=−log2p(xi)
p(xi)はこのカテゴリの確率である.
このデータセットは、すべてのカテゴリのすべての可能な値に含まれる情報の期待値にエントロピーを分けます.
H=∑i=1np(xi)log2p(xi)
Pythonコード計算エントロピー

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

上記エントロピーの計算は、1つの集合のエントロピーを計算するものであり、1つの特徴に基づいて分割されたすべてのデータサブセットのエントロピーを計算するには、各サブセットのエントロピーにそのサブセットを乗じた確率を最後に加算する必要がある.この部分のPythonコードは以下の通りです.

for value in uniqueEntropy:
            subDataSet =                                         splitDataSet(dataSet,i,value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)

ID 3 Python実現
ID 3決定ツリー全体のPythonコードは以下のように実現される.

#-*- coding:utf-8 -*-
from math import log

def createDataSet():
    dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,0,'no']]
    labels=['no surfacing','flippers']
    return dataSet,labels

#           
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
#           
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
    baseEntroy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueEntropy = set(featList)
        newEntropy = 0.0
        for value in uniqueEntropy:
            subDataSet = splitDataSet(dataSet,i,value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
        infoGain = baseEntroy -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
    sortedClassCount = sorted(classCount.iteritems(),key=classCount.iteritems(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]
    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:
        subLables = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLables)
    return myTree
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
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)