Active query selection for constraint-based clustering algorithms

Semi-supervised clustering uses a small amount of supervised data in the form of pairwise constraints to improve the clustering performance. However, most current methods are passive in the sense that the pairwise constraints are provided beforehand and selected randomly. This may lead to the use of constraints that are redundant, unnecessary, or even harmful to the clustering results. In this paper, we address the problem of constraint selection to improve the performance of constraint-based clustering algorithms. Based on the concepts of Maximum Mean Discrepancy, we select the set of most informative instances that minimizes the difference in distribution between the labeled and unlabeled data. Then, we query these instances with the existing neighborhoods to determine which neighborhood they belong. The experimental results with state-of-the-art methods on different real world dataset demonstrate the effectiveness and efficiency of the proposed method.