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?


4 Answers 4


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.

  • $\begingroup$ It is important to note that gunes' answer implicitly assumes that there do not exist any inputs in the training set where $(x_i,y_i)$ and $(x_j,y_j)$ where $x_i = x_j$ but $y_i != y_j$, in other words not allowing inputs with duplicate features but different classes). $\endgroup$ Commented Feb 2, 2021 at 21:09
  • $\begingroup$ @KareemSayed thanks for your input. I mentioned this in the last two sentences. $\endgroup$
    – gunes
    Commented Jul 24, 2023 at 17:54

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)

perpendicular bisector animation

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:

k=1 with all boundaries

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:

enter image description here

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.

enter image description here

images source


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


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?

  • 1
    $\begingroup$ As it's written, it's unclear if this is intended to ask a new question or answer OP's original question. I think that it could be made clearer if instead of using rhetorical questions, you edit to directly address OP's stated question. $\endgroup$
    – Sycorax
    Commented Jan 8, 2023 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.