В Элементах Статистического Изучения введена проблема, чтобы выделить проблемы с k-nn в многомерных пространствах. Есть точек данных, которые равномерно распределены в мерном единичном шаре.
Среднее расстояние от начала координат до ближайшей точки данных определяется выражением:
Когда , формула разбивается на половину радиуса шара, и я могу видеть, как самая близкая точка приближается к границе как , таким образом, интуиция позади knn разрушается в больших измерениях. Но я не могу понять, почему формула зависит от N. Может кто-нибудь уточнить?
Кроме того, в книге также рассматривается эта проблема: «... прогнозирование намного сложнее вблизи границ обучающей выборки. Необходимо экстраполировать из соседних точек выборки, а не интерполировать между ними». Это кажется глубоким утверждением, но я не могу понять, что это значит. Может ли кто-нибудь перефразировать?
источник
Ответы:
Объем мерного гипербола радиуса r имеет объем, пропорциональный r p .п р рп
Таким образом, доля объема, превышающего расстояние от начала координат, составляет r p - ( k r ) pк р .рп- ( к р )прп= 1 - кп
Вероятность того, что все случайным образом выбранные точки больше , чем расстояние K г от начала координат ( 1 - к р ) Н . Чтобы получить среднее расстояние до ближайшей случайной точки, установите эту вероятность равной 1N к р ( 1 - кп)N . Итак(1-кр)N=112
Наглядно это делает какой - то смысл: чем больше случайных точек есть, чем ближе вы ожидаете , что ближайший к происхождению быть, поэтому следует ожидать быть убывающей функцией от N . Здесь 2 1 / N - убывающая функция от N , поэтому 1К N 21 / N N является возрастающей функциейN, и, следовательно,1-1121 / N N - убывающая функцияN,как и егоp-го корня.1 - 121 / N N п
источник
А теперь без рук машет
Для любой последовательности iid rv's где F - общий CDF
Таким образом , если мы IID равномерно распределены X I в единичном шаре в р измерениях, то Р ( мин 1 ≤ я ≤ N | | Х я | | > г ) = ( 1 - Р ( г ) ) Н , где Р является общий CDF расстояний, | | X я | | , я = 1 , 2 ,N Икся п
Таким образом, решение
является
источник
Как кратко, но на словах:
источник