并行k均值聚类算法的完备性证明与实现  

Completeness Proof and Implementation of Parallel k-means Clustering Algorithm

作　　者：陶冶[1] 曾志勇[1] 余建坤[1] 冯涛[1] 

机构地区：[1]云南财经大学信息学院,昆明650221

出　　处：《计算机工程》2010年第22期72-74,共3页Computer Engineering

基　　金：云南省自然科学基金资助项目(2007G079M);云南省教育厅科学研究基金资助项目(6Y0159D)

摘　　要：对经典k均值算法进行分析,证明如何在减少节点间通信代价的情况下,从局部聚类信息生成完备的全局聚类信息,使聚类质量等价于相应串行算法,并具有较高的执行效率,在此基础上给出可信的基于消息传递接口的并行k均值算法。实验结果表明,该算法是高效的和可行的。This paper analyzes classical k-means clustering algorithm, proves the way that generated complete global clustering information from the local clustering information in the case of minimizing the cost of communication between computing nodes. The clustering quality of the way is equivalent to the corresponding serial algorithm, and has higher efficiency in the implementation. On this basis, this paper gives a credible parallel k-means algorithm based on Message Passing Interface（MPl）. Experimental result shows that the algorithm is efficient and feasible.

关 键 词：聚类 K均值算法 并行 消息传递接口 

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