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

arXiv: https://arxiv.org/abs/1801.09955 · HTML: https://mlsanity.com/paper/1801.09955/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2018.

## Built on by (most cited first, 9 of 9)

- [Human-in-the-Loop Visual Re-ID for Population Size Estimation](https://mlsanity.com/paper/2312.05287/) (2023)
- [Correlation Clustering with Active Learning of Pairwise Similarities](https://mlsanity.com/paper/2302.10295/) (2023)
- [Query-augmented Active Metric Learning](https://mlsanity.com/paper/2111.04871/) (2021)
- [Personalized Clustering via Targeted Representation Learning](https://mlsanity.com/paper/2412.13690/) (2024)
- [A3S: A General Active Clustering Method with Pairwise Constraints](https://mlsanity.com/paper/2407.10196/) (2024)
- [Information-Theoretic Active Correlation Clustering](https://mlsanity.com/paper/2402.03587/) (2024)
- [Semi-Supervised Clustering via Structural Entropy with Different Constraints](https://mlsanity.com/paper/2312.10917/) (2023)
- [Data Skeleton Learning: Scalable Active Clustering with Sparse Graph Structures](https://mlsanity.com/paper/2509.08530/) (2025)
- [Semi-Supervised Hyperbolic Hierarchical Clustering with Set-Level Structural Priors](https://mlsanity.com/paper/2606.01525/) (2026)

## Abstract (arXiv)

Clustering is inherently ill-posed: there often exist multiple valid clusterings of a single dataset, and without any additional information a clustering system has no way of knowing which clustering it should produce. This motivates the use of constraints in clustering, as they allow users to communicate their interests to the clustering system. Active constraint-based clustering algorithms select the most useful constraints to query, aiming to produce a good clustering using as few constraints as possible. We propose COBRA, an active method that first over-clusters the data by running K-means with a K that is intended to be too large, and subsequently merges the resulting small clusters into larger ones based on pairwise constraints. In its merging step, COBRA is able to keep the number of pairwise queries low by maximally exploiting constraint transitivity and entailment. We experimentally show that COBRA outperforms the state of the art in terms of clustering quality and runtime, without requiring the number of clusters in advance.