The concentration of fractional distances
The concentration of fractional distances
复制标题
DOI：
10.1109/tkde.2007.1037
复制
发表时间：
2007-07-01
影响因子：
8.9
通讯作者：
Verleysen, Michel
中科院分区：
文献类型：
--
作者：
Francois, Damien;Wertz, Vincent;Verleysen, Michel
最近邻搜索和许多其他数值数据分析工具最常依赖于欧氏距离的使用。然而，当数据是高维时，欧几里得距离似乎是集中的；数据元素对之间的所有距离似乎都非常相似。因此，欧几里得距离的相关性在过去一直受到质疑，并引入分数范数（指数小于1的类闵可夫斯基范数）来对抗集中现象。本文通过证明浓度确实是距离的固有属性而不是有限样本的人工产物来证明使用替代距离来对抗浓度是合理的。此外，还给出了浓度作为距离指数和数据分布的函数的估计。它得出的结论是，与一般承认的相反，分数范数并不总是比欧几里得范数更不集中；给出了一个反例来证明这一说法。理论论证表明，对于不符合定理假设的实际数据，特别是独立和同分布变量的假设，可能会出现集中现象。最后，给出了如何选择最优度量的一些见解。
Nearest neighbor search and many other numerical data analysis tools most often rely on the use of the euclidean distance. When data are high dimensional, however, the euclidean distances seem to concentrate; all distances between pairs of data elements seem to be very similar. Therefore, the relevance of the euclidean distance has been questioned in the past, and fractional norms (Minkowski-like norms with an exponent less than one) were introduced to fight the concentration phenomenon. This paper justifies the use of alternative distances to fight concentration by showing that the concentration is indeed an intrinsic property of the distances and not an artifact from a finite sample. Furthermore, an estimation of the concentration as a function of the exponent of the distance and of the distribution of the data is given. It leads to the conclusion that, contrary to what is generally admitted, fractional norms are not always less concentrated than the euclidean norm; a counterexample is given to prove this claim. Theoretical arguments are presented, which show that the concentration phenomenon can appear for real data that do not match the hypotheses of the theorems, in particular, the assumption of independent and identically distributed variables. Finally, some insights about how to choose an optimal metric are given.