具有成对约束的聚类最近在聚类社区中引起了很多关注。 特别地,数据集中给定实例对之间的必须链接约束和不能链接约束是当今许多聚类算法中所包含的常识。 事实证明,这种方法可以成功地指导许多著名的聚类算法获得更准确的结果。 但是,最近的工作还表明,必须链接约束和不能链接约束的合并使聚类算法对“实例的分配顺序”过于敏感,因此导致了随后的约束冲突。 本文的主要贡献有两个方面。 一种方法是在执行“无法链接”集合的“广度优先”搜索后,通过强调无法链接实例的有序分配来解决Cop-Kmeans中违反约束的问题。 另一个是通过采用MapReduce框架来降低大数据集的Cop-Kmeans计算复杂度。 实验结果表明,我们的方法在海量数据集上表现良好,同时可以克服约束冲突的问题。
1