PaperlayerView exact revision on arXiv

Source-linked AI summary

COPOD: Copula-Based Outlier Detection

Zheng Li, Yue Zhao, Nicola Botta, Cezar Ionescu, Xiyang Hu

arXiv:2009.09463v1stat.MLcs.IRcs.LG

TL;DR

Outlier detection needs accurate, fast, and interpretable identification of rare observations, while high-dimensional settings create additional challenges. COPOD uses empirical copulas and tail probabilities to score extremeness without hyperparameters. Across 30 datasets, it performs strongly, ranks among the fastest methods, and provides dimension-level abnormality guidance.

  • Problem

    Outlier detection requires high detection performance, fast execution, and interpretability, while high-dimensional spaces create additional challenges for detection algorithms.

  • Method

    COPOD constructs empirical distribution-based tail probabilities for each observation and uses them to produce comparative outlier scores without learning or stochastic training.

  • Results

    COPOD ranks first among 10 compared detectors, scoring 1.5% higher in ROC-AUC and 2.7% higher in Average Precision than the second-best detector.

  • Takeaways & Limitations

    COPOD combines strong detection performance with interpretability through dimension-level abnormality contributions and efficiency for large, high-dimensional datasets.

Abstract

from arXiv · show

Outlier detection refers to the identification of rare items that are deviant from the general data distribution. Existing approaches suffer from high computational complexity, low predictive capability, and limited interpretability. As a remedy, we present a novel outlier detection algorithm called COPOD, which is inspired by copulas for modeling multivariate data distribution. COPOD first constructs an empirical copula, and then uses it to predict tail probabilities of each given data point to determine its level of "extremeness". Intuitively, we think of this as calculating an anomalous p-value. This makes COPOD both parameter-free, highly interpretable, and computationally efficient. In this work, we make three key contributions, 1) propose a novel, parameter-free outlier detection algorithm with both great performance and interpretability, 2) perform extensive experiments on 30 benchmark datasets to show that COPOD outperforms in most cases and is also one of the fastest algorithms, and 3) release an easy-to-use Python implementation for reproducibility.

I. INTRODUCTION

COPOD addresses practical and methodological limitations in outlier detection with a deterministic, interpretable, efficient algorithm. Across 30 datasets, it is reported to rank first among compared detectors.

  • Existing outlier detection applications require high detection performance, fast execution, and strong interpretability.Applications include credit card fraud detection, network intrusion detection, and synthetic data generation.
  • Subjective hyperparameter choices can lead to different outcomes.
  • COPOD is deterministic and hyperparameter-free, using ECDFs without learning or stochastic training.This avoids challenges in hyperparameter selection and potential biases.
  • COPOD ranks first among 10 compared detectors, scoring 1.5% more in ROC-AUC and 2.7% more in Average Precision than the second-best detector.
  • COPOD quantifies each dimension’s abnormality contribution through the Dimensional Outlier Graph to guide investigation of abnormality causes.Practitioners can focus on certain subspaces to improve data quality.
  • COPOD averages third in execution time across 30 datasets and can handle 10,000 features and 1,000,000 observations on a standard laptop.The paper attributes this scalability to low computation overhead.

II. PROPOSED ALGORITHM

Copulas separate marginal distributions from dependency structure, allowing multivariate distributions to be modeled through their marginals and a linking dependence function. Sklar’s Theorem guarantees this representation for multivariate CDFs with continuous marginals.

  • Copulas separate marginal distributions from the dependency structure of a multivariate distribution.
  • A d-variate copula is a CDF on [0,1]^d for a random vector with Uniform(0,1) marginals.
  • Uniform distributions can be transformed into desired distributions through inverse sampling.
  • A copula describes a joint distribution using only its marginal distributions.
  • Modeling each dimension separately while linking marginals into a joint distribution provides flexibility for high-dimensional datasets.
  • Sklar’s Theorem guarantees a copula for any multivariate CDF with continuous marginals and provides a closed-form construction.The copula is uniquely determined when the marginals are continuous.

B. Empirical Copula

COPOD builds a nonparametric empirical copula from empirical cumulative distribution functions. The empirical construction has discrete uniform marginals and asymptotically converges to the underlying copula.

  • COPOD fits empirical cumulative distribution functions nonparametrically to construct an empirical copula.
  • The empirical CDF is defined from the observed values in each dataset dimension.
  • Empirical copula observations are obtained by applying the inverse of the copula representation to the empirical distributions.
  • An empirical copula supported on n grid points has discrete uniform marginals on {1/n, 2/n, ..., 1}.
  • The empirical copula asymptotically converges to the underlying copula.The passage attributes this convergence to the central limit theorem.

C. Theoretical Framework of COPOD

COPOD treats outliers as observations with unusually small multivariate tail probabilities. It estimates these probabilities through a three-stage empirical-copula process.

  • COPOD computes empirical CDFs, constructs an empirical copula, and uses it to approximate tail probabilities for each observation.
  • An observation is considered more likely to be an outlier when either its lower-tail or upper-tail probability is extremely small.
  • The resulting tail probabilities quantify how rarely each point occurs relative to the multivariate distribution.

1) Outliers as Tail Events:

COPOD estimates marginal tail probabilities empirically, combines them across dimensions, and uses negative log probabilities to avoid numerical collapse in high dimensions.

  • Outliers as Tail Events: COPOD feeds each coordinate into its empirical CDF to obtain copula observations, whose product estimates the left-tail probability.
  • Computing Right Tail Probabilities: Right-tail probabilities are computed analogously by transforming the observations and applying the empirical CDF.
  • Computing Right Tail Probabilities: The empirical CDF has support only on {1/n, 2/n, ..., 1}^d, so a maximum copula observation can produce a zero right-tail probability.
  • Computing Right Tail Probabilities: COPOD derives the right-tail ECDF from -X to avoid the zero-probability problem caused by the empirical CDF’s bounded support.
  • Diminishing Tail Probabilities: As dimensionality increases, joint tail probabilities decrease exponentially and the copula function approaches zero.
  • Diminishing Tail Probabilities: COPOD therefore sums negative log probabilities, preserving monotonicity while avoiding diminishing numerical values.

4) Skewness Correction:

COPOD corrects tail selection for skewed dimensions. This prevents one-sided outlier patterns from being misclassified by relying on the wrong tail.

  • Skewness Correction: Using only left-tail probabilities works for data whose outliers all lie on the lower side of the distribution.
  • Skewness Correction: Using only right-tail probabilities performs poorly when no unusually large outliers exist, misidentifying relatively large normal points.
  • Skewness Correction: Averaging both tails compromises the result and identifies only half of the left-tail outliers in the illustrated dataset.
  • Skewness Correction: COPOD uses the dimension’s skewness to select the appropriate left or right tail for each marginal.
  • Skewness Correction: The skewness-corrected version captures the correct outliers in the illustrated datasets.

D. COPOD Algorithm

COPOD converts marginal empirical tail behavior into comparative outlier scores. Its skewness correction and tail aggregation determine how extremeness is measured across dimensions.

  • COPOD takes a d-dimensional dataset and produces one comparative outlier score for each observation.Scores lie in (0, ∞); larger values indicate greater relative outlier likelihood, not an outlier probability.
  • The first stage fits empirical left-tail CDFs, right-tail CDFs from -X, and a skewness vector.
  • The second stage computes empirical copula observations and selects skewness-corrected tail observations dimension by dimension.
  • The final stage takes the maximum negative log probability across left, right, and skewness-corrected empirical copulas as the outlier score.
  • A smaller tail probability produces a larger negative log value and therefore a stronger outlier score.

E. COPOD as an Interpretable Outlier Detector

COPOD makes outlier detection interpretable by decomposing each point’s anomaly into dimensional tail-based scores. Its Dimensional Outlier Graph highlights the specific feature subspaces contributing to an outlier decision.

  • Interpretability: COPOD evaluates anomalous behaviour dimension by dimension, enabling explanations of which feature subspaces contribute to a point’s outlier status.The paper motivates interpretability as useful for understanding and auditing model decisions.
  • Tail-probability choices: In the toy example, skewness-corrected tail probabilities produce the best detection among left-tail, right-tail, two-tail, and skewness-corrected alternatives.The figure compares ground truth with detections based on different tail-probability choices.
  • Dimensional interpretation: COPOD quantifies each dimension’s anomalousness using tail-copula scores and compares these scores with thresholds to indicate why points are considered outliers.The dimensional score can be compared with −log(0.01) = 4.61 or a top-α percentile threshold.
  • Dimensional interpretation: The Dimensional Outlier Graph plots nine dimensional scores alongside the 99th-percentile and 65.01th-percentile bands for each data point.The 65.01th-percentile band corresponds to 1−contamination rate.
  • Breast Cancer Wisconsin example: The example connects the highlighted dimensions with extreme cell-size characteristics and a greater likelihood of reproduction via mitosis rather than meiosis.The interpretation is intended to guide practitioners toward particular subspaces for investigating data quality.

A. Datasets and Evaluation Metrics

COPOD is evaluated against nine other detectors on 30 benchmark datasets using repeated-trial ROC-AUC and average precision. It achieves the strongest average detection performance and remains among the fastest methods tested.

  • Datasets and metrics: 30 benchmark datasets are evaluated using 60% training data, 40% validation data, and averages over 10 independent trials.Performance is measured with ROC-AUC and average precision.
  • Variant evaluation: Among COPOD variants, skewness-corrected ECDF achieves the highest average ROC-AUC of 0.8247 and average precision of 0.5649.Two-tail, right-tail, and left-tail variants score lower on both reported metrics.
  • Compared detectors: COPOD is compared with nine detectors spanning angle-based, clustering-based, feature-bagging, histogram-based, isolation, nearest-neighbor, online, local-factor, and one-class SVM approaches.The competing implementations are available in PyOD.
  • ROC-AUC results: 82.47% average ROC-AUC places COPOD 1.5% above the second-best alternative across the 30 datasets.COPOD ranks first on 12 datasets and in the top two on 16.
  • Average precision results: 56.49% average precision places COPOD 2.7% above the second-place detector across the 30 datasets.COPOD ranks first on 12 datasets and in the top two on 17.
  • Computation time: 0.227 seconds is COPOD’s average time to process the 30 test datasets, ranking third behind HBOS and LODA.HBOS averages 0.046 seconds and LODA 0.062 seconds.

E. Scaling to High Dimensions

COPOD is designed for low computational overhead and scales across both feature dimensionality and dataset size. The reported experiments show that it can process very large, high-dimensional datasets without retraining for new points.

  • Scalability evaluation: COPOD’s scalability is tested on random datasets with dimensions 10, 100, 1,000, and 10,000 and observation counts from 1,000 to 1,000,000.The datasets are used strictly to evaluate computation time.
  • Computational overhead: COPOD incurs low computational overhead compared with proximity-based models requiring pairwise distances and learning-based models requiring training.The paper presents this as a consequence of COPOD’s computational design.
  • Scalability results: COPOD can process 10,000-dimensional datasets with 1,000,000 data points in under an hour and a half on a personal computer.Table III reports performance in seconds across dimension and data-size settings.
  • Deployment implication: COPOD requires no retraining to fit new data points, making it suitable for real-time prediction applications within the reported scope.This claim accompanies the scalability results in Table III.
  • Overall evaluation: The conclusion characterizes COPOD as comparable or better than leading detectors in both detection accuracy and computational cost across real-world experiments.The paper reports comparative studies on 30 datasets and describes COPOD as one of the fastest algorithms.
Loading 2009.09463v1…