2014年,《Science》上发表了一种聚类算法,被称为密度峰值聚类算法(Density Peaks Clustering,以下简称DPC),此算法尝试使用两个目标:密度和峰值,以自动确定簇的数量。它可以处理任意形状分布的数据集,拥有原理简单、效率出众、调节参数少等让科研人员青睐的优点,这使它成为了聚类分析中的热门算法。此算法首先设计了一种称为决策图的启发式方法来找出局部密度和偏移距离最大的数据点作为聚类中心,然后在用户选择了聚类中心之后,通过将数据点分配给与其最近的邻居(具有更高密度)来组成一个个簇。该过程非常简单,主要在于它的两个核心的直观假设:(1)聚类中心总是那些周围点比较密集,自己密度比它周围点的密度都大的点。(2)不同聚类中心间的距离比聚类中心与其周围点的距离更远。但是,此算法也拥有如下不足和缺点:(1)在选择截断距离d_c时,算法需要基于数据集上的经验值人工选择:即算法建议的截断距离为按此截断距离选择的数据点个数为数据点总数的2%左右。(2)算法需人工选择选择聚类中心,但没有一个通用的选择标准,所以误差较大,直接影响聚类结果。(3)在数据集规模大、维度高时,算法的聚类效果很差。针对上述缺点,本文提出了两个改进的方法,主要从以下两个方面进行了改进:1.针对缺点(1)和(2),提出一种自动确定截断距离及类中心的密度峰值聚类算法。首先提出了一种基于Gini系数可以自适应选择截断距离d_c的计算方法,Gini系数越小,数据集的稠密稀疏程度相差越大,即每一类数据在数据集的分布更加不均匀,这样的情况下更容易聚类,也就可以自动确定截断距离。然后计算每个点的局部密度和偏移距离的score函数值并画出排序图,根据score变化趋势自动确定出潜在聚类中心,最后通过聚类中心距离大于阈值d_c的方法来确定真正聚类中心。实验结果表明本章所提出的算法无论是在运行准确率还是在处理数据的鲁棒性上都有良好的效果。2.针对缺点(3),提出一种基于网格的改进密度峰值聚类算法。首先给出一种网格划分的方法并给出相邻网格和网格中心点的定义,将数据点粒度放大到了网格粒度,然后采用更加高效合理的局部密度和偏移距离的衡量方法,结合使用改进方法1中提出的自动确定截断距离和筛选聚类中心的方法对网格聚类,这样处理使得空间复杂度和时间复杂度都较DPC算法有明显的降低。通过实验验证了此算法无论在数据规模较小还是较大的数据集上都拥有很好的性能且运行速度比DPC快很多,算法的鲁棒性进一步提升,尤其是在大规模数据集上的效果,比对比的算法有更好的效果。