ADOD: Adaptive Density Outlier Detection

Outlier detection plays a dual role in data analysis: cleansing data to optimize the performance of downstream tasks and identifying potentially rare valuable events or patterns. Proximity-based methods, which are independent of data distribution assumptions, are plagued by parameter selection and performance challenges when handling data with varying densities. This study proposed a novel unsupervised algorithm named Adaptive Density Outlier Detection (ADOD) to address these challenges. The core innovation of ADOD involves two main aspects: adaptive neighborhood boundaries and density consistency scoring. First, instead of relying on a predefined fixed radius, ADOD employs perplexity to calculate the local scale of each data point. It then dynamically adjusts the neighborhood boundaries according to this scale to adapt to data with varying densities. Second, ADOD estimates local density using a mutual neighbor graph and combines the density differences between data points and their neighbors to compute outlier scores, effectively distinguishing outliers that significantly deviate from their surroundings. This study evaluated ADOD on one synthetic and 32 real datasets, and compared it with 14 classical and state-of-the-art algorithms from different categories. Extensive experimental results demonstrated the superior performance of ADOD, achieving the highest average accuracy across ROC, P@N, and AP metrics. This study promotes the development of outlier detection techniques and expands their potential for real-time applications.