Introduction

K-nearest neighbors (KNN) is a popular lazy learning algorithm used for classification and regression tasks. The algorithm functions by identifying the K-nearest data points to a new observation and making decisions based on the majority class for classification or the average for regression. The choice of the parameter K is crucial, as it influences both the model's performance and complexity. One might intuitively believe that reducing K would inherently simplify the model by focusing on fewer data points. However, a smaller K can actually increase the complexity of the model in various ways.

Understanding K in KNN

K in KNN refers to the number of nearest neighbors considered when making a prediction:

• K = 1: The prediction is made purely based on the closest single neighbor.
• Higher K: The prediction is more of a local average of K closest data points.

Choosing the optimal K involves a trade-off between bias and variance. A small K leads to low bias and high variance, while a large K increases bias but reduces variance.

Effect of Decreasing K on Complexity

1. Overfitting with Small K:
   • With a smaller K, particularly K = 1, the model becomes very sensitive to the noise in the dataset.
   • Each data point's class can disproportionately influence the decision boundary.
   • This increased sensitivity results in a highly complex model that may fit the training data perfectly but performs poorly on unseen data due to overfitting.
2. Decision Boundary Complexity:
   • In the case of K=1, the decision boundaries can become overly intricate and fragmented, essentially forming a Voronoi tessellation of the feature space.
   • This can be mathematically conceptualized using concepts from topology and geometry where a smaller K results in highly non-linear and complex decision boundaries, making the model potentially unstable on future data.
3. Computational Complexity:
   • While computational complexity of finding the K-nearest neighbors remains $O(n \cdot d)$ where $n$ is the number of training samples and $d$ is the number of dimensions, smaller K might require finer evaluation over distances, leading to increased computational challenges, especially in high-dimensional spaces.
4. Impact of Noisy Data:
   • With fewer neighbors averaged together, the prediction becomes more sensitive to outliers.
   • If an outlier is one of the nearest neighbors, it can unduly influence the class assigned to a particular region of the feature space.

Practical Example

Consider a simple two-dimensional binary classification task where data points from two classes are scattered around two means. With K = 5, the KNN decision boundary between classes is reasonably smooth and consistent, reflecting the natural boundary between the two centroids. When K is reduced to 1, each point becomes a potential boundary point, leading to erratic and wiggly boundaries that map directly to data noise rather than true class separation.

Summary Table

The table below summarizes the effects of decreasing K in KNN:

Conclusion

While a smaller K in K-nearest neighbors may seem to simplify the model by focusing on fewer data points, it can lead to increased complexity in the form of higher variance, overfitting, more erratic decision boundaries, and greater sensitivity to noise. The choice of K should therefore be carefully considered in the context of the specific data and the application, ideally using techniques such as cross-validation to find the optimal balance between bias and variance.