O5MediumPart O · BA-to-Python Data Science & Stats Kernels
K-Means++ D-Squared Initialization for RFM & Codebooks
Implement K-Means++ seeding with distance-squared probability sampling and O(ND) incremental nearest-distance tracking.
⏱️ Time:
O(K * N * D)💾 Space:
O(N + 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_pp_init(X: np.ndarray, k: int, seed: int = 42) -> np.ndarray:
rng =
n, d = X.shape
centroids = np.empty((k, d), dtype=np.float64)
first_idx = int(rng.integers(0, n))
centroids[0] = X[first_idx]
min_sq_dist = np.sum((X - centroids[0]) ** 2, axis=1)
for i in range(1, k):
total = float(min_sq_dist.sum())
if total <= 1e-12:
centroids[i] = X[int(rng.integers(0, n))]
continue
probs = min_sq_dist / total
next_idx = int(rng.choice(n, p=probs))
centroids[i] = X[next_idx]
new_sq_dist = np.sum((X - centroids[i]) ** 2, axis=1)
min_sq_dist =
return centroids
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: Why does unscaled RFM clustering usually collapse onto Monetary outliers?
Q2: Where else does K-Means++ appear inside AI Infrastructure?
💡
Core Mental Anchor / Mnemonic
Sample proportional to squared nearest distance, update with running minimum
📐 Mathematical Derivation & Core Formula
$$P(x_i) = \frac{D(x_i)^2}{\sum_j D(x_j)^2},\quad D(x_i) = \min_{c \in \mathcal{C}} \|x_i - c\|_2$$
Rather than uniform random seeding, K-Means++ samples centroid proportional to squared distance from the closest existing centroid, guaranteeing an competitive expected objective bound while incremental
np.minimum maintains linear time per step.🔄 Tensor Dimensions & Shape Flow
X: (N, D) -> incremental min_sq_dist: (N,) -> centroids: (K, D)
🛡️ Numerical Stability & Pitfalls Checklist
- Standardize skewed RFM features (log1p + z-score) prior to Euclidean clustering
- Guard against zero total squared distance on deduplicated or identical-point datasets
- Maintain running min_sq_dist instead of recomputing full pairwise (N, k) distance matrices each step
💻 Reference Code Implementation
import numpy as np
def kmeans_pp_init(X: np.ndarray, k: int, seed: int = 42) -> np.ndarray:
rng = np.random.default_rng(seed)
n, d = X.shape
centroids = np.empty((k, d), dtype=np.float64)
first_idx = int(rng.integers(0, n))
centroids[0] = X[first_idx]
min_sq_dist = np.sum((X - centroids[0]) ** 2, axis=1)
for i in range(1, k):
total = float(min_sq_dist.sum())
if total <= 1e-12:
centroids[i] = X[int(rng.integers(0, n))]
continue
probs = min_sq_dist / total
next_idx = int(rng.choice(n, p=probs))
centroids[i] = X[next_idx]
new_sq_dist = np.sum((X - centroids[i]) ** 2, axis=1)
min_sq_dist = np.minimum(min_sq_dist, new_sq_dist)
return centroids🧪 Runnable Assertions & Validation
Copy and run directly in Python / Jupyter:
rng = np.random.default_rng(0)
c1 = rng.normal([0, 0], 0.1, (20, 2))
c2 = rng.normal([10, 0], 0.1, (20, 2))
c3 = rng.normal([0, 10], 0.1, (20, 2))
X = np.vstack([c1, c2, c3])
cts = kmeans_pp_init(X, 3, seed=123)
d01 = np.linalg.norm(cts[0]-cts[1]); d02 = np.linalg.norm(cts[0]-cts[2]); d12 = np.linalg.norm(cts[1]-cts[2])
assert min(d01, d02, d12) > 5.0
print('O5 PASS')🎯 Core Follow-up Inquiries & Reference Answers
Q1:Why does unscaled RFM clustering usually collapse onto Monetary outliers?
Heavy-tailed revenue scales dominate day counts and frequencies by orders of magnitude under L2 distance unless log-transformed and standardized.
Q2:Where else does K-Means++ appear inside AI Infrastructure?
IVF coarse quantizer centroid training in vector databases (Qdrant/Faiss) and residual codebook initialization in audio/vision tokenizers.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.