代永杨，张清华，支学超

(重庆邮电大学 计算智能重庆市重点实验室，重庆 400065)

0 引 言

作为一种无监督学习方法,聚类旨在发现数据之间潜在的数据结构[1]。目前国内外学者已经提出了许多不同类型的经典聚类算法。基于层次的聚类算法有CURE[2]和BIRCH[3]等; 基于划分的聚类算法有K-means[4]等; 基于网格的聚类算法有WaveCluster[5],STING[6]和CLIQUE[7]等; 基于密度的聚类算法有DBSCAN[8]和OPTICS[9]等。这些经典的聚类算法已经被广泛应用到数据挖掘[10-11]、图像分割[12-14]、数据压缩[15]等领域。

密度峰值聚类算法(density peaks cluster,DPC)是由A.Rodriguez等[16]于2014年发表在Science上的一种基于密度的聚类算法。样本的密度和相对距离是DPC中的2个重要概念。给定数据集中任意一个样本p，p的密度即在给定截断距离dc的条件下，以p为圆心，dc为半径的邻域中所包含的样本数量。p的相对距离即从密度比p大样本中找到距离p最近的样本q，p和q之间的距离为p的相对距离。在本文中，记q为p的父节点。DPC根据2个假设进行聚类:①类簇中心被周围密度更低的样本包围;②类簇中心与其父节点间的距离较远。基于以上2个假设，DPC首先计算样本的密度和相对距离，构建决策图; 然后，从决策图中选择具有较大密度和相对距离的样本作为聚类中心; 最后，将非中心点按照密度由高到低的顺序分配到各自父节点所在的类簇。

由于DPC算法思想简单且能够聚类任意形状的类簇，这使得DPC已经被广泛应用，然而，该算法仍然存在以下不足。

①DPC的非中心点的分配策略容易引起密度跳跃，从而导致连续错误，影响聚类结果[17]。……