Subspace Determination through Local Intrinsic Dimensional Decomposition: Theory and Experimentation

Ruben Becker, Imane Hafnaoui, Michael E. Houle, Pan Li, Arthur Zimek

Abstract

Axis-aligned subspace clustering generally entails searching through enormous numbers of subspaces (feature combinations) and evaluation of cluster quality within each subspace. In this paper, we tackle the problem of identifying subsets of features with the most significant contribution to the formation of the local neighborhood surrounding a given data point. For each point, the recently-proposed Local Intrinsic Dimension (LID) model is used in identifying the axis directions along which features have the greatest local discriminability, or equivalently, the fewest number of components of LID that capture the local complexity of the data. In this paper, we develop an estimator of LID along axis projections, and provide preliminary evidence that this LID decomposition can indicate axis-aligned data subspaces that support the formation of clusters.

Introduction

In high-dimensional data mining, the "curse of dimensionality" often renders traditional distance metrics meaningless as distances between points converge. While global feature selection attempts to find a single relevant subset of features, subspace clustering recognizes that different clusters may be defined by entirely different feature subsets. The primary challenge lies in identifying these "locally relevant" features without prior knowledge of the cluster structure.

This research introduces a mathematical framework to decompose Local Intrinsic Dimensionality (LID)—a measure of how the density of data points grows as a neighborhood expands—into its individual feature components. By quantifying the contribution of each dimension to local complexity, we provide a novel tool for identifying discriminative subspaces, outperforming traditional methods like DiSH and CLIQUE.

Methodology

LID Decomposition and Additivity

The core theoretical insight of this work is that local complexity is additive. The authors prove that the total LID of a point can be decomposed into a sum of LID components, one for each axis (feature). In an ideal scenario, if a point lies on a 2D plane within a 100D space, the LID components for the two relevant dimensions will approach 1.0, while the 98 noisy dimensions will contribute near 0.

Correcting Projection Bias

A significant technical hurdle in estimating LID along a single axis is geometric bias. When using a hyperspherical (Euclidean) neighborhood, points far along an axis are rarer in a sphere than they would be in a cube. Simply "dropping" dimensions from a Euclidean neighborhood fails because a sphere projected onto an axis does not result in a uniform interval.

Geometric representation of the projection bias when estimating LID along a single axis within a hyperspherical neighborhood.

To address this, the authors developed a Maximum Likelihood Estimator (MLE) featuring a novel weighting scheme. This scheme compensates for the projection bias, ensuring that the estimated components accurately reflect the local data distribution along each axis.

Experimental Evaluation

The proposed method was evaluated using synthetic benchmarks designed to simulate high-dimensional challenges, including uniform noise distributions, the DiSH 3D dataset, and complex synthetic manifolds (D1-D4) with up to 78 dimensions.

Comparison of LID estimators across different dimensions (m), demonstrating that the weighted sum approach (sum_w_hill_projections) accurately tracks the total intrinsic dimension.

As shown in the experimental results, the weighted estimator (sum_w_hill_projections) successfully approximates the total LID across varying dimensions ($m$), whereas unweighted sums tend to diverge. This empirical validation supports the theoretical claim that LID can be reliably decomposed and reconstructed.

Key Results and Insights

  • Subspace Accuracy: On manifold datasets, the LID-based approach significantly outperformed the DiSH algorithm in terms of Relative Non-Intersecting Area (RNIA) and Average Relative Relevance (ARR), demonstrating superior precision in feature selection.
  • Clustering Performance: The authors implemented LID-DBSCAN, a two-stage approach that first assigns points to subspaces via LID decomposition and then clusters within those subspaces. In a 100-attribute toy dataset, LID-DBSCAN achieved an Adjusted Rand Index (ARI) of 0.699, substantially higher than DiSH (0.412) and CLIQUE (0.568).
  • Discriminative Power: Counter-intuitively, a low LID component in a specific direction indicates that the feature is highly discriminative for that local neighborhood. By identifying "gaps" in ranked LID values, the intrinsic subspace for each point can be determined.

Conclusion and Future Work

While the theory of LID additivity is robust, practical estimators only approximate perfect additivity. Future research will focus on optimizing the computational overhead of calculating LID for every point across all dimensions and validating the method on messy, real-world datasets where manifolds are less clearly defined. Beyond clustering, this LID decomposition "primitive" holds promise for enhancing outlier detection and similarity search in high-dimensional spaces.

Summary updated

Abstract

Axis-aligned subspace clustering generally entails searching through enormous numbers of subspaces (feature combinations) and evaluation of cluster quality within each subspace. In this paper, we tackle the problem of identifying subsets of features with the most significant contribution to the formation of the local neighborhood surrounding a given data point. For each point, the recently-proposed Local Intrinsic Dimension (LID) model is used in identifying the axis directions along which features have the greatest local discriminability, or equivalently, the fewest number of components of LID that capture the local complexity of the data. In this paper, we develop an estimator of LID along axis projections, and provide preliminary evidence that this LID decomposition can indicate axis-aligned data subspaces that support the formation of clusters.
BibTeX
@inproceedings{becker2019subspace,
  author = {Ruben Becker and Imane Hafnaoui and Michael E. Houle and Pan Li and Arthur Zimek},
  title = {{Subspace Determination through Local Intrinsic Dimensional Decomposition: Theory and Experimentation}},
  booktitle = {SISAP},
  year = {2019},
  url = {https://openreview.net/forum?id=0OSbspp6BGg},
}
Figure