k-NN -- The Nearest Neighbor

Let us assume we have sets $D_i$, these represent $c$ classes, $k>0$ and test sample $\mathbf{x}$. We want to classify $\mathbf{x}$ as a member of one of classes $D_i$, k-NN does this very simply (figure 3.13 on page ):

• find $k$ closest vectors to test vector $\mathbf{x}$, let these are $\mathbf{r_1},\dots,\mathbf{r_k}$
• make a hypercycle $C_n$ around $\mathbf{x}$ with radius $r$, $r=\max_{i=1,\dots,k}{\vert\mathbf{r_i}\vert}$
• classify $\mathbf{x}$ as $D_i$: $S_i \subseteq D_i$ $S_i=argmax_{R_i} \vert R_i\vert$ $R_i = \{\mathbf{r_i}: \vert\vert\mathbf{r_i} - \mathbf{x}\vert\vert \leq r \land \mathbf{r_i} \in D_i\}$

The last step says: classify input vector $\mathbf{x}$ as the member of the class which has the majority in hypercycle $C_n$.

Figure 3.13: Classification using k-NN, $k=3$. The test sample T is being classified as $\times$, because in the hypercycle surrounding T are 2 elements from $\times$ and only one from $\circ$.

The special case of k-NN is 1-NN, where we are classifying sample $\mathbf{x}$ as the closest vector to $\mathbf{x}$.

The very important thing here is the metric used to find the closest vectors. This was discussed in section Error Function.