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

Метод k-ближайших соседей (k-nearest neighbors, k-NN) — это непараметрический алгоритм машинного обучения, используемый для задач классификации и регрессии. В основе метода лежит предположение, что объекты, близкие в пространстве признаков, принадлежат к одному классу или имеют схожие количественные характеристики. Алгоритм не требует построения модели на этапе обучения (является «ленивым» обучением) и принимает решение на основе анализа ближайших к новому объекту точек из обучающей выборки.

История

Метод k-ближайших соседей был впервые описан в 1951 году американскими статистиками Эвелин Фикс и Джозефом Ходжесом-младшим в рамках работы по непараметрической классификации. В 1967 году математик Томас Ковер и его коллеги формализовали алгоритм и доказали, что при увеличении объёма обучающей выборки вероятность ошибки k-NN стремится к байесовской ошибке (минимально возможной для данной задачи). В 1990-х годах, с ростом вычислительных мощностей и доступности больших данных, метод получил широкое распространение в системах распознавания образов, рекомендательных системах и биоинформатике.

Принцип работы

Алгоритм k-NN состоит из трёх этапов:

Выбор числа соседей k — гиперпараметра, определяющего количество ближайших объектов, участвующих в голосовании. Значение k обычно выбирается нечётным для избежания равенства голосов при бинарной классификации и подбирается экспериментально (например, с помощью кросс-валидации).
Вычисление расстояния — для нового объекта рассчитывается расстояние до всех точек обучающей выборки. Наиболее распространённые метрики:

Евклидово расстояние (для непрерывных признаков);
Манхэттенское расстояние (для данных с разными масштабами);
Расстояние Минковского (обобщённая форма);
Косинусное сходство (для текстовых данных).

Принятие решения:

Классификация: объект относится к классу, который встречается чаще всего среди k ближайших соседей (голосование по большинству).
Регрессия: предсказанное значение вычисляется как среднее (или медиана) целевых переменных k соседей.

Пример работы

Пусть имеется обучающая выборка из точек двух классов (красные и синие). Для нового объекта (зелёная точка) при k=3 находятся три ближайших соседа. Если два из них красные, а один синий, объект классифицируется как красный. При k=5, если три соседа синие и два красные, объект будет отнесён к синему классу.

Выбор числа k

Выбор гиперпараметра k критически влияет на качество модели:

Малое k (например, k=1) приводит к высокой чувствительности к шуму и выбросам, что вызывает переобучение (overfitting). Граница между классами становится излишне извилистой.
Большое k (например, k=50) сглаживает границы, но может привести к недообучению (underfitting), когда модель игнорирует локальные закономерности.

Оптимальное значение k подбирается с помощью методов валидации, таких как k-fold кросс-валидация. На практике часто используют k = √N, где N — количество объектов в обучающей выборке, но это правило не является универсальным.

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

Выбор метрики зависит от природы данных:

Евклидово расстояние — стандартный выбор для непрерывных признаков с одинаковым масштабом. Чувствительно к разным единицам измерения, поэтому признаки часто нормализуют.
Манхэттенское расстояние — более устойчиво к выбросам, чем евклидово, и эффективно для данных с большим количеством нулевых значений (например, разреженные матрицы).
Расстояние Чебышёва — максимум разности по координатам; используется в задачах, где важна наибольшая разница между признаками.
Косинусное сходство — часто применяется для текстовых данных, представленных в виде векторов TF-IDF, так как не зависит от длины вектора.

Взвешивание соседей

Для улучшения качества классификации применяется взвешенное голосование: вклад каждого соседа в решение пропорционален обратному расстоянию до него (или другой функции веса). Это позволяет уменьшить влияние далёких точек и повысить роль близких соседей. Формула веса часто имеет вид:

\[ w_i = \frac{1}{d_i^2} \]

где \(d_i\) — расстояние до i-го соседа. Взвешенный k-NN даёт более гладкие границы и снижает чувствительность к выбору k.

Особенности и ограничения

Вычислительная сложность: на этапе классификации требуется вычислять расстояния до всех точек обучающей выборки, что делает метод медленным при больших объёмах данных (сложность O(N·M), где N — число объектов, M — число признаков). Для ускорения применяют структуры данных, такие как k-d-деревья, шаровые деревья или метод локально-чувствительного хеширования.
Чувствительность к масштабу: признаки с большим диапазоном значений доминируют при расчёте расстояния. Обязательным этапом является нормализация (например, Min-Max или Z-оценка).
Проклятие размерности: при большом числе признаков (десятки и сотни) расстояния между точками становятся почти одинаковыми, что снижает эффективность метода. Для борьбы применяют отбор признаков или методы снижения размерности (PCA, t-SNE).
Необходимость хранения всей выборки: метод требует хранения обучающих данных в памяти, что может быть проблематично для очень больших наборов данных.

Применение

Метод k-ближайших соседей используется в различных областях:

Распознавание образов: классификация рукописных цифр, изображений лиц, отпечатков пальцев.
Рекомендательные системы: поиск пользователей с похожими предпочтениями (collaborative filtering) — например, в системах Netflix или Amazon.
Медицинская диагностика: классификация опухолей (доброкачественные/злокачественные) на основе признаков, полученных из анализов или изображений.
Финансовый анализ: оценка кредитного риска, обнаружение мошеннических транзакций.
Биоинформатика: классификация генов, предсказание функций белков на основе последовательностей.
Геоинформационные системы: интерполяция пространственных данных (например, температуры или уровня загрязнения).

Сравнение с другими методами

Деревья решений: k-NN не создаёт интерпретируемой модели, но часто даёт более высокую точность на небольших наборах данных с чёткой кластеризацией.
Линейные модели (логистическая регрессия, SVM): k-NN эффективен при нелинейных границах между классами, но требует больше памяти и времени при классификации.
Нейронные сети: k-NN проще в реализации и не требует длительного обучения, но уступает нейросетям на больших и сложных данных (например, изображения высокого разрешения).

Вариации метода

k-NN с отбрасыванием далёких соседей: учитываются только соседи, расстояние до которых меньше заданного порога (radius-based NN).
Локально-взвешенный k-NN: веса соседей зависят не только от расстояния, но и от плотности данных в окрестности.
Адаптивный k-NN: значение k может меняться для каждого нового объекта в зависимости от локальной плотности выборки.
Метод на основе графов: строится граф ближайших соседей, и классификация выполняется с помощью алгоритмов распространения меток.

Интересные факты

Метод k-NN часто используется как эталонный (baseline) при сравнении новых алгоритмов машинного обучения, так как он прост в реализации и не требует настройки сложной модели.
В 2006 году на конкурсе Netflix Prize, посвящённом улучшению рекомендательной системы, многие участники использовали варианты k-NN в комбинации с другими методами.
Алгоритм k-NN лежит в основе некоторых методов поиска по сходству в базах данных изображений (content-based image retrieval).

Источники

Fix, E., Hodges, J. L. (1951). Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties. USAF School of Aviation Medicine.
Cover, T., Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
Hastie, T., Tibshirani, R., Friedman, J. (2009). The Elements of Statistical Learning. Springer.
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
Duda, R. O., Hart, P. E., Stork, D. G. (2001). Pattern Classification. Wiley.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →