Why does choosing $k=\sqrt{n}$ in $k$-nearest neighbors not work well when the data are very noisy?

Question

I am making a system that outputs an estimate using some data input (think speech recognition). When testing my solution, I find that low values of knn work very well for data with low "noise" and badly for data of high "noise", however, high values of knn work very well for data with high "noise" but badly for data of low "noise", where high "noise" is akin to a crowded room and low "noise" is akin to one person speaking clearly.

Ideally, I would implement a system that would figure out an estimated best k value to use depending on the number of unique neighbours. I know that k is generally set to the square root of the number of data points, however, my results show that there is no one right value of k to use. I am simply assuming that this is something to do with the number of unique neighbours, however, I can't get my head round the reason as to why this is.

Answer 1

Using $k = \sqrt n$ is a rule of thumb. This means that this is a solution that worked reasonably well for many cases but gives you no guarantees to work for your problem. To pick the value of $k$ you need to conduct proper hyperparameter tuning. This is not something that depends on the number of samples themselves and cannot be calculated from the sample size. As you noticed, the number of neighbors is related to overfitting, so to the noisiness of the data--this does not have much to do with sample size. If you want to guess it only based on the sample size, you can only use rules of thumb like the one above, which sometimes would work and sometimes not.

Answer 2

Try to look at the features that are giving you good accuracy for various data sets, based on recursive feature elimination procedure. This might give you an idea on the possible set of features that will work in different scenarios.