Search papers, labs, and topics across Lattice.
This paper develops a semi-supervised clustering framework that leverages the statistical relationship between clustering and anomaly detection to define robust clusters in noisy environments. By employing a novel Perception algorithm that utilizes an expectation-based threshold for outlier detection, the method minimizes the need for manual parameter tuning and effectively isolates non-anomalous data points. Evaluations on various datasets show that the approach can achieve strong clustering performance with minimal user input, demonstrating linear scalability and robustness against noise.
Clustering can be revolutionized by treating it as a dual problem to anomaly detection, achieving strong results with just a handful of seed labels.
This paper introduces a semi-supervised clustering framework grounded in the statistical duality between grouping principles and anomaly detection. We address the challenge of robust cluster definition in noisy environments -- a task where partitioning algorithms often over-assign outliers and density-based methods remain sensitive to heuristic global parameters. Drawing on \textit{a-contrario} statistical reasoning and Gestalt proximity principles, we define a cluster as a maximal subset of data points containing no anomalies relative to a null hypothesis of uniform randomness. Central to this approach is the Perception algorithm, which utilises a principled expectation-based threshold ($\mathbb{E} < 1$) to identify outliers without manual parameter tuning. By treating clustering as the dual of anomaly detection, we employ an iterative ``clustering-by-exclusion'' mechanism. The algorithm is seed-guided, leveraging minimal user-provided labels to initialise robust cluster medians and form initial groups, which are subsequently expanded by admitting non-anomalous points. This approach naturally isolates fringe points, isolated noise, and emerging unknown clusters. We evaluate the method on synthetic and real-world benchmarks, including image and text datasets represented through raw, linear-reduced, and neighbourhood-preserving embeddings. Results demonstrate that with as few as 10--30 seeds per cluster, the proposed method achieves competitive and often very strong performance under a practical low-tuning benchmarking protocol, while maintaining linear scalability with respect to both observations and dimensionality for a fixed number of seeded clusters and iterations.
