kNearestNeighborsImputation

k-Nearest Neighbors (kNN) is a simple, instance-based learning method used for classification and regression. There is no explicit training phase beyond storing labeled training data; predictions are made by comparing a new instance to stored examples using distance in feature space.

To predict, choose a value of k and a distance metric (Euclidean distance is common; others include Manhattan and Minkowski). For a new instance, compute distances to all training samples, select the k closest, and aggregate their labels: classification by majority vote (ties may be resolved by various strategies); regression by averaging the target values of the neighbors, often with distance-based weighting.

kNN is a lazy learner and a non-parametric method, capable of modeling complex, non-linear decision boundaries given sufficient data. It requires feature scaling to ensure that features contribute proportionally to distances. It is straightforward to implement and handles multi-class classification naturally.

Disadvantages include high computational cost at prediction time and substantial storage requirements, since the entire training set must be retained. Performance can degrade with irrelevant or highly correlated features, and with imbalanced classes. The method also suffers in high-dimensional spaces due to the curse of dimensionality, where distances become less informative.

Common extensions involve distance weighting, cross-validation to select k, and dimensionality reduction to mitigate the curse of dimensionality. Efficient query structures such as KD-trees or Ball trees, or approximate nearest-neighbor methods, can speed up predictions for large datasets.

kNN finds use in pattern recognition, image and text classification, recommender systems, and anomaly detection, offering a simple baseline and a flexible, non-parametric approach to prediction.