Anomaly Detection by an Ensemble of Random Pairs of Hyperspheres

Anomaly detection is a crucial task in data mining, focusing on identifying data points that deviate significantly from the main patterns in the data. This paper introduces Anomaly Detection by an Ensemble of Random Pairs of Hyperspheres (ADERH), a new isolation-based technique leveraging two key observations: (i) anomalies are comparatively rare, and (ii) they typically deviate stronger from general patterns than normal data points. Drawing on a δ-separation argument, ADERH constructs an ensemble of multi-scale hyperspheres built upon randomly paired data points to identify anomalies. To address inevitable overlaps between anomalous and normal regions in the feature space, ADERH integrates two complementary concepts: Pitch, which highlights points near hypersphere boundaries, and NDensity, which down-weights hyperspheres centered on sparse (and often anomalous) regions. By averaging these local, density-adjusted "isolation" indicators across many random subsets, ADERH yields robust anomaly scores that clearly separate normal from abnormal samples. Extensive experiments on diverse real-world datasets show that ADERH consistently outperforms state-of-the-art methods while maintaining linear runtime scalability and stable performance across varying hyperparameter settings. • RARITY: Anomalies comprise only a small proportion of the dataset, i.e., most of the samples represent regular data points [Barnett et al., 1994 , Aggarwal, 2016 ]. • DEVIATION: Anomalies differ significantly from the general patterns in a dataset, suggesting that they originate from different processes than regular samples [Hawkins, 1980] . We formalize these properties with the δ-separation assumption: normal samples form compact regions, while anomalies lie mainly beyond their boundaries (Section 3.1). However, current isolationbased methods have certain limitations. IForest [Liu et al., 2008] efficiently detects anomalies via random partitioning, but its reliance on global, axis-aligned splits can miss complex or locally defined outliers. INNE [Bandaragoda et al., 2014] attempts to address this by utilizing hyperspheres to capture local patterns, but it is sensitive to the sample size and assigns equal weights to hyperspheres, which can limit its robustness [Bandaragoda et al., 2018] . We propose ADERH, a method that isolates anomalies using compact hyperspheres designed to minimize overlap with anomalies. Guided by the δ-separation principle-which assumes that anomalies lie beyond normal regions -ADERH constructs small local subsets and pairs of points. By halving each pairwise distance, it forms compact hyperspheres that adapt to multiple scales and collectively cover diverse normal regions, thereby reducing overlap with anomalies and enhancing isolation precision. Since perfect δ-separation may fail in practice, we refine each hypersphere's isolation signal with (i) Pitch, a ratio-based distance measure accentuating boundary anomalies, and (ii) NDensity, which down-weights hyperspheres in sparse (anomalous) regions. Finally, ADERH ensemble-averages these local isolation signals, further reducing variance and enhancing robustness on real-world, heterogeneous data. In summary, we make the following contributions: • We present ADERH, a novel technique for assigning anomaly scores to data points by analyzing their position within multiple hyperspheres and the characteristics of these hyperspheres. • Hyperspheres may still include anomalies near the boundary or span around anomalies, blurring distinctions between normal and abnormal data. To overcome this, ADERH introduces two components: NDensity, which down-weights hyperspheres in sparse (anomalous) regions, and Pitch, which emphasizes points near hypersphere boundaries. • Thus, ADERH more effectively distinguishes anomalies from normal samples, overcoming limitations that arise from relying solely on hypersphere-or distance-based methods. • ADERH delivers robust and stable anomaly scores across a wide range of hyperparameters, maintains high efficiency on large-scale datasets, and-through extensive experiments involving both default parameter settings and exhaustive grid searches-outperforms stateof-the-art anomaly detection methods. Related work Over the past few decades, anomaly detection has been extensively studied using various techniques such as density, isolation, or deep learning. Isolation-based approaches assume that a small fraction of the data consists of anomalies (RARITY) and that those have different attribute values than normal data points (DEVIATION). A prominent example is the Isolation Forest (IForest) [Liu et al., 2008], which recursively partitions the feature space by selecting random features and random split values; anomalies tend to have shorter paths from the root node. The Extended Isolation Forest (EIF) [Hariri et al., 2019] improves on IForest by using hyperplanes with randomly determined slopes for splitting, enhancing accuracy across diverse datasets.