KNN choosing class label when k=4

Question

In k-NN classification, the output is a class membership. An object is classified by a majority vote of its neighbors, with the object being assigned to the class most common among its k nearest neighbors (k is a positive integer, typically small).

1. If k = 1, then the object is simply assigned to the class of that single nearest neighbor.
2. If k=3, and the class labels are Good =2 Bad=1,then the predicted class label will be Good,which contains the majority vote.
3. If k=4, and the class labels are Good =2 Bad=2, What will be the class label?

Answer 1

There are different approaches. For example Matlab uses 'random' or 'nearest' as documented here.

When classifying to more than two groups or when using an even value for k, it might be necessary to break a tie in the number of nearest neighbors. Options are 'random', which selects a random tiebreaker, and 'nearest', which uses the nearest neighbor among the tied groups to break the tie.

Answer 2

This problem is not specific to k=4.

Consider a data set with 3 classes. At k=2, two different classes may arise. At k=3, three different classes may arise, at k=4, it may be 0,2,2... any k beyond 1 bears the risk of a tie.

Choose one at random, or use weighting (i.e. give the 1NN more weight than the 2nd nearest neighbor etc.) to further reduce the risk of ties.