机器学习实战学习笔记（二）决策树

PS：该系列数据都可以在图灵社区（点击此链接）中随书下载中下载（如下）

1 决策树的构造

													决策树
	优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
	缺点：可能会产生过度匹配问题。
	使用数据类型：数值型和标称型。

  创建分支的伪代码函数createBranch()如下：

检测数据集中的每个子项是否属于同一分类：
	If so return 类标签:
	Else:
		寻找划分数据集的最好特征
		划分数据集
		创建分支节点
			for 每个划分的子集:
				调用函数createBranch并增加返回结果到分支节点中
		return 分支节点

  这里使用ID3算法划分数据集。

1.1 信息增益

  划分数据集的最大原则是：将无序的数据变得更加有序。用到两个概念信息增益（information）和熵（entropy）.
  熵定义为信息的期望值，先引入信息的定义。如果待分类的事务可能划分在多个分类之中，则符号$x_i$xi​的信息定义为：$l(x_i) = - log_2p(x_i)$l(xi​)=−log2​p(xi​)，其中$p(x_i)$p(xi​)是选择该分类的概率。而计算熵，需要计算所有类别所有可能值包含的信息期望值，熵公式：$H = -\sum_{i=1}^np(x_i)log_2p(x_i)$H=−∑i=1n​p(xi​)log2​p(xi​)，其中$n$n是分类的数目。
  建立trees.py文件，利用python计算信息熵：

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) #以2为底求对数
    return shannonEnt 

  编写createDataSet()函数创建数据集，以便于测试：

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命令符下输入命令测试：


  可见，熵越高，则混合的数据也越多，我们可以按照获取最大信息增益的方法划分数据集。

1.2 划分数据集

def splitDataSet(dataSet, axis, value):
    '''
    按照给定特征划分数据集
    dataSet：划分数据集
    aixs：划分数据集的特征
    value：需要返回的特征的值
    '''
    retDataSet = []
    for featVec in dataSet:
        #将符合特征的数据抽取出来
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

  同样在python命令行界面进行测试，这里需要注意的是我们修改了trees.py文件就需要利用importlib.reload()函数重新载入该模块：

  遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。

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]
        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

  根据信息增益是熵的减少或者是数据无序度的减少选择最好的特征划分方式。同样的在Python命令行中测试：

  观察myDat中的数据，如果按照第一个特征属性划分数据集，那么第一个特征为1的结果将有两个‘yes’，一个‘no’，另一个分组结果则全部为‘no’；而如果按照第二个特征属性划分数据集，那么第二个特征为1的结果将有两个‘yes’，两个‘no’，另一个分组将只有一个‘no’。显然第一种划分更好地处理了相关结果，证明改程序划分结果正确。

1.3 递归构建决策树

  递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果数据集已经处理了所有属性，但是类标签依然不是唯一的，在这种情况下，通常会采用多数表决的方法决定改叶子节点的分类。因此增加majorityCnt()函数来投票表决返回出现次数最多的分类名称和createTree()函数来创建树，首先在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.items(), 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

  同样在Python命令行界面进行测试：

  这里通过嵌套字典代表了树结构信息，这棵树包含了3个叶子节点以及2个判断节点。

2 在Python中使用Matplotlib绘制树形图

2.1 Matplotlib注解

  Matplotlib提供了一个注释工具annotations，利用其功能可以绘制树形图，以便于更直观的理解数据信息的内在含义。因此创建名为treePlotter.py的新文件，输入下面程序：

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(nodeText, centerPt, parentPt, nodeType):
    '''绘制带箭头的注解'''
    #annotate是一个关于数据点的文本
    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为全局变量，111代表在画布中的图有一行一列，最后一个1表示第一个图
    #frameon表示是否绘制坐标轴矩形
    createPlot.ax1 = plt.subplot(111, frameon=False)
    plotNode(U'decisionNode', (0.5, 0.1), (0.1, 0.5), decisionNode)
    plotNode(U'leafNode', (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()

  在python命令行界面进行测试输出结果：


  程序输出结果如上图，这里只是基本展示一下如何绘制树节点，后面进入如何绘制整棵树。

2.2 构造注解树

  绘制一棵完整的树需要考虑如何放置所有的树节点。所以我们必须知道有多少个树节点，以便于可以正确确定节点x轴的长度；还需要知道树有多少层，以便可以正确确定节点在y轴的高度。因此定义两个新函数获取叶节点的数目和树的层数，注意这里的层数不算根节点（即根节点不算一层），添加到文件treePlotter.py中。
  同时为了方便测试，编写函数预先存储树的信息，避免每次测试代码都要从数据中创建树的麻烦（这里使用python3的写法区别书中的python2写法）：

def getNumLeafs(myTree):
    '''获取叶节点的数目'''
    numLeafs = 0
    #获得myTree的第一个键值，即第一个特征
    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

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]

  在Python命令行界面进行测试结果正确：

  下面我们绘制完整的一棵树，为此我们需要更新createPlot()函数并增加新的代码，下面的程序是这部分的关键其中的细节也不太好理解：

def plotMidText(cntrPt, parentPt, tXtString):
    '''在父子节点间填充文本信息'''
    xMid = (parentPt[0] + cntrPt[0]) / 2.0
    yMid = (parentPt[1] + cntrPt[1]) / 2.0
    createPlot.ax1.text(xMid, yMid, tXtString)

def plotTree(myTree, parentPt, nodeText):
    '''绘制决策树'''
    #计算宽和高
    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, nodeText)
    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

def createPlot(inTree):
    '''绘图主函数'''
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    #定义横纵坐标，无内容
    axprops = dict(xticks=[], yticks=[])
    #createPlot.ax1为全局变量，111代表在画布中的图有一行一列，最后一个1表示第一个图
    #frameon表示是否绘制坐标轴矩形
    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()

  这里作者很聪明，利用偏移量的机制，通过计算树包含的所有叶子节点数，划分图形的宽度，从而计算得到当前节点的中心位置，也就是说，我们按照叶子的数目将x轴划分为若*分。按照图形比例绘制树形图的最大好处是无需关系实际图形的大小，一旦图形大小发生了变化，函数会自动按照图形大小重新绘制。如果以像素为单位绘制图形，则不容易缩放图形。同理对于y轴也是如此。
  这里有两句更新$xOff$xOff(当前节点的x轴坐标)的代码不太容易理解plotTree.xOff = -0.5 / plotTree.totalW和cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)，关于这部分的理解可以参考[机器学习&数据挖掘]机器学习实战决策树plotTree函数完全解析，这篇博客里已经解释的很详细了，这里就不再赘述。
  Python命令行测试结果如下：

3 测试和存储分类器

3.1 测试算法：使用决策树执行分类

  为了验证算法的实际效果，编写决策树的分类函数代码，添加到trees.py文件中：

def classify(inputTree, featLables, testVec):
    '''使用决策树的分类函数'''
    firstStr = list(inputTree.keys())[0]
    secondDict = inputTree[firstStr]
    #将标签字符串转换为索引
    featIndex = featLables.index(firstStr)
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = classify(secondDict[key], featLables, testVec)
            else:
                classLabel = secondDict[key]
    return classLabel

  在Python命令行进行如下测试，将结果与之前绘制的第一个树形注解图做对比，结果正确：

3.2 使用算法：决策树的存储

  可以使用Python模块pickle序列化对象，序列化对象可以在磁盘上保存对象，并在需要的时候读取出来。下面的代码可以将分类器存储在硬盘上，而不用每次对数据分类时重新学习一遍，这也是决策树的优点之一，而像kNN算法就无法持久化分类器。我们可以预先提炼并存储数据集中包含的知识信息，在需要对事物进行分类时再使用这些知识。

'''使用pickle模块存储决策树'''
def storeTree(inputTree, filename):
    import pickle
    with open(filename, 'wb') as fileObject:
        pickle.dump(inputTree, fileObject)

def grabTree(filename):
    import pickle
    with open(filename, 'rb') as fileObject:
        return pickle.load(fileObject)

  进行测试：

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

  下载数据集，并将其中Ch03文件夹中的lenses.txt数据文件复制到trees.py和treePlotter.py所在文件夹，在Python命令行输入下列命令加载数据并绘制决策树：


  上图所示的决策树很好地匹配了实验数据，然而这些匹配选项可能太多了，我们将这个问题称之为过度匹配（overfitting）。为了减少过度匹配问题，可以裁剪决策树，去掉一些不必要的叶子节点。如果叶子节点只能增加少许信息，则可以删除该节点，将它并入到其他叶子节点中。
  可以利用另一个决策树构造算法CART，这里使用的是ID3算法，ID3算法无法直接处理数值型数据。

5 小结

  决策树分类器就像带有终止块的流程图，终止块表示分类结果。开始处理数据集时，我们首先需要测量集合中数据的不一致性，也就是熵，然后寻找最优方案划分数据集，直到数据集中的所有数据属于同一分类。ID3算法可以用于划分标称型数据集。
  使用Matplotlib的注解功能，我们可以将存储的树结构转化为容易理解的图形。Python语言的pickle模块可用于存储决策树的结构。隐形眼镜的例子表明决策树可能会产生大量信息增益从而产生过度匹配数据集的问题。我们可以通过裁剪决策树，合并相邻的无法产生大量信息增益的叶节点，消除过度匹配问题。