题解 | #聚类识别#

题目链接

聚类识别

题目描述

给出 $m$ 个终端的四维数值特征，需将它们用 K-Means 聚成 $k$ 类，并输出各簇的样本数，从小到大排序后以空格分隔打印。

实现规则如下：

初始质心：直接取数据中的前 $k$ 个样本。
距离：使用四维欧氏距离的平方（少一次开方，比较大小结果不变）。
更新：每轮按最近质心分配样本，再用簇内四维特征的平均值更新该簇质心。
收敛判定：若所有质心的新旧位置变化量（平方距离）最大值小于 1e-8，或已达到最多迭代次数 $n$ ，则停止。
空簇处理：若某簇本轮没有样本，保持该簇质心不变，避免除零错误。

输入描述

第一行： $k, m, n$ (聚类数, 样本数, 最大迭代次数)
接下来 $m$ 行：每行 4 个浮点数，表示一个终端的四维特征。

输出描述

一行： $k$ 个整数（各簇样本数），升序排列，用空格分隔。

解题思路

本题要求我们手动实现一个特定配置的K-Means聚类算法。K-Means是一个迭代算法，其目标是将数据点划分到K个簇（cluster）中，使得每个数据点都属于与其最近的均值（质心）对应的簇。整个过程是一个数值模拟，需要精确地按照步骤实现。

1. 初始化

读取参数: 读取聚类数 $k$ 、样本数 $m$ 、最大迭代次数 $n$ 。
读取数据: 读取 $m$ 个四维的样本数据点。
初始化质心: 题目明确规定，使用前 $k$ 个样本作为初始的 $k$ 个质心。

2. 迭代过程

算法的核心是一个循环，该循环会一直执行，直到满足收敛条件或达到最大迭代次数。

在每一轮迭代中，执行以下两个步骤：

分配步骤 (Assignment Step):
1. 创建一个数组（或列表）来记录每个样本被分配到的簇的ID。
2. 遍历每一个样本点。
3. 对于每个样本点，计算它与当前所有 $k$ 个质心的距离。题目要求使用四维欧氏距离的平方： $dist^2 = (x_1-c_1)^2 + (x_2-c_2)^2 + (x_3-c_3)^2 + (x_4-c_4)^2$
4. 找到距离最小的那个质心，并将该样本分配给这个质心所属的簇。
更新步骤 (Update Step):
1. 创建新的质心数组 new_centroids，以及用于计算的辅助数组（如 cluster_sums 用于累加簇内样本的特征值，cluster_counts 用于记录簇内样本数）。
2. 遍历所有样本及其分配结果。
3. 将每个样本的四维特征值累加到其所属簇的 cluster_sums 中，并递增该簇的 cluster_counts。
4. 遍历所有 $k$ 个簇：
  - 空簇处理：如果某个簇的 cluster_counts 为0，说明没有样本被分配到该簇。根据题目要求，该簇的质心保持不变，直接将旧质心复制到新质心位置。
  - 常规更新：如果簇非空，则通过计算簇内样本特征的平均值来更新质心： new_centroid_j = cluster_sum_j / cluster_count

3. 收敛判定

在每一轮迭代的更新步骤之后，需要检查算法是否收敛：

计算每个质心在新旧位置之间的变化量（同样使用欧氏距离的平方）。
找到这 $k$ 个变化量中的最大值 max_shift。
如果 max_shift < 1e-8，则认为算法已收敛，可以提前终止迭代。
同时，需要维护一个迭代计数器，如果迭代次数达到了 $n$ ，也必须终止循环。

4. 输出结果

当迭代结束后，我们需要统计最终每个簇中包含的样本数量。这可以在最后一轮的分配步骤中顺便完成，或者根据最终的分配结果再统计一次。
将得到的 $k$ 个簇的样本数进行升序排序。
按要求的格式（空格分隔）输出排序后的结果。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

// 计算两个四维点之间的欧氏距离的平方
double dist_sq(const vector<double>& p1, const vector<double>& p2) {
    double d = 0.0;
    for (int i = 0; i < 4; ++i) {
        d += (p1[i] - p2[i]) * (p1[i] - p2[i]);
    }
    return d;
}

int main() {
    int k, m, n;
    cin >> k >> m >> n;

    vector<vector<double>> samples(m, vector<double>(4));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < 4; ++j) {
            cin >> samples[i][j];
        }
    }

    // 初始化质心
    vector<vector<double>> centroids(k, vector<double>(4));
    for (int i = 0; i < k; ++i) {
        centroids[i] = samples[i];
    }

    vector<int> assignments(m);

    for (int iter = 0; iter < n; ++iter) {
        // 分配步骤
        for (int i = 0; i < m; ++i) {
            double min_dist = -1.0;
            int best_cluster = -1;
            for (int j = 0; j < k; ++j) {
                double d = dist_sq(samples[i], centroids[j]);
                if (best_cluster == -1 || d < min_dist) {
                    min_dist = d;
                    best_cluster = j;
                }
            }
            assignments[i] = best_cluster;
        }

        // 更新步骤
        vector<vector<double>> new_centroids(k, vector<double>(4, 0.0));
        vector<int> cluster_counts(k, 0);
        for (int i = 0; i < m; ++i) {
            int cluster_idx = assignments[i];
            for (int j = 0; j < 4; ++j) {
                new_centroids[cluster_idx][j] += samples[i][j];
            }
            cluster_counts[cluster_idx]++;
        }

        for (int i = 0; i < k; ++i) {
            if (cluster_counts[i] == 0) { // 空簇处理
                new_centroids[i] = centroids[i];
            } else {
                for (int j = 0; j < 4; ++j) {
                    new_centroids[i][j] /= cluster_counts[i];
                }
            }
        }

        // 收敛判定
        double max_shift = 0.0;
        for (int i = 0; i < k; ++i) {
            max_shift = max(max_shift, dist_sq(centroids[i], new_centroids[i]));
        }

        centroids = new_centroids;

        if (max_shift < 1e-8) {
            break;
        }
    }

    // 输出结果
    vector<int> final_counts(k, 0);
    for (int assignment : assignments) {
        final_counts[assignment]++;
    }
    sort(final_counts.begin(), final_counts.end());
    for (int i = 0; i < k; ++i) {
        cout << final_counts[i] << (i == k - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    // 计算四维欧氏距离的平方
    private static double distSq(double[] p1, double[] p2) {
        double d = 0.0;
        for (int i = 0; i < 4; i++) {
            d += (p1[i] - p2[i]) * (p1[i] - p2[i]);
        }
        return d;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int m = sc.nextInt();
        int n = sc.nextInt();

        double[][] samples = new double[m][4];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 4; j++) {
                samples[i][j] = sc.nextDouble();
            }
        }

        // 初始化质心
        double[][] centroids = new double[k][4];
        for (int i = 0; i < k; i++) {
            centroids[i] = Arrays.copyOf(samples[i], 4);
        }

        int[] assignments = new int[m];

        for (int iter = 0; iter < n; iter++) {
            // 分配步骤
            for (int i = 0; i < m; i++) {
                double min_dist = -1.0;
                int best_cluster = -1;
                for (int j = 0; j < k; j++) {
                    double d = distSq(samples[i], centroids[j]);
                    if (best_cluster == -1 || d < min_dist) {
                        min_dist = d;
                        best_cluster = j;
                    }
                }
                assignments[i] = best_cluster;
            }

            // 更新步骤
            double[][] new_centroids = new double[k][4];
            int[] cluster_counts = new int[k];
            for (int i = 0; i < m; i++) {
                int cluster_idx = assignments[i];
                for (int j = 0; j < 4; j++) {
                    new_centroids[cluster_idx][j] += samples[i][j];
                }
                cluster_counts[cluster_idx]++;
            }

            for (int i = 0; i < k; i++) {
                if (cluster_counts[i] == 0) { // 空簇处理
                    new_centroids[i] = Arrays.copyOf(centroids[i], 4);
                } else {
                    for (int j = 0; j < 4; j++) {
                        new_centroids[i][j] /= cluster_counts[i];
                    }
                }
            }

            // 收敛判定
            double max_shift = 0.0;
            for (int i = 0; i < k; i++) {
                max_shift = Math.max(max_shift, distSq(centroids[i], new_centroids[i]));
            }

            centroids = new_centroids;
            
            if (max_shift < 1e-8) {
                break;
            }
        }
        
        // 输出结果
        int[] final_counts = new int[k];
        for (int assignment : assignments) {
            final_counts[assignment]++;
        }
        Arrays.sort(final_counts);
        for (int i = 0; i < k; i++) {
            System.out.print(final_counts[i] + (i == k - 1 ? "" : " "));
        }
        System.out.println();
    }
}

import math

def dist_sq(p1, p2):
    # 计算四维欧氏距离的平方
    return sum([(a - b) ** 2 for a, b in zip(p1, p2)])

def solve():
    k, m, n = map(int, input().split())
    samples = [list(map(float, input().split())) for _ in range(m)]

    # 初始化质心
    centroids = samples[:k]
    
    assignments = [0] * m

    for _ in range(n):
        # 分配步骤
        for i, sample in enumerate(samples):
            min_dist = -1.0
            best_cluster = -1
            for j, centroid in enumerate(centroids):
                d = dist_sq(sample, centroid)
                if best_cluster == -1 or d < min_dist:
                    min_dist = d
                    best_cluster = j
            assignments[i] = best_cluster
            
        # 更新步骤
        new_centroids = [[0.0] * 4 for _ in range(k)]
        cluster_counts = [0] * k
        for i, sample in enumerate(samples):
            cluster_idx = assignments[i]
            for j in range(4):
                new_centroids[cluster_idx][j] += sample[j]
            cluster_counts[cluster_idx] += 1
            
        for i in range(k):
            if cluster_counts[i] == 0: # 空簇处理
                new_centroids[i] = centroids[i]
            else:
                for j in range(4):
                    new_centroids[i][j] /= cluster_counts[i]
                    
        # 收敛判定
        max_shift = 0.0
        for i in range(k):
            max_shift = max(max_shift, dist_sq(centroids[i], new_centroids[i]))
            
        centroids = new_centroids
        
        if max_shift < 1e-8:
            break
            
    # 输出结果
    final_counts = [0] * k
    for assignment in assignments:
        final_counts[assignment] += 1
        
    final_counts.sort()
    print(*final_counts)

solve()

算法及复杂度

算法: K-Means聚类（模拟）
时间复杂度: $O(n \cdot m \cdot k)$ - 其中 $n$ 是最大迭代次数， $m$ 是样本数， $k$ 是聚类数。
空间复杂度: $O(m + k)$ - 需要存储 $m$ 个样本数据和 $k$ 个质心位置。