解题思路
本题要求用训练样本（m 个二值特征，标签为 0/1）构建一个二叉决策树（ID3），再对 q 个查询样本进行预测。
核心要点：
-
划分准则：使用信息增益（Entropy + Information Gain）。
- 节点样本集合 S 的熵 H(S)=−∑pilog2pi（二分类时就是看 0/1 的占比）。
- 选择尚未使用的特征 f 进行二分（按 0/1 分到 S0,S1），条件熵为
P3792.第3题-基于决策树的无线状态预策
题目内容
通过分析基站的关键性能指标（如信息强度，干扰水平，用户数量等）。可以预测网络是否处于正常状态（标签0）或劣化状态（标签1）.决策树算法因其直观的判断逻辑和快速的响应能力，被广泛应用于无线网络智能运维场景。
给定一组基站性能特征数据和对应的网络质量标签，请实现一个基于信息增益的决策树分类器。用于判断网络质量是否劣化。信息熵定义为：
H(S)=−i∈S∑pilog2(pi)
信息熵 = 划分前熵 - 划分后条件熵
特殊情况处理：
- 当多个特征对应的信息增益相等时，优先选择索引较小的特征进行样本划分；
- 当没有特征对样本进一步划分时，该节点预测为样本数较多的标签（若标签0和标签1数量一致，则默认该节点预测为0）。
输入描述
第一行：整数 n (1≤n≤1000)，表示训练样本数量，整数 m (2≤m≤10) 表示特征数。
接下来 n 行，每行包含 m+1 个整数，前 m 个是特征 1 ~ 特征 m 对应的特征值（取值为 0 或 1），最后一个是要预测的标签（ 0 或 1）。
下一行，整数 q(1≤q≤100)，表示查询样本数量。
接下来 q 行，每行包括 m 个整数，表示查询样本的特征值 (0 或 1)。
输出描述
输出 q 行，每行为一个整数（0或1），表示对应查询样本的预测类别。
样例1
输入
10 3
1 0 1 1
1 0 0 0
1 1 1 1
1 1 0 1
0 0 1 0
0 0 0 0
0 1 1 1
0 1 0 0
1 0 1 1
0 1 1 1
3
1 0 1
0 0 0
1 1 0
输出
1
0
1
说明
数据包含 10 个样本，每个样本包含三个特征。基于训练数据，可以构建出如下决策树：
| 1. |
[特征3] |
| 2. |
/ \ |
| 3. |
/ \ |
| 4. |
[特征1] [特征1] |
| 5. |
/ \ / \ |
| 6. |
/ \ / \ |
| 7. |
标签=0 [特征2] [特征2] 标签=1 |
| 8. |
/ \ / \ |
| 9. |
/ \ / \ |
| 10. |
标签=0 标签=1 标签=0 标签=1 |
样例2
输入
6 2
1 1 1
0 0 0
1 0 1
0 1 0
1 1 1
0 0 0
2
1 1
0 0
输出
1
0
说明
训练数据包含 6 个样本，每个样本包含两个特征(特征 1 和特征 2 )，构建得到的决策树如下：
| 1. |
特征1 |
| 2. |
/ \ |
| 3. |
/ \ |
| 4. |
标签=0 标签=1 |
原始信息熵：−1/2 log(1/2)−1/2log(1/2)=1
使用特征 1 进行划分后：信息熵 =1log(1)=0 ，增益为 1
使用特征 2 进行划分后：信息熵 =0.5×0.9183+0.5×0.9183=0.9183，增益为 0.0817
