k-means算法研究综述-华夏学术资源库

k-means算法研究综述

摘要

k-means算法作为最经典、应用最广泛的聚类算法之一，自提出以来便在数据挖掘、机器学习和模式识别领域占据着核心地位，其核心思想简单直观：通过迭代优化，将数据点划分为k个簇，使得簇内数据点的相似度最大化（簇内距离最小化），而簇间数据点的相似度最小化（簇间距离最大化），尽管k-means算法简单高效，但其对初始值敏感、对非凸簇形状适应性差、需要预先指定k值等固有缺陷也限制了其应用，本综述旨在系统性地回顾k-means算法的理论基础、经典改进算法、关键挑战及其解决方案,并探讨其前沿应用与未来发展方向。

（图片来源网络，侵删）

聚类是无监督学习的关键任务，旨在将数据集划分为若干个不同的组（簇），使得同一簇内的数据点彼此相似，而不同簇的数据点彼此相异，在众多聚类算法中，k-means因其算法简单、易于实现、时间复杂度相对较低等优点，成为最常用的划分聚类算法之一，正是由于其简单性，也带来了诸多需要深入研究和解决的问题，本综述将围绕这些问题展开，深入剖析k-means算法的演进脉络。

k-means算法核心原理

k-means算法的目标是将一个包含n个数据点的数据集X划分为k个不相交的簇C₁, C₂, ..., Cₖ，其优化目标是最化化所有数据点到其所属簇中心的距离之和，通常称为簇内平方和。

1 数学模型

给定数据集 $X = {x_1, x_2, ..., x_n}$，$x_i \in \mathbb{R}^d$，目标是找到k个簇中心 $μ = {μ_1, μ_2, ..., μ_k}$ 和一个划分 $C = {C_1, C_2, ..., C_k}$,最小化以下目标函数：

（图片来源网络，侵删）

$$ J = \sum{j=1}^{k} \sum{x_i \in C_j} ||x_i - μ_j||^2 $$

$|| \cdot ||^2$ 是欧氏距离的平方，$μ_j$ 是簇 $C_j$ 的质心（Centroid）,计算公式为：

$$ μ_j = \frac{1}{|Cj|} \sum{x_i \in C_j} x_i $$

2 算法流程

（图片来源网络，侵删）

k-means算法通过迭代执行以下两个步骤直至收敛：

分配步骤：对于每个数据点 $x_i$，将其分配给距离最近的簇中心 $μ_j$ 所在的簇 $C_j$。 $$ C_j = {x_i : ||x_i - μ_j||^2 \leq ||x_i - μ_l||^2, \forall l = 1, ..., k} $$
更新步骤：重新计算每个簇 $C_j$ 的质心 $μ_j$，使其成为簇内所有点的均值。 $$ μ_j = \frac{1}{|Cj|} \sum{x_i \in C_j} x_i $$

这两个步骤交替进行，目标函数J单调递减，直至簇中心不再发生显著变化或达到预设的最大迭代次数,算法终止。

k-means算法的经典变体与改进

针对k-means的固有缺陷，研究者们提出了大量的改进算法，主要集中在初始化、距离度量、聚类过程和k值确定四个方面。

1 改进的初始化方法

k-means对初始簇中心的敏感性是其最主要的缺点之一，糟糕的初始化容易导致算法陷入局部最优解,且收敛速度慢。

Forgy方法：随机从数据集中选择k个数据点作为初始中心。
Random Partition方法：随机将每个数据点分配到k个簇中,然后计算初始质心。
k-means++算法：这是目前最主流的初始化方法，它通过一种概率化的方式选择初始中心，使得初始中心之间相互远离，从而显著提高算法找到全局最优解的概率，并加快收敛速度。
- 步骤：
  1. 随机选择一个数据点作为第一个初始中心。
  2. 计算每个数据点与最近已选中心的距离D(x)。
  3. 按照与D(x)²成正比的概率,随机选择下一个数据点作为新的中心。
  4. 重复步骤2和3,直到选出k个中心。

2 改进的聚类过程

k-medoids (PAM - Partitioning Around Medoids)：与k-means使用质心（均值）不同，k-medoids使用簇中实际存在的数据点（称为medoids，即中心点）作为簇中心，这使其对异常值更加鲁棒，因为均值对异常值非常敏感，而中位数则不然，但其计算复杂度高于k-means。
Fuzzy C-Means (FCM) 模糊C均值：传统k-means是硬划分，一个数据点只属于一个簇，FCM则引入了模糊隶属度的概念，允许数据点以不同的隶属度同时属于多个簇,这更符合现实世界中数据点边界模糊的特性。
Mini-Batch k-means：为了处理大规模数据集，该算法采用小批量数据来更新簇中心，每次迭代只使用一个随机抽取的小批量数据来近似计算梯度，从而大大减少了计算时间和内存消耗，虽然牺牲了一定的聚类精度,但在大规模数据场景下效率极高。

3 改进的距离度量

标准的k-means使用欧氏距离，这隐含地假设了数据是各向同性的（在所有方向上的方差相同）且簇是凸形的。

k-modes & k-prototypes：针对分类数据，k-modes使用匹配不相似度来代替欧氏距离，并使用modes（众数）作为簇中心，k-prototypes则将k-means和k-modes结合,用于处理包含数值型和分类型特征的混合数据集。
基于核函数的k-means：通过引入核技巧，将原始数据映射到一个高维特征空间，然后在该空间中执行k-means，这使得k-means能够发现原始空间中非凸的、复杂的簇结构，如环形、月牙形等。

4 动态确定k值

如何选择最优的簇数k是一个经典难题。

肘部法则：计算不同k值下的簇内平方和，绘制成曲线，当k值超过某个“肘点”后，J值的下降趋势会显著减缓，这个肘点被认为是较优的k值选择，缺点是肘点有时不明显,难以判断。
轮廓系数：该指标同时衡量簇的凝聚度（a，一个点到同簇其他点的平均距离）和分离度（b，一个点到最近簇中所有点的平均距离），轮廓系数S = (b - a) / max(a, b)，取值范围在[-1, 1]，S值越大，说明聚类效果越好，通过计算不同k值下的平均轮廓系数,选择使其最大的k值。
Gap Statistic：通过将数据集与参考分布（如均匀分布）进行比较，来评估聚类结果的优良程度，它衡量的是实际数据的簇内平方和与期望数据的簇内平方和之间的差距,选择使差距最大的k值。

关键挑战与应对策略总结

挑战	应对策略
对初始值敏感，易陷入局部最优	k-means++ 等智能初始化算法；多次运行取最优结果；模拟退火、遗传算法等全局优化算法与k-means结合。
只能发现凸形、球形簇	核k-means；使用谱聚类（先将数据图化，再在图上划分）。
对异常值敏感	k-medoids (PAM)；在计算质心前先对数据进行异常值检测和清洗。
需要预先指定k值	肘部法则、轮廓系数、Gap Statistic等评估指标；X-means、G-means等自动确定k值的算法。
对数据的尺度和分布敏感	数据预处理：对数值特征进行标准化或归一化。
难以处理高维数据	降维：在聚类前使用PCA、t-SNE等方法降维；子空间聚类：只关注与特定簇相关的维度。
只能处理数值型数据	**k-modes