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.
1. Introduction
Outlier detection is the process of identifying data points that deviate significantly from the norm. Neighbor-based methods are fundamental to this field, operating on the intuition that an outlier is a point whose characteristics differ sharply from its closest peers. While much research has focused on inventing new outlier scoring factors, the definition and selection of the neighborhood itself are often overlooked. This paper argues that the way neighbors are selected is critical, particularly for identifying "local" outliers—points that appear normal globally but are anomalous within specific clusters—especially in high-dimensional data.
2. A Taxonomy of Neighbor-based Methods
The core contribution of this work is a modular three-level taxonomy that breaks neighbor-based methods into interchangeable components: Information, Neighbor, and Methodology.
2.1 Information Level
This level determines the data representation used for distance calculations.
- Full-space: Utilizes all original features.
- Subspace: Employs dimensionality reduction (e.g., PCA) to find more reliable distances in high-dimensional settings.
2.2 Neighbor Level
This level defines the nature of the relationship between a point and its neighbors.
- KNN: Standard K-Nearest Neighbors.
- RKNN (Reverse KNN): Points that consider the target sample as one of their own neighbors.
- Hybrid: A combination of KNN and RKNN.
- NaN (Natural Neighbors): Mutual neighbors (A is a neighbor of B, and B is a neighbor of A).
- Non-NaN: Unidirectional relationships where A is a neighbor of B, but B does not reciprocate.
2.3 Methodology Level
This level determines the algorithmic approach to finding neighbors.
- Static Sorting: The standard approach of calculating distances and selecting the top $K$ closest points.
- Dynamic Selection: An iterative process where the neighborhood grows flexibly based on the data distribution.
3. Experimental Evaluation
The taxonomy was evaluated using three synthetic datasets designed to test challenges like varying cluster densities and complex shapes, alongside 11 real-world datasets from the UCI repository (e.g., Arrhythmia, PenDigits, WDBC). These datasets range in size from 148 to nearly 10,000 samples.
4. Key Insights and Results
- RKNN Dominance: Reverse K-Nearest Neighbor methods were the top performers in 22 experiments. This suggests that reciprocity—being considered a neighbor by others—is a stronger indicator of inlier status than simple proximity.
- Dynamic Selection for High-D: Static sorting often fails in high-dimensional spaces due to the "curse of dimensionality," creating rigid neighborhoods. Dynamic selection adapts more organically to complex distributions.
- The "Fake Friend" Advantage: In low-density scenarios, Non-NaN neighbors were surprisingly effective at identifying outliers.
- Subspace vs. Full-space: Subspace methods generally outperformed full-space methods on high-dimensional datasets, proving that feature reduction is essential for reliable neighbor calculation.
5. Conclusion
By decoupling the components of neighbor-based outlier detection, this study demonstrates that "mixing and matching" specific strategies can create algorithms that significantly outperform traditional methods. Future work will focus on automating subspace selection and developing adaptive methods for choosing the optimal number of neighbors ($K$).
Summary updated