Лекция 6. Метод k ближайших соседей и метрические методы

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

Ключевые понятия: kNN, евклидово расстояние, манхэттенское расстояние, метрика Минковского, выбор k, голосование соседей, взвешивание, масштабирование, проклятие размерности, поиск ближайших соседей.

1. Назначение и принцип работы метода k ближайших соседей

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

В отличие от логистической регрессии, kNN не строит явную формулу зависимости целевой переменной от признаков. При обучении алгоритм в основном сохраняет данные, а основная вычислительная работа выполняется при прогнозировании. Поэтому kNN относят к методам обучения на примерах (instance-based learning).

Алгоритм выполняет следующие действия:

1. Вычисляет расстояния от нового объекта до обучающих наблюдений.

2. Выбирает объектов с наименьшими расстояниями.

3. Объединяет ответы выбранных соседей: голосованием при классификации или усреднением при регрессии.

4. Возвращает итоговый прогноз.

Например, если среди пяти ближайших объектов три относятся к классу A, а два — к классу B, метод большинства присвоит новому объекту класс A.

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

Результат работы kNN зависит от того, как определяется близость между объектами. Метрика расстояния позволяет численно оценить различие двух векторов признаков.

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

Для двух объектов и с признаками:

Это обычное геометрическое расстояние между точками. Оно часто применяется к числовым признакам после масштабирования.

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

Манхэттенская метрика суммирует абсолютные различия по координатам:

В отличие от евклидовой метрики, здесь различия не возводятся в квадрат перед суммированием.

Метрика Минковского

Евклидово и манхэттенское расстояния являются частными случаями метрики Минковского:

При получаем манхэттенское расстояние, при — евклидово.

Пример. Рассмотрим новую точку и две обучающие точки: и .

Следовательно, точка B ближе к A. При прогноз определяется меткой точки B.

3. Выбор числа соседей k

Число соседей — основной гиперпараметр алгоритма. Оно определяет, сколько обучающих объектов участвует в принятии решения.

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

При большом решение становится более сглаженным, но модель может перестать учитывать важные локальные различия между классами.

Малое k	Большое k
Более гибкая граница классов	Более сглаженная граница
Высокая чувствительность к шуму	Меньшая чувствительность к отдельным наблюдениям
Риск переобучения	Риск недообучения

Оптимальное значение обычно выбирают с помощью перекрёстной проверки на обучающих данных. Тестовая выборка должна оставаться независимой от этого выбора.

Для бинарной классификации нечётное значение иногда помогает уменьшить число ничьих при голосовании, но не гарантирует их отсутствия во всех ситуациях.

4. Классификация, регрессия и взвешивание соседей

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

При обычном голосовании каждому из ближайших соседей назначается одинаковый вес. Прогнозируемый класс — наиболее часто встречающаяся метка:

Здесь — метка i-го ближайшего соседа.

Регрессия

Для числовой целевой переменной используется среднее значение ответов соседей:

Взвешивание по расстоянию

Иногда ближайшие соседи должны влиять на прогноз сильнее, чем более далёкие. Тогда применяют веса, зависящие от расстояния, например:

где — расстояние до i-го соседа, а предотвращает деление на ноль.

Для взвешенной регрессии:

При классификации можно суммировать веса соседей отдельно для каждого класса и выбирать класс с наибольшей суммой. В scikit-learn доступны варианты weights="uniform" и weights="distance"; точная обработка нулевых расстояний зависит от реализации.

5. Масштабирование признаков и проклятие размерности

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

Предположим, в наборе данных есть возраст в диапазоне от 18 до 70 лет и годовой доход в диапазоне от 100 000 до 10 000 000 тенге. Без масштабирования доход будет доминировать при вычислении евклидова расстояния.

Один из способов устранить эту проблему — стандартизация:

где — среднее значение признака, а — его стандартное отклонение, вычисленные по обучающей выборке.

Стандартизацию следует выполнять внутри Pipeline, чтобы параметры преобразования не рассчитывались по тестовым данным.

Проклятие размерности

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

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

Дополнительное ограничение — стоимость поиска соседей. Для больших наборов данных вычисление расстояний до множества объектов может требовать значительных ресурсов. Для ускорения применяются структуры поиска, например KD-деревья и Ball-деревья; их эффективность зависит от размерности и распределения данных.

6. Практическая реализация на Python

Рассмотрим классификацию цветов ириса с помощью KNeighborsClassifier из библиотеки scikit-learn.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report

X, y = load_iris(return_X_y=True)

X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.2, random_state=42, stratify=y
)

model = make_pipeline(
StandardScaler(),
KNeighborsClassifier(n_neighbors=5)
)

model.fit(X_train, y_train)
predictions = model.predict(X_test)

print("Accuracy:", accuracy_score(y_test, predictions))
print(classification_report(y_test, predictions))

В примере сначала загружается набор данных Iris. После разделения выборки стандартизация и kNN объединяются в Pipeline. Это позволяет вычислять параметры масштабирования только на обучающих данных.

Метод fit() сохраняет обучающие наблюдения, а predict() определяет классы тестовых объектов на основе ближайших соседей.

Эксперимент с числом соседей

Для сравнения разных значений используем перекрёстную проверку только на обучающей выборке:

for k in [1, 3, 5, 7, 11]:
candidate = make_pipeline(
StandardScaler(),
KNeighborsClassifier(n_neighbors=k)
)

scores = cross_val_score(
candidate, X_train, y_train,
cv=5, scoring="accuracy"
)

print(f"k={k}: средняя Accuracy = {scores.mean():.3f}")

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

Для исследования влияния расстояний можно сравнить weights="uniform" и weights="distance" либо значения параметра p=1 и p=2 при метрике Минковского.

7. Практическое значение и выводы

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

Однако качество kNN существенно зависит от выбранной метрики, числа соседей, масштабирования признаков и структуры данных. При большом числе признаков или очень крупной обучающей выборке могут возникать проблемы с качеством и скоростью прогнозирования.

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