Abstract
As datasets grow to massive scales, practitioners often rely on sampling to make outlier detection computationally feasible. However, it remains unclear if an algorithm trained on a small sample identifies the same outliers as it would on the full dataset. This paper introduces resilience to sampling, a metric that quantifies this consistency. Our evaluation of seven diverse algorithms across synthetic and real-world datasets reveals that while density-based methods often lack resilience due to shifts in local data structures, simple statistical methods and outlier ensembles remain remarkably stable, offering a reliable path for scalable big data analysis.
Introduction
In the era of "Big Data," many sophisticated outlier detection algorithms are too computationally expensive to run on entire datasets. A common workaround is to train models on a representative sample. This raises a critical question: is a model trained on a 10% sample a faithful proxy for the full-scale analysis?
Traditional metrics like precision and recall measure accuracy against a known "ground truth." However, in many real-world scenarios, ground truth is unavailable. We instead require our sampling shortcut to be consistent with the full-scale results. This paper identifies a gap in current evaluation frameworks, noting that an algorithm might be highly accurate on a full dataset but lose "resilience"—failing to find the same outliers—when given only a sample.
Methods
Formalization of Resilience
The authors define resilience ($\rho$) as the harmonic mean of "relative precision" and "relative recall." In this framework, the "ground truth" is defined as the set of outliers the algorithm would have detected if it had processed the entire dataset.
Resilience Estimation
Since running an algorithm on the full dataset is often the very bottleneck we aim to avoid, the authors propose an EM-based approach to estimate resilience using only samples. By adapting the Dawid-Skene model, different outlier detectors are treated as "noisy observers," allowing for the inference of a consensus without requiring full dataset results.
Comparative Study
Seven algorithms were evaluated across four categories:
- Statistical: $3\sigma$, Boxplot, Chi-Square ($\chi^2$).
- Deviation-based: Median Absolute Deviation (MAD).
- Distance-based: Mahalanobis distance, K-Means.
- Density-based: Local Outlier Factor (LOF).
Experimental Setup
The study utilized a mix of synthetic bivariate normal distributions (with 1%, 5%, and 10% outlier rates) and eight real-world benchmarks from the UCI and ODDS repositories, including Arrhythmia, Diabetes, Spambase, and Isolet5. These datasets provided a wide range of dimensions and outlier prevalence to test the algorithms' stability.
Key Insights and Results
Resilience vs. Accuracy
Resilience is orthogonal to traditional accuracy. A model may be excellent at identifying outliers on a full dataset but have low resilience if its "view" of outliers changes drastically with different samples.
The Density Trap
Density-based methods like LOF were found to be the least resilient. Sampling inherently alters the "local density" of data points; removing 90% of the data destroys the local neighborhoods that LOF relies on, leading to inconsistent results across different samples.
Stability in Simplicity and Ensembles
Simple univariate statistical methods (e.g., $3\sigma$) proved to be the most resilient because they rely on global properties like mean and variance, which are better preserved in random samples than complex local structures. Furthermore, outlier ensembles—which combine multiple methods—emerged as a "silver bullet," maintaining high stability by relying on the consensus of constituent models.
Conclusion
There is no "one size fits all" solution for large-scale outlier detection. Practitioners must carefully choose a combination of sampling schemes and detection methods. While density-based methods struggle under standard random sampling, statistical methods and ensembles offer a robust alternative. Future work should explore density-preserving sampling techniques to improve the resilience of more complex algorithms.
Summary updated