Dimensionality, Discriminability, Density and Distance Distributions
- 1 December 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23759232,p. 468-473
Abstract
For many large-scale applications in data mining, machine learning, and multimedia, fundamental operations such as similarity search, retrieval, classification, clustering, and anomaly detection generally suffer from an effect known as the `curse of dimensionality'. As the dimensionality of the data increases, distance values tend to become less discriminative, due to their increasing relative concentration about the mean of their distribution. For this reason, researchers have considered the analysis of structures and methods in terms of measures of the intrinsic dimensionality of the data sets. This paper is concerned with a generalization of a discrete measure of intrinsic dimensionality, the expansion dimension, to the case of continuous distance distributions. This notion of the intrinsic dimensionality of a distribution is shown to precisely coincide with a natural notion of the indiscriminability of distances and features. Furthermore, for any distance distribution with differentiable cumulative density function, a fundamental relationship is shown to exist between probability density, the cumulative density (cumulative probability divided by distance), intrinsic dimensionality, and discriminability.Keywords
This publication has 19 references indexed in Scilit:
- Rank Cover Trees for Nearest Neighbor Search2013
- Generalized Expansion Dimension2012
- A survey on unsupervised outlier detection in high‐dimensional numerical dataStatistical Analysis and Data Mining: An ASA Data Science Journal, 2012
- Finding Local Anomalies in Very High Dimensional Space2010
- Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?2010
- Information-theoretic metric learning2007
- Cover trees for nearest neighbor2006
- Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancyIEEE Transactions on Pattern Analysis and Machine Intelligence, 2005
- Bounded geometries, fractals, and low-distortion embeddings2004
- LOFACM SIGMOD Record, 2000