基于密度峰值剪枝后的最短路径聚类算法

胡恩祥，汪春雨，潘美芹

1.上海外国语大学国际工商管理学院，上海201600

2.华东师范大学计算机科学与技术学院，上海200062

最早在1996年由Ester等[1]提出的DBSCAN 算法使人们意识到密度这一概念的引入，不仅能够直观地解释类别是如何分配的，而且对较大体量的数据和噪声点的数量也有较好的包容性.聚类的速度和准确性得到了明显的提升和改进.此后，围绕DBSCAN 算法的领域半径Eps 值和MinPts 最小点数量展开了讨论，如荆继武等[2]提出的SA-DBSCAN 仍取MinPts=4，但采用了Inverse Gaussian 拟合曲线模拟第4 近邻距离下点概率分布图，用更准确的统计模型计算出实际拐点对应的Eps 值.曹晶等[3]提出了PDBSAN 并认为DBSCAN 采用全局参数，而对不同类型和密度的类别需要分开确定局部参数.通过数据特性进行分区，确定局部参数，局部聚类后再进行局部类合并.基于分区的思想，曹晶等[4]又提出了FDBSCAN，通过选择每一个核心点区域的代表对象，减少区域内的点被重复遍历的次数和可能.后来，Rodriguez等[5]在密度属性的基础上又定义了一个新的距离属性δ，由此提出了CDP 算法，具有较大的密度值和δ值的点作为聚类中心，然后依次对剩余点进行分类.与DBSCAN 算法相比，该算法的核心是通过引入属性δ值使聚类中心表现出更“离群”和突出的特性，同时δ值计算过程也暗示了剩余点的分配规则.这样的CDP 算法通过巧妙的双重属性设置，解决了DBSCAN 算法中通过单一全局密度值判断所有潜在核心点的尴尬情景.2019年，Pizzagalli等[6]在剩余点的分配规则上提出了新的……