K-means 怎么做？为什么取均值？
复杂度多少？k 怎么选？

英文问法Explain K-means and implement it. · Why is the centroid the mean? · What's the time complexity? · How do you choose k?

考过★ 作者本人微软 AS 电面 · 微软 AS 实习 VO：手撕 + time complexity · 微软 AS2 推导轮：证明 centroid 取 mean。完整练习见 ml-coding。

先弄清楚：每个概念是什么

K-means: 像开 K 家快递站：每户去最近的站取件（assign），每个站再搬到自己住户的正中间（update），反复直到没人换站。
Centroid（质心）: 一堆点每一维各自取平均。例：(1, 1)、(3, 1)、(2, 4) 的质心是 (2, 2)。
Inertia（目标函数）: 每个点到自己质心距离的平方，全部加起来。越小，每堆越紧。
Local minimum 与 k-means++: 结果取决于起点。k-means++ 让初始中心尽量散开，再多跑几次取最好的。
K-means vs KNN: K-means 是 clustering，K 是簇数；KNN 是 supervised 预测，K 是邻居数。

30 秒回答

K-means splits n points into k clusters by minimizing inertia, the within-cluster sum of squared distances. It alternates two steps: assign each point to its nearest centroid, then move each centroid to the mean of its points. The mean is optimal because the gradient of Σ‖xᵢ − c‖² is zero there. Neither step increases inertia, so it always converges, but only to a local minimum, so we use k-means++ and several restarts. Each iteration is O(nkd). k is a hyperparameter: try several values and pick one by the elbow of inertia or the best silhouette score.

推导

为什么质心取均值（AS2 原题）

固定分配，只看一堆 \(S\)：

\[ \nabla_c \sum_{i\in S}\|x_i - c\|^2 = -2\sum_{i\in S}(x_i - c) = 0 \;\Longrightarrow\; c = \frac{1}{|S|}\sum_{i\in S} x_i,\qquad \nabla^2 = 2|S|\,I \succ 0 \]

为什么一定收敛

两步都不增大 inertia，而分组方式只有有限种 → 一定停。但只到 local minimum（找全局最优是 NP-hard）。

手撕代码（NumPy）

def kmeans(X, k, iters=100, seed=0):
    rng = np.random.default_rng(seed)
    C = X[rng.choice(len(X), k, replace=False)]      # 初始质心：随机 k 个点
    for _ in range(iters):
        # (n, k) 距离平方：||x||² − 2x·c + ||c||²
        D = (X**2).sum(1)[:, None] - 2 * X @ C.T + (C**2).sum(1)
        labels = D.argmin(1)                         # assign
        # update：取均值；空簇保持不动
        newC = np.array([X[labels == j].mean(0) if (labels == j).any() else C[j]
                         for j in range(k)])
        if np.allclose(newC, C):
            break
        C = newC
    return C, labels

复杂度

\(n\) 个点、\(d\) 维、\(k\) 个簇、\(I\) 轮：

步骤	对应代码	计算量
assign：算距离	`X @ C.T`（\(n\times d\) 乘 \(d\times k\)）	\(O(nkd)\)
assign：找最近	`D.argmin(1)`	\(O(nk)\)
update：取均值	`X[labels == j].mean(0)`，每个 \(j\)	\(O(nk + nd)\)

每轮 \(O(nkd)\)，总共 \(O(nkdI)\)。距离矩阵多占 \(O(nk)\) 内存。向量化只让矩阵乘法跑得快，复杂度不变。

k 怎么选

k 是试出来的。对一串 k 各跑一次 K-means 再打分。不能直接选 inertia 最小的，因为 k 越大 inertia 越小（k = n 时为 0）。

① Elbow：inertia 下降突然变慢的地方

一组真有 3 团的数据：

k	1	2	3	4	5	6
inertia	766.0	280.6	22.6	18.8	16.0	13.7
少了多少	–	485.4	258.0	3.9	2.7	2.3
silhouette	–	0.66	0.86	0.71	0.53	0.35

加第 3 个簇还能少 258，加第 4 个只少 3.9 → k = 3。缺点是真实数据的拐点常常不明显。

② Silhouette：每个点打分，取平均最高的 k

对每个点：\(a\) = 到同簇其他点的平均距离，\(b\) = 到最近的另一簇的平均距离，

\[ s = \frac{b - a}{\max(a, b)} \in [-1, 1] \]

例：一维的 1, 2, 3, 10, 11。分成 {1, 2, 3} 和 {10, 11} 时，点 2 的 \(a = 1\)、\(b = 8.5\)、\(s = 7.5/8.5 = 0.88\)，全部点平均 0.86。再拆出 {1}，点 2 的 \(b\) 变成 1，\(s = 0\)，平均掉到 0.45。拆得太碎分数反而下降，所以它不像 inertia 那样偏向大的 k。

# 看 inertia 的拐点，或取 silhouette 最大的 k
for k in range(1, 11):
    km = KMeans(n_clusters=k, n_init=10).fit(X)
    s = silhouette_score(X, km.labels_) if k > 1 else None   # silhouette 至少要 2 簇
    print(k, km.inertia_, s)

也可以直接按下游任务的指标选 k。

必答点

objective 是 inertia；两步交替：assign 到最近质心 → update 为均值
取均值：求导等于 0，Hessian 正定
收敛但只到 local minimum → k-means++ + 多次重启
复杂度：每轮 \(O(nkd)\)，总共 \(O(nkdI)\)
k 是试出来的：elbow 或 silhouette 最大

追问

k-means++ 怎么做？

第一个中心随机选；之后按 \(D(x)^2\) 的比例抽样，\(D(x)\) 是点到最近已选中心的距离。误差期望不超过最优的 \(O(\log k)\) 倍。

出现空簇怎么办？

把它挪到离自己质心最远的点，或重新随机选一个点。不能直接求均值（0/0 → nan）。

什么数据上会失效？换什么？

环形、细长等非凸的簇，大小或密度差很多的簇，有 outlier，feature 尺度不一（要先 standardize）。换 GMM、DBSCAN、spectral clustering。

n 很大怎么办？

分块算距离。或者用 mini-batch K-means，每步只用一小批点更新。

和 GMM 什么关系？

K-means 是 hard assignment，GMM 是 soft assignment。GMM 的 covariance 都取 \(\epsilon I\) 且 \(\epsilon \to 0\) 时就退化成 K-means。

来源Murphy, PML1 §21.3（pp.722–728）· Bishop, PRML §9.1、§9.3.2 · Aloise et al. 2009（NP-hard）

K-means 怎么做？为什么取均值？复杂度多少？k 怎么选？