Что такое KNN?

KNN: K-Nearest Neighbors

KNN (K-Nearest Neighbors) — это один из самых простых и интуитивных алгоритмов машинного обучения, основанный на принципе близости. Несмотря на простоту, он остаётся полезным инструментом в практике Data Science.

Основной принцип

Алгоритм работает на простой идее: объект похож на объекты, находящиеся рядом с ним в пространстве признаков.

Для предсказания значения для нового объекта:

1. Вычислить расстояние от этого объекта до всех объектов в обучающем наборе
2. Найти K ближайших объектов
3. Для классификации: выбрать класс, который наиболее часто встречается среди K соседей
4. Для регрессии: вычислить среднее значение целевой переменной K соседей

Пример реализации

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris

# Загрузка данных
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Создание и обучение модели
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train)

# Прогнозирование
y_pred = knn.predict(X_test)
accuracy = knn.score(X_test, y_test)
print(f"Точность: {accuracy:.3f}")

# Получение вероятностей классов
proba = knn.predict_proba(X_test)
print(f"Вероятности для первого объекта: {proba[0]}")

Выбор метрики расстояния

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

1. Евклидово расстояние (Euclidean Distance)

d = sqrt((x1 - x2)^2 + (y1 - y2)^2 + ... + (z1 - z2)^2)

Мост часто используется по умолчанию. Измеряет прямую линию между двумя точками.

2. Манхэттенское расстояние (Manhattan Distance)

d = |x1 - x2| + |y1 - y2| + ... + |z1 - z2|

Используется для данных с дискретными признаками или когда важны изменения по отдельным осям.

3. Косинусное сходство (Cosine Similarity)

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

knn_cosine = KNeighborsClassifier(
    n_neighbors=5,
    metric='cosine'  # Опции: 'euclidean', 'manhattan', 'cosine'
)

Выбор K

Параметр K критичен для производительности:

• K = 1: Модель «запоминает» все примеры, высокое переобучение
• K = 3–5: Хороший баланс для большинства случаев
• K = N (размер набора): Модель предсказывает наиболее частый класс, очень высокий bias

Оптимальное K выбирается через кросс-валидацию:

from sklearn.model_selection import GridSearchCV

param_grid = {'n_neighbors': [3, 5, 7, 9, 11, 15]}
grid_search = GridSearchCV(KNeighborsClassifier(), param_grid, cv=5, scoring='accuracy')
grid_search.fit(X_train, y_train)
print(f"Лучший K: {grid_search.best_params_['n_neighbors']}")
print(f"Лучший CV score: {grid_search.best_score_:.3f}")

Преимущества KNN

1. Простота: Легко понять и реализовать
2. No training phase: Алгоритм не требует явного обучения, всё происходит при предсказании
3. Универсальность: Работает для классификации, регрессии и поиска аномалий
4. Нелинейность: Может захватывать сложные нелинейные зависимости без явного моделирования
5. Интерпретируемость: Легко объяснить решение — посмотрели на соседей

Недостатки KNN

1. Вычислительная сложность: На этапе предсказания нужно вычислить расстояние до всех обучающих примеров — O(N×D), где N — размер обучения, D — размерность
2. Масштабируемость: Для больших датасетов предсказание медленное
3. Проклятие размерности: В высоких размерностях все точки становятся примерно одинаково далеко друг от друга
4. Чувствительность к масштабированию: Необходимо нормализовать признаки
5. Неинформативные признаки: Все признаки влияют одинаково на расстояние

Практические решения

Нормализация признаков

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)
accuracy = knn.score(X_test_scaled, y_test)

Взвешенный KNN (Weighted KNN)

Ближайшие соседи должны иметь большее влияние:

knn_weighted = KNeighborsClassifier(
    n_neighbors=5,
    weights='distance'  # 'uniform' или 'distance'
)

При weights='distance' ближайшие соседи получают больший вес (обратный расстояний).

Ускорение поиска

Для больших датасетов используются пространственные индексы:

knn = KNeighborsClassifier(
    n_neighbors=5,
    algorithm='kd_tree'  # 'ball_tree', 'kd_tree', 'brute'
)

• brute: полный перебор (медленно, но точно)
• kd_tree: быстрее для низких размерностей
• ball_tree: эффективнее для высоких размерностей

Когда использовать KNN

• Baseline модель: Быстро проверить, какой accuracy можно получить
• Небольшие датасеты: Когда вычислительные ограничения не критичны
• Поиск аномалий: KNN хорошо выявляет выбросы
• Рекомендательные системы: Поиск похожих пользователей или элементов
• Локальные закономерности: Когда разные части пространства имеют разные паттерны

KNN — это мощный инструмент для быстрого прототипирования и как база для сравнения более сложных моделей.