3
$\begingroup$

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 :)

$\endgroup$
  • 2
    $\begingroup$ Please add the [self-study] tag & read its wiki. Then tell us what you understand thus far, what you've tried & where you're stuck. We'll provide hints to help you get unstuck. We aren't going to simply answer your exam questions for you. $\endgroup$ – gung - Reinstate Monica Apr 3 '15 at 19:13
  • 1
    $\begingroup$ Done. I'm not really stuck, I simply needed to write how ties is resolved in my report, and was unable to find this information online. We are free to use any software at the exam, and I sure asking about missing documentation of the software used is well within the parameters of the exam :) $\endgroup$ – AllanLRH Apr 3 '15 at 21:47
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Seems like the sorting only happens for the brute-force approach, and not the tree-based method? BTW: nicely spottet, and nice that you included sources for you knowledge! $\endgroup$ – AllanLRH Apr 4 '15 at 13:09
  • $\begingroup$ I think the binary trees' query method returns sorted results already. $\endgroup$ – Dougal Apr 4 '15 at 21:34
1
$\begingroup$

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.

$\endgroup$

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.