Optimal selection of k in K-NN

Question

I am currently reviewing some concepts related to Machine Learning, and I started to wonder about the hyperparameter selection of K-NN classifier.

Suppose you need to solve a classification task with a number of classes equal to M: I was thinking that the best choice for the parameter K of our classifier should be for K > M.

In this way, we are avoiding all the pathological cases in which a sample may be in the middle of all the M classes and then have a tie. For instance, consider the following example in which we have M=3 and each geometrical shape represents a class:

Assume that K<=M: for sure you will have a tie for a sample in the middle of samples 1, 2 and 3. This tie could be avoided if K > M.

Clearly this is just a toy example, but I think it is sufficient to illustrate my thoughts. I have tried to look for an answer but I wasn't able to find any resource mentioning this, am I wrong in some way or this reasoning may be sound?

Answer 1

Your idea isn't wrong, however in k-NN there always might be a case where you have the same number of votes for 2 or more classes (e.g. you have $k=6$ and you have 3 samples of one class vs 3 of another). With your solution you are just overcoming one very small case of ties and the $k$ that you choose might not be the optimal $k$ for classification, which is your primary objective (i.e. you might hurt your classification performance with a sub-optimal $k$ so that you don't get one type of ties).

Because there are also other times of ties, you always need to have a tiebreaker condition. I have seen a lot of strategies for this, like reducing $k$ by one until you break the tie, selecting the class with the minimum distance, selecting the class with the fewest samples overall, etc.

Since you already have such a condition, you could also handle your situation, without selecting a sub-optimal $k$.

Answer 2

As I was playing with this problem, Djib just wrote an answer which is certainly better than whatever I could have come up with. To illustrate Djib's point, here is a small demonstration that as soon as there are more than 2 classes there's no value of $k$ which guarantees the absence of tie (except if $k=1$ of course).

By definition we have $k=|c_1| + |c_2| + ... + |c_n|$, where $|c_i|$ is the number of instances for the class $c_i$. Let $|c_1|\geq |c_2|$ be the number of instances for the top two classes. A tie is when (at least) the top two classes have the same number of instances: $|c_1| = |c_2|$ (it doesn't matter when there is a tie which is not at the top).

It's easy to prove that for any integer $k>1$, there are always two integers $a\geq b\geq 0$ such that $2a+b=k$: if $k$ is even, pick $a=k/2$ and $b=0$. If $k$ is odd, pick the integer part of $k/2$ as $a$ and $b=1$.

So for any $k$ it's always possible to find $a\geq b\geq 0$ such that $|c_1|=|c_2|=a$ and $|c_3|=b$. Therefore it's always possible to have a tie at the top of the ranking of at least 3 classes in $k$-NN, whatever the value of $k$.

Example with 3 classes and $k=4$ (note that $k>M$): a tie happens when $|c_1|=|c_2|=2$ and $|c_3|=0$.

Answer 3

To add a couple of references, to the already good answers, on the problem of selecting the optimum $k$ for $k-NN$.

1. How to find the optimal value of K in KNN?

Then how to select the optimal K value?

• There are no pre-defined statistical methods to find the most favorable value of K.
• Initialize a random K value and start computing.
• Choosing a small value of K leads to unstable decision boundaries.
• The substantial K value is better for classification as it leads to smoothening the decision boundaries.
• Derive a plot between error rate and K denoting values in a defined range. Then choose the K value as having a minimum error rate.

2. K-nearest neighbors algorithm, Parameter selection

The best choice of k depends upon the data; generally, larger values of k reduces effect of the noise on the classification, but make boundaries between classes less distinct. A good k can be selected by various heuristic techniques (see hyperparameter optimization). The special case where the class is predicted to be the class of the closest training sample (i.e. when k = 1) is called the nearest neighbor algorithm.

The accuracy of the k-NN algorithm can be severely degraded by the presence of noisy or irrelevant features, or if the feature scales are not consistent with their importance. Much research effort has been put into selecting or scaling features to improve classification. A particularly popular[citation needed] approach is the use of evolutionary algorithms to optimize feature scaling. Another popular approach is to scale features by the mutual information of the training data with the training classes.

In binary (two class) classification problems, it is helpful to choose k to be an odd number as this avoids tied votes. One popular way of choosing the empirically optimal k in this setting is via bootstrap method.

3. Optimal choice of k for k-nearest neighbor regression

The k-nearest neighbor algorithm (k-NN) is a widely used non-parametric method for classification and regression. We study the mean squared error of the k-NN estimator when k is chosen by leave-one-out cross-validation (LOOCV). Although it was known that this choice of k is asymptotically consistent, it was not known previously that it is an optimal k. We show, with high probability, the mean squared error of this estimator is close to the minimum mean squared error using the k-NN estimate, where the minimum is over all choices of k.