کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
468188 698196 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Is the kk-NN classifier in high dimensions affected by the curse of dimensionality?
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Is the kk-NN classifier in high dimensions affected by the curse of dimensionality?
چکیده انگلیسی

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 kk nearest neighbours based learning algorithms such as the kk-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 kk 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 Borel isomorphism.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Mathematics with Applications - Volume 65, Issue 10, May 2013, Pages 1427–1437
نویسندگان
,