Source-linked AI summary
ECOD: Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functions
Zheng Li, Yue Zhao, Xiyang Hu, Nicola Botta, Cezar Ionescu, George H. Chen
TL;DR
Existing outlier-detection methods can be costly, difficult to tune, and hard to interpret, especially for large, high-dimensional data. ECOD uses per-dimension empirical cumulative distributions to estimate tail probabilities and aggregate them into outlier scores; across 30 benchmarks, it outperforms 11 baselines while remaining parameter-free, efficient, scalable, and interpretable.
Problem
Outlier detection requires accurate, fast, and interpretable identification of anomalous data points, but existing methods often have limited interpretability and can be costly or difficult to tune.
Method
ECOD computes left- and right-tail empirical cumulative distributions per dimension, estimates each point’s tail probabilities, and aggregates them into a final outlier score without hyperparameter tuning.
Results
ECOD outperforms 11 baseline outlier-detection methods on 30 benchmark datasets, ranking highest overall and achieving an average ROC score of 0.825, 2% above iForest.
Takeaways & Limitations
ECOD provides an interpretable outlier score through per-dimension tail probabilities and supports efficient, scalable processing with O(nd) time complexity and dimension-wise parallelization.
Takeaways & Limitations
ECOD is not designed for multimodal distributions where an outlier may lie in neither the left nor right tail.
Abstract
from arXiv · showhide
Outlier detection refers to the identification of data points that deviate from a general data distribution. Existing unsupervised approaches often suffer from high computational cost, complex hyperparameter tuning, and limited interpretability, especially when working with large, high-dimensional datasets. To address these issues, we present a simple yet effective algorithm called ECOD (Empirical-Cumulative-distribution-based Outlier Detection), which is inspired by the fact that outliers are often the "rare events" that appear in the tails of a distribution. In a nutshell, ECOD first estimates the underlying distribution of the input data in a nonparametric fashion by computing the empirical cumulative distribution per dimension of the data. ECOD then uses these empirical distributions to estimate tail probabilities per dimension for each data point. Finally, ECOD computes an outlier score of each data point by aggregating estimated tail probabilities across dimensions. Our contributions are as follows: (1) we propose a novel outlier detection method called ECOD, which is both parameter-free and easy to interpret; (2) we perform extensive experiments on 30 benchmark datasets, where we find that ECOD outperforms 11 state-of-the-art baselines in terms of accuracy, efficiency, and scalability; and (3) we release an easy-to-use and scalable (with distributed support) Python implementation for accessibility and reproducibility.
1 INTRODUCTION
The introduction presents ECOD as a parameter-free, interpretable outlier detector based on per-dimension empirical cumulative distributions and tail probabilities. It targets accuracy, efficiency, and scalability challenges in unsupervised detection.
- Motivation: Existing outlier detection methods can lose accuracy and runtime efficiency on large, high-dimensional data, while unsupervised hyperparameter tuning remains difficult.These limitations motivate a method that avoids expensive computation and tuning.
- Method idea: ECOD uses empirical cumulative distribution functions to identify rare events through tail probabilities, avoiding histogram binning choices and their associated tuning.It computes univariate ECDFs separately for each dimension and aggregates tail probabilities across dimensions under an independence assumption.
- Effectiveness: ECOD outperforms 11 baseline outlier detection methods on 30 benchmarks, ranking highest overall.The evaluation covers detection effectiveness across a broad benchmark collection.
- Efficiency and scalability: ECOD has time complexity O(nd), parallelizes across dimensions, and requires no hyperparameter-tuning time.With a single thread, it handles 1,000,000 observations and 10,000 features on a standard laptop in 2 hours.
- Interpretability: Per-dimension left- and right-tail probabilities show how each dimension contributes to a point’s overall outlier score.This information guides practitioners toward dimensions relevant for improving data quality.
2 RELATED WORK
Related work covers proximity-, statistical-, learning-, and ensemble-based outlier detection methods, emphasizing their trade-offs in computation, tuning, dimensionality, and interpretability. ECOD combines nonparametric per-dimension modeling with straightforward aggregation.
- Proximity-based methods: Proximity-based methods use local density or neighbor distances, but are computationally expensive, hyperparameter-sensitive, and vulnerable to the curse of dimensionality.Neighbor definitions depend on choices such as distance function and neighborhood size.
- Statistical models: Statistical outlier detection fits probability distributions, using parametric or nonparametric models such as Gaussian mixtures, KDE, and histograms.Parametric methods assume a distributional form, whereas nonparametric methods do not.
- Learning-based methods: Learning-based methods train models to distinguish outliers from inliers, including one-class SVMs, clustering methods, neural networks, and autoencoders.Many such methods are computationally expensive, require nontrivial tuning, and can be difficult to interpret.
- Ensemble-based methods: Ensemble-based methods combine multiple detectors and often work well on high-dimensional data, but may require meta-detector tuning and offer less interpretability.Examples include feature bagging, isolation forests, and LSCP.
- ECOD positioning: ECOD models each dimension nonparametrically and aggregates the resulting models across dimensions, making its detection process easy to interpret.Its structural assumption is that dimensions are independent, so it cannot represent all possible multivariate distributions.
3 PROPOSED ALGORITHM: ECOD
This section introduces the detailed presentation of ECOD through its problem formulation, algorithmic motivation, technical design, and properties. The properties include interpretability and scalability.
- 3.1 Problem Formulation and Challenges: The section first presents the problem statement for unsupervised outlier detection and its associated challenges.The problem formulation appears in Section 3.1.
- 3.2 Motivation and Technical Details: It then develops ECOD’s motivation and technical details.The motivation and algorithmic design are presented in Section 3.2.
- 3.3 Properties: The section discusses ECOD’s interpretability and scalability properties.These properties are covered in Section 3.3.
3.1 Problem Formulation and Challenges
The paper formulates unsupervised outlier detection as assigning an outlier score to each data point in an i.i.d. dataset. It identifies dimensionality, interpretability, and tuning as central challenges.
- Problem formulation: The setup assumes n data points X1, X2, . . . , Xn ∈ R^d sampled independently and identically.The full dataset is represented as a matrix X ∈ R^(n×d).
- Problem formulation: An outlier detection model assigns each data point Xi an outlier score Oi, with higher scores indicating greater outlier likelihood.The score is a real-valued comparison measure.
- Challenges: High-dimensional or large datasets make many methods less accurate or less computationally scalable, especially when density estimation or pairwise distances are required.High-dimensional density estimation can require the number of data points to grow exponentially with dimensionality.
- Challenges: Many outlier detection algorithms provide limited interpretability, making it difficult to explain why a financial transaction is classified as fraudulent.Applications may require evidence supporting an outlier decision.
- Challenges: Without ground-truth outlier labels, model selection and hyperparameter tuning are challenging in existing unsupervised methods.This challenge arises because tuning lacks labeled guidance.
3.2 The Proposed ECOD
ECOD estimates left- and right-tail behavior independently for each dimension, then aggregates these probabilities into an outlier score. It uses skewness to select the more informative tail per dimension, avoiding exhaustive tail combinations while preserving interpretability.
- Motivation: ECOD treats outliers as rare events and estimates their extremeness through left- and right-tail probabilities across dimensions.Lower estimated tail probabilities indicate that a point is less likely under the corresponding distributional behavior.
- High-level idea: The method avoids joint-ECDF estimation by computing a univariate ECDF for each dimension under an independence assumption.This sidesteps the slower convergence of joint ECDFs as dimensionality increases.
- Algorithm: ECOD computes left- and right-tail ECDFs for every feature, aggregates the resulting probabilities into O_i, and returns higher scores for more likely outliers.The scores are comparison values rather than probabilities.
- Skewness correction: Skewness automatically selects the tail used for a dimension, rather than evaluating all 2^d left-right combinations.Negative skewness favors the left tail, while positive skewness favors the right tail.
- Tail-selection example: In the synthetic example, left-tail probabilities work well, right-tail probabilities work poorly, averaging compromises performance, and skewness-corrected ECOD captures the correct outliers.The data contain 180 inliers and 20 outliers, with the outliers lying on the left side of the distribution.
3.3 Properties of ECOD
ECOD is designed to explain outlier decisions dimension by dimension and to scale linearly with the number of samples and features. Its dimensional scores identify which features contribute most to a point’s outlyingness, while independent feature processing supports distributed acceleration.
- Interpretability: ECOD exposes each dimension’s tail probability, showing how individual features contribute to a point’s overall outlier score.These contributions can guide practitioners toward dimensions relevant for improving data quality.
- Interpretability: A Dimensional Outlier Graph compares feature-level outlier scores with a reference threshold to explain why a point is classified as an outlier.For the malignant 70th BreastW sample, dimensions 2, 5, and 9 reach the 99th-percentile band while other features remain below it.
- Efficiency and scalability: ECOD has O(nd) time and space complexity because both ECDF estimation and tail-probability aggregation process n observations across d dimensions.The stated complexity applies to both the estimation and aggregation steps.
- Efficiency and scalability: Independent dimension processing allows ECOD to distribute ECDF estimation and tail-probability computation across multiple workers.The implementation provides both single-thread and distributed versions in PyOD.
4 EMPIRICAL EVALUATION
ECOD is evaluated on 30 public benchmark datasets against eleven baseline detectors, with experiments covering tail-probability variants, overall accuracy, failure conditions, efficiency, and scalability. It generally achieves stronger detection performance while retaining low computational cost and handling large, high-dimensional datasets.
- Evaluation setup: ECOD is evaluated on 30 public outlier-detection benchmark datasets using ten independent trials and ROC and average precision metrics.The datasets come from the ODDS and DAMI repositories; Shuttle versions are truncated to 10,000 observations because some baselines fail to converge at larger sizes.
- Tail-probability variants: Automatic tail selection outperforms ECOD variants using only left tails, only right tails, or their average.ECOD achieves average ROC 0.824 and average precision 0.564, compared with 0.781 and 0.476 for ECOD-B, 0.714 and 0.411 for ECOD-R, and 0.506 and 0.251 for ECOD-L.
- Overall results: ECOD outperforms the eleven baselines overall, achieving average ROC 0.825 and average AP 0.565 while ranking first on 13 and 12 of 30 datasets, respectively.It ranks among the top three on 21 datasets for ROC and 20 datasets for AP; its ROC is 2% above iForest and its AP is 5% above iForest.
- Overall results: ECOD also outperforms HBOS, a detector with a similar per-dimension mechanism, because ECOD retains more within-bin information and avoids choosing histogram-bin counts.The reported averages are ROC 0.825 and AP 0.565 for ECOD versus ROC 0.795 and AP 0.509 for HBOS.
- Case study: ECOD’s performance degrades when outliers mingle with inliers rather than appearing in the tails of at least some dimensions.The case study reports strong performance on Breastw and Shuttle but not top performance on Ionosphere and Speech; the authors note that such cases are unlikely when outliers differ from normal points in at least one dimension.
5 CONCLUSION AND FUTURE WORKS
ECOD detects outliers by aggregating per-dimension tail probabilities estimated from univariate ECDFs, offering a parameter-free, scalable approach. Its scope excludes multimodal settings where outliers may lie outside both tails.
- ECOD estimates left- and right-tail probabilities with univariate ECDFs, then aggregates them into an outlier score for each data point.
- ECOD is parameter-free and evaluated on 30 benchmark datasets, where it outperforms state-of-the-art baselines while remaining fast and scalable.
- The method provides single- and multi-thread Python implementations for accessible use.
- Future work: ECOD is not designed for multimodal distributions in which an outlier lies in neither the left nor right tail.