题解思路

方法思路

1. 问题分析：决策树可能过拟合训练数据，需要通过剪枝提高泛化能力。对于每个节点，考虑将其转换为叶节点后的F1值，选择最优方案。
2. 算法选择：使用深度优先搜索(DFS)后序遍历决策树。对于每个节点，计算：
   • 保留子树时的F1值（递归处理左右子树）
   • 剪枝为叶节点时的F1值
3. 关键操作：比较两种方案的F1值，选择较大的一个，实现贪心剪枝。
4. 复杂度分析：每个节点处理一次，每次处理需要遍历验证数据子集。时间复杂度为O(N*M)，其中N为节点数，M为验证集大小。

题目内容

决策树生成算法递归地产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。

在决策树学习中将已生成的树进行简化的过程称为剪枝。具体地，剪枝从已生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类树模型。

小$A$希望通过决策树的方法解决一个二分类任务。在该二分类的任务中，标签 $1$ 是正分类，标签 $0$ 是负分类。现在小A已经训练了一个未剪枝的二分类的决策树。他希望对该决策树进行剪枝，能够在验证集上达到最优的 $F1$ 值。

给定一个二叉树为待剪枝的二分类决策树，每个节点有 $3$ 个参数 $f_i、th_i、label_i$ 。当节点非叶节点时，$f_i、th_i$ 表示该节点决策应用的特征编号和阈值。在数据的第 $f_i$ 个特征小于等于 $th_i$ 时决策走左节点，大于 $th_i$ 时走右节点。决策树的预测通过该规则推理到叶节点时，叶节点的 $label_i$ 为该条数据的预测结果。

请输出小$A$通过剪枝在验证集上可以达到的最优 $F1$ 值。

输入描述

第一行为一个 $N、M、K$ 。其中，$N(1<=N<=100)$ 表示决策树的节点个数。$M(1<=M<=300)$ 表示验证集条数。$K(1<=K<=100)$ 表示每条验证集特征个数。

随后 $N$ 行，第 $i$ 行表示第 $i$ 个节点，根节点编号为 $1$ ，每行包括 $5$ 个整数 $l_i、r_i、f_i、th_i、label_i$ 。其中 $l_i、r_i$ 分别表示节点的左右子节点编号 $(0<=l_ir_i<=100)$ 。若 $l_i =0、r_i=0$ 则表示无子节点，不存在只有一个子节点的情况。当节点非叶节点时，$f_i、th_i$ 表示该节点的特征编号和阔值，否则 $f_i、th_i$ 为 $0$ 。$label_i$ 表示当该节点作为叶节点时的分类结果( $label_i$ 取值为 $0$ 或 $1$ )。

随后 $M$ 行为验证集特征和 $label$，每行 $K+1$ 个整数，前 $K$ 个整数为该条数据的特征，最后一个整数位该条数据的 $label$ 。

输出描述

请输出一个浮点数，为验证集可达到的最优 $F1$ 值，四舍五入保留小数点后 $6$ 位。

样例1

输入

7 3 2
2 3 1 50 0
4 5 2 50 0
6 7 2 50 1
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 1
30 60 1
30 30 1
60 30 1

输出

0.800000

说明

原始决策树为

第一条数据的终止节点为 $5$ ，节点 $predict_label$ 为 $1$ ，预测正确。

第二条数据的终止节点为 $4$ ，节点 $predict_label$ 为 $0$ ，预测错误。

第三条数据的终止节点为 $6$ ，节点 $predict_label$ 为 $0$ ，预测错误。

$Precision$ 为 $1$ , $Recall$ 为 $1/3,F1$ $Score$ 为 $1/2$ 。

决策树可将节点 $6、7$ 裁剪掉，裁剪后的决策树为：

第一条数据的终止节点为 $5$ ，节点 $predict_label$ 为 $1$ ，预测正确。

第二条数据的终止节点为 $4$ ，节点 $predict_label$ 为 $0$ ，预测错误。

第三条数据的终止节点为 $3$ ，节点 $predict_label$ 为 $1$ ，预测正确。

$Precision$ 为 $1,Recall$ 为 $2/3,F1$ $Score$ 为 $4/5=0.800000$ 。

样例2

输入

7 3 3
2 3 3 87 1
0 0 1 3 0
4 5 1 38 1
0 0 2 8 1
6 7 2 94 1
0 0 2 44 1
0 0 2 9 0
30 78 73 0
73 99 99 1
72 3 2 0

输出

1.000000

提示

$F1$ 值计算公式：

$F1=2*(Precision *Recall) /(Precision + Recall)$