知识卡片
k-means++ 选初始中心
K-Means 的第一步是从样本里随便挑 K 个点当初始中心。这一步的风险在于偶然性:如果几个初始中心恰好挤在同一片稠密区域,它们会一起收敛到同一个簇,剩下的簇只能靠远处的点勉强撑起,迭代次数变多、结果变差,甚至停在明显不合理的局部最优上。
k-means++ 的思路是让初始中心”彼此尽量远离”,把随机性从”随便挑”改成”有约束地挑”:
- 随机选 1 个样本作第一个中心 μ₁。
- 计算所有样本到已有中心的距离,把每个样本归到最近的中心。
- 把”离自己所属中心最远的那个样本”选为新中心。远的点最可能是另一个簇的代表,选它相当于优先覆盖尚未被代表的区域。
- 重复 2、3,直到凑满 K 个中心;然后用这 K 个中心作为初始值,跑标准 K-Means 流程。
代价是要多算几轮距离,但换来的是更少的迭代次数和更稳的结果,所以 scikit-learn 把它设为 init 的默认值(另一个选项是 random)。它改善的是”起点”,并不改变 K-Means 只能收敛到局部最优的本质——真正的兜底仍是多跑几组初值(n_init),见 [[K-Means调参的四个抓手]]。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第12章 聚类
原书出处 · 1 处
- 第12章 聚类 12.2.2 K-Means算法优化 · 查看原书依据
前面说过,K-Means算法中K个聚类中心的初始值选择会直接影响需要迭代的次数,传统的K-Means算法是先随机从M个样本点中选择K个点作为聚类中心点的初始值,但这样有较大的偶然性,并不是最好的方法。
参考来源
- 位置:《机器学习基础:从入门到求职》第12章《第12章 聚类》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00015.html)
- 结论依据:原文指出随机选初始中心"有较大的偶然性,并不是最好的方法",并给出 k-means++ 的四步流程:随机取一点、反复把离自身中心最远的样本加入中心集,凑满 K 个后再跑 K-Means。
- 原始内容:前面说过,K-Means算法中K个聚类中心的初始值选择会直接影响需要迭代的次数,传统的K-Means算法是先随机从M个样本点中选择K个点作为聚类中心点的初始值,但这样有较大的偶然性,并不是最好的方法。