Introduction to Machine Learning

by Albert Major

Introduction to K-Nearest Neighbors (KNN)

• Definition: KNN is a machine learning algorithm used for both classification (predicting a discrete label) and regression (predicting a continuous value).

• Lazy Learning: It is considered a "lazy" learner because the training cost is zero. It does not build an explicit model during a training phase; instead, it stores the entire dataset and performs computations only when making a prediction.

• Mechanism:

  • Classification: It identifies the $k$ nearest labeled data points to a new instance and assigns the label held by the majority of those neighbors.
  • Regression: It finds the $k$ nearest neighbors and calculates the average (or weighted average) of their target values to predict a continuous number.

• Missing Value Imputation: KNN can be used to fill in missing data. Unlike simple mean imputation (which distorts distributions), KNN finds similar rows (neighbors) and imputes the missing value based on them, providing a more realistic estimate.

The Hyperparameter 'k'

The choice of $k$ (the number of neighbors) is a critical hyperparameter that controls the model's behavior.

• Small k (e.g., k=1):
  • Decision Boundary: The boundary is highly complex, jagged, and "wiggly," following specific data points closely.
  • Voronoi Diagram: With $k=1$, the space is divided into regions (Voronoi cells) based on the closest single point. This is visible in nature, such as in the patterns on a giraffe's skin.
  • Overfitting: A small $k$ captures noise and outliers, leading to high model complexity and overfitting.
  • Bias/Variance: This results in Low Bias (very flexible) but High Variance (unstable; changing one training point significantly shifts the boundary).

This diagram illustrates a 1-Nearest Neighbor (1-NN) classifier, where new data points (squares) are assigned the class label of their single closest neighbor. The arrows indicate the specific nearest training point (red triangle or blue circle) that determines the classification for each test instance.

These plots demonstrate that as k increases, the decision boundary becomes smoother and less complex. This visualizes the transition from high variance (overfitting) at k=1 to high bias (underfitting) at higher k values.

• Large k:
  • Decision Boundary: The boundary becomes much smoother and ignores local fluctuations.
  • Underfitting: A very large $k$ oversimplifies the problem, potentially missing important patterns.
  • Bias/Variance: This results in High Bias (strong assumptions, overly smooth) but Low Variance (stable predictions).
• Extreme Case (k = N): If $k$ equals the total number of samples ($N$), the model predicts the majority class of the entire dataset for every single input, effectively ignoring the input features.
• Choosing k:

  • There is no analytical formula. It is determined by testing different values (tuning) to find a "sweet spot" that minimizes error on a validation set.

  • Rule of Thumb: A common starting point is:

    $k = \sqrt{N}$

  • Parity: It is typically better to choose an odd number for $k$ (e.g., 3, 5) to prevent tie votes in binary classification.

    

    This diagram illustrates splitting the dataset into three distinct parts: training, validation, and testing. The validation set is crucial for tuning hyperparameters (like k) to find the best model configuration before final evaluation.

Distance Metrics

KNN relies entirely on calculating the "distance" between points to determine similarity.

• Euclidean Distance: The straight-line distance between points. It is calculated as the square root of the sum of squared differences:

  $d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$

• Manhattan Distance: The distance measured along axes at right angles (like a taxi driving in a city grid). It is the sum of absolute differences:

  $d = |x_2-x_1| + |y_2-y_1|$

• Weights:

  • Uniform: All $k$ neighbors have an equal vote, regardless of how far away they are.
  • Distance-Weighted: Neighbors are assigned weights based on their distance (e.g., inverse distance). Closer neighbors contribute more to the decision than distant ones. This helps mitigate the effect of outliers included in the neighborhood.