On the Surprising Behavior of Distance Metrics in High Dimensional Spaces
By Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim. 2001
2,357 citations recorded by the source corpus.
In recent years, the effect of the curse of high dimensionality has been studied in great detail on several problems such as clustering, nearest neighbor search, and indexing. In high dimensional space the data becomes sparse, and traditional indexing and algorithmic techniques fail from a efficiency and/or effectiveness perspective. Recent research results show that in high dimensional space, the concept of proximity, distance or nearest neighbor may not even be qualitatively meaningful. In this paper, we view the dimensionality curse from the point of view of the distance metrics which are used to measure the similarity between objects. We specifically examine the behavior of the commonly used L k norm and show that the problem of meaningfulness in high dimensionality is sensitive to the value of k. For example, this means that the Manhattan distance metric (L 1 norm) is consistently more preferable than the Euclidean distance metric (L 2 norm) for high dimensional data mining applications. Using the intuition derived from our analysis, we introduce and examine a natural extension of the L k norm to fractional distance metrics. We show that the fractional distance metric provides more meaningful results both from the theoretical and empirical perspective. The results show that fractional distance metrics can significantly improve the effectiveness of standard clustering algorithms such as the k-means algorithm.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory, Algorithms & Complexity, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Percy Liang
- Ruslan Salakhutdinov
- Charu C. Aggarwal
- Eric P. Xing
- Yoshua Bengio
- Mohit Bansal
- Noah A. Smith
- Jianfeng Gao
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Yi Yang
- Dacheng Tao
- Cordelia Schmid
- Trevor Darrell
- Xiaogang Wang
- Andrew Zisserman
- Jitendra Malik
In Statistical Learning Theory
- Andrew Gordon Wilson
- Ruslan Salakhutdinov
- Eric P. Xing
- Zhiting Hu
- Christian Beecks
- Han Lin Shang
- Anil Jayanti Aswani
- T. Chari
In Algorithms & Complexity
- Christian Beecks
- Han Lin Shang
- Anil Jayanti Aswani
- T. Chari
- Lior S. Pachter
- Matt Olfat
- Michel Verleysen
- Damien François
In Signal Processing
- Charu C. Aggarwal
- Renato Cordeiro de Amorim
- Arthur Zimek
- Pavel Berkhin
- Boris G. Mirkin
- Hans-Peter Kriegel
- Lalit P. Jain
- Elena A. Allen
Citations in the corpus
- Detecting Backdoor Attacks on Deep Neural Networks by Activation Clustering (2018, methodology): “s will be especially true when we have hundreds of thousands of activations. Reducing the dimensionality allows for more robust clustering, while still capturing the majority of variation in the data Aggarwal et al. (2001). After dimensionality reduction, we found k-means with k = 2 to be highly eff”
- Deep Weighted Averaging Classifiers (2018, methodology): “holds or 0 if not. The primary limitation on NW is due to the curse of dimensionality: as the dimensionality of x grows, sparse data becomes a problem, and the notion of proximity becomes problematic [1]. In this work, we show how we can avoid this problem by using neural networks to embed inputs in”
- A self-organizing neural network architecture for learning human-object interactions (2017, methodology): “nating them through the temporal window technique. Methods based on the Euclidean distance metric, as in our case, are shown to have a performance degradation when data lies in high-dimensional space [51]. Therefore, we apply the principal component analysis (PCA) dimensionality reduction technique ”
- Deep Kernel Learning (2015, background): “ intuitive in some cases, one cannot expect Euclidean and absolute distance as measures of similarity to be generally applicable, and they are especially problematic in high dimensional input spaces (Aggarwal et al., 2001). Modern approaches attempt to learn a exible parametric family, for example, ”
- Stochastic Variational Deep Kernel Learning (2016, methodology): “lar, where we typically have high dimensional input vectors, with little intuition about how these vectors should correlate, and therefore most want to learn a flexible non-Euclidean similarity metric [1]. *Equal contribution. 29th Conference on Neural Information Processing Systems (NIPS 2016), Barc”
- The Concentration of Fractional Distances (2007, methodology): “in [24]: the segmentation data set and the Wisconsin Diagnostic Breast Cancer (WDBC) data set from the University of California, Irvine (UCI) Machine Learning Repository [44].”
- On k-Anonymity and the Curse of Dimensionality (2005, background): “It has been argued in [2, 8], that under certain reasonable assumptions on the data distribution, the distances of the nearest and farthest neighbors to a given target in high dimensional space is almost the same for a variety of data distributions and distance functions.”
- Angle-based outlier detection in high-dimensional data (2008, background): “One of the most thoroughly discussed effects of this malediction of mining high-dimensional data is that concepts like proximity, distance, or nearest neighbor become less meaningful with increasing dimensionality of data sets [7, 13, 1].”
- Deep rule-based classifier with human-level performance and characteristics (2018, background): “The vector normalization operation helps to overcome the so-called “curse of dimensionality” [1].”
- A Survey of Clustering Data Mining Techniques (2006, background): “If the expected number of edges per cluster is |C| , β ∈ [1, 2], then the aggregate inter-cluster similarity has to be normalized by the factor (|Ci|+ |Cj |) − |Ci| − |Cj | representing the number of intercluster edges.”
- The Extreme Value Machine (2015, result): “This is consistent with the previous finding that euclidean distance does not work well when comparing deep features of individual samples [48].”
- Tracking whole-brain connectivity dynamics in the resting state. (2014, positive): “We used the L1 distance function (Manhattan distance), guided by work suggesting the L1-norm may be a more effective similarity measure than the L2 (Euclidean) distance for high-dimensional data (Aggarwal et al. 2001).”
- Outlier Analysis (2013, methodology): “tant from one another, and therefore the contrast in the distances is lost [22, 215].”