期刊
COMPUTERS & MATHEMATICS WITH APPLICATIONS
卷 65, 期 10, 页码 1427-1437出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.camwa.2012.09.011
关键词
Nearest neighbour search; The curse of dimensionality; Approximate k-NN classifier; Borel dimensionality reduction
There is an increasing body of evidence suggesting that exact nearest neighbour search in high-dimensional spaces is affected by the curse of dimensionality at a fundamental level. Does it necessarily mean that the same is true for k nearest neighbours based learning algorithms such as the k-NN classifier? We analyse this question at a number of levels and show that the answer is different at each of them. As our first main observation, we show the consistency of a k approximate nearest neighbour classifier. However, the performance of the classifier in very high dimensions is provably unstable. As our second main observation, we point out that the existing model for statistical learning is oblivious of dimension of the domain and so every learning problem admits a universally consistent deterministic reduction to the one-dimensional case by means of a Bore! isomorphism. (C) 2012 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据