Метод ближайших соседей (kNN)

Метод ближайших соседей (kNN - k Nearest Neighbours) - метод решения задач классификации и задач регрессии, основанный на поиске ближайших объектов с известными значения целевой переменной.

Идея

Метод основан на предположении о том, что близким объектам в признаковом пространстве соответствуют похожие метки.

Для нового объекта $x$ метод предполагает найти ближайшие к нему объекты $x_{1},x_{2},...x_{K}$ и построить прогноз по их меткам.

Формальное описание

Классификация

${\hat {y}}=\mathrm {arg} \max _{y}\sum _{k=1}^{K}{\mathrm {I} (y_{k}==y)}$.

Классификация в пограничном случае

Когда несколько классов имеют одинаковый ранг, можно сопоставить класс:

• случайным образом
• имеющий большую априорную вероятность
• чей ближайший представитель ближе к $x$
• для которого среднее значение представителей этого класса среди ближайших соседей ближе
• чей самый дальний представитель среди ближайших соседей ближе (т.е. класс представлен более компактно)

Регрессия

${\hat {y}}={\frac {\sum _{k=1}^{K}{y_{k}}}{K}}$.

Параметры

• $K$ - подбирается по кросс-валидации
• метрика - выбирается исходя из выбранного признакового пространства

Границы классов при этом будут очень сложными, что интуитивно противоречит тому, что параметр у метода всего один. Парадокс разрешается тем, что на самом деле объекты обучающей выборки также являются своеобразными параметрами алгоритма.

Сложность

Сложность обучения - $O(1)$. Технически правильным ответом также является $O(n)$, так как требуется запоминать обучающую выборку.

Сложность прогнозирования - $O(n)$ для каждого объекта. Если по фиксированной обучающей выборке требуется независимо сделать прогноз для $k$ объектов, сложность $O(kn)$.

Особенности

• + простой, лёгкий и интерпретируемый
• + не требуется предобучения
• + онлайновый
• - высокая сложность одного прогноза
• - проклятие размерности

Взвешенный учёт объектов

Пусть тренировочная выборка задается объектами $x_{1},x_{2},\ldots x_{n}$

Упорядочим их относительно рассматриваемого объекта х $\rho (x,x_{i_{1}})<=\rho (x,x_{i_{2}})<=\ldots <=\rho (x,x_{i_{n}})$.

Обозначим $z_{1}=x_{i_{1}},z_{2}=x_{i_{2}},\ldots z_{K}=x_{i_{K}}$.

Обычный алгоритм $Knn$ можно записать с помощью C-дискриминантных функций: $g_{c}(x)=\sum _{k=1}^{K}\operatorname {I} [z_{k}\in w_{c}],c=1,2,\ldots C$,

где $w_{c}=\{x_{i}:y_{i}=c\}$.

Тогда алгоритм для классификации записывается как

${\hat {y}}=\mathrm {arg} \max _{c=1,2,\ldots C}g_{c}(x)$ Тогда мы можем записать $Knn$ со взвешенным учетом объектов через С-дискриминантную функцию. Для случая с весами она принимает вид:$g_{c}(x)=\sum _{k=1}^{K}\operatorname {I} [z_{k}\in w_{c}]w(k,\rho (x,z_{k}))$.

Для классификации вид алгоритма не изменится. Для регрессии же вид будет следующим:

${\hat {y}}={\frac {\sum _{k=1}^{K}{y_{i}\cdot w(k,\rho (x,z_{k})}}{\sum _{k=1}^{K}w(k,\rho (x,z_{k})}}$.

Где $w(k,\rho )$ - вес(степень важности) $k$-го соседа относительно $x$, не возрастает по $k$, положителен.

Примеры весов

Веса, зависящие от индекса:

$w_{k}=\alpha ^{k},\alpha \in (0,1)$,

$w_{k}={\frac {K+1-k}{K}}$.

Веса, зависящие от расстояния:

$w_{k}={\begin{cases}{\frac {\rho (z_{K},x)-\rho (z_{k},x)}{\rho (z_{K},x)-\rho (z_{1},x)}},&\rho (z_{K},x)\neq \rho (z_{1},x)\\1,&\rho (z_{K},x)=\rho (z_{1},x)\end{cases}}$,

$w_{k}={\frac {1}{\rho (x,z_{k})}}$.

Оптимизации

Структурирование пространства признаков

Методы фильтрации обучающей выборки

Ссылки

Китов, слайды

И еще слайды Китова

Немного Соколова