首页 > 试题广场 >

基于决策树的QAM调制符合检测

[编程题]基于决策树的QAM调制符合检测
  • 热度指数:4 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

用一小段带噪声的复数信号样本来训练一棵 CART 决策树,对16QAM符号进行分类判决。每个样本用两维实数特征表示:实部 x1 与虚部 x2;标签是整型类标(如0~15,对应16QAM的16个星座点)。

  • 划分标准:使用基尼系数(Gini)作为节点不纯度度量,选择加权 Gini 最小且左右子集均非空的划分。
  • 切分方式:只允许在特征 x1 或 x2 上,用固定阈值集合 {-3, -2, -1, 0, 1, 2, 3} 中的某个阈值 t 进行二分;样本按“特征值 < t 进左子集,否则进右子集”分配。
  • 叶子输出:叶子节点输出该节点内样本的多数类;若并列,取数值较小的标签,保证确定性。
  • 树深度:最大深度为 5(根深度计 1)。
  • 训练集整体 Gini:按训练集中各标签频率一次性计算并输出。

请在读入训练样本后,先输出训练集整体 Gini(四舍五入保留 4 位小数),再用训练好的树对给定测试点 (tx1, tx2) 进行预测并输出其标签。

约束与说明

  • 仅使用特征 x1、x2;阈值必须从 {-3, -2, -1, 0, 1, 2, 3} 中选择。
  • 每次划分两侧必须均非空;若所有候选划分都不能降低加权 Gini,或深度到限,则当前节点为叶子。
  • 并列多数类时取数值更小的类标。

输入描述:
  • 第 1 行:整数 M,表示训练样本数。
  • 第 2~M+1 行:每行三个数 x1 x2 y(x1、x2 为实数,y 为整型类标)。
  • 第 M+2 行:两个实数 tx1 tx2,表示测试样本的特征。


输出描述:
  • 第 1 行:训练集整体 Gini,四舍五入保留 4 位小数。
  • 第 2 行:对测试样本的预测标签(整数)。
示例1

输入

1
2.10 3.00 7
-0.50 1.20

输出

0.0000
7

说明

训练集中只有 1 条样本,其标签分布完全单一,训练集 Gini=0。
无法有效划分,根即叶,预测恒为 7。

这道题你会答吗?花几分钟告诉大家答案吧!