決策樹

決策樹是一個選擇的過程，以樹的結(jié)構來展示，其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出。
如找對象決策樹

1_3.png

構造決策樹

構造決策樹的問題在于哪個特征在劃分數(shù)據(jù)分類中起到?jīng)Q定性作用，為此要去評估起決定作用的特征值。
這里介紹兩種方法信息增益和基尼不純度

信息增益

信息增益是劃分數(shù)據(jù)集之前之后的變化。信息增益最高的特征就是最好的選擇。
集合信息的度量方式稱之為熵或香農(nóng)熵 ，其信息的熵計算公式為

pi為選擇該類的概率
限制把數(shù)據(jù)集D 分成D1,D2,D3.... ，則劃分后的信息熵為

那么信息增益則為:

實現(xiàn)代碼

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1      #the last column is used for the labels
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):        #iterate over all the features
        featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
        uniqueVals = set(featList)       #get a set of unique values
        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     #calculate the info gain; ie reduction in entropy
        if (infoGain > bestInfoGain):       #compare this to the best gain so far
            bestInfoGain = infoGain         #if better than current best, set to best
            bestFeature = i
    return bestFeature                      #returns an integer

基尼不純度

同樣的可以通過基尼不純度來劃分數(shù)據(jù)集
基尼不純度的定義:

在劃分k個子集后數(shù)據(jù)集的不純度的公式為

前后的變化：

遞歸構建決策樹

這里使用信息增益的方法來選擇特征，通過遞歸來構造決策樹

def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList): 
        return classList[0]#stop splitting when all of the classes are equal
    if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
        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[:]       #copy all of labels, so trees don't mess up existing labels
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree  

可視化決策樹

創(chuàng)建的決策樹以字典的新式返回，使用graphviz來繪制
以下是隱形眼鏡決策樹

1.jpg