COBRA: A Fast and Simple Method for Active Clustering with Pairwise Constraints

1 Introduction

Clustering is inherently subjective [Caruana et al., 2006; von Luxburg et al., 2014]: a single dataset can often be clustered in multiple ways, and different users may prefer different clusterings. This subjectivity is one of the motivations for constraintbased (or semi-supervised) clustering [Wagstaff et al., 2001; Bilenko et al., 2004]. Methods in this setting exploit background knowledge to obtain clusterings that are more aligned with the user's preferences. Often, this knowledge is given in the form of pairwise constraints that indicate whether two instances should be in the same cluster (a must-link constraint) or not (a cannot-link constraint) [Wagstaff et al., 2001]. In traditional constraint-based clustering systems the set of constraints is assumed to be given a priori, and in practice, the pairs that are queried are often selected randomly. In contrast, in active clustering [Basu et al., 2004a; Mallapragada et al., 2008; Xiong et al., 2014] it is the method itself that decides which pairs to query. Typically, active methods query pairs that are more informative than random ones, which improves clustering quality.

This work introduces an active constraint-based clustering method named Constraint-Based Repeated Aggregation (COBRA). It differs from existing approaches in several ways. First, it aims to maximally exploit constraint transitivity and entailment [Wagstaff et al., 2001], two properties that allow deriving additional constraints from a given set of constraints. By doing this, the actual number of pairwise constraints that COBRA works with is typically much larger than the number of pairwise constraints that are queried from the user. Secondly, COBRA introduces the assumption that there exist small local regions in the data that are grouped together in all potential clusterings. To clarify this, consider the example of clustering images of people taking different poses (e.g. facing left or right). There are at least two natural clustering targets for this data: one might want to cluster based on identity or pose. In an appropriate feature space, one expects images that agree on both criteria (i.e. of a single person, taking a single pose) to be close. There is no need to consider all of these instances individually, as they will end up in the same cluster for each of the two targets that the user might be interested in. COBRA aims to group such instances into a super-instance, such that they can be treated jointly in the clustering process. Doing so substantially reduces the number of pairwise queries. Thirdly, COBRA is an inherently active method: the constraints are selected during the execution of the algorithm itself, as constraint selection and algorithm execution are intertwined. In contrast, existing approaches consist of a component that selects constraints and another one that uses them during clustering.

Our experiments show that COBRA outperforms state-ofthe-art active clustering methods in terms of both clustering quality and runtime. Furthermore, it has the distinct advantage that it does not require knowing the number of clusters beforehand, as the competitors do. In many realistic clustering scenarios this number is not known, and running an algorithm with the wrong number of clusters often results in a significant decrease in clustering quality.

We discuss related work on (active) constraint-based clustering in section 2. In section 3 we elaborate the key ideas in COBRA and describe the method in more detail. We present our experimental evaluation in section 4, and conclude in section 5.

2 Background and RelatedWork

Most existing constraint-based methods are extensions of wellknown unsupervised clustering algorithms. They use the constraints either in an adapted clustering procedure [Wagstaff et al., 2001; Rangapuram and Hein, 2012; Wang et al., 2014], to learn a similarity metric [Xing et al., 2003; Davis et al., 2007], or both [Bilenko et al., 2004; Basu et al., 2004b]. Constraintbased extensions have been developed for most clustering algorithms, including K-means [Wagstaff et al., 2001; Bilenko et al., 2004], spectral clustering [Rangapuram and Hein, 2012; Wang et al., 2014], DBSCAN [Lelis and Sander, 2009; Campello et al., 2013] and EM [Shental et al., 2004].

Basu et al. [2004a] introduce a strategy to select the most informative constraints, prior to performing a single run of a constraint-based clustering algorithm. They show that active constraint selection can improve clustering performance. Several selection strategies have been proposed since [Mallapragada et al., 2008; Xu et al., 2005; Xiong et al., 2014], most of which are based on the classic approach of uncertainty sampling. As COBRA also chooses which pairs to query, we consider it to be an active method, and in our experiments we compare to other methods in this setting. Note, however, that COBRA is quite different from existing methods in active constrained clustering and active learning in general. For COBRA, selecting which pairs to query is inherent to the clustering procedure, whereas for most other methods the selection strategy is optional and considered to be a separate component.

In its core, COBRA is related to hierarchical clustering as it follows the same procedure of sequentially trying to merge the two closest clusters. Constraints have been used in hierarchical clustering before but in different ways. Davidson et al. [2009], for example, present an algorithm to find a clustering hierarchy that is consistent with a given set of constraints. Nogueira et al. [2012] propose an active semi-supervised hierarchical clustering algorithm that is based on merge confidence. Also related to ours is the work of Campello et al. [2013], who have developed a framework to extract from a given hierarchy a flat clustering that is consistent with a given set of constraints. The key difference is that COBRA starts from super-instances, i.e. small clusters produced by K-means, and that each merging decision is settled by a pairwise constraint.

The idea of working with a small number of representatives (in our case the super-instance medoids, as will be discussed in section 3) instead of all individual instances has been used before, but for very different purposes. For example, Yan et al. [2009] use it to speed up unsupervised spectral clustering, whereas we use it to reduce the number of pairwise queries.

3 Constraint-Based Repeated Aggregation

Constraint-based clustering algorithms aim to produce a clustering of a dataset that resembles an unknown target clustering Y as close as possible. The algorithm cannot query the cluster labels in Y directly, but can query the relation between pairs of instances. Amust-link constraint is obtained if the instances have the same cluster label in Y , a cannot-link constraint otherwise. The aim is to produce a clustering that is close to the target clustering Y , using as few pairwise queries as possible.

Several strategies can be used to exploit constraints in clustering. Figure 1 illustrates some of them. The most naive strategy is to query all pairwise relations, and construct clusters as sets of instances that are connected by a must-link constraint (Figure 1a). Though this is clearly not a good strategy in any scenario, it allows us to formulate a baseline for further improvements. It always results in a perfect clustering, but at a very high cost: for a dataset of N instances, (N2 ) questions are asked.

The previous strategy can be improved by exploiting constraint transitivity and entailment, two well known properties in constraint-based clustering [Wagstaff et al., 2001; Bilenko et al., 2004]. Must-link constraints are known to be transitive:

whereas cannot-link constraints have an entailment property:

Thus, every time a constraint is queried and added to the set of constraints, transitivity and entailment can be applied to expand the set. This strategy is illustrated in Figure 1b. Exploiting transitivity and entailment significantly reduces the number of pairwise queries needed to obtain a clustering, without a loss in clustering quality.

The order in which constraints are queried strongly influences the number of constraints that can be derived. In general, it is better to obtain must-link constraints early on. That way, any future query involving one of the instances connected by a must-link also applies to all others. This suggests querying the closest pairs first, as they are more likely to belong to the same cluster and hence be connected by a must-link constraint. This is strategy is illustrated in Figure 1c.

The previous strategies all obtain a perfect clustering, but require a high number of queries which makes them inapplicable for reasonably sized datasets. To further reduce the number of queries, COBRA groups similar instances into super-instances and only clusters their representatives, i.e. medoids. It assumes that all instances within a super-instance are connected by a must-link constraint. While clustering the medoids, COBRA uses both previously discussed strategies of querying the closest pairs and exploiting transitivity and entailment. This strategy, illustrated in Figure 1d, results in a substantial reduction of the number of queries. It does not always result in a perfect clustering as it is possible that the instances within a particular super-instance should not be grouped together w.r.t. the target clustering.

Table 1 illustrates to what extent each of the improvements described above reduces the number of queries. We perform an extensive evaluation of the quality of the clusterings that COBRA produces in section 4.

3.1 Algorithmic Description

After presenting the main motivations for each step of COBRA, we now give a more detailed description in Algorithm 1. Let X = {xi}Ni=1 , xi ∈ Rm the instances to be clustered. The set of instances X is first over-clustered into NS disjoint subsets, namely super-instances {Si}NS i=1 , such that ⋃i Si = X.

Hence, this dataset has 4 target clusterings: identity, pose, expression and sunglasses. We extract a 2048-value feature vector for each image by running it through the pre-trained Inception-V3 network [Szegedy et al., 2015] and storing the output of the second last layer. Finally, we also cluster the 20 newsgroups text data. For this dataset, we consider two tasks: clustering documents from 3 newsgroups on related topics (the target clusters are comp.graphics, comp.os.ms-windows and comp.windows.x, as in [Basu et al., 2004a; Mallapragada et al., 2008]), and clustering documents from 3 newsgroups on very different topics (alt.atheism, rec.sport.baseball and sci.space, as in [Basu et al., 2004a; Mallapragada et al., 2008]). We first extract tf-idf features, and next apply latent semantic indexing (as in [Mallapragada et al., 2008]) to reduce the dimensionality to 10. This brings the total to 17 datasets, for which 21 clustering tasks are defined (15 UCI datasets with a single target, CMU faces with 4 targets, and 2 subsets of the 20 newsgroups data).

Experimental Methodology

We use a cross-validation procedure that is highly similar to the ones used in e.g. [Basu et al., 2004a] and [Mallapragada et al., 2008]. In each of 5 folds, 20% of the instances are set aside as the test set. The clustering algorithm is then run on the entire dataset, but can only query pairwise constraints for which both instances are in the training set. To evaluate the quality of the resulting clustering, we compute the Adjusted Rand index (ARI, [Hubert and Arabie, 1985]) only on the instances in the test set. The ARI measures the similarity between two clusterings, in this case between the one produced by the constraint-based clustering algorithm and the one indicated by the class labels. An ARI of 0 means that the clustering is not better than random, 1 indicates a perfect clustering. The final score for an algorithm for a particular dataset is computed as the average ARI over the 5 folds.

The exact number of pairwise queries is not known beforehand for COBRA, but more super-instances generally results in more queries. To evaluate COBRA with varying amounts of user input, we run it with 25, 50 and 100 super-instances. For each fold, we execute the following steps:

• Run COBRA and count how many constraints it needs.
• Run the competitors with the same number of constraints.
• Evaluate the resulting clusterings by computing the ARI on the test set.

To make sure that COBRA only queries pairs of which both instances are in the training set, the medoid of a super-instance is calculated based on only the training instances in that superinstance (and as such, test instances are never queried during clustering). In the rare event that a super-instance contains only test instances, it is merged with the nearest super-instance that does contain training instances. For the MinMax and NPU selection strategies, pairs involving an instance from the test set are simply excluded from selection.

Results

The results over all 21 clustering tasks are summarized in Tables 2 and 3. Table 2 reports wins and losses against each of the 4 competitors. It shows that COBRA tends to produce better clusterings than its competitors. The difference with COSC is significant according to the Wilcoxon test with p < 0.05, whereas the difference with MPCKMeans is not. Table 3 shows the average ranks for COBRA and its competitors. The Friedman aligned rank test [Hodges and Lehmann, 1962], which has more power than the Friedman test when the number of algorithms under comparison is low [Garca et al., 2010], indicates that for 50 and 100 super-instances, the differences in rank between COBRA and all competitors are significant, using a posthoc Holm test with p < 0.05.

Running Competitors with Different Numbers of Queries In the previous experiments, the competitors are run with the same number of queries that COBRA required, as for COBRA this cannot be fixed beforehand. One might wonder whether this constitutes an advantage for COBRA, and whether the above conclusions also hold when competitors can be run with different numbers of constraints. To answer this question, we run COBRA with a wider range of super-instances, and its competitors with more numbers of constraints. Figure 3 shows the results for 4 datasets, but the conclusions that are drawn here also hold for the others. A first conclusion is that for the datasets for which COBRA outperforms its competitors in the experiments discussed above, it also does so for larger numbers of constraints (e.g. in Figures 3a and 3b). As such, the results discussed in the previous section are representative. Secondly,

• [Bilenko et al., 2004] Mikhail Bilenko, Sugato Basu, and Raymond J. Mooney. Integrating constraints and metric learning in semi-supervised clustering. In Proc. of 21st International Conference on Machine Learning, pages 81-88, July 2004.
• [Campello et al., 2013] Ricardo J. G. B. Campello, Davoud Moulavi, Arthur Zimek, and J¨org Sander. A framework for semi-supervised and unsupervised optimal extraction of clusters from hierarchies. Data Mining and Knowledge Discovery, 27(3):344-371, 2013.
• [Caruana et al., 2006] Rich Caruana, Mohamed Elhawary, and Nam Nguyen. Meta clustering. In Proc. of the International Conference on Data Mining, 2006.
• [Davidson and Ravi, 2009] I Davidson and SS Ravi. Using instance-level constraints in agglomerative hierarchical clustering: theoretical and empirical results. Data mining and knowledge discovery, pages 1-30, 2009.
• [Davis et al., 2007] Jason V. Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S. Dhillon. Information-theoretic metric learning. In Proceedings of the 24th International Conference on Machine Learning, ICML '07, pages 209216, New York, NY, USA, 2007. ACM.
• [Garca et al., 2010] Salvador Garca, Alberto Fernndez, Julin Luengo, and Francisco Herrera. Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power. Information Sciences, 180(10):2044 - 2064, 2010. Special Issue on Intelligent Distributed Information Systems.
• [Hodges and Lehmann, 1962] J. L. Hodges and E. L. Lehmann. Rank methods for combination of independent experiments in analysis of variance. The Annals of Mathematical Statistics, 33(2):482-497, 1962.
• [Hubert and Arabie, 1985] Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of Classification, 2(1):193-218, 1985.
• [Lelis and Sander, 2009] Levi Lelis and J¨org Sander. Semisupervised density-based clustering. In 2009 Ninth IEEE International Conference on Data Mining, pages 842-847, Dec 2009.
• [Mallapragada et al., 2008] Pavan K. Mallapragada, Rong Jin, and Anil K. Jain. Active query selection for semisupervised clustering. In Proc. of the 19th International Conference on Pattern Recognition, 2008.
• [Nogueira et al., 2012] Bruno M Nogueira, M Jorge, and Solange O Rezende. HCAC : Semi-supervised Hierarchical Clustering Using Confidence-Based Active Learning. (1):139-153, 2012.
• [Rangapuram and Hein, 2012] Syama S. Rangapuram and Matthias Hein. Constrained 1-spectral clustering. In Proc. of the 15th International Conference on Artificial Intelligence and Statistics, 2012.
• [Shental et al., 2004] Noam Shental, Aharon Bar-Hillel, Tomer Hertz, and Daphna Weinshall. Computing Gaussian mixture models with EM using equivalence constraints. In
• In Advances in Neural Information Processing Systems 16, 2004.
• [Szegedy et al., 2015] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and ZbigniewWojna. Rethinking the inception architecture for computer vision. CoRR, abs/1512.00567, 2015.
• [von Luxburg et al., 2014] Ulrike von Luxburg, Robert C. Williamson, and Isabelle Guyon. Clustering: Science or Art? In Workshop on Unsupervised Learning and Transfer Learning, JMLR Workshop and Conference Proceedings 27, 2014.
• [Wagstaff et al., 2001] Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schroedl. Constrained K-means Clustering with Background Knowledge. In Proc. of the Eighteenth International Conference on Machine Learning, pages 577584, 2001.
• [Wang et al., 2014] Xiang Wang, Buyue Qian, and Ian Davidson. On constrained spectral clustering and its applications. Data Mining and Knowledge Discovery, 28(1):1-30, 2014.
• [Xing et al., 2003] Eric P. Xing, Andrew Y. Ng, Michael I. Jordan, and Stuart Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems 15, pages 505-512, 2003.
• [Xiong et al., 2014] Sicheng Xiong, Javad Azimi, and Xiaoli Z. Fern. Active learning of constraints for semisupervised clustering. IEEE Transactions on Knowledge and Data Engineering, 26(1):43-54, 2014.
• [Xu et al., 2005] Qianjun Xu, Marie desJardins, and Kiri L. Wagstaff. Active Constrained Clustering by Examining Spectral Eigenvectors, pages 294-307. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.
• [Yan et al., 2009] Donghui Yan, Ling Huang, and Michael I. Jordan. Fast approximate spectral clustering. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09, pages 907-916, New York, NY, USA, 2009. ACM.