解题思路

本题要求用训练样本（m 个二值特征，标签为 0/1）构建一个二叉决策树（ID3），再对 q 个查询样本进行预测。 核心要点：

1. 划分准则：使用信息增益（Entropy + Information Gain）。

   • 节点样本集合 $S$ 的熵 $H(S)=-\sum p_i\log_2 p_i$（二分类时就是看 0/1 的占比）。
   • 选择尚未使用的特征 $f$ 进行二分（按 0/1 分到 $S_0,S_1$），条件熵为 $H(S|f)=\frac{|S_0|}{|S|}H(S_0)+\frac{|S_1|}{|S|}H(S_1)$， 信息增益 $IG=H(S)-H(S|f)$。
   • 在信息增益最大的特征上划分；若增益相等，选索引更小的特征。

2. 停止与叶子规则（与题面特殊情况一致）：

   • 若当前样本全为同一标签 → 返回该标签。
   • 若没有可带来进一步划分的特征（所有剩余特征信息增益 $\le 0$ 或已用尽）→ 返回多数标签（平票返回 0）。
   • 实现时，为了保证预测分支完整：当某次划分出现一侧子集为空，也令该子结点为多数标签叶子（平票 0）。

3. 预测：从根开始，按结点记录的特征索引读查询样本的该特征值（0/1）走向子结点，直到叶子输出标签。

实现细节：

• 递归建树，传入：样本下标集合、剩余可用特征（或 used 标记）。
• 计算信息增益时用双计数即可（统计在该特征取 0/1 时两类数量）。
• 为避免浮点误差，用一个很小的 $\varepsilon=1e{-12}$ 比较大小。

代码实现

Python

import sys
import math
from typing import List, Dict, Any

# 计算集合 S 的熵（S 给出为标签列表 0/1）
def entropy(labels: List[int]) -> float:
    n = len(labels)
    if n == 0:
        return 0.0
    c1 = sum(labels)
    c0 = n - c1
    res = 0.0
    for c in (c0, c1):
        if c == 0:
            continue
        p = c / n
        res -= p * math.log2(p)
    return res

# 返回多数标签（平票返回 0）
def majority_label(labels: List[int]) -> int:
    c1 = sum(labels)
    c0 = len(labels) - c1
    return 1 if c1 > c0 else 0

# 递归建树；features 为可用特征下标列表
def build_tree(X: List[List[int]], y: List[int], idxs: List[int], features: List[int]) -> Dict[str, Any]:
    # 若纯节点，直接返回叶子
    labels = [y[i] for i in idxs]
    if all(l == labels[0] for l in labels):
        return {"leaf": True, "label": labels[0]}

    # 若没有可用特征，或所有增益 <= 0，则返回多数标签
    base_H = entropy(labels)
    best_gain = -1.0
    best_f = -1
    eps = 1e-12

    for f in features:
        # 按特征 f 二分，统计 0/1 两侧标签
        idx0, idx1 = [], []
        lab0, lab1 = [], []
        for i in idxs:
            if X[i][f] == 0:
                idx0.append(i)
                lab0.append(y[i])
            else:
                idx1.append(i)
                lab1.append(y[i])
        cond = (len(idx0) / len(idxs)) * entropy(lab0) + (len(idx1) / len(idxs)) * entropy(lab1)
        gain = base_H - cond
        if gain > best_gain + eps or (abs(gain - best_gain) <= eps and f < best_f):
            best_gain = gain
            best_f = f

    if best_gain <= eps or best_f == -1:
        return {"leaf": True, "label": majority_label(labels)}

    # 根据最优特征划分
    idx0, idx1 = [], []
    for i in idxs:
        (idx0 if X[i][best_f] == 0 else idx1).append(i)

    # 子结点：空子集用多数标签叶子填充，保证可预测
    next_features = [f for f in features if f != best_f]
    if len(idx0) == 0:
        left_node = {"leaf": True, "label": majority_label(labels)}
    else:
        left_node = build_tree(X, y, idx0, next_features)

    if len(idx1) == 0:
        right_node = {"leaf": True, "label": majority_label(labels)}
    else:
        right_node = build_tree(X, y, idx1, next_features)

    return {"leaf": False, "feat": best_f, "left": left_node, "right": right_node}

# 用树进行预测
def predict(tree: Dict[str, Any], x: List[int]) -> int:
    node = tree
    while not node["leaf"]:
        f = node["feat"]
        node = node["left"] if x[f] == 0 else node["right"]
    return node["label"]

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    X, y = [], []
    for _ in range(n):
        row = [int(next(it)) for _ in range(m + 1)]
        X.append(row[:m])
        y.append(row[m])
    q = int(next(it))
    Q = [[int(next(it)) for _ in range(m)] for _ in range(q)]

    idxs = list(range(n))
    features = list(range(m))
    tree = build_tree(X, y, idxs, features)

    out = []
    for x in Q:
        out.append(str(predict(tree, x)))
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.util.*;

/* 决策树(ID3)构建与预测：ACM 风格，读取输入并输出结果 */
public class Main {
    static class Node {
        boolean leaf;
        int label;     // 叶子：标签
        int feat;      // 非叶：特征下标
        Node left;     // 特征值=0
        Node right;    // 特征值=1
    }

    static double entropy(List<Integer> labels) {
        int n = labels.size();
        if (n == 0) return 0.0;
        int c1 = 0;
        for (int v : labels) c1 += v;
        int c0 = n - c1;
        double res = 0.0;
        if (c0 > 0) {
            double p = 1.0 * c0 / n;
            res -= p * (Math.log(p) / Math.log(2));
        }
        if (c1 > 0) {
            double p = 1.0 * c1 / n;
            res -= p * (Math.log(p) / Math.log(2));
        }
        return res;
    }

    static int majorityLabel(List<Integer> labels) {
        int c1 = 0;
        for (int v : labels) c1 += v;
        int c0 = labels.size() - c1;
        return (c1 > c0) ? 1 : 0; // 平票返回 0
    }

    static Node buildTree(int[][] X, int[] y, List<Integer> idxs, boolean[] used) {
        // 若纯节点
        int first = y[idxs.get(0)];
        boolean pure = true;
        for (int id : idxs) if (y[id] != first) { pure = false; break; }
        if (pure) {
            Node leaf = new Node();
            leaf.leaf = true;
            leaf.label = first;
            return leaf;
        }

        // 选择最佳特征
        List<Integer> labels = new ArrayList<>();
        for (int id : idxs) labels.add(y[id]);
        double baseH = entropy(labels);
        double bestGain = -1.0;
        int bestF = -1;
        double eps = 1e-12;

        int m = X[0].length;
        for (int f = 0; f < m; f++) {
            if (used[f]) continue;
            List<Integer> lab0 = new ArrayList<>();
            List<Integer> lab1 = new ArrayList<>();
            for (int id : idxs) {
                if (X[id][f] == 0) lab0.add(y[id]);
                else lab1.add(y[id]);
            }
            double cond = (lab0.size() * 1.0 / idxs.size()) * entropy(lab0)
                        + (lab1.size() * 1.0 / idxs.size()) * entropy(lab1);
            double gain = baseH - cond;
            if (gain > bestGain + eps || (Math.abs(gain - bestGain) <= eps && f < bestF)) {
                bestGain = gain;
                bestF = f;
            }
        }

        if (bestF == -1 || bestGain <= eps) {
            Node leaf = new Node();
            leaf.leaf = true;
            leaf.label = majorityLabel(labels);
            return leaf;
        }

        // 真正划分
        List<Integer> idx0 = new ArrayList<>();
        List<Integer> idx1 = new ArrayList<>();
        for (int id : idxs) {
            if (X[id][bestF] == 0) idx0.add(id); else idx1.add(id);
        }

        Node cur = new Node();
        cur.leaf = false;
        cur.feat = bestF;

        used[bestF] = true;
        if (idx0.isEmpty()) {
            Node lf = new Node();
            lf.leaf = true;
            lf.label = majorityLabel(labels);
            cur.left = lf;
        } else {
            cur.left = buildTree(X, y, idx0, used);
        }
        if (idx1.isEmpty()) {
            Node rf = new Node();
            rf.leaf = true;
            rf.label = majorityLabel(labels);
            cur.right = rf;
        } else {
            cur.right = buildTree(X, y, idx1, used);
        }
        used[bestF] = false; // 回溯
        return cur;
    }

    static int predict(Node root, int[] x) {
        Node p = root;
        while (!p.leaf) {
            p = (x[p.feat] == 0) ? p.left : p.right;
        }
        return p.label;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] X = new int[n][m];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) X[i][j] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        int q = sc.nextInt();
        int[][] Q = new int[q][m];
        for (int i = 0; i < q; i++) {
            for (int j = 0; j < m; j++) Q[i][j] = sc.nextInt();
        }

        List<Integer> idxs = new ArrayList<>();
        for (int i = 0; i < n; i++) idxs.add(i);
        boolean[] used = new boolean[m];
        Node root = buildTree(X, y, idxs, used);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            sb.append(predict(root, Q[i])).append('\n');
        }
        System.out.print(sb.toString());
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

/* ID3 决策树：二值特征，信息增益最大化；相等时选更小的特征索引 */

struct Node {
    bool leaf;
    int label;   // 叶子标签
    int feat;    // 非叶特征下标
    Node* left;  // 特征值 = 0
    Node* right; // 特征值 = 1
    Node(): leaf(true), label(0), feat(-1), left(nullptr), right(nullptr) {}
};

double entropy(const vector<int>& labels) {
    int n = (int)labels.size();
    if (n == 0) return 0.0;
    int c1 = 0;
    for (int v : labels) c1 += v;
    int c0 = n - c1;
    double res = 0.0;
    if (c0 > 0) {
        double p = 1.0 * c0 / n;
        res -= p * (log(p) / log(2.0));
    }
    if (c1 > 0) {
        double p = 1.0 * c1 / n;
        res -= p * (log(p) / log(2.0));
    }
    return res;
}

int majorityLabel(const vector<int>& labels) {
    int c1 = 0;
    for (int v : labels) c1 += v;
    int c0 = (int)labels.size() - c1;
    return (c1 > c0) ? 1 : 0; // 平票返回 0
}

Node* buildTree(const vector<vector<int>>& X, const vector<int>& y,
                const vector<int>& idxs, vector<char>& used) {
    // 如果全同标签，返回叶子
    bool pure = true;
    for (int id : idxs) if (y[id] != y[idxs[0]]) { pure = false; break; }
    if (pure) {
        Node* leaf = new Node();
        leaf->leaf = true;
        leaf->label = y[idxs[0]];
        return leaf;
    }

    // 选择信息增益最大的特征
    vector<int> labels; labels.reserve(idxs.size());
    for (int id : idxs) labels.push_back(y[id]);
    double baseH = entropy(labels);
    double bestGain = -1.0, eps = 1e-12;
    int bestF = -1;
    int m = (int)X[0].size();

    for (int f = 0; f < m; ++f) {
        if (used[f]) continue;
        vector<int> lab0, lab1;
        for (int id : idxs) {
            if (X[id][f] == 0) lab0.push_back(y[id]);
            else lab1.push_back(y[id]);
        }
        double cond = (lab0.size() * 1.0 / idxs.size()) * entropy(lab0)
                    + (lab1.size() * 1.0 / idxs.size()) * entropy(lab1);
        double gain = baseH - cond;
        if (gain > bestGain + eps || (fabs(gain - bestGain) <= eps && f < bestF)) {
            bestGain = gain; bestF = f;
        }
    }

    if (bestF == -1 || bestGain <= eps) {
        Node* leaf = new Node();
        leaf->leaf = true;
        leaf->label = majorityLabel(labels);
        return leaf;
    }

    // 划分并递归
    vector<int> idx0, idx1;
    for (int id : idxs) {
        if (X[id][bestF] == 0) idx0.push_back(id);
        else idx1.push_back(id);
    }

    Node* cur = new Node();
    cur->leaf = false;
    cur->feat = bestF;
    used[bestF] = 1;

    if (idx0.empty()) {
        Node* lf = new Node();
        lf->leaf = true;
        lf->label = majorityLabel(labels);
        cur->left = lf;
    } else cur->left = buildTree(X, y, idx0, used);

    if (idx1.empty()) {
        Node* rf = new Node();
        rf->leaf = true;
        rf->label = majorityLabel(labels);
        cur->right = rf;
    } else cur->right = buildTree(X, y, idx1, used);

    used[bestF] = 0; // 回溯
    return cur;
}

int predict(Node* root, const vector<int>& x) {
    Node* p = root;
    while (!p->leaf) {
        p = (x[p->feat] == 0) ? p->left : p->right;
    }
    return p->label;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; 
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> X(n, vector<int>(m));
    vector<int> y(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) cin >> X[i][j];
        cin >> y[i];
    }
    int q; cin >> q;
    vector<vector<int>> Q(q, vector<int>(m));
    for (int i = 0; i < q; ++i)
        for (int j = 0; j < m; ++j) cin >> Q[i][j];

    vector<int> idxs(n);
    iota(idxs.begin(), idxs.end(), 0);
    vector<char> used(m, 0);
    Node* root = buildTree(X, y, idxs, used);

    for (int i = 0; i < q; ++i) {
        cout << predict(root, Q[i]) << "\n";
    }
    return 0;
}

题目内容

通过分析基站的关键性能指标（如信息强度，干扰水平，用户数量等）。可以预测网络是否处于正常状态（标签0）或劣化状态（标签1）.决策树算法因其直观的判断逻辑和快速的响应能力，被广泛应用于无线网络智能运维场景。

给定一组基站性能特征数据和对应的网络质量标签，请实现一个基于信息增益的决策树分类器。用于判断网络质量是否劣化。信息熵定义为：

信息熵 = 划分前熵 - 划分后条件熵

特殊情况处理：

• 当多个特征对应的信息增益相等时，优先选择索引较小的特征进行样本划分；
• 当没有特征对样本进一步划分时，该节点预测为样本数较多的标签（若标签0和标签1数量一致，则默认该节点预测为0）。

输入描述

第一行：整数 $n \ (1 \leq n \leq 1000)$，表示训练样本数量，整数 $m \ (2 \leq m \leq 10)$ 表示特征数。

接下来 $n$ 行，每行包含 $m + 1$ 个整数，前 $m$ 个是特征 1 ~ 特征 $m$ 对应的特征值（取值为 0 或 1），最后一个是要预测的标签（ 0 或 1）。

下一行，整数 $q (1 \le q \le 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$ 个样本，每个样本包含三个特征。基于训练数据，可以构建出如下决策树：

样例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/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$