Semi-supervised clustering uses a small amount of supervised data to aid unsupervised learning. One typical approach specifies a limited number of must-link and cannotlink constraints between pairs of examples. This paper presents a pairwise constrained clustering framework and a new method for actively selecting informative pairwise constraints to get improved clustering performance. The clustering and active learning methods are both easily scalable to large datasets, and can handle very high dimensional data. Experimental and theoretical results confirm that this active querying of pairwise constraints significantly improves the accuracy of clustering when given a relatively small amount of supervision. In many data mining and machine learning tasks, there is a large supply of unlabeled data but limited labeled data, since labeled data can be expensive to generate. Consequently, semi-supervised learning, learning from a combination of both labeled and unlabeled data, has become a topic of significant recent interest [6, 20, 30] . More specifically, semisupervised clustering, the use of class labels or pairwise constraints on some examples to aid unsupervised clustering, has been the focus of several recent projects [4, 22, 33, 34] . In a semi-supervised clustering setting, the focus is on clustering large amounts of unlabeled data in the presence of a small amount of supervised data. In this setting, we consider a framework that has pairwise must-link and cannotlink constraints between points in a dataset (with an associated cost of violating each constraint), in addition to having distances between the points. These constraints specify that two examples must be in the same cluster (must-link) or different clusters (cannot-link) [33] . In real-world unsupervised learning tasks, e.g., clustering for speaker identification in a conversation [17] , visual correspondence in multiview image processing [7] , clustering multi-spectral information from Mars images [32] , etc., considering supervision in the form of constraints is generally more practical than
Another related line of research in machine learning is clustering or classification with constraints REF , where supervision is given in the form of constraints.
Active Semi-Supervision for Pairwise Constrained Clustering
SDM
Computer Science