# Choosing optimal K for KNN

I performed a 5-fold CV to select the optimal K for KNN. And it seems like the bigger K gets, the smaller the error...

Sorry I didn't have a legend, but the different colors represent different trials. There are 5 total and it seems like there's little variation between them. Error always seems to decrease when K gets larger. So how can I choose the best K? Would K = 3 be a good choice here because the graph kind of levels off after K = 3?

• What are you going to do with the clusters once you've found them? Ultimately it's what you're going to do with the clusters produced by your clustering algorithm that will help to determine whether using more clusters to get a small error is worth while. – Brian Borchers Nov 30 '14 at 23:58
• I want high predictive power. In this case...should I go with K = 20? Since it has the lowest error. However, I actually plotted the errors for K up to 100. And 100 has the lowest error of all...so I suspect that error will decrease as K increases. But I don't know what's a good cut off point. – YQC Dec 1 '14 at 1:41

## 3 Answers

If you carry on going, you will eventually end up with the CV error beginning to go up again. This is because the larger you make $k$, the more smoothing takes place, and eventually you will smooth so much that you will get a model that under-fits the data rather than over-fitting it (make $k$ big enough and the output will be constant regardless of the attribute values). I'd extend the plot until the CV error starts to go noticably up again, just to be sure, and then pick the $k$ that minimizes the CV error. The bigger you make $k$ the smoother the decision boundary and the more simple the model, so if computational expense is not an issue, I would go for a larger value of $k$ than a smaller one, if the difference in their CV errors is negligible.

If the CV error doesn't start to rise again, that probably means the attributes are not informative (at least for that distance metric) and giving constant outputs is the best that it can do.

Why not choose $K=17$? It looks like the CV error goes down until then and flattens out afterwards. If all you care about is predictive accuracy then I would not choose $K=3$ because it looks pretty clear that you can do better.

Is there any physical or natural meaning behind the number of clusters? If I am not wrong, it is only natural that as K increases, error decreases - kind of like overfitting. Rather than fishing for the optimal K, its probably better to pick K based on domain knowledge or some intuition?

• I think this answer would be more appropriate for k-means clustering rather than k-nn classification or regression. – Dikran Marsupial Dec 1 '14 at 10:20
• If k is too large, you are under-fitting it then the error will go up again. – James LT Nov 4 '18 at 17:16