彭启慧，宣士斌，高 卿

广西民族大学 信息科学与工程学院，南宁530006

聚类分析[1]是数据挖掘和机器学习中的一个基础研究内容。在过去的几十年中，研究人员已提出多种聚类算法。典型算法包括基于分区的K-means[2]和Kmedoids[3]、基于层次的CURE[4]和BIRCH[5]、基于密度的DBSCAN[6]和OPTICS[7]和基于网格的WaveCluster[8]和STING[9]，以及基于模型的统计聚类[10]和基于图论的谱聚类[11]。经典的聚类算法K-means是通过指定聚类中心，然后通过迭代的方式更新聚类中心，在具有凸球形结构的数据集上实现了良好的聚类结果，但由于每个点都被指派到距离其最近的聚类中心，所以导致它不能检测非球面类别的数据分布。虽然有DBSCAN可以对任意形状的分布进行聚类，并且具有很强的抗噪能力，但对于变密度簇和高维数据的聚类效果较差[12-14]，此外，选择半径和阈值也是DBSCAN的难题。Rodriguez和Laio[15]提出的DPC（Clustering by fast search and find of Density Peaks）根据局部密度和密度最近邻可以得到决策图，并根据决策图求得聚类中心。这种算法不仅高效，而且所依赖的参数只有截止距离这一个。虽然DPC算法在某些方面有着明显的优势，但它仍然存在如下的一些情况：

首先，局部密度和距离测量的定义简单[16-17]，因此，当处理具有多尺度，交叉缠绕，各种密度或高维度的复杂数据集时，DPC算法的聚类结果可能较差[18-21]。其次，依据决策图人工选择类中心点，带有较强的主观性[22-23]。第三，由于在大多数情况下每个属性的范围都是未知的，所以通常很难确定截断距离[24-25]。针对DPC存在的问题，研究人员提出了很多DPC的改进和优化方法。……