Semi-supervised Clustering by Input Pattern Assisted Pairwise Similarity Matrix Completion

Many semi-supervised clustering algorithm-s have been proposed to improve the clus-tering accuracy by effectively exploring the available side information that is usually in the form of pairwise constraints. However, there are two main shortcomings of the ex-isting semi-supervised clustering algorithms. First, they have to deal with non-convex op-timization problems, leading to clustering re-sults that are sensitive to the initialization. Second, none of these algorithms is equipped with theoretical guarantee regarding the clus-tering performance. We address these limi-tations by developing a framework for semi-supervised clustering based on input pattern assisted matrix completion. The key idea is to cast clustering into a matrix completion problem, and solve it efficiently by exploiting the correlation between input patterns and cluster assignments. Our analysis shows that under appropriate conditions, only O(log n) pairwise constraints are needed to accurately recover the true cluster partition. We verify the effectiveness of the proposed algorithm by comparing it to the state-of-the-art semi-supervised clustering algorithms on several benchmark datasets. 1.