机器学习——决策树（四）后剪枝

后剪枝先从训练集生成一棵完整决策树
从完整的决策树底层的非叶子结点出发，由下至上，对每一个分支结点（非叶子结点）考虑：
1. 如果划分：验证集精度=a
2. 如果不划分，令当前结点的label=1，class=max，验证集精度=b 比较a和b的大小:
  1. 如果a>b 则划分,令当前结点label = 0
  2. 如果a<=b 则不划分，令当前结点的label=1

2、编程实践

1、划分训练集和验证集

train_data = D[0:3]+D[5:7]+[D[9]]+D[13:]
val_data = D[3:5]+[D[7]]+D[8:13]
print("训练集")
show(train_data)
print("验证集")
show(val_data)

2、生成训练集完整的决策树

root_v5 = TreeGenerate(train_data,Attr)
drawTree(root_v5)

drawTree显示：

手绘更明确：

3、收集所有的非叶结点

def collectAllNoLeaf(root):
  NoLeafQ = queue.Queue()
  NoLeafS = []
  if root.label == 1:
    # 根结点本身是叶子，那就没有讨论空间了
    print(f"根结点本身是叶子")
    return NoLeafS
  
  NoLeafQ.put(root)
  NoLeafS.append(root)

  while NoLeafQ.empty() == False:
    # 当前层的结点数目
    n = NoLeafQ.qsize()
    for i in range(n):
      cur = NoLeafQ.get()
      # cur结点的子结点的数目
      for value,node in cur.subDs.items():
        if node.label != 1:
          # 子结点不是叶子结点
          
          NoLeafS.append(node)
          NoLeafQ.put(node)
  return NoLeafS
NoLeafnodes = collectAllNoLeaf(root_v5)

按层遍历了决策树，所有越底层的分支结点越在NoLeafnodes列表的后面

4、处理分支结点：划分or剪枝？

# 倒叙遍历
def train_v5(NoLeafnodes,root,val_data):
  n = len(NoLeafnodes)

  for i in range(n):

    cur = NoLeafnodes[n-1-i]
    # 沿用predict_v4 精度计算方法
    res_o,acc_o = predict_v4(root,val_data)
    print(f"划分的预测序列{res_o}")
    # 假如当前不划分
    cur.label = 1
    cur.Class = cur.max
    # 计算精度
    res_d,acc_d = predict_v4(root,val_data)
    print(f"不划分的预测序列{res_d}")
    if acc_o > acc_d:
      # 划分的精度更高
      print(f"划分的精度更高，划分了以后{acc_o}\t不划分{acc_d}")
      cur.label = 0
    else:
      print(f"不划分的精度更高，划分了以后{acc_o}\t不划分{acc_d}")
  return root

r = train_v5(NoLeafnodes,root_v5,val_data)
drawTree(r)

结果：

剪枝后的决策树为：

从最后打印的信息可以看到，虽然剪枝后决策树的分类精度还是0.875，但模型得到了简化

原文地址:https://blog.csdn.net/m0_60402183/article/details/136912880 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1770758756687286272.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部