基于MapReduce和改进密度峰值的划分聚类算法

作者：黄学雨^*; 向驰; 陶涛

来源：计算机应用研究, 2021, 38(10): 2988-2993+3024.

DOI：10.19734/j.issn.1001-3695.2021.03.0093

• 划分聚类算法
• 密度峰值
• 自然最近邻
• MapReduce
• 数据倾斜

对于基于划分的聚类算法随机选取初始聚类中心导致初始中心敏感,聚类结果不稳定、集群效率低等问题,提出一种基于MapReduce框架和改进的密度峰值的划分聚类算法(based on MapReduce framework and improved density peak partition clustering algorithm,MR-IDPACA)。首先,通过自然最近邻定义新的局部密度计算方式,将搜索样本密度峰值点作为划分聚类算法的初始聚类中心;其次针对算法在大规模数据下运行时间复杂,提出基于E2LSH(exact Euclidean locality sensitive hashing)的一种分区方法,即KLSH(K of locality sensitive hashing)。通过该方法对数据分区后结合MapReduce框架并行搜寻初始聚类中心,有效减少了算法在搜索初始聚类中心时的运行时间;对于MapReduce框架中的数据倾斜问题,提出ME(multistage equilibrium)策略对中间数据进行多段均衡分区,以提升算法运行效率;在MapReduce框架下并行聚类,得到最终聚类结果。实验得出MR-IDPACA算法在单机环境下有着较高的准确率和较强的稳定性,集群性能上也有着较好的加速比和运行时间,聚类效果有所提升。

• 单位
  江西理工大学