決定木アルゴリズム生成剪断in Python

1、基本思想
基本的な分類と回帰方法として、決定ツリーはif-thenルールの集合と見なすことができ、このとき、決定ツリーの経路またはそれに対応するif-thenルールの集合は反発し、完備している.
決定ツリーはまた、特定の特徴条件下のクラスの条件確率分布を表し、この条件確率分布は特徴空間の1つの区分に定義され、決定ツリーの1つの経路は区分後の1つのユニットに対応する.
2、メリット
2.1可読性が高く、説明性があり、人工分析に役立つ
2.2効率が高く、意思決定ツリーは一度に構築し、繰り返し使用する必要があり、予測ごとの最大計算回数は意思決定ツリーの深さを超えない.
比較的短時間で大規模なデータソースに対して実行可能で効果的な結果を得ることができる.
2.3中間値の欠落に敏感ではなく、関連しない特徴データを処理することができ、多くの属性を持つデータセットに対して決定ツリーを構築することができ、データ型と従来型の属性を同時に処理することができる.
他のテクノロジーでは、データ属性の単一性が要求されることが多い.
2.4決定木については、データの準備が簡単である、あるいは不要であることが多い.
他の技術では、余分な属性や空白の属性を取り除くなど、データを一般化することが要求されることが多い.
2.5決定ツリーは、大規模なデータベースによく拡張され、データベースのサイズとは独立したサイズになります.
3、短所
3.1オーバーマッチングの問題が発生しやすい(そのため、枝切りが必要)
3.2各カテゴリのサンプル数が一致しないデータについて、決定ツリーでは、情報利得の結果は、より多くの数値的特徴を有するものに偏っている.
3.3データセット属性間の相関を無視する.
3.4分類器の性能が上がらないのは、分類器の良し悪しではなく、特徴の鑑別性が不足していることが主な原因であり、良い特徴こそ良い分類効果があり、分類器は弱い相関にすぎない.
(これはML通病であり,非意思決定ツリー独自の欠点である)
3.5決定ツリーは、所与の時間内に最適な選択を行う必要がある貪欲なアルゴリズムですが、グローバル最適化に達するかどうかは気にしません.
4、実施プロセス
4.1データ収集
4.2データの準備
ツリー構造アルゴリズムは公称型データにのみ適用されるため,数値型データは離散化しなければならない.
4.3分析データ
4.4トレーニングデータ
ツリーを構築するデータ構造、すなわち、フィーチャー選択、決定ツリー生成、および決定ツリー剪断を含むツリーの学習
A.特徴選択
すなわち、訓練データに対して分類能力を有する特徴を選択する.
ID 3で情報ゲインを最大にするフィーチャーを選択
C4.5で情報ゲイン比を最大にするフィーチャーを選択
CART分類木におけるキニー指数の最小の特徴とその対応する切り分け点の選択
CART回帰木は二乗誤差を最小にする特徴と対応する切り分け点を選択する
B.決定木生成
局所最適化のみを考慮
C.決定木トリミング
グローバル最適化を試験し,決定ツリー生成のオーバーフィット現象を解決した.
4.5テストアルゴリズム
経験ツリーを使用したエラー率の計算
4.6アルゴリズムの使用
使用のために生成ツリーを保存
5、trees in Python
ID 3アルゴリズムによる決定ツリーの生成と記憶を考慮すると、Pythonはソースコードを以下のように実現する.

from numpy import *
import operator
from math import log


### preparing the data ###
def createDataSet():
    fr = open(r'F:\ResearchData\MyCode\Python\trees\lenses.txt')
    lenses = [inst.strip().split('\t') for inst in fr.readlines()]
    dataSet = lenses
    # the last column of dataSet denotes the y or the labels
    lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
    labels = lensesLabels
    # the labels mark the former columns in dataSet (features)
    return dataSet labels


### training ###
# calculate the shannon entropy of dataSet
def calcShannonEnt(dataSet):
    numEntries = len(dataSet) # type(dataSet) is list
    # the number of rows, N
    labelCounts = {}    # dict
    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

# choose the best feature to split the dataSet
# split the dataSet according the value of feature of dataSet
# more details see P61
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 # the last one denotes the label
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    # the reason we use -1 is due to that it can be set as a mark to check whether the function progresses well
    # that the output is -1 after calling this function denotes it is wrong
    for ii in range(numFeatures):
        featList = [example[ii] for example in dataSet] # return the data of the ii-th feature in dataSet as a list 
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, ii, value)
            prob = len(subDataSet)/float(len(dataSet)) # len(subDataSet) denotes abs(D_ii)
            newEntropy += prob * calcShannonEnt(subDataSet) # calcShannonEnt(subDataSet) obtains the H(D_ii)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = ii
    return bestFeature

# majority voting for each leaf note
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=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


# creating new tree
# the input para labels is not necessary, just for well see the meaning
def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # for the leaf nodes
    # for the case(1) in Alg5.2 in P63
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # for the case(2) in Alg5.2 in P63
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # for the iterations (3)-(6) in Alg5.2 in P64
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat]) # delect an element, bestFeatLabel, in this iteration
    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)
    labels.insert(bestFeat, bestFeatLabel) # recover the labels from del(labels[bestFeat])
    return myTree


### testing ###
# classify
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


### using ###
# storing the built trees
def storeTree(inputTree, filename):
    import pickle # a module
    fw = open(filename, 'w')
    pickle.dump(inputTree, fw)
    fw.close()

def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)

次の枝切りプロセスの追加