L1Medium★ 工业基石 (核心高频)Part L · 经典 ML 与统计模拟
K-Means 聚类算法(距离矩阵与质心迭代更新)
无监督聚类经典,交替执行样本分配与质心均值重新计算,直到收敛。
⏱️ 时间复杂度:
O(iters * N * K * D)💾 空间复杂度:
O(N * K + K * D)🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
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 =
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] =
# 检查收敛
if np.max(np.linalg.norm(new_centroids - centroids, axis=-1)) < tol:
break
centroids = new_centroids
return centroids, labels
Step 3 · 反例与边界断言核对
💡
实战一句话记忆口诀
欧氏距离求分配,簇内求均更新点,交替收敛方差降
📐 核心数学公式与机理推导
### EM 算法特例与坐标下降收敛性
K-Means 旨在最小化样本到最近簇质心的误差平方和(Inertia / WCSS):
1. E 步(分配样本):固定所有簇质心 ,计算每个样本到所有质心的欧氏距离,将样本分配给距离最近的簇;
2. M 步(更新质心):固定分配关系 ,对每个簇内的样本取算术平均,作为新的簇质心 ;
交替迭代直至质心移动距离小于阈值 或达到最大轮数。
K-Means 旨在最小化样本到最近簇质心的误差平方和(Inertia / WCSS):
1. E 步(分配样本):固定所有簇质心 ,计算每个样本到所有质心的欧氏距离,将样本分配给距离最近的簇;
2. M 步(更新质心):固定分配关系 ,对每个簇内的样本取算术平均,作为新的簇质心 ;
交替迭代直至质心移动距离小于阈值 或达到最大轮数。
🔄 张量维度与形状流转说明
x: (N, D), centroids: (K, D) -> dists: (N, K) -> labels: (N,) -> new_centroids: (K, D)
🛡️ 数值稳定性自检与边界要点
- 若某个簇在迭代中分到 0 个样本(空簇),必须有兜底策略(如重新随机抽取一个数据点作为新质心)
- K-Means++ 初始化策略通过与已知质心距离的平方作为采样概率,显著提升收敛质量与稳定性
💻 完整参考代码实现
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
🧪 本地测试与正确性断言
可直接复制到本地 Python / Jupyter 验证:
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 聚类算法自测通过")🎯 核心工程追问与标准应答
Q1:K-Means 与高斯混合模型(GMM)有何本质联系与区别?
K-Means 是 GMM 的硬分配(Hard Assignment)极限特例。当 GMM 假设各个高斯分量的协方差矩阵均为各向同性 且方差 时,EM 算法中的后验概率软权重全部坍缩为 0 或 1,完全退化为 K-Means。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!