云环境下的高效K-Medoids并行算法

Highly efficient parallel algorithm of K-Medoids in cloud environment

摘要:

传统聚类算法K-Medoids对初始点的选择具有随机性,容易产生局部最优解；替换聚类中心时采用的全局顺序替换策略降低了算法的执行效率；同时难以适应海量数据的运算。针对上述问题,提出了一种云环境下的改进K-Medoids算法,该改进算法结合密度法和最大最小原则得到优化的聚类中心,并在Canopy区域内对中心点进行替换,再采用优化的准则函数,最后利用顺序组合MapReduce编程模型的思想实现了算法的并行化扩展。实验结果表明,该改进算法与传统算法相比对初始中心的依赖降低,提高了聚类的准确性,减少了聚类的迭代次数,降低了聚类的时间。

关键词:云环境;K-Medoids聚类;Canopy算法;最大最小原则;MapReduce

Abstract:

Traditional K-Medoids clustering algorithm selects the initial points randomly, which is easy to produce local optimum; when replace the cluster centers, adopted global sequential replacement policy reduces the efficiency of the algorithm; at the same time, it is difficult to adapt to operation of massive data. In response to the above problems, an improved K-Medoids clustering algorithm in cloud environment is proposed. The algorithm combines the density method and Max-Min principle to obtain optimized cluster centers, and replaces centers in the area of Canopy, and adopts optimization criterion function, and finally uses the ideas of sequential composition of MapReduce programming model to achieve the parallel extensions of the algorithm. Result of the experiments shows that the improved method is less dependent on the initial points and reduces the number of iterations and the clustering time.

Key words:Cloud Environment; K-Medoids clustering; Canopy algorithm; Max-Min principle; MapReduce