機械学習決定木アルゴリズム学習ノート

基本概念

決定木は分類アルゴリズムです。

データ型: 数値と名目値。構築アルゴリズムは名目データに対してのみ機能するため、数値データは離散化する必要があります。

仕組み

シャノンエントロピーを使用して、情報ゲインが最も高い特徴を見つけ、情報ゲインが最も高い特徴に従ってデータを分割し、このプロセスを繰り返して、無秩序なデータをより秩序のあるものにします。ツリー構造は ID3 アルゴリズムを使用して構築されます。新しいデータが渡されると、リーフノードがなくなるまで、データに従って対応するツリーノードが検索され、分類が完了します。

例

水面に浮かばなくても生き残れるのか？ひれはあるか？魚なのか？

ある種が魚類であるかどうかは、水面に浮上せずに生きられる能力と、水かきのある足を持っているかどうかによって決まります。簡単な決定木を構築します。新しい生物が見つかったら、それを使ってそれが魚かどうかを判断できます。

サンプルコード

デフcreateDataSet():
    データセット = [[1, 1, 'はい' ],
               [1, 1, 「はい」 ],
               [1, 0, 'いいえ' ],
               [0, 1, 'いいえ' ],
               [0, 1, 'いいえ' ]]
    labels = [ '浮上禁止' , '足ひれ' ]
データセットとラベルを返す

シャノンエントロピー公式

分類対象となる取引が複数のカテゴリに分けられる場合、シンボル Xi の情報は次のように定義されます。

ここでP(Xi)はこのカテゴリーを選択する確率である。

エントロピーを計算するには、すべてのカテゴリのすべての可能な値に含まれる情報の期待値の合計を計算する必要があります。式は次のとおりです。

ここでnはカテゴリの数である

シャノンエントロピーアルゴリズム

calcShannonEnt(データセット):
    # このカテゴリを選択する確率は、各タイプ/合計数です
    # 合計数、データの行数
    numEntries = len(データセット)
    ラベル数 = {}
    # 入手した各タイプの数
データセット内のfeatVecの場合:
        現在のラベル = featVec[-1]
        現在のラベルが  labelCounts.keys()内: labelCounts[currentLabel] = 0
        ラベル数[現在のラベル] += 1 
 
    シャノンEnt = 0.0
のために 鍵 ラベルカウント内:
        # このカテゴリを選択する確率を取得します
        prob = float (labelCounts[ key ])/numEntries
        # 式によると
        shannonEnt -= prob * log(prob,2) #2を底とする対数
shannonEntを返す

シャノンエントロピーに従ってデータを分割する

情報エントロピーを測定することに加えて、現在の分割が正しいかどうかを判断するために、データセットを分割し、データセットのエントロピーを測定することも必要です。 Shannon エントロピーと splitDataSet() の計算をループして、機能を分割する最適な方法を見つけます。

 def splitDataSet(データセット、軸、値):
    # このアルゴリズムは軸の添え字の外側の列を返します
    retデータセット = []
データセット内のfeatVecの場合:
        featVec[axis] == valueの場合:
            ReducedFeatVec = featVec[:axis] #分割に使用する軸を切り取る
            縮小されたフィーチャベクトルを拡張します(フィーチャベクトル[軸+1:])
            retDataSet.append(縮小されたフィーチャベクトル)
 retDataSetを返す
 
 def chooseBestFeatureToSplit(データセット):
    # まず最後の列を取り、それを使って結果にラベルを付けます: 魚か魚でないか。
    numFeatures = len(データセット[0]) - 1
    # オリジナル相農エントロピー
    ベースエントロピー = calcShannonEnt(データセット) 
 
    ベストインフォゲイン = 0.0; ベストフィーチャ = -1
    # すべての機能を反復処理する
i が範囲内(numFeatures)の場合:
        # この機能のすべての値を含むリストを作成します
        featList = [example[i] データセット内の例]
        #重複を削除するにはsetを使用する
        uniqueVals =設定(featList)
        新しいエントロピー = 0.0
        # この特徴に含まれる型のシャノンエントロピーの合計を計算します
uniqueValsの値の場合:
            サブデータセット = 分割データセット(データセット、i、値)
            prob = len(subDataSet)/ float (len(dataSet))
            新しいエントロピー += 確率 * calcShannonEnt(subDataSet)
        # 情報を得る
        infoGain = ベースエントロピー - 新しいエントロピー
        # ***情報ゲインを取り、添え字を記録する
        情報ゲイン > ベスト情報ゲインの場合:
            ベストインフォゲイン = インフォゲイン
            ベストフィーチャ = i
    # 下付き文字を返す
ベストフィーチャを返す

データセットは特定の要件を満たす必要があります。

データはリスト要素のリストである必要があります。 (2次元配列)
すべてのリスト要素の長さは同じである必要があります。
最初の列は現在のインスタンスのラベルである必要があります。

再帰的に決定木を構築する

多数決アルゴリズム

データセットがすべての属性を処理したが、クラスラベルがまだ一意でない場合は、リーフノードをどのように定義するかを決定する必要があります。この場合、通常は多数決を使用してリーフノードを決定します。

インポート演算子
defmajorityCnt(クラスリスト):
    # 最も多くの種類をソートして抽出する
    クラスカウント={}
クラスリストの投票:
        投票しない場合  classCount.keys()内: classCount[vote] = 0
        クラスカウント[投票] += 1
    sortedClassCount = sorted(classCount.iteritems(), key =operator.itemgetter(1), reverse= True )
 sortedClassCount[0][0]を返す

ツリー構築アルゴリズム

def createTree(データセット、ラベル):
    # 結果を取得する
    classList = [example[-1] dataSet内の例]
    # 結果の最初の要素で表されるデータの数が結果自体と等しい場合、他の分類がないことを意味します
    classList.count (classList[0]) == len(classList)の場合:
クラスリスト[0]を返す
    # データがない場合は、複数のデータを分類する意味があります
    len(dataSet[0]) == 1の場合:
        # 多数決で、出現回数が最も多いものを返す
多数決Cnt(classList)を返す
 
    # セグメンテーションタイプに最も適した下付き文字を選択してください
    bestFeat = 分割する最適なフィーチャを選択する(データセット)
    # インデックスに従ってラベルを取得します
    bestFeatLabel = ラベル[bestFeat]
    # 木を作る
    myTree = {ベストフィーチャラベル:{}}
    # 繰り返し計算を避けるために、取り出されたタグを削除します
    del(ラベル[ベストフィーチャ])
    featValues = [example[bestFeat] データセット内の例] 
 
    #重複を削除するにはsetを使用します
    uniqueVals =設定(featValues) 
 
 
 uniqueValsの値の場合:
        #サブラベルはすべて参照型なので、元のラベルデータの変更を避けるためにコピーします。
        サブラベル = ラベル[:]
        # 再帰的にツリーを構築する
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
 myTreeを返す

決定木を使った分類

def classify(inputTree,featLabels,testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index (firstStr )
    # 'featIndex %s'を印刷% (featIndex)
キー= testVec[featIndex]
    # 'キー %s'を印刷% (キー)
    valueOfFeat = secondDict[キー]
    if isinstance(valueOfFeat, dict):
        classLabel = classify(valueOfFeat, featLabels, testVec)
そうでない場合: classLabel = valueOfFeat
クラスラベルを返す
 
データセット、ラベル = createDataSet()
 mytree = createTree(dataSet, labels[:]) #ラベル内の値は内部的に削除されるため、次のようにコピーします
マイツリーを印刷する
# { '浮上禁止' : {0: 'いいえ' , 1: { '足ひれ' : {0: 'いいえ' , 1: 'はい' }}}}
印刷分類(mytree, ラベル, [0,1])
いいえ

決定木の保存

決定木の構築は、データセットが小さい場合でも時間のかかる作業です。したがって、構築された決定木を使用できます。

 def storeTree(入力ツリー、ファイル名):
    輸入ピクルス
    fw = open ( ファイル名 , 'w' )
    pickle.dump(入力ツリー、fw)
    fw.close () 関数 
 def grabTree(ファイル名):
    輸入ピクルス
    fr =開く(ファイル名)
 pickle.loadを返す(fr )