K-nearest neighbors для аналитика

Зачем это знать

KNN — одна из простейших и интуитивных ML-моделей. «Похожих users найди, посмотри что они делают». Применяется в classification, regression, recommendations, anomaly detection.

На собесах KNN часто просят объяснить как baseline. Understanding — middle-level.

Короткое объяснение

Для нового наблюдения:

1. Найти K ближайших соседей из training set
2. Classification: vote majority
3. Regression: average

Нет «обучения» в классическом смысле — всё хранится, compute at predict time.

Алгоритм

Classification

def knn_predict(x_new, X_train, y_train, k=5):
    # 1. Distance to all training points
    distances = [euclidean(x_new, x) for x in X_train]
    
    # 2. K smallest
    nearest_indices = np.argsort(distances)[:k]
    
    # 3. Majority vote
    return mode([y_train[i] for i in nearest_indices])

Regression

Same, но step 3: np.mean(y_train[i] for i in nearest).

Distance metrics

Euclidean

d(x, y) = √Σ (x_i - y_i)²

Default для continuous data.

Manhattan

d(x, y) = Σ |x_i - y_i|

Robust к outliers.

Cosine

cos(x, y) = (x · y) / (|x| × |y|)

Для text embeddings, recommendations.

Hamming

Для categorical. Считает mismatches.

K — параметр

Low K (1-3)

• Sensitive к шуму
• Overfitting
• Capture local patterns

High K (50+)

• Smooth predictions
• Underfitting
• Miss details

Optimal — cross-validation.

Rule of thumb

K = √N (где N — training size).

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

• Simple. Легко explain.
• No training. Lazy learning.
• Works для classification и regression.
• Non-linear. Handles complex boundaries.

Недостатки

• Slow at predict time. Recompute distances — O(N).
• Memory-intensive. Store all training.
• Curse of dimensionality. Bad at high dimensions.
• Sensitive to scale. Features must be normalized.

Feature scaling

KNN полагается на distances → features с разными scales мешают:

from sklearn.preprocessing import StandardScaler

X_scaled = StandardScaler().fit_transform(X)

Без scaling «age» (0-100) dominates «income» (0-1M).

В Python

from sklearn.neighbors import KNeighborsClassifier

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

Curse of dimensionality

В high-dimensional space все points almost равны по distance. KNN теряет power.

Fix:

• Feature selection
• Dimensionality reduction (PCA)
• Use other model

Rule: < 20 features обычно ok.

Применение в аналитике

User similarity

Найти похожих users → рекомендации.

-- Pseudo SQL
SELECT similar_user_id, item
FROM
    (knn(my_features, user_features, k=10) AS similar)
JOIN user_purchases ON user_id = similar.similar_user_id;

Collaborative filtering

User-based или item-based KNN для recommendations.

Missing data imputation

Для пропусков — KNN-imputation. Найти похожих rows, импутировать.

Anomaly detection

Big distance to k-nearest = outlier.

KNN vs другие модели

vs Tree

Tree — explicit rules. KNN — implicit distance.

vs Linear

Linear — parametric (coefficients). KNN — non-parametric.

vs Neural network

NN — scale. KNN — small data, interpretable.

Hyperparameters

n_neighbors (K)

Главный. Tune через CV.

weights

• uniform: все равны
• distance: closer — больше weight

metric

Euclidean default, но можно Manhattan, cosine.

На собесе

«Что такое KNN?» Для нового point — find K nearest, majority vote / average.

«K как выбрать?» Cross-validation.

«Scaling нужен?» Да. Features в одинаковом range.

«Проблемы?» Slow predict, curse of dimensionality, memory.

Частые ошибки

Без scaling

Результат meaningless если features несопоставимы.

Too small K

Overfitting, шумные predictions.

High dimensions

Imbalanced data

Majority class dominates. Use weighted KNN.

Связанные темы

• Classification vs regression
• Decision trees для аналитика
• Clustering простыми словами
• Cross-validation простыми словами

FAQ

KNN для regression?

Да. Average K neighbors.

Оптимальная complexity?

O(N × D) per prediction, где N — training, D — features. На больших datasets slow.

Kd-tree помогает?

Ускоряет neighbor search для low-dimensional data. > 20 dim — не сильно помогает.

---

Тренируйте ML — откройте тренажёр с 1500+ вопросами для собесов.