题目内容

模式识别是智能感知系统实现自主决策与环境理解的核心功能之一，在准确识别传感器信号中的潜在的周期性与谐波特征，对于实现故障预警，行为分析、个性化服务等关键应用具有重要意义。

下面你将设计一个基于频域特征的K-Means聚类系统，系统需要完成以下步骤：

步骤一：对输入的每组信号数组 $data[i]$，进行DFT频域变换

• 假设有 $N$ 组信号 $data[0] - data[N-1]$，每组信号 $data[i]$ 长度为 $L$
• 对每组信号执行离散傅里叶变换（DFT），DFT计算公式如下：

$X[k]=\sum_{n=0}^{L-1}x[n]\cdot e^{-j2\pi kn/L}$

其中：

• $x[n]$：输入信号 $data[i]$
• $X[k]$：DFT输出结果
• $k=0,1,\ldots,L-1$
• 补充说明，该复数形式结果的实部和虚部可表示如下：

$X[k]=Re[k]+j\cdot Im[k]$

其中：

$Re[k]=\sum_{n=0}^{L-1}x[n]\cdot cos(\frac{2\pi kn}{L})$

$Im[k]=-\sum_{n=0}^{L-1}x[n]\cdot sin(\frac{2\pi kn}{L})$

步骤二：提取3个最大幅值对应的 k 值

$|X[k]|=\sqrt{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(\vec{v_i},\vec{c_j})=\sqrt{\sum_{k=1}^{3}(v_{i,k}-c_{j,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]$

迭代过程：

1. 将每个样本分配给 距离最近 的聚类中心
2. 更新每个聚类中心：计算该聚类内所有样本特征向量（$k$ 值）的均值，然后四舍五入取整，保存为新的中心
3. 最多迭代 $100$ 次，或所有聚类中心的前后两次变化误差 $\le 1e-4$
4. 如果迭代过程中，某个中心没有被任何样本选择为最近中心（即该中心聚类为空），仍保留该中心且数值保持不变

注意：本题的输入输出均为小数，使用银行家舍入规则（即四舍六入五成双）：

• 当舍去的第一位小数数字小于 $5$ 时，直接舍去
• 当舍去的第一位小数数字大于 $5$ 时，进位
• 当舍去的第一位小数数字等于 $5$ 时：
  • 如果 $5$ 后面还有非零数字，则进位
  • 如果 $5$ 后面没有数字或全是零，则看前一位数字：
    • 如果是偶数，则舍去
    • 如果是奇数，则进位

输入描述

输入共 $N+2$ 行：

第 $1$ 行：$3$ 个整数（空格隔开）

$N\ L\ K$

其中：

• $N$：信号组数，即 $data[0]$ 到 $data[N-1]$，共 $N$ 组（$9\le N\le20$）
• $L$：每组信号的长度（$20\le L\le50$）
• $K$：聚类数量（$2\le K\le4$）

第 $2\sim N+1$ 行：每行 $L$ 个浮点数（空格隔开），表示一组信号数据：

$x[0]\ x[1]\ \ldots\ x[L-1]$

第 $N+2$ 行：$K$ 个整数（空格隔开），初始聚类中心在信号数据中的索引（$\in[0,N-1]$）

$index[0]\ index[1]\ \ldots\ 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\sim 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]前。