Machine learning basics (part 11): Nearest neighbor searching

Foundation of nearest neighbors

At first, let us look at the theoretical background (in a simplified way) on the probabilistic basis. Suppose we place a region of volume V and x is a vector representing the case for which k nearest neighbors are searched for. V is the volume of the variable space comprising all training cases. Let us assume that searching for neighbors yields k cases (samples, examples or observations), k_i of which are from class c_i .

Algorithm: Nearest neighbor search