一种基于快速网格块的密度峰值聚类算法

《Neurocomputing》：A Fast Grid-Block-Based Density Peak Clustering Algorithm

　　

郑玉燕|潘金宇

山东师范大学商学院，中国山东省济南市，250014

摘要

近年来，密度峰聚类（DPC）算法因其简单性和有效性而受到了越来越多的关注。然而，它仍存在一些缺点。例如，高计算复杂性使得处理大规模数据集变得困难。此外，局部密度需要依赖于截止距离参数，这会影响聚类性能。为了解决这些挑战，我们提出了一种基于网格块的快速密度峰聚类算法，称为FastGB-DPC。该算法首先引入了网格聚类的概念，将数据集创建的网格空间划分为多个网格单元。然后，进一步设计了一种多层次扩散邻居搜索策略，在网格单元上生成网格块，这些网格块是由局部连贯且高度相似的网格单元组成的集合。最后，通过将网格块作为基本聚类单元而不是原始数据样本来执行密度峰聚类，这大大减少了数据规模并大幅降低了运行时间。此外，还设计了一种新的双重密度函数，使聚类结果不受截止距离的影响。在合成数据和真实世界数据集上的广泛实验表明，FastGB-DPC不仅实现了类似甚至更好的性能，而且运行时间也比现有算法短得多。同时，统计测试结果表明算法之间存在统计学上的显著差异。总体而言，所提出的算法具有更好的聚类效果。

章节片段

引言

作为一种无监督学习方法，聚类已被广泛应用于数据挖掘[1]、机器学习[2]、图像处理[3]、欺诈检测[4]等领域。聚类的目标是将整个数据集划分为多个类别，其中相似的对象被分组到同一个簇中，而不相似的对象被分组到不同的簇中，即同一簇内的对象具有高相似性，不同簇内的对象具有低相似性。

已经提出了多种基于聚类的算法

DPC算法

由于DPC具有高效率、鲁棒性和易于理解的特点，已被广泛应用于不同领域。在检测簇中心时，它基于两个假设：（1）簇中心应被局部密度较低的样本所包围；（2）不同的簇中心应彼此远离。根据上述两个特征，对于一个包含个样本的数据集X={< />

${\rho }_i$' role="presentation">${\rho }_i$ 和相对距离

FastGB-DPC

我们提出的算法的基本思想是将数据样本首先放置在一个小的网格单元上，以实现数据规模的初步缩减，然后基于网格单元，通过一种设计的策略生成一个称为网格块的粗粒度数据单元，其数量远少于数据样本的数量，从而进一步减少数据规模并提高算法速度。最后，使用原始的DPC算法进行聚类

数据集

实验中使用的10个合成数据集和4个真实世界数据集的详细总结见表2和表3。这些数据集选自知名的基准数据集，它们在样本数量、簇数量和维度方面各不相同。这有助于从不同角度测试不同聚类算法的性能。具体来说，D1和Jain数据集的密度分布不均匀，上方的簇较为稀疏，下方的簇较为密集

结论

在本文中，提出了一种快速的密度峰聚类算法FastGB-DPC。FastGB-DPC引入了网格聚类算法，并提出了一种新的概念——网格块，它是由局部连贯且高度相似的网格单元组成的集合。这些相邻的网格单元在某些方面具有相似的特征，可以被视为DPC中的基本数据单元。FastGB-DPC结合了DPC和网格聚类的优点，仅需要一个唯一的网格尺寸参数

CRediT作者贡献声明

潘金宇：撰写——原始草案、可视化、验证、资源整理、数据管理。郑玉燕：撰写——审稿与编辑、验证、监督、资源管理、项目协调、资金筹集、形式分析、概念构思。

利益冲突声明

作者声明他们没有已知的可能会影响本文报告工作的竞争性财务利益或个人关系。

致谢

本工作部分得到了国家自然科学基金（编号62102236）和山东省自然科学创新发展联合基金（编号ZR2024LZH012）的支持。

郑玉燕于2011年在青岛理工大学获得信息管理与信息系统学士学位，2015年在山东师范大学获得管理科学与工程硕士学位，2019年在北京邮电大学获得计算机科学与技术博士学位。在攻读博士学位期间，她获得了中国国家留学基金委员会（CSC）的奖学金，赴美国继续深造