机器学习算法之决策树_机器学习算法构造决策树

目录

一.前言

二.决策树

 2.1.概念

决策树构建整体流程如下

2.3实验

3决策树改进算法

3.1 改进ID3算法

4.剪枝策略

4.1预剪枝

4.2后剪枝

4.3剪枝实验代码

4.2.2预剪枝

五 结论

---

一.前言

决策树（decision tree）是一类常见的机器学习算法，用于分类和回归任务.它是基于树结构来进行决策的。从根节点开始一步步走到叶子节点（决策）。所有的数据最终都会落到叶子节点，既可以做分类也可以做回归。本文将深入探讨决策树算法，从基本原理到在Python中的实际应用，以及如何改进算法和进行实验分析。

二.决策树

 2.1.概念：

决策树是一种描述对实例进行分类的树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果，本质是一颗由多个判断节点组成的树。分类决策树模型是一种树形结构。 决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。

举个例子

决策树分类的思想类似于我们找对象。比如：

儿子：多大年纪了？                       (年龄)
 
母亲：26。
 
儿子：长的美不美？                       (长相)
 
母亲：很漂亮的。
 
儿子：收入高不？                           (收入情况)
 
母亲：不算很高，中等情况。
 
儿子：是公务员不？                        (是否公务员)
 
母亲：是，在税务局上班呢。
 
儿子：那好，我去见见。       

构造该例子的决策树：

   从上面的图中我们可以看出，前面五个决策树的规模比最后一个决策树大得多，这说明特征选择会影响决策树的形状及规模大小，也会影响决策的快慢，从上面六个决策树里可以观察到，富是起主要作用的特征属性，再者是白，然后再到美，所以对于结点的特征选取（即也是属性划分）是很重要的。

        决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度 ”(purity)越来越高。
 

决策树构建整体流程如下

(1) 收集数据：可以使用任何方法。
(2) 准备数据：树构造算法只是用于标称型数据，因此数值型数据必须离散化。
(3) 分析数据：可以使用任何方法，决策树构造完成后，可以检查决策树图形是否符合预期。
(4) 训练算法：构造一个决策树的数据结构。
(5) 测试算法：使用经验树计算错误率。当错误率达到可接收范围，此决策树就可投放使用。
(6) 使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

划分数据集的原则是：将无需的数据变得更加有序。

2.2信息增益

在划分数据集之前之后信息发生的变化称为信息增益（通俗理解就是特征X使得类Y的不确定性减少的程度），知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择 。

在可以评测哪种数据划分方式就是最好的数据划分之前，必须学习如何计算信息增益。集合信息的度量方式称为香农熵（information gain） 或者简称为熵（entropy） 。熵是表示随机变量不确定的度量（通俗理解就是物体内部的混乱程度，不确定性越大，得到的熵值也就越大）。

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事物可能划分在多个分类之中，则符号Xi的信息定义为

                                                

其中P(Xi)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：
 

                                             

n是分类的数目。

当或时，随机变量完全没有不确定性。
当,随机变量的不确定性最大。
熵随P变化的曲线图像如下：

用Python计算熵

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet: #the the number of unique elements and their occurance
        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

代码首先计算数据集的实例总数，然后创建一个数据字典，它的键值是最后一列的数值 。如果当前键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。最后，使用所有类标签的发生频率计算类别出现的概率。我们将用这个概率计算香农熵 ，统计所有类标签发生的次数。

2.3实验

目录：

用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
 
 
import trees
myDat, labels = trees.createDataSet()
print(myDat)
print(trees.calcShannonEnt(myDat))
 

运行结果：

熵越高，则混合的数据也越多，我们可以在数据集中添加更多的分类，观察熵是如何变化的。添加第三个名为maybe的分类，测试熵的变化：

myDat[0][-1]='maybe'
print(myDat)
print(trees.calcShannonEnt(myDat))

来看运行结果：

可以看到熵明显增大了，得到熵之后，我们就可以按照获取最大信息增益的方法划分数据集。

1.2 划分数据集

分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据集的熵，以便判断当前是否正确地划分了数据集。将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。

#按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
    """
    按照给定特征划分数据集
    :param dataSet:待划分的数据集
    :param axis:划分数据集的特征
    :param value:需要返回的特征的值
    """
    retDataSet = []                 # 创建一个新的列表对象
    for featVec in dataSet:
        if featVec[axis] == value:  # 将符合特征的数据抽取出来
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet
 

在函数的开始声明一个新列表对象。因为该函数代码在同一数据集上被调用多次，为了不修改原始数据集，创建一个新的列表对象 。数据集这个列表中的各个元素也是列表，要遍历数据集中的每个元素，一旦发现符合要求的值，则将其添加到新创建的列表中。

可以在简单样本数据上测试函数splitDataSet()。
 

myDat, labels = trees.createDataSet()
print(myDat)
print(trees.splitDataSet(myDat, 0, 1))  # 抽取，特征[0]值为1
print(trees.splitDataSet(myDat, 0, 0))  # 抽取，特征[0]值为0

运行结果如下，表明第1个特征是最好的用于划分数据集的特征。

如果我们按照第一个特征属性划分数据，也就是说第一个特征是1的放在一个组，第一个特征是0的放在另一个组，按照上述的方法划分数据集，第一个特征为1的海洋生物分组将有两个属于鱼类，一个属于非鱼类；另一个分组则全部属于非鱼类。

如果按照第二个特征分组，第一个海洋动物分组将有两个属于鱼类，两个属于非鱼类；另一个分组则只有一个非鱼类。

很明显就是第1个特征是最好的用于划分数据集的特征。
 

1.3 递归构建决策树

决策树的构建是一个递归过程。

工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。
第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

递归结束的条件是： 程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。

如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决定该叶子节点的分类。
 

def majorityCnt(classList):
    """
    多数表决
    :param classList: 分类名称的列表
    :return:返回出现次数最多的分类名称
    """
    classCount = {}         # 创建键值为 classList 中唯一值的数据字典
    for vote in classList:  # 字典对象存储了 classList 中每个类标签出现的频率
        if vote not in classCount.keys():
            classCount[vote] = 0    # 没有就添加
        classCount[vote] += 1       # 次数+1
    # 利用operator操作键值降序排序字典
    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]#stop splitting when all of the classes are equal    #所有的类标签完全相同，则直接返回该类标签
    if len(dataSet[0]) == 1: #使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组 
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)  #当前数据集选取的最好特征存储在变量 bestFeat 中
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}   #字典变量 myTree 存储了树的所有信息
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]       #复制了类标签，并将其存储在新列表变量 subLabels 
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree     

测试：

myDat, labels = trees.createDataSet()
print(myDat)
myTree = trees.createTree(myDat, labels)
print(myTree)

变量 myTree 包含了很多代表树结构信息的嵌套字典，从左边开始，第一个关键字 no surfacing 是第一个划分数据集的特征名称，该关键字的值也是另一个数据字典。第二个关键字是 no surfacing 特征划分的数据集，这些关键字的值是 no surfacing 节点的子节点。这些值可能是类标签（例如’flippers’），也可能是另一个数据字典。如果值是类标签，则该子节点是叶子节点；如果值是另一个数据字典，则子节点是一个判断节点，这种格式结构不断重复就构成了整棵树。这棵树包含了3个叶子节点以及2个判断节点。
 

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

2.1 Matplotlib 注解

字典的表示形式非常不易于理解，而且直接绘制图形也比较困难。现在使用Matplotlib库创建树形图。决策树的主要优点就是直观易于理解，如果不能将其直观地显示出来，就无法发挥其优势。

在Python中，我们可以使用Matplotlib库来绘制决策树的树形图。

#使用文本注解绘制树节点
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)
    
 
def createPlot():  #创建了一个新图形并清空绘图区，然后在绘图区上绘制两个代表不同类型的树节点，用这两个节点绘制树形图。
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    createPlot.ax1 = plt.subplot(111, frameon=False)
    plotNode('a decision node', (0.5, 0.1), (0.1, 0.5), decisionNode)
    plotNode('a leaf node', (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()
 

测试:

import treePlotter
 
treePlotter.createPlot()

2.2 构造注解树

虽然现在有x、y坐标，但是如何放置所有的树节点却是个问题。必须知道有多少个叶节点，以便可以正确确定x轴的长度；还需要知道树有多少层，以便可以正确确定y轴的高度。
这里定义两个新函数 getNumLeafs() 和 getTreeDepth() ，来获取叶节点的数目和树的层数

#获取叶节点的数目和树的层数
#遍历整棵树，累计叶子节点的个数，并返回该数值
def getNumLeafs(myTree):  
    numLeafs = 0
    firstStr = list(myTree)[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)[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

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

import treePlotter
 
print(treePlotter.retrieveTree(1))
myTree = treePlotter.retrieveTree(0)
print(treePlotter.getNumLeafs(myTree))
print(treePlotter.getTreeDepth(myTree))

调用 getNumLeafs()函数返回值为3，等于树0的叶子节点数；调用 getTreeDepths() 函数也能够正确返回树的层数。

现在可以绘制一棵完整的树。代码如下：

#在父子节点间填充文本信息
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):#if the first key tells you what feat was split on
    numLeafs = getNumLeafs(myTree)  #this determines the x width of this tree
    depth = getTreeDepth(myTree)
    firstSides = list(myTree.keys())
    firstStr = firstSides[0]  # 找到输入的第一个元素     #the text label for this node should be this
    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':#test to see if the nodes are dictonaires, if not they are leaf nodes   
            plotTree(secondDict[key],cntrPt,str(key))        #recursion
        else:   #it's a leaf node print the leaf node
            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
#if you do get a dictonary you know it's a tree, and the first element will be another dict
 
 
def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)    
    #createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses 
    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()

效果：

变更字典，重新绘制树形图。

myTree = treePlotter.retrieveTree(0)
myTree['no surfacing'][3]='maybe'
treePlotter.createPlot(myTree)

效果：

3决策树改进算法

3.1 改进ID3算法

下面另外举一个决策树构造实例，验证ID3算法的不足，以及做出新的改进。

数据：14天打球情况
特征：4种环境变化

1.基于天气的划分

2.基于温度的划分

3.基于湿度的划分

4.基于有风的划分

在历史数据中（14天）有9天打球，5天不打球，所以此时的熵应为：

4个特征逐一分析，先从outlook特征开始：

1.当outlook=sunny时，熵值为0.971

2.当outlook=overcast时，熵值为0

3.当outlook=rainy时，熵值为0.971

根据数据统计，outlook取值分别为sunny,overcast,rainy的概率分别为： 5/14, 4/14, 5/14

熵值计算：5/14 * 0.971 + 4/14 * 0 + 5/14 * 0.971 = 0.693

信息增益：系统的熵值从原始的0.940下降到了0.693，增益为0.247，信息增益最大，则outlook是根节点。
（gain(temperature)=0.029 gain(humidity)=0.152 gain(windy)=0.048）

同样的方式可以计算出其他特征的信息增益，那么我们选择最大的那个就可以啦，相当于是遍历了一遍特征，找出来根节点，然后再其余的中继续通过信息增益找节点！

现在我们就可以详细分析ID3算法的不足了，假设在outlook特征前面加一个ID特征，ID编号为1到14，在每个节点只有自己一个，那么在1号节点只有一种可能取值，那么熵值就是0，在2号节点只有一种可能取值，那么熵值也是0，以此类推，都是0，加到一起也是0，意味着总体熵值也为0，理想状态下分的特别好的情况才会为0，那么就会误把ID当做根节点，但是把ID当做根节点并没有任何意义。

改进：
C4.5算法：信息增益率（解决ID3问题，考虑自身熵）
ID的信息增益很大，但是对于ID里面的14个特征来说，取到每个特征的概率很小，都是1/14，此时可以看ID自身的熵值

                                

这个值非常大，现在假设信息增益为9，取最大值，但是信息增益率很小：

                        ​​​​​​​        ​​​​​​​        ​​​​​​​

这样就解决ID3算法的误差。

CART：使用GINI系数来当做衡量标准

 

4.剪枝策略

1、未剪枝存在的问题
决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即容易出现过拟合现象。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化，下面来探讨以下决策树剪枝算法。
 
2、剪枝的目的
决策树的剪枝是为了简化决策树模型，避免过拟合。
 
同样层数的决策树，叶结点的个数越多就越复杂；同样的叶结点个数的决策树，层数越多越复杂。
剪枝前相比于剪枝后，叶结点个数和层数只能更多或者其中一特征一样多，剪枝前必然更复杂。
层数越多，叶结点越多，分的越细致，对训练数据分的也越深，越容易过拟合，导致对测试数据预测时反而效果差，泛化能力差。
3、剪枝算法实现思路
剪去决策树模型中的一些子树或者叶结点，并将其上层的根结点作为新的叶结点，从而减少了叶结点甚至减少了层数，降低了决策树复杂度。
在决策树的建立过程中不断调节来达到最优，可以调节的条件有：
 
树的深度：在决策树建立过程中，发现深度超过指定的值，那么就不再分了。
叶子节点个数：在决策树建立过程中，发现叶子节点个数超过指定的值，那么就不再分了。
叶子节点样本数：如果某个叶子结点的个数已经低于指定的值，那么就不再分了。
信息增益量或Gini系数：计算信息增益量或Gini系数，如果小于指定的值，那就不再分了。

4.1预剪枝

预剪枝是在决策树生成过程中，对树进行剪枝，提前结束树的分支生长。其中的核心思想就是，在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。加入预剪枝后的决策树生成流程图如下：

优点：预剪枝可以有效降低过拟合现象，在决策树建立过程中进行调节，因此显著减少了训练时间和测试时间；预剪枝效率比后剪枝高。

缺点：预剪枝是通过限制一些建树的条件来实现的，这种方式容易导致欠拟合现象：模型训练的不够好。

4.2后剪枝：

决策树建立完成之后再进行的，根据以下公式：

C = gini(或信息增益)*sample(样本数) + a*叶子节点个数

C表示损失，C越大，损失越多。通过剪枝前后的损失对比，选择损失小的值，考虑是否剪枝。

a是自己调节的，a越大，叶子节点个数越多，损失越大。因此a值越大，偏向于叶子节点少的，a越小，偏向于叶子节点多的。

后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往由于预剪枝决策树，但是后剪枝过程是在生成完全决策树后进行的，并且要自下往上地对树中的非叶子节点逐一进行考察计算，因此训练时间的开销比为剪枝和预剪枝决策树都要大得多。

4.3剪枝实验代码：

4.3.1未剪枝：

import matplotlib.pyplot as plt 
 
decisionNodeStyle = dict(boxstyle = "sawtooth", fc = "0.8")
leafNodeStyle = {"boxstyle": "round4", "fc": "0.8"}
arrowArgs = {"arrowstyle": "<-"}
 
 
# 画节点
def plotNode(nodeText, centerPt, parentPt, nodeStyle):
    createPlot.ax1.annotate(nodeText, xy = parentPt, xycoords = "axes fraction", xytext = centerPt
                            , textcoords = "axes fraction", va = "center", ha="center", bbox = nodeStyle, arrowprops = arrowArgs)
 
 
# 添加箭头上的标注文字
def plotMidText(centerPt, parentPt, lineText):
    xMid = (centerPt[0] + parentPt[0]) / 2.0
    yMid = (centerPt[1] + parentPt[1]) / 2.0 
    createPlot.ax1.text(xMid, yMid, lineText)
    
    
# 画树
def plotTree(decisionTree, parentPt, parentValue):
    # 计算宽与高
    leafNum, treeDepth = getTreeSize(decisionTree) 
    # 在 1 * 1 的范围内画图，因此分母为 1
    # 每个叶节点之间的偏移量
    plotTree.xOff = plotTree.figSize / (plotTree.totalLeaf - 1)
    # 每一层的高度偏移量
    plotTree.yOff = plotTree.figSize / plotTree.totalDepth
    # 节点名称
    nodeName = list(decisionTree.keys())[0]
    # 根节点的起止点相同，可避免画线；如果是中间节点，则从当前叶节点的位置开始，
    #      然后加上本次子树的宽度的一半，则为决策节点的横向位置
    centerPt = (plotTree.x + (leafNum - 1) * plotTree.xOff / 2.0, plotTree.y)
    # 画出该决策节点
    plotNode(nodeName, centerPt, parentPt, decisionNodeStyle)
    # 标记本节点对应父节点的属性值
    plotMidText(centerPt, parentPt, parentValue)
    # 取本节点的属性值
    treeValue = decisionTree[nodeName]
    # 下一层各节点的高度
    plotTree.y = plotTree.y - plotTree.yOff
    # 绘制下一层
    for val in treeValue.keys():
        # 如果属性值对应的是字典，说明是子树，进行递归调用； 否则则为叶子节点
        if type(treeValue[val]) == dict:
            plotTree(treeValue[val], centerPt, str(val))
        else:
            plotNode(treeValue[val], (plotTree.x, plotTree.y), centerPt, leafNodeStyle)
            plotMidText((plotTree.x, plotTree.y), centerPt, str(val))
            # 移到下一个叶子节点
            plotTree.x = plotTree.x + plotTree.xOff
    # 递归完成后返回上一层
    plotTree.y = plotTree.y + plotTree.yOff
    
    
# 画出决策树
def createPlot(decisionTree):
    fig = plt.figure(1, facecolor = "white")
    fig.clf()
    axprops = {"xticks": [], "yticks": []}
    createPlot.ax1 = plt.subplot(111, frameon = False, **axprops)
    # 定义画图的图形尺寸
    plotTree.figSize = 1.5 
    # 初始化树的总大小
    plotTree.totalLeaf, plotTree.totalDepth = getTreeSize(decisionTree)
    # 叶子节点的初始位置x 和 根节点的初始层高度y
    plotTree.x = 0 
    plotTree.y = plotTree.figSize
    plotTree(decisionTree, (plotTree.figSize / 2.0, plotTree.y), "")
    plt.show()

结果：

4.2.2预剪枝：

创建预剪枝决策树：

def createTreePrePruning(dataTrain, labelTrain, dataTest, labelTest, names, method = 'id3'):
    trainData = np.asarray(dataTrain)
    labelTrain = np.asarray(labelTrain)
    testData = np.asarray(dataTest)
    labelTest = np.asarray(labelTest)
    names = np.asarray(names)
    # 如果结果为单一结果
    if len(set(labelTrain)) == 1: 
        return labelTrain[0] 
    # 如果没有待分类特征
    elif trainData.size == 0: 
        return voteLabel(labelTrain)
    # 其他情况则选取特征 
    bestFeat, bestEnt = bestFeature(dataTrain, labelTrain, method = method)
    # 取特征名称
    bestFeatName = names[bestFeat]
    # 从特征名称列表删除已取得特征名称
    names = np.delete(names, [bestFeat])
    # 根据最优特征进行分割
    dataTrainSet, labelTrainSet = splitFeatureData(dataTrain, labelTrain, bestFeat)
 
    # 预剪枝评估
    # 划分前的分类标签
    labelTrainLabelPre = voteLabel(labelTrain)
    labelTrainRatioPre = equalNums(labelTrain, labelTrainLabelPre) / labelTrain.size
    # 划分后的精度计算 
    if dataTest is not None: 
        dataTestSet, labelTestSet = splitFeatureData(dataTest, labelTest, bestFeat)
        # 划分前的测试标签正确比例
        labelTestRatioPre = equalNums(labelTest, labelTrainLabelPre) / labelTest.size
        # 划分后 每个特征值的分类标签正确的数量
        labelTrainEqNumPost = 0
        for val in labelTrainSet.keys():
            labelTrainEqNumPost += equalNums(labelTestSet.get(val), voteLabel(labelTrainSet.get(val))) + 0.0
        # 划分后 正确的比例
        labelTestRatioPost = labelTrainEqNumPost / labelTest.size 
    
    # 如果没有评估数据 但划分前的精度等于最小值0.5 则继续划分
    if dataTest is None and labelTrainRatioPre == 0.5:
        decisionTree = {bestFeatName: {}}
        for featValue in dataTrainSet.keys():
            decisionTree[bestFeatName][featValue] = createTreePrePruning(dataTrainSet.get(featValue), labelTrainSet.get(featValue)
                                      , None, None, names, method)
    elif dataTest is None:
        return labelTrainLabelPre 
    # 如果划分后的精度相比划分前的精度下降, 则直接作为叶子节点返回
    elif labelTestRatioPost < labelTestRatioPre:
        return labelTrainLabelPre
    else :
        # 根据选取的特征名称创建树节点
        decisionTree = {bestFeatName: {}}
        # 对最优特征的每个特征值所分的数据子集进行计算
        for featValue in dataTrainSet.keys():
            decisionTree[bestFeatName][featValue] = createTreePrePruning(dataTrainSet.get(featValue), labelTrainSet.get(featValue)
                                      , dataTestSet.get(featValue), labelTestSet.get(featValue)
                                      , names, method)
    return decisionTree 

测试：

xgDataTrain, xgLabelTrain, xgDataTest, xgLabelTest = splitXgData20(xgData, xgLabel)
# 生成不剪枝的树
xgTreeTrain = createTree(xgDataTrain, xgLabelTrain, xgName, method = 'id3')
# 生成预剪枝的树
xgTreePrePruning = createTreePrePruning(xgDataTrain, xgLabelTrain, xgDataTest, xgLabelTest, xgName, method = 'id3')
# 画剪枝前的树
print("剪枝前的树")
createPlot(xgTreeTrain)
# 画剪枝后的树
print("剪枝后的树")
createPlot(xgTreePrePruning)

4.2.3后剪枝：

# 创建决策树 带预划分标签
def createTreeWithLabel(data, labels, names, method = 'id3'):
    data = np.asarray(data)
    labels = np.asarray(labels)
    names = np.asarray(names)
    # 如果不划分的标签为
    votedLabel = voteLabel(labels)
    # 如果结果为单一结果
    if len(set(labels)) == 1: 
        return votedLabel 
    # 如果没有待分类特征
    elif data.size == 0: 
        return votedLabel
    # 其他情况则选取特征 
    bestFeat, bestEnt = bestFeature(data, labels, method = method)
    # 取特征名称
    bestFeatName = names[bestFeat]
    # 从特征名称列表删除已取得特征名称
    names = np.delete(names, [bestFeat])
    # 根据选取的特征名称创建树节点 划分前的标签votedPreDivisionLabel=_vpdl
    decisionTree = {bestFeatName: {"_vpdl": votedLabel}}
    # 根据最优特征进行分割
    dataSet, labelSet = splitFeatureData(data, labels, bestFeat)
    # 对最优特征的每个特征值所分的数据子集进行计算
    for featValue in dataSet.keys():
        decisionTree[bestFeatName][featValue] = createTreeWithLabel(dataSet.get(featValue), labelSet.get(featValue), names, method)
    return decisionTree 
 
 
# 将带预划分标签的tree转化为常规的tree
# 函数中进行的copy操作，原因见有道笔记 【YL20190621】关于Python中字典存储修改的思考
def convertTree(labeledTree):
    labeledTreeNew = labeledTree.copy()
    nodeName = list(labeledTree.keys())[0]
    labeledTreeNew[nodeName] = labeledTree[nodeName].copy()
    for val in list(labeledTree[nodeName].keys()):
        if val == "_vpdl": 
            labeledTreeNew[nodeName].pop(val)
        elif type(labeledTree[nodeName][val]) == dict:
            labeledTreeNew[nodeName][val] = convertTree(labeledTree[nodeName][val])
    return labeledTreeNew
 
 
# 后剪枝 训练完成后决策节点进行替换评估  这里可以直接对xgTreeTrain进行操作
def treePostPruning(labeledTree, dataTest, labelTest, names):
    newTree = labeledTree.copy()
    dataTest = np.asarray(dataTest)
    labelTest = np.asarray(labelTest)
    names = np.asarray(names)
    # 取决策节点的名称 即特征的名称
    featName = list(labeledTree.keys())[0]
    # print("\n当前节点：" + featName)
    # 取特征的列
    featCol = np.argwhere(names==featName)[0][0]
    names = np.delete(names, [featCol])
    # print("当前节点划分的数据维度：" + str(names))
    # print("当前节点划分的数据：" )
    # print(dataTest)
    # print(labelTest)
    # 该特征下所有值的字典
    newTree[featName] = labeledTree[featName].copy()
    featValueDict = newTree[featName]
    featPreLabel = featValueDict.pop("_vpdl")
    # print("当前节点预划分标签：" + featPreLabel)
    # 是否为子树的标记
    subTreeFlag = 0
    # 分割测试数据 如果有数据 则进行测试或递归调用  np的array我不知道怎么判断是否None, 用is None是错的
    dataFlag = 1 if sum(dataTest.shape) > 0 else 0
    if dataFlag == 1:
        # print("当前节点有划分数据！")
        dataTestSet, labelTestSet = splitFeatureData(dataTest, labelTest, featCol)
    for featValue in featValueDict.keys():
        # print("当前节点属性 {0} 的子节点：{1}".format(featValue ,str(featValueDict[featValue])))
        if dataFlag == 1 and type(featValueDict[featValue]) == dict:
            subTreeFlag = 1 
            # 如果是子树则递归
            newTree[featName][featValue] = treePostPruning(featValueDict[featValue], dataTestSet.get(featValue), labelTestSet.get(featValue), names)
            # 如果递归后为叶子 则后续进行评估
            if type(featValueDict[featValue]) != dict:
                subTreeFlag = 0 
            
        # 如果没有数据  则转换子树
        if dataFlag == 0 and type(featValueDict[featValue]) == dict: 
            subTreeFlag = 1 
            # print("当前节点无划分数据！直接转换树："+str(featValueDict[featValue]))
            newTree[featName][featValue] = convertTree(featValueDict[featValue])
            # print("转换结果：" + str(convertTree(featValueDict[featValue])))
    # 如果全为叶子节点， 评估需要划分前的标签，这里思考两种方法，
    #     一是，不改变原来的训练函数，评估时使用训练数据对划分前的节点标签重新打标
    #     二是，改进训练函数，在训练的同时为每个节点增加划分前的标签，这样可以保证评估时只使用测试数据，避免再次使用大量的训练数据
    #     这里考虑第二种方法 写新的函数 createTreeWithLabel，当然也可以修改createTree来添加参数实现
    if subTreeFlag == 0:
        ratioPreDivision = equalNums(labelTest, featPreLabel) / labelTest.size
        equalNum = 0
        for val in labelTestSet.keys():
            equalNum += equalNums(labelTestSet[val], featValueDict[val])
        ratioAfterDivision = equalNum / labelTest.size 
        # print("当前节点预划分标签的准确率：" + str(ratioPreDivision))
        # print("当前节点划分后的准确率：" + str(ratioAfterDivision))
        # 如果划分后的测试数据准确率低于划分前的，则划分无效，进行剪枝，即使节点等于预划分标签
        # 注意这里取的是小于，如果有需要 也可以取 小于等于
        if ratioAfterDivision < ratioPreDivision:
            newTree = featPreLabel 
    return newTree

五 结论：

5.1报错：

发生异常: UnboundLocalError local variable 'classLabel' referenced before assignment File 

代码中存在一个局部变量 classLabel 在被赋值之前被引用的问题。这通常是因为在某些条件下没有为 classLabel 赋初值，但在后续的代码中尝试引用它。

解决：需要确保 classLabel 在所有可能的条件分支中都被赋值，或者在函数开始时为它设置一个默认值。

  classLabel = None  # 添加默认值