Comparative study of neighbor-based methods for local outlier detection

Zhuang Qi, Junlin Zhang, Xiaming Chen, Xin Qi

TL;DR

This paper introduces a modular three-level taxonomy—Information, Methodology, and Neighbor—to systematically categorize and evaluate neighbor-based outlier detection. By decoupling these components, the authors demonstrate that "mixing and matching" specific strategies, such as using dynamic selection in high-dimensional subspaces, can create outlier detection algorithms that significantly outperform traditional, static methods.

What Problem Does This Paper Address?

Outlier detection is the process of identifying data points that deviate significantly from the norm. Neighbor-based methods are the "bread and butter" of this field, operating on the simple intuition that an outlier is a point whose characteristics differ sharply from its closest peers.

However, most research has focused on inventing new "outlier factors" (the mathematical formulas used to score a point's "weirdness") while treating the definition of the "neighborhood" as a solved problem. The authors argue that the way we define and select neighbors is just as critical as the scoring formula. Existing methods often struggle with "local" outliers—points that look normal on a global scale but are anomalies within their specific cluster—especially when dealing with high-dimensional data or datasets with varying densities.

Methods

The core contribution is a taxonomy that breaks neighbor-based methods into three modular levels:

  1. Information Level: Determines the data used.
  2. Full-space: Uses all original features.
  3. Subspace: Uses dimensionality reduction (like PCA) to find more reliable distances in high-dimensional settings.
  4. Methodology Level: Determines how neighbors are found.
  5. Static Sorting: The standard approach; simply calculate distances and pick the top $K$ closest points.
  6. Dynamic Selection: An iterative process where neighbors are selected one by one, allowing the "neighborhood" to grow more flexibly based on the distribution of the data.
  7. Neighbor Level: Defines the type of relationship.
  8. KNN: Standard K-Nearest Neighbors.
  9. RKNN (Reverse KNN): Points that consider the target sample as their neighbor.
  10. Hybrid: A combination of KNN and RKNN.
  11. NaN (Natural Neighbors): Mutual friends (A is a neighbor of B, and B is a neighbor of A).
  12. Non-NaN: "Fake friends" (A is a neighbor of B, but B does not consider A a neighbor).

By treating these as interchangeable parts, the authors can evaluate "hybrid" algorithms (e.g., a Subspace-based, Dynamic-selection, RKNN method) to see which combinations work best.

Datasets

The authors evaluated their taxonomy using:

  • 3 Synthetic Datasets: Designed to test specific challenges like varying cluster densities, complex shapes (crescents), and low-density patterns.
  • 11 Real-World Datasets: Sourced from the UCI repository, including Arrhythmia, PenDigits, Pima (diabetes), and WDBC (breast cancer). These range in size from 148 to nearly 10,000 samples and feature counts from 5 to 258.

Key Insights and Ideas

  • The Power of Reciprocity (RKNN): Reverse K-Nearest Neighbor methods were the standout performers. They achieved the best results in 22 out of the comparative experiments. This suggests that "who considers me a neighbor" is often a stronger signal of belonging than "who is closest to me."
  • Dynamic is Better for High-D: Static sorting creates rigid, spherical neighborhoods that fail in high-dimensional space (the "curse of dimensionality"). Dynamic selection is more "organic" and adapts better to complex data distributions.
  • The "Fake Friend" Advantage: In low-density scenarios, "Non-NaN" neighbors (points that are in your KNN set but don't consider you a neighbor back) were surprisingly effective at identifying outliers.
  • The NaN Paradox: While "Natural Neighbors" (NaN) sound like a robust way to define a cluster, they are often too similar to the target point. This makes it nearly impossible to distinguish a true outlier from a legitimate inlier, leading to poor performance.

Key Results

  • RKNN Dominance: RKNN-based methods consistently secured the highest AUC (Area Under the Curve) scores across most datasets.
  • Hybrid Success: Hybrid methods (combining KNN and RKNN) were the second-best performers, winning 11 times.
  • Subspace vs. Full-space: Subspace methods generally outperformed full-space methods on high-dimensional datasets like Waveform, proving that feature reduction is essential for reliable neighbor calculation.
  • Hyperparameter Sensitivity: The performance of almost all algorithms peaked when the number of neighbors ($K$) was around 30, providing a useful rule of thumb for practitioners.

Limitations and Future Work

While the taxonomy provides a powerful framework, the authors acknowledge a few hurdles:

  • Subspace Selection: The paper primarily uses PCA for subspace construction. However, they note that the choice of which subspace to use is critical and remains a difficult problem to automate.
  • Adaptive K: The value of $K$ (number of neighbors) still needs to be manually tuned. Future work could focus on algorithms that find the optimal $K$ adaptively based on local data density.
  • Scalability: While not the primary focus, the computational cost of dynamic selection vs. static sorting in massive datasets warrants further investigation.
  • New Frontiers: The authors suggest extending this modular approach to emerging fields like federated learning and complex visual classification tasks.

Summary updated

Abstract

The neighbor-based method has become a powerful tool to handle the outlier detection problem, which aims to infer the abnormal degree of the sample based on the compactness of the sample and its neighbors. However, the existing methods commonly focus on designing different processes to locate outliers in the dataset, while the contributions of different types neighbors to outlier detection has not been well discussed. To this end, this paper studies the neighbor in the existing outlier detection algorithms and a taxonomy is introduced, which uses the three-level components of information, neighbor and methodology to define hybrid methods. This taxonomy can serve as a paradigm where a novel neighbor-based outlier detection method can be proposed by combining different components in this taxonomy. A large number of comparative experiments were conducted on synthetic and real-world datasets in terms of performance comparison and case study, and the results show that reverse K-nearest neighbor based methods achieve promising performance and dynamic selection method is suitable for working in high-dimensional space. Notably, it is verified that rationally selecting components from this taxonomy may create an algorithms superior to existing methods.
BibTeX
@article{qi2025comparative,
  author = {Zhuang Qi and Junlin Zhang and Xiaming Chen and Xin Qi},
  title = {{Comparative study of neighbor-based methods for local outlier detection}},
  journal = {J. Ambient Intell. Smart Environ.},
  year = {2025},
  doi = {10.1177/18761364251359900},
}

Loading related content...

Figure