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

If k = 1, then the object is simply assigned to the class of that single nearest neighbor.
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.
If k=4, and the class labels are Good =2 Bad=2, What will be the class label?

score 2 · Accepted Answer · answered Jan 20 '15 at 13:50

2

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.

answered Jan 20 '15 at 13:50

Alper

12,860
2
31
41

Yes, that is one way of doing it. – Alper Jan 21 '15 at 08:17

score 1 · Answer 2 · answered Jan 20 '15 at 21:17

1

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.

answered Jan 20 '15 at 21:17

Has QUIT--Anony-Mousse

76,138
12
138
194

How can we choose that at random? – USB Jan 21 '15 at 03:27
Pick a random one of those that are maximal. – Has QUIT--Anony-Mousse Jan 21 '15 at 07:44
@HasQUIT--Anony-Mousse the easiest way is to implement function like here - https://stackoverflow.com/a/84747/2047418 – Filip Bartuzi Jun 20 '20 at 15:54

KNN choosing class label when k=4

2 Answers2