解题思路
先对每组长度为 L 的信号做 DFT，只考虑非冗余正频率，即 k=1 到 k=(L−1)/2。
计算每个频率的幅值，因为比较大小时平方根不影响顺序，所以直接比较 Re2+Im2。
对每组信号选出幅值最大的 3 个频率下标，幅值相同则频率下标 k 小的优先，得到三维特征向量。
然后使用 K-Means 聚类：
P5122.第3题-基于频域特征的轻量级传感器信号聚类系统
题目内容
模式识别是智能感知系统实现自主决策与环境理解的核心功能之一，在准确识别传感器信号中的潜在的周期性与谐波特征，对于实现故障预警，行为分析、个性化服务等关键应用具有重要意义。
下面你将设计一个基于频域特征的K-Means聚类系统，系统需要完成以下步骤：
步骤一：对输入的每组信号数组 data[i]，进行DFT频域变换
- 假设有 N 组信号 data[0]−data[N−1]，每组信号 data[i] 长度为 L
- 对每组信号执行离散傅里叶变换（DFT），DFT计算公式如下：
X[k]=∑n=0L−1x[n]⋅e−j2πkn/L
其中：
- x[n]：输入信号 data[i]
- X[k]：DFT输出结果
- k=0,1,…,L−1
- 补充说明，该复数形式结果的实部和虚部可表示如下：
X[k]=Re[k]+j⋅Im[k]
其中：
Re[k]=∑n=0L−1x[n]⋅cos(L2πkn)
Im[k]=−∑n=0L−1x[n]⋅sin(L2πkn)
步骤二：提取3个最大幅值对应的 k 值
∣X[k]∣=Re[k]2+Im[k]2
- 从 k=1 到 k=L/2−1 中提取DFT计算结果（排除DC分量 k=0 和奈奎斯特频率 k=L/2）
- 计算每个频率点的幅值（magnitude）
- 按幅值从大到小排序，若幅值相同，则索引较小的排在前面
- 取前 3 个最大幅值对应的 k 值（频数索引），构成 3 维特征向量，从大到小排列（第 i 信号的特征向量可表示为 feature[i][3]）
步骤三：K-Means聚类（K 输入指定）
d(vi,cj)=∑k=13(vi,k−cj,k)2
初始聚类中心选择：
- 由输入给出 K 个整数索引 index[K]，直接作为初始聚类中心中特征向量的原始信号索引（index in [0,N−1]）
- 例如：若 K=3，且 init_centers=[0,1,5]，则初始中心为：
中心0：data[0]对应的特征向量feature[0][3]
中心1：data[1]对应的特征向量feature[1][3]
中心2：data[5]对应的特征向量feature[5][3]
迭代过程：
- 将每个样本分配给 距离最近 的聚类中心
- 更新每个聚类中心：计算该聚类内所有样本特征向量（k 值）的均值，然后四舍五入取整，保存为新的中心
- 最多迭代 100 次，或所有聚类中心的前后两次变化误差 ≤1e−4
- 如果迭代过程中，某个中心没有被任何样本选择为最近中心（即该中心聚类为空），仍保留该中心且数值保持不变
注意：本题的输入输出均为小数，使用银行家舍入规则（即四舍六入五成双）：
- 当舍去的第一位小数数字小于 5 时，直接舍去
- 当舍去的第一位小数数字大于 5 时，进位
- 当舍去的第一位小数数字等于 5 时：
- 如果 5 后面还有非零数字，则进位
- 如果 5 后面没有数字或全是零，则看前一位数字：
输入描述
输入共 N+2 行：
第 1 行：3 个整数（空格隔开）
N L K
其中：
- N：信号组数，即 data[0] 到 data[N−1]，共 N 组（9≤N≤20）
- L：每组信号的长度（20≤L≤50）
- K：聚类数量（2≤K≤4）
第 2∼N+1 行：每行 L 个浮点数（空格隔开），表示一组信号数据：
x[0] x[1] … x[L−1]
第 N+2 行：K 个整数（空格隔开），初始聚类中心在信号数据中的索引（∈[0,N−1]）
index[0] index[1] … index[K−1]
输出描述
输出共 K 行，每行对应一个聚类中心，格式如下：
k1 k2 k3
- 每行包含 3 个整数，表示该聚类中心的特征向量（3 个 k 值索引）
- 输出顺序为字典序（即不同特征向量，先比较第一个元素，数值小的排前面，如果相同，则继续比较第二个元素，如果第二个元素仍相同，则比较第三个元素）
- 所有输出以空格分隔，末尾无多余空格
样例1
输入
15 16 4
4.9 1.9 1.3 0.5 -3.0 -0.9 -1.3 -1.6 1.1 -1.6 -1.3 -0.9 -3.0 0.5 1.3 1.9
3.0 -0.5 -1.5 -0.0 -0.5 1.8 -0.0 -1.3 1.0 -1.3 -0.0 1.8 -0.5 -0.0 -1.5 -0.5
4.1 0.7 -0.4 -0.1 -1.4 2.0 0.4 -2.6 -1.4 -2.6 0.4 2.0 -1.4 -0.1 -0.4 0.7
3.8 0.6 -0.4 -0.1 -1.3 1.9 0.4 -2.4 -1.2 -2.4 0.4 1.9 -1.2 -0.1 -0.4 0.6
3.8 2.3 0.1 -0.3 -0.3 -1.5 -2.1 -0.5 0.8 -0.5 -2.1 -1.5 -0.2 -0.3 0.1 2.3
4.9 1.0 -2.3 -0.7 -1.6 -1.6 2.3 1.3 -1.6 1.3 2.3 -1.6 -1.6 -0.7 -2.3 1.0
4.1 -0.3 0.2 2.7 -1.6 -0.4 -0.2 -2.0 -0.9 -2.0 -0.2 -0.4 -1.6 2.7 0.2 -0.3
4.1 0.6 -1.3 2.0 1.1 -2.0 -0.9 -0.6 -1.9 -0.6 -0.9 -2.0 1.1 2.0 -1.3 0.6
5.6 1.2 -2.8 -1.4 -1.6 -0.9 2.8 1.1 -2.4 1.1 2.8 -0.9 -1.6 -1.4 -2.8 1.2
6.0 1.7 -1.4 1.2 -0.0 -1.2 1.4 -1.7 -6.0 -1.7 1.4 -1.2 0.0 1.2 -1.4 1.7
4.9 1.0 -2.3 -0.7 -1.6 -1.6 2.3 1.3 -1.6 1.3 2.3 -1.6 -1.6 -0.7 -2.3 1.0
6.0 1.3 -3.0 -1.5 -1.8 -1.0 3.0 1.1 -2.5 1.1 3.0 -1.0 -1.7 -1.5 -3.0 1.3
3.8 1.6 1.1 0.4 -2.3 -0.8 -1.1 -1.2 0.8 -1.2 -1.1 -0.8 -2.2 0.4 1.1 1.6
3.4 -0.3 0.2 2.2 -1.4 -0.3 -0.2 -1.7 -0.6 -1.7 -0.2 -0.3 -1.4 2.2 0.2 -0.3
5.6 0.2 -0.3 2.2 -0.5 0.8 -3.0 -3.2 1.9 -3.2 -3.0 0.8 -0.5 2.2 -0.3 0.2
0 1 3 10
输出
1 2 5
3 6 2
5 2 3
6 1 4
样例2
输入
9 26 2
3.5 -0.6 -0.3 -2.4 1.0 0.3 0.2 0.2 0.3 1.0 -2.4 -0.3 -0.6 3.5 -0.6 -0.3 -2.4 1.0 0.3 0.2 0.2 0.3 1.0 -2.4 -0.3 -0.6
3.5 0.0 -0.2 3.0 -0.2 -0.7 1.9 -0.7 -1.2 0.4 -1.2 -1.3 -0.7 -1.5 -0.7 -1.3 -1.2 0.4 -1.2 -0.7 1.9 -0.7 -0.2 3.0 -0.2 0.0
2.8 -1.1 -0.3 -0.7 0.8 -0.5 1.1 0.2 -2.0 0.6 0.7 0.8 -1.6 1.2 -1.6 0.8 0.7 0.6 -2.0 0.2 1.1 -0.5 0.8 -0.7 -0.3 -1.1
2.5 -0.8 0.3 -0.4 -0.0 -1.8 0.4 0.8 -0.6 1.3 0.4 0.2 -1.8 1.2 -1.8 0.2 0.4 1.3 -0.6 0.8 0.4 -1.8 -0.0 -0.4 0.3 -0.8
2.3 0.0 -0.1 2.0 -0.2 -0.4 1.3 -0.6 -0.8 0.3 -0.9 -0.8 -0.4 -1.1 -0.4 -0.8 -0.9 0.3 -0.8 -0.6 1.3 -0.4 -0.2 2.0 -0.1 0.0
2.3 -0.3 -1.1 0.7 -1.2 -0.6 1.8 0.2 -0.4 0.2 -1.1 -0.4 0.7 0.5 0.7 -0.4 -1.1 0.2 -0.4 0.2 1.8 -0.6 -1.2 0.7 -1.1 -0.3
3.7 -0.3 -0.0 -3.2 -0.0 0.7 1.9 0.6 -1.4 -0.3 -1.3 1.6 -1.0 1.5 -1.0 1.6 -1.3 -0.3 -1.4 0.6 1.9 0.7 -0.0 -3.2 -0.0 -0.3
2.1 0.1 -0.4 1.1 -0.4 -0.9 -0.3 -1.0 -0.1 -0.1 -0.9 1.2 1.2 -0.7 1.2 1.2 -0.9 -0.1 -0.1 -1.0 -0.3 -0.9 -0.4 1.1 -0.4 0.1
3.2 -0.4 0.2 -1.8 0.8 -0.6 -1.0 -0.3 1.0 2.5 -0.8 -0.1 -1.8 1.4 -1.8 -0.1 -0.8 2.5 1.0 -0.3 -1.0 -0.6 0.8 -1.8 0.2 -0.4
0 7
输出
9 2 8
12 6 4
说明
以第一行信号为例，DFT结果为X[k]=[0.20,0.00,0.06,0.00,13.24,0.00,14.90,0.00,0.02,0.00,0.09,0.00,17.40,0.00,17.40,0.00,0.09,0.00,0.02,0.00,14.90,0.00,13.24,0.00,0.06,0.00]，取 k=1∼L/2−1，排序后，最大的三个频域幅值为 X[12]、X[6] 和 X[4]，因此，该信号特征为 [12,6,4]。
所有样本特征如下：
[12,6,4]
[9,1,8]
[12,8,5]
[12,8,3]
[9,1,8]
[9,4,8]
[12,4,5]
[9,2,7]
[12,6,3]
取第0个和第7个向量为初值中心center[0]、center[1]，根据距离最近原则，特征0、2、3、6、8属于center[0]所表示的簇，特征1、4、5、7属于center[1]所表示的簇，每个簇的样本取均值并四舍五入后，取代原中心，进行下一轮迭代，Kmeans最终聚类结果为[12, 6, 4], [9, 2, 8]，按字典排序后，[9, 2, 8]排在[12, 6, 4]前。
