Online active constraint selection for semi-supervised clustering

Due to strong demand for the ability to enforce top-down struc-ture on clustering results, semi-supervised clustering methods using pairwise constraints as side information have received increasing at-tention in recent years. However, most current methods are passive in the sense that the side information is provided beforehand and selected randomly. This may lead to the use of constraints that are redundant, unnecessary, or even harmful to the clustering results. To overcome this, we present an active clustering framework which se-lects pairwise constraints online as clustering proceeds, and propose an online constraint selection method that actively selects pairwise constraints by identifying uncertain nodes in the data. We also pro-pose two novel methods for computing node uncertainty: one global and parametric and the other one local and nonparametric. We evalu-ate our active constraint selection method with two different semi-supervised clustering algorithms on UCI, digits, gene and image datasets, and achieve results superior to current state of the art ac-tive techniques.