基于约束信息的并行k-means算法

Parallel k-means algorithm based on constrained information

为获得分布式数据集上用户所期望的聚类结果,提出了基于约束信息的并行k-means聚类算法.在分析并行k-means能够有效实现对水平分布式数据集进行聚类的基础上,修改并行k-means算法的目标函数,设计约束并行k-means算法,将站点用户的约束信息以chunklet的形式引入到分布式聚类过程,从而引导算法执行有偏搜索.约束并行k-means算法在理论上保证无约束样本簇内距离最小的同时能够确保chunklet约束中的样本与对应的簇中心之间的平均距离最小.实验结果表明,约束并行k-means算法能够有效改善并行k-means的聚类精度,同时在分布式环境下能够得到与已有约束聚类算法在集中式数据集上相等价的聚类结果.

In order to obtain the desired clustering results on the distributed data set,a parallel k-means algorithm is presented based on constrained information.On the basis of the facts that the parallel k-means algorithm can be effectively used in clustering the horizontal distributed data set,the objective function of the parallel k-means algorithm is modified,and the constrained parallel k-means algorithm is designed,then the constrained information of site users is introduced into the distributed clustering process in the form of chunklets,which can guide the algorithm to a bias search.Theoretically the algorithm guarantees the inter-cluster distance among the unconstrained samples to be the closest,and guarantees the average distance between constrained samples in a chunklet and the corresponding cluster center to be the closest one.The results from the experiments show that the algorithm can effectively enhance the clustering precision of parallel k-means,meanwhile it can obtain the clustering results on the distributed data set,which are equivalent to the results of the constrained k-means algorithm running on a centralized data set.