Why does the complexity of KNearest Neighbors increase with lower value of k? And when does the plot for k-nearest neighbor have smooth or complex decision boundary? Please explain in detail.

And also , given a data instance to classify, does K-NN compute the probability of each possible class using a statistical model of the input features or just gets the class with the most number of points in favour of it?


1 Answer 1


The complexity in this instance is discussing the smoothness of the boundary between the different classes. One way of understanding this smoothness complexity is by asking how likely you are to be classified differently if you were to move slightly. If that likelihood is high then you have a complex decision boundary.

For the $k$-NN algorithm the decision boundary is based on the chosen value for $k$, as that is how we will determine the class of a novel instance. As you decrease the value of $k$ you will end up making more granulated decisions thus the boundary between different classes will become more complex.

You should note that this decision boundary is also highly dependent of the distribution of your classes.

Let's see how the decision boundaries change when changing the value of $k$ below. We can see that nice boundaries are achieved for $k=20$ whereas $k=1$ has blue and red pockets in the other region, this is said to be more highly complex of a decision boundary than one which is smooth.

First let's make some artificial data with 100 instances and 3 classes.

from sklearn.datasets.samples_generator import make_blobs
X, y = make_blobs(n_samples=100, centers=3, n_features=2, cluster_std=5)

Let's plot this data to see what we are up against

enter image description here

Now let's see how the boundary looks like for different values of $k$. I'll post the code I used for this below for your reference.

$k$ = 1

enter image description here

$k$ = 5

enter image description here

$k$ = 10

enter image description here

$k$ = 20

enter image description here

The code

The code used for these experiments is as follows taken from here

from sklearn import neighbors

k = 1
clf = neighbors.KNeighborsClassifier(20)
clf.fit(X, y)

from matplotlib.colors import ListedColormap
import matplotlib.pyplot as plt

cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])

# Plot the decision boundary. For that, we will assign a color to each
# point in the mesh [x_min, x_max]x[y_min, y_max].
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])

# Put the result into a color plot
Z = Z.reshape(xx.shape)
plt.pcolormesh(xx, yy, Z, cmap=cmap_light)

# Plot also the training points
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold)
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
  • $\begingroup$ "You should note that this decision boundary is also highly dependent of the distribution of your classes." - While saying this are you meaning that if the distribution is highly clustered, the value of k -won't effect much? Since k=1 or k=5 or any other value would have similar effect. $\endgroup$
    – aspiring1
    Oct 19, 2018 at 7:31
  • $\begingroup$ That's right because the data will already be very mixed together, so the complexity of the decision boundary will remain high despite a higher value of k. $\endgroup$
    – JahKnows
    Oct 20, 2018 at 16:22

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.