L1Medium★ Core Essential · Industrial BedrockPart L · Classical ML & Statistical Simulation
K-Means Clustering from Scratch
Industrial-grade implementation and mathematical foundations of K-Means Clustering from Scratch.
⏱️ Time Complexity:
O(iters * N * K * D)💾 Space Complexity:
O(N * K + K * D)💡
Core Mental Anchor / Mnemonic
Master K-Means Clustering from Scratch: enforce numerical stability, check tensor shapes, and eliminate redundant memory allocations.
📐 Mathematical Derivation & Core Formula
### Mathematical Derivation & Theoretical Principles
Detailed first-principles formulation and architectural mechanics for K-Means Clustering from Scratch.
Refer to the LaTeX equation above for the core operator definition. The operator is designed to ensure strict numerical bounds, avoiding floating-point overflows and gradient anomalies.
Detailed first-principles formulation and architectural mechanics for K-Means Clustering from Scratch.
Refer to the LaTeX equation above for the core operator definition. The operator is designed to ensure strict numerical bounds, avoiding floating-point overflows and gradient anomalies.
🔄 Tensor Dimensions & Shape Flow
x: (N, D), centroids: (K, D) -> dists: (N, K) -> labels: (N,) -> new_centroids: (K, D)
🛡️ Industrial Numerical Stability & Pitfalls
- 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).
💻 Industrial 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 to verify correctness:
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 Architecture Follow-up Q&A
Q1:What are the key trade-offs and memory bottlenecks when deploying K-Means Clustering from Scratch in high-throughput inference?
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.
Q2:How does K-Means Clustering from Scratch handle extreme numerical boundaries or precision reduction (FP16/BF16/INT8)?
Under low precision, operations must be upcasted to FP32 during accumulation to prevent underflow/overflow, followed by proper scaling and clamping before converting back to the target format.