Note: [] This work is supported by the National Science Foundation of China (Nos. 61170111, 61175047, 61134002 and 61202043), the Fundamental Research Funds for the Central Universities (Nos. SWJTU11ZT08 and SWJTU12CX098) and the Research Fund of Traction Power State Key Laboratory, Southwest Jiaotong University (No. 2012TPL-T15) Address for correspondence: School of Information Science and Technology, Southwest Jiaotong University, Chengdu, 610031, P.R. China
Abstract: Clustering with pairwise constraints has received much attention in the clustering community recently. Particularly, must-link and cannot-link constraints between a given pair of instances in the data set are common prior knowledge incorporated in many clustering algorithms today. This approach has been shown to be successful in guiding a number of famous clustering algorithms towards more accurate results. However, recent work has also shown that the incorporation of must-link and cannot-link constraints makes clustering algorithms too much sensitive to “the assignment order of instances” and therefore results in consequent constraint violation. The major contributions of this paper are two folds. One is to address the issue of constraint violation in Cop-Kmeans by emphasizing a sequenced assignment of cannot-link instances after conducting a Breadth-First Search of the cannot-link set. The other is to reduce the computational complexity of Cop-Kmeans for massive data sets by adopting a MapReduce Framework. Experimental results show that our approach performs well on massive data sets while may overcome the problem of constraint violation.
