O5MediumPart O · BA→Python 数据科学化与统计算子

K-Means++ D² 采样初始化(RFM 客群聚类与 Vector Quantization)

⚡闪卡盲测➔

手写实现带 $D^2$ 距离平方概率分布的 K-Means++ 质心初始化,并用增量最小值维护加速距离更新,避免重复扫描已选质心。

⏱️ 时间复杂度: O(K * N * D)
💾 空间复杂度: O(N + K*D)
🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
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 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: 业务上用 RFM(Recency, Frequency, Monetary)直接聚类为什么经常效果崩盘?
Q2: K-Means++ 思想在向量检索引擎(如 Faiss IVF 倒排索引)中怎么应用?
下一题: 抗离群鲁棒数据契约门禁(NaN 率 + Median-MAD Z-Score) →
💡

实战一句话记忆口诀

按 D² 加权轮盘抽,越远越易被选中,增量 minimum 省算力

📐 核心数学公式与机理推导

$$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$$
传统随机初始化极易陷入局部最优(多个质心落在同一大簇);K-Means++ 按当前各点到最近已选中心平方距离 D(xi)2D(x_i)^2 成正比抽取下一个质心,理论保证初始目标函数在 O(log⁡K)O(\log K) 竞争比之内。用向量维护 min_sq_dist = np.minimum(...) 将单步更新降至线性 O(ND)O(ND)。

🔄 张量维度与形状流转说明

X: (N, D) -> incremental min_sq_dist: (N,) -> centroids: (K, D)

🛡️ 数值稳定性自检与边界要点

  • 必须先对 RFM 等量纲差异大的特征做 Z-Score 或 log1p 归一化后再跑欧氏距离
  • 若样本存在大量完全重复点导致 total <= 1e-12,须做好除零兜底
  • 维护增量 min_sq_dist 避免每轮重复计算 N×i 个点对距离矩阵

💻 完整参考代码实现

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

🧪 本地测试与正确性断言

可直接复制到本地 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')

🎯 核心工程追问与标准应答

Q1:业务上用 RFM(Recency, Frequency, Monetary)直接聚类为什么经常效果崩盘?
客单价 Monetary 常呈长尾幂律分布(几倍于 Recency),不先做 log1p 变换和标准化会导致欧氏距离完全被金额单维度统治。
Q2:K-Means++ 思想在向量检索引擎(如 Faiss IVF 倒排索引)中怎么应用?
构建百万级以上向量库 IVF-PQ 量化码本时,先做规范化与 K-Means++ 播种可大幅减少空桶率并提高残差量化召回精度。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!
🎯 立即在闪卡中盲测此题➔
← 上一题: 无 SQL 窗口函数手写乱序事件流 Session 切分算子返回 Part O 与全部 105 题下一题: 抗离群鲁棒数据契约门禁(NaN 率 + Median-MAD Z-Score) →