Intrinsic dimension and its application to association rules

Tom Hanika, Friedrich Martin Schneider, Gerd StummearXiv 2018 · arXiv

TL;DR

This paper introduces a computationally feasible method to measure the "intrinsic dimension" of a dataset, specifically targeting the curse of dimensionality in association rule mining. By bridging geometric analysis and machine learning, the authors provide a way to quantify how data distribution—rather than just combinatorial complexity—impacts performance in high-dimensional spaces.

What Problem Does This Paper Address?

In machine learning, the "curse of dimensionality" is a well-known hurdle. Usually, researchers talk about it in terms of combinatorial explosion: as you add more features, the number of possible combinations grows exponentially, making computation impossible.

However, there is a second, subtler curse: the distributional curse. In high-dimensional spaces, data points often exhibit a mathematical phenomenon called "concentration of measure" (or the Lévy property). Essentially, in very high dimensions, data points tend to behave in counterintuitive ways—for example, distances between points can become nearly identical, making traditional similarity measures useless.

While mathematicians like V. Pestov have developed axiomatic ways to define "intrinsic dimension" to describe this, these methods have historically been computationally infeasible for real-world datasets. This paper seeks to bridge that gap by providing a practical, measurable setup for the dimension curse.

Methods

The authors build their approach on the foundations of geometric analysis. They define a Data Structure as a triple $D = (X, \mu, F)$, where:

  • $X$ is the data space (a Polish space).
  • $\mu$ is a probability measure representing the data distribution.
  • $F$ is a set of "features" (equicontinuous real-valued functions).

To measure the dimension, they adapt the concept of observable diameter from Gromov. This measures how "spread out" the data appears when viewed through the lens of its features. They then define a specific intrinsic dimension function, $\partial_\Delta(D)$, which is designed to diverge (go to infinity) if a sequence of data structures exhibits the Lévy property.

To apply this to association rule mining, they treat transactions as data points and association rules as feature functions. The value of a feature for a given transaction is the relative amount of items covered by the head of a specific rule.

Datasets

The authors evaluated their method using three well-known benchmarks for association rule mining:

  • Accident: Data regarding high-frequency accident locations.
  • Mushroom: A dataset describing biological characteristics of mushrooms.
  • Chess: A dataset of chess game states.

Key Insights and Ideas

  • Separating the Curses: The paper emphasizes that we shouldn't just worry about how many items we have, but how they are distributed. A dataset might have few items but a high intrinsic dimension, making it difficult to analyze.
  • Geometric Feasibility: The core "aha moment" is translating abstract concepts from geometric analysis (like Borel probability measures and Polish spaces) into a framework that can actually be calculated for a discrete set of transactions and rules.
  • Support vs. Dimension: A surprising finding is the relationship between rule support and dimension. As the support threshold for rules increases, the intrinsic dimension of the data structure also increases. This reveals how different feature sets "cover" the underlying data.

Key Results

The researchers calculated the intrinsic dimension across different levels of rule support (70, 80, 90) and confidence (70%, 80%, 90%).

As shown in the figures below, the intrinsic dimension increases significantly as support increases. The "Accidents" dataset consistently showed the highest intrinsic dimension (reaching over $10^6$), while the "Chess" dataset had the lowest (around $10^2$ to $10^4$).

The intrinsic dimension for multiple data sets, supports and confidence.

The slope of these increases differs between datasets, which the authors suggest reveals the varying ability of specific feature sets to effectively represent the data.

Limitations and Future Work

The authors acknowledge that due to space constraints, they could not address all the technical mathematical challenges and connections to geometric analysis in this specific paper.

For future work, they suggest that this measure of intrinsic dimension could be a powerful tool for evaluating dimension reduction procedures like Principal Component Analysis (PCA). By measuring the intrinsic dimension before and after reduction, researchers could better understand if a procedure is actually simplifying the data distribution or just reducing the number of columns.

Summary updated

Abstract

The curse of dimensionality in the realm of association rules is twofold. Firstly, we have the well known exponential increase in computational complexity with increasing item set size. Secondly, there is a \emph{related curse} concerned with the distribution of (spare) data itself in high dimension. The former problem is often coped with by projection, i.e., feature selection, whereas the best known strategy for the latter is avoidance. This work summarizes the first attempt to provide a computationally feasible method for measuring the extent of dimension curse present in a data set with respect to a particular class machine of learning procedures. This recent development enables the application of various other methods from geometric analysis to be investigated and applied in machine learning procedures in the presence of high dimension.
BibTeX
@misc{hanika2018intrinsic,
  author = {Tom Hanika and Friedrich Martin Schneider and Gerd Stumme},
  title = {{Intrinsic dimension and its application to association rules}},
  year = {2018},
  eprint = {1805.05714},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.05714},
}

Loading related content...

Figure