Finding Nearest Neighbors

KNN Algorithm - Finding Nearest Neighbors

Introduction to K-Nearest Neighbors (KNN)

K-Nearest Neighbors (KNN) is a simple, yet effective, non-parametric supervised machine learning algorithm used for both classification and regression tasks. It’s particularly popular for classification.

Key characteristics of KNN:

• Lazy Learning: KNN is considered a ‘lazy’ learner because it doesn’t build an explicit model during a distinct training phase. Instead, it stores the entire training dataset.
• Instance-Based Learning: Predictions for new data points are made based on the characteristics of their nearest neighbors in the training set.
• Non-Parametric: It makes no assumptions about the underlying data distribution (unlike, for example, linear regression or Gaussian Naive Bayes).

How KNN Works

The core idea is ‘feature similarity’ or proximity: a new data point is assigned to the class (or predicted value) that is most common among its ‘K’ closest neighbors in the feature space.

The process for classifying a new data point:

1. Choose K: Select the number of neighbors (K) to consider. This is a crucial hyperparameter.
2. Calculate Distances: Compute the distance between the new data point and every point in the training dataset. Common distance metrics include:
3. • Euclidean Distance: The straight-line distance between two points (most common for continuous variables). sqrt(Σ(xᵢ - yᵢ)²)
4. • Manhattan Distance: The sum of the absolute differences of their Cartesian coordinates. Σ|xᵢ - yᵢ|
5. • Hamming Distance: Used for categorical variables (number of positions at which corresponding symbols are different).
6. • Minkowski Distance: A generalization of Euclidean and Manhattan distance.
7. Identify Neighbors: Find the K training data points with the smallest calculated distances to the new point (the K nearest neighbors).
8. Majority Vote (Classification): Determine the most frequent class label among these K neighbors. Assign this majority class label to the new data point.
9. Average (Regression): Calculate the average (or median) of the target values of the K nearest neighbors. Assign this average value as the prediction for the new data point.

Choosing the Right K

The value of K significantly impacts the model’s performance:

• Small K (e.g., K=1): The model is highly sensitive to noise and outliers. Decision boundaries can be complex and irregular (high variance, low bias). Prone to overfitting.
• Large K: The model becomes smoother and less sensitive to noise. Decision boundaries become simpler. However, if K is too large, it might include neighbors from other classes, potentially misclassifying the point (high bias, low variance). Prone to underfitting.
• Choosing K: K is typically chosen via hyperparameter tuning using cross-validation. Odd values for K are often preferred for binary classification to avoid ties in voting.

Importance of Feature Scaling

Since KNN relies on distance calculations, features with larger value ranges can disproportionately influence the distance metric. Therefore, feature scaling (e.g., Standardization using StandardScaler or Normalization using MinMaxScaler) is crucial before applying KNN.

Implementation in Python (Scikit-learn)

Let’s implement KNN for classification using the Iris dataset.

KNN as Classifier Example

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, cross_val_score, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report, confusion_matrix, accuracy_score

# 1. Load Iris dataset
iris = load_iris()
X = iris.data
y = iris.target
feature_names = iris.feature_names
class_names = iris.target_names

# 2. Split data into training and test sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42, stratify=y)

# 3. Create a pipeline: StandardScaler + KNeighborsClassifier
# Pipeline ensures scaling is applied correctly during cross-validation and prediction
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier())
])

# 4. --- Hyperparameter Tuning (Finding the best K) ---
# Define a range of K values to test
param_grid = {'knn__n_neighbors': range(1, 26)} # Test K from 1 to 25

# Use GridSearchCV for exhaustive search with cross-validation (e.g., 5-fold)
grid_search = GridSearchCV(pipe, param_grid, cv=5, scoring='accuracy')
grid_search.fit(X_train, y_train)

# Best K found
best_k = grid_search.best_params_['knn__n_neighbors']
print(f"Best K found by GridSearchCV: {best_k}")
print(f"Best cross-validation accuracy: {grid_search.best_score_:.4f}")

# 5. Train the final model using the best K on the full training data
final_model = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(n_neighbors=best_k))
])
final_model.fit(X_train, y_train)

# 6. Make predictions on the test set
y_pred = final_model.predict(X_test)

# 7. Evaluate the final model
print("\n--- Final Model Evaluation on Test Set ---")
conf_mat = confusion_matrix(y_test, y_pred)
acc = accuracy_score(y_test, y_pred)
class_rep = classification_report(y_test, y_pred, target_names=class_names)

print(f"Test Accuracy: {acc:.4f}")
print("\nConfusion Matrix:")
# Using seaborn for a nicer heatmap
plt.figure(figsize=(6, 4))
sns.heatmap(conf_mat, annot=True, fmt='d', cmap='Blues', xticklabels=class_names, yticklabels=class_names)
plt.xlabel('Predicted Label')
plt.ylabel('True Label')
plt.title('Confusion Matrix')
plt.show()

print("\nClassification Report:")
print(class_rep)

Output (Illustrative)

Best K found by GridSearchCV: 3
Best cross-validation accuracy: 0.9619

--- Final Model Evaluation on Test Set ---
Test Accuracy: 0.9778

Confusion Matrix:
(Seaborn heatmap plot showing the confusion matrix)

Classification Report:
              precision    recall  f1-score   support

      setosa       1.00      1.00      1.00        15
  versicolor       1.00      0.93      0.97        15
   virginica       0.94      1.00      0.97        15

    accuracy                           0.98        45
   macro avg       0.98      0.98      0.98        45
weighted avg       0.98      0.98      0.98        45

This example demonstrates loading data, splitting, using a Pipeline for scaling and classification, finding the optimal K using GridSearchCV with cross-validation, training the final model with the best K, and evaluating its performance on the unseen test set. The results show high accuracy for the Iris dataset with K=3.

KNN as Regressor Example

KNN can also predict continuous values. Here’s a brief example using KNeighborsRegressor on the Diabetes dataset.

import numpy as np
from sklearn.datasets import load_diabetes
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsRegressor
from sklearn.pipeline import Pipeline
from sklearn.metrics import mean_squared_error, r2_score

# 1. Load Diabetes dataset (regression task)
diabetes = load_diabetes()
X, y = diabetes.data, diabetes.target

# 2. Split data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# 3. Create pipeline
pipe_reg = Pipeline([
    ('scaler', StandardScaler()),
    ('knn_reg', KNeighborsRegressor())
])

# 4. Tune K
param_grid_reg = {'knn_reg__n_neighbors': range(1, 31)} # Test K from 1 to 30
grid_search_reg = GridSearchCV(pipe_reg, param_grid_reg, cv=5, scoring='neg_mean_squared_error')
grid_search_reg.fit(X_train, y_train)

best_k_reg = grid_search_reg.best_params_['knn_reg__n_neighbors']
print(f"Best K for Regression: {best_k_reg}")
print(f"Best CV Negative MSE: {grid_search_reg.best_score_:.2f}")

# 5. Final Model Training & Evaluation
final_model_reg = Pipeline([
    ('scaler', StandardScaler()),
    ('knn_reg', KNeighborsRegressor(n_neighbors=best_k_reg))
])
final_model_reg.fit(X_train, y_train)
y_pred_reg = final_model_reg.predict(X_test)

mse = mean_squared_error(y_test, y_pred_reg)
r2 = r2_score(y_test, y_pred_reg)

print("\n--- Regression Model Evaluation on Test Set ---")
print(f"Mean Squared Error (MSE): {mse:.2f}")
print(f"R-squared (R2): {r2:.4f}")

Output (Illustrative)

Best K for Regression: 11
Best CV Negative MSE: -3380.73

--- Regression Model Evaluation on Test Set ---
Mean Squared Error (MSE): 3027.05
R-squared (R2): 0.4529

This shows KNN used for regression, predicting a continuous target. The best K was found via cross-validation, and the model’s performance is evaluated using MSE and R-squared.

Pros and Cons of KNN

Pros

• Simple and Intuitive: Easy to understand and implement.
• No Training Phase: Learns instantly (just stores data), making it fast to ‘train’.
• Adapts Easily: Can adapt to new training data easily without retraining a complex model.
• Non-Parametric: Makes no assumptions about data distribution.
• Versatile: Usable for both classification and regression.

Cons

• Computationally Expensive Prediction: Calculating distances to all training points for each prediction can be slow, especially with large datasets (can be mitigated with algorithms like BallTree or KDTree, often used by default in Scikit-learn).
• High Memory Usage: Requires storing the entire training dataset.
• Sensitivity to K: Performance heavily depends on the choice of K.
• Sensitivity to Feature Scaling: Requires features to be scaled appropriately.
• Sensitivity to Irrelevant Features (‘Curse of Dimensionality’): Performance degrades in high-dimensional spaces as distances become less meaningful and irrelevant features can dominate distance calculations.

Applications of KNN

KNN is often used in:

• Recommendation Systems: Finding similar items or users.
• Image Recognition: Classifying images based on similarity to known images.
• Anomaly Detection: Identifying points far from their neighbors.
• Financial Modeling: Predicting credit ratings or stock prices based on similar historical patterns.
• Medical Diagnosis: Assisting diagnosis based on similar patient cases (though requires careful validation).

Further Resources

• Scikit-learn Nearest Neighbors Documentation: https://scikit-learn.org/stable/modules/neighbors.html
• StatQuest: K-Nearest Neighbors Explained: https://statquest.org/video-index/ (Search for KNN)