Improving clustering with constrained communities.

In this paper, we propose a new constrained clustering algorithm, named Constrained Community Clustering (C 3 ). It can utilize both must-link and cannot-link constraints that specify the pairs of data that belong to the same or different clusters. Instead of directly enforcing the pairwise constraints on the constrained data, C 3 first builds constrained communities around each constrained data, and then exert pairwise constraints on the constrained communities. Therefore, C 3 can not only extend the influence of pairwise constraints to the surrounding unconstrained data, but also uncover the underlying sub-structures of the clusters. The promising experimental results on the real-world text documents, handwritten digits, alphabetic characters, face recognition, and community discovery illustrate the effectiveness of our method. [ABSTRACT FROM AUTHOR]