EGBDPM:用于流形数据的高效颗粒球密度峰值聚类算法

《Neurocomputing》:EGBDPM: Efficient granular ball density peaks clustering for manifold data

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

编辑推荐:

  针对GB-DP聚类方法生成的粒球(GB)质量不高、未充分考虑GB局部关系及无法有效处理非均匀密度分布和流形数据的问题,本文提出高效流形数据粒球密度峰值聚类算法(EGBDPM)。通过改进GB生成方法、融合GB局部关系进行密度计算,并采用球面测地距离替代欧氏距离,显著提升了算法效率与性能,在合成和真实数据集上的实验验证了其有效性。

  
张行国|徐莉|贾卫宽
中国山东省枣庄市枣庄大学信息科学与工程学院,277160

摘要

颗粒球密度峰值聚类(GB-DP)是一种将颗粒球(GB)的概念应用于密度峰值聚类(DPC)的聚类方法,显著提高了DPC的效率。研究表明,GB-DP生成颗粒球的方法仅依赖于颗粒球内包含的数据点数量,忽略了数据的分布情况,这导致生成的颗粒球质量普遍较低。密度估计仅使用单个颗粒球,而没有充分考虑颗粒球周围的邻域信息,因此在处理密度分布不均匀的数据时性能较差。欧几里得距离被用来计算颗粒球之间的距离,但在处理流形数据时无法产生理想的结果。为了解决这些问题,本文提出了一种针对流形数据的高效颗粒球密度峰值聚类算法(EGBDPM)。该算法采用了一种自适应的快速颗粒球生成方法,结合数据点的分布情况来生成颗粒球,从而在保证生成效率的同时提高了颗粒球的质量。该算法通过考虑邻域关系和颗粒球的质量来估计局部密度,有效处理了密度分布复杂的 数据集。用球形测地距离替换欧几里得距离,有效增强了处理流形数据的能力。为了验证EGBDPM的性能,在10个合成数据集和10个真实数据集上进行了对比实验,并将其与7种先进的聚类算法进行了比较。结果表明,EGBDPM在效率和性能方面都表现出色,能够有效处理流形等复杂数据。

引言

聚类分析是机器学习领域的一个重要研究方向。其核心目标是根据对象的相似性将它们分组,使得同一组内的对象具有高相似性,而不同组内的对象具有低相似性[1],[2]。常见的聚类算法包括k-means[3]、谱聚类(SC)[4]、DBSCAN[5]和DPC[6]。近年来,DPC[7]因其简单的实现方式而受到研究人员的广泛关注,因为它仅使用数据点之间的距离就完成了整个聚类过程。
SNNDPC[8]通过共享邻居改进了密度计算,提高了其对复杂数据的适应性。DPC-DLP[9]利用局部密度来确定聚类中心,并提出聚类核心处的点具有更高的密度值。DPC-KNN[10]通过使用k最近邻(KNN)来计算每个点的局部密度,提高了对不同密度分布数据集的适应性。ADPC-KNN[11]引入了KNN的概念来计算全局参数dc,并采用密度可达性策略进行聚类。G-KNN-DPC[12]结合了基尼系数和KNN来自动优化密度计算的截止距离。RDPCM[13]使用改进的KNN方法重新设计了密度计算公式,有效识别了多模态聚类中心。AGB-DP[14]通过结合分布指标提高了局部密度估计的准确性。FastDP[15]通过快速的KNN搜索解决了大规模数据处理问题。DPCG[16]基于网格划分简化了局部密度的计算过程,提高了大规模数据集的计算效率。Fast-LDP-MST[16]重新定义了密度计算方法,简化了计算逻辑,并减少了密度评估期间的计算工作量,使密度评估更加高效。HFDPC[18]通过网格聚类加速了DPC的过程。
颗粒球作为一种新的数据表示形式,使用粗粒度表示数据,有效降低了计算复杂度。GB-DP[19]将颗粒球引入DPC算法中,显著提高了DPC的速度。然而,研究表明GB-DP存在一些缺点:(1)生成的颗粒球没有根据数据分布进行进一步处理,导致颗粒球质量较低;(2)它仅考虑单个颗粒球的密度,忽略了局部邻域中颗粒球之间的关系;(3)它无法处理密度分布不均匀的数据和流形数据。为了解决这些问题,本文提出了一种针对流形数据的高效颗粒球密度峰值聚类算法,通过改进颗粒球生成方法和重新设计密度及距离计算公式来解决这些问题。主要贡献如下:(1)
快速自适应颗粒球生成方法:在单次迭代中生成初始颗粒球,使用基于主成分的分割方法优化其质量,并通过自适应阈值进一步处理异常颗粒球。整个颗粒球生成过程是自适应进行的。
  • (2)
    密度计算方法:结合颗粒球的邻域关系,通过结合颗粒球的邻域关系和质量来计算局部密度,有效提高了对密度分布复杂数据集的适应性。
  • (3)
    球形测地距离计算方法:用球形测地距离替换欧几里得距离,可以更准确地捕捉流形数据集的非线性几何结构。
  • 本文的其余部分安排如下:第2节回顾了颗粒球计算、主成分分析(PCA)、四分位距(IQR)、测地距离和与DPC相关的内容。第3节介绍了所提出的EGBDPM的基本定义和具体算法。第4节讨论了EGBDPM的性能、参数分析和相关消融实验。最后,第5节总结了EGBDPM。

    相关工作

    本节主要回顾了本文中使用的相关技术,包括颗粒球计算、PCA、IQR、测地距离和DPC相关概念。

    针对流形数据的高效颗粒球密度峰值聚类

    本节全面介绍了所提出的EGBDPM算法,其聚类过程如图2所示。首先,基于k-means++的单次迭代结果生成初始颗粒球。然后,使用基于主成分投影(ESPCM)的高效分割方法对颗粒球进行评估和优化。优化后的颗粒球可能包含半径较大的异常颗粒球(图2中的红色颗粒球)。通过设计异常检测方法来检测异常颗粒球。

    实验评估

    本节介绍了EGBDPM的基线算法和实验数据,通过比较结果来验证EGBDPM算法的有效性。

    结论

    研究发现,GB-DP的颗粒球生成方法没有进一步优化颗粒球,导致颗粒球质量较低,在处理密度分布不均匀的数据和流形数据时表现不佳。为了解决这些问题,本文提出了EGBDPM算法,该算法采用自适应的快速颗粒球生成方法来提高生成效率,同时保证颗粒球的质量。通过结合颗粒球的邻域关系和质量来估计局部密度,EGBDPM

    未引用的参考文献

    [17]

    CRediT作者贡献声明

    张行国:撰写——原始草案、方法论、研究。徐莉:撰写——审稿与编辑、监督、项目管理、资金获取、数据整理、概念化。贾卫宽:可视化、资源准备。

    利益冲突声明

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

    致谢

    本研究得到了中国国家自然科学基金(项目编号62206240)和山东省自然科学基金(项目编号ZR2020QF110)的支持。
    张行国于2023年从枣庄大学信息科学与工程学院获得学士学位,目前正在山东师范大学攻读硕士学位,主要研究方向为聚类分析和粒度计算。
    相关新闻
    生物通微信公众号
    微信
    新浪微博
    • 搜索
    • 国际
    • 国内
    • 人物
    • 产业
    • 热点
    • 科普

    热点排行

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

      版权所有 生物通

      Copyright© eBiotrade.com, All Rights Reserved

      联系信箱:

      粤ICP备09063491号