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

摘要

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