A novel subspace outlier detection method by entropy-based clustering algorithm

Zheng Zuo, Ziqiang Li, Pengsen Cheng, Jian Zhao

TL;DR

This paper introduces EPOD, a novel method for outlier detection in high-dimensional data by focusing on "interesting" subspaces identified through entropy-based clustering. EPOD significantly outperforms existing methods by efficiently finding relevant subspaces and accurately identifying outliers, even when they are hidden in complex, multi-dimensional patterns.

What Problem Does This Paper Address?

High-dimensional datasets, common in fields like bioinformatics and finance, pose a significant challenge for traditional outlier detection methods. This is due to the "curse of dimensionality," where data points become increasingly similar as the number of features grows, making it difficult to distinguish outliers based on distance or density in the full feature space. Outliers might only be apparent in specific subsets of features (subspaces), but exhaustively searching all possible subspaces is computationally infeasible (NP-hard). The paper addresses the critical need for an efficient and accurate method to identify these subspace outliers without being overwhelmed by the sheer number of potential subspaces.

Methods

The core of EPOD lies in its novel approach to selecting and analyzing relevant subspaces.

  • Intuitive Outlier Definition: The paper proposes a new definition for outlierness within subspaces, focusing on how far a data point deviates from its nearest neighbors.
  • Entropy-Based Subspace Selection: EPOD leverages entropy as a key metric to identify "interesting" subspaces. Subspaces with low entropy are considered to have good clustering properties (high density and coverage), making them more likely to reveal outliers.
  • Interest Gain Criterion: To further refine subspace selection and ensure attribute correlation, an "interest gain" criterion is introduced. This helps to avoid redundant subspaces and focus on those with meaningful attribute combinations.
  • Top-N Outlier Ranking: Instead of a binary outlier classification, EPOD identifies the "top N" outliers. This is achieved by aggregating outlier scores from the most interesting subspaces, providing a ranked list that is more interpretable and robust.
  • Algorithm (EPOD): The proposed algorithm combines these elements:
  • Search for potential subspaces: An Apriori-like, bottom-up approach is used to find one-dimensional subspaces with entropy below a threshold, then extending them to higher dimensions while checking for interest gain.
  • Rank interesting subspaces: Subspaces are ranked based on their entropy and interest gain characteristics.
  • Rank top N outliers: Outlier scores (using kNN distance) are computed for data points within the selected interesting subspaces, and these scores are aggregated to identify the top N outliers.

Datasets

The paper evaluates EPOD on a combination of real-world and synthetic datasets:

  • Real-world datasets: Eight datasets from the UCI Machine Learning Repository were used, including:
  • Ann-Thyroid
    • Arrhythmia
    • Breast (Prognostic)
    • Breast (Diagnostic)
    • Diabetes
    • Glass
    • Ionosphere
    • Pendigits
  • Synthetic datasets: Used for evaluating scalability and performance under controlled conditions, including datasets from Keller et al. and artificially generated data with varying dimensions and outlier distributions.

Key Insights and Ideas

  • Entropy as a proxy for outlier-rich subspaces: The paper demonstrates that subspaces with low entropy are not only good for clustering but also highly effective for outlier detection, as they tend to isolate unusual data points.
  • The power of "interesting" subspaces: By focusing on a curated set of subspaces identified by entropy and interest gain, EPOD avoids the computational burden of exhaustive search and achieves higher accuracy than full-space methods.
  • Top-N approach for interpretability: Moving beyond binary outlier labels, the top-N approach provides a ranked list of potential outliers, allowing domain experts to further investigate and validate findings.
  • Robustness to dimensionality: EPOD shows remarkable stability and performance even in high-dimensional scenarios where traditional methods falter.

Key Results

  • Superior Accuracy: EPOD consistently outperforms state-of-the-art subspace outlier detection methods (HiCS, OutRank, SOD) and full-space methods (kNN, LOF) across multiple real-world datasets, achieving higher AUC (Area Under the ROC Curve) values. For example, on the Ann-Thyroid dataset, EPOD achieved an AUC of 98.62%, significantly higher than kNN (94.42%) and HiCS (95.22%).
  • Scalability: The algorithm demonstrates good scalability with increasing dimensionality and dataset size, making it suitable for large, high-dimensional datasets.
  • Parameter Stability: The performance of EPOD is shown to be relatively stable across a range of parameter settings for entropy and interest gain thresholds, simplifying its application.

Limitations and Future Work

  • Parameter Sensitivity: While generally stable, the paper notes that the choice of parameters (w and ∈) can influence the number of subspaces found and thus affect performance. Further research could explore more automated parameter tuning.
  • LOF vs. kNN: While EPOD performs well with kNN for outlier scoring, its performance with LOF (Local Outlier Factor) did not always match kNN, suggesting that the choice of outlier scoring method within EPOD can be important. The authors suggest that for efficiency and scalability, kNN is a promising approach.
  • Future Work: The authors suggest exploring more advanced outlier scoring methods within the EPOD framework and investigating its application to other data mining tasks beyond outlier detection. They also highlight the potential for further optimization of the subspace selection process.

Summary updated

Abstract

Subspace outlier detection has emerged as a practical approach for outlier detection. Classical full space outlier detection methods become ineffective in high dimensional data due to the "curse of dimensionality". Subspace outlier detection methods have great potential to overcome the problem. However, the challenge becomes how to determine which subspaces to be used for outlier detection among a huge number of all subspaces. In this paper, firstly, we propose an intuitive definition of outliers in subspaces. We study the desirable properties of subspaces for outlier detection and investigate the metrics for those properties. Then, a novel subspace outlier detection algorithm with a statistical foundation is proposed. Our method selectively leverages a limited set of the most interesting subspaces for outlier detection. Through experimental validation, we demonstrate that identifying outliers within this reduced set of highly interesting subspaces yields significantly higher accuracy compared to analyzing the entire feature space. We show by experiments that the proposed method outperforms competing subspace outlier detection approaches on real world data sets.
BibTeX
@inproceedings{zuo2023novel,
  author = {Zheng Zuo and Ziqiang Li and Pengsen Cheng and Jian Zhao},
  title = {{A novel subspace outlier detection method by entropy-based clustering algorithm}},
  booktitle = {Scientific},
  year = {2023},
  doi = {10.1038/s41598-023-42261-4},
}
Figure