针对Science发表的密度峰值聚类(Density peaks clustering,DPC)算法及其改进算法效率不高的缺陷,提出一种相对邻域和剪枝策略优化的密度峰值聚类(Relative neighborhood and pruning strategy optimized DPC,RP-DPC)算法.DPC聚类算法...针对Science发表的密度峰值聚类(Density peaks clustering,DPC)算法及其改进算法效率不高的缺陷,提出一种相对邻域和剪枝策略优化的密度峰值聚类(Relative neighborhood and pruning strategy optimized DPC,RP-DPC)算法.DPC聚类算法主要有两个阶段:聚类中心点的确定和非聚类中心点样本的类簇分配,并且时间复杂度集中在第1个阶段,因此RP-DPC算法针对该阶段做出改进研究.RP-DPC算法去掉了DPC算法预先计算距离矩阵的步骤,首先利用相对距离将样本映射到相对邻域中,再从相对邻域来计算各样本的密度,从而缩小各样本距离计算及密度统计的范围;然后在计算各样本的δ值时加入剪枝策略,将大量被剪枝样本δ值的计算范围从样本集缩小至邻域以内,极大地提高了算法的效率.理论分析和在人工数据集及UCI数据集的对比实验均表明,与DPC算法及其改进算法相比,RP-DPC算法在保证聚类质量的同时可以实现有效的时间性能提升.展开更多
文摘针对Science发表的密度峰值聚类(Density peaks clustering,DPC)算法及其改进算法效率不高的缺陷,提出一种相对邻域和剪枝策略优化的密度峰值聚类(Relative neighborhood and pruning strategy optimized DPC,RP-DPC)算法.DPC聚类算法主要有两个阶段:聚类中心点的确定和非聚类中心点样本的类簇分配,并且时间复杂度集中在第1个阶段,因此RP-DPC算法针对该阶段做出改进研究.RP-DPC算法去掉了DPC算法预先计算距离矩阵的步骤,首先利用相对距离将样本映射到相对邻域中,再从相对邻域来计算各样本的密度,从而缩小各样本距离计算及密度统计的范围;然后在计算各样本的δ值时加入剪枝策略,将大量被剪枝样本δ值的计算范围从样本集缩小至邻域以内,极大地提高了算法的效率.理论分析和在人工数据集及UCI数据集的对比实验均表明,与DPC算法及其改进算法相比,RP-DPC算法在保证聚类质量的同时可以实现有效的时间性能提升.
