Непараметрические методы типа K-ближайших соседей в пространстве пространственных объектов

11

Основная идея к-ближайших соседей учитывает ближайших точек и определяет классификацию данных большинством голосов. Если это так, то он не должен иметь проблемы в более высоких размерности данных , поскольку такие методы , как н.п. чувствительное хеширование могут эффективно находить ближайшие сосед.k

Кроме того, выбор функции с сетями байесовскими может уменьшить размерность данных и сделать обучение более легким.

Тем не менее, этот обзорный документ Джона Лафферти в области статистического обучения указывает на то, что непараметрическое обучение в многомерных пространствах признаков все еще остается проблемой и не решено.

Что не так?

Strin
источник
1
Пожалуйста , дайте полную ссылку на бумаге; авторы, кажется, не появляются (заметно) в нем.
Рафаэль

Ответы:

5

Эта проблема известна как проклятие размерности . В основном, когда вы увеличиваете количество измерений, , точки в пространстве обычно стремятся стать далекими от всех других точек. Это делает разделение пространства (например, необходимое для классификации или кластеризации) очень трудным.d

Вы можете увидеть это для себя очень легко. Я сгенерировал случайных мерных точек в единичном гиперкубе при 20 равномерно выбранных значениях из . Для каждого значения я вычислил расстояние от первой точки до всех остальных и взял среднее значение этих расстояний. Построив это, мы можем видеть, что среднее расстояние увеличивается с размерностью, хотя пространство, в котором мы генерируем точки в каждом измерении, остается тем же.д д 1..1000 д50dd1..1000d

Среднее расстояние и размерность

Ник
источник
Конечно. Вы увеличиваете количество точек в гиперсфере фиксированного радиуса экспоненциально в dimensionalty, так что если вы выбираете 50 баллов случайно равномерно это имеет произойти. Поэтому, если ваши рассуждения верны, разделение должно стать легким, если у меня много образцов; это так?
Рафаэль
Я верю, что у тебя все наоборот. Увеличивая размерность, я УМЕНЬШАЮ количество точек в гиперсфере. Разделение становится более трудным, потому что мера расстояния по существу теряет свое значение (например, все далеко).
Ник
kNn|NnSn(k)|n
ndn<<d
Я не вижу, что это верно по определению; похоже, это соглашение, основанное на опыте.
Рафаэль
3

Не полный ответ, но страница википедии, на которую вы ссылались, гласит:

Точность алгоритма k-NN может быть серьезно ухудшена из-за присутствия шумных или нерелевантных признаков, или если масштабы признаков не соответствуют их важности.

Вероятность этого возрастает в присутствии пространственных пространственных объектов.

Дэйв Кларк
источник
Но я думаю, что с PCA (анализ основных компонентов) или любыми другими методами, чтобы уменьшить размерность и удалить ненужные данные, k-NN все еще может работать. И что означают страницы в Википедии, так это то, что наивный k-NN потерпит неудачу. Так что это не объясняет обзорную статью.
Стрин
PCA конечно может работать, но не во всех ситуациях.
Дейв Кларк,