机器学习

#机器学习| 来源: 网络整理| 查看: 265

此篇博客对决策树的剪枝做展开了解，对决策树还不了解的读者可以先读我的上一篇博客机器学习-决策树（Decision Tree）基础篇https://blog.csdn.net/m0_52053228/article/details/127839854?spm=1001.2014.3001.5501

此篇博客我将拿西瓜书中的数据以及我自己的数据来做决策树的剪枝。

一、剪枝

1-1、什么是过拟合

1-2、基本策略

二、预剪枝

2-1、西瓜书数据2.0实现预剪枝

2-2、用自己的数据实现预剪枝

三、后剪枝

3-1、西瓜书数据2.0实现后剪枝

3-2、用自己的数据实现后剪枝

四、整体代码

五、总结

一、剪枝

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。

1-1、什么是过拟合

过拟合（over-fitting）是指模型在训练集上表现很好，到了验证和测试阶段就很差，即模型的泛化能力很差。

举个例子讲就是当我需要建立好一个模型之后，比如是识别一只狗狗的模型，我需要对这个模型进行训练。恰好，我训练样本中的所有训练图片都是二哈，那么经过多次迭代训练之后，模型训练好了，并且在训练集中表现得很好，给定一个二哈的测试样本都能正确的预测结果。基本上二哈身上的所有特点都涵括进去，那么问题来了！假如我的测试样本是一只金毛呢？将一只金毛的测试样本放进这个识别狗狗的模型中，很有可能模型最后输出的结果不是一条狗（因为这个模型基本上是按照二哈的特征去打造的，这个模型太贴合二哈，对二哈的识别率非常高，反而导致泛化能力比较差）。所以这样就造成了模型过拟合，虽然在训练集上表现得很好，但是在测试集中表现得恰好相反，在性能的角度上讲就是协方差过大（variance is large），同样在测试集上的损失函数（cost function）会表现得很大。

1-2、基本策略

决策树剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（postpruning）。

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点得划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。二、预剪枝 2-1、西瓜书数据2.0实现预剪枝

我们先拿西瓜书的数据来看一下预剪枝是如何进行的。

下面是西瓜书中给出的数据集以及根据信息增构造出的一颗未剪枝的决策树

因为是预剪枝，所以要判断是否应该进行这个划分。

判断的标准就是看划分前后的泛华性能是否有提升，也就是如果划分后泛华性能有提升，则划分；否则，不划分。

下面来看看是否要用脐部进行划分。

划分前：所有样例集中在根结点，若不进行划分，该结点将被标记为叶结点，其类别标记为训练样例数最多的类别，假设我们将这个叶结点标记为“好瓜”。用验证集对这个单结点决策树进行评估，则编号为{4，5，8}的样例被分类正确，另外4个样例分类错误，于是，验证集精度为

$\frac{3}{7}=42.9%$

划分后：图4.6中的结点②、③、④分别包含编号为{1，2，3，14}、{6，7，15，17}、{10，16}的训练样例，因此这3个结点分别被标记为叶结点“好瓜”、“好瓜”、“坏瓜”。此时，验证集中编号为{4，5，8，11，12}的样例被分类正确，验证集精度为 $\frac{5}{7}=71.4%$

$71.4% 42.9%$ ，即划分后精度大于划分前精度，于是用“脐部”进行划分得以确定。

接下来，决策树算法对结点②进行划分，再次使用信息增益挑选出值最大的那个特征，这里我就不算了，计算方法和上面类似。以此类推，就可以得出预剪枝之后的决策树。

下面我们通过python来实现预剪枝

# 创建预剪枝决策树 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

生成决策树并通过matplotlib可视化

matplotlib相关的函数与上一篇博客中的一样，这里就不再展现了

# 将西瓜数据2.0分割为测试集和训练集 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)

下图为剪枝前的树：

下图为剪枝后的树：

2-2、用自己的数据实现预剪枝

我们还用之前是否申请生源地贷款的数据来做剪枝处理

划分数据、生成树、并可视化：

#将自己的数据分割为测试集和训练集 myDataTrain, myLabelTrain, myDataTest, myLabelTest = splitMyData(myData,myLabel) # 生成不剪枝的树 myTreeTrain = createTree(myDataTrain, myLabelTrain, myName, method='id3') # 生成预剪枝的树 myTreePrePruning = createTreePrePruning(myDataTrain, myLabelTrain, myDataTest, myLabelTest, myName, method='id3') # 画剪枝前的树 #print("剪枝前的树") createPlot(myTreeTrain) # 画剪枝后的树 #print("剪枝后的树") createPlot(myTreePrePruning)

剪枝前的树：

剪枝后的树：

三、后剪枝 3-1、西瓜书数据2.0实现后剪枝

后剪枝就是先构造一颗完整的决策树，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点。前面已经说过了，使用前面给出的训练集会生成一颗（未剪枝）决策树：

后剪枝首先考虑上图中的结点⑥。若将其领衔的分支剪除，则相当于把⑥替换为叶结点。替换后的叶结点包含编号为{7，15}的训练样本，于是，该叶结点的类别标记为“好瓜”，此时决策树的验证集精度提高至57.1%。于是，后剪枝策略决定剪枝，如下图所示。

以此类推，就可以构造出后剪枝的决策树。

下面我们通过python来实现后剪枝

# 创建决策树带预划分标签 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

生成树并可视化

xgTreeBeforePostPruning = createTreeWithLabel(xgDataTrain, xgLabelTrain, xgName, method='id3') #print(xgTreeBeforePostPruning) xgTreePostPruning = treePostPruning(xgTreeBeforePostPruning, xgDataTest, xgLabelTest, xgName) createPlot(convertTree(xgTreeBeforePostPruning)) createPlot(xgTreePostPruning)

剪枝前的树：

剪枝后的树：

3-2、用自己的数据实现后剪枝 myTreeBeforePostPruning = createTreeWithLabel(myDataTrain, myLabelTrain, myName, method='id3') #print(myTreeBeforePostPruning) myTreePostPruning = treePostPruning(myTreeBeforePostPruning, myDataTest, myLabelTest, myName) createPlot(convertTree(myTreeBeforePostPruning)) createPlot(myTreePostPruning)

剪枝前的树：

剪枝后的树：

四、整体代码 import math #导入一系列数学函数 import numpy as np import pandas as pd import matplotlib.pyplot as plt from pylab import * decisionNodeStyle = dict(boxstyle = "sawtooth", fc = "0.8") leafNodeStyle = dict(boxstyle = "round4", fc = "0.8") arrowArgs = dict(arrowstyle="

【本文地址】

公司简介

联系我们