How does KNN work if there are duplicates?

Question

I am currently debating with my friend about how KNN handles duplicates. Suppose K = 2, and we have a 1-dimensional set of data points to illustrate my dilemma

I = {1, 2, 2, 2, 2, 2, 6}

Thus is it correct to say that the K=2 nearest neighbours of data point 1 is simply {2, 2}? Also, same reasoning if we did the 2 nearest neighbours of data point 2 it would be {2, 2} as well not including itself?

Answer 1

Your reasoning is correct - you should consider duplicate points as separate. You can see that this must be the case in several ways:

1. Introduction of small random noise to the data should not affect the classifier on average. This would not be the case if you removed duplicates.

2. Suppose that your input space only has two possible values - 1 and 2, and all points "1" belong to the positive class while points "2" - to the negative. If you remove duplicates in the KNN(2) algorithm, you would always end up with both possible input values as the nearest neighbors of any point, and would have to predict a 50% probability for either class, which is certainly not a consistent classification strategy.

The extra question to think about is how to deal with the situation when you have different Y labels assigned to several points with the same X coordinate.

You could mix all classes together and say that the label of each point in the set of duplicates is represented by the distribution of labels in the whole set of points with that coordinate. Alternatively, you could simply sample K random points from the set.

Both strategies should result in a consistent classifier, however in the second case your predictions may not be deterministic. Most practical implementations (including, for example, sklearn.neighbors.KNeighborsClassifier), however, use this simpler, nondeterministic strategy, as it is perhaps slightly more straightforward.