《机器学习实战》3.决策树算法分析与源码实现

结合源码分析第三章中实现的Demo
运行环境：Anaconda——Jupyter Notebook
Python版本为：3.6.2（原书代码实现为2.x 所以在一些代码上略有改动）
阅读本博文你将获取：
1.决策树的基本思想
2.信息增益和熵的概念——本文中使用信息增益作为划分数据集的标准
3.全部的代码实现，且包含了大部分注释，便于初学者者理解
4.在最后的总结部分对决策树的优缺点做了总结
参考资料：Apachecn 专注于优秀项目维护的开源组织

---

前言

决策树（Decesion Tree）是一种基本的分类算法。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点就是模型具有可读性，分类速度块。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从可能的决策树中直接选取最优决策树是NP问题，现实中采用启发方法学习次优的决策树。
决策树学习算法包括3部分：特征选择、树的生成和树的剪枝。常用算法有ID3（本文采用）、C4.5和CART算法。
决策树的生成：通常使用信息增益最大，信息增益比最大，或基尼指数最小作为特征选择的准则。决策树的生成往往通过计算信息增益或其他指标，从根节点开始，递归地产生决策树。这相当于用信息增益或其他准则不断地选取局部最优 的特征，或将训练集分割为能够基本正确分类的子集。
决策树的剪枝：由于生成的决策树存在过拟合的问题，需要对它进行剪枝（考虑全局最优）。决策树的剪枝，往往从已生成的树上剪掉一些叶结点或叶结点以上的树，并将其父结点或根结点作为新的叶结点。

---

3.1 决策树的构造

创建分支的伪代码如下：

决策树的一般开发流程：

---

3.1.1 信息增益（Information）和熵（Entropy）

严格来说这个概念是信息论里的概念。（笔者之前学过通信原理所以相对熟悉一点）。
首先，明白一点。我们日常生活中会接收到无数的消息，但是只有那些你关心在意（或对你有用）的才叫做信息。（张三告诉我李四今天一只袜子丢了，事实上我也不认识李四，对于我来说这仅仅是一则消息，因为这和我没有太多关系，我也不必去在意）。
另外，想一下如何度量这种信息的大小或多少呢，香农说了，可以使用信息量来度量。在日常生活中，极少发生 的事件一旦发生是容易引起人们关注的（新闻说发生空难了，那必然会引起人们很大的关注，但事实是发生空难的概率很小很小），而 司空见惯的事不会引起注意 ，也就是说，极少见的事件所带来的信息量多。如果用统计学的术语来描述，就是出现概率小的事件信息量多。因此，事件出现得概率越小，信息量愈大。即信息量的多少是与事件发生频繁（即概率大小）成反比 。

---

设X是一个取有限个值的离散随机变量，X=xi （i=1,2…,n）。则信息量定义为
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值：<对数以2和e为底时，熵的单位分别叫做比特（bit）和奈特（nat）>

程序清单3-1：计算给定数据集的香农熵

from math import log
def calcShanonEnt(dataSet):
    numEntries = len(dataSet) #计算实例总数
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1] #-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) #base = 2 求对数
    return shannonEnt

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

输入：

myDat,labels = createDataSet()
myDat

输出：

[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

输入：

calcShanonEnt(myDat)

输出：

0.9709505944546686

按照书上内容，在数据集中增加更多的分类，观察熵的变化。
输入：

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

输出：

[[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

再次计算熵，输入：

calcShanonEnt(myDat)

输出：

1.3709505944546687

发现增加了maybe分类后，熵有了增加。

---

3.1.2 划分数据集

程序清单3-2 按照给定特征划分数据集

#输入：dataSet 数据集——待划分的数据集
#axis 表示每一行的axis列——划分数据集的特征
#value 表示axis列对应的value值——需要返回的特征的值
#输出：index列为value的数据集 <该数据集不包括axis列>
def splitDataSet(dataSet,axis,value):
    #splitDataSet(通过遍历dataSet数据集，求出index对应的colnum列的值为value的行)
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:  #判断axis列的值是否为value
            reducedFeatVec = featVec[:axis]  #取featVec的前axis行
            # start 缺省默认从头开始。当操作对象是一维数据时，就是去前axis个元素
            reducedFeatVec.extend(featVec[axis+1:]) #[axis+1:]表示跳过第axis行，从第axis+1行开始，取接下来的数据
            #当操作对象是一维数据时，就是跳过第axis个元素，从第axis+1个元素开始，取接下来的数据
            retDataSet.append(reducedFeatVec)
    return retDataSet

myDat

输出：

[[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

输入；

splitDataSet(myDat,0,1)

输出：

[[1, 'maybe'], [1, 'yes'], [0, 'no']]

输入：

splitDataSet(myDat,0,0)

输出：

[[1, 'no'], [1, 'no']]

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

程序清单3-3 选择最好的数据集划分方式

#熵H(Y)与H(Y\X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息
#输入：数据集
#输出：返回最优的特征列
def chooseBestFeatureToSplit(dataSet):
    #计算Feature的个数（列数）
    numFeatures = len(dataSet[0]) - 1  #dataSet[0]计算行元素的个数 最后一列是label
    baseEntropy = calcShanonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures): #在所有Feature中循环
        # 获取每一个实例的第i+1个feature，组成list集合
        featList = [example[i] for example in dataSet] #example[i]代表样本集中，第i+1列所有feature
        uniqueVals = set(featList) #使用set对featList进行去重
        newEntropy = 0.0 #创建一个临时的信息熵
        # 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。
        for value in uniqueVals: # 遍历某一列的value集合，计算该列的信息熵
            subDataSet = splitDataSet(dataSet,i,value)
            prob = len(subDataSet)/float(len(dataSet)) #根据不同的特征值分类计算所占百分比
            newEntropy += prob * calcShanonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i 
    return bestFeature

该函数实现选取特征，划分数据，计算得出最好的划分数据集的特征。

键入命令：

chooseBestFeatureToSplit(myDat)

输出结果为：

0

代码运行结果告诉我们，第0个特征是最好的用于划分数据集的特征。

---

3.1.3 递归构建决策树

在基于最好的属性值划分数据集后（第一次），数据将被向下传递到树分支的下一个节点，在这个节点上，我们再次划分数据。因此我们可以采用递归的原则处理数据集。
递归结束的条件是：
1.每个分支下的所有实例都具有相同的分类。
2.数据集已经处理了所有属性，但是类标签依然不唯一，此时我们需要使用投票的方式决定该叶子节点的分类。
程序清单 3-4：

#实现多数表决
import operator
def majorityCnt(classList):
    classCount = {}
    for vote in classCount:
        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] #这边返回的是yes和no
    #count()函数是统计括号中的值在list中出现的次数
    if classList.count(classList[0]) == len(classList):  
        return classList[0]
    # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
    # 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
    # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
    if len(dataSet[0]) == 1: #dataSet[0]为第一行所有元素
        return majorityCnt(classList)
    # 选择最优的列，得到最优列对应的label含义
    bestFeat = chooseBestFeatureToSplit(dataSet) #返回最优的特征列序号
    print('bestFeat:',bestFeat)
    bestFeatLabel = labels[bestFeat] # 获取对应的label名称
    print('bestFeatLabel:',bestFeatLabel)
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat]) #用完了删除该label名称
    featValues = [example[bestFeat] for example in dataSet]
    print('featValues:',featValues)
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:] #求出剩余的标签
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
        print('myTree:',myTree)
    return myTree

键入命令：

myDat,labels = createDataSet()
myTree = createTree(myDat,labels)
myTree

输出：

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

3.2在Python中使用Matplotlib注解绘制树形图

3.2.1 Matplotlib注解

程序清单3-5 使用文本注解绘制树节点：

import matplotlib.pyplot as plt
#定义决策树决策结果的属性 sawtooth 波浪方框 fc表示字体颜色的深浅 0.1~0.9 依次变浅
decisionNode = dict(boxstyle = 'sawtooth',fc = '0.8')
#定义决策树的叶子节点的属性 round4 矩形方框 
leafNode = dict(boxstyle ="round4",fc="0.8")
#定义决策树箭头属性 
arrow_args = dict(arrowstyle ="<-")
#nodeTxt为要显示的文本，centerPt为文本的中心点，箭头所在的点，parentPt为指向文本的点
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)
#创建绘图    
def createPlot():
    fig = plt.figure(1,facecolor='white') #定义一个画布 背景为白色
    fig.clf() #清空画布
    #createPlot.ax1为全局变量，绘制图像的句柄
    #frameon 是否绘制坐标轴矩形
    createPlot.ax1 = plt.subplot(111,frameon=False) 
    #绘制节点
    plotNode('decisionNode',(0.5,0.1),(0.1,0.5),decisionNode)
    plotNode('leafNode',(0.8,0.1),(0.3,0.8),leafNode)
    plt.show()

键入命令：

createPlot()

输出图形结果：

---

3.2.2构造注解树

上面的结果只是一个绘制树节点的小例子。
如果想要构造完整的树还需要一些小技巧：
1.需要知道有多少个叶节点，以便确定x轴的长度
2.需要知道树的层数，以便确定y轴的高度
程序清单3-6 获取叶节点的数目和树的层数：

# 获取决策树的叶子节点
def getNumLeafs(myTree): #变量myTree包含了很多代表树结构信息的嵌套字典
    numLeafs = 0 # 初始化叶子节点数目
    #获取myTree的第一个key，即第一个特征，分割的标签
    firstStr = myTree.keys()[0]
    #根据key得到相应的value，即根据第一个特征分类的结果
    secondDict = myTree[firstStr]
    #遍历得到的secondDict
    for key in secondDict.keys(): #其实上面得到的value是(嵌套的)dict
        #注意type()和isinstance()的区别
        #如果secondDict[key]为一个字典
        if type(secondDict[key])._name_ == 'dict':
            #则递归计算secondDict中的叶子节点数
            numLeafs += getNumLeafs(secondDict[key])
        else:
            #否则叶子节点数加一
            numLeafs +=1
    return numLeafs
#获取决策树的深度
def getTreeDepth(myTree):
    maxDepth = 0
    firstStr = myTree.keys()[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        #如果secondDict[key]为一个dict类型<非叶子节点>
        if type(secondDict[key])._name_ == 'dict':
            #则当前树的深度等于1加上secondDict的深度
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:
            #则将当前树的深度置为1
            thisDepth = 1
        #返回max{当前树的深度，最大树的深度}
        if thisDepth > maxDepth:
            maxDepth = thisDepth
    return maxDepth

接着，函数retrieveTree输出预先存储的树信息，避免每次测试代码时都要从数据中创建树的函数。

#预定义的树，用来测试
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]

输入如下代码:

myTree = retrieveTree(0)
print('NumLeafs:',getNumLeafs(myTree))
print('TreeDepth:',getTreeDepth(myTree))

输出结果应为：

NumLeafs: 3
TreeDepth: 2

现在我们将前面学习到的方法组合在一起，绘制一棵完整的树：

createPlot(myTree)

输出结果为：

程序清单3-7：plotTree函数

#绘制中间文本（在父子节点间填充文本信息）
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)
#绘制决策树
def plotTree(myTree,parentPt,nodeTxt):
    #获得决策树的叶子节点数与深度
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    #firstStr = myTree.keys()[0]
    firstSides = list(myTree.keys())
    firstStr = firstSides[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():
        #如果secondDict[key]是一颗子决策树，即字典
        if type(secondDict[key]) is 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 = 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()

树这里就不过多解释了。自己看以看一下书上的说明。上述程序是对的，可以绘出如下图形：

3.3 测试和存储分类器

到目前为止，本章学习的主要内容是如何从原始数据中创建决策树，并使用Python函数库绘制树形图，下面我们将要学习如何利用决策树执行数据分类上

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

依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。
程序清单 3-8 使用决策树的分类函数

#参数：inputTree--决策树模型 
#      featLabels--Feature标签对应的名称
#   testVec--测试输入的数据
#返回结果 classLabel分类的结果值(需要映射label才能知道名称)
def classify(inputTree,featLabels,testVec):
    firstsides = list(inputTree.keys())
    firStr = firstsides[0] #获取根节点的key
    secondDict = inputTree[firStr] #得到根节点对应的value(具体是嵌套着的一个Dict类型)
    #判断根节点名称,获取根节点在label中的向后顺序,这样就知道输入的testVec怎么开始对照树来做分类
    featIndex = featLabels.index(firStr)
    #测试数据，找到根节点对应的label位置,也就知道从输入的数据的第几位来开始分类
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    #判断valueOfFeat是不是字典类型，也就是判断是不是还有子集，有在进行递归判断
    if isinstance(valueOfFeat,dict):
        classLabel = classify(secondDict[key],featLabels,testVec)
    else:
        classLabel = valueOfFeat
    return classLabel

键入：

myTree = retrieveTree(0)
classify(myTree,labels,[1,0])

输出结果：

'no'

以前绘制的树形图和此处代表的数据结构完全相同。

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

由于构造决策树是一个十分耗时的任务。因此我们可以用创建好的决策树解决分类问题。此处，我们使用python中pickle序列化对象，保存相应的决策树模型。
程序清单3-9 使用pickle模块存储决策树

#使用pickle模块存储决策树
def storeTree(inputTree,filename):
    import pickle
    #创建一个可以'写'的文本文件
    #这里，如果按树中写的'w',将会报错write() argument must be str,not bytes
    #所以这里改为二进制写入'wb'
    fw = open(filename,'wb')
    pickle.dump(inputTree,fw) #将inputTree保存到fw中
    fw.close()

def grabTree(filename):
    import pickle
    #对应于二进制方式写入数据，'rb'采用二进制形式读出数据
    fr = open(filename,'rb')
    return pickle.load(fr) #读取

输入下列命令验证上述代码效果：

storeTree(myTree,'classifierStorage.txt')
grabTree('classifierStorage.txt')

输出结果为：

---

3.4 示例：使用决策树预测隐形眼镜模型

依次输入：

fr=open(r'C:\Users\Rujin_shi\Apache_cn\input\3.DecisionTree\lenses.txt')
#将文本数据的每一个数据行按照tab键分割，并依次存入lenses
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lenseLabels = ['age','prescript','astigmatic','tearRate']
#创建并存入特征标签列表
lenseTree=createTree(lenses,lenseLabels)
lenseTree

可视化：

#可视化
createPlot(lenseTree)

总结

本次实验所采取的算法称为ID3，虽然直观但是不是十分完美。ID3算法无法直接处理数值型数据，尽管我们可以通过量化的方法将数值型数据转化为标称型数据，但是如果存在太多的特征划分，ID3算法仍然会面临其他问题。
此外，我们还有的划分标准：信息增益比（C4.5）、基尼指数（CART）这些会在后续章节里用到。

对于决策树而言，优点有：
1.基于if-then的结构，理解简单；
2.计算复杂度不高，每一次预测的最大计算次数不会超过决策树的深度；
3.可以处理不相关特征数据
4.能够处理多输出问题
5.对中间缺失值不敏感
缺点：
1.容易生成较复杂的树，即过拟合问题（需要进行剪枝处理）
2.不适合处理高维数据，当属性数量过大的时候，部分决策树就不再适用
3.对异常值过于敏感。