K-Nearest Neighbors (KNN) is a method belonging to a category called instance-based learning. In this case, there's no parametrized model, but rather a rearrangement of the samples in order to speed up specific queries. In the simplest case (also known as brute-force search), let's say we have a dataset X containing M samples xi ∈ ℜN. Given a distance function d(xi, xj), it's possible to define the radius neighborhood of a test sample xi as:
The set ν(xi) is a ball centered on xi and including all the samples whose distance is less or equal to R. Alternatively, it's possible to compute only the top k nearest neighbors, which are the k samples closer to xi (in general, this set is a subset of ν(xi), but the opposite condition can also happen when k is very large). The procedure is straightforward but, unfortunately...
