K-Nearest Neighbors Algorithm

Definition

Suppose $d_i(x):=d(x,X_i)$ is the distance between the training sample $X_i$ and the given point $x$. Let $d_{(1)}(x)\le d_{(2)}(x)\le \cdots \le d_{(n)}(x)$ $\underset{1\le k\le K}{\mathrm{argmax}}{\hat{f}}_k=\underset{1\le j\le K}{\mathrm{argmax}}{p}_j(x)=\underset{1\le j\le K}{\mathrm{argmax}}\frac{1}{k}\sum _{i=1}^{n}I(d_i(x)\le d_{(k)}(x))I(Y_i=j)$

The k-NN determines a sample’s class using the $k$-nearest training datum.

Facts

$k$ and $d$ are hyperparameters.