Nearest-Neighbor Method

Let’s say we have a sample set $S_N=\left\{\begin{array}{c}(x_1,{\theta }_1,\dots ,(x_N,{\theta }_N)\end{array}\right\}$ and $x_i$ is the sample while ${\theta }_i=\left\{\begin{array}{c}1,2,\dots ,c\end{array}\right\}$.

We want to measure the distance (let’s say, using Euclidean distance):

$$\delta (x_i,x_j)=\Vert \begin{array}{c}{x}_i-x_j\end{array}\Vert$$

And so, the nearest neighbor decision is

$$\text{If δ(x,x′)=minj=1,…,Nδ(x,xj)∩ω(x′)=θ′ then ω1^(x)=θ′}$$

Note here that $\omega (x)$ is the ground truth class of $x$, while $\hat{\omega }(x)$ is the predicted class of $x$.

Nearest-Neighbor

We find the nearest value ($x^{\prime }$) to our target value $x$. Then, we copy whatever is the label of $x^{\prime }$ to $x$.

Some questions that you may have:

1. What distance to use?
2. How many samples should we base it on, data could be too noisy.