O5MediumPart O · BA-to-Python Data Science & Stats Kernels

K-Means++ D-Squared Initialization for RFM & Codebooks

⚡Flashcard Drill➔

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?
Next: Robust Data Contract Gate (NaN Rate + Median-MAD Z-Score) →
💡

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 ii proportional to squared distance D(x)2D(x)^2 from the closest existing centroid, guaranteeing an O(log⁡K)O(\log K) 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.
🎯 Drill This Card Now➔
← Prev: Vectorized Out-of-Order Event Stream Sessionization (SQL LAG to NumPy)Back to Part O & All 105Next: Robust Data Contract Gate (NaN Rate + Median-MAD Z-Score) →