KNN

A way to classify a data point based on its “similarity distance” to the $k$ nearest neighbors.

Topics

• Feature Normalization

Steps to Classify (based on this animation)

1. Initialize
   1. Place the data point in a feature space
2. Calculate Distance
   1. Find the Euclidean distance from the data point with all other labeled data
   2. May have to normalize data point values along different coordinates to be Z-scores for each coordinate
3. Sort Distance
   1. Sort distances of the data point with other labeled data points in increasing order
   2. For classification, the most common class of $k$-nearest neighbors determines the data point class
   3. For regression, use the average of the $k$-nearest neighbors’ labels

Choices of $k$

• Too small $k$
  • Results in overfitting of the model to the data
• Too large $k$
  • Results in underfitting

CS M146

${\text{nn}}_k(x)={\text{argmin}}_{n\in \left([N]-{\sum }_{i=1}^{k-1}{\text{nn}}_i(x)\right)}\Vert x-x_n{\Vert }_2^2$

• Gives the index in $[N]$ of the $k$th nearest neighbor of $x$, or the data point we’re interested in classifying
• $[N]$ is an array of indices for each data sample point
• We use the square of the L2 norm here to calculate distance but other measures could work

$\text{knn}(x)=\left\{{\text{nn}}_1(x),{\text{nn}}_2(x),\dots ,{\text{nn}}_K(x)\right\}$

• Gives the set of indices of the $K$ nearest neighbors to $x$

$v_c=\sum _{n\in \text{knn}(x)}\mathbb{I}(y_n==c)\forall c\in [C]$

• Gives the number of “votes” for a particular class/label $c$
• We iterate over each of the $K$-nearest neighbors and increment by one every time the neighbor equals the class of interest

$y=h(x)={\text{argmax}}_{c\in [C]}{v}_c$

• The prediction is the class $c$ that maximizes the number of votes

Training Time Complexity $O(1)$

• I don’t know why this isn’t $O(n)$, but spatial complexity definitely is $O(n)$

Classifying Time Complexity: $O(nd+n\log n)$

• To classify, we need to calculate the distances from our point to all of our $n$ data points, where calculating the distances scales linearly with the number of features $d$, which overall takes $O(nd)$ time. We must also sort these distances before finding the $K$-nearest neighbors, which takes $O(n\log n)$ time