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?
