KNN is an algorithm where the "Curse of Dimensionality" applies extremely literally and directly.

Let's take some kind of basic, 50/50 balanced, binary classification problem. I'm wondering if there's any commonly accepted "ball-park" figure of how many features/dimensions will make the KNN too sparse to be an effective predictive model?

Is there a way to do a back-of-the-envelope calculation for when the feature space becomes too sparse for a given number of data points?

For example, if I have 1,000 rows of data vs. 10,000 rows of data - can I calculate roughly how many features I could add before the data becomes too sparse for the algorithm to generate useful/good predictions?

Additional example: I was running binary classification KNN on about 7,000 data points, with 25 features. Interestingly, through cross validation, I found that a value of k=1 was the best choice. I found this strange. Is this indicative of an overly sparse feature space, so the model defaulting to finding the single nearest point was the best option?

  • 3
    $\begingroup$ Too sparse for what? Effective for what? Please edit to clarify. $\endgroup$
    – Sycorax
    Commented Feb 14, 2022 at 19:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.