KNN & K Selection

K-nearest neighbors (KNN) is a non-parametric lazy-learning algorithm: training only stores the data (zero training cost); at prediction time it finds the $K$ closest training samples to the input — majority voting for classification, mean for regression.Distance-weighted voting often improves robustness: $w_i = \tfrac{1}{d(x, x_i)}$ or $w_i = \tfrac{1}{d(x, x_i)^2}$, giving nearby neighbors more say; the decision boundary is set by the training points' Voronoi regions.Too-small K → high-variance overfitting (a single neighbor decides), too-large K → high-bias underfitting (distant classes intrude); cross-validation picks K.Curse of dimensionality: in high dimensions samples are sparse, all pairwise distances converge, the relative spread $d_{\max} - d_{\min}$ collapses, neighbors are almost equidistant and discrimination degrades toward random — mitigated by dimensionality reduction or feature selection.

classification/regression baselines on small, low-dimensional data, recall stage of recommendation/retrieval, interpretable online prediction; interviews focus on why KNN fails in high dimensions and on complexity analysis.

no training, non-parametric decision surfaces, incremental updates, and per-sample explanations; the catch is that all computation is deferred to prediction — naive inference costs $O(nd)$, reduced to $O(\log n)$ scale in low dimensions via KD-Tree/Ball-Tree but degrading to a linear scan in high dimensions; it is also scale-sensitive and requires z-score standardization first, otherwise large-magnitude features dominate the distance.

Test Your Knowledge: Practice Questions for "KNN & K Selection"

Single choice pitfall questions with instant feedback and mistake tracking.