Curse of dimensionality

Так называемое «проклятие размерности (curse of dimensionality)» это явление накладывающее серьзные ограничения на классификаторы основанные на оценке локальных свойств плотности вероятности наблюдений в многомерных данных. Одним из наиболее простых и интуитивно понятных методов классификации является метод k ближайших соседей. Класс к которому принадлежит объект определяется наиболее распространенным классом среди наблюдений в прилежащей локальной области:

 

Число соседей k обычно выбирается пропорциональным общему количеству наблюдений в training data set. Очень важно свойство локальности выборки. Рассмотрим одномерный случай. Допустим у нас есть 1000 равномерно распределенных наблюдений на отрезке (0,1). Для того чтобы захватить r (fraction) = 0.01 всех наблюдений в одномерном кубе (отрезок) понадобится интервал длины L = 0.01. В двумерном случае чтобы охватить тот же объем в близлежащей окрестности любого наблюдения  нам понадобится интервал длинны L =0.01^0.5 = 0.1. В 10 мерном случае 0.01 ^ 10 = 0.63 (при том что вся длина ребра 1). Как видим свойство локальности теряется. Иначе говоря, чтобы охватить 1% данных в 10 мерном пространстве для того чтобы оценить класс нового объекта нам понадобится 63% всего диапазона значений каждой переменной. Следующий код строит длинну интервала многомерного пространства (от 1 до 10) в зависимости от величины r(fraction) определяющей число наблюдений в локальной области усреднения:

Добавить комментарий

Войти с помощью: 

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.