跳到主要内容

K-means++

一、直观理解：让初始中心尽量“彼此远离”​

标准 K-means 若随机抓 KK 个点当种子，可能多个中心挤在同一团，另一团无人问津，迭代陷入差局部最优。

K-means++ 改进的是初始化：

  1. 第一个中心均匀随机选；
  2. 之后每个中心被选中的概率与它到已有最近中心的距离平方成正比——离现有中心越远，越容易被选中；
  3. 选满 KK 个后再跑普通 Lloyd 迭代。

这像在地图上开连锁店：第一家随便开，后面优先覆盖空白商圈，而不是扎堆。

二、适用场景与优缺点​

类型说明
适用场景凡使用 K-means 之处；希望减少坏初值；KK 中等、欧氏平方距离目标。
核心优点理论保证期望 SSE 有近似比；实践中常更快收敛、结果更稳；实现成本低。
局限与缺点仍是 K-means 家族，不解决非球状簇与 KK 选择；初始化本身 O(K)O(K) 遍扫描；极端噪声点可能因“远”被选成中心。

MATLAB 的 kmeans 在较新版本中默认或可选 Start="plus"，即 K-means++。

三、核心原理​

记已选中心集合 CC。对未选点 xx，令 D(x)=min⁡c∈C∥x−c∥2D(x)=\min_{c\in C}\|x-c\|^2。下一个中心以概率

P(x)=D(x)∑x′D(x′)P(x)=\frac{D(x)}{\sum_{x'}D(x')}

抽取。直觉：覆盖当前代价（距离平方）大的区域。

Arthur & Vassilvitskii 证明：K-means++ 初始化得到的期望目标值满足相对最优的 O(log⁡K)O(\log K) 近似比（在一定意义下），显著优于纯随机初始化的最坏情况。

之后仍最小化

J=∑imin⁡k∥xi−μk∥2J=\sum_{i}\min_{k}\|x_i-\mu_k\|^2

故一切 K-means 的形状假设仍然成立。

四、关键决策​

决策点建议
是否启用默认启用 K-means++
仍需多重启Replicates 建议 ≥5–10，++ 不是万能
噪声极端远点可能成种子，可先缩尾/去异常
与随机对比 Start="sample" 与 "plus" 的 SSE 分布
KK、标准化与普通 K-means 完全相同

五、MATLAB 示例​

rng(0);
X = [randn(40,2)+[0 0]; randn(40,2)+[5 0]; randn(40,2)+[2 4]];
Xz = zscore(X);
K = 3;

% K-means++ 初始化
[idx1, C1, sumd1] = kmeans(Xz, K, ...
    "Start", "plus", ...
    "Replicates", 1, ...
    "MaxIter", 200);

% 纯随机采样初始化对照
[idx2, C2, sumd2] = kmeans(Xz, K, ...
    "Start", "sample", ...
    "Replicates", 1, ...
    "MaxIter", 200);

fprintf("++  的 SSE = %.3f\n", sum(sumd1));
fprintf("随机 SSE = %.3f\n", sum(sumd2));

% 多次重启下的 SSE 分布
nTry = 20;
ssePlus = zeros(nTry,1); sseSamp = zeros(nTry,1);
for t = 1:nTry
    [~,~,sd] = kmeans(Xz, K, "Start","plus",  "Replicates",1);
    ssePlus(t) = sum(sd);
    [~,~,sd] = kmeans(Xz, K, "Start","sample","Replicates",1);
    sseSamp(t) = sum(sd);
end
figure;
boxplot([ssePlus, sseSamp], "Labels", {"K-means++","Random"});
ylabel("SSE"); title("不同初始化的 SSE 分布");

% 手写 K-means++ 选种子（便于论文写清算法）
function C = kmeanspp_seeds(X, K)
    n = size(X,1);
    C = zeros(K, size(X,2));
    C(1,:) = X(randi(n), :);
    for k = 2:K
        D = min(pdist2(X, C(1:k-1,:)).^2, [], 2);
        p = D / sum(D);
        C(k,:) = X(randsample(n, 1, true, p), :);
    end
end

seeds = kmeanspp_seeds(Xz, K);
[idx, C] = kmeans(Xz, K, "Start", seeds);
figure; gscatter(Xz(:,1), Xz(:,2), idx); hold on;
plot(C(:,1), C(:,2), "kp", "MarkerSize", 12, "MarkerFaceColor","y");
title("K-means++ 种子启动后的聚类");

六、如何解释结果​

  1. 对比 SSE/轮廓：++ 是否降低坏结果频率；
  2. 初始中心位置：是否落在不同高密度区；
  3. 仍失败的情形：严重重叠、错误 KK、非球状；
  4. 报告：Start="plus"、Replicates、最终 SSE、簇画像。

七、常见误区​

1. 以为 K-means++ 会自动选 KK​

它只改进初值，不选簇数。

2. 开了 ++ 就只跑 1 次​

复杂数据仍需多次复制取最优。

3. 与 K-means 写成两种完全不同的模型​

主体相同，差别在初始化。

4. 把最远点启发式当成 ++​

“每次选最远点”是确定性的，与概率版 ++ 不同，也更怕离群点。

5. 忽略标准化​

初始化与迭代都依赖距离，尺度问题依旧。

附：建模论文中的写法要点​

  1. 问题对应：用一两句话说明为何该方法匹配题目数据结构与目标（分类/分群/排序/效率）。
  2. 符号与步骤：按“输入 → 预处理 → 核心计算 → 输出指标”列出编号步骤，公式与代码变量名一致。
  3. 参数表：列出全部可调参数、取值、选取依据（CV、信息准则、业务约束或灵敏度）。
  4. 结果呈现：主结果用表格；辅以 1–2 张图（边界、树状图、得分条形图、效率分解等）。
  5. 稳健性：至少做一种扰动——删点、换权重、换距离、换初值或换阈值，观察结论是否保持。
  6. 局限：主动写明假设（球状簇、线性可分、CRS、完全补偿等）及适用边界，避免被质询时被动。

若主方法结论与合理基线（如 K-means 对 GMM、加权和对 TOPSIS、CCR 对 BCC）严重冲突，应回到数据质量与指标方向检查，而不是只报告“更好看”的一种结果。

八、小结​

K-means++ 用“距离平方加权”的方式分散初始中心，从源头减少 K-means 掉进差局部最优的概率。

实践中应作为 K-means 的默认启动策略，并与标准化、多重启和 KK 选择一起构成完整流程。