Pairwise Constrained Fuzzy Clustering: Relation, Comparison and Parallelization.

Although clustering with pairwise constraints through penalty regularization has been widely adopted in existing semi-supervised clustering approaches, little work has been done on theoretical comparison of these pairwise constrained approaches with respect to difference in penalties. In this paper, we first propose two types of penalties in the context of pairwise constrained fuzzy clustering. The first one accounts for the overall consistency of assignments in terms of fuzzy memberships regarding constrained pairs. The second one is the total Euclidean distance between membership vectors of constrained pairs. After analytical discussion, we establish the connection between different penalties to provide a unified view as well as a better understanding of each of them. Following the idea of penalty regularization, variants of pairwise constrained fuzzy c-means are formulated by incorporating the consistency-type and distance-type penalties, respectively, into the objective function of fuzzy c-means. We also extend this idea to co-clustering by considering pairwise constraints of two types of objects to produce fuzzy co-clusters. Efficient and scalable algorithms have been proposed for parallel implementation. The experimental results with real-world datasets show good performance of the proposed approaches with respect to effectiveness, efficiency and scalability. [ABSTRACT FROM AUTHOR]