ML23. 实现 k-Means 聚类算法

题目描述

实现 k-Means 聚类算法，接受输入并生成最终质心的列表。

输入格式

4 个参数：

1. points：数据点列表，每个点为坐标元组，如 [(1, 2), (3, 4), ...]
2. k：簇的数量（由 initial_centroids 长度决定，但题目保留了参数）
3. initial_centroids：初始质心列表，形状为 (k, d)
4. max_iterations：最大迭代次数

输出格式

簇的最终质心的列表，其中每个质心都四舍五入保留小数点后四位，用元组表示。

示例

示例 1

输入：

[(1, 2), (1, 4), (1, 0), (10, 2), (10, 4), (10, 0)]
2
[(1, 1), (10, 1)]
10

输出：

[(1.0, 2.0), (10.0, 2.0)]

说明：

• 6 个数据点分为 2 簇
• 初始质心为 (1, 1) 和 (10, 1)
• 迭代后，靠近 (1,*) 的点聚为一簇，靠近 (10,*) 的点聚为另一簇
• 第一簇的点：(1,2), (1,4), (1,0)，质心 = ((1+1+1)/3, (2+4+0)/3) = (1.0, 2.0)
• 第二簇的点：(10,2), (10,4), (10,0)，质心 = ((10+10+10)/3, (2+4+0)/3) = (10.0, 2.0)

---

解题思路

第一步：理解 k-Means 算法

k-Means 是经典的无监督聚类算法，核心思想是：将数据划分为 k 个簇，使得簇内数据尽可能相似（距离近），簇间数据尽可能不同（距离远）。

算法迭代执行两个步骤直到收敛：

1. 分配阶段（Assignment）：每个点分配到距离最近的质心所在的簇
2. 更新阶段（Update）：重新计算每个簇的质心（簇内所有点的均值）

第二步：确定实现方案

使用 numpy 进行向量化计算，避免 Python 循环带来的性能问题。

关键计算：

• 点到质心的距离：使用广播机制 points[:, np.newaxis, :] - centroids[np.newaxis, :, :]
• 分配：使用 np.argmin 找到每个点最近的质心
• 更新：使用 mean(axis=0) 计算簇内均值

第三步：收敛判断

当质心位置不再变化（或变化极小）时，算法收敛。使用 np.allclose() 判断：

if np.allclose(centroids, new_centroids):
    break

---

完整代码实现

import numpy as np


def k_means_clustering(points, k, initial_centroids, max_iterations):
    """手动实现 k-Means 聚类算法

    算法步骤：
    1. 将输入数据转为 numpy 数组
    2. 迭代执行（最多 max_iterations 次）：
       a. 分配：计算每个点到每个质心的欧氏距离，分配到最近的簇
       b. 更新：计算每个簇内所有点的均值作为新质心
       c. 若质心不再变化，提前结束
    3. 返回保留四位小数的质心列表
    """
    points = np.array(points)
    centroids = np.array(initial_centroids, dtype=float)

    # 一维情况处理
    if centroids.ndim == 1:
        centroids = centroids.reshape(-1, 1)

    n, d = points.shape
    k = centroids.shape[0]

    for _ in range(max_iterations):
        # 1. 分配阶段
        # 广播计算距离: (n, 1, d) - (1, k, d) -> (n, k, d) -> 范数 -> (n, k)
        distances = np.linalg.norm(
            points[:, np.newaxis, :] - centroids[np.newaxis, :, :], axis=2
        )
        labels = np.argmin(distances, axis=1)

        # 2. 更新阶段
        new_centroids = np.zeros_like(centroids)
        for i in range(k):
            cluster_points = points[labels == i]
            if len(cluster_points) > 0:
                new_centroids[i] = cluster_points.mean(axis=0)
            else:
                new_centroids[i] = centroids[i]  # 空簇保留原质心

        # 3. 收敛判断
        if np.allclose(centroids, new_centroids):
            break
        centroids = new_centroids

    # 结果保留四位小数
    result = [tuple(np.round(c, 4)) for c in centroids]
    return result


def main():
    points = eval(input())
    k = int(input())
    initial_centroids = eval(input())
    max_iterations = int(input())
    final_centroids = k_means_clustering(points, k, initial_centroids, max_iterations)
    print(final_centroids)


if __name__ == "__main__":
    main()

---

示例推演

以示例输入为例：

初始状态：

• 数据点：[(1, 2), (1, 4), (1, 0), (10, 2), (10, 4), (10, 0)]
• 初始质心：[(1, 1), (10, 1)]

第 1 轮迭代：

分配阶段 —— 计算每个点到两个质心的距离：

点	到 (1,1) 距离	到 (10,1) 距离	分配
(1,2)	1.0	9.06	簇 0
(1,4)	3.0	9.49	簇 0
(1,0)	1.0	9.06	簇 0
(10,2)	9.06	1.0	簇 1
(10,4)	9.49	3.0	簇 1
(10,0)	9.06	1.0	簇 1

更新阶段 —— 计算新质心：

• 簇 0 质心：((1+1+1)/3, (2+4+0)/3) = (1.0, 2.0)
• 簇 1 质心：((10+10+10)/3, (2+4+0)/3) = (10.0, 2.0)

收敛判断：新质心与旧质心不同，继续迭代。

第 2 轮迭代：

用新质心 (1.0, 2.0) 和 (10.0, 2.0) 重新分配，点的归属不变。

新质心计算结果仍为 (1.0, 2.0) 和 (10.0, 2.0)，算法收敛。

输出：[(1.0, 2.0), (10.0, 2.0)]

---

复杂度分析

指标	复杂度	说明
时间	O(T · n · k · d)	T: 迭代次数, n: 点数, k: 簇数, d: 维度
空间	O(n + k · d)	存储数据点和质心

---

易错点总结

1. 空簇处理

cluster_points = points[labels == i]
if len(cluster_points) > 0:
    new_centroids[i] = cluster_points.mean(axis=0)
else:
    new_centroids[i] = centroids[i]  # 保留原质心

如果某个簇没有分配到任何点（空簇），mean() 会报错。需要特殊处理。

2. 一维数据形状

if centroids.ndim == 1:
    centroids = centroids.reshape(-1, 1)

一维数据输入时，numpy 数组形状可能不正确，需要手动调整为列向量。

3. 广播机制理解

distances = np.linalg.norm(
    points[:, np.newaxis, :] - centroids[np.newaxis, :, :], axis=2
)

• points[:, np.newaxis, :]：形状 (n, 1, d)
• centroids[np.newaxis, :, :]：形状 (1, k, d)
• 广播后相减：形状 (n, k, d)
• axis=2 求范数：形状 (n, k)

4. 结果精度

result = [tuple(np.round(c, 4)) for c in centroids]

题目要求保留四位小数，必须使用 np.round(c, 4)。

---

扩展思考

k-Means 的局限性

1. 需要预设 k 值：实际应用中 k 往往未知
2. 对初始质心敏感：不同初始值可能收敛到不同局部最优
3. 假设簇为球形：对非球形数据效果差
4. 对异常值敏感：一个异常点会显著影响质心位置

改进算法

• k-Means++：更智能的初始质心选择
• Mini-Batch k-Means：大数据集加速
• DBSCAN：无需预设 k 值，能发现任意形状簇
• 层次聚类：自底向上或自顶向下的聚类

scikit-learn 实现对比

from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=k, init=initial_centroids, max_iter=max_iterations)
kmeans.fit(points)
print(kmeans.cluster_centers_)

---

相关题目

• ML 系列其他题目