kNN: сравнение способов поиска ближайших соседей

Что такое kNN

Метод k ближайших соседей относится к алгоритмам машинного обучения с учителем. Для нового объекта алгоритм находит k наиболее близких объектов обучающей выборки и определяет класс по большинству голосов.

ŷ(x) = arg max_c Σ 1(y_i = c)

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

Способы поиска соседей

Brute force

Полный перебор всех объектов. Прост в реализации и часто эффективен на небольших наборах данных.

KD-tree

Древовидная структура, разделяющая пространство признаков. Может ускорять поиск при умеренной размерности.

Ball-tree

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

Расстояния и стандартизация

Поскольку kNN основан на расстояниях, признаки необходимо привести к сопоставимому масштабу. В работе использовалась стандартизация:

z = (x − μ) / σ

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

d(x,z) = √Σ(x_j − z_j)²

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

d(x,z) = Σ|x_j − z_j|

Постановка эксперимента

Набор данных
Breast Cancer из scikit-learn

Разделение
70% обучение, 30% тест

Значения k
1, 5, 15, 25

Оценка
Accuracy, F1, время predict

Результаты для евклидовой метрики

k	Brute, мс	Ball-tree, мс	KD-tree, мс	Accuracy	F1
1	5.878555	6.037340	6.260570	0.959064	0.967136
5	5.299840	6.176430	6.839890	0.959064	0.968326
15	5.218685	6.586120	7.197855	0.959064	0.968326
25	5.505515	6.696930	7.601640	0.947368	0.959641

Среднее время предсказания

Brute

5.22 мс

Ball-tree

6.59 мс

KD-tree

7.20 мс

Для наглядности показаны результаты при k = 15.

Выводы

      На исследованном наборе данных brute force оказался быстрее KD-tree
      и Ball-tree. Причина заключается в небольшом объёме выборки и накладных
      расходах древовидных структур. Качество классификации в большей степени
      зависело от значения k, метрики расстояния и подготовки данных.
    

Поиск ближайших соседей применяется не только в классическом kNN, но и в рекомендательных системах, векторных базах данных, retrieval-системах и RAG-подходах.