摘要：決策樹是一種十分常用的分類方法，作為一個預測模型，決策樹表示對象屬性與對象值之間的一種映射關系。判斷類型測試評價以上決策樹的的實現方式，沒有剪枝的步驟，容易發生過度擬合，導致決策樹過高。

決策樹(Decision Tree）是一種十分常用的分類方法，作為一個預測模型，決策樹表示對象屬性與對象值之間的一種映射關系。

公式表示為：其中S表示樣本集，c表示樣本集合中類別個數，Pi表示第i個類別的概率。

信息熵的意思就是一個變量i（就是這里的類別）可能的變化越多（只和值的種類多少以及發生概率有關），它攜帶的信息量就越大（因為是相加累計），即類別變量i的信息熵越大。

二分類問題中，當X的概率P(X)為0.5時，表示變量的不確定性最大，此時的熵達到最大值1。

信息熵反映系統的確定程度：信息熵越低，系統越確定；信息熵越高，系統越不確定

公式表示為：其中ti表示屬性T的取值。條件熵的直觀理解：假設多帶帶計算明天下雨的信息熵：H(Y)=2，而在已知今天陰天情況下計算明天下雨的條件熵：H(Y|X)=0.5（熵變小，確定性變大，明天下雨的概率變大，信息量減少），這樣相減后為1.5，在獲得陰天這個信息后，下雨信息不確定性減少了1.5，信息增益很大，所以今天是否時陰天這個特征信息X對明天下雨這個隨機變量Y的來說是很重要的。

公式表示為：
信息增益考察某個特征對整個系統的貢獻。

通過“不浮出水面能否生存 no surfacing” 和 “是否有腳蹼 flippers”來判斷5種海洋生物是否屬于魚類。

from math import log

def calcInforEnt(dataSet):
    num = len(dataSet)
    labelCount = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCount.keys():
            labelCount[currentLabel] = 0
        labelCount[currentLabel] += 1  # 統計類別數目，labelCount = {"yes": 2, "no": 3} 
    inforEnt = 0.0
    for key in labelCount:
        prob = float(labelCount[key]) / num
        inforEnt -= prob * log(prob, 2)
    return inforEnt

測試：

dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
calcInforEnt(dataSet)  # 0.9709505944546686

按照給定特征值劃分數據集

def splitDataSet(dateSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

測試：

dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
splitDataSet(dataSet, 0, 1)  # [[1, "yes"], [1, "yes"], [0, "no"]]
splitDataSet(dataSet, 0, 0)  # [[1, "no"], [1, "no"]]

遍歷整個數據集，循環計算信息熵和splitDataSet()函數，找到最好的特征劃分方式。

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1  # 數據集的最后一列表示類標簽
    baseEntropy = calcInforEnt(dataSet)
    bestInforGain = 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 * calcInforEnt(subDataSet)
        inforGain = bestInforGain - newEntropy
        if inforGain > bestInforGain:
            bestInforGain = inforGain
            bestFeature = i
    return bestFeature

測試：

dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
chooseBestFeatureToSplit(dataSet)  # 0

工作原理：得到原始數據集，基于最佳的屬性劃分數據集，由于屬性存在兩個或以上屬性值，因此存在兩個或以上的數據分支。第一次劃分結束后，數據向下傳遞到樹分支中，每個分支按照條件繼續分叉。
遞歸結束條件：程序遍歷完所有劃分數據集的屬性，或者每一個分支下的實例屬于相同分類

import operator

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)
        return sortedClassCount[0][0]

# 創建樹
def ctrateTree(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:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = ctrateTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree 

測試：

dataSet = [[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
labels = ["no surfacing", "flippers"]
ctrateTree(dataSet, labels)  # {"no surfacing": {0: "no", 1: {"flippers"：{0: "no", 1: "yes"}}}}

比較測試數據與決策樹上的值，遞歸執行該過程直到進入葉子節點，最后將測試數據定義為葉子節點所屬的類型。

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

測試：

inputTree = {"no surfacing": {0: "no", 1: {"flippers"：{0: "no", 1: "yes"}}}}
featLabels = ["no surfacing", "flippers"]
classify(inputTree, featLabels, [1, 0])  # "no"
classify(inputTree, featLabels, [1, 1])  # "yes"

以上決策樹的ID3的實現方式，沒有剪枝的步驟，容易發生過度擬合，導致決策樹過高。C4.5決策樹的改進策略：

用信息增益率來選擇屬性，克服了用信息增益選擇屬性偏向選擇多值屬性的不足

在構造樹的過程中進行剪枝，參考剪枝算法

對連續屬性進行離散化

能夠對不完整的數據進行處理

《機器學習實戰》

信息熵與信息增益