Active clustering enhances traditional semi-supervised clustering by introducing machine-led interaction, where informative constraints are dynamically selected and posed to humans. This enables goal-driven interaction and reduces the number of required constraints for achieving high-quality clustering. In this paper, we propose a newly designed Active Clustering framework with Minimal Constraint Graph (ACMCG). ACMCG operates on two cooperating tailored sparse graphs: a tree-structured graph (clustering tree) representing the nested clustering result, and a minimal constraint graph that supports constraint deduction during iterative refinement. In each refinement round, (a) the most suspicious edge in the tree is identified for constraint verification; (b) if a cannot-link constraint is confirmed, a pruning-and-grafting approach is performed to refine the clustering tree, guided by our proposed constraint deduction strategies; (c) the constraint is either deduced from the minimal constraint graph using transitive and probabilistic deduction, or obtained via user interaction when deduction fails. Extensive experiments across diverse domains demonstrate that ACMCG consistently outperforms both classical and state-of-the-art methods in accuracy, while significantly reducing the number of user-provided constraints and maintaining low computational cost, highlighting its cost-effectiveness in real-world applications.

Active constraint-based clustering enhances semi-supervised clustering through a machine-led interaction process. This approach dynamically selects the most informative constraints to query, minimizing the number of human annotations required. Existing methods face three key challenges in real-world applications: scalability, timeliness, and robustness against user annotation errors. In this work, we propose a robust and high-efficiency Active Clustering framework with Multi-user Collaboration (ACMC). ACMC constructs a diffusion tree using the nearest-neighbor technique and employs a multi-user online collaboration framework to iteratively refine clustering results. In each iteration: (a) nodes with high uncertainty and representativeness are selected in batch; (b) well-designed multi-user asynchronous query categorizes selected nodes using neighborhood sets, reducing individual workloads and improving overall timeliness; (c) user-provided constraints and newly discovered categories are synchronized, with user confidences dynamically updated to enhance robustness against erroneous annotations; (d) categorized nodes, stored in neighborhood sets, serve as sources in the diffusion tree to refine the clusters. Experimental results demonstrate that ACMC outperforms baseline methods in terms of clustering quality, scalability, and robustness against user annotation errors.

Clustering is fundamentally a subjective task: a single dataset can be validly clustered in various ways, and without further information, clustering systems cannot determine the appropriate clustering to perform. This underscores the importance of integrating constraints into clustering, enabling users to convey their preferences to the system. Active constraint-based clustering approaches prioritize the identification of the most valuable constraints to inquire about, striving to achieve effective clustering with the minimal number of constraints needed. We propose an A ctive C lustering with D iffusion M odel (ACDM). ACDM applies the nearest-neighbor technique to construct a diffusion graph, and utilizes an online framework to refine the clustering result iteratively. In each iteration, (a) nodes with high uncertainty and representativeness are selected in batch mode, (b) then a novel neighborhood-set-based query is used for categorizing the selected nodes, using pairwise constraints, and (c) the categorized nodes are used as source nodes in the diffusion model for cluster refinement. We experimentally demonstrate that ACDM outperforms state-of-the-art methods in terms of clustering quality and scalability.