k-Nearest neighbours

Main result of error rate analysis of k-NN regression

Nearest-neighbour classification

Nearest-neighbor methods: To get the prediction Ŷ for a point $x$, use [those observations ($k$ of them) in the training set T, closest in input space to point x]. Remember training set is a set of pairs $(x,y)$. Closest often refers to Euclidean distance.

Lecture about theoretical analysis and understanding of k-NN

Can alsu use for Regression KNN

It turns out that the effective number of parameters of k-nearest neighbors is $N/k$, even if technically there is only one parameter, $k$.

Interactive app: https://github.com/lettier/interactiveknn

Unbounded capacity but it generalizes at non-trivial rate. Indeed in Nonparametric statistics, overparametrization isn't incompatible with Generalization!

Of course, we need to assume something about the target function, typically Lipschitz continuity, but also other assumptions

Curse of dimensionality

–> To me it seems more like a method in Nonparametric statistics! Indeed it is (see Wiki).

Classification w/ K Nearest Neighbors Intro - Practical Machine Learning Tutorial with Python p.13

A KNN classifier with K=1 induces a Voronoi tessellation