GB-MDPC:基于颗粒球模型的流形数据密度峰值聚类算法

《Neurocomputing》:GB-MDPC: Density peaks clustering based on granular balls for manifold data

【字体: 大 中 小 】 时间:2026年04月21日 来源:Neurocomputing 6.5

编辑推荐:

  针对密度峰值聚类(DPC)算法在流形数据中的局限性,本文提出基于颗粒球与流形距离的改进算法(GB-MDPC)。通过约束半径生成颗粒球,利用分布熵优化密度计算,构建最小生成树(MST)实现流形距离度量,有效提升聚类精度和效率。实验表明GB-MDPC在合成和真实数据集上优于传统方法。

  
江润宇|张金金|黄冰|崔英柳|孙旭|王天星
南京审计大学计算机科学学院,南京,211815,中国

摘要

密度峰聚类(DPC)算法在处理流形数据时存在若干固有局限性,包括欧几里得距离引入的偏差、链式分配导致的多米诺效应错误、参数敏感性以及较高的时间复杂度。为了解决这些问题,我们提出了一种基于流形距离度量的粒状球体聚类算法(GB-MDPC)。该方法通过使用分布熵来校正原始数据集上生成的粒状球体的密度,然后通过调整粒状球体之间的距离并构建最小生成树(MST)来获得粒状球体之间的流形距离度量。最终,在决策图上定义粒状球体的密度及其之间的距离,选择同时具有高密度和高距离的粒状球体作为聚类中心。其余的粒状球体被分配到最近的高密度粒状球体所在的簇中,并将聚类结果映射回原始数据集。在13个具有流形结构的合成数据集和13个高维真实世界数据集上的聚类实验中,GB-MDPC表现出优异的聚类性能。

引言

聚类是无监督机器学习领域的一项基本技术,旨在揭示未标记数据集中隐藏的固有分组或结构[29] [37]。该方法的目的是对数据进行分组,它利用数据点之间的相似性或差异性将数据划分为不同的簇[38]。整个分组过程追求的目标是在最大化簇内数据一致性的同时,最大化簇之间的差异性。这种内在的组织结构有助于数据压缩和模式识别,并提供有关数据分布的宝贵信息[2]。聚类算法有很多类型,根据生成簇的机制,大致可以分为基于分区的[20]、基于层次的[19]、基于密度的[16]、基于网格的[9]、基于模型的[3]和基于模糊的[1]方法[29]。现在我们回顾一些与我们的工作相关的聚类算法的研究进展。
首先是经典的基于分区的聚类算法K-means[17],其核心思想是通过最小化簇内样本与其质心之间的平方误差来迭代地将数据划分为多个簇。然而,由于它需要预先指定簇的数量,在非球形数据上的表现较差,并且对异常值敏感,K-means算法无法覆盖所有聚类场景。针对K-means的这些局限性,Rodríguez等人[22]提出了密度峰聚类(DPC)算法。该算法的核心思想是假设簇中心应具有较高的局部密度并且与其他簇中心相对较远。这种基于密度的聚类算法可以自动识别簇中心,无需迭代,能够实现任意形状的简单高效聚类。然而,DPC本身也存在一些局限性[29]。由于其对于截止距离参数的高度敏感性,聚类结果的准确性会受到该参数的严重影响。由于其分配阶段的链式特性,单个错误可能导致大规模的错误聚类。为此,研究人员提出了多种改进DPC的方法。Zhang等人[40]设计了一个新的有效性指标来替代原始的决策图,并在过程中动态定义邻居,从而无需先验知识即可自动识别簇中心。对于高维数据,Du等人[8]提出了DPC-KNN-PCA算法,该算法结合了K最近邻(KNN)和主成分分析(PCA)技术来重新定义局部密度,并利用PCA来应对高维数据带来的挑战。Guo等人[11]提出的DPC-CE算法利用估计的局部中心之间的连通性来评估它们的相似性,从而避免了链式分配错误。Wang等人[30]提出的VDPC算法专注于变密度聚类任务,其中初始簇的构建依赖于代表性点,并进一步分析簇属性。Ding等人[7]通过引入采样策略和改进的TI搜索策略,实现了近似代表性点的快速识别,有效提高了聚类过程的效率。这些改进旨在增强DPC的鲁棒性和适用性,并解决其在处理复杂数据时的不足。
Xia等人[32]提出了粒状球计算(GBC),这是一种基于粒状计算的学习方法的代表。传统分类器通常以点或像素作为输入,而GBC作为一种新颖的结构,生成包含数据点的粒状球体(GB),以替代点式输入并参与分类器学习过程,这种数据压缩和效率提升显著提高了算法的可扩展性[34],使用单个GB表示数据区域可以提供更高的抗随机噪声和异常值的鲁棒性[31]。此外,由于球体的完全对称性和简单的数学表示,GBC可以很容易地与其他模型集成[36]。因此,Xia等人开发了粒状球支持向量机和粒状球k最近邻(GBkNN)算法[32]。Xia等人[33]提出了球体K-means算法,通过利用相邻球体簇将每次迭代中的距离计算次数减少,并将粒状球体划分为稳定和活跃区域,从而加速K-means算法。Wang等人[28]提出了一种基于GBC的无监督异常检测方法,该方法通过用多粒度GB覆盖数据并计算稳态分布来评估样本异常。
作为数据的粗粒度表示,GB也可以应用于聚类任务。Cheng等人[6]提出了GB-DPC算法,该算法在DPC中用GB替换数据点,并定义每个GB的密度及其之间的距离。这使得GB-DPC不受截止距离参数的影响。此外,由于GB的数量远小于数据点的数量,GB-DPC在大型数据集上表现出显著的效率优势。Ni等人[21]引入了GBK-DPC,该算法结合了自适应优化机制来生成更清晰表示边界的GB。它从GB的内部和外部因素估计GB的密度,并通过动态分配策略提高容错能力。在聚类任务中,使用GB可以有效降低计算成本。
尽管现有的基于GB的DPC改进提高了效率,但它们依赖于欧几里得距离度量,这使得它们在处理流形数据时容易发生错误分配[25]。流形距离可以有效地捕捉数据的内在几何结构[23],为解决这一问题提供了理论方向[5] [13]。直接在原始高维数据点上计算流形距离在计算成本方面并不理想。GB提供的粗粒度和稳定的数据表示为构建流形距离创造了条件,以较小的效率损失换取了复杂流形数据聚类准确性的显著提高。我们提出的GB-MDPC算法使用GB覆盖原始数据,通过分布熵优化其密度计算,并通过构建最小生成树来计算GB之间的流形距离,有效地捕捉数据的内在拓扑结构,从而完成簇分配。GB-MDPC的工作流程如图1所示。GB-MDPC的主要贡献如下:蓝色框展示了GB的生成过程,黄色框描述了GB的密度计算和流形距离计算,橙色框描述了聚类过程:
  • 1. 提出了一种半径受限的GB生成机制,通过设置半径阈值有效减少了过度分割和分割不足,从而提高了GB的质量和聚类性能。
  • 2. 引入了一种基于分布熵优化的密度评估方法,以细化GB的紧凑性测量,从而更准确地描述数据分布和识别簇中心。
  • 3. 采用基于流形距离的度量来替代GB之间的欧几里得距离,捕捉更真实的数据接近性,并克服了流形数据上的错误分配。
  • 本文的其余部分组织如下。第2节介绍了DPC、流形距离度和GB的基础概念。第3节详细介绍了提出的GB-MDPC算法。第4节在合成和真实世界的UCI数据集上进行了全面实验,以展示GB-MDPC的优异聚类性能。最后,第5节总结了研究结果。

    部分摘录

    预备知识

    在本节中,提供了DPC、GB和流形距离度的概念,以便更好地理解所提出的算法。

    提出的算法

    在本节中,我们详细描述了GB-MDPC算法。该算法首先通过对数据集应用受限的半径阈值来生成适当大小的GB,然后使用提出的分布熵定义量化GB内的数据点分布,并获得GB的调整后的密度。根据GB之间的重叠或分离情况调整它们的间距,并从构建的最小生成树中得出GB之间的流形距离度量

    实验分析

    本节介绍了在合成和真实世界数据集上对GB-MDPC聚类算法的实验分析,以评估其有效性。选定的代表性数据集包括12个合成数据集和来自UCI仓库的13个真实世界数据集。这些数据集在维度、簇数量、实例数量和特征维度上有所不同。总结了合成和真实数据集的详细特征

    结论

    本文提出了一种结合粒状球体和流形距离度的密度峰聚类算法,称为GB-MDPC。在这种方法中,GB在数据域上以无监督的方式生成。这些GB的大小受到限制,以防止密集区域中的冗余和稀疏区域中的过大GB。之后,使用分布熵计算每个GB的密度,并计算GB之间的流形距离,以更好地捕捉

    作者贡献声明

    江润宇:撰写——原始草稿、可视化、方法论、调查、概念化。张金金:监督、调查。黄冰:撰写——审阅与编辑、监督。崔英柳:可视化、调查。孙旭:撰写——审阅与编辑、调查。王天星:撰写——审阅与编辑。

    利益冲突声明

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

    致谢

    本工作得到了中国国家自然科学基金(编号62276136、62206129和62176116)的支持。
    江润宇目前是中国南京审计大学计算机科学学院的硕士研究生。他的当前研究兴趣包括粒状计算和聚类分析。
    相关新闻
    生物通微信公众号
    微信
    新浪微博
    • 搜索
    • 国际
    • 国内
    • 人物
    • 产业
    • 热点
    • 科普

    热点排行

      今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

      版权所有 生物通

      Copyright© eBiotrade.com, All Rights Reserved

      联系信箱:

      粤ICP备09063491号