A New Effective and Efficient Measure for Outlying Aspect Mining

Durgesh Samariya, Sunil Aryal, Kai Ming Ting, Jiangang Ma

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

Abstract

Outlying Aspect Mining (OAM) aims to find the subspaces (a.k.a. aspects) in which a given query is an outlier with respect to a given data set. Existing OAM algorithms use traditional distance/density-based outlier scores to rank subspaces. Because these distance/density-based scores depend on the dimensionality of subspaces, they cannot be compared directly between subspaces of different dimensionality. Z-score normalisation has been used to make them comparable. It requires to compute outlier scores of all instances in each subspace. This adds significant computational overhead on top of already expensive density estimation—making OAM algorithms infeasible to run in large and/or high-dimensional datasets. We also discover that Z-score normalisation is inappropriate for OAM in some cases. In this paper, we introduce a new score called Simple Isolation score using Nearest Neighbor Ensemble (SiNNE), which is independent of the dimensionality of subspaces. This enables the scores in subspaces with different dimensionalities to be compared directly without any additional normalisation. Our experimental results revealed that SiNNE produces better or at least the same results as existing scores; and it significantly improves the runtime of an existing OAM algorithm based on beam search.
BibTeX
@inproceedings{samariya2020new,
  author = {Durgesh Samariya and Sunil Aryal and Kai Ming Ting and Jiangang Ma},
  title = {{A New Effective and Efficient Measure for Outlying Aspect Mining}},
  booktitle = {WISE},
  year = {2020},
  doi = {10.1007/978-3-030-62008-0\_32},
}

Loading related content...

Figure