Local subspace-based outlier detection using global neighbourhoods

Bas van Stein, Matthijs van Leeuwen, Thomas Bäck

Abstract

In high-dimensional data, outliers often manifest only within specific feature subsets (subspaces). Detecting these anomalies is particularly challenging in datasets composed of mixtures of different distributions, where traditional local methods may compare an outlier against neighbors from a different mixture component. We introduce GLOSS (Global-Local Outliers in SubSpaces), a novel algorithm that leverages global high-dimensional neighborhoods to ensure "apples-to-apples" comparisons when calculating outlier scores in low-dimensional subspaces.

Introduction

Traditional outlier detection methods struggle with the "curse of dimensionality." In many real-world scenarios, a point is not globally anomalous but becomes an outlier when viewed through a specific subset of features. However, existing subspace methods often fail when the data is a mixture of different distributions (e.g., different grades of steel in manufacturing). In these cases, a point's nearest neighbors in a specific subspace might belong to a different distribution entirely, masking the point's true anomalous nature.

The authors identify a critical gap: local outlier detection should be relative to the point's generative process (its "true" peers), not just its spatial proximity in a random subspace.

The GLOSS Methodology

GLOSS addresses this by decoupling neighborhood identification from outlier scoring. The algorithm follows a three-step process:

  1. Global Neighborhood Selection: GLOSS identifies the $k$-nearest neighbors in the full high-dimensional feature space. Despite the noise inherent in high dimensions, global distances are typically sufficient to group points belonging to the same mixture component.
  2. Subspace Search: Using an adapted version of the High Contrast Subspaces (HiCS) algorithm, GLOSS identifies subspaces where features exhibit high conditional dependence, indicating they are likely to reveal interesting patterns.
  3. Local Outlier Scoring: For each candidate subspace, GLOSS projects the point and its pre-defined global neighbors into that space. It then calculates an outlier score (based on Local Outlier Probabilities, or LoOP) relative only to those global peers.
Visualization of GLOSS: A point (red star) and its global neighbors (yellow diamonds) across the global space and three distinct subspaces. While the point appears normal in the global space and Subspace 2, it is clearly an outlier in Subspace 1 relative to its true peers.

By fixing the neighborhood globally, GLOSS ensures that an outlier is always compared against its "family," preventing it from "hiding" among members of other clusters in the data mixture.

Experimental Validation

The researchers evaluated GLOSS against state-of-the-art methods like HiCS and LoOP across synthetic and real-world datasets:

  • Synthetic Data: GLOSS maintained a high AUC (~0.90) in dimensions up to 400D, whereas competitors' performance degraded as outliers became increasingly hidden within mixture components.
  • UCI Benchmarks: Across 12 datasets, GLOSS consistently outperformed existing methods in identifying "implanted" outliers that were swapped between different classes.
  • BMW Manufacturing Case Study: In a 1,200-dimensional dataset of steel coil measurements, GLOSS identified four critical manufacturing defects that were confirmed by domain experts. These outliers were missed by standard local methods because they were physically close to coils of different steel grades in the relevant subspaces.

Conclusion

GLOSS demonstrates that high-dimensional global space, often viewed as a source of noise, is actually a powerful filter for identifying a point's true neighborhood. By combining global context with local subspace analysis, GLOSS provides a robust framework for detecting hidden anomalies in complex, mixed-distribution datasets. Future work will focus on automating the selection of the neighborhood size $k$ and further optimizing the computational efficiency of the subspace search.

Summary updated

BibTeX
@inproceedings{stein2016local,
  author = {Bas van Stein and Matthijs van Leeuwen and Thomas Bäck},
  title = {{Local subspace-based outlier detection using global neighbourhoods}},
  booktitle = {IEEE BigData},
  year = {2016},
  doi = {10.1109/bigdata.2016.7840717},
}
Figure