解题思路
本题可以分成两个阶段：
- 先按照给定阈值，把连续特征离散化为 0/1
- 再用离散后的训练数据构建 ID3 决策树，并对新样本分类
本题的特征在离散化后都是二值特征，因此非常适合直接使用 ID3 算法。
P4831.第3题-决策树实现网络设备故障预测
题目内容
在大型网络运维系统中，交换机和路由器会持续上报关键 “运行状态”，如 CPU 使用率、内存占用、丢包率、温度等。为了进行故障分析，需要先将这些指标转换为二值告警信号：
- 当指标值 <阈值时，记为 0 (正常)
- 当指标值 >= 阈值时，记为 1 (异常)
例如：CPU使用率 50,70,60,80,90，阈值为 85，转换后为：0,0,0,0,1。
当多个指标同时异常时，设备发生故障的概率会增加。现给定一组 “原始运行数据（连续值）” 及对应阈值，请你：
- 将原始特征数据进行告警判断，转换为 0/1特征；
- 使用 ID3 决策树算法学习特征与设备故障之间的关系；
- 对新的样本进行预测。
决策树分类算法（ID3）公式
-
信息熵计算公式：
H(D)=−∑i∈Dpi⋅log2pi
其中，pi为第i类样本在数据集D中所占的比例。
-
信息增益计算公式：
Gain(D,A)=H(D)−H(D∣A)=H(D)−∑∣D∣∣Dv∣H(Dv)
其中，H(D∣A)为特征 A 对数据集 D 的条件熵，Dv是特征A取值为 v 的子集。
输入描述
第一行：两个整数N 和 M
第二行：M个浮点数，表示每个特征的阈值
接下来 N 行：每行包含M+1 个浮点数
- 前 M 个为原始特征值（连续值）
- 最后一个为标签（0 表示正常，1 表示故障）
下一行：待测样本数量 q
接下来 q 行：每行包含 M 个原始特征值
约束条件
1≤N≤103
1≤M≤20
1≤q≤103
输出描述
输出 q 个待检测样本的预测类别，以空格分隔：0 1 1 0...
样例1
输入
10 3
75.0 65.0 5.0
60.5 60.2 3.1 0
80.3 70.8 6.2 1
78.7 60.4 6.5 1
72.1 68.9 4.2 0
90.6 80.1 7.3 1
85.2 62.5 3.6 0
65.4 75.3 6.8 1
70.8 60.7 5.0 0
88.9 66.2 4.8 1
74.6 72.4 6.1 1
3
82.5 64.0 4.0
68.2 70.5 6.2
91.0 60.3 3.2
输出
0 1 0
说明
1、特征离散化
例如：判断阈值为75.065.05.0
第三行60.560.23.1−>000
第四行80.370.86.2−>111
2、根据转换后的特征值和标签，构建ID3决策树。构建过程如下：
整体信息熵：标签有 6个1，4个0，H(S)=0.971
计算按各特征划分后的信息增益：（F0，F1，F2 表示分别是第 0 个，1 个，2 个特征为划分节点）
-
第一层：选择根节点
Gain(F0)≈0.125
Gain(F1)≈0.257
Gain(F2)≈0.610 (最大)
选择 F2 作为根节点
-
第二层划分
当 F2=0:
Gain(F0)≈0.322
Gain(F1)≈0.322(相同)
选择F0为分支节点；
当 F2=1: 分支已纯，直接为叶节点
-
第三层
当 F2=0且 F0=1:
Gain(F1)=1.0 (最大)
选择F1为分支节点
-
F1 为最终叶子节点，划分已纯净。最终构建树如下：（向左为 0，向右为 1）
F2
/ \
F0 1
/ \
0 F1
/ \
0 1
样例2
输入
8 3
75.5 68.0 4.5
60.2 55.1 2.0 0
82.3 70.5 6.1 1
78.0 65.2 5.0 1
69.5 72.3 3.8 0
90.1 85.0 7.2 1
74.0 60.0 4.0 0
88.8 66.6 5.5 1
72.2 69.1 4.8 1
3
80.0 60.0 3.0
85.0 75.0 6.0
70.0 80.0 5.0
输出
0 1 1
说明
数据解释:
第一行:共8个训练样本，每个样本有3个特征值
第二行:3个特征值的告警阈值
第3−10行:训练样本的原始特征值与判别标签
第11行:待测样本数3
第12−14行:待测样本的原始特征值
解题过程:
1、特征离散化 根据阈值(75.5,68.0,4.5)，将连续值转为0/1。例如:第三行60.2,55.1,2.0−>0,0,0
2、根据转换后的特征值和标签，构建ID3决策树。构建过程如整体信息熵:标签有5个1，3个0，H(S)=0.954计算按各特征划分后的信息增益:(FO，F1，F2表示分别是第o个，1个，2个特征为划分节点)Gain(Fo) 0.55Gain(F1) 0.05Gain(F2)≈0.95(最大)选择 F2 为根节点。划分后，样本已完全纯净，构建完毕。该样例为一层决策树，根节点为F2
