Scikit Learn - KNN Learning

Scikit-learn - k-Nearest Neighbors (k-NN) Learning

k-Nearest Neighbors (k-NN) is a simple, versatile, and widely used machine learning algorithm. It’s classified as non-parametric, meaning it makes no assumptions about the underlying data distribution, and as a lazy learning (or instance-based) algorithm, meaning it doesn’t build a general internal model during training. Instead, it stores all training data and performs computations only at prediction time.

The k-NN algorithm operates in two main steps:

1. Training/Storage Phase: Store all data points from the training set and their corresponding labels (for supervised learning).
2. Prediction Phase: For a new, unlabeled sample: a. Calculate the distance (e.g., Euclidean) from the new sample to all samples in the training set. b. Identify the k nearest neighbors (the k training samples with the smallest distances). c. For classification, predict the class label by a majority vote among these k neighbors. For regression, predict the value as the average (or median) of the target values of these k neighbors.

The sklearn.neighbors module in Scikit-learn implements k-NN for both unsupervised (neighbor searches) and supervised (classification and regression) learning tasks.

Unsupervised k-NN Learning: Nearest Neighbor Searches

The core of k-NN involves finding the nearest neighbors to a given point. This neighbor search capability is fundamental to many algorithms beyond k-NN itself (e.g., some clustering methods, manifold learning). Scikit-learn provides sklearn.neighbors.NearestNeighbors for this purpose. It acts as a uniform interface to efficient neighbor search algorithms like BallTree, KDTree, and brute-force search.

Scikit-learn Module: NearestNeighbors

sklearn.neighbors.NearestNeighbors is used to implement unsupervised nearest neighbor learning. It finds the k nearest neighbors for each sample in a dataset or for new query points.

Key Parameters for NearestNeighbors:

Parameter	Description
n_neighbors	Integer (default=5). Number of neighbors to retrieve.
radius	Float (default=1.0). Radius for finding neighbors within a fixed distance. If used, kneighbors returns all points within this radius.
algorithm	String {‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’} (default=‘auto’). Algorithm used to compute nearest neighbors. ‘auto’ attempts to decide the best algorithm based on the input data.
leaf_size	Integer (default=30). Leaf size passed to BallTree or KDTree. Affects construction speed, query speed, and memory.
metric	String or callable (default=‘minkowski’). Distance metric to use. Common values: ‘euclidean’, ‘manhattan’, ‘cosine’. See Scikit-learn documentation for a full list from sklearn.metrics.pairwise_distances or scipy.spatial.distance.
p	Integer (default=2). Parameter for the Minkowski metric. p=1 is Manhattan distance (L1), p=2 is Euclidean distance (L2).
metric_params	Dict (default=None). Additional keyword arguments for the metric function.
n_jobs	Integer or None (default=None). Number of parallel jobs to run for neighbor search. -1 means using all processors.

Implementation Example: Finding Neighbors

from sklearn.neighbors import NearestNeighbors
import numpy as np

# Sample input data
input_data = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])

# Initialize NearestNeighbors to find 3 nearest neighbors
nrst_neigh = NearestNeighbors(n_neighbors=3, algorithm='ball_tree')

# Fit the model with the input data (builds the tree)
nrst_neigh.fit(input_data)

# Find the K-neighbors for the same input_data points
# Returns distances and indices of the neighbors
distances, indices = nrst_neigh.kneighbors(input_data)

print("Indices of nearest neighbors (each row corresponds to a point in input_data):")
print(indices)
print("\nDistances to nearest neighbors:")
print(distances)

# We can also get a sparse graph showing connections between neighbors
# For each point, a '1' indicates a neighbor within the k specified
connectivity_graph = nrst_neigh.kneighbors_graph(input_data).toarray()
print("\nConnectivity Graph (Adjacency Matrix of Neighbors):")
print(connectivity_graph)

Output

Indices of nearest neighbors (each row corresponds to a point in input_data):
[[0 1 3]
 [1 0 2]
 [2 1 0]
 [3 4 0]
 [4 3 5]
 [5 4 3]]

Distances to nearest neighbors:
[[0.         1.         2.82842712]
 [0.         1.         1.41421356]
 [0.         1.41421356 2.23606798]
 [0.         1.         2.82842712]
 [0.         1.         1.41421356]
 [0.         1.41421356 2.23606798]]

Connectivity Graph (Adjacency Matrix of Neighbors):
[[1. 1. 0. 1. 0. 0.]
 [1. 1. 1. 0. 0. 0.]
 [0. 1. 1. 0. 0. 1.]
 [1. 0. 0. 1. 1. 0.]
 [0. 0. 0. 1. 1. 1.]
 [0. 0. 1. 0. 1. 1.]]

The first neighbor is always the point itself (distance 0) because the query set is the same as the training set. This NearestNeighbors object can then be used by other algorithms requiring efficient neighbor lookups.

Supervised k-NN Learning

Supervised k-NN uses neighbor information for prediction tasks:

• Classification: For data with discrete labels. Assigns the class label that is most frequent among the k nearest neighbors (majority vote).
• Regression: For data with continuous labels. Assigns the predicted value as the average (or other aggregate like median) of the target values of the k nearest neighbors.

k-NN Classifiers

Scikit-learn provides two main k-NN classifiers:

• KNeighborsClassifier: Classifies based on the k nearest neighbors. k is a user-specified integer.
• RadiusNeighborsClassifier: Classifies based on the number of neighbors within a fixed radius r around each query point. r is a user-specified float.

Key parameters for these classifiers include n_neighbors (for KNeighborsClassifier), radius (for RadiusNeighborsClassifier), weights (‘uniform’ for equal weighting, ‘distance’ to weight closer neighbors more), algorithm, leaf_size, metric, p, and n_jobs.

Example: KNeighborsClassifier on Iris Dataset

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
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, stratify=y)

# Scale features (important for distance-based algorithms like KNN)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Initialize and train KNeighborsClassifier
knn_clf = KNeighborsClassifier(n_neighbors=5, weights='distance') # Using 5 neighbors, distance weighting
knn_clf.fit(X_train_scaled, y_train)

# Make predictions
y_pred = knn_clf.predict(X_test_scaled)

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

Output

KNeighborsClassifier Accuracy: 0.9778

Choosing an optimal k is crucial and often done via cross-validation. Smaller k values can lead to noisy decision boundaries (high variance), while larger k values can oversmooth (high bias).

k-NN Regressors

Similarly, Scikit-learn provides two main k-NN regressors:

• KNeighborsRegressor: Predicts based on the average (or other aggregation) of target values from the k nearest neighbors.
• RadiusNeighborsRegressor: Predicts based on neighbors within a fixed radius r.

Parameters are similar to their classifier counterparts.

Example: KNeighborsRegressor

from sklearn.datasets import fetch_california_housing # A regression dataset
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error
import numpy as np

# Load California Housing dataset
housing = fetch_california_housing()
X, y = housing.data, housing.target

# For faster example, use a subset of data
X_subset, y_subset = X[:2000], y[:2000]

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

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

# Initialize and train KNeighborsRegressor
knn_reg = KNeighborsRegressor(n_neighbors=7, weights='distance') # Using 7 neighbors
knn_reg.fit(X_train_scaled, y_train)

# Make predictions
y_pred_reg = knn_reg.predict(X_test_scaled)

# Evaluate using Mean Squared Error (MSE)
mse = mean_squared_error(y_test, y_pred_reg)
print(f"KNeighborsRegressor MSE: {mse:.4f}")
print(f"KNeighborsRegressor RMSE: {np.sqrt(mse):.4f}")

# Example prediction on a new sample (must be scaled similarly)
sample_new_data = X_test_scaled[0].reshape(1, -1) # Taking the first test sample
predicted_value = knn_reg.predict(sample_new_data)
print(f"Predicted value for a sample: {predicted_value[0]:.4f}, True value: {y_test[0]:.4f}")

Output (values depend on dataset and split)

KNeighborsRegressor MSE: 0.5568
KNeighborsRegressor RMSE: 0.7462
Predicted value for a sample: 0.9695, True value: 0.4770

The weights='distance' parameter often improves performance by giving more influence to closer neighbors. The choice of k and the distance metric remain important considerations for k-NN regressors as well.

For more detailed information, refer to the Scikit-learn User Guide: https://scikit-learn.org/stable/modules/neighbors.html