K-means聚类
- 提出者
- MacQueen, J. B.; Lloyd, S. P.
- 年份
- 1967 (formalized 1982)
- 类型
- Partitional clustering
- 类别
- Machine learning
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
K-means是一种经典的无监督划分聚类算法,它通过迭代地将每个观测值分配给其最近的质心,并以分配点的均值更新质心,将数据集划分为K个互不重叠的组。它是机器学习和数据分析中最广泛使用的探索性工具之一。
方法背后的直觉
想象一下在数据点地图上放置K个磁铁。每个点都被吸引到最近的磁铁,然后每个磁铁移动到它所吸引点的重心。重复这个拉动-移动周期,直到没有任何东西移动:磁铁已经找到了K个自然分组。K-means精确地形式化了这个想法,最小化了每个点到其簇中心的总平方距离,称为簇内平方和(WCSS 或 inertia)。
历史学
K-means的思路由MacQueen于1967年独立提出并创造了该术语,并由Bell Labs的Stuart Lloyd在20世纪50年代(1982年发表)形式化为一个有效的迭代算法。Arthur和Vassilvitskii于2007年提出的k-means++初始化改进解决了局部最小值敏感性问题。如今,k-means仍然是几乎所有数据科学课程中教授的基石性无监督学习方法。
何时使用
K-means适用于大型、纯数值数据集的探索性聚类,当你需要快速、可扩展的分区,并且能够预先指定K或使用肘部法则或轮廓系数方法搜索K时。它适用于客户细分、图像压缩、文档主题分组以及监督学习之前的预处理。当簇呈非球形、大小或密度差异很大时,当特征是分类或有序的(改用k-modes或k-prototypes)时,当簇的数量完全未知且无法进行K值实验时,或者当数据包含许多异常值时(改用DBSCAN或鲁棒变体),应避免使用它。
局限与注意事项
- 需要预先指定K;错误地选择K会产生无意义的簇。
- 假设簇是球形、大小相似的;细长、不规则或尺度差异大的簇会被错误地分割或合并。
- 对异常值敏感:单个极端点会将质心拉离簇的大部分区域。
- 仅适用于数值连续特征;分类数据需要不同的算法(k-modes)。
- 收敛到局部最小值;在不同随机种子下运行结果可能不同,除非使用k-means++或多次重启。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 快速且可扩展:每次迭代的复杂度为 O(nKdi),在具有中等K和维度的数百万个观测值上是实用的。
- 易于实现,在所有主流机器学习框架中广泛可用,并且易于向非技术受众解释。
- 在大型、分离良好、大致呈球形且大小相似的簇上效果很好。
- k-means++初始化相比于随机初始化,大大降低了对起始条件的敏感性。
- 在固定的随机种子下是确定性的,使得结果可复现。
应用
- 基于行为或人口统计学特征的营销和个性化客户细分。
- 通过将像素颜色量化为K个代表性值(颜色量化)来进行图像压缩。
- 文档和文本聚类,作为向量化后主题建模管道中的一个步骤。
- 异常检测预处理:远离任何质心的点是潜在的异常值。
- 更复杂算法(如高斯混合模型或层次聚类)的初始化步骤。
- 基因表达分析,用于对具有相似表达谱的基因或样本进行分组。
使用方式
使用方式
在特征空间中放置K个簇质心,可以通过随机选择K个数据点(Forgy方法)或更智能的k-means++策略来完成,后者通过分散初始质心来减少陷入不良局部最优解的可能性。初始化的选择很重要:k-means++通常能更快收敛并获得更好的最终结果。
根据欧氏距离,将每个观测值分配给质心最近的簇。这种硬分配创建了数据的K个互不重叠的分区。形式上,每个点 x_i 被分配到簇 c_i = argmin_k ||x_i - mu_k||^2。
公式
c_i = \arg\min_k \|x_i - \mu_k\|^2
每个质心被重新计算为当前分配给该簇的所有点的算术平均值:mu_k = (1/|C_k|) * sum(x_i for x_i in C_k)。此步骤保证了在给定当前分配的情况下,新质心最小化了每个簇内的WCSS。
公式
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i分配和更新步骤交替进行,直到质心位置不再变化(或变化小于某个容差阈值),或者达到最大迭代次数。该算法保证收敛到WCSS的局部最小值,但不一定是全局最小值。
解决方案的质量通过总WCSS(inertia)J = sum(sum(||x_i - mu_k||^2 for x_i in C_k) for k in clusters) 来评估。选择K是一个单独的问题,可以通过肘部法则、轮廓系数或差距统计量来解决,因为算法本身要求预先指定K。
公式
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2常见陷阱
- 在聚类之前忘记标准化特征——尺度大的变量将主导距离计算。
- 仅通过样本内WCSS选择K,而没有肘部图或轮廓系数验证,导致K值过小或过大。
- 只进行一次初始化,并接受第一个结果,而不进行多次重启以防范不良的局部最小值。
- 在特征矩阵中包含分类或有序变量,而没有适当的编码或切换到k-modes。
- 将簇标签视为有意义的组身份,而没有外部验证,尤其是在簇未充分分离的情况下。
常见问题
如何选择合适的簇数量K?
对一系列K值运行k-means,绘制簇内平方和与K的关系图,寻找下降速率急剧减缓的“肘部”。用轮廓系数来补充,它衡量每个点与其自身簇相比于邻近簇的相似度;较高的平均轮廓系数表示簇定义更清晰。
为什么每次运行的结果都不同?
K-means对初始化敏感,并且收敛到WCSS的局部最小值而非全局最小值。使用k-means++初始化并设置固定的随机种子以保证可复现性。多次使用不同种子运行算法并保留具有最低惯量(inertia)的解是一种良好的实践。
K-means是否适用于分类数据?
否。K-means依赖于欧氏距离和质心均值,而这些对于分类变量是未定义的。对于纯分类数据,使用k-modes;对于混合数值和分类数据,使用k-prototypes。
何时应优先选择DBSCAN或GMM而非k-means?
当簇形状不规则或需要自动异常检测而无需指定K时,使用DBSCAN。当需要软(概率性)簇分配或大小和方向不同的簇时,使用高斯混合模型(GMM),但计算复杂度更高。
我需要对特征进行缩放吗?
是的,几乎总是需要。K-means使用欧氏距离,因此数值范围大的特征将主导聚类。在拟合k-means之前应用z-score标准化或min-max缩放,除非所有特征已经处于同一尺度。
相关方法
参考文献
Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.
打开 DOI 文献已复制。MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
打开出版物文献已复制。