L1Medium★ Core Essential · Industrial BedrockPart L · Classical ML & Statistical Simulation

K-Means Clustering from Scratch

⚡Flashcard Drill➔

Unsupervised K-Means clustering alternating nearest-centroid assignment and cluster-mean updates.

⏱️ Time: O(iters * N * K * D)
💾 Space: O(N * K + K * D)
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
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 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: What is the exact theoretical connection between K-Means and Gaussian Mixture Models (GMM)?
Next: Linear Regression: Closed-Form & Gradient Descent →
💡

Core Mental Anchor / Mnemonic

Assign points to nearest centroid, recompute cluster means, iterate until shifts < tol.

📐 Mathematical Derivation & Core Formula

rnk={1k=arg⁡min⁡j∥xn−μj∥20otherwise,μk=∑nrnkxn∑nrnkr_{nk} = \begin{cases} 1 & k = \arg\min_j \|x_n - \mu_j\|^2 \\ 0 & \text{otherwise} \end{cases}, \quad \mu_k = \frac{\sum_{n} r_{nk} x_n}{\sum_n r_{nk}}
### Alternating Coordinate Descent on WCSS
K-Means minimizes within-cluster sum of squares J=∑n=1N∑k=1Krnk∥xn−μk∥2J = \sum_{n=1}^N \sum_{k=1}^K r_{nk} \|x_n - \mu_k\|^2 via two alternating steps until centroid shifts fall below tolerance:
1. Assignment (E-step): Assign each point xnx_n to its nearest centroid μk\mu_k by Euclidean distance;
2. Update (M-step): Recompute each centroid μk\mu_k as the arithmetic mean of assigned points.

🔄 Tensor Dimensions & Shape Flow

x: (N, D), centroids: (K, D) -> dists (N, K) -> labels (N,) -> new_centroids (K, D)

🛡️ Numerical Stability & Pitfalls Checklist

  • Handle empty clusters cleanly (e.g., re-seed from a random data point) to avoid NaN centroids.
  • Use K-Means++ initialization to spread starting centroids and improve convergence.

💻 Reference Code Implementation

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

🧪 Runnable Assertions & Validation

Copy and run directly in 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 聚类算法自测通过")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:What is the exact theoretical connection between K-Means and Gaussian Mixture Models (GMM)?
K-Means is the zero-variance isotropic limit of GMM under EM: when all Gaussian components share covariance σ2I\sigma^2 \mathbf{I} and σ2→0\sigma^2 \to 0, soft posterior responsibilities collapse to hard 0/1 nearest-centroid assignments.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Flow Matching Velocity Field ObjectiveBack to Part L & All 105Next: Linear Regression: Closed-Form & Gradient Descent →