機器學習：決策樹

決策樹

決策樹簡介

你是否玩過二十個問題的游戲，游戲的規則很簡單：參與游戲的一方在腦海中想象某個事物，其他參與者者向他提問題，只允許提20個問題，問題的答案也只能用對或錯回答。問問題的人通過推斷分解，逐步縮小待猜測事物的范圍。 決策樹 的工作原理與20個問題類似，用戶輸入一系列的數據，然后給出游戲的答案。我們經常使用決策樹處理分類問題，近來的調查表明，決策樹也是最經常使用的數據挖掘算法。它之所以如此流行，一個很重要的原因就是不需要了解機器學習的知識，就能搞明白決策樹是如何工作的。

上邊所示的圖，就可以被稱為是決策樹，長方形代表 判斷模塊 ，橢圓形代表 終止模塊 ，表示已經得出結論，可以終止運行。從判斷模塊引出的左右箭頭被稱為 分支 ，它可以到達另一個判斷模塊或者終止模塊。上圖構造了一個假象的郵件分類系統，首先檢測了郵箱的地址，接下來檢測是否包含某一單詞來決定是否為垃圾郵件。 上篇文章我們所學習的 k-近鄰算法 可以完成很多分類任務，但是它最大的缺點就是無法給出數據的內在含義，決策樹的主要優勢在于數據形式非常容易理解。所以我們說， 決策樹 的一個重要的任務是為了理解數據中所蘊含的知識信息，因此，決策樹可以使用不熟悉的數據集合，并從中提取出一系列規則，這些機器根據數據集創建規則的過程，就是機器學習的過程。

決策樹給出的結果往往可以匹敵在當前領域具有幾十年工作經驗的人類專家。

決策樹的構造

在構造決策樹之前，我們首先來看一下決策樹的優缺點：

優點：計算復雜度不高，輸出結果容易理解，對中間值的缺失不敏感，可以處理不相關特征數據 缺點：可能會產生 過度匹配問題 適用數據類型：數值型、標稱型

• 使用 信息論 劃分數據集

在構造決策樹時，我們需要解決的第一個問題就是，哪個特征對于我們劃分數據分類起決定性作用，在學習 k-近鄰算法 的時候，我們在對社交網站進行升級時，對關鍵特征的選擇是通過圖中所分布的點來決定，這次我們通過 信息論 來計算和評估每個特征對分類的影響。 那么，如何劃分數據集呢？我們約定，如果某個分支下的數據屬于同一類型，則當前無需閱讀的垃圾郵件已經正確的劃分數據分類，無需進一步對數據集進行分割，如果數據自己內的數據不屬于同一類型，則需要重復劃分數據自己的過程，直到所有具有相同類型的數據均在一個數據子集內。 一些決策樹算法采用二分法劃分數據，但是我們使用 信息論 作為劃分數據子集的工具。首先我們來了解一下什么是 信息增益 ：

信息增益

劃分數據子集的大原則是：將無序的數據變得更加有序。有很多方法可以用于劃分數據子集，每種方法各有優缺點。組織雜亂無章數據的一種方法就是使用信息論度量信息，信息論是量化處理信息的分支科學。我們可以在劃分數據之前或者之后使用信息論度量信息的內容。 在劃分數據集之前之后信息發生的變化稱為 信息增益 ，知道如何計算信息增益，我們就可以計算每個特征值劃分數據獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。那么，如何計算信息增益呢？集合信息的度量方式稱為 香農熵 ，或者簡稱為 熵 。

• 熵，定義為信息的期望值，如果待分類的事務可能劃分在多個分類之中，則符號X ⁱ 的信息定義為：

l(x<sup>i</sup>) = -log<sup>2</sup>p(x<sup>i</sup>)

其中，p(x ⁱ )是選擇該分類的概率。為了計算熵，我們需要計算所有類別所有可能值包含的信息期望值，通過下面的公事得到：

H = -求和（n, i=1） p(x<sup>i</sup>)log<sup>2</sup>p(x<sup>i</sup>)

其中，n是分類的數目。

注，由于github的markdown暫不支持數學公事，所以一些數學符號我暫時用文字或者math中的方法名稱代替，比如說 sqrt 等等

下面我們使用代碼來實現計算信息熵，創建名為 trees.py 的文件：

from math import log

def calcShannonEnt(dataSet) :
    numEntries = len(dataSet) # 獲得數據集中實例的總數
    labelCounts = {} # 創建數據字典，它的鍵值是最后一列的數值，每個鍵值都記錄了當前類別出現的次數

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</code></pre> 

接下來我們創建一個簡單的數據集：
 
  
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
 
  
然后我們來測試一下上述內容
 
  
>>> reload(trees)
<module 'trees' from 'trees.py'>
>>> myData, labels = trees.createDataSet()
>>> trees.calcShannonEnt(myData)
0.9709505944546686
 
  
熵越高，則混合的數據也越多，我們可以在集合中添加更多的分類，觀察熵是如何變化的，這里我們新增一個名為 hello 的分類并測試
 
  
>>> myData[0][-1] = 'hello'
>>> myData
[[1, 1, 'hello'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myData)
1.3709505944546687

>>> myData[2][-1] = 'machine'
>>> myData
[[1, 1, 'hello'], [1, 1, 'yes'], [1, 0, 'machine'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myData)
1.9219280948873623
 
  
我們看到，分類越多，熵值越高。得到熵之后，我們就可以按照獲取最大信息增益的方法劃分數據集。下面我們來學習如何劃分數據集，并創建決策樹。
 
  
劃分數據集
 
  
我們將對每個特征劃分數據集的結果計算一次信息熵，然后判斷按照哪個特征劃分數據集是最好的劃分方式。我們來按照給定的特征劃分數據集：
 
  
# 輸入的參數分別為，待劃分的數據集，劃分數據集的特征，需要返回的特征的值
 # 注：python語言方法中傳遞的是列表的引用，為了不改變源數據，所以我們用一個新的變量來存儲返回結果
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
 
  
注：代碼中用到的 append 與 extend 方法略有不同，extent是將當前列表的元素添加到源列表中，append意為將該列表作為元素添加至源列表中
 
  
我們可以這樣理解這段代碼，當我們按照某個特征劃分數據集時，就需要將所有符合要求的元素抽取出來。接下來，我們看一下代碼的效果：
 
  
>>> reload(trees)
<module 'trees' from 'trees.py'>
>>> myData, labels = trees.createDataSet()
>>> trees.splitDataSet(myData, 0, 1)
[[1, 'yes'], [1, 'yes'], [0, 'no']]
>>> trees.splitDataSet(myData, 0, 0)
[[1, 'no'], [1, 'no']]
 
  
我們看到，當特征為0的時候，我們希望返回特征值為1的對象，我們看一下：
 
  
[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no']
 
  
這3個對象的第一個特征值均為1，所以程序沒問題，大家也可以測試下其他特征。接下來我們遍歷整個數據集，找到最好的特征劃分方式，熵計算將會告訴我們如何劃分數據集是最好的數據組織方式。
 
  
選擇最好的數據集劃分方式
 
  
def chooseBestFeatureToSplit(dataSet) : 
    numFeatures = len(dataSet[0]) - 1 # 判斷有多少個特征屬性
    baseEntropy = calcShannonEnt(dataSet) # 獲得整個數據集的原始香農熵
    bestInfoGain = 0.0
    bestFeature = -1

    for i in range(numFeatures) :  # 遍歷數據集中所有的特征
        featList = [example[i] for example in dataSet] # 使用[列表推倒](https://www.baidu.com/s?wd=python%20列表推倒&rsv_spt=1&rsv_iqid=0xea8c6dc30000af65&issp=1&f=8&rsv_bp=0&rsv_idx=2&ie=utf-8&tn=baiduhome_pg&rsv_enter=1&rsv_sug3=24&rsv_sug1=20&rsv_sug7=100&rsv_sug2=0&inputT=5475&rsv_sug4=6400)來創建新的列表
        uniqueVals = set(featList) # 使用set將list去重
        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

        if (infoGain > bestInfoGain) : # 比較所有特征的熵（信息增益），返回用于劃分的最好特征的索引值
            bestInfoGain = infoGain
            bestFeature = i

    return bestFeature
 
  
該函數實現了選取特征，劃分數據集，計算出最好的劃分數據集的特征的功能。調用該函數需要滿足一定的要求：1. 數據必須是一種由列表元素組成的列表，而且所有列表元素的長度都相同。 2. 數據的最后一列或者每個實例的最后一個元素是當前實例的類別標簽。3. 我們無需先定list中的數據類型。
 
  
運行得出結果：
 
  
>>> reload(trees)
<module 'trees' from 'trees.py'>
>>> myData, labels = trees.createDataSet()
>>> trees.chooseBestFeatureToSplit(myData)
0
 
  
構建決策樹
 
  
得到原始數據集，然后基于最好的屬性值劃分數據集，由于特征值可能多于2個，因此可能存在大于兩個分支的數據集劃分，第一次劃分后，數據將被向下傳遞到樹分支的下一個節點，在這個節點上，我們可以再次劃分數據。因此，我們采用遞歸的方式處理數據集。遞歸結束的條件是：程序遍歷完所有劃分數據集的屬性，或者每個分支下的所有實例都具有相同的分類，如果實例都具有相同的分類，則得到一個葉子節點或者終止塊，任何到達葉子節點的數據必然屬于葉子節點的分類。如果數據集已經處理了所有屬性，但是類標簽依然不是唯一的，此時我們需要決定如何定義該葉子節點，在這種情況下，我們通常會采用多數表決的方式決定該葉子節點的分類。
 
  
首先在trees.py中
 
  
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.iteritems(), key=operator.itemgetter(1), reverse=True) # 排序并返回出現次數最多的分類名稱
    return sortedClassCount[0][0]
 
  
接下來我們來創建樹，大家細看注釋：
 
  
# 輸入數據集、標簽列表
def createTree(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] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) # 每個數據集調用上，遞歸調用函數創建樹

    return myTree
 
  
運行上述代碼：
 
  
>>> reload(trees)
<module 'trees' from 'trees.py'>
>>> myData, labels = trees.createDataSet()
>>> myTree = trees.createTree(myData, labels)
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
 
  
 
   
擴展：如何使用MapPlotlib繪制樹
 
  
 
  
>>> import treePlotter
>>> myTree = treePlotter.retrieveTree(0)
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
>>> treePlotter.createPlot(myTree)
 
  
大家閱讀下相關代碼
 
  
測試算法
 
  
我們繼續在trees.py中添加方法，一個使用決策樹的分類方法：
 
  
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
 
  
進行測試：
 
  
>>> reload(trees)
<module 'trees' from 'trees.py'>
>>> myData, labels = trees.createDataSet()
>>> labels
['no surfacing', 'flippers']
>>> myTree = treePlotter.retrieveTree(0)
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
>>> trees.classify(myTree, labels, [1, 0])
'no'
>>> trees.classify(myTree, labels, [1, 1])
'yes'
 
  
上面代碼中，myTree我們是從 treePlotter 中獲取的已經手工將之前創建號的樹寫死到代碼里的，但是實際情況中，我們需要把樹保存到本地供使用，所以我們來看下如何保存樹，也就是決策樹的存儲。
 
  
決策樹的存儲
 
  
我們依舊在trees.py中添加以下2個方法：
 
  
def storeTree(inputTree, filename) :
    import pickle

    fw = open(filename, 'w')
    pickle.dump(inputTree, fw)
    fw.close

def grabTree(filename) :
    import pickle

    fr = open(filename)
    return pickle.load(fr)
 
  
接下來，我們驗證一下效果：
 
  
>>> reload(trees)
<module 'trees' from 'trees.py'>
>>> trees.storeTree(treePlotter.retrieveTree(0), 'sTree.txt')
>>> trees.grabTree('sTree.txt')
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
>>>
 
  
示例工程，使用決策樹預測隱形眼睛類型
 
  
樣本文件我存放到了跟代碼以及的目錄下，大家可以使用。
 
  
>>> fr = open('lenses.txt')
>>> lenses = [inst.strip().split('\t') for inst in fr.readlines()]
>>> lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
>>> lensesTree = trees.createTree(lenses, lensesLabels)
>>> lensesTree
{'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses', 'presbyopic': 'no lenses', 'youn
g': 'hard'}}, 'myope': 'hard'}}, 'no': {'age': {'pre': 'soft', 'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}}, 'young': 'soft'}}}}}}
>>> treePlotter.createPlot(lensesTree)
 
  
并且我們得到了樹圖：
 
  
 
  
小結
 
  
決策樹分類器就像帶有終止塊的流程圖，終止塊表示分類結果，開始處理數據集時，我們首先測量數據的不一致性，也就是熵，然后尋找最優方案劃分數據集，直到數據集中的所有數據屬于同一分類。