TL;DR
This paper introduces SiNNE, a novel, dimensionality-unbiased scoring measure for Outlying Aspect Mining (OAM). SiNNE significantly speeds up OAM by avoiding computationally expensive normalizations and instance-wise score calculations, making OAM feasible for large and high-dimensional datasets.
What Problem Does This Paper Address?
Outlying Aspect Mining (OAM) aims to identify specific "aspects" or subsets of features within a dataset where a particular data point is anomalous. Imagine an insurance claim: OAM could tell you which combination of factors (e.g., claim amount, location, and type of damage) makes the claim suspicious, rather than just saying the claim itself is an outlier.
Existing OAM methods often rely on distance or density-based outlier scores. A major challenge is that these scores are sensitive to the dimensionality of the subspace they are calculated in. To compare scores across subspaces of different dimensions, researchers have used Z-score normalization. However, this process is computationally very expensive, requiring the calculation of outlier scores for all data instances in each subspace. This makes OAM impractical for large datasets. Furthermore, the authors discover that Z-score normalization can sometimes produce misleading results, even introducing bias.
Methods
The core contribution of this paper is the Simple Isolation score using Nearest Neighbor Ensemble (SiNNE). SiNNE is designed to be:
- Dimensionality-unbiased: Its raw score can be directly compared across subspaces of varying dimensions, eliminating the need for Z-score normalization.
- Efficient: It avoids the costly computation of scores for all data instances in each subspace.
SiNNE is inspired by anomaly detection methods that use nearest neighbor ensembles. For each subspace, SiNNE constructs multiple "models" based on small random subsamples of the data. Each model defines a "normal region" using hyperspheres centered around data points. A query point is considered an anomaly if it falls outside these hyperspheres in a significant number of models. The anomaly score is then derived from this isolation.
Datasets
The paper evaluates SiNNE on a combination of synthetic and real-world datasets:
- Synthetic Dataset: A 10-dimensional dataset with 19 known outliers, used for evaluating the quality of discovered subspaces against ground truth.
- Real-world Datasets:
- Pendigits
- Shuttle
- ALOI
- KDDCup99
These datasets vary in size (N) and dimensionality (M), allowing for comprehensive evaluation of both effectiveness and efficiency.
Key Insights and Ideas
- Z-score normalization's Achilles' heel: The paper convincingly demonstrates that Z-score normalization, while intended to make scores comparable, can introduce bias. Specifically, it can unfairly favor subspaces with high variance in density, even if the raw density of the query point isn't as extreme. This is a critical finding for anyone using Z-score normalization in OAM.
- Dimensionality-unbiasedness is crucial for OAM: The ability to directly compare outlier scores across subspaces of different dimensions is essential for effective OAM. SiNNE achieves this inherently, simplifying the process and improving interpretability.
- Efficiency is paramount for practical OAM: The computational burden of existing methods is a major bottleneck. SiNNE's isolation-based approach bypasses the need to score every data point in every subspace, leading to dramatic speedups.
- A simpler definition of "normal" can be effective: By using a straightforward hypersphere-based definition of normal regions, SiNNE achieves competitive or superior results compared to more complex density estimation methods.
Key Results
- Effectiveness: SiNNE achieved exact matches with ground truth for all queries on the synthetic dataset, outperforming existing methods like RKDE, ZKDE, and ZsGrid. On real-world datasets, visual inspection suggests SiNNE identifies comparable or better outlying subspaces.
- Efficiency: SiNNE demonstrated significant speedups. On large real-world datasets (ALOI and KDDCup99), SiNNE completed queries in seconds, while RKDE and ZKDE failed to finish within 10 days. SiNNE was also an order of magnitude faster than ZsGrid on these datasets.
- Scalability: Scale-up tests showed SiNNE's ability to handle datasets with millions of instances and thousands of dimensions, completing tasks that were infeasible for other methods within reasonable timeframes. For instance, SiNNE processed a 10 million instance dataset in 44 seconds, while other methods were projected to take days or weeks.
Limitations and Future Work
- Definition of Dimensionality Unbiasedness: The authors note that the current formal definition of dimensionality unbiasedness might not be sufficient for OAM. They suggest that while density rank and Z-score normalization satisfy the definition, they can still exhibit biases. This points to a need for a more nuanced definition tailored to OAM.
- Theoretical Properties: The paper proposes investigating the theoretical properties of SiNNE as a future research direction.
- Improved Dimensionality Unbiasedness Definition: Developing a better definition of dimensionality unbiasedness specifically for OAM is identified as an open question and future work.
Summary updated