Novel CCD-Based Algorithms for High-Accuracy Outlier Detection

Music City Center 

We propose a novel family of outlier detection algorithms built upon Cluster Catch Digraphs (CCDs)
and their extensions, designed to overcome the limitations of existing methods in handling
high-dimensional, heterogeneous, and irregularly shaped data.
Our approach introduces Mutual Catch Graphs (MCGs) to enhance the discrimination between inliers
and outliers by incorporating local density and geometric structure.
Building on CCDs derived from Kolmogorov-Smirnov-type statistics, Ripley's K function,
and nearest neighbor distances, we develop a suite of algorithms---U-MCCD, UN-MCCD, and their
shape-adaptive variants (SU-MCCD and SUN-MCCD)---which adaptively refine cluster boundaries
and suppress false detections.
These methods are largely parameter-free or require minimal tuning,
making them scalable and user-friendly.
We provide theoretical guarantees for computational complexity,
demonstrate robustness through extensive Monte Carlo experiments,
and evaluate performance across a wide range of dimensions, cluster configurations,
and contamination levels.
Our results show that shape-adaptive variants significantly improve detection accuracy,
particularly in high-dimensional or non-uniform settings,
where traditional graph- and density-based methods often fail.

Outlier detection

Outlyingness score

Graph-based clustering

Cluster catch digraphs

High-dimensional data 

Section on Statistical Learning and Data Science