k-Nearest Neighbors (kNN)

k-Nearest Neighbors (kNN) is a non-parametric, instance-based learning algorithm. Unlike parametric models such as linear regression or logistic regression, kNN does not explicitly learn a mapping function from the training data during a training phase. Instead, it memorizes the training dataset and performs classification or regression on the fly when a new data point is presented. Because the computational work is deferred until the prediction phase, kNN is often referred to as a “lazy learning” algorithm.

The core principle of kNN is that similar data points exist in close proximity. To classify a new, unseen data point, the algorithm identifies the $k$ training examples that are closest to it in the feature space and assigns a label based on the majority class among those neighbors.

Classification of New Data Points

The kNN algorithm for classification follows these steps:

1. Calculate Distances: Compute the distance between the new data point and all points in the training dataset.
2. Identify Nearest Neighbors: Select the $k$ training points with the smallest calculated distances.
3. Determine the Majority Class: Count the class labels among the $k$ nearest neighbors. The new data point is assigned the class that appears most frequently (majority vote). In the case of a tie, the algorithm may resolve it randomly or weight the votes by the inverse of their distances.

Distance Metrics

The choice of distance metric fundamentally defines what it means for two data points to be “close.” Depending on the data type and dimensionality, different metrics are appropriate.

Euclidean Distance

The most common distance metric for continuous variables is the Euclidean distance, which represents the straight-line distance between two points in Euclidean space. For two vectors $\mathbf{x} = (x_1, x_2, \dots, x_n)$ and $\mathbf{y} = (y_1, y_2, \dots, y_n)$, the Euclidean distance is defined as:

$d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$

Manhattan Distance

Manhattan distance (also known as $L_1$ norm or city block distance) calculates the distance between two points by summing the absolute differences of their Cartesian coordinates. It is often preferred in high-dimensional spaces because it is less susceptible to the curse of dimensionality than Euclidean distance.

$d(\mathbf{x}, \mathbf{y}) = \sum_{i=1}^{n} |x_i - y_i|$

Minkowski Distance

Minkowski distance is a generalized metric that encompasses both Euclidean and Manhattan distances. It introduces a parameter $p$:

$d(\mathbf{x}, \mathbf{y}) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{\frac{1}{p}}$

When $p=1$, it is equivalent to the Manhattan distance, and when $p=2$, it reduces to the Euclidean distance.

The Hyperparameter $k$

The parameter $k$ represents the number of nearest neighbors considered during the voting process. It is a crucial hyperparameter that dictates the complexity and generalization capability of the model.

Impact of $k$

• Small $k$ (e.g., $k=1$): The model is highly sensitive to noise in the training data. The decision boundary becomes complex and jagged, leading to low bias but high variance (overfitting). With $k=1$, a new data point is assigned the exact class of its single closest neighbor.
• Large $k$: The voting process incorporates a broader region of the feature space, resulting in smoother, more robust decision boundaries. However, if $k$ is too large, the model may suffer from high bias (underfitting), as it risks simply predicting the majority class of the entire dataset regardless of the specific input location.

Even or Odd $k$

In binary classification problems (where there are only two possible classes), it is critical to choose an odd value for $k$. If an even $k$ is selected, there is a possibility of a tie in the majority voting process. An odd $k$ inherently prevents tied votes, ensuring a definitive class assignment for every new data point. For multi-class problems, ties can still occur with an odd $k$, but they are significantly less frequent.

The Importance of Scaling

kNN is highly sensitive to the scale of the features. Because the algorithm relies entirely on distance calculations, features with larger ranges will disproportionately influence the final distance metric.

Consider a dataset with two features: age (ranging from 18 to 80 years) and income (ranging from $20,000 to $150,000). If the Euclidean distance is calculated without scaling, the income feature will completely dominate the distance computation, rendering the age feature effectively irrelevant.

To prevent this, it is mandatory to normalize or standardize the data before applying kNN.

• Min-Max Scaling (Normalization): Rescales features to a fixed range, typically $[0, 1]$.
• Standardization (Z-score scaling): Transforms features to have a mean of 0 and a standard deviation of 1.

By ensuring all features contribute equally to the distance calculation, scaling significantly improves the performance and reliability of the kNN algorithm.

Exercise

Evaluate your understanding of kNN properties:

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (3rd ed.). O’Reilly Media.