How does Scikit Learn resolve ties in the KNN classification?

Question

I have a multi-class classification problem, in which I'm using Scikit Learn's k nearest neighbour classifier, (5 classes), which means that an odd number for k won't prevent classification ties.

So how does Scikit Learn resolve ties in the k nearest neighbour classification? I can't seem find this anywhere in the internet.

I need this for an exam assignment, so quick answers, if possible with a source of your knowledge, is much appreciated :)

Answer 1

From the documentation for KNeighborsClassifier:

Warning: Regarding the Nearest Neighbors algorithms, if it is found that two neighbors, neighbor k+1 and k, have identical distances but but different labels, the results will depend on the ordering of the training data.

To get exactly what happens, we'll have to look at the source. You can see that, in the unweighted case, KNeighborsClassifier.predict ends up calling scipy.stats.mode, whose documentation says

Returns an array of the modal (most common) value in the passed array.

If there is more than one such value, only the first is returned.

So, in the case of ties, the answer will be the class that happens to appear first in the set of neighbors.

Digging a little deeper, the used neigh_ind array is the result of calling the kneighbors method, which (though the documentation doesn't say so) appears to return results in sorted order. So ties should be broken by choosing the class with the point closest to the query point, but this behavior isn't documented and I'm not 100% sure it always happens.

Answer 2

This answer is just to show with a brief example how sklearn resolves the ties in kNN choosing the class with lowest value:

from sklearn.neighbors import KNeighborsClassifier
import numpy as np

# We start defining 4 points in a 1D space: x1=10, x2=11, x3=12, x4=13
x = np.array([10,11,12,13]).reshape(-1,1)   # reshape is needed as long as is 1D

# We assign different classes to the points
y = np.array([0,1,1,2])

# we fit a 2-NN classifier
knn = KNeighborsClassifier(n_neighbors=2 , weights='uniform')
knn.fit(x, y)

# We try to predict samples with 5 and 15 values (it will be a tie in both cases) 
x_test=np.array([5,15]).reshape(-1,1)
pred = knn.predict(x_test)
print(pred)

#[0 1]

We see how the tie is resolved assigning not the closest neighbor's value but the lowest class value.