适用于大型数据集的叠加k均值聚类算法

《Neurocomputing》：An overlapping k-means clustering algorithm for large datasets

　　

摘要

重叠聚类允许对象属于多个簇（多重分配），这一特性在文档组织、社交网络分析以及入侵检测等领域非常有用。在用于重叠聚类的算法中，基于重叠k均值算法的算法最为常见。现有研究中有一些基于OKM的算法能够生成良好的聚类结果，但当数据集规模变大时，这些算法的运行时间会显著增加，而如今大型数据集越来越常见。本研究提出了OKCLD，这是一种专为处理大型数据集设计的重叠k均值聚类算法。该算法首先将数据集分解为较小的子集，从每个子集中选取具有代表性的对象，通过重叠k均值算法构建重叠簇，再基于这些代表性对象构建出的重叠聚类结构，对整个大型数据集进行聚类处理。我们的研究结果具有重要意义，因为所提出的算法在聚类质量上与目前最优秀的重叠k均值聚类算法相当，同时还能在不牺牲聚类质量的前提下，更快地处理大型数据集。

引言

数据聚类是一种模式识别技术，它根据对象的相似性将对象分类到不同的簇中[1]。这项技术已被广泛应用于多个研究领域，用于解决图像分割[2]、异常检测[3]、文本分类[4]等诸多问题[5]、[6]。目前大多数已报道的聚类算法所生成的簇中，每个对象仅属于一个簇[7]、[8]。而另一些较少被研究的聚类算法则可以将对象分配到多个簇中[9]，也就是能够实现重叠聚类。重叠聚类算法有助于解决生物数据分析[10]、疾病分析[11]、社交网络分析[12]等其他领域的难题[13]、[14]。

已有不少算法通过结合或改进传统算法来生成重叠簇[9]、[15]。其中，应用最广泛且效果最好的重叠聚类算法就是重叠k均值算法，它以其简洁性和高效性著称。因此，已有不少改进版的重叠k均值聚类算法提升了聚类质量[9]、[15]，同时也有研究提出了相关的噪声检测方法[16]、[17]。尽管重叠k均值算法概念简单且被广泛采用，但其存在一些局限性，使得它们难以应用于大型数据集。现有的算法往往依赖迭代的多重分配策略，比如反复计算对象的“特征向量”，或者依赖全局距离阈值。与传统k均值算法中每个对象仅被分配到最近的单一簇不同，重叠k均值算法会不断评估一个对象是否应该属于其他簇。因此，在确定最终归属之前，对象可能需要经过多次成员资格评估和目标函数计算。

由此可见，多重分配过程需要持续计算对象与簇之间的距离，在某些方法中还需要计算对象之间的相互距离。这些重复的计算带来了巨大的计算开销，使得重叠k均值算法在处理大型数据集时成本极高。此外，那些用于处理对象多重归属的策略也限制了现有算法的可扩展性，这凸显出当前研究领域在开发高效、低成本且能处理大型数据集的算法方面存在的重大方法论缺口。为弥补这一缺口，我们提出了OKCLD，这是一种采用“分而治之”策略的算法，旨在降低运行时间。通过将大型数据集分解为较小的子集，仅对其中具有代表性的对象应用重叠k均值算法，OKCLD避免了大规模全局距离计算的巨大成本。这样一来，该算法既能够在不牺牲计算效率的前提下实现重叠聚类，又能够处理大型数据集。

针对上述问题，我们提出了OKCLD，这是一种高效的“分而治之”算法，它通过将可扩展性约束与重叠分配阶段分开，降低了计算复杂度。本文提出了一种发现间接重叠关系的新机制：实验表明，没有必要对整个数据集进行处理，只需对数据集进行划分，将计算负担转移到规模为$$的局部平衡子集上即可。这一目标的实现依赖于这样一个事实：诸如带有$$的聚类算法就能够成功提取出局部的结构代表点（即质心）。此外，实验还表明，复杂的多重分配函数也可以在代表性对象上进行分析计算。该算法还针对规模过大的代表性对象集合提出了递归处理策略，同时设计了一种直接映射函数，能够将基于代表性集合发现的重叠聚类结构映射回整个数据集，且不会影响重叠聚类的质量，这一点在我们的后续实验中也得到了验证。由于重叠聚类步骤仅在代表性集合上执行，因此该算法可以与其他任何基于重叠k均值的聚类算法相结合，从而让这类算法也能应用于大型数据集。

本文的其余部分结构如下：第2节回顾相关研究；第3节介绍所提出的算法，第4节会对该算法进行评估；最后，第5节总结本文的研究结论。

章节节选

相关研究

多年来，已有不少算法被提出用于实现重叠聚类功能。有研究对这些算法进行了分类：包括图论相关算法[18]、[19]、[20]、[21]，层次结构相关算法[22]，相关性相关算法[23]、[24]，基于分割的算法[9]、[25]、[26]，生成模型相关算法[27]、[28]、[29]，以及拓扑结构相关算法[30]、[31]。不过近年来，又出现了一些不属于上述任何类别的重叠聚类算法，比如基于三向关系的算法[32]、[33]、[34]。

所提出的算法

如前文所述，基于k均值的重叠聚类算法因结构简单且聚类质量优异而被广泛使用。不过，如何处理大型数据集的重叠聚类问题目前研究尚不多，而且这类算法在处理大型数据集时的计算量远高于传统k均值算法。因此，我们提出了一种新的算法OKCLD，该算法采用了“分而治之”的策略，而这种策略本身就被广泛用于处理大型数据集。

实验结果

在本节中，我们在介绍实验设置之后，展示了用于评估所提算法的实验结果。由于在大型数据集上使用FBcubed指标进行性能评估不仅耗时，对于某些数据集来说甚至不可行，因此我们设计了一个实验，使用我们自行开发的更快速的替代方法来计算FBcubed指标，并证明其得到的结果与FBcubed指标的结果十分接近。接下来，我们还进行了另一组实验，通过调整参数$$的不同值来观察算法性能变化。

结论

在许多现实问题中，研究对象并不严格属于单一类别，它们往往与多个类别存在关联。在这种情况下，重叠聚类就显得非常有用，因为它不同于传统的聚类方法，能够捕捉到这些关联关系。不过，由于计算成本较高，重叠聚类算法在处理大型数据集时往往会耗费大量时间。因此，本文我们提出了一种专为大型数据集设计的基于重叠k均值的新型聚类算法，该算法能够有效解决这一问题。

CRediT作者贡献说明

何塞·安东尼奥·桑切斯-蒂罗：负责撰写原始草稿、可视化处理、软件开发、方法设计、研究实施、形式化分析以及概念构思工作。何塞·弗朗西斯科·马丁内斯-特里尼达：负责撰写内容的审阅与编辑、算法验证、研究监督以及形式化分析工作。赫苏斯·阿里尔·卡拉斯科-奥乔亚：负责撰写内容的审阅与编辑、可视化处理、研究监督以及形式化分析工作。

利益冲突声明

作者声明，他们不存在任何可能影响本文研究结果的已知财务利益关系或个人关系。

致谢

我们要感谢墨西哥科学、人文、技术及创新部（Secihti）对本研究提供的支持。

何塞·安东尼奥·桑切斯-蒂罗拥有墨西哥普埃布拉州国家天体物理、光学与电子学研究所计算机科学系的硕士学位。他的研究兴趣包括聚类分析、数据挖掘以及计算机视觉领域。

何塞·安东尼奥·桑切斯-蒂罗|何塞·弗朗西斯科·马丁内斯-特里尼达|赫苏斯·阿里尔·卡拉斯科-奥乔亚

墨西哥普埃布拉州圣安德烈斯乔卢拉市斯塔玛丽亚托南辛特拉镇路易斯恩里克埃罗1号，国家天体物理、光学与电子学研究所计算机科学系，邮编72840