k-Nearest Neighbors

What is KNN:

Supervised learning algorithm for classification.

Some assumptions:

• Real world data will not be this nice
• Assuming that the features that we extracted to represent data are good, we can assume that there will be some form of clustering for each class. More formally, Given $X=\{x_1,x_2....x_n\}$ and $Y=\{y_1,y_2,y_3,y_4....y_k\}$, we can distribute X such that: $X^{\{y_1\}}\cup X^{\{y_2\}}\cup X^{\{y_3\}}....X^{\{y_k\}}=X$ and $X^{\{y_i\}}\cap X^{\{y_j\}}=\varnothing ,\text{for }i\ne j$
  Meaning: All points must be clustered and no point can be clustered to more than one class

Visualize the data

Task

Image you are given data D = ($x_i$ , $y_i$) where $x\in R^n$ and $y\in N$, Can you find the value of y for a new arbitrary test point $x_t$ (in black)

Training (sort of)

Intuitively:

• At every new data point, we ask “Which are the closest k points to this”
• Then, we predict the label by looking at those k things and seeing which y shows up the most
• If everything is tied, just take the closest one

Given a new test point $x_t\in {\mathbb{R}}^n$, we can predict the label ( y_t ) by:

• Compute the Euclidean distance between ( x_t ) and each ( x_i ) in the D: $d(x_t,x_i)=\Vert x_t-x_i{\Vert }_2$
• Identify the k nearest neighbors by selecting the k smallest distances:$\{d(x_t,x_1),d(x_t,x_2),\dots ,d(x_t,x_{i_k})\}$ where $1,2,\dots ,k$ correspond to the indices of the nearest neighbors
• Predict the label $y_t$ by majority voting among the labels of the ( k ) nearest neighbors: $y_t=\arg {\max }_{y\in \mathbb{N}}\left({\sum }_{j=1}^k\mathbb{I}(y_j=y)\right)$ where $\mathbb{I}$ is the indicator function: $\mathbb{I}(y_j=y)=\{\begin{array}{ll}1,& \text{if }{y}_j=y\\ 0,& \text{otherwise.}\end{array}$

Note for ties: If there is a tie among labels, select the label with the closest distance to $x_t$ Formally, let $Y_{\text{tie}}\subseteq \mathbb{N}$ be the set of labels tied for the majority vote. Then: $y_t=\arg {\min }_{y\in Y_{\text{tie}}}{\min }_{j\in \{1,2,\dots ,k\},y_j=y}d(x_t,x_j)$

Example here: I created a meshgrid and predicted every point on it. The graph contours should what label would be predicted if the data point existed at (x, y)

I was playing around with different looking inputs and trying to see the boundaries. It was fun. I deployed it here if you want to do the same: https://knn-implementation.onrender.com/ Pls don’t abuse. This runs on a free tier, and is very slow. If it does not load, wait for a minute till it spins up again lol