How to manually draw a $k$-NN decision boundary with $k=1$ knowing the dataset

enter image description here

the labels are

enter image description here

and the euclidean distance between two points is defined as

enter image description here


This is a rather involved task. What to do from a high-level theoretical perspective might be easy to see, but it's difficult putting that into code from scratch.

Doing this in Python using existing libraries in not too complicated, though. See for example this tutorial or this StackOverflow post.


Theoretically, I would first plot (draw) the points from your dataset in a graph and then watch out for "decision points" half-way in between any two near-by points (from the dataset) from distinct classes.

For the next step, keep in mind those decision points. Given close-by data points from classes (e.g.) A and B, imagine a straight line connecting these two points from separate classes. Next, take the point half-way along that imaginary line (i.e. your decision point) and draw a "soft" line (maybe using pencil instead of pen) orthogonal/perpendicular to that imaginary line which intersects the imaginary line in the decision point. Do that for all combinations of "reasonably" close points from different classes.

Parts of the lines you have just drawn will define the final decision boundary. Next, think of each line as consisting of multiple elements, which are separated from one another by means of the points of intersection with other drawn lines. In other words, split lines into elements wherever they intersect other lines. Now, decide which of these elements to outline as the eventual decision boundary (finally using a pen instead of pencil). This step simply involves human intelligence and is difficult to describe. Whenever a line's element accurately separates (logically speaking) two classes, indicate it using a pen. Otherwise, if it does not contribute to separating two classes, don't indicate it.

After having indicated the final decision boundary using a pen, simply erase the pencil drawings. Now, you should be left with a decision boundary.

I hope this is clear and accurate enough.

  • $\begingroup$ The question is come from a old exam. So the decision boundaries can be drawn by hand. I am not even sure how to do it $\endgroup$ – David Oct 30 '20 at 18:05
  • $\begingroup$ Yes, I realized and corrected that already. I went through a few examples and encountered problems with the previous proposal indeed. $\endgroup$ – Daniel B. Oct 30 '20 at 19:18
  • 1
    $\begingroup$ ok now, thus I delete my answer. Hint: think about the problem as if each point was an independent class. After draw the perpendiculars, each point is enclosed by a convex polygon formed by these perperndiculars. This is the area the point "owns". Latter, just paint of same color the areas of points with same labels. $\endgroup$ – pasaba por aqui Oct 30 '20 at 19:26

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.