《机器学习实战》决策树算法

决策树

优点: 计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。

缺点: 可能会产生过度匹配问题。

适用数据类型: 数值型和标称型

1.计算香农熵

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

这段代码主要是用于计算数据的香农熵。首先创建以数据各个标签为键的哈希表，值初始化为0。然后根据出现次数进行计数。
各个标签的出现次数除以数据总数就是该标签的出现概率。有了概率我们就可以计算香农熵。

香农熵公式

计算每个标签的熵并累加，就可得到数据整体的香农熵。

2.建立测试用数据

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

建立一个简单的数据用于测试算法的各个部分是否正确。这是一组关于海洋生物的数据，no surfacing对应dataSet的第1列表示不浮出水面是否可以生存，flippers对应第2列表示是否有脚蹼，第3列的yes和no为标签，表示是否为鱼类。接下来我们会对这组数据进行分类。

3.划分数据

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

划分数据的函数需要3个参数。其中axis表示划分轴，value表示某个特定的值。
这里我们以数据矩阵的某1列(某一种特征)为轴进行划分。遍历矩阵每行，如果轴上的元素等于value，那么我们就用轴左边的所有元素加上轴右边的所有元素，来创建一个新向量(也就是去除了轴上元素的该行所有元素)，把新向量添加到新的矩阵中。

4.计算最佳的特征划分

def chooseBestFeatureToSplit(dataSet):
    numFeatrues = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatrues):
        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 * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = I
    return bestFeature

在第3节中我们实现了划分数据的函数，但是我们需要知道如何划分数据才是最好的。我们可以用香农熵进行选择，如果某种划分下，数据整体的香农熵最小(也就是原始未划分状态下的香农熵减去划分后的香农熵的值最大)，那么该划分就是最佳划分。
在代码中，首先获得特征数量(最后1列是标签，所以要减1)，并计算数据的原始未划分状态下的香农熵。
初始化最佳信息增益bestInfoGain和最佳划分特征bestFeature。按列遍历特征，利用集合无重复特性，将当前列所有特征保存在集合中。
初始化新的香农熵为newEntropy。遍历特征集合，累加以当前列为轴，各个特征(无重复)为指定value划分下的香农熵，值赋给newEntropy。遍历完后的newEntropy就是当前轴划分下的数据整体香农熵。原始熵减去新熵就是得到了信息增益。
这里的if语句就是传统的求最大值的方法。在遍历完所有轴，计算完所有划分后，bestInfoGain保存的就是最大的信息增益，bestFeature就是最大信息增益划分的对应轴。最后把该轴返回。

5.多数表决制决定分类

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] # 返回出现次数最多的分类

在实际建树之前，我们需要处理一种可能发生的情况。就是在处理完所有特征划分后，剩下的向量中的元素仍然不属于同一个标签。显然只有1列的向量无法划分，所以我们采用多数表决制。这段代码的作用就是让我们就对每个标签进行计数，然后返回次数最多的标签。

6.建树

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

建立树这种数据类型的时候，通常会采用递归的方法。采用递归方法时，我们需要一个基本条件终止递归。这段代码中，首先建立最后1列标签向量组成的列表。然后判断两种情况，第1种情况是如果列表里只有一种标签，也就是剩下的数据全都是同一个分类时，直接返回该标签。第2种情况是剩余数据为列向量，也就是处理完了所有划分的时候，采用多数表决制，返回次数最多的标签。
接下来是函数的主要部分，首先使用第4节的chooseBestFeatureToSplit函数获得最佳划分特征，保存该特征的标签。创建以该标签为键的哈希表myTree，其值为1个空的哈希表。然后将最佳标签从labels列表中删除。
通过列表推导和集合，保存最佳特征轴的所有不同值。这些值作为myTree的子哈希表中的键，键的值通过递归建树获得。注意，递归函数中的第1个参数是通过最佳特征轴划分后剩余的数据(去除了该轴)，第2个参数是去除了最佳特征标签的labels的拷贝subLabels。

myTree

7.绘制树结点

import matplotlib.pyplot as plt


decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")

def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt, \
    xycoords='axes fraction', \
    xytext=centerPt, textcoords='axes fraction', \
    va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)

决策树的测试是通过绘制图形来实现的。这里我们要利用matplotlib模组进行图形绘制。
首先建立treePlotter.py。定义决策结点、叶结点，树枝的样式，然后定义plotNode函数绘制树结点。

函数plotNode()的例子

8.获取叶节点的数目和树的层数

def getNumLeafs(myTree):
    numLeafs = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            numLeafs += getNumLeafs(secondDict[key])
        else: numLeafs += 1
    return numLeafs

def getTreeDepth(myTree):
    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

遍历树时，和建树一样，使用递归方法会更加高效。在getNumLeafs函数中，我们先获得根节点，然后获得根节点的值(哈希表)。遍历这个哈希表的所有键，如果键是字典属性(哈希表)，那么递归求得这个子哈希表的叶。如果不是字典属性，那么就让numLeafs变量自增。
getTreeDepth函数也是一样的方法，先获得根节点，然后获得根节点的值(哈希表)，遍历其所有键，如果键是字典属性，那么深度为子哈希表递归函数的返回值+1。如果不是字典属性的话，深度就等于1。这里比getNumLeafs函数多了一个求最大值的步骤，保证最后返回的是最大深度。

def retrieveTree(i):
    listOfTrees = [{'no surfacing': {0: 'no', 1: {'flippers': \
                    {0: 'no', 1: 'yes'}}}},
                   {'no surfacing': {0: 'no', 1: {'flippers': \
                    {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
                   ]
    return listOfTrees[I]

这里定义一个测试用的函数，返回的列表中第1个元素为之前我们建的树。这个函数用来测试getNumLeafs函数和getTreeDepth函数是否正常工作。

函数正常工作

9.绘制树

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, va="center", ha="center", rotation=30)

plotMidText函数用来在两个节点坐标的中点绘制文本信息。rotation=30可以让文本信息绘制时逆时针旋转30度，显示文字信息时更加美观。

def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    firstStr = list(myTree.keys())[0]
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, \
              plotTree.yOff)
    plotMidText(cntrPt, parentPt, nodeTxt)
    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.0 / 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

plotTree函数是绘制树的主要函数。和之前的getNumLeafs函数和getTreeDepth函数一样，plotTree函数采用递归方法遍历树进行绘制。
cntrPt变量保证每次绘制子结点时，动态平分坐标，对称绘制。计算式中的plotTree.xOff，plotTree.yOff为全局变量，plotTree.xOff在遍历到叶时更新，向右增加一个叶结点的平均宽度，plotTree.yOff在每深入一层后更新，向下递减1个深度，并且在函数最后还原，这样可以保证在递归到某个不是最深的子树时，遍历完该子树所有叶后y坐标可以返回子树的根继续绘制另一方向。

def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    plotTree.xOff = -0.5 / plotTree.totalW; plotTree.yOff = 1.0;
    plotTree(inTree, (0.5, 1.0), '')
    plt.show()

createPlot是运行绘制程序的函数，在函数中获得树的总宽度和总深度，然后根据这两个值计算xOff和yOff。

函数createPlot()运行结果

10.实现决策树分类器

def classify(inputTree, featLabels, testVec):
    firstStr = list(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

我们需要实现分类器才能对外部数据进行分类预测。这里的代码还是老样子，递归进行匹配。
在使用海洋生物数据建的树进行分类时，输入数据testVec应为一个包含2个元素列表，分别为不浮出水面是否可以生存{0,1}和是否有脚蹼{0,1}。程序会在根结点进行第1列特征的匹配，如果第1列特征值为1的话，进入右侧子树根结点，然后进行第2列特征的匹配，最后返回分类结果。

11.决策树的存储

def storeTree(inputTree, filename):
    import pickle
    fw = open(filename, 'wb') # 以二进制格式写入
    pickle.dump(inputTree, fw)
    fw.close()

def grabTree(filename):
    import pickle
    fr = open(filename, 'rb') # 以二进制格式读取
    return pickle.load(fr)

和k-近邻算法不同，决策树建成后的模型可以作为数据存储，不用每次重新计算。这里利用pickle模组，可以以二进制格式存储决策树。

12.使用决策树预测隐形眼镜类型

def createLensesTree:
    import treePlotter
    fr = open('lenses.txt')
    lenses = [inst.strip().split('\t') for inst in fr.readlines()]
    lensesLabel = ['age', 'prescript', 'astigmatic', 'tearRate']
    lensesTree = createTree(lenses, lensesLabel)
    print(lensesTree)
    storeTree(lensesTree, 'lensesTree_classifierStorage.txt')
    treePlotter.createPlot(lensesTree)

首先导入绘制树的程序，因为数据中每个特征用制表符分割，所以用split方法提取每个特征，并用strip方法去除行首尾的空格，推导出二维列表。

lenses.txt

手动定义标签列表，然后使用createTree函数建树，输出树后可以看到，哈希表层数过多已经很难分清逻辑关系。

lensesTree

用treePlotter.createPlot函数绘制树后如下图。