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

Постановка задачи

Рассмотрим задачу классификации животных по двум признакам:

• Длина усов
• Длина хвоста

Для каждого объекта в обучающей выборке известна метка: кот или пёс. Цель — построить модель, которая по новым измерениям определит класс животного.

При визуализации данных наблюдается, что объекты одного класса группируются в определённых областях пространства признаков.

Гипотеза о компактности

Основа метода KNN — гипотеза о компактности:

Объекты одного класса расположены «близко» друг к другу в пространстве признаков, а объекты разных классов — «далеко».

Эта гипотеза позволяет решать задачу классификации через поиск похожих (близких) объектов в обучающей выборке.

Алгоритм KNN

Определение:
K-ближайших соседей (K Nearest Neighbors, KNN) — один из самых простых и интуитивно понятных алгоритмов классификации.

Алгоритм предсказания:

1. Для нового объекта вычислить расстояние до всех объектов обучающей выборки
2. Выбрать $K$ объектов с наименьшим расстоянием
3. Присвоить объекту класс, который чаще всего встречается среди $K$ соседей (голосование большинства)

Гиперпараметр:
$K$ — количество соседей, участвующих в голосовании. Выбор $K$ влияет на качество модели:

• Малое $K$: модель чувствительна к шуму и выбросам
• Большое $K$: граница решений становится более гладкой, но может потерять локальные особенности

Метрики расстояния

Для определения «близости» объектов используются различные метрики:

Манхэттенское расстояние

$$d(\mathbf{x}, \mathbf{\hat{x}}) = \sum_{i=1}^{N} |x_i - \hat{x}_i|$$

Евклидово расстояние

$$d(\mathbf{x}, \mathbf{\hat{x}}) = \sqrt{\sum_{i=1}^{N} (x_i - \hat{x}_i)^2}$$

Косинусное расстояние

$$d(\mathbf{x}, \mathbf{\hat{x}}) = 1 - \frac{\sum_{i=1}^{N} x_i \hat{x}i}{\sqrt{\sum{i=1}^{N} x_i^2} \cdot \sqrt{\sum_{i=1}^{N} \hat{x}_i^2}}$$

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

Проблемы и решения

1. Зависимость от масштаба признаков

Проблема:
Если признаки имеют разные масштабы (например, 29 признаков ∈ [0, 1], а один ∈ [0, 1000]), то расстояние будет доминироваться признаком с большим масштабом.

Решение — нормализация признаков:

• Минимакс-нормализация: приведение всех значений к диапазону [0, 1]
• Стандартизация: приведение к нулевому математическому ожиданию и единичной дисперсии ($\mu = 0, \sigma = 1$)

2. Вычислительная сложность

Проблема:
При большом объёме обучающей выборки ($N$ объектов) поиск ближайших соседей требует $O(N)$ операций сравнения для каждого нового объекта.

Решение — структуры данных для ускорения поиска:

• kD-tree (k-dimensional tree): дерево разбиения пространства, на каждом уровне разделяющее данные по одному признаку
• Ball tree: иерархическая структура на основе гиперсфер
• HNSW (Hierarchical Navigable Small World): графовая структура для приближённого поиска ближайших соседей
• FRiS-Stolp: метод отбора эталонных объектов для сокращения размера выборки

3. Улучшение голосования

Вместо простого подсчёта количества соседей каждого класса можно использовать взвешенное голосование, где вес соседа обратно пропорционален расстоянию до него:

$$\text{вес}_i = \frac{1}{d(\mathbf{x}, \mathbf{x}_i)} \quad \text{или} \quad \text{вес}_i = e^{-d(\mathbf{x}, \mathbf{x}_i)}$$

Свойства модели KNN

Метод FRiS-Stolp для отбора эталонов

Для сокращения вычислительной сложности можно отобрать подмножество наиболее информативных объектов — эталонов (столпов).

Критерий качества эталона:
Объект является хорошим эталоном своего класса, если:

• Объекты его класса расположены максимально близко к нему
• Объекты других классов расположены максимально далеко

Функция FRiS: $$\text{FRiS}(z, a_i, b_i) = \frac{r_2 - r_1}{r_2 + r_1}$$

где $r_1$ — расстояние до ближайшего объекта своего класса, $r_2$ — до ближайшего объекта чужого класса.

В следующих главах: метрики качества моделей машинного обучения, линейная регрессия.