Knn

K-Nearest Neighbors (KNN) is a simple, instance-based learning method used for classification and regression. It does not build an explicit model during training; instead, it stores the training data and makes predictions by comparing new instances to stored examples. In prediction, the algorithm identifies the k training samples closest to the query instance according to a chosen distance metric and aggregates their labels or values.

Common distance metrics include Euclidean, Manhattan, and Minkowski distances, and, for categorical features, Hamming distance. The choice of distance and the scale of features have a large impact on performance; therefore, data normalization or standardization is often essential so that features contribute comparably.

For classification, the prediction is typically the most frequent class among the k nearest neighbors (majority vote). Weighted variants assign each neighbor a weight inversely related to distance, so closer neighbors have more influence. For regression, the predicted value is usually the average (or sometimes a weighted average) of the neighbors’ target values.

Advantages include simplicity, no training phase, and the ability to model complex decision boundaries. Limitations include high prediction-time cost on large datasets, sensitivity to irrelevant or correlated features, and the curse of dimensionality. The choice of k is important: small k makes the model sensitive to noise, large k smooths the decision boundary.

To improve efficiency on larger datasets, spatial indexing structures such as KD-trees or Ball Trees can be used. Approximate nearest neighbor methods and hashing-based approaches offer faster but less exact searches. KNN is best suited for small to medium-sized problems or where a simple baseline is desired, and it is common to normalize features and validate k via cross-validation.