机器学习（三）决策树对连续值数据的预剪枝及后剪枝（Python代码）_机器学习后剪枝python

---

参考：
https://blog.csdn.net/ylhlly/article/details/93213633
https://zhuanlan.zhihu.com/p/267368825

一、前言

为什么要进行剪枝？

当我们的数据集样本量很大、每个特征的取值很多时，生成决策树的代价就会很大。不仅如此，虽然一个完整的决策树对训练数据的预测非常准，但这会造成对训练数据的过拟合，造成模型的泛化性能（预测除训练集意外数据的能力）降低。因此，本节我们将引入剪枝的概念。

二、基本概念

1.剪枝

  剪枝就是将决策树下的某个子树的根节点作为叶结点，并且将该子树根节点以下的点全部删除。

  剪枝可以使决策树的节点数减少，减小决策树过拟合的可能，提高决策树的泛化性能。

  剪枝分为预剪枝与后剪枝。

2.预剪枝

2.1 介绍

  预剪枝其实就是在生成决策树的过程中边生成决策树边剪枝。

  预剪枝在构建决策树的过程中，计算以下两个精确度 :
  1、如果不划分样本集合此时模型在验证集上的精确度；
  2、如果划分样本集合此时模型在验证集上的精确度。

  如果划分后的精确度更高，说明此时划分样本集对整体的泛化性能的提高是有益的，那此时就选择划分样本。

  如果划分后的精确度更低或不变，说明划分后此时泛化性能不变或变差，此时就不划分样本，将该节点作为叶结点。

  注意：本次划分样本集后的泛化性能变差不代表在该划分方法的基础下继续进行划分样本集后的泛化性能差
  （本次虽然造成泛化性能变差，但有可能该次的样本划分对下一次的某个特征的划分有帮助）

2.2 优点

  在生成决策树的过程中剪枝，减少了很多划分样本集的过程，使得计算量较小。

2.3 缺点

  如上面注意所说的一样，仅仅根据当前划分样本集造成泛化能力下降就将该节点作为叶结点、不再对该节点下的样本集进行划分，可能会造成最终的泛化能力变差，导致欠拟合。

3.后剪枝

3.1 介绍

  后剪枝其实就是生成决策树后，自底向上循环每个子树进行剪枝。

  后剪枝在构建决策树的过程中，自底向上遍历每个子树，计算以下两个精确度 :
  1、留下该子树的精确度；
  2、将该子树作为叶子节点的精确度。

  如果将该子树作为叶结点的精确度更高，说明此时的操作对整体的泛化性能的提高是有益的，那此时就选择该操作。

  反之，则不对该子树进行操作。

3.2 优点

  在生成完整的决策树以后再对决策树进行剪枝操作，由于后剪枝的条件是当剪枝后的精确度高于不剪枝的精确度，而当前的完整的决策树已经达到一个较高的精确度，剪枝后的决策树不会欠拟合。

3.3缺点

  不仅要生成完整的决策树，还要对决策树当中的每个子树进行遍历，检测是否需要剪枝，使得计算量大大增加。

---

三、数据集准备

本次数据集比上一篇博客中的数据集新增了7个数据。
数据集以集美大学为背景，数据集中的前四列代表从宿舍至该楼的时间，单位为分钟，最后一列为对应的交通方式，共有21个数据以csv文件方式存储，其中前14个作为训练集，后7个作为验证集。

四、代码实现

1.创建决策树

由于本数据的特征都为连续属性，采取二分法对数据集进行划分。

本篇文章的剪枝代码在上一篇的创建决策树的代码上进行修改。

本文只贴出与上一篇博客中有差异的代码，该段函数中包含不进行剪枝操作、进行预剪枝以及进行后剪枝的代码。

创建决策树：

def createTree(trainDataset, testDataset, labels, method = None):
    '''
    method 为 [None, 'pre', 'post']中的一种
    None为不使用剪枝操作，
    'pre'为使用预剪枝操作，
    'post'为使用后剪枝操作，
    
    递归建树
    1.获取最佳特征索引bestIndex以及最佳划分点bestSplitValue
    2.根据bestIndex和bestSplitValue将训练集与测试集划分为左右两个子集subDataset1和subDataset2
    3.如选择预剪枝，则每次衡量划分子集前的精确度和划分子集后的精确度，如有提高才生成子树；
    4.如选择后剪枝，则先生成子树，再衡量去除每个子树是否带来精确度的提高，如有提高则去除子树；
    
    返回值：
    1.method为None或'pre'时，返回myTree
    2.method为'post'时，返回myTree与correct
    
    注意：
    这个correct是指由训练集划分出的子树对测试集进行预测，一共预测对多少个样本的个数。
    
    '''
    # 获取训练集与测试集当中的所有类别
    trainClassList = [example[-1] for example in trainDataset] 
    testClassList = [example[-1] for example in testDataset]
    
    # 若训练集中只有一个类时，有两种情况：
    # 1.如果当前采用后剪枝，则返回predict_class与correct
    # 2.如果不剪枝或采用预剪枝，则返回predict_class
    if trainClassList.count(trainClassList[0]) == len(trainClassList):
        
        # 当前子树预测类别
        predict_class = trainClassList[0]
        # 当前预测类别预测测试集对的个数
        correct = testClassList.count(predict_class)
        
        if method == 'post':
            return predict_class, correct
        else: 
            return predict_class
        
    # 若训练集最后只剩下类别，有两种情况：
    # 1.如果当前采用后剪枝，则返回predict_class与correct
    # 2.如果不剪枝或采用预剪枝，则返回predict_class
    if len(trainDataset[0]) == 1: 
        
        # 当前子树预测类别
        predict_class = majorityCnt(trainClassList)
        # 当前预测类别预测测试集对的个数
        correct = testClassList.count(predict_class)
        
        if method == 'post':
            return predict_class, correct
        else: 
            return predict_class
        
    # 找到当前情况下使训练集信息增益最大的特征的索引，以及最佳的划分点值
    bestIndex, bestSplitValue = chooseBestFeatureToSplit(trainDataset) 
    # 最优特征的名字
    bestFeature = labels[bestIndex]
    # 创建决策树 
    myTree = {bestFeature:{}}
    # 从labels中删除最优特征
    del(labels[bestIndex])
    
    # 使用最优特征索引与最佳参数划分出训练集与测试集的两个子集
    trainSubDataset1, trainSubDataset2 = splitDataset(trainDataset,bestIndex
                                                      ,bestSplitValue)
    testSubDataset1, testSubDataset2 = splitDataset(testDataset,bestIndex
                                                    ,bestSplitValue)
    # 获取训练集与测试集中子集1与子集2的所有类别
    trainSubClassList1 = [example[-1] for example in trainSubDataset1] 
    trainSubClassList2 = [example[-1] for example in trainSubDataset2] 
    testSubClassList1 = [example[-1] for example in testSubDataset1] 
    testSubClassList2 = [example[-1] for example in testSubDataset2] 
    if method == 'pre':
        
        # 划分子集前：
        # 预测类别为当前训练集中最多的类别
        predict_class_pre = majorityCnt(trainClassList)
        # 使用训练集中最多的类别预测当前未划分的测试集的准确度
        precision_pre = testClassList.count(predict_class_pre)/len(testClassList)
        
        # 划分子集后：
        # 子集1的预测类别为当前训练子集1中最多的类别，子集2同理
        predict_class_post1 = majorityCnt(trainSubClassList1)
        predict_class_post2 = majorityCnt(trainSubClassList2)
        # 使用这两个类别分别预测测试集的子集1与子集2的正确总数
        correct1 = testSubClassList1.count(predict_class_post1)
        correct2 = testSubClassList2.count(predict_class_post2)
        totalCorrect = correct1 + correct2
        # 划分子集后的准确率
        precision_post = totalCorrect / len(testClassList)
        
        # 如果划分子集后的准确率比划分前更高，则划分子集，否则返回当前样本中最多的类别
        if precision_post > precision_pre:
            myTree[bestFeature]["<="+str(bestSplitValue)] = createTree(trainSubDataset1,testSubDataset1, labels, method = 'pre')
            myTree[bestFeature][">"+str(bestSplitValue)] = createTree(trainSubDataset2,testSubDataset2, labels, method = 'pre')
        else:
            return predict_class_pre
    elif method == 'post':
        
        # 剪枝前：
        # 生成leftTree与rightTree并得到该子树预测测试集对的数量correct1与correct2
        leftTree, correct1 = createTree(trainSubDataset1,testSubDataset1, labels, 
                                        method = 'post')
        rightTree, correct2 = createTree(trainSubDataset2,testSubDataset2, labels, 
                                         method = 'post')
        totalCorrect = correct1 + correct2
        # 剪枝前的准确率
        precision_pre = totalCorrect / len(testClassList)
        
        # 剪枝后
        # 预测类别为当前训练集中最多的类别
        predict_class_post = majorityCnt(trainClassList)
        # 使用训练集中最多的类别预测剪枝后的测试集的准确度
        precision_post = testClassList.count(predict_class_post)/len(testClassList)
        
        # 如果剪枝后的精确度比剪枝前更高，则进行剪枝，
        # 返回剪枝后的预测类别predict_class_post与剪枝后预测对的个数correct_post；
        # 否则返回剪枝前的树myTree以及剪枝前预测正确的个数totalCorrect
        if precision_post > precision_pre:
            correct_post = testClassList.count(predict_class_pre)
            return predict_class_pre, correct_post
        else:
            myTree[bestFeature]["<="+str(bestSplitValue)] = leftTree
            myTree[bestFeature][">"+str(bestSplitValue)] = rightTree
            return myTree, totalCorrect
            
    elif method == None:
        myTree[bestFeature]["<="+str(bestSplitValue)] = createTree(trainSubDataset1,testSubDataset1, labels, method = None)
        myTree[bestFeature][">"+str(bestSplitValue)] = createTree(trainSubDataset2,testSubDataset2, labels, method = None)
    return myTree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

2.决策树绘画

与上一节博客中的一样，此处就不贴出了。

3.完整代码链接

链接：https://pan.baidu.com/s/13ySeH9oeT0VXVKDYQruXQg?pwd=tnv9
提取码：tnv9

五、结果

使用剪枝前：

使用预剪枝后：

使用后剪枝后：

结果分析：
关于预剪枝：
  原本划分数据集时使用了四个特征，预剪枝后只使用了一个特征。
  这是因为预剪枝的特性 ：只要当前划分子集之后没有带来精度的提高，就会停止划分当前的节点，将该节点作为叶结点。
  而该数据刚刚好使用了“禹州楼”这一特征进行划分出左右两个子集之后，左右两个子集分别再进行划分都没有再带来精度上的提升，故决策树停止生长。

关于后剪枝：
  后剪枝对先前生成的决策树没有影响。
  这是因为后剪枝的特性 ：只要当前剪枝之后没有带来精度的提高，就不进行剪枝。
  而该数据先前生成的决策树刚刚好每一个子树剪枝之后都不会带来精度上的提升，故决策树没有进行任何剪枝操作。

不足：
  可以对比ID3算法与其他决策树算法的区别，还可以对比决策树算法与KNN算法的区别，但由于时间问题，目前没有时间做比较。

---