Scikit Learn - K-Nearest Neighbors

Scikit-Learn - K-Nearest Neighbors (KNN)

This chapter explores K-Nearest Neighbors (KNN), a fundamental instance-based learning algorithm used for both classification and regression tasks in Scikit-Learn.

Neighbors-based learning methods are non-parametric, meaning they do not make strong assumptions about the underlying data distribution. They are often referred to as ‘lazy learners’ because they typically do not have a distinct training phase where a model is explicitly built. Instead, they store the entire training dataset and perform computations only at prediction time.

The core principle of K-Nearest Neighbors is straightforward:

• To classify a new data point, find a predefined number (k) of training samples closest in distance to the new point.
• For classification: Assign the class label that is most frequent among these k neighbors (majority vote).
• For regression: Assign the average (or median) of the target values of these k neighbors.

The ‘distance’ is typically Euclidean distance, but other metrics can be used. The choice of k (number of neighbors) and the distance metric are crucial hyperparameters.

sklearn.neighbors Module

Scikit-Learn’s sklearn.neighbors module provides functionality for both unsupervised (e.g., finding nearest neighbors) and supervised (e.g., KNN classification/regression) neighbors-based learning. These classes can handle NumPy arrays or SciPy sparse matrices as input. Key estimators include KNeighborsClassifier, KNeighborsRegressor, and NearestNeighbors (for unsupervised neighbor searches).

Algorithms for Nearest Neighbor Search

Finding the nearest neighbors efficiently is critical for KNN performance, especially with large datasets. The algorithm parameter in Scikit-Learn’s neighbors-based estimators controls the method used:

Brute Force (algorithm='brute')

The most naive approach computes the distance from the query point to every point in the training set. For a single query point and N training samples in D dimensions, the complexity is O(DN). While simple, it becomes computationally expensive for large N.

When to use: Effective for small datasets or when the overhead of building a tree structure (like KD-Tree or Ball Tree) is not justified for a small number of queries.

K-D Tree (algorithm='kd_tree')

A K-Dimensional Tree is a binary tree data structure that recursively partitions the parameter space along data axes. This creates nested orthographic regions, allowing for faster neighbor searches than brute force.

Advantages:

• Fast construction: Partitioning along axes is relatively quick.
• Efficient queries in low dimensions: For D < ~20, query time can be O(D log N) on average.

Disadvantages:

• Curse of dimensionality: Performance degrades significantly in high dimensions (D > ~20), approaching O(DN) in worst cases.

Ball Tree (algorithm='ball_tree')

A Ball Tree is another tree-based data structure designed to address the inefficiencies of K-D Trees in higher dimensions. It recursively divides data into nodes defined by a centroid and a radius, forming nested hyper-spheres. The triangle inequality is used to prune search paths.

Advantages:

• Better for high dimensions: Often outperforms K-D Trees when D > ~20.
• Handles various distance metrics well.

Disadvantages:

• Higher construction cost: Partitioning into hyper-spheres can be more computationally intensive than K-D Tree construction.

Automatic Selection (algorithm='auto')

This is usually the default setting. Scikit-Learn attempts to determine the best algorithm (brute, kd_tree, or ball_tree) based on the input data (e.g., n_samples, n_features, sparsity) and the metric parameter during the fit method.

Choosing the Right Nearest Neighbors Algorithm

The optimal choice of algorithm depends on several factors:

• Number of Samples (N) and Dimensionality (D):
• Data Structure (Sparsity, Intrinsic Dimensionality): Tree-based algorithms (Ball Tree, K-D Tree) can be faster on sparse data or data with low intrinsic dimensionality. Brute force query time is unaffected by data structure.
• Number of Neighbors (k): Query time for tree-based algorithms can increase with k. Brute force is less affected by k for a single query after distances are computed.
• Number of Query Points: For a small number of queries, the overhead of building a tree might make brute force competitive or even faster. Trees are more beneficial when performing many queries on a static dataset.
• Distance Metric: Ball Trees are generally more robust to different distance metrics compared to K-D Trees, which are optimized for Euclidean-like distances.

It’s often a good idea to start with algorithm='auto' and let Scikit-Learn choose. If performance is critical, benchmarking different algorithms might be necessary.

Example: Using KNeighborsClassifier

Let’s illustrate how these algorithms are used within a KNeighborsClassifier.

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

# Load Iris dataset
iris = load_iris()
X, y = iris.data, iris.target

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

# Create a pipeline: StandardScaler + KNeighborsClassifier
# Feature scaling is important for distance-based algorithms like KNN
knn_pipeline = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=5, algorithm='auto', metric='minkowski', p=2) # p=2 for Euclidean distance
)

# Fit the model
knn_pipeline.fit(X_train, y_train)

# Make predictions
y_pred = knn_pipeline.predict(X_test)

# Evaluate accuracy
accuracy = accuracy_score(y_test, y_pred)
print(f"KNeighborsClassifier Accuracy: {accuracy:.4f}")

# You can try changing algorithm to 'ball_tree', 'kd_tree', or 'brute'
# e.g., KNeighborsClassifier(n_neighbors=5, algorithm='kd_tree')
# and observe if there's any noticeable difference in fitting/prediction time for this small dataset.

Output Example:

KNeighborsClassifier Accuracy: 1.0000

Key Considerations for KNN:

• Choosing k: A small k can lead to a noisy decision boundary (high variance), while a large k can oversmooth it (high bias). k is often chosen via cross-validation.
• Distance Metric: Euclidean is common, but others like Manhattan, Minkowski, or Cosine similarity might be more appropriate depending on the data.
• Feature Scaling: Essential because KNN relies on distances. Features with larger scales can dominate the distance calculation.
• Computational Cost: Prediction can be slow for large datasets as it involves computing distances to all (or many, for tree-based methods) training samples.

For more details on nearest neighbors algorithms and their usage, refer to the Scikit-Learn Nearest Neighbors documentation.