K-means clustering algorithms: A comprehensive review, variants analysis, and advances in the era of big data

摘要

在大数据时代，最近的科学数据收集技术的进步允许在各种数据采集地点系统地积累大量数据。同样，不同数据分析方法的指数增长，其中K-means算法仍然是最流行和最直接的聚类算法。该算法在许多聚类应用领域的广泛适用性可以归因于其实现的简单性和计算复杂度低。然而，K-means算法存在许多对其聚类性能的负面挑战。在算法的初始化过程中，用户必须随机选择给定数据集中的集群数量，而初始集群中心是随机选择的。此外，该算法的性能易受初始聚类选择的影响，对于大型数据集，确定最优的集群数量变得复杂，是一项非常具有挑战性的任务。此外，由于初始聚类中心的随机选择，有时会导致最小的局部收敛。进一步的限制是，某些数据对象特征通过使用欧氏距离度量作为相似性度量来确定其相似性，但这限制了算法在检测其他聚类形状时的鲁棒性，并对检测重叠聚类提出了很大的挑战。关于提高K-means算法的性能和鲁棒性，已经在文献中进行了许多研究和报道。目前的工作提出了K-means聚类算法及其变体的概述和分类。本文还讨论了k均值的历史、当前的趋势、开放的问题和挑战，以及未来的研究前景。

1.介绍

从收集的数据中提取有意义和有形的信息是数据挖掘[4]的主要目标。然而，大多数数据都是以任意的形式和类别收集的，这使得这些数据难以分析，特别是当数据对象的特征未知时。未标记数据的适当组织是由聚类分析处理的数据挖掘的一个方面。将这些未标记的数据进行有意义的分组视为数据聚类。其目标是对未标记的数据进行分组，使其特征和属性相似的数据对象聚集在一个集群中，从而使同一集群中的数据对象的相似性比其他集群中的数据对象的相似性更高。换句话说，数据聚类分析对未标记数据进行分类，以确保较高的簇内相似度和较低的簇间相似度[59]。聚类分析的过程可以比作学习过程，当处理无标记数据集[55]时，它涉及到与无监督学习相关的特定预测行为。图1清楚地说明了模式识别和机器学习中感兴趣的不同类别的学习问题，如Jain [95]中所讨论的。

图1。聚类分析被认为是一个学习问题。图上的点对应于没有标签的点。相反，带有标签的点用加号、星号和叉号表示。在(c)中，必须链接和不能链接约束分别用实线、虚线和虚线表示。

聚类分析已成功应用于解决不同领域的数据聚类问题，如医学、制造、机器人、金融部门、隐私保护、人工智能、城市开发、航空、行业、销售和营销[61,7,180,59,20,111,49]。从这些领域的数据中提取有用的信息对于提供更好的服务和产生更多的利润[181,148,172]至关重要。生成的真实数据大多是大量的、未标记的和不同的维度。这使得数据集群变得困难。不能快速地预先识别真实数据集中的集群数量。因此，对于标准的聚类算法来说，确定一个具有高密度和维数特征的真实数据集中的最优聚类数量是相当棘手的。这对传统的聚类算法提出了一个重大的挑战，其中集群的数量必须被指定为算法的输入。
数据聚类算法分为两大类，即层次聚类算法和分区聚类算法。分层聚类算法以分层的形式将数据对象划分为集群，可以采用自下而上的方法（凝聚方法）或自上而下的方法（划分方法）。在凝聚方法中，单个数据对象根据它们的相似性进行迭代合并。在分裂法中，将初始数据集视为单个聚类，并使用数据对象相似度进行迭代分解，直到每个数据对象形成一个聚类或满足一个集合准则。层次聚类算法生成合并（凝聚）或分裂（分裂）数据对象的树状图，描述相应的聚类层次结构作为聚类分析[60]的输出。树状图是数据对象嵌套分组的图形表示，显示每个分组更改[97]的相似性级别。
在分区聚类方法中，生成一个初始数据集的单一分区，而不是一个树状图的聚类结构。集群是以启发式方法产生的，同时优化一个全局定义在集合中所有数据对象上的标准函数，或者局部定义在数据对象[246,9,189]的子集上。使用对所有可能的值的组合搜索来优化一组数据对象上的标准函数，以得到最优值，这在计算上是不可能的。因此，分区聚类算法需要指定在不同运行时提供的不同k值，以获得产生最优聚类的最佳配置。
K-means聚类算法是由不同学科的研究者独立提出的，包括20世纪50年代和60年代的JacQueen[135]和Jancey [98]。这些研究人员的不同版本的算法显示了四个常见的处理步骤，每个步骤[171]都不同。K-means聚类算法使用聚类的对象均值[197,34]生成聚类。在标准的K-means算法中，需要聚类号作为用户参数，用于从数据集的任意聚类中心选择。然而，由于其贪婪性质[95]，均值算法可能收敛到局部最小值。因此，对于给定的k值，需要选择不同的初始聚类中心进行多次运行，才能得到最优的聚类结果[243,59,19]。此外，标准算法检测球形或球形聚类，只是因为使用欧几里得度量作为其距离度量[95]。一个典型的k均值聚类过程如图2所示。

图2。K-means聚类： (a)随机分布的数据集和(b)最近的聚类质心，有三个聚类[142]。

通过向K-means聚类算法提供一组输入数据，可以很容易地识别质心向量\(C=\{c_{1},c_{2},...,c_{k}\}\)，K是由用户定义的质心的数量。图2a显示了一个在二维空间中随机分布在\(-100\leq x_{i},y_{i}\leq100\)中的数据集，图2b显示了K-means聚类结果，质心数设置为K=3。
尽管有这些限制，K-means聚类算法被认为具有灵活性、效率和易于实现。它也是数据挖掘[59,217,105,94]中的十大聚类算法之一。K-means聚类算法的简单性和低计算复杂度使得K-means聚类算法在许多领域被广泛用于解决聚类问题。为了提高其性能，已经开发了几种K-means聚类算法。本项工作概述了K-means聚类算法及其变体，并提出了对变体的分类法。并详细讨论了该算法从一开始的研究进展、当前的趋势、开放的问题和未来研究前景的挑战。
本文提出了以下重点研究问题，以反映这项综合综述工作的目的：
“自成立以来，解决聚类问题的k均值算法的现有变体是什么？”在提供主要研究问题的答案时，我们考虑了以下子研究问题：

a. 确定为改进标准K-means聚类算法而进行的研究
b. 在(a)的各种研究中，采用了哪些方法来提高K-means聚类算法的性能？
c. 所报告的K-means聚类算法变量的性能如何？
d. 目前涉及K-means聚类算法的研究进展如何？

本综述工作将从四个角度提出：首先，系统地回顾K-mean聚类算法及其变体。其次，在文献中提出了一种新的K-means聚类方法的分类方法。第三，通过深入分析验证K-means聚类方法各个方面的结果。第四，概述开放的问题和挑战，并建议未来的趋势。主要思想是提出一个全面的系统回顾，将为当前的研究人员和从业者提供未来涉及K-means聚类算法的新研究的途径。本研究工作的主要贡献总结如下：

对K-means算法进行了全面的回顾，包括提出了最近变异的变异分类和K-means聚类算法的趋势应用领域。
本文确定并讨论了有关采用元启发式算法作为自动聚类数生成器来提高K-means算法的性能质量的公开研究问题。
最后，确定了K-means算法的研究差距和未来范围，特别是在概述解决K-means聚类算法及其变体挑战的新视角方面。

本文的其余部分组织如下：第1节介绍了拟议的审查研究的背景工作；第2节概述了方法；第3节提出了文献中K-means聚类方法的分类，然后详细讨论了K-means算法变体的审查；第4节讨论了审查结果；第5节报告了K-means算法目前正在应用的趋势领域；第6节概述了K-means聚类方法的开放问题和挑战；第7节总结了回顾。

2.研究方法

2.1.相关文献的检索策略和关键词

2.2.搜索结果

2.3.文章的筛选和选择标准

2.4.与现有勘察工作的比较

3.标准的K-means聚类算法

3.1.K-means计算复杂度分析

3.2.K-means变异体的分类法

3.3.K-means算法设计变体

3.3.1.算法输入修改

a.)数据集预处理

Huang[88]等人[88]提出了一种鲁棒的深度k-均值，作为一种简单有效的数据聚类方法，以避免标准单层公式的问题，该公式包含基于数据集复杂层次信息的数据聚类。他们提出的算法采用深度学习技术来提取深度表示，以提高聚类性能，使用深度K-means模型来学习隐式底层属性的隐藏表示。Lithio和Maitra [131]提出了Km-means算法作为Kmeans算法的一种有效变体，该算法允许对具有不完整记录的数据集进行聚类。当数据集有完整的记录时，该算法被简化为标准的K-means算法。Km-means算法还配备了初始化策略和方法来估计数据集中的簇的数量。Marom和Feldman [139]提出了一种用于大数据聚类线的Kmeans变体。当一些或所有输入向量中缺失条目，有时数据集中信息不完整时，k均值变量的问题就出现了。这个问题的一个例子在计算机视觉中很典型，一个点或k个点的位置根据它们通过针孔相机模型对二维图像的投影转换成线。在矩阵近似理论和数据科学中，考虑了数据库记录中缺失条目的所有可能值，从而将一个点变成了一条直线。然后，聚类过程考虑在k均值中心周围相交的线。

b.)自动规格化的K

c.) 改进了初始质心的选择

3.3.2.算法处理增强

a.)数据对象分配过程的修改

b.)迭代减少变体

3.3.3.算法输出改进变量

a.)检测其他形状的簇

b.)模糊团簇

c.) 粗糙的集群

d.) 重叠的集群

3.4.算法的概念修改

3.4.1.一般算法的概念修改

3.4.2.杂交变体

3.5.算法实现变量

3.5.1.并行操作机的实现

3.5.2.量子机的实现

3.5.3.MapReduce框架的实现

3.5.4.其他实现范例

4.讨论

5.K-means算法的趋势应用领域

6.开放的问题和挑战

7.结论

K-means聚类算法以其简单性而闻名，并应用于不同领域的数据集聚类。尽管有这种优势，但由于其实现过程中固有的一些问题，其性能受到了极大的阻碍。因此，为了提高算法的总体性能，人们进行了大量的研究。这项综述工作已经能够识别出标准算法的各种局限性，以及为解决本综述工作之前所确定的问题而开发的众多变体。本文将有利于致力于扩展现有变体以实现更鲁棒和可扩展的基于k-means的聚类技术的研究人员，以及对使用标准算法的最先进的变体来满足其领域的数据聚类需求感兴趣的从业者。对现有的基于k-means的算法有问题的从业者可以很容易地识别哪种变体将充分满足他们的应用需求，或者识别可以采用的改进他们现有算法的方法。
本研究的结果表明，人们非常关注解决K-means算法的初始化问题，而很少关注解决混合数据类型的问题。目前正在研究一些新技术，如MapReduce、并行实现和基于内核的实现，以使用标准算法解决大数据聚类问题。标准算法与自动聚类的元启发式算法的杂交是一个新的和即将到来的领域，到目前为止所做的工作很少。据报道，只有少数现有的元启发式算法与标准算法相结合来解决收敛到局部最优的问题。未来的研究可以研究自动聚类算法，混合标准或变体与其他群体智能元启发式算法。寻求基于标准算法或其变体设计改进的自动聚类的研究人员和从业者将会发现这项调查非常有用。