P4465.第3题-基于决策树的QAM调制符合检测
题目内容
在无线通信中使用QAM调制将信息通过无线信号从发送端传递到接收端。QAM调制后的信号可以使用一个复数表示。16QAM调制会生成16个不同的复数信号。在无线信号传输过程中，信号会受到高斯噪声污染，使得接收到的QAM信号与发送的QAM信号产生误差。该过程可以用如下公式表示：
Srx=Stx+n，其中，n为复数高斯噪声。
例如，一个发送16QAM调制符号为：
Stx=−1+1j
传输过程中受到的噪声信号为：
n=0.38−1.2j
接收到的16QAM调制符号为：
Srx=−0.62−0.2j
无线信号的符号检测过程，就是根据接收到的受噪声污染的QAM符号，判决输出其真实发送QAM符号。
下图所示为16QAM调制符号的星座图。图中，蓝色圆点表示发送的QAM符号，红色点表示受噪声污染后的接收QAM符号。
请使用CART决策树实现一个QAM符号检测器，完成16QAM调制的无线信号的接收检测。
要求：
- 根据输入的M个接收16QAM调制符号和真实标签构建CART决策树；
- 使用基尼系数（Gini）作为划分标准；
- 决策树最大深度=5；
- 特征值切分点限制为{−3,−2,−1,0,1,2,3}；
- 输出训练集的Gini系数；
- 输出验证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=(P1,P2,...,PK)
给定样本集合D，计算其Gini系数时，首先需要计算出样本集合中每个类别出现的比例Pi，然后基于如下Gini系数计算公式计算：
Gini(D)=1−∑i=1KPi2
其中，Pi是第i类样本出现的比例，K是样本中总类别数。
CART树实现步骤：
- 特征及切分点选择
遍历样本所有特征，对每一个特征值的特征值进行排序，以相邻特征值的中值作为切分点，计算以该切分点将样本划分为D1和D2两个子集后的加权基尼系数。
加权Gini系数计算公式为：
Giniweight=W1Gini(D1)+W2Gini(D2)
其中，W1为子集D1中样本在集合D中占比，W2为子集D2中样本在集合D中占比。
- 节点划分
选择使加权Gini系数最小的特征和特征值切分点，将数据集划分为左右两个子集：左子集D1(<特征值划分点)和右子集D2(≥特征值划分点)。
- 递归构建树
对每个子集重复步骤1和2，直到满足停止条件（如节点样本数小于阈值，或达到最大深度）。
