Subspace outlier mining in large multimedia databases

Ira Assent, Ralph Krieger, Emmanuel Müller, Thomas Seidl

TL;DR

This paper introduces a novel density-based approach to "subspace outlier mining" for massive, high-dimensional multimedia databases. It tackles the challenge of finding outliers in complex datasets where traditional methods fail due to the "curse of dimensionality," proposing a method that identifies objects deviating from patterns found in specific subsets of dimensions.

What Problem Does This Paper Address?

Modern applications, from life sciences to e-commerce, are generating enormous amounts of multimedia data. Manually sifting through this data to find interesting patterns or anomalies is impossible. Knowledge Discovery in Databases (KDD) aims to automate this. Clustering, a core KDD task, groups similar data points. While density-based clustering excels at finding arbitrarily shaped clusters in low-dimensional data, it falters in high-dimensional spaces. This is because, as dimensionality increases, the concept of distance becomes less meaningful, and clusters become obscured – the "curse of dimensionality."

Subspace clustering attempts to solve this by looking for clusters within subsets of dimensions. However, finding all possible subspaces is computationally prohibitive. Furthermore, in applications like fraud detection, identifying "outliers" – objects that don't fit into any established cluster – is crucial. In high-dimensional spaces, an object might appear normal in one subspace but anomalous in another, creating conflicting information. This paper addresses the need for a robust method to detect outliers in high-dimensional data by leveraging subspace clustering, specifically by defining outliers as objects that don't fit into any relevant and non-overfitting subspace clusters.

Methods

The paper proposes a density-based subspace clustering model for outlier detection. This builds upon existing density-based clustering concepts where objects are considered "dense" if they have enough neighbors within a certain radius (defined by parameters $\epsilon$ and minpts). Density-connectivity then links dense objects transitively.

The core innovation lies in extending this to subspace clustering. Here, density and density-connectivity are defined within specific subspaces (subsets of dimensions). A subspace cluster is then defined as a set of density-connected objects within a subspace that is maximal (cannot be extended) and non-redundant (not contained within a higher-dimensional cluster).

For outlier detection, the paper defines a subspace outlier as an object that is not density-connected to any relevant (meeting a minimum size threshold) and non-overfitting (within specified dimension range) subspace cluster. The paper also introduces the concept of parallel universes for heterogeneous data, where different subsets of attributes (e.g., customer demographics vs. transaction data) are treated as separate "universes" for outlier detection, allowing for more nuanced anomaly identification.

Datasets

The paper evaluates its approach on "real world data sets." Specific dataset names mentioned are:

  • Pendigits
  • Shapes
  • Glass

The paper does not introduce new benchmark datasets.

Key Insights and Ideas

  • The "Curse of Dimensionality" is a fundamental barrier: Simply applying standard clustering to high-dimensional data is futile because distances become less meaningful. Subspace clustering is a necessary step to recover meaningful patterns.
  • Outliers are context-dependent: An object might be an outlier in one subspace but not in another. A robust outlier detection method must account for this.
  • Density-based approaches are well-suited for subspace clustering: The concept of local density can be effectively applied to subsets of dimensions to identify clusters that might be missed by other methods.
  • "Parallel Universes" for Heterogeneous Data: Recognizing that different types of attributes can represent distinct "models" of the same entity is crucial for complex data. Treating these as separate universes allows for more targeted and meaningful outlier detection.
  • The importance of "relevant" and "non-overfitting" clusters: Simply finding any subspace cluster isn't enough for outlier detection. The clusters must be significant in terms of the number of objects they contain and the number of dimensions they span to be meaningful for identifying true anomalies.

Key Results

The paper presents experimental results demonstrating the quality of their subspace clustering approach. Figure 3 shows a comparison of their method against "SCHISM" and "SUBCLU" on the Pendigits, Shapes, and Glass datasets. The authors claim their approach achieves superior quality compared to these competing methods.

While specific quantitative metrics for outlier detection are not detailed in the provided text, the experiments indicate that their subspace clustering algorithm is capable of detecting "pure subspace clusters." The coverage ratios (percentage of data assigned to clusters) were around 80-90%, suggesting that a significant portion of the data (10-20%) is not assigned to clusters, implying the presence of outliers.

Limitations and Future Work

  • Computational Complexity: While subspace clustering aims to reduce complexity, the exponential number of subspaces remains a challenge. The paper mentions using pruning thresholds, but this can lead to "dimensionality bias" where clusters in certain subspaces are missed.
  • Outlier Ranking: The paper acknowledges that the 10-20% of data not assigned to clusters suggests outliers exist. They plan to investigate ranking of outliers to help users prioritize the most urgent cases.
  • Expert Knowledge Integration: For specific applications like money laundering detection, the authors plan to incorporate expert knowledge to better identify typical cases and anomalies.
  • Further Validation: The preliminary experiments are promising, but further validation on more datasets, including financial data, is planned.
  • Heterogeneous Data: While the "parallel universes" concept is introduced, its full experimental validation and integration into the outlier detection process are areas for future work.

Summary updated

Abstract

Increasingly large multimedia databases in life sciences, e-commerce, or monitoring applications cannot be browsed manually, but require automatic knowledge discovery in databases (KDD) techniques to detect novel and interesting patterns. One of the major tasks in KDD, clustering, aims at grouping similar objects into clusters, separating dissimilar objects. Density-based clustering has been shown to detect arbitrarily shaped clusters even in noisy data bases. In high-dimensional data bases, meaningful clusters can no longer be detected due to the "curse of dimensionality". Consequently, subspace clustering searches for clusters hidden in any subset of the set of dimensions. As the number of subspaces is exponential in the number of dimensions, traditional approaches use fixed pruning thresholds. This results in dimensionality bias, i.e. with growing dimensionality, more clusters are missed. Clustering information is very useful for applications like fraud detection where outliers, i.e. objects which differ from all clusters, are searched. In subspace clustering, an object may be an outlier with respect to some groups, but not with respect to others, leading to possibly conflicting information. We propose a density-based unbiased subspace clustering model for outlier detection. We define outliers with respect to all maximal and non-redundant subspace clusters, taking their distance (deviation in attribute values), relevance (number of attributes covered) and support (number of objects covered) into account. We demonstrate the quality of our subspace clustering results in experiments on real world and synthetic databases and discuss our outlier model.
BibTeX
@inproceedings{assent2007subspace,
  author = {Ira Assent and Ralph Krieger and Emmanuel Müller and Thomas Seidl},
  title = {{Subspace outlier mining in large multimedia databases}},
  booktitle = {Parallel Universes and Local Patterns},
  year = {2007},
  url = {https://openreview.net/forum?id=MaCCiH1MI1},
}
Figure