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

Highly Efficient Parallel Algorithm of K-Medoids in Cloud Environment

作　　者：李媛媛[1] 孙玉强[1] 晁亚 刘阳 

机构地区：[1]常州大学信息科学与工程学院,江苏常州213164 [2]中国电建上海电力环保设备制造总厂有限公司,上海201900

出　　处：《计算机测量与控制》2016年第12期139-142,146,共5页Computer Measurement &Control

基　　金：国家自然科学基金项目(11271057;51176016);江苏省自然科学基金项目(BK2009535)

摘　　要：传统聚类算法K-Medoids对初始点的选择具有随机性,容易产生局部最优解;替换聚类中心时采用的全局顺序替换策略降低了算法的执行效率;同时难以适应海量数据的运算;针对上述问题,提出了一种云环境下的改进K-Medoids算法,该改进算法结合密度法和最大最小原则得到优化的聚类中心,并在Canopy区域内对中心点进行替换,再采用优化的准则函数,最后利用顺序组合MapReduce编程模型的思想实现了算法的并行化扩展;实验结果表明,该改进算法与传统算法相比对初始中心的依赖降低,提高了聚类的准确性,减少了聚类的迭代次数,降低了聚类的时间。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 sarrie time, it is diffi- cult to adapt to operation of massive data. In response to the above problems, an improved K--Medoids clustering algorithm in cloud environ- ment is proposed. The algorithm combines the density method and Max--Min principle to obtain optimized cluster centers, and replaces cen ters in the area of Canopy, and adopts optimization criterion function, and finally uses the ideas of sequential composition of Map.Reduce pro- gramming model to achieve the parallel extensions of the algorithm. -Result of the experiments shows that the improved method is less de- pendent on the initial points and reduces the number of iterations and the clustering time.

关 键 词：云环境 K-Medoids聚类 Canopy算法 最大最小原则 MAPREDUCE 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]