Are Outlier Detection Methods Resilient to Sampling?

Laure Berti-Équille, Ji Meng Loh, Saravanan ThirumuruganathanarXiv 2019 · arXiv

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.

Visualizing the impact of sampling on data distribution and detection boundaries using scatter plots and boxplots.

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.

Conceptual framework for calculating Resilience based on the overlap between full dataset detections and sample-based detections.

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

Abstract

Outlier detection is a fundamental task in data mining and has many applications including detecting errors in databases. While there has been extensive prior work on methods for outlier detection, modern datasets often have sizes that are beyond the ability of commonly used methods to process the data within a reasonable time. To overcome this issue, outlier detection methods can be trained over samples of the full-sized dataset. However, it is not clear how a model trained on a sample compares with one trained on the entire dataset. In this paper, we introduce the notion of resilience to sampling for outlier detection methods. Orthogonal to traditional performance metrics such as precision/recall, resilience represents the extent to which the outliers detected by a method applied to samples from a sampling scheme matches those when applied to the whole dataset. We propose a novel approach for estimating the resilience to sampling of both individual outlier methods and their ensembles. We performed an extensive experimental study on synthetic and real-world datasets where we study seven diverse and representative outlier detection methods, compare results obtained from samples versus those obtained from the whole datasets and evaluate the accuracy of our resilience estimates. We observed that the methods are not equally resilient to a given sampling scheme and it is often the case that careful joint selection of both the sampling scheme and the outlier detection method is necessary. It is our hope that the paper initiates research on designing outlier detection algorithms that are resilient to sampling.
BibTeX
@misc{bertiequille2019are,
  author = {Laure Berti-Équille and Ji Meng Loh and Saravanan Thirumuruganathan},
  title = {{Are Outlier Detection Methods Resilient to Sampling?}},
  year = {2019},
  eprint = {1907.13276},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.13276},
}
Figure