Knn Decision boundary I am new to machine learning and trying to draw decision boundary for k nearest neighbor where k=3. I know that the decision boundary for k=1 would be the perpendicular bisector between two different classes. But how do I draw the decision boundary for k>=3. 
 A: Here's an easy way to plot the decision boundary for any classifier (including KNN with arbitrary $k$). I'll assume 2 input dimensions.


*

*Train the classifier on the training set.

*Create a uniform grid of points that densely cover the region of input space containing the training set.

*Classify each point on the grid. Store the results in an array $A$, where $A_{ij}$ contains the predicted class for the point at row $i$, column $j$ on the grid.

*Plot the array as an image, where each pixel corresponds to a grid point and its color represents the predicted class. The decision boundary can be seen as contours where the image changes color.

*The coordinates and predicted classes of the grid points can also be passed to a contour plotting function (e.g. contour() or contourf() in python or matlab). This will plot contours corresponding to the decision boundary.
For example, the contour plot on the right shows the result of this procedure, after fitting a KNN classifier ($k=25$) to the spiral dataset on the left:

A: For 3 points, the boundary (also called the Voronoi diagram) is formed by taking the triangle on these points and drawing the perpendicular bisectors. Classical geometry tells us that they will intersect at a single point, which is equivalently the center of the circumscribed circle. So just extend the blue lines below to get the region. 

For an arbitrary number of points, there are efficient algorithms to draw the boundary that are usually at worst $O(n\log n)$. See here:
https://dccg.upc.edu/people/vera/wp-content/uploads/2013/06/GeoC-Voronoi-algorithms.pdf
