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

观前提示：这是本人决策树相关的第四篇博文，前3篇的内容如下：

1、建造训练集的决策树【完成结点类编写和建树过程】

2、用验证集评估模型、选出泛化较好的数据划分方式训练模型

3、预剪枝

读者可根据需要从上方《机器学习》专栏中查阅对应文章

第四章是后剪枝的内容，用到了许多前文相关的代码

完整代码都被集成到了colab的notebook当中，读者可以直接运行。

指路：DrawPixel/decisionTree.ipynb at main · ndsoi/DrawPixel (github.com)

1、后剪枝的理论部分

2、编程实践

1、划分训练集和验证集

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

3、收集所有的非叶结点

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

1、后剪枝的理论部分

作用：减少分支，提高模型的泛化能力

对比预剪枝：优势：防止训练不充分导致欠拟合；劣势：开销较大、时间较长

算法过程：

后剪枝先从训练集生成一棵完整决策树
从完整的决策树底层的非叶子结点出发，由下至上，对每一个分支结点（非叶子结点）考虑：
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)

结果：

剪枝后的决策树为：