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?


3 Answers 3


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$ Feb 2, 2021 at 21:09
  • $\begingroup$ This would be a valuable comment under my answer. I already tried to state this problem in my last sentence: There is one logical assumption here by the way... $\endgroup$
    – gunes
    Feb 2, 2021 at 21:23
  • $\begingroup$ Aha yes I initially tried to comment under your answer but did not have the reputation to do so, apologies! $\endgroup$ Feb 2, 2021 at 21:30

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 Reference

  • 1
    $\begingroup$ Reference link seems broken $\endgroup$
    – gunes
    May 28, 2021 at 10:05
  • 1
    $\begingroup$ Could you add some identifying information to the reference, like author names and title of the paper? The sci-hub link may die and the reference would become unidentifiable. $\endgroup$
    – Tim
    May 28, 2021 at 10:07
  • $\begingroup$ 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 $\endgroup$ Jun 26, 2021 at 10:56
  • $\begingroup$ I fixed the link $\endgroup$ Jun 26, 2021 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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