<aside> 💡 Remember that there isn't one correct value for $k$. Instead, our goal is to optimize our $k$ value such that the KNN model performs effectively on the task at hand.
</aside>
Our motivation for finding an optimal $k$ value is that if $k$ is too small, it will be too susceptible to outliers (as seen in Section 3.1). A larger value of $k$ usually works well, but one that's too large can be influenced by how many data points each label has. We can visualize this phenomenon below, where $k=3$ corresponds to the inner circle and $k=5$ corresponds to the outer circle.
Source: Wikipedia
Intuitively, it seems like the correct label for the new data point should be red. A KNN model with$k=3$ would correctly classify this new data point as red because two of its three closest neighbors are red while only one of its closest neighbors are blue. However, a KNN model with $k=5$ would instead classify the new data point as blue because the next two closest neighbors are blue. **Here, we can see that our KNN model was influenced by the fact that there are generally more blue points in the vicinity of our new data point, even though the new data point was closer to the area with red points.
Thus, we have a motivation to find a value of $k$ such that the KNN model isn't too susceptible to outliers and that it doesn't get influenced by the amount of data points each label has. An effective method to find an optimal value of $k$ is the elbow method, where we try all values of $k$ from 1-40. For each value of $k$, we will train a KNN model on the train set, create predictions on the test set, and store its error rate $(1-\text{accuracy})$. Then, we can use Matplotlib to plot a graph of error rate vs. $k$ value.
Source: Moussa Doumbia
Notice how our graph resembles an elbow, where there is initially a steep decline in the error rate, which then quickly begins to level off. We want to choose a $k$ value right before the error rate begins leveling off and fluctuating. In this example, a great choice would be 7. Make sure to not just choose a $k$ value that produces the lowest error rate despite being located in an area that fluctuates a ton, because that will likely cause overfitting.
All of the data we've been dealing with so far only have two features, thus we were able to just plot them all on a graph and visually find nearest neighbors. To find the distance between two data points $a$ and $b$, we can just use the distance formula we learned in school:
$$ D(a,b)=\sqrt{(a_x-b_x)^2+(a_y-b_y)^2} $$
But how can we do the same with higher dimensional data that we can't visualize? The most popular distance metric is Euclidian distance, which is just an extension of the distance formula for 2D points.
$$ D(a,b)=\sqrt{\sum^{n}_{i=1}(a_i-b_i)^2} $$
The only difference between the Euclidian distance function and the 2D distance function is that with Euclidian distance, there can be $n$ dimensions. Thus, for each dimension (or feature), we do the same as we would with the 2D distance function - find the difference between the values of the two points for that feature and square it. Finally, we take the square root of the sum of all the values we get.
Another popular distance metric is Manhattan distance, which simply takes the absolute differences between the values of the two points for each feature and sums them up:
$$ D(a,b)=\sum^{n}_{i=1} |x_i-y_i| $$
Here is a side by side comparison of the 2D version of each distance function:
Source: KDNuggets
