解题思路

本题可以分成两个阶段：

1. 先按照给定阈值，把连续特征离散化为 $0/1$
2. 再用离散后的训练数据构建 $ID3$ 决策树，并对新样本分类

本题的特征在离散化后都是二值特征，因此非常适合直接使用 $ID3$ 算法。

题目内容

在大型网络运维系统中，交换机和路由器会持续上报关键 “运行状态”，如 CPU 使用率、内存占用、丢包率、温度等。为了进行故障分析，需要先将这些指标转换为二值告警信号：

• 当指标值 $<$阈值时，记为 $0$ (正常)
• 当指标值 $>=$ 阈值时，记为 $1$ (异常)

例如：$CPU$使用率 $50, 70, 60, 80, 90$，阈值为 $85$，转换后为：$0, 0, 0, 0, 1$。

当多个指标同时异常时，设备发生故障的概率会增加。现给定一组 “原始运行数据（连续值）” 及对应阈值，请你：

1. 将原始特征数据进行告警判断，转换为 $0/1$特征；
2. 使用 $ID3$ 决策树算法学习特征与设备故障之间的关系；
3. 对新的样本进行预测。

决策树分类算法（$ID3$）公式

1. 信息熵计算公式：

   $H(D) = -\sum_{i \in D} p_i \cdot \log_2 p_i$

   其中，$pi$为第$i$类样本在数据集$D$中所占的比例。

2. 信息增益计算公式：

   $Gain(D, A) = H(D) - H(D|A) = H(D) - \sum \frac{|D_v|}{|D|} H(D_v)$

   其中，$H(D∣A)$为特征 $A$ 对数据集 $D$ 的条件熵，$Dv$是特征$A$取值为 $v$ 的子集。

输入描述

第一行：两个整数$N$ 和 $M$

• $N$：训练样本数量
• $M$：特征数量

第二行：$M$个浮点数，表示每个特征的阈值

接下来 $N$ 行：每行包含$M+1$ 个浮点数

• 前 M 个为原始特征值（连续值）
• 最后一个为标签（$0$ 表示正常，$1$ 表示故障）

下一行：待测样本数量 $q$

接下来 $q$ 行：每行包含 $M$ 个原始特征值

约束条件

$1≤N≤10^3$

$1≤M≤20$

$1≤q≤10^3$

输出描述

输出 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.0 65.0 5.0$

第三行$60.5 60.2 3.1 -> 0 0 0$

第四行$80.3 70.8 6.2 -> 1 1 1$

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.55 Gain(F1)~ 0.05Gain(F2)≈ 0.95$(最大)选择 $F2$ 为根节点。划分后，样本已完全纯净，构建完毕。该样例为一层决策树，根节点为$F2$