一浑玛、前言

你是否玩過二十個問題的游戲趾断？游戲規(guī)則很簡單：參與游戲的一方在腦海中想某個事物拒名，其他參與者向其提問，只允許提二十個問題芋酌，而且問題的答案只能用對和錯來回答增显。問問題的人通過答案進行推斷，逐步縮小猜測事物的范圍脐帝。決策樹原理與二十個問題類似同云，用戶給出一次列輸入數(shù)據(jù)，然后分類器給出答案腮恩。

決策樹流程圖

圖 3-1 的流程圖就是一個決策樹梢杭，其中正方形表示判斷模塊，橢圓形表示終止模塊秸滴。

二武契、決策樹構(gòu)造原理

在構(gòu)造決策樹時，我們首先需要考慮的問題就是哪個特征在劃分數(shù)據(jù)集時起決定性作用。為了找到?jīng)Q定性特征咒唆，劃分出最佳結(jié)果届垫，我們需要對每個特征進行評估。完成測試后全释，原始數(shù)據(jù)集就會被分成幾個數(shù)據(jù)子集装处。這些數(shù)據(jù)子集會分布在第一個決策點的所有分支上。如果某個分支上的數(shù)據(jù)已經(jīng)屬于某一類別浸船，那么該數(shù)據(jù)子集已經(jīng)被正確分類妄迁，無需進一步劃分，反之則需要進一步劃分李命，直到所有相同類型的數(shù)據(jù)在同一個數(shù)據(jù)集中為止登淘。

一些決策樹采用二分法劃分數(shù)據(jù)，但本文將使用 ID3 算法劃分數(shù)據(jù)集封字。每次劃分數(shù)據(jù)集只需選擇一個特征黔州，但如果某個數(shù)據(jù)集中有 20 個特征，應(yīng)該如何選壤选流妻？為了解決這個問題，我們必須采用量化的方法判斷如何劃分數(shù)據(jù)笆制，這需要用到信息論的知識绅这。

三、決策樹先導(dǎo)知識

1. 信息增益

劃分數(shù)據(jù)集的大原則是：將無序的數(shù)據(jù)變得有序在辆。組織雜亂無章的數(shù)據(jù)的一種方法就是使用信息論度量信息君躺，我們可以在劃分數(shù)據(jù)前使用信息論度量信息的內(nèi)容。

在劃分數(shù)據(jù)集前后开缎，信息發(fā)生的變化叫做信息增益，知道如何計算信息增益林螃，我們就可以計算每個特征劃分數(shù)據(jù)集后的信息增益奕删，然后選擇信息增益最大的特征。因此疗认，為了解決這個問題完残，我們必須學(xué)習(xí)如何計算信息增益。

香農(nóng)熵（熵）

集合信息的度量方式横漏。熵是對混亂的度量谨设。

熵定義為信息的期望值，在明晰這個概念之前缎浇，我們必須知道信息的定義扎拣。如果待分類的事物可能劃分在多個分類中，則符號 xi 的信息定義為：

xi 的信息定義

pxi

是選擇該分類的概率。

為了計算熵二蓝，我們需要所有類別所有可能值包含的信息期望值誉券，可以通過如下公式得到：

信息熵

其中 n 是分類的數(shù)目。

計算給定數(shù)據(jù)集的香農(nóng)熵

from math import log
import operator
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.preprocessing import LabelEncoder

'''
函數(shù)說明：構(gòu)造數(shù)據(jù)集
參數(shù)：無
返回值：新構(gòu)造的數(shù)據(jù)集
'''
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

dataSet,labels = createDataSet()
# print(labels)

'''
函數(shù)說明：計算給定數(shù)據(jù)集的香農(nóng)熵
參數(shù)：dataSet -- 數(shù)據(jù)集
返回值：shannonEnt -- 數(shù)據(jù)集的熵
'''
def calcShannonEnt(dataset):
    totalNum = len(dataset)
    labelCounts = {}
    for featVec in dataset:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():          
            labelCounts[currentLabel] = 1
        else:
            labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / totalNum
        shannonEnt -= prob * log(prob,2)
    return shannonEnt
dataSet,labels = createDataSet()
# print(labels)
shannonEnt = calcShannonEnt(dataSet)
# print(dataSet)
# print(shannonEnt)

執(zhí)行結(jié)果：

數(shù)據(jù)集的信息熵

熵越高刊愚，則混合的數(shù)據(jù)越多踊跟。我們可以在數(shù)據(jù)集中增加分類，觀察熵的變化鸥诽。

dataSet[0][-1] = 'maybe'

執(zhí)行結(jié)果為：

分類越多熵越高

得到熵之后商玫，我們就可以根據(jù)最大信息增益來劃分數(shù)據(jù)集。

2. 根據(jù)給定特征劃分數(shù)據(jù)集

上一節(jié)我們學(xué)習(xí)如何度量數(shù)據(jù)的無序程度牡借，也即是熵的計算拳昌，接下來我們將對每個特征劃分得到的數(shù)據(jù)集進行信息熵計算，然后找出信息增益最大的劃分方式所對應(yīng)的特征蓖捶。

按照給定的特征劃分數(shù)據(jù)集

'''
函數(shù)說明：按照給定特征劃分數(shù)據(jù)集
參數(shù)：dataSet -- 待劃分的數(shù)據(jù)集
      axis -- 劃分數(shù)據(jù)集的特征
      value -- 特征的返回值
返回值：retDataSet -- 劃分好的數(shù)據(jù)集
'''
def splitDataSet(dataset,axis,value):
    retDataSet = []
    for featVec in dataset:
        if featVec[axis] == value:
            #把劃分數(shù)據(jù)集的特征從數(shù)據(jù)集中剔除地回，
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet


# print(splitDataSet(dataSet,0,1))
# print(splitDataSet(dataSet,0,0))

執(zhí)行結(jié)果：

按照給定特征劃分

目前我們只是根據(jù)給定的特征實現(xiàn)了數(shù)據(jù)集的劃分，接下來我們需要遍歷整個數(shù)據(jù)集俊鱼，對每個特征進行劃分并計算信息增益刻像，找到最佳分類特征。

3. 尋找最佳劃分特征

'''
函數(shù)說明：選擇最佳劃分特征
參數(shù)：dataset -- 待劃分的數(shù)據(jù)集
返回值：最佳劃分特征
'''
def chooseBestFeatureToSplit(dataset):
    # 數(shù)據(jù)集特征數(shù)
    numFeatures = len(dataset[0]) - 1
    # 原始數(shù)據(jù)的信息熵
    bestEntropy = calcShannonEnt(dataSet)
    #最大信息增益
    bestInfoGain = 0.0
    # 最佳劃分特征
    bestFeature = -1
    for i in range(numFeatures):
        featureList = [example[i] for example in dataset]
        # 特征對應(yīng)的取值
        uniqueVals = set(featureList)
        newEntropy = 0.0
        for value in uniqueVals:
            # 遍歷劃分每個特征的每個取值
            subDataSet = splitDataSet(dataset,i,value)
            prob = len(subDataSet) / float(len(dataSet))
            # 新數(shù)據(jù)集的信息熵
            newEntropy += prob * calcShannonEnt(subDataSet)
        # 信息增益
        infoGain = bestEntropy - newEntropy
        if(infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature
# print(dataSet)
# print('最佳劃分特征：特征',chooseBestFeatureToSplit(dataSet))

執(zhí)行結(jié)果：

最佳劃分特征

代碼運行結(jié)果顯示并闲，第 0 個特征是劃分數(shù)據(jù)集的最佳特征细睡。也即是第一個特征取值為 1 的是一組，取值為 0 的是一組帝火×镝悖可以看到，取值為 1 的分組中有兩個是魚類犀填，有一個是非魚類蠢壹；取值為 0 的分組中，兩個都是非魚類九巡。如果按照第二個特征來分類图贸，則取值為 1 的分組中，有兩個是魚類冕广，兩個是非魚類疏日；取值為 0 的分組中，只有一個非魚類撒汉。

4. 遞歸構(gòu)造決策樹

目前我們已經(jīng)得到從數(shù)據(jù)集構(gòu)造決策樹算法所需要的子功能模塊沟优，其工作原理為：得到原始數(shù)據(jù)集，然后基于最佳分類特征對數(shù)據(jù)集進行劃分睬辐，由于特征值可能不止兩個挠阁，所以可能存在大于兩個分支的數(shù)據(jù)集劃分宾肺。第一次劃分之后，數(shù)據(jù)被向下傳遞到數(shù)分支的下一個節(jié)點鹃唯，在這個節(jié)點上爱榕，我們可以再次劃分數(shù)據(jù)。因此我們可以采用遞歸的原則來處理數(shù)據(jù)集坡慌。

遞歸結(jié)束的條件：當程序遍歷完所有劃分數(shù)據(jù)集的屬性或所有分支下的實例都屬于同一個分類黔酥。如果所有實例具有相同的分類，則得到一個葉子節(jié)點或者說終止塊洪橘。任何到達葉子節(jié)點的數(shù)據(jù)必定屬于葉子節(jié)點的分類跪者。

由于特征數(shù)目并不一定每次劃分都會減少，因此這些算法在實際使用時可能會出現(xiàn)一些問題熄求。不過目前我們并不需要考慮這個問題渣玲，我們只需要在算法開始運行前計算出所有列的數(shù)目，查看算法是否使用了所有屬性即可弟晚。如果數(shù)據(jù)集已經(jīng)處理了所有屬性忘衍，但分類標簽并不唯一的情況下，我們通常會采用多數(shù)表決的方法決定該葉子節(jié)點的分類卿城。
在樹頂(根節(jié)點)處熵最高枚钓，逐層降低，直到數(shù)據(jù)被劃分為各自的類型瑟押。

'''
函數(shù)說明：在葉子節(jié)點類別標簽不唯一的情況下搀捷，采用多數(shù)表決的方法決定該葉子節(jié)點的分類
參數(shù):classList -- 數(shù)據(jù)集所有分類標簽
返回值：葉子節(jié)點中出現(xiàn)次數(shù)最多的分類標簽
'''
def majorityCnt(classList):
    #初始化字典用于記錄各分類標簽及其出現(xiàn)的次數(shù)
    classCount = {}
    # 遍歷數(shù)據(jù)集中的所有分類標簽，并統(tǒng)計其出現(xiàn)的次數(shù)
    for vote in classList:
        if vote not in classList.keys():
            classCount[vote] = 0
        else:
            classCount[vote] += 1
    # 對分類標簽出現(xiàn)的次數(shù)進行排序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

'''
函數(shù)說明：創(chuàng)建樹的函數(shù)代碼,構(gòu)造決策樹
參數(shù)：dataSet -- 數(shù)據(jù)集
      labels -- 數(shù)據(jù)集所有分類標簽
返回值：根據(jù)數(shù)據(jù)集構(gòu)造得到的決策樹
'''
def createTree(dataSet,labels):
    # 得到數(shù)據(jù)集的所有類別標簽
    classList = [example[-1] for example in dataSet]
    # 如果數(shù)據(jù)集中的所有數(shù)據(jù)都屬于同一類別多望，則停止劃分
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    #當遍歷完所有特征時(即數(shù)據(jù)集的列數(shù)為1時)嫩舟，仍然不能將數(shù)據(jù)集劃分成分類標簽唯一的分組，則返回出現(xiàn)次數(shù)最多的分類標簽
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    # 由當前最佳分類特征組成的決策樹
    myTree = {bestFeatLabel:{}}
    # 當特征被添加到?jīng)Q策樹中后怀偷，”就將其從分類標簽中刪除
    del(labels[bestFeat])
    # 最佳分類特征的取值
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    # 刪除最佳分類特征之后的所有分類標簽
    for value  in uniqueVals:
        subLabels = labels[:]
        # 遞歸得到當前數(shù)據(jù)集的最佳分類特征家厌，并構(gòu)造決策樹
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree
mytree = createTree(dataSet,labels)
# print(mytree)

執(zhí)行結(jié)果為：

決策樹

變量 mytree 包含了很多代表樹結(jié)構(gòu)信息的嵌套字典，第一個關(guān)鍵字 no surfacing 是第一個最佳數(shù)據(jù)集劃分特征椎工，該關(guān)鍵字的值又是另一個數(shù)據(jù)字典像街。關(guān)鍵字的值可能是分類標簽，也有可能是另一個數(shù)據(jù)字典晋渺。如果值時分類標簽，則該子節(jié)點就是葉子節(jié)點脓斩；否則該節(jié)點就是另一個判斷節(jié)點木西，這種格式不斷重復(fù)就構(gòu)成了整棵樹，也就是我們剛剛看到的執(zhí)行結(jié)果随静。但是以字典的方式呈現(xiàn)決策樹非常不便于理解八千，因此吗讶，我們接下來將繪制決策樹，以更加直觀的方式來觀察決策樹恋捆。

5. 在 Python 中使用 matplotlib 注解繪制決策樹

'''
函數(shù)說明：使用matplotlib繪制樹節(jié)點
參數(shù)：nodeText -- 節(jié)點注解
      centerPt -- 子節(jié)點
      parentPt -- 父節(jié)點
      nodeType -- 節(jié)點類型
返回值： 無

'''
# 定義判斷節(jié)點照皆、子節(jié)點以及箭頭的格式
decisionNode = dict(boxstyle = "sawtooth",fc = "0.8")
leafNode = dict(boxstyle = "round4",fc = "0.8")
arrow_args = dict(arrowstyle = "<-")

def plotNode(nodeText,centerPt,parentPt,nodeType):
    # 繪制帶箭頭的注解
    createPlot.ax1.annotate(nodeText,xy=parentPt,xycoords = 'axes fraction',xytext = centerPt,textcoords = 'axes fraction',va = "center",ha = "center",bbox = nodeType,arrowprops = arrow_args)

def createPlot():
    fig = plt.figure(1,facecolor = 'white')
    fig.clf()
    createPlot.ax1 = plt.subplot(111,frameon = False)
    # 繪制判斷節(jié)點
    plotNode('a decison node',(0.5,0.1),(0.1,0.5),decisionNode)
    # 繪制子節(jié)點
    plotNode('a leaf node',(0.8,0.1),(0.3,0.8),leafNode)
    plt.show()

# createPlot()

繪制樹節(jié)點：

繪制樹節(jié)點

現(xiàn)在我們已經(jīng)學(xué)會了樹節(jié)點的繪制，接下來我們將要對整棵樹進行繪制沸停。

繪制一顆完整的數(shù)需要一些技巧膜毁。雖然我們有 x , y 坐標，但如何放置所有的樹節(jié)點是個問題愤钾。我們必須知道有多少個葉節(jié)點瘟滨，以便我們能確定 x 軸的長度；我們還需要知道數(shù)有多少層能颁，以便確定 y 軸的長度杂瘸。因此這里我們定義了兩個函數(shù) getNumLeafs() 和 getTreeDepth() 來獲取葉子節(jié)點的數(shù)目以及數(shù)的高度。

'''
函數(shù)說明：獲取葉子節(jié)點的數(shù)目以及數(shù)的高度
參數(shù)：myTree -- 決策樹
返回值: numLeafs -- 葉子節(jié)點數(shù)
        maxDepth -- 數(shù)的高度
'''
def getNumLeafs(myTree):
    #初始化葉子節(jié)點數(shù)
    numLeafs = 0
    #得到第一個關(guān)鍵字
    firstStr = list(myTree.keys())[0]
    # 得到第一個關(guān)鍵字的值伙菊，該值又是一個字典
    secondDict = myTree[firstStr]
    # 遍歷第二個字典的值败玉，判斷是字典還是葉子節(jié)點
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            # 遞歸遍歷
            numLeafs += getNumLeafs(secondDict[key])
        else:
            numLeafs += 1
    return numLeafs

numLeafs = getNumLeafs(mytree)
# print('width of tree:',numLeafs)

def getTreeDepth(myTree):
    # 初始化數(shù)的高度
    maxDepth = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:
            thisDepth = 1
        if thisDepth > maxDepth:
            maxDepth = thisDepth
    return maxDepth

treeDepth = getTreeDepth(mytree)
# print('depth of tree:',treeDepth)

計算得到數(shù)的寬度和高度分別為：

計算數(shù)的寬度和高度

'''
函數(shù)說明：在父子節(jié)點之間填充文本信息
參數(shù)：cntrPt -- 子節(jié)點
      parentPt -- 父節(jié)點
      txtString -- 文本信息
返回值：無
'''
def plotMidText(cntrPt,parentPt,txtString):
    # 文本信息的橫坐標
    xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
    yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
    createPlot.ax1.text(xMid,yMid,txtString)

'''
函數(shù)說明：繪制的具體步驟
參數(shù)：mytree -- 決策樹
      parentPt -- 父節(jié)點
      nodeTxt -- 節(jié)點信息
返回值：無
'''
def plotTree(myTree,parentPt,nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    # 決策樹的第一個關(guān)鍵字
    firstStr = list(myTree.keys())[0]
    # 計算子節(jié)點的位置
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW,plotTree.yOff)
    # 在父子節(jié)點之間填充文本信息
    plotMidText(cntrPt,parentPt,nodeTxt)
    # 繪制節(jié)點
    plotNode(firstStr,cntrPt,parentPt,decisionNode)
    secondDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
    # 遞歸繪制決策樹
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            plotTree(secondDict[key],cntrPt,str(key))
        else:
            plotTree.xOff =  plotTree.xOff + 1 / plotTree.totalW
            plotNode(secondDict[key],(plotTree.xOff,plotTree.yOff),cntrPt,leafNode)
            plotMidText((plotTree.xOff,plotTree.yOff),cntrPt,str(key))
    plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD


'''
函數(shù)說明:將決策樹以圖形的形式繪制出來
參數(shù)：inTree -- 決策樹
返回值：無
'''
def createPlot(inTree):
    fig = plt.figure(1,facecolor = 'white')
    fig.clf()
    #將xy坐標存放于一個字典內(nèi)，不過此時的xy坐標值為空
    axprops = dict(xticks=[],ytick=[])
    createPlot.ax1 = plt.subplot(111,frameon=False)
    # 數(shù)的寬度镜硕，用于計算判斷節(jié)點的位置（應(yīng)該在水平方向和垂直方向的中心位置）
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    #例如有三個葉子節(jié)點运翼，那么它們將x軸平分為三等分，坐標依次為1/3,2/3,3/3,但此時整個圖像靠右谦疾，并不在畫布的中心南蹂，因此將其向左移
    # plotTree.xOff、plotTree.yOff用于追蹤已繪制節(jié)點的位置念恍，以及放置下一個節(jié)點的位置
    plotTree.xOff = -0.5 / plotTree.totalW
    plotTree.yOff = 1.0
    plotTree(inTree,(0.5,1.0),'')
    plt.show()


# createPlot(mytree)

繪制得到的決策樹如下：

繪制得到的決策樹

到目前為止六剥，我們已經(jīng)學(xué)習(xí)而了如何構(gòu)造決策樹以及繪制樹形圖的方法，下一節(jié)我們將實際使用這些方法峰伙，并從算法和數(shù)據(jù)中得到新知識疗疟。