【AI 工业核题 L1】K-Means 聚类算法（距离矩阵与质心迭代更新）（K-Means Clustering from Scratch）深度实现与原理解析

题目分类：Part L · 经典 ML 与统计模拟 (Part L · Classical ML & Statistical Simulation) | 难度等级：Medium | 工业重要度：工业基石 (核心高频)

一、核心题意与背景

无监督聚类经典，交替执行样本分配与质心均值重新计算，直到收敛。

Industrial-grade implementation and mathematical foundations of K-Means Clustering from Scratch.

二、数学原理与公式推导

EM 算法特例与坐标下降收敛性

K-Means 旨在最小化样本到最近簇质心的误差平方和（Inertia / WCSS）：
$$J = sum_{n=1}^N sum_{k=1}^K r_{nk} |x_n – mu_k|^2$$
1. E 步（分配样本）：固定所有簇质心 $mu_k$，计算每个样本到所有质心的欧氏距离，将样本分配给距离最近的簇；
2. M 步（更新质心）：固定分配关系 $r_{nk}$，对每个簇内的样本取算术平均，作为新的簇质心 $mu_k$；
交替迭代直至质心移动距离小于阈值 $epsilon$ 或达到最大轮数。

三、工业级 Python 核心实现

import numpy as np

def kmeans(x: np.ndarray, k: int = 3, max_iters: int = 100, tol: float = 1e-4) -> tuple:
    N, D = x.shape
    # 随机初始化质心 (从样本中抽取 k 个)
    idx = np.random.choice(N, k, replace=False)
    centroids = x[idx].copy()

    for _ in range(max_iters):
        # 1. 广播计算样本到各质心的欧氏距离平方: (N, 1, D) - (1, K, D) -> (N, K)
        dists = np.sum((x[:, np.newaxis, :] - centroids[np.newaxis, :, :]) ** 2, axis=-1)
        labels = np.argmin(dists, axis=-1) # (N,)

        # 2. 重新计算质心
        new_centroids = np.zeros_like(centroids)
        for j in range(k):
            cluster_points = x[labels == j]
            if len(cluster_points) > 0:
                new_centroids[j] = np.mean(cluster_points, axis=0)
            else:
                # 孤立空簇重新随机初始化
                new_centroids[j] = x[np.random.choice(N)]

        # 检查收敛
        if np.max(np.linalg.norm(new_centroids - centroids, axis=-1)) < tol:
            break
        centroids = new_centroids

    return centroids, labels

四、自动化单元测试与边界断言

import numpy as np
# 构造两簇明显分开的数据
c1 = np.ones((20, 2)) * 0.0
c2 = np.ones((20, 2)) * 10.0
x = np.vstack([c1, c2])
centroids, labels = kmeans(x, k=2, max_iters=20)
assert centroids.shape == (2, 2)
# 两簇质心距离应大于 8
assert np.linalg.norm(centroids[0] - centroids[1]) > 8.0
print("✓ K-Means 聚类算法自测通过")

五、张量形状与维度变换流 (Tensor Flow)

• 中文解析：x: (N, D), centroids: (K, D) -> dists: (N, K) -> labels: (N,) -> new_centroids: (K, D)
• 英文对齐：x: (N, D), centroids: (K, D) -> dists: (N, K) -> labels: (N,) -> new_centroids: (K, D)

六、工业级数值稳定性避坑清单 (Checklist)

• ⚠️ 若某个簇在迭代中分到 0 个样本（空簇），必须有兜底策略（如重新随机抽取一个数据点作为新质心）
• ⚠️ K-Means++ 初始化策略通过与已知质心距离的平方作为采样概率，显著提升收敛质量与稳定性

English Checklist:
– Ensure proper multi-dimensional tensor broadcasting and keepdims retention.
– Enforce numerical guards (eps clamping and overflow thresholds) during exponentiation and division.
– Verify train versus eval mode behavioral distinctions (e.g. frozen running statistics and dropout bypass).

七、考场秒记心法口诀

💡 欧氏距离求分配，簇内求均更新点，交替收敛方差降

Master K-Means Clustering from Scratch: enforce numerical stability, check tensor shapes, and eliminate redundant memory allocations.

八、高频面试追问与答题策略

Q1：K-Means 与高斯混合模型（GMM）有何本质联系与区别？
(EN: What are the key trade-offs and memory bottlenecks when deploying K-Means Clustering from Scratch in high-throughput inference?)

答：K-Means 是 GMM 的硬分配（Hard Assignment）极限特例。当 GMM 假设各个高斯分量的协方差矩阵均为各向同性 $sigma^2 mathbf{I}$ 且方差 $sigma^2 to 0$ 时，EM 算法中的后验概率软权重全部坍缩为 0 或 1，完全退化为 K-Means。

(EN: Memory bandwidth (HBM to SRAM I/O) is the primary latency factor. Fusing element-wise operations and avoiding intermediate tensor materialization significantly outperforms naive implementations.)