摘要：本篇內(nèi)容為機器學(xué)習(xí)實戰(zhàn)第章決策樹部分程序清單。適用數(shù)據(jù)類型數(shù)值型和標(biāo)稱型在構(gòu)造決策樹時，我們需要解決的第一個問題就是，當(dāng)前數(shù)據(jù)集上哪個特征在劃分?jǐn)?shù)據(jù)分類時起決定性作用。下面我們會介紹如何將上述實現(xiàn)的函數(shù)功能放在一起，構(gòu)建決策樹。

本篇內(nèi)容為《機器學(xué)習(xí)實戰(zhàn)》第 3 章決策樹部分程序清單。所用代碼為 python3。

決策樹
優(yōu)點：計算復(fù)雜度不高，輸出結(jié)果易于理解，對中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。
缺點：可能會產(chǎn)生過度匹配問題。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型

在構(gòu)造決策樹時，我們需要解決的第一個問題就是，當(dāng)前數(shù)據(jù)集上哪個特征在劃分?jǐn)?shù)據(jù)分類時起決定性作用。為了找到?jīng)Q定性的特征，劃分出最好的結(jié)果，我們必須評估每個特征。完成測試之后，原始數(shù)據(jù)集就被劃分為幾個數(shù)據(jù)子集。這些數(shù)據(jù)子集會分布在第一個決策點的所有分支上。如果某個分支下的數(shù)據(jù)屬于同一類型，則無需進一步對數(shù)據(jù)集進行分割。如果數(shù)據(jù)子集內(nèi)的數(shù)據(jù)不屬于同一類型，則需要重復(fù)劃分?jǐn)?shù)據(jù)子集的過程。劃分?jǐn)?shù)據(jù)子集的算法和劃分原始數(shù)據(jù)集的方法相同，直到所有具有相同類型的數(shù)據(jù)均在一個數(shù)據(jù)子集內(nèi)。

創(chuàng)建分支的偽代碼函數(shù)createBranch()如下所示：

檢測數(shù)據(jù)集中的每個子項是否屬于同一分類：
    If so return 類標(biāo)簽
    Else
        尋找劃分?jǐn)?shù)據(jù)集的最好特征
        劃分?jǐn)?shù)據(jù)集
        創(chuàng)建分支節(jié)點
            for 每個劃分的子集
                調(diào)整函數(shù)createBranch()并增加返回結(jié)果到分支節(jié)點中
        return 分支節(jié)點

下面我們采用量化的方法來判定如何劃分?jǐn)?shù)據(jù)，我們以下圖所示的數(shù)據(jù)集為例：

"""
Created on Sep 16, 2018

@author: yufei
"""

# coding=utf-8

"""
計算給定數(shù)據(jù)的香農(nóng)熵
"""
from math import log
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}

    # 為所有可能的分類創(chuàng)建字典
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0

    # 以 2 為底求對數(shù)
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

"""
得到數(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

在 python 提示符下，執(zhí)行代碼并得到結(jié)果：

>>> import trees
>>> myDat, labels = trees.createDataSet()
>>> myDat
[[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
>>> trees.calcShannonEnt(myDat)
0.9709505944546686

# 參數(shù)：待劃分的數(shù)據(jù)集、劃分?jǐn)?shù)據(jù)集的特征、需要返回的特征的值
def splitDataSet(dataSet, axis, value):
    # 為了不修改原始數(shù)據(jù)集，創(chuàng)建一個新的列表對象
    retDataSet = []
    for featVec in dataSet:
        # 將符合特征的數(shù)據(jù)抽取出來
        # 當(dāng)我們按照某個特征劃分?jǐn)?shù)據(jù)集時，就需要將所有符合要求的元素抽取出來
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

測試函數(shù)splitDataSet()，在 python 提示符下，執(zhí)行代碼并得到結(jié)果：

>>> myDat, labels = trees.createDataSet()
>>> myDat
[[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]
>>> trees.splitDataSet(myDat, 0, 0)
[[1, "no"], [1, "no"]]

"""
函數(shù)功能：選擇特征，劃分?jǐn)?shù)據(jù)集，計算得出最好的劃分?jǐn)?shù)據(jù)集的特征

數(shù)據(jù)集需滿足：
1、數(shù)據(jù)是一種由列表元素組成的列表，且所有的列表元素都要具有相同的數(shù)據(jù)長度
2、數(shù)據(jù)的最后一列或每個實例的最后一個元素是當(dāng)前實例的類別標(biāo)簽
"""
def chooseBestFeatureToSplit(dataSet):
    # 判定當(dāng)前數(shù)據(jù)集包含多少特征屬性
    numFeatures = len(dataSet[0]) - 1
    # 計算整個數(shù)據(jù)集的原始香農(nóng)熵，即最初的無序度量值
    baseEntropy = calcShannonEnt(dataSet)

    bestInfoGain = 0.0
    bestFeatures = -1

    # 遍歷數(shù)據(jù)集中的所有特征
    for i in range(numFeatures):
        # 創(chuàng)建唯一的分類標(biāo)簽列表，將數(shù)據(jù)集中所有第 i 個特征值寫入這個 list 中
        featList = [example[i] for example in dataSet]
        # 從列表中創(chuàng)建集合來得到列表中唯一元素值
        uniqueVals = set(featList)
        newEntropy = 0.0

        # 遍歷當(dāng)前特征中的所有唯一屬性值，對每個唯一屬性值劃分一次數(shù)據(jù)集，計算數(shù)據(jù)集的新熵值
        # 即計算每種劃分方式的信息熵
        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
            bestFeatures = i
    return bestFeatures

在 python 提示符下，執(zhí)行代碼并得到結(jié)果：

>>> myDat, labels = trees.createDataSet()
>>> trees.chooseBestFeatureToSplit(myDat)
0
>>> myDat
[[1, 1, "yes"], [1, 1, "yes"], [1, 0, "no"], [0, 1, "no"], [0, 1, "no"]]

代碼運行結(jié)果告訴我們，第 0 個特征是最好的用于劃分?jǐn)?shù)據(jù)集的特征。也就是說第一個特征是 1 的放在一個組，第一個特征是 0 的放在另一個組。因為這個數(shù)據(jù)集比較簡單，我們直接觀察可以看到第一種劃分更好地處理了相關(guān)數(shù)據(jù)。

下面我們會介紹如何將上述實現(xiàn)的函數(shù)功能放在一起，構(gòu)建決策樹。

"""
使用分類名稱的列表，創(chuàng)建數(shù)據(jù)字典
返回出現(xiàn)次數(shù)最多的分類名稱
"""
import operator
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote in classList:
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

# 參數(shù)：數(shù)據(jù)集，標(biāo)簽列表
def createTree(dataSet, labels):
    # 創(chuàng)建名為 classList 的列表變量，包含了數(shù)據(jù)集的所有類標(biāo)簽
    classList = [example[-1] for example in dataSet]
    # 遞歸函數(shù)的第一個停止條件：所有類標(biāo)簽完全相同，則直接返回該類標(biāo)簽
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 遞歸函數(shù)的第二個停止條件：使用完所有特征，仍然不能將數(shù)據(jù)集劃分成僅包含唯一類別的分組
    # 由于無法簡單地返回唯一的類標(biāo)簽，這里遍歷完所有特征時使用 majorityCnt 函數(shù)返回出現(xiàn)次數(shù)最多的類別
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    # 當(dāng)前數(shù)據(jù)集選取的最好特征存儲在變量 bestFeat 中，得到列表包含的所有屬性值
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    # 字典變量 myTree 存儲了樹的所有信息
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])

    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    # 遍歷當(dāng)前選擇特征包含的所有屬性值
    for value in uniqueVals:
        # 復(fù)制類標(biāo)簽，將其存儲在新列表變量 subLabels 中
        # 在python語言中，函數(shù)參數(shù)是列表類型時，參數(shù)是按照引用方式傳遞的
        # 為了保證每次調(diào)用函數(shù) createTree 時不改變原始列表的內(nèi)容
        subLabels = labels[:]
        # 在每個數(shù)據(jù)集劃分上遞歸的調(diào)用函數(shù) createTree（）
        # 得到的返回值被插入字典變量 myTree 中
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

在 python 提示符下，執(zhí)行代碼并得到結(jié)果：

>>> myDat, labels = trees.createDataSet()
>>> myTree = trees.createTree(myDat, labels)
>>> myTree
{"no surfacing": {0: "no", 1: {"flippers": {0: "no", 1: "yes"}}}}

最后得到的變量myTree包含了很多代表樹結(jié)構(gòu)信息的嵌套字典。這棵樹包含了 3 個葉子節(jié)點以及 2 個判斷節(jié)點，形狀如下圖所示：

不足之處，歡迎指正。