FALCON : An effective and robust method for active clustering with pairwise constraints

Constraint-based clustering incorporates user knowledge into the clustering process through pairwise constraints, which specify whether two elements should be linked (Must-Link) or separated (Cannot-Link). Active constraint-based clustering extends this framework by selecting constraints iteratively to improve clustering quality while minimizing user effort. While effective, its performance strongly depends on the choice of queried constraints. Existing active approaches often ignore the underlying data distribution, which leads to a non-informed exploration of the data space and results in constraints that are uninformative or unrepresentative. We introduce FALCON ( F unctional A ctive L earning with Co nstraints based on criticisms and N eighborhood prototypes), a novel active constraint-based clustering method. FALCON formulates constraint selection as a modelling task that uses a minimal set of representative samples (prototypes) to approximate the data distribution, identifying areas with poor coverage (criticisms). Both prototypes and criticisms are then selected from this model to generate pairwise constraints that direct queries towards the most informative and homogeneous regions of the data space. Extensive experiments on 31 real-world datasets demonstrate that FALCON consistently outperforms state-of-the-art methods in terms of query efficiency, clustering accuracy, and robustness.