devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

决策树的剪枝_决策树剪枝

作者：你好赵伟 | 2024-03-28 20:07:25

赞

踩

决策树剪枝

目录

一、为什么要剪枝

二、剪枝的策略

1、预剪枝（pre-pruning）

2、后剪枝（post-pruning）

三、代码实现

1、收集、准备数据：

2、分析数据：

3、预剪枝及测试：

 4、后剪枝及测试：

四、总结

一、为什么要剪枝

剪枝（pruning）的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵树的分支过多，也就导致了过拟合。

可通过“剪枝”来一定程度避免因决策分支过多，以致于把训练集 自身的一些特点当做所有数据都具有的一般性质而导致的过拟合。

二、剪枝的策略

决策树的剪枝策略最基本的有两种：预剪枝（pre-pruning）和后剪枝（post-pruning）

1、预剪枝（pre-pruning）

预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
数据集：

 预剪枝：

 

预剪枝的优缺点
•优点
        –降低过拟合风险
        –显著减少训练时间和测试时间开销。
•缺点
        –欠拟合风险 ：有些分支的当前划分虽然不能提升泛化性能，但 在其基础上进行的后续划分却有可能显著提高性能。预剪枝基于 “ 贪心 ”本质禁止这些分支展开，带来了欠拟合风险。

2、后剪枝（post-pruning）

后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点。

 

后剪枝处理：

 

 

 

 

后剪枝的优缺点
•优点
        后剪枝比预剪枝保留了更多的分支， 欠拟合风险小 ， 泛化性能往往优于预剪枝决策树
•缺点
        训练时间开销大 ：后剪枝过程是在生成完全决策树 之后进行的，需要自底向上对所有非叶结点逐一计算

三、代码实现

1、收集、准备数据：

这里采用上面西瓜2.0的数据集：

  1. import math
  2. import numpy as np 
  3.  
  4. def createMyData():
  5.     data = np.array([['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑']
  6.                     , ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑']
  7.                     , ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑']
  8.                     , ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑']
  9.                     , ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑']
  10.                     , ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘']
  11.                     , ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘']
  12.                     , ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑']
  13.                     , ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑']
  14.                     , ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘']
  15.                     , ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑']
  16.                     , ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘']
  17.                     , ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑']
  18.                     , ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑']
  19.                     , ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘']
  20.                     , ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑']
  21.                     , ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑']])
  22.     label = np.array(['是', '是', '是', '是', '是', '是', '是', '是', '否', '否', '否', '否', '否', '否', '否', '否', '否'])
  23.     name = np.array(['色泽', '根蒂', '敲声', '纹理', '脐部', '触感'])
  24.     return data, label, name
  25.  
  26. def splitMyData20(myData, myLabel):
  27.     myDataTrain = myData[[0, 1, 2, 5, 6, 9, 13, 14, 15, 16],:]
  28.     myDataTest = myData[[3, 4, 7, 8, 10, 11, 12],:]
  29.     myLabelTrain = myLabel[[0, 1, 2, 5, 6, 9, 13, 14, 15, 16]]
  30.     myLabelTest = myLabel[[3, 4, 7, 8, 10, 11, 12]]
  31.     return myDataTrain, myLabelTrain, myDataTest, myLabelTest

2、分析数据：

  1. equalNums = lambda x,y: 0 if x is None else x[x==y].size
  2.  
  3. # 定义计算信息熵的函数
  4. def singleEntropy(x):
  5.     x = np.asarray(x)
  6.     xValues = set(x)
  7.     entropy = 0
  8.     for xValue in xValues:
  9.         p = equalNums(x, xValue) / x.size 
  10.         entropy -= p * math.log(p, 2)
  11.     return entropy
  12.     
  13.     
  14. # 定义计算条件信息熵的函数
  15. def conditionnalEntropy(feature, y):
  16.     feature = np.asarray(feature)
  17.     y = np.asarray(y)
  18.     featureValues = set(feature)
  19.     entropy = 0
  20.     for feat in featureValues:
  21.         p = equalNums(feature, feat) / feature.size 
  22.         entropy += p * singleEntropy(y[feature == feat])
  23.     return entropy
  24.     
  25.     
  26. # 定义信息增益
  27. def infoGain(feature, y):
  28.     return singleEntropy(y) - conditionnalEntropy(feature, y)
  29.  
  30.  
  31. # 定义信息增益率
  32. def infoGainRatio(feature, y):
  33.     return 0 if singleEntropy(feature) == 0 else infoGain(feature, y) / singleEntropy(feature)
  34.  
  1. # 特征选取
  2. def bestFeature(data, labels, method = 'id3'):
  3.     assert method in ['id3', 'c45'], "method 须为id3或c45"
  4.     data = np.asarray(data)
  5.     labels = np.asarray(labels)
  6.     # 根据输入的method选取 评估特征的方法：id3 -> 信息增益; c45 -> 信息增益率
  7.     def calcEnt(feature, labels):
  8.         if method == 'id3':
  9.             return infoGain(feature, labels)
  10.         elif method == 'c45' :
  11.             return infoGainRatio(feature, labels)
  12.     featureNum = data.shape[1]
  13.     bestEnt = 0 
  14.     bestFeat = -1
  15.     for feature in range(featureNum):
  16.         ent = calcEnt(data[:, feature], labels)
  17.         if ent >= bestEnt:
  18.             bestEnt = ent 
  19.             bestFeat = feature
  20.     return bestFeat, bestEnt 
  21.  
  22.  
  23. # 根据特征及特征值分割原数据集 
  24. def splitFeatureData(data, labels, feature):
  25.     features = np.asarray(data)[:,feature]
  26.     data = np.delete(np.asarray(data), feature, axis = 1)
  27.     labels = np.asarray(labels)
  28.     
  29.     uniqFeatures = set(features)
  30.     dataSet = {}
  31.     labelSet = {}
  32.     for feat in uniqFeatures:
  33.         dataSet[feat] = data[features == feat]
  34.         labelSet[feat] = labels[features == feat]
  35.     return dataSet, labelSet
  36.     
  37.     
  38. # 多数投票 
  39. def voteLabel(labels):
  40.     uniqLabels = list(set(labels))
  41.     labels = np.asarray(labels)
  42.  
  43.     finalLabel = 0
  44.     labelNum = []
  45.     for label in uniqLabels:
  46.         labelNum.append(equalNums(labels, label))
  47.     return uniqLabels[labelNum.index(max(labelNum))]
  48.  
  49.  
  50. # 创建决策树
  51. def createTree(data, labels, names, method = 'id3'):
  52.     data = np.asarray(data)
  53.     labels = np.asarray(labels)
  54.     names = np.asarray(names)
  55.     if len(set(labels)) == 1: 
  56.         return labels[0] 
  57.     elif data.size == 0: 
  58.         return voteLabel(labels)
  59.     bestFeat, bestEnt = bestFeature(data, labels, method = method)
  60.     bestFeatName = names[bestFeat]
  61.     names = np.delete(names, [bestFeat])
  62.     decisionTree = {bestFeatName: {}}
  63.     dataSet, labelSet = splitFeatureData(data, labels, bestFeat)
  64.     for featValue in dataSet.keys():
  65.         decisionTree[bestFeatName][featValue] = createTree(dataSet.get(featValue), labelSet.get(featValue), names, method)
  66.     return decisionTree 
  67.  
  68.  
  69. # 统计叶子节点数和树深度
  70. def getTreeSize(decisionTree):
  71.     nodeName = list(decisionTree.keys())[0]
  72.     nodeValue = decisionTree[nodeName]
  73.     leafNum = 0 
  74.     treeDepth = 0 
  75.     leafDepth = 0
  76.     for val in nodeValue.keys():
  77.         if type(nodeValue[val]) == dict:   
  78.             leafNum += getTreeSize(nodeValue[val])[0]   
  79.             leafDepth = 1 + getTreeSize(nodeValue[val])[1] 
  80.         else :
  81.             leafNum += 1 
  82.             leafDepth = 1 
  83.         treeDepth = max(treeDepth, leafDepth)
  84.     return leafNum, treeDepth 
  85.  
  86.  
  87. # 使用模型对其他数据分类
  88. def dtClassify(decisionTree, rowData, names):
  89.     names = list(names)
  90.     feature = list(decisionTree.keys())[0]
  91.     featDict = decisionTree[feature]
  92.     feat = names.index(feature)
  93.     featVal = rowData[feat]
  94.     if featVal in featDict.keys():
  95.         if type(featDict[featVal]) == dict:
  96.             classLabel = dtClassify(featDict[featVal], rowData, names)
  97.         else:
  98.             classLabel = featDict[featVal] 
  99.     return classLabel

使用Matplotlib注解绘制树形图：

  1. import matplotlib.pyplot as plt
  2.  
  3. #定义文本框和箭头格式
  4. decisionNode=dict(boxstyle="sawtooth",fc='0.8')
  5. leafNode=dict(boxstyle="round4",fc='0.8')
  6. arrow_args=dict(arrowstyle="<-")
  7.  
  8. #绘制带箭头的注释
  9. def plotNode(nodeTxt,centerPt,parentPt,nodeType):
  10.     createPlot.axl.annotate(nodeTxt,xy=parentPt,xycoords='axes fraction',
  11.     xytext=centerPt,
  12.     textcoords='axes fraction',
  13.     va="center",ha="center",bbox=nodeType,arrowprops=arrow_args)
  14.  
  15. #获取叶节点的数目和树的层数
  16. def getNumLeafs(myTree):
  17.     numLeafs=0
  18. #  firstStr=myTree.keys()[0]
  19.     firstStr=list(myTree.keys())[0]
  20.     secondDict=myTree[firstStr]
  21.     for key in secondDict.keys():
  22.         if type(secondDict[key]).__name__=='dict':
  23.             numLeafs+=getNumLeafs(secondDict[key])
  24.         else:
  25.             numLeafs+=1
  26.     return numLeafs
  27.  
  28. def getTreeDepth(myTree):
  29.     maxDepth=0
  30.     firstStr=list(myTree.keys())[0]
  31.     secondDict=myTree[firstStr]
  32.     for key in secondDict.keys():
  33.         if type(secondDict[key]).__name__=='dict':
  34.             thisDepth=1+getTreeDepth(secondDict[key])
  35.         else:
  36.             thisDepth=1
  37.         if thisDepth>maxDepth:maxDepth=thisDepth
  38.     return maxDepth
  39.  
  40.  
  41.  
  42. def plotMidText(cntrPt,parentPt,txtString):
  43.     xMid=(parentPt[0]-cntrPt[0])/2.0+cntrPt[0]
  44.     yMid=(parentPt[1]-cntrPt[1])/2.0+cntrPt[1]
  45.     createPlot.axl.text(xMid,yMid,txtString)
  46.  
  47. def plotTree(mytree,parentPt,nodeTxt):
  48.     numLeafs=getNumLeafs(mytree)
  49.     depth=getTreeDepth(mytree)
  50.     firstStr=list(mytree.keys())[0]
  51.     cntrPt=(plotTree.xOff+(1.0+float(numLeafs))/2.0/plotTree.totalW,plotTree.yOff)
  52.     plotMidText(cntrPt,parentPt,nodeTxt)
  53.     plotNode(firstStr,cntrPt,parentPt,decisionNode)
  54.     secondDict=mytree[firstStr]
  55.     plotTree.yOff=plotTree.yOff-1.0/plotTree.totalD
  56.     for key in secondDict.keys():
  57.         if type(secondDict[key]).__name__=='dict':
  58.             plotTree(secondDict[key],cntrPt,str(key))
  59.         else:
  60.             plotTree.xOff=plotTree.xOff+1.0/plotTree.totalW
  61.             plotNode(secondDict[key],(plotTree.xOff,plotTree.yOff),cntrPt,leafNode)
  62.             plotMidText((plotTree.xOff,plotTree.yOff),cntrPt,str(key))
  63.     plotTree.yOff=plotTree.yOff+1.0/plotTree.totalD
  64.  
  65.  
  66. def createPlot(inTree):
  67.     fig=plt.figure(1,facecolor='white')
  68.     fig.clf()
  69.     axprops=dict(xticks=[],yticks=[])
  70.     createPlot.axl=plt.subplot(111,frameon=False,**axprops)
  71.     plotTree.totalW=float(getNumLeafs(inTree))
  72.     plotTree.totalD=float(getTreeDepth(inTree))
  73.     plotTree.xOff=-0.5/plotTree.totalW;plotTree.yOff=1.0;plotTree(inTree,(0.5,1.0),'')
  74.     plt.show()
  75.

3、预剪枝及测试：

  1. # 创建预剪枝决策树
  2. def createTreePrePruning(dataTrain, labelTrain, dataTest, labelTest, names, method = 'id3'):
  3.     trainData = np.asarray(dataTrain)
  4.     labelTrain = np.asarray(labelTrain)
  5.     testData = np.asarray(dataTest)
  6.     labelTest = np.asarray(labelTest)
  7.     names = np.asarray(names)
  8.     if len(set(labelTrain)) == 1: 
  9.         return labelTrain[0] 
  10.     elif trainData.size == 0: 
  11.         return voteLabel(labelTrain)
  12.     bestFeat, bestEnt = bestFeature(dataTrain, labelTrain, method = method)
  13.     bestFeatName = names[bestFeat]
  14.     names = np.delete(names, [bestFeat])
  15.     dataTrainSet, labelTrainSet = splitFeatureData(dataTrain, labelTrain, bestFeat)
  16.  
  17.  
  18.     labelTrainLabelPre = voteLabel(labelTrain)
  19.     labelTrainRatioPre = equalNums(labelTrain, labelTrainLabelPre) / labelTrain.size
  20.     if dataTest is not None: 
  21.         dataTestSet, labelTestSet = splitFeatureData(dataTest, labelTest, bestFeat)
  22.         labelTestRatioPre = equalNums(labelTest, labelTrainLabelPre) / labelTest.size
  23.         labelTrainEqNumPost = 0
  24.         for val in labelTrainSet.keys():
  25.             labelTrainEqNumPost += equalNums(labelTestSet.get(val), voteLabel(labelTrainSet.get(val))) + 0.0
  26.         labelTestRatioPost = labelTrainEqNumPost / labelTest.size 
  27.     
  28.     if dataTest is None and labelTrainRatioPre == 0.5:
  29.         decisionTree = {bestFeatName: {}}
  30.         for featValue in dataTrainSet.keys():
  31.             decisionTree[bestFeatName][featValue] = createTreePrePruning(dataTrainSet.get(featValue), labelTrainSet.get(featValue)
  32.                                       , None, None, names, method)
  33.     elif dataTest is None:
  34.         return labelTrainLabelPre 
  35.     elif labelTestRatioPost < labelTestRatioPre:
  36.         return labelTrainLabelPre
  37.     else :
  38.         decisionTree = {bestFeatName: {}}
  39.         for featValue in dataTrainSet.keys():
  40.             decisionTree[bestFeatName][featValue] = createTreePrePruning(dataTrainSet.get(featValue), labelTrainSet.get(featValue)
  41.                                       , dataTestSet.get(featValue), labelTestSet.get(featValue)
  42.                                       , names, method)
  43.     return decisionTree 
  44.  
  1. myDataTrain, myLabelTrain, myDataTest, myLabelTest = splitMyData20(myData, myLabel)
  2. myTreeTrain = createTree(myDataTrain, myLabelTrain, myName, method = 'id3')
  3. myTreePrePruning = createTreePrePruning(myDataTrain, myLabelTrain, myDataTest, myLabelTest, myName, method = 'id3')
  4. # 画剪枝前的树
  5. print("剪枝前的树")
  6. createPlot(myTreeTrain)
  7. # 画剪枝后的树
  8. print("剪枝后的树")
  9. createPlot(myTreePrePruning)

输出结果：

 

 

 4、后剪枝及测试：

  1. # 创建决策树 带预划分标签
  2. def createTreeWithLabel(data, labels, names, method = 'id3'):
  3.     data = np.asarray(data)
  4.     labels = np.asarray(labels)
  5.     names = np.asarray(names)
  6.     votedLabel = voteLabel(labels)
  7.     if len(set(labels)) == 1: 
  8.         return votedLabel 
  9.     elif data.size == 0: 
  10.         return votedLabel
  11.     bestFeat, bestEnt = bestFeature(data, labels, method = method)
  12.     bestFeatName = names[bestFeat]
  13.     names = np.delete(names, [bestFeat])
  14.     decisionTree = {bestFeatName: {"_vpdl": votedLabel}}
  15.     dataSet, labelSet = splitFeatureData(data, labels, bestFeat)
  16.     for featValue in dataSet.keys():
  17.         decisionTree[bestFeatName][featValue] = createTreeWithLabel(dataSet.get(featValue), labelSet.get(featValue), names, method)
  18.     return decisionTree 
  19.  
  20. def convertTree(labeledTree):
  21.     labeledTreeNew = labeledTree.copy()
  22.     nodeName = list(labeledTree.keys())[0]
  23.     labeledTreeNew[nodeName] = labeledTree[nodeName].copy()
  24.     for val in list(labeledTree[nodeName].keys()):
  25.         if val == "_vpdl": 
  26.             labeledTreeNew[nodeName].pop(val)
  27.         elif type(labeledTree[nodeName][val]) == dict:
  28.             labeledTreeNew[nodeName][val] = convertTree(labeledTree[nodeName][val])
  29.     return labeledTreeNew
  30.  
  31.  
  32. # 后剪枝 训练完成后决策节点进行替换评估  
  33. def treePostPruning(labeledTree, dataTest, labelTest, names):
  34.     newTree = labeledTree.copy()
  35.     dataTest = np.asarray(dataTest)
  36.     labelTest = np.asarray(labelTest)
  37.     names = np.asarray(names)
  38.     featName = list(labeledTree.keys())[0]
  39.     featCol = np.argwhere(names==featName)[0][0]
  40.     names = np.delete(names, [featCol])
  41.     newTree[featName] = labeledTree[featName].copy()
  42.     featValueDict = newTree[featName]
  43.     featPreLabel = featValueDict.pop("_vpdl")
  44.     subTreeFlag = 0
  45.     dataFlag = 1 if sum(dataTest.shape) > 0 else 0
  46.     if dataFlag == 1:
  47.         dataTestSet, labelTestSet = splitFeatureData(dataTest, labelTest, featCol)
  48.     for featValue in featValueDict.keys():
  49.         if dataFlag == 1 and type(featValueDict[featValue]) == dict:
  50.             subTreeFlag = 1 
  51.             newTree[featName][featValue] = treePostPruning(featValueDict[featValue], dataTestSet.get(featValue), labelTestSet.get(featValue), names)
  52.             if type(featValueDict[featValue]) != dict:
  53.                 subTreeFlag = 0 
  54.             
  55.  
  56.         if dataFlag == 0 and type(featValueDict[featValue]) == dict: 
  57.             subTreeFlag = 1 
  58.             newTree[featName][featValue] = convertTree(featValueDict[featValue])
  59.  
  60.     if subTreeFlag == 0:
  61.         ratioPreDivision = equalNums(labelTest, featPreLabel) / labelTest.size
  62.         equalNum = 0
  63.         for val in labelTestSet.keys():
  64.             equalNum += equalNums(labelTestSet[val], featValueDict[val])
  65.         ratioAfterDivision = equalNum / labelTest.size 
  66.         if ratioAfterDivision < ratioPreDivision:
  67.             newTree = featPreLabel 
  68.     return newTree
  69.  
  70.  
  1. myTreeTrain1 = createTreeWithLabel(myDataTrain, myLabelTrain, myName, method = 'id3')
  2. createPlot(myTreeTrain1)
  3. print(myTreeTrain1)
  1. xgTreeBeforePostPruning = {"脐部": {"_vpdl": "是"
  2.                                    , '凹陷': {'色泽':{"_vpdl": "是", '青绿': '是', '乌黑': '是', '浅白': '否'}}
  3.                                    , '稍凹': {'根蒂':{"_vpdl": "是"
  4.                                                   , '稍蜷': {'色泽': {"_vpdl": "是"
  5.                                                                   , '青绿': '是'
  6.                                                                   , '乌黑': {'纹理': {"_vpdl": "是"
  7.                                                                                , '稍糊': '是', '清晰': '否', '模糊': '是'}}
  8.                                                                   , '浅白': '是'}}
  9.                                                   , '蜷缩': '否'
  10.                                                   , '硬挺': '是'}}
  11.                                    , '平坦': '否'}}
  12.                                    
  13. xgTreePostPruning = treePostPruning(xgTreeBeforePostPruning, xgDataTest, xgLabelTest, xgName)
  14. createPlot(convertTree(xgTreeBeforePostPruning))
  15. createPlot(xgTreePostPruning)
  16.

 结果：

 

 

 

四、总结

对比预剪枝与后剪枝生成的决策树，可以看出，后剪枝通常比预剪枝保留更多的分支，其欠拟合风险很小，因此后剪枝的泛化性能往往由于预剪枝决策树。但后剪枝过程是从底往上裁剪，因此其训练时间开销比前剪枝要大。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号