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.

What is the KNN classification/regression procedure? Why is it called lazy learning? What actually happens at train time?

What errors come from too-small vs too-large K? How to choose K? How does distance weighting $w_i = 1/d(x, x_i)$ help?

What is the curse of dimensionality? Why do neighbors degenerate in high dimensions (relative distances converge)? Mitigations?

How does KNN differ from K-Means? Naive prediction complexity $O(nd)$ vs KD-Tree-accelerated inference?

Why is KNN sensitive to feature scaling? What preprocessing is required? Outputs for classification vs regression?