圆形网格抽样和逆近邻优化的密度峰值聚类算法

摘要

密度峰值聚类(DPC)算法是一种简单高效的聚类算法，因其可直观和快速发现数据集中的类簇而得到广泛关注.但DPC算法需计算所有样本间的欧氏距离，算法的时间复杂度较高；局部密度定义未考虑类簇间密度差异影响，易误选类簇中心；使用链式分配策略，易产生错误连带效应.因此，本文提出一种圆形网格抽样和逆近邻优化的密度峰值聚类算法.该算法采用圆形网格抽样得到代表以减少需要计算的样本数，降低算法计算的时间开销，并引入近似K近邻策略加强代表和初始样本的联系，减少抽样导致的聚类精度丢失；利用逆近邻优化局部密度定义策略，根据样本所处环境调节其局部密度的大小，准确找到密度峰值；通过共享逆近邻计算相似性，由相似性矩阵分配代表，避免样本分配策略产生的错误连带效应.设置了复杂形态合成数据集、真实数据集和较大规模数据集进行分组实验.实验结果表明，本文算法在复杂形态、真实及较大规模数据集上聚类优势显著，精度与效率较DPC算法及其他基于DPC的改进算法均有较大提升.

关键词

密度峰值聚类 / 圆形网格抽样 / 近似K近邻 / 逆近邻 / 共享逆近邻

基金资助

国家自然科学基金资助项目（62466037,62463021）