解题思路

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

相关算法与实现要点

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

题目内容

在无线通信中使用$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$符号标签。

输入描述

第一行：一个整数 $M$ ，表示训练样本集个数，取值范围[10~20]

接下来M行：两个实数 $x1$ ， $x2$ 和一个整数 $y$ ，以空格间隔。其中， $x1$ ， $x2$ 分别表示复数QAM符号的实部和虚部，取值范围 [-10 ~ +10]，保留小数点后2位。 $y$ 表示QAM符号的标签，取值范围[0~15]。

第 $M+2$ 行：两个实数 $x1$ ， $x2$ ，分别表示测试用接收QAM符号的实部和虚部，取值范围 [-10 ~ +10]，保留小数点后2位。

输出描述

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

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

样例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，直到满足停止条件（如节点样本数小于阈值，或达到最大深度）。