P3480.第3题-F1值最优的决策树剪枝
题目内容
决策树生成算法递归地产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。
在决策树学习中将已生成的树进行简化的过程称为剪枝。具体地，剪枝从已生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶节点，从而简化分类树模型。
小A希望通过决策树的方法解决一个二分类任务。在该二分类的任务中，标签 1 是正分类，标签 0 是负分类。现在小A已经训练了一个未剪枝的二分类的决策树。他希望对该决策树进行剪枝，能够在验证集上达到最优的 F1 值。
给定一个二叉树为待剪枝的二分类决策树，每个节点有 3 个参数 fi、thi、labeli 。当节点非叶节点时，fi、thi 表示该节点决策应用的特征编号和阈值。在数据的第 fi 个特征小于等于 thi 时决策走左节点，大于 thi 时走右节点。决策树的预测通过该规则推理到叶节点时，叶节点的 labeli 为该条数据的预测结果。
请输出小A通过剪枝在验证集上可以达到的最优 F1 值。
输入描述
第一行为一个 N、M、K 。其中，N(1<=N<=100) 表示决策树的节点个数。M(1<=M<=300) 表示验证集条数。K(1<=K<=100) 表示每条验证集特征个数。
随后 N 行，第 i 行表示第 i 个节点，根节点编号为 1 ，每行包括 5 个整数 li、ri、fi、thi、labeli 。其中 li、ri 分别表示节点的左右子节点编号 (0<=liri<=100) 。若 li=0、ri=0 则表示无子节点，不存在只有一个子节点的情况。当节点非叶节点时，fi、thi 表示该节点的特征编号和阈值，否则 fi、thi 为 0 。labeli 表示当该节点作为叶节点时的分类结果( labeli 取值为 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 ，节点 predictlabel 为 1 ，预测正确。
第二条数据的终止节点为 4 ，节点 predictlabel 为 0 ，预测错误。
第三条数据的终止节点为 6 ，节点 predictlabel 为 0 ，预测错误。
Precision 为 1 , Recall 为 1/3,F1 Score 为 1/2 。
决策树可将节点 6、7 裁剪掉，裁剪后的决策树为：
第一条数据的终止节点为 5 ，节点 predictlabel 为 1 ，预测正确。
第二条数据的终止节点为 4 ，节点 predictlabel 为 0 ，预测错误。
第三条数据的终止节点为 3 ，节点 predictlabel 为 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)
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
