K-均值聚类

K-均值聚类通过最小化到聚类质心的平方距离的总簇内和，将观测值划分为固定数量的簇。

Definition

K-均值聚类是一种分区方法，它设置预定数量的聚类中心，并将每个观测值分配到其最近的中心，以最小化观测值到其指定中心的总平方欧几里得距离。

Scope

本主题涵盖簇内平方和目标、在将点分配到最近质心和重新计算质心之间交替的迭代分配和更新算法、对初始化的依赖性以及由此产生的局部最优、簇数量的选择以及该方法的假设和局限性。

Core questions

• 如何划分观测值以最小化簇内离散度？
• 为什么该算法只收敛于局部最优，以及如何缓解这种情况？
• 如何选择簇的数量？
• 该方法隐含地假设了哪些簇形状和尺度？

Key theories

簇内平方和最小化

K-均值寻求使点到其聚类中心的总平方距离最小化的分区和质心集，对于这个目标，交替分配-更新迭代会单调地降低判据。

局部最优敏感性

由于目标是非凸的，该算法收敛于一个局部最小值，该最小值取决于初始中心，因此需要多次重新启动和仔细播种。

Clinical relevance

K-均值是一种快速、可扩展的默认方法，用于划分大型数据集，并应用于向量量化、图像颜色减少、客户细分以及作为更复杂模型的初始化。

History

基于质心的分区思想由MacQueen在1967年正式提出，他将该方法命名为K-均值，其基础是Lloyd早期的量化算法。由于其简单性和速度，它成为最广泛使用的聚类方法之一。

Debates

K-均值的隐含假设

最小化平方欧几里得距离倾向于大致球形、大小相等的簇，因此当簇是细长的、大小不相等或非凸时，K-均值可能会产生误导，这促使人们寻求基于模型或基于密度的替代方法。

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

为什么K-均值在不同的运行中会给出不同的结果？

其目标是非凸的，因此该算法收敛于一个局部最优，该局部最优取决于随机初始中心；多次运行并保留最佳结果是标准做法。

如何选择簇的数量k？

常见的启发式方法包括簇内平方和的“肘部法则”、间隙统计量和平均轮廓宽度，尽管没有一种是决定性的，并且领域知识通常指导选择。