Exploring Decision Boundaries in K-Nearest Neighbors (KNN)

A decision boundary is a crucial concept in classification tasks, representing the lines or surfaces that separate different groups. It defines the regions attributed to each class based on the model's predictions. The K-Nearest Neighbors (KNN) algorithm relies on the idea that data points with similar features tend to be near each other in the feature space.

Decision Boundaries in KNN

The configuration of decision boundaries in KNN is affected by:

• The value of K: This determines how many neighbors are considered.
• Data distribution: How data points are arranged in the space.

For instance, in a dataset with two classes, the decision boundary is the line or curve that separates regions where each class is predicted. In a 1-nearest neighbor scenario, this boundary can be visualized using a Voronoi diagram.

Visualizing with Voronoi Diagrams

• Voronoi diagrams partition space into regions based on the closest training point.
• Each region, or Voronoi cell, is composed of points nearest to a specific training point.
• The lines between regions indicate where points are equidistant to two or more training points. These lines form the decision boundaries in a 1-nearest neighbor model, which are often irregular.
• Labeling training points by class in a Voronoi diagram reveals how KNN classifies new points based on the region they fall into.
• The boundary line between two points is the perpendicular bisector of the line segment joining them, cutting it in half at a right angle.

Formation of Decision Boundaries

KNN and Voronoi Relationship

In two-dimensional space, KNN decision boundaries can be visualized as Voronoi diagrams:

• KNN Boundaries: They are defined by the regions where classification shifts based on the nearest neighbors. As K increases, the boundaries become smoother, less influenced by local variations, and may predict the majority class for larger areas.
• Voronoi Diagram as a Special Case: With K=1, KNN's decision boundaries align with the Voronoi diagram of training points, where each region represents proximity to the nearest training point.

How KNN Defines Decision Boundaries

In KNN, decision boundaries are shaped by both the selection of K and the distance metric:

1. Impact of 'K' on Decision Boundaries:

   • Small K: Results in complex boundaries that closely follow training data, possibly leading to overfitting.
   • Large K: Results in smoother boundaries that are less sensitive to individual data points, which can lead to underfitting.

2. Distance Metric:

   • Euclidean Distance: Commonly used, resulting in circular or elliptical boundaries.
   • Manhattan Distance: Leads to axis-aligned boundaries.

Decision Boundaries for Different K

Consider a binary classification problem with two features to observe how KNN decision boundaries vary with different K values. This example uses synthetic data to demonstrate these changes:

• Creating a Grid: Generate a grid of points across the feature space.
• Classifying Grid Points: Use KNN to classify each grid point based on its neighbors.
• Plotting: Color the grid points according to their class labels and delineate where class changes occur.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_classification
from sklearn.neighbors import KNeighborsClassifier

X, y = make_classification(n_samples=200, n_features=2, n_informative=2, n_redundant=0, n_clusters_per_class=1, random_state=42)

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.01), np.arange(y_min, y_max, 0.01))

fig, axs = plt.subplots(2, 2, figsize=(12, 10))
k_values = [1, 3, 5, 10]

for ax, k in zip(axs.flat, k_values):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X, y)
    
    Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    ax.contourf(xx, yy, Z, alpha=0.3, cmap=plt.cm.Paired)
    ax.scatter(X[:, 0], X[:, 1], c=y, edgecolor='k', cmap=plt.cm.Paired, marker='o')
    ax.set_title(f'KNN Decision Boundaries (k={k})')
    ax.set_xlabel('Feature 1')
    ax.set_ylabel('Feature 2')

plt.tight_layout()
plt.show()

Factors Affecting KNN Decision Boundaries

• Feature Scaling: KNN is sensitive to data scale. Features with larger ranges can dominate distance calculations, impacting boundary shapes.
• Noise in Data: Outliers and noisy data can distort boundaries, leading to errors.
• Data Distribution: The spread of data points affects how KNN separates classes.
• Boundary Shape: Clear boundaries enhance classification accuracy, while unclear ones can lead to mistakes.

Understanding these boundaries is essential for optimizing KNN's performance for specific datasets.