Training error in KNN classifier when K=1

Question

I got this question in a quiz, it asked what will be the training error for a KNN classifier when K=1. What does training mean for a KNN classifier? My understanding about the KNN classifier was that it considers the entire data-set and assigns any new observation the value the majority of the closest K-neighbors. Where does training come into the picture? Also the correct answer provided for this was that the training error will be zero irrespective of any data-set. How is this possible?

Answer 1

Training error here is the error you'll have when you input your training set to your KNN as test set. When K = 1, you'll choose the closest training sample to your test sample. Since your test sample is in the training dataset, it'll choose itself as the closest and never make mistake. For this reason, the training error will be zero when K = 1, irrespective of the dataset. There is one logical assumption here by the way, and that is your training set will not include same training samples belonging to different classes, i.e. conflicting information. Some real world datasets might have this property though.

Answer 2

For a visual understanding, you can think of training KNN's as a process of coloring regions and drawing up boundaries around training data.

We can first draw boundaries around each point in the training set with the intersection of perpendicular bisectors of every pair of points. (perpendicular bisector animation is shown below)

gif source

To find out how to color the regions within these boundaries, for each point we look to the neighbor's color. When $K=1$, for each data point, $x$, in our training set, we want to find one other point, $x'$, that has the least distance from $x$. The shortest possible distance is always $0$, which means our "nearest neighbor" is actually the original data point itself, $x=x'$.

To color the areas inside these boundaries, we look up the category corresponding each $x$. Let's say our choices are blue and red. With $K=1$, we color regions surrounding red points with red, and regions surrounding blue with blue. The result would look something like this:

Notice how there are no red points in blue regions and vice versa. That tells us there's a training error of 0.

Note that decision boundaries are usually drawn only between different categories, (throw out all the blue-blue red-red boundaries) so your decision boundary might look more like this:

Again, all the blue points are within blue boundaries and all the red points are within red boundaries; we still have a test error of zero. On the other hand, if we increase $K$ to $K=20$, we have the diagram below. Notice that there are some red points in the blue areas and blue points in red areas. This is what a non-zero training error looks like.

When $K = 20$, we color color the regions around a point based on that point's category (color in this case) and the category of 19 of its closest neighbors. If most of the neighbors are blue, but the original point is red, the original point is considered an outlier and the region around it is colored blue. That's why you can have so many red data points in a blue area an vice versa.

images source

Answer 3

In the KNN classifier with the k= 1 and with infinite number of training samples, the minimum error is never higher than twice the of the Bayesian error

Detecting moldy Bread using an E-Nose and the KNN classifier Hossein Rezaei Estakhroueiyeh, Esmat Rashedi Department of Electrical engineering, Graduate university of Advanced Technology Kerman, Iran

Answer 4

Sorry to be late to the party, but how does this state of affairs make any practical sense?

In practice you often use the fit to the training data to select the best model from an algorithm. So we might use several values of k in kNN to decide which is the "best", and then retain that version of kNN to compare to the "best" models from other algorithms and choose an ultimate "best". But under this scheme k=1 will always fit the training data best, you don't even have to run it to know. Regardless of how terrible a choice k=1 might be for any other/future data you apply the model to.

The obvious alternative, which I believe I have seen in some software. is to omit the data point being predicted from the training data while that point's prediction is made. So when it's time to predict point A, you leave point A out of the training data. I realize that is itself mathematically flawed. But isn't that more likely to produce a better metric of model quality?