决策树的搭建与绘制

理论知识大部分参考七月在线学习笔记（很好，推荐）https://www.zybuluo.com/frank-shaw/note/103575

部分理论和编程主要参考《机器学习实战》

 

一、作用

首先，要搞清楚决策树能做什么？

事实上，决策树学习是用于处理分类问题的机器学习方法，而这些类别事先是知道的，你只需要选择其中的某一个类作为你最终的决策即可，也就是说，决策树的学习是一个监督学习的过程。

具体例子网络上太多了，最经典的、我看的最多的一个也就是女儿相亲问题，有兴趣可以查看我给出的参考文献中的具体例子。

总之，决策树的作用就是帮助我们在一定的情况下，作出作好的决策或者说是决定！

 

二、决策树的一般流程

(1)收集数据：可以使用任何方法。

(2)准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。

(3)分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。

(4)训练算法：构造树的数据结构。

(5)测试算法：使用经验树计算错误率。

(6)使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据

的内在含义。

 

三、决策树的生成算法

决策树算法中，最重要的一步，也就是根据已有数据构建决策树。那么如何来构建这个决策树呢？这里主要采用自顶向下的构建方式，采用的算法主要有以下三种：ID3、C4.5、CART,这里简单介绍一下三个算法表达的思想，具体数学推导这里不再赘述，网络上实在太多太多，参考资料中有较为消息的解释！

（1）ID 3

ID3算法的实质就是使用贪婪算法的思想，自顶向下地使寻找减小数据无序程度的分类方式！

而这个无序程度我们用信息熵来进行量化。公式如下：假如一个随机变量的取值为，每一种取到的概率分别是，那么

   的熵定义为

信息熵的值越高则表示当前数据无序程度越高，越低则表示数据无序程度越低。对于数据分类，我们当然希望得到无序程度尽可能低的分类方式！

那么，每选择一个分类特征，该数据的无序程度应该得到一定的减少，而这个减少的量我们称之为信息增益！

上文中说明该算法使用到了贪婪算法的思想：实际上，每次之选择当前最好的，也就是能使当前数据无序程度减少最多的特征作为分类对象，而像这样的每次筛选，实际上是对局部最优解的求解而非全局，所以，该算法下决策数很可能过拟合！

（2）C4.5

C4.5算法是基于ID3算法的，也是ID3的一种改进算法！

之所以说ID3算法的改进，是因为ID3算法是有明显的缺点，举例说明：

若对于当前数据来说，有一个特征X下有10个（甚至更多）不同的、独立的取值，而每个取值恰好只有一个数据！

仔细想一下，该特征分类下，无序程度将刚好等于0,也就代表着此时的信息增益是最大的！那么算法选择该特征为分类特征，则会得到一个很宽但是很浅的决策数，这样的分类是很不理想的！

这是一个极端情况，实际上，ID3算法更倾向于选择特征取值更多的特征！

此时，引入了C4.5算法，该算法使用信息增益率来筛选分类特征！

上述情况下，信息增益率将引入一个很大的数（分母）来修正信息增益，于是就避免了ID3算法的不足之处！

（3）CART

也称为回归决策树

 CART算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，

 因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能

 是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。在CART算法中主要分为两个步骤

   （1）将样本递归划分进行建树过程

   （2）用验证数据进行剪枝

参考：http://blog.csdn.net/acdreamers/article/details/44664481

http://www.cnblogs.com/zhangchaoyang/articles/2709922.html

 

上述三个算法，都是基于贪新算法原理的，所以都存在局部最优解以及过拟合的问题。过拟合实际上就是对噪声数据过于敏感，是一种不利于得到正确结果的拟合方式。

决策树算法中，为了避免过拟合的出现，往往采用修剪树的办法，具体修剪理论，参考：http://blog.sina.com.cn/s/blog_4e4dec6c0101fdz6.html

 

四、基于Python的具体实现

代码见下，注释写的非常清楚了！

import matplotlib.pyplot as plt
from math import log
import operator

#定义节点的绘图类型以及箭头形式
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")

#计算最后一个特征分类的信息熵
def calcShannonEnt(dataSet):
    numEntries  = len(dataSet)#统计数据量的大小
    labelCounts = {}#对每一个例子特征计数的数组
    #遍历所有的例子
    for feature in dataSet:
        currentLabel = feature[-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
#创建数据
def createDataSet():
    dataset = [[0,1,1,1,'yes'],[0,0,1,1,'yes'],[1,1,0,0,'maybe'],[0,1,0,1,'no'],[1,0,0,0,'no']]
    labels = ['tail','head','no surfacing','flippers']
    #dataset = [[1,1,'mabey'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
    #labels = ['no surfacing','flippers']
    return dataset,labels
#dataset带划分数据集，axis划分数据集的特征，value特征的返回值
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
#看选取哪一个特征作分类可以使得信息增益最大，也就是无序程度降得最低
def chooseBestFeatureToSplit(dataset):
    numFeature = len(dataset[0]) - 1#最后一个是决策层
    baseEntropy = calcShannonEnt(dataset)#计算整个数据的信息熵
    bestInfoGain = 0.0
    bestFeature = -1#表示最后一个特征哟
    for i in range(numFeature):
        featList = [example[i] for example in dataset]#第i个特征的所有特征分类值
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataset,i,value)
            prob = len(subDataSet)/float(len(dataset))#value的例子个数/整个例子的个数
            newEntropy += prob * calcShannonEnt(subDataSet)#这里实际上计算分类后的无序程度，作为增益
            infoGain = baseEntropy - newEntropy#信息增益是熵的减少或者是数据无序度的减少
        if (bestInfoGain < infoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature
#求某个特征中特征值最多的特征值
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):#如果所有的特征值都和classList[0]相同的话，返回这个类别
        return classList[0]
    if len(dataSet[0]) == 1:#只有一个特征了,返回这个特征出现次数最多的特征值
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)#求当前最佳的划分特征
    #print(bestFeat)
    bestFeatLabel = labels[bestFeat]
    print(bestFeat)
    myTree = {bestFeatLabel:{}}
    #print(myTree)
    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.数据要一一对应，

    data = {{data1,data2,....datan,decision1},{...},...,{...}}

    labels = {label1,label2,....,labeln}

    data中最后一个数据是决策层的数据！

     2.注意退出条件：（关注createTree函数）

    <1> 决策相同，无需分类（所以这可能出现有些类别用不到，后面会详细提到）

    <2> data只有决策层了，特征都已经分完了

              

 五、基于Python的决策树绘制

该部分参考《机器学习实战》一书，但是仔细做过的同学应该会发现，书上给的代码貌似不是很正确，或者说，不是很理想吧，这里对决策树的绘制进行了一些修改，得到还不错的效果。这里使用到Python的绘图工具Matplotlib，首先，我们需要安装Matplolib工具包。      

 （1）安装Matplotlib工具包

为了方便，可以安装Anaconda的Python科学集成环境，Anaconda中包含有很多Python的科学计算工具，包括numpy、matplotlib等。安装完成之后，在Pycharm中选择当前解释器为Anaconda/python.exe，即可使用Anaconda提供的科学工具包了

（2）先来看看代码和效果吧          

代码：      

#定义节点的绘图类型以及箭头形式
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")

#获得树的叶节点的数目
def getNumLeafs(myTree):
    numLeafs = 0
    firstStr = list(myTree.keys())[0]#获得当前第一个根节点
    secondDict = myTree[firstStr]#获取该根下的子树
    for key in list(secondDict.keys()):#获得所有子树的根节点，进行遍历
        if type(secondDict[key]).__name__ == 'dict':#如果子节点是dict类型，说明该子节点不是叶子节点
            numLeafs += getNumLeafs(secondDict[key])#不是子节点则继续往下寻找子节点，直到找到子节点为止
        else:
            numLeafs += 1#找到子节点，数+1
    return numLeafs

#获得树的层数
def getTreeDepth(myTree):
    treeDepth = 0
    temp = 0
    firstStr = list(myTree.keys())[0]#获得当前第一个根节点
    secondDict = myTree[firstStr]#获取该根下的子树
    for key in list(secondDict.keys()):#获得所有子树的根节点，进行遍历
        if type(secondDict[key]).__name__ == 'dict':#如果子节点是dict类型，说明该子节点不是叶子节点
            temp = 1 + getTreeDepth(secondDict[key])#该节点算一层，加上往下数的层数
        else:
            temp = 1#叶子节点算一层
        if temp > treeDepth:
            treeDepth = temp
    return treeDepth

#计算父节点到子节点的中点坐标，在该点上标注txt信息
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)


def plotTree(myTree,parentPt,nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    firstStr = list(myTree.keys())[0]
    #cntrPt = (plotTree.xOff + (0.5 + float(numLeafs)/2.0/(plotTree.totalW*plotTree.totalW)),plotTree.yOff)
    #cntrPt = (0.5,1.0)
    cntrPt =((2 * plotTree.xOff + (float(numLeafs) + 1) * (1 / plotTree.totalW)) / 2 , plotTree.yOff)
    print(plotTree.xOff)
    plotMidText(cntrPt,parentPt,nodeTxt)
    plotNode(firstStr,cntrPt,parentPt,decisionNode)
    secondDict =  myTree[firstStr]
    #print(secondDict)
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    for key in list(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 = 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子节点绘图添加注释。具体解释：nodeTxt：节点显示的内容；xy：起点位置；xycoords/xytext：坐标说明？；xytext：显示字符的位置
#va/ha：显示的位置？；bbox：方框样式；arrow：箭头参数，字典类型数据
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
                            xytext=centerPt, textcoords='axes fraction',
                            va="bottom", ha="center", bbox=nodeType, arrowprops=arrow_args)                          

我们注意到程序中定义的数据和标签如下：

    dataset = [[0,1,1,1,'yes'],[0,0,1,1,'yes'],[1,1,0,0,'maybe'],[0,1,0,1,'no'],[1,0,0,0,'no']]
    labels = ['tail','head','no surfacing','flippers']

得到决策树结果：{'no surfacing': {0: {'tail': {0: 'no', 1: {'head': {0: 'no', 1: 'maybe'}}}}, 1: 'yes'}}

绘制决策树：

      这个决策树的绘制是怎么得到的呢？（再次强调一下，我自己运行《机器学习实战》一书的代码，得到的绘制结果是不对的，不知道是不是我自己弄错了，还望大家指正，这里我揣测文意，稍微修改了一下代码）

首先，我们要确定一下绘制决策树的一些原则：

1.自上到下的树形结构

2.树的根节点在图的中心位置

3.树的宽度尽量均匀覆盖整个图片（就是最左\右边的叶子离图像边框距离短且相等）

4.假设整张图片的大小为1*1

有了以上的基本原则，在使用决策树算法得到了myTree的决策树后，就能方便地绘制决策树了！在编程过程中，实际上是利用递归的方式（与myTree的构建方式类似），自上而下、自左而右的顺序来绘制图像，终止条件是遇到了叶子节点。

（1）对于高度，我们希望树能填充整个图像，于是，我们要得到树的深度depth，则可以设置高度的绘制步长为step_h = height/depth。由于绘制顺序是自上而下的（这里的自上而下是一个宏观上的看法，对于每个小的子树的搜寻顺序实际上是：根节点->左子树->根节点->右子树），故每一次递归都要y-step_h，当该次递归结束之后，需要y+step_h，回到递归的起始节点，继续判断递归（这个意思就是，该节点左子树递归，递归完毕回到该节点，开始递归右子树的过程）

（2）对于宽度，我们同样希望树能填充整个图像，于是，我们要得到树的叶子节点数目leafs，则可以设置宽度的绘制步长为step_w = width/leafs。根节点设置在中点位置，即（0.5，1）。接下来，每次递归的子树的根节点将位于其子树的中心位置（也就是该子树所有叶子节点构成宽度的中间）。由于绘制顺序是自左而右的，故我们设置xOff的初始值是-step_w*0.5，每次递归都令xOff = xOff + step_w，如此，最左和最右的叶子节点与图边框相差距离为step_w*0.5！

 绘图过程完毕！是不是很简单！

 

回过头来，再来看看决策树构建过程，createTree的终止条件问题。首先看这几组数据集得到的决策树结果：

（1）

 dataset = [[0,1,1,1,'yes'],[0,0,1,1,'yes'],[1,1,0,0,'maybe'],[0,1,0,1,'no'],[1,0,0,0,'no']]
 labels = ['tail','head','no surfacing','flippers']

 结果：{'no surfacing': {0: {'tail': {0: 'no', 1: {'head': {0: 'no', 1: 'maybe'}}}}, 1: 'yes'}}

 

（2）

dataset = [[0,1,1,1,'yes'],[0,0,1,1,'yes'],[1,1,0,0,'maybe'],[0,1,0,1,'no'],[1,0,0,1,'no']]
labels = ['tail','head','no surfacing','flippers']

    结果：{'no surfacing': {0: {'flippers': {0: 'maybe', 1: 'no'}}, 1: 'yes'}}              

                     
仔细看会发现，（1）和（2）的数据集相差仅一个数据的不同，但是（2）的分类方式却与（1）大相径庭，甚至少一个标签，乍一看，有种“我写的决策树是不是错的”感觉！其实，认真思考会发现，这是递归终止条件所导致的！回顾一下上文中提到的决策树递归终止条件，有两个：

     <1> 决策相同，无需分类

     <2> data只有决策层了，特征都已经分完了

不妨模拟一下（2）的过程。（2）的数据集如下表：

tail	head	no surfacing	flippers	fish
0	1	1	1	yes
0	0	1	1	yes
1	1	0	0	maybe
0	1	0	1	no
1	0	0	1	no

step1：发现，no surfacing是当前最好的分类特征，划分出来

于是根据no surfacing得到两组数据

1.no surfacing = 1

tail	head	flippers	fish
0	1	1	yes
0	0	1	yes

2.no surfacing = 0

tail	head	flippers	fish
1	1	0	maybe
0	1	1	no
1	0	1	no

step2:

对no surfacing = 1的数据，可以看到，决策层都为“yes”，故该子树递归结束！即，如图得到no surfacing的右子树。

对no surfacing = 0的数据，继续递归，得到最佳的分类特征为“flippers”，分类后得到数据如下表：

1.flippers = 0

tail	head	fish
1	1	maybe

2.flippers = 1

tail	head	fish
0	1	no
1	0	no

step3:

对flippers = 0的数据，很明显，只有一条数据集，故递归结束，该子树生成叶子节点。

对flippers = 1的数据，决策层数据都为“no”，故递归也结束，生成叶子节点。

决策树生成完毕！！！