cs.LGJun 17, 2026

Seed-Guided Semi-Supervised Clustering by A-Contrario Anomaly Detection

Authors: Nassir Mohammad

Organizations: Cyber Innovation Lab, Airbus, Newport, UK

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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 (E<1\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.

Explore similar work

CardsList
May 8, 2026cs.LG

Simple KNN-Based Outlier Detection Achieves Robust Clustering

Being robust to the presence of outliers is crucial for applying clustering algorithms in practice. In the \textit{robust k-Means} problem (i.e., kk-Means with outliers), the goal is to remove zz outliers and minimize the kk-Means cost on the remaining points. Despite the close connection between robust kk-Means and outlier detection, both theoretical and empirical understanding of the effectiveness of classic outlier detection heuristics\textit{classic outlier detection heuristics} for robust kk-Means remains limited. In this paper, we prove that under a practical assumption on the optimal cluster sizes, simply removing points with large KK-Nearest-Neighbor distances achieves performance comparable to prior work in terms of approximation guarantees: it yields a constant-factor reduction from robust kk-Means to standard kk-Means, without introducing additional centers or discarding extra outliers, as is commonly required by existing approaches. Empirically, experiments on real-world datasets show that our method outperforms or matches several more sophisticated algorithms in terms of clustering cost and runtime. These results demonstrate that simple KNN-based heuristics can be surprisingly effective for robust clustering, highlighting new opportunities to bridge techniques from outlier detection and clustering.
Tianle Jiang, Yufa Zhou
K-MeansImage ClusteringOutliersApproximate Nearest-Neighbor Search
AskPDF
Sep 22, 2026stat.ME

Automatic depth-based local center clustering via ββ-integrated local depth and adaptive grouping

Clustering is an unsupervised learning technique that partitions unlabeled data into groups. Most existing methods require user-specified parameters, such as the number of clusters or neighborhood size. Conversely, we propose automatic depth-based local center clustering (A-DLCC), a fully data-driven method that eliminates numerical parameter tuning. A-DLCC uses the ββ-integrated local depth to identify stable exemplars, points consistently central across multiple locality levels, termed local centers, which are ranked by their representativeness. Each local center induces a group of similar points, with group-level similarity measured by a proposed nonparametric metric called group-level local similarity. To guide merging, we incorporate the bottleneck path idea from graph theory, which forms the basis of our adaptive merging criterion. Based on this criterion, we design a single agglomeration rule in which a group is either absorbed by a neighbor it reaches better than itself or bonded to a neighbor that both sides find more reachable than their own background, every merge being additionally required to be carried by a contact stronger than a configuration-model null expects. The rule automatically estimates the number of clusters and decides when to stop merging. Experiments on synthetic and real data show that A-DLCC produces interpretable clustering results without parameter tuning.
Siyi Wang, Alexandre Leblanc, Paul D. McNicholas
Image Clustering
AskPDF
Oct 15, 2025cs.LG

Isolation-based Spherical Ensemble Representations for Tabular Anomaly Detection

Unsupervised tabular anomaly detection is a critical task with applications spanning offensive language detection, network security, and quality control. Despite extensive research, existing unsupervised anomaly detection methods still face fundamental challenges including conflicting distributional assumptions, computational inefficiency, and difficulty handling different anomaly types. To address these problems, we propose ISER (Isolation-based Spherical Ensemble Representations) that extends existing isolation-based methods by using hypersphere radii as a monotonic transformation of local density characteristics while maintaining linear time and constant space complexity w.r.t. the dataset size. ISER constructs ensemble representations where hypersphere radii encode local sparsity through a monotonic transformation of density: smaller radii correspond to dense regions while larger radii correspond to sparse regions. We introduce a novel similarity-based scoring method that measures pattern consistency by comparing ensemble representations against a theoretical anomaly reference pattern. Additionally, we enhance the performance of Isolation Forest by using ISER and adapting the scoring function to address axis-parallel bias and local anomaly detection limitations. Comprehensive experiments on 20 real-world datasets demonstrate ISER's competitive performance over 12 SOTA methods.
Yang Cao, Sikun Yang, Hao Tian +5
Reconstruction-Based Anomaly DetectionAnomaly DetectionUnsupervisedTabular LearningEnsemble
AskPDF