解题思路

本题要求用 CART 决策树 在二维特征（实部 x1、虚部 x2）上完成 16QAM 符号标签的分类，并使用 Gini 系数作为划分标准，树的最大深度为 5，且切分点仅允许取自集合 {-3,-2,-1,0,1,2,3}。训练后需要输出： 1）训练样本集合的整体 Gini 系数；2）对给定测试点的预测标签。

相关算法与实现要点

1. 节点不纯度（Gini） 对任意样本集合 $D$，令第 $i$ 类（标签）比例为 $P_i$，则

   $$Gini(D)=1-\sum_i P_i^2$$

   训练集整体 Gini 直接按全部训练样本的标签频率计算一次即可。

2. 候选划分

   • 特征：两维 $(x1,x2)$。

   • 切分点：限定在 $\{-3,-2,-1,0,1,2,3\}$。

   • 对每个特征与每个切分点，按规则将样本分为： 左子集 $D_1=\{x\mid x_f < t\}$，右子集 $D_2=\{x\mid x_f \ge t\}$。

   • 计算加权 Gini：

     $$Gini_{weight}=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

   • 选择 加权 Gini 最小 且 两侧非空 的划分；若最优加权 Gini 未严格小于 当前集合的 Gini（或已纯/深度到限），则生成叶子结点。

3. 叶子预测

   • 叶子输出当前集合的多数类标签；若并列，取数值更小的标签，保证确定性。

4. 构树

   • 从根开始递归，深度上限为 5。
   • 每个结点重复“枚举划分 → 选择最优 → 递归子树”的步骤。

5. 预测

   • 自根结点按“< 阈值走左，$\ge$ 阈值走右”到达叶子，输出叶子标签。

代码实现

Python

import sys
from collections import Counter

# 计算集合的 Gini 系数
def gini_of_labels(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    cnt = Counter(labels)
    s = 0.0
    for c in cnt.values():
        p = c / n
        s += p * p
    return 1.0 - s

# 多数类（并列取更小标签）
def majority_label(labels):
    cnt = Counter(labels)
    maxc = max(cnt.values())
    candidates = [k for k, v in cnt.items() if v == maxc]
    return min(candidates)

# 决策树结点
class Node:
    def __init__(self):
        self.is_leaf = True
        self.label = 0
        self.feature = -1
        self.threshold = 0.0
        self.left = None
        self.right = None

# 递归建树
THRESHOLDS = [-3, -2, -1, 0, 1, 2, 3]

def build_tree(X, y, idxs, depth_left):
    node = Node()
    curr_labels = [y[i] for i in idxs]
    curr_gini = gini_of_labels(curr_labels)
    # 叶子条件：纯、深度用尽
    if curr_gini == 0.0 or depth_left == 0:
        node.is_leaf = True
        node.label = majority_label(curr_labels)
        return node

    best_gini = float('inf')
    best_f, best_t = -1, None
    best_left, best_right = None, None

    # 枚举特征与阈值
    for f in [0, 1]:
        for t in THRESHOLDS:
            left = []
            right = []
            for i in idxs:
                if X[i][f] < t:
                    left.append(i)
                else:
                    right.append(i)
            # 两侧必须非空
            if len(left) == 0 or len(right) == 0:
                continue
            g_left = gini_of_labels([y[i] for i in left])
            g_right = gini_of_labels([y[i] for i in right])
            w = (len(left) / len(idxs)) * g_left + (len(right) / len(idxs)) * g_right
            # 选择加权 Gini 更小的划分；平手时用更小特征、更小阈值保证确定性
            if w < best_gini - 1e-12 or (abs(w - best_gini) <= 1e-12 and (f < best_f or (f == best_f and t < (best_t if best_t is not None else 0)))):
                best_gini = w
                best_f, best_t = f, t
                best_left, best_right = left, right

    # 若无有效提升则设为叶子
    if best_left is None or best_gini >= curr_gini - 1e-12:
        node.is_leaf = True
        node.label = majority_label(curr_labels)
        return node

    # 划分并递归
    node.is_leaf = False
    node.feature = best_f
    node.threshold = best_t
    node.left = build_tree(X, y, best_left, depth_left - 1)
    node.right = build_tree(X, y, best_right, depth_left - 1)
    return node

def predict(root, x):
    node = root
    while not node.is_leaf:
        if x[node.feature] < node.threshold:
            node = node.left
        else:
            node = node.right
    return node.label

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    M = int(next(it))
    X = []
    y = []
    for _ in range(M):
        x1 = float(next(it)); x2 = float(next(it)); yy = int(next(it))
        X.append([x1, x2]); y.append(yy)
    tx1 = float(next(it)); tx2 = float(next(it))
    test = [tx1, tx2]

    # 训练集整体 Gini
    G = gini_of_labels(y)

    # 训练 CART 树
    idxs = list(range(M))
    root = build_tree(X, y, idxs, depth_left=5)

    # 预测
    pred = predict(root, test)

    # 输出
    print(f"{G:.4f}")
    print(pred)

if __name__ == "__main__":
    main()

Java

import java.util.*;

/* ACM 风格主类名要求为 Main */
public class Main {

    static class Node {
        boolean isLeaf = true;
        int label = 0;
        int feature = -1;     // 0: x1, 1: x2
        int threshold = 0;    // 阈值取自 {-3,-2,-1,0,1,2,3}
        Node left = null, right = null;
    }

    static final int[] THRESH = {-3, -2, -1, 0, 1, 2, 3};
    static int M;
    static double[] X1, X2;
    static int[] Y;

    // 计算 labels 的 Gini
    static double giniOfLabels(int[] idxs, int size) {
        if (size == 0) return 0.0;
        int[] cnt = new int[32]; // 标签范围 0..15，开大一点无妨
        for (int i = 0; i < size; i++) cnt[Y[idxs[i]]]++;
        double n = size;
        double s = 0.0;
        for (int c : cnt) {
            if (c == 0) continue;
            double p = c / n;
            s += p * p;
        }
        return 1.0 - s;
    }

    // 多数类（并列取更小标签）
    static int majorityLabel(int[] idxs, int size) {
        int[] cnt = new int[32];
        for (int i = 0; i < size; i++) cnt[Y[idxs[i]]]++;
        int bestCnt = -1, bestLab = 0;
        for (int lab = 0; lab <= 31; lab++) {
            if (cnt[lab] > bestCnt) {
                bestCnt = cnt[lab];
                bestLab = lab;
            } else if (cnt[lab] == bestCnt && cnt[lab] > 0 && lab < bestLab) {
                bestLab = lab;
            }
        }
        return bestLab;
    }

    static Node buildTree(int[] idxs, int size, int depthLeft) {
        Node node = new Node();
        double currGini = giniOfLabels(idxs, size);
        if (currGini == 0.0 || depthLeft == 0) {
            node.isLeaf = true;
            node.label = majorityLabel(idxs, size);
            return node;
        }

        double bestGini = Double.POSITIVE_INFINITY;
        int bestF = -1, bestT = 0;
        int[] bestLeft = null, bestRight = null;
        int bestLeftSize = 0, bestRightSize = 0;

        // 枚举特征与阈值
        for (int f = 0; f < 2; f++) {
            for (int t : THRESH) {
                int[] left = new int[size];
                int[] right = new int[size];
                int ls = 0, rs = 0;
                for (int i = 0; i < size; i++) {
                    int idx = idxs[i];
                    double v = (f == 0) ? X1[idx] : X2[idx];
                    if (v < t) left[ls++] = idx;
                    else right[rs++] = idx;
                }
                if (ls == 0 || rs == 0) continue;
                double gLeft = giniOfLabels(left, ls);
                double gRight = giniOfLabels(right, rs);
                double w = (ls * 1.0 / size) * gLeft + (rs * 1.0 / size) * gRight;

                if (w < bestGini - 1e-12 || (Math.abs(w - bestGini) <= 1e-12 && (f < bestF || (f == bestF && t < bestT)))) {
                    bestGini = w;
                    bestF = f;
                    bestT = t;
                    bestLeft = left; bestRight = right;
                    bestLeftSize = ls; bestRightSize = rs;
                }
            }
        }

        if (bestLeft == null || bestGini >= currGini - 1e-12) {
            node.isLeaf = true;
            node.label = majorityLabel(idxs, size);
            return node;
        }

        node.isLeaf = false;
        node.feature = bestF;
        node.threshold = bestT;
        node.left = buildTree(Arrays.copyOf(bestLeft, bestLeftSize), bestLeftSize, depthLeft - 1);
        node.right = buildTree(Arrays.copyOf(bestRight, bestRightSize), bestRightSize, depthLeft - 1);
        return node;
    }

    static int predict(Node root, double x1, double x2) {
        Node p = root;
        while (!p.isLeaf) {
            double v = (p.feature == 0) ? x1 : x2;
            if (v < p.threshold) p = p.left;
            else p = p.right;
        }
        return p.label;
    }

    static double trainsetGini() {
        int[] idxs = new int[M];
        for (int i = 0; i < M; i++) idxs[i] = i;
        return giniOfLabels(idxs, M);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        X1 = new double[M];
        X2 = new double[M];
        Y = new int[M];
        for (int i = 0; i < M; i++) {
            X1[i] = sc.nextDouble();
            X2[i] = sc.nextDouble();
            Y[i] = sc.nextInt();
        }
        double tx1 = sc.nextDouble();
        double tx2 = sc.nextDouble();

        // 训练集整体 Gini
        double G = trainsetGini();

        // 建树
        int[] idxs = new int[M];
        for (int i = 0; i < M; i++) idxs[i] = i;
        Node root = buildTree(idxs, M, 5);

        // 预测
        int pred = predict(root, tx1, tx2);

        System.out.printf("%.4f\n", G);
        System.out.println(pred);
        sc.close();
    }
}

C++

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

struct Node {
    bool isLeaf = true;
    int label = 0;
    int feature = -1;   // 0: x1, 1: x2
    int threshold = 0;  // 取自 {-3,-2,-1,0,1,2,3}
    Node *left = nullptr, *right = nullptr;
};

static const int THRESH[7] = {-3, -2, -1, 0, 1, 2, 3};

int M;
vector<double> X1, X2;
vector<int> Y;

// 计算集合 Gini
double giniOfLabels(const vector<int>& idxs) {
    int n = (int)idxs.size();
    if (n == 0) return 0.0;
    int cnt[32] = {0};
    for (int id : idxs) cnt[Y[id]]++;
    double s = 0.0, nn = (double)n;
    for (int i = 0; i < 32; ++i) if (cnt[i] > 0) {
        double p = cnt[i] / nn;
        s += p * p;
    }
    return 1.0 - s;
}

// 多数类（并列取更小标签）
int majorityLabel(const vector<int>& idxs) {
    int cnt[32] = {0};
    for (int id : idxs) cnt[Y[id]]++;
    int bestCnt = -1, bestLab = 0;
    for (int lab = 0; lab < 32; ++lab) {
        if (cnt[lab] > bestCnt) {
            bestCnt = cnt[lab];
            bestLab = lab;
        } else if (cnt[lab] == bestCnt && cnt[lab] > 0 && lab < bestLab) {
            bestLab = lab;
        }
    }
    return bestLab;
}

Node* buildTree(const vector<int>& idxs, int depthLeft) {
    Node* node = new Node();
    double currGini = giniOfLabels(idxs);
    if (currGini == 0.0 || depthLeft == 0) {
        node->isLeaf = true;
        node->label = majorityLabel(idxs);
        return node;
    }

    double bestGini = 1e100;
    int bestF = -1, bestT = 0;
    vector<int> bestLeft, bestRight;

    // 枚举特征与阈值
    for (int f = 0; f < 2; ++f) {
        for (int t : THRESH) {
            vector<int> left, right;
            left.reserve(idxs.size());
            right.reserve(idxs.size());
            for (int id : idxs) {
                double v = (f == 0) ? X1[id] : X2[id];
                if (v < t) left.push_back(id);
                else right.push_back(id);
            }
            if (left.empty() || right.empty()) continue;
            double gLeft = giniOfLabels(left);
            double gRight = giniOfLabels(right);
            double w = (left.size() * 1.0 / idxs.size()) * gLeft
                     + (right.size() * 1.0 / idxs.size()) * gRight;
            if (w < bestGini - 1e-12 || (fabs(w - bestGini) <= 1e-12 && (f < bestF || (f == bestF && t < bestT)))) {
                bestGini = w;
                bestF = f; bestT = t;
                bestLeft.swap(left);
                bestRight.swap(right);
            }
        }
    }

    if (bestLeft.empty() || bestGini >= currGini - 1e-12) {
        node->isLeaf = true;
        node->label = majorityLabel(idxs);
        return node;
    }

    node->isLeaf = false;
    node->feature = bestF;
    node->threshold = bestT;
    node->left = buildTree(bestLeft, depthLeft - 1);
    node->right = buildTree(bestRight, depthLeft - 1);
    return node;
}

int predict(Node* root, double x1, double x2) {
    Node* p = root;
    while (!p->isLeaf) {
        double v = (p->feature == 0) ? x1 : x2;
        if (v < p->threshold) p = p->left;
        else p = p->right;
    }
    return p->label;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M_in;
    if (!(cin >> M_in)) return 0;
    M = M_in;
    X1.resize(M); X2.resize(M); Y.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> X1[i] >> X2[i] >> Y[i];
    }
    double tx1, tx2;
    cin >> tx1 >> tx2;

    // 训练集整体 Gini
    vector<int> allIdx(M);
    iota(allIdx.begin(), allIdx.end(), 0);
    double G = giniOfLabels(allIdx);

    // 建树并预测
    Node* root = buildTree(allIdx, 5);
    int pred = predict(root, tx1, tx2);

    cout.setf(std::ios::fixed); cout << setprecision(4) << G << "\n";
    cout << pred << "\n";
    return 0;
}

题目内容

在无线通信中使用$QAM$调制将信息通过无线信号从发送端传递到接收端。$QAM$调制后的信号可以使用一个复数表示。$16Q$AM调制会生成$16$个不同的复数信号。在无线信号传输过程中，信号会受到高斯噪声污染，使得接收到的$QAM$信号与发送的$QAM$信号产生误差。该过程可以用如下公式表示：

$S_{rx} = S_{tx} + n$，其中，$n$为复数高斯噪声。

例如，一个发送$16QAM$调制符号为：

$S_{tx} = -1 + 1j$

传输过程中受到的噪声信号为：

$n = 0.38 - 1.2j$

接收到的$16QAM$调制符号为：

$S_{rx} = -0.62 - 0.2j$

无线信号的符号检测过程，就是根据接收到的受噪声污染的$QAM$符号，判决输出其真实发送$QAM$符号。

下图所示为$16QAM$调制符号的星座图。图中，蓝色圆点表示发送的$QAM$符号，红色点表示受噪声污染后的接收$QAM$符号。

请使用CART决策树实现一个$QAM$符号检测器，完成$16QAM$调制的无线信号的接收检测。

要求：

1. 根据输入的$M$个接收16QAM调制符号和真实标签构建CART决策树；
2. 使用基尼系数（$Gini$）作为划分标准；
3. 决策树最大深度=$5$；
4. 特征值切分点限制为$\{-3,-2,-1,0,1,2,3\}$；
5. 输出训练集的$Gini$系数；
6. 输出验证$QAM$符号标签。

输入描述

第一行：一个实数$G$，表示训练样本集合的$Gini$系数，四舍五入后保留小数点后4位。

第二行：一个整数$y$，表示测试$QAM$符号的分类标签。

输出描述

对于每组测试数据，输出一行一个整数表示最大的$f(b)·g(b)$值.

补充说明

注意:$gcd(0,x)=x$,即$0$与任意数$x$的最大公约数都是任意数$x$。

样例1

输入

10
2.56 0.73 14
3.88 0.83 14
-0.32 2.93 7
-2.99 -3.56 0
3.36 -1.52 13
-2.70 -1.13 1
-0.57 0.97 6
2.71 3.22 15
2.35 -2.55 12
4.18 -1.25 13
-1.14 0.20

输出

0.8600
6

说明

上述输入第1行为训练样本集合中样本个数：10。

接下来10行为10个16QAM调制符号的接收信号（复数信号的实部、虚部），以及对应的原始发送符号的标签。

第12行为测试用的接收16QAM调制符号信号（复数信号的实部、虚部）。

输出第1行数值为使用这10个符号及对应原始符号标签作为训练样本集合，计算出的该集合Gini系数。数值四舍五入后保留四位小数。

输出第2行为基于上述构建的决策树对测试样本的原始发送符号标签的预测值。

样例2

输入

11
-3.24 0.96 2
2.79 0.95 14
2.99 -2.94 12
0.67 -2.55 8
-1.30 -0.71 5
0.73 -2.96 8
-3.04 1.30 2
-2.81 -0.68 1
2.88 3.33 15
-2.55 2.87 3
-1.01 -0.62 5
-3.24 -2.90

输出

0.8595
2

说明

上述输入第1行为训练样本集合中样本个数：11。

接下来11行为11个16QAM调制符号的接收信号（复数信号的实部、虚部），以及对应的原始发送符号的标签。

第13行为测试用的接收16QAM调制符号接收信号（复数信号的实部、虚部）。

输出第1行为使用这11个符号和对应的符号标签作为训练样本集合，计算出的该集合$Gini$系数。数值四舍五入后保留四位小数。

输出第2行为基于上述构建的决策树对测试样本的原始发送符号标签的预测值。

提示

样本集合中的样本有$K$个类别，每个类别的样本，在样本集合中的概率分布为$P = (P_1, P_2, ..., P_K)$

给定样本集合$D$，计算其$Gini$系数时，首先需要计算出样本集合中每个类别出现的比例$P_i$，然后基于如下$Gini$系数计算公式计算：

$Gini(D) = 1 - \sum_{i=1}^{K} P_i^2$

其中，$P_i$是第$i$类样本出现的比例，$K$是样本中总类别数。

CART树实现步骤：

1. 特征及切分点选择

遍历样本所有特征，对每一个特征值的特征值进行排序，以相邻特征值的中值作为切分点，计算以该切分点将样本划分为$D1$和$D2$两个子集后的加权基尼系数。

加权$Gini$系数计算公式为：

$Gini_{weight} = W_1Gini(D_1) + W_2Gini(D_2)$

其中，$W_1$为子集$D1$中样本在集合$D$中占比，$W_2$为子集$D2$中样本在集合$D$中占比。

2. 节点划分

选择使加权$Gini$系数最小的特征和特征值切分点，将数据集划分为左右两个子集：左子集$D1(<特征值划分点)$和右子集$D2(≥特征值划分点)$。

3. 递归构建树

对每个子集重复步骤1和2，直到满足停止条件（如节点样本数小于阈值，或达到最大深度）。