2
$\begingroup$

I found that often used rule of thumb for k equals the square root of the number of points in the training data set in kNN.

In my problem I have 300 features of 1000 users and I use 10 fold cross validation.

Can someone tell me what value I should consider to obatin the square root? is it 300 or 1000?

$\endgroup$
  • $\begingroup$ 1000 is the number of your points. You may want to understand the term curse of dimensionality before you start implementing. Once you understood the concept you may want to review your model and think about why this cannot work. $\endgroup$ – cel Nov 25 '15 at 7:53
  • $\begingroup$ @cel Do you think kNN is not appropriate for my problem? :) $\endgroup$ – Volka Nov 25 '15 at 9:36
2
$\begingroup$

Since you have 300 of features the kNN method is doomed - the curse of dimensionality. The issue is that with so many dimensions any data point is actually closer to the border of your feature space than to any other point (i.e. all of the points are not 'close' to each other at all). So for such high-dimensional problems you either need much MUCH more data points to overcome the curse of dimensionality or reduce the number of dimensions in your problem (number of features) or just use other algorithm.

More generally, if you need to decide which K you'd better use in current problem - try to plot the test error on test set as a function of K. Look for an elbow in this plot (the moment when increase of K not makes the test error significantly better). This is your optimal K.

$\endgroup$
  • $\begingroup$ But I can reduce the number of features by using a feature selection. Then would it be a problem? :) $\endgroup$ – Volka Nov 25 '15 at 9:36
  • $\begingroup$ Well, if you use for example a PCA to reduce number of features to something like 5 dimensions and have 3000 of data points - it should work. I suggest you to read more about the theory behind this issue, you could find it here: math.stackexchange.com/questions/346775/… $\endgroup$ – Maksim Khaitovich Nov 25 '15 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy