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

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

Идея

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

Для нового объекта $x$ метод предполагает найти ближайшие к нему объекты $x_1, x_2, ... x_K$ и построить прогноз по их меткам.

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

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

$\hat{y} = \mathrm{arg}\max_y \sum_{k = 1}^{K} {\Iota (y_k == y)}$

Регрессия

$\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)}$