【機械学習実戦学習ノート(2-2)】決定木python 3.6実現と簡単な応用

7219 ワード

文書ディレクトリ
  • 1.ID 3及びC 4.5アルゴリズムベース
  • 1.1シャノンエントロピー
  • を計算する
  • 1.2所与の特徴に従ってデータセット
  • を分割する.
  • 1.3最適特徴
  • を選択する.
  • 1.4多数決で
  • を実現
  • 2.ID 3、C 4に基づく.5アルゴリズム作成決定ツリー
  • 3.決定ツリーによる分類
  • 4.ストレージ決定ツリー
  • 意思決定ツリーの原理と関連概念の詳細を通じて、意思決定ツリーの学習アルゴリズムは主に3つのステップを含む:特徴選択、意思決定ツリー生成アルゴリズム、意思決定ツリー剪定枝、私たちはこの構想に従って一つ一つ関連機能を実現する.
    本稿の実現は現在主に特徴選択、ID 3及びC 4に関する.5アルゴリズム.枝切りおよびCARTアルゴリズムはしばらく関与せず,後期に補完した.
    1.ID 3およびC 4.5アルゴリズムの基礎
    前述のID 3とC 4.5の主な違いは、特徴選択基準の違いです.
  • ID 3:情報ゲイン
  • C4.5:情報ゲイン比
  • 1.1シャノンエントロピーの計算
    どちらも情報利得の計算に関与し,情報利得の計算の基礎はシャノンエントロピーの計算である.まずシャノンエントロピーを計算するコードを実現します
    from math import log
    import operator
    
    #            
    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) #  2     
        return shannonEnt
    

    次に、本のデータセットを作成し、そのデータセットのシャノンエントロピーを計算します.
    #         
    def createDataSet():
        dataSet = [[1, 1, 'yes'],
                  [1, 1, 'yes'],
                  [1, 0, 'no'],
                  [0, 1, 'no'],
                  [0, 1, 'no']]
        labels = ['no surfacing','flippers']
        return dataSet, labels
    
    myDat,labels=createDataSet()  
    myDat  #  [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
    
    calcShannonEnt(myDat)  #  0.9709505944546686
    

    1.2所与の特徴に従ってデータセットを区分する
    #            
    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
    

    テスト:
    splitDataSet(myDat,0,1)  #  [[1, 'yes'], [1, 'yes'], [0, 'no']]
    

    1.3最適特性の選択
    #             
     #             
    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 += prob * calcShannonEnt(subDataSet)
            infoGain = baseEntropy - newEntropy  # ID3
            #  infoGain = baseEntropy - newEntropy  #  C4.5 
            #          
            if (infoGain > bestInfoGain):
                bestInfoGain = infoGain
                bestFeature = i
        return bestFeature         
    

    1.4多数決の実現
    ID 3、C 4にある.5アルゴリズムの停止条件の1つは、選択可能なフィーチャーがない場合にアルゴリズムを停止することですが、この場合もノードクラスラベルが一意ではない場合は、リーフノードをどのように定義するかを決定する必要があります.この場合、葉の結点の分類は、通常、多数決の方法で決定される.
    #       
    def majorityCnt(classList):
        classCount={}
        for vote in classList:
            if vote not in classCount.keys(): 
            	classCount[vote] = 0
            classCount[vote] += 1
        #        
        sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
        # Python3     iteritems(), iteritems()  items()
        return sortedClassCount[0][0]
    

    「多数決実装」関数のコメント:
  • 1.dict.items()の役割:辞書のすべての項目をリストで返すことができます.辞書は無秩序であるため,items法で辞書のすべての項目を返すのも順序がない.
  • 2.operator.itemgetter()operatorモジュールが提供するitemgetter関数は、オブジェクトのどの次元のデータを取得するために使用され、パラメータはいくつかのシーケンス番号である.
  • 3.sorted()関数、並べ替えlist.sort()は、既存のリストを操作し、さらに操作を変更できるリストである.sortedは、従来の操作
  • ではなく、新しいlistを返します.
    2.ID 3、C 4に基づく.5アルゴリズム作成決定ツリー
    ここでは主にID 3生成アルゴリズムに基づく決定木,C 4の作成について説明する.5.ID 3生成決定ツリーコードでchooseBestFeatureToSplit(dataSet)関数のinfoGain=baseEntropy-newEntropyをinfoGain=baseEntropy-newEntropyに置き換えるだけでよい.
    #         
    def creatTree(dataSet,labels):
        classList = [example[-1] for example in dataSet]
        labels2 = labels[:]
        #              
        if classList.count(classList[0]) == len(classList):
            return classList[0]
        #                    
        if len(dataSet[0]) == 1:
            return majorityCnt(classList)
        bestFeat = chooseBestFeatureToSplit(dataSet)
        bestFeatLabel = labels2[bestFeat]
        myTree = {bestFeatLabel:{}}
        del (labels2[bestFeat])
        #        (        )     
        featValues = [example[bestFeat] for example in dataSet]
        uniqueVals = set(featValues)
        for value in uniqueVals:
            subLabels = labels2[:] #      
            #   
            myTree[bestFeatLabel][value] = creatTree(splitDataSet(dataSet, bestFeat, value),subLabels)
        return myTree
    

    「creatTree」関数のコメント:
  • 1.list.count(obj)は、ある要素がリストに現れる回数
  • を統計する.
  • 2.del,list.remove(),list.pop()del:インデックス位置に基づいて単一の値または指定範囲内の値を削除します.list.remove():単一の要素を削除し、最初の条件に合致する要素を削除し、値によって削除し、戻り値が空です.list.pop():インデックス位置要素を削除し、パラメータなしで最後の要素を削除し、削除した要素値を返します.

  • テスト:
    myTree = creatTree(myDat, labels)
    myTree  #  {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
    

    3.決定木による分類
    #           
    def classify(inputTree, featLabels, testVec):
        firstStr = list(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':
                #if isinstance(secondDict[key], dict):      
                    classLabel = classify(secondDict[key],featLabels,testVec)
                else:
                    classLabel = secondDict[key]
        return classLabel
    

    classifyのコメント:
  • 1.type(a).name=="dict":aのタイプがdictであるか否かを判断することができ、list tupleこれらも
  • に適用する.
  • 2.タイプはisinstance(変数名、タイプ)で判断することもできます.変数がタイプであるかどうか、またはクラスとクラスの親タイプであるかどうかを判断します.
      :
    type(   ):         ,  ==                (    value )
    
      :a   b ,  c=a()
    isinstance(c,a) isinstance(c,b)  True
    type(c) value  a,a    b ,  a==b False :type(c)==b False
    
  • 3.==和is==:変数名のvalue値が等しいかis:変数名のid(アドレス)が等しいかどうか(数値タイプのvalue値が等しいとidが等しい)
  • テスト:
    classify(myTree, labels, [1,0])  #  'no'
    classify(myTree, labels, [1,1])  #  'yes'
    

    4.ストレージ決定ツリー
    import pickle
    
    #   pickle       
    def storeTree(inputTree, filename):
            with open(filename, 'wb') as f:
                pickle.dump(inputTree, f)
    #       
    def grabTree(filename):
        with open(filename, 'rb') as f:
            return pickle.load(f)
    

    テスト:
    storeTree(myTree,'classifierStorage.txt')
    grabTree('classifierStorage.txt')  #  {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
    

    参考資料:「機械学習実戦」第三章