Review: Estimating the intrinsic dimension of datasets by a minimal neighborhood information¶
Citation
- Facco, E., d'Errico, M., Rodriguez, A., & Laio, A. (2017). Estimating the intrinsic dimension of datasets by a minimal neighborhood information. Scientific Reports, 7, 12140.
- DOI
Abstract¶
Analyzing large volumes of high-dimensional data is an issue of fundamental importance in data science, molecular simulations and beyond. Several approaches work on the assumption that the important content of a dataset belongs to a manifold whose Intrinsic Dimension (ID) is much lower than the crude large number of coordinates. Such manifold is generally twisted and curved; in addition points on it will be non-uniformly distributed: two factors that make the identification of the ID and its exploitation really hard. Here we propose a new ID estimator using only the distance of the first and the second nearest neighbor of each point in the sample. This extreme minimality enables us to reduce the effects of curvature, of density variation, and the resulting computational cost. The ID estimator is theoretically exact in uniformly distributed datasets, and provides consistent measures in general. When used in combination with block analysis, it allows discriminating the relevant dimensions as a function of the block size. This allows estimating the ID even when the data lie on a manifold perturbed by a high-dimensional noise, a situation often encountered in real world data sets. We demonstrate the usefulness of the approach on molecular simulations and image analysis.
Facco et al. (2017) introduce the TWO-NN estimator, which Hifuku uses to report the intrinsic dimension of a cloud of elite trees. The estimator is attractive here for a specific reason: it requires no embedding and no choice of neighborhood size, so it can characterize a tree cloud without first committing to a projection of it.
The estimator¶
For a point \( i \), let \( r_1 \) and \( r_2 \) be the distances to its first and second nearest neighbors, and define the ratio
Under the assumption that the density is approximately constant on the lengthscale of the second neighbor, the paper derives the probability density and cumulative distribution of this ratio (equations 5 and 6):
The result that makes the estimator useful is that both depend on the intrinsic dimension \( d \) but not on the density \( \rho \), which cancels. Rearranging the cumulative distribution gives equation 7:
so \( d \) is the slope of \( -\log(1 - F) \) against \( \log \mu \), fitted through the origin.
The algorithm given in the paper has five steps: compute pairwise distances, take the two shortest for each point, form \( \mu_i \), build the empirical cumulate by sorting \( \mu \) in ascending order and setting \( F^{\mathrm{emp}}(\mu_{\sigma(i)}) = i / N \), then fit a straight line through the origin.
Robustness and the discard threshold¶
The paper reports that heavy-tailed distributions destabilize the fit. A small number of points with very large \( \mu \) dominate the slope, because a large ratio \( r_2 / r_1 \) is significant in such distributions. The authors therefore discard the 10 percent of points with the highest \( \mu \) before fitting.
The effect is asymmetric and instructive. Fitting all points gives slopes of 14.09, 2.01 and 6.05 for a uniform hypercube of dimension 14, a Swiss roll, and a Cauchy dataset of dimension 20. Discarding the top decile gives 13.91, 2.01 and 22.16. The first two estimates are essentially unchanged, while the Cauchy estimate moves from badly wrong to approximately correct. Discarding therefore costs nothing on well-behaved data and rescues the difficult case.
Hifuku's implementation follows this procedure, including the 10 percent discard, and fits by least squares through the origin.
Relevance to Hifuku¶
The estimator requires local uniformity only at the scale of the second neighbor, which the authors identify as an advantage over methods requiring uniformity at larger distances. This matters for a cloud of elite trees, which is not uniformly distributed: it consists of per-gene groups of differing size and spread.
The reported benchmark also supplies a validation target. A Swiss roll, a two-dimensional sheet embedded in three dimensions, returns 2.01. Hifuku uses the same construction as a test fixture, so a correct implementation is expected to return approximately 2 for a Swiss roll and approximately 5 for a five-dimensional Gaussian sample.
The estimate is reported alongside, not in place of, the classical multidimensional scaling spectrum. The two answer different questions. TWO-NN measures the local dimension of the manifold, while the spectrum measures how many linear axes the distances occupy. A cloud made of tight per-gene filaments spread across many global directions returns a low value from the first and a high value from the second, and the disagreement is itself informative.
In-document navigation¶
| Section | Content |
|---|---|
| Results, equations 1 to 6 | Distribution of the neighbor-distance ratio, and cancellation of the density |
| A Two Nearest Neighbors estimator | Equation 7 and the five-step algorithm |
| Benchmark, Figure 1 | Hypercube, Swiss roll and Cauchy datasets; the 10 percent discard |
| Estimating a scale-dependent intrinsic dimension | Block analysis, and separating signal dimensions from noise |
| Discussion | Comparison with DANCo and other estimators |