K-nearest neighbors complexity

Question

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?

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

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

$k$ = 5

$k$ = 10

$k$ = 20

---

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.figure()
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())
plt.show()