1
$\begingroup$

How do I implement nested K-fold cross-validation when it comes to k-Nearest Neighbours?

Let's say I built a kNN classifier, and used K-Fold CV to tune the hyper-parameter. Now, how do I use nested K-Fold CV? I have read multiple articles, but they don't explain it well enough (esp. in the case of kNN).

From my understanding, in nested CV:

I do K-Fold CV with K = 5 and k = 1, for example, on the training data and see the mean error rate. Then I do CV again with K = 10, for example, and k = 1, and then I do it again, with K = 15, for example, and k = 1, and so on, for multiple values of K.

Then I repeat the whole thing for k = 2, and so on, for multiple values of k.

In the end, I can use the data to plot a graph to see the what the mean error rate is with multiple values of k and for multiple values of K. So the X axis = k values, y axis = mean error rate and I can plot K lines.

And so I can look for the value of k with the minimum mean error rate, for the biggest K I could find, and use that value with the classifier to test out-of-sample accuracy on the test set.

Is that what is meant by nested CV?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

That is not quite what is meant by nested CV.

Suppose your basic learning algorithm is "use 20-fold CV to find the best value of k, for $k = 1, 2, 3$". In order to assess the performance of this algorithm, you could again use CV, say 10-fold this time. As commented cbeleites, let's term these 10-folds "outer folds":

  • In outer fold 1, you would leave out the 1st 10th of the data; on the remainder of the data, you would perform 20-fold CV for each of $k = 1, 2, 3$, and note the best $$k you found. For this k, you would train on all of the data except for the 1st 10th, and check the performance on the 1st 10th.

  • In outer fold 2, you would leave out the 2nd 10th of the data; on the remainder of the data, you would perform 20-fold CV for each of $k = 1, 2, 3$, and note the best $k$ you found. For this $k4, you would train on all of the data except for the 2nd 10th, and check the performance on the 2nd 10th.

  • ...

  • In outer fold 10, you would leave out the last 10th of the data; on the remainder of the data, you would perform 20-fold CV for each of $k = 1, 2, 3$, and note the best $k4 you found. For this k, you would train on all of the data except for the last 10th, and check the performance on the last 10th.

So the 10 outer folds give you altogether 10 CV estimates; the 20 inner folds each outer fold uses, is just for selecting $k$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Oh ok, that sounds like something that's gonna take a long time to do on my computer. For a dataset thats extremely small (150), I think it's better to just stick with K-Fold or Stratified K-Fold. $\endgroup$
    – coderrio
    Commented Oct 25, 2017 at 15:30
  • 1
    $\begingroup$ Note that there is also iterated (aka repeated) cross validation where each iteration refers to a "run" of all 20 folds. Maybe renaming your "iterations" -> "outer folds" would be more clear wrt. papers in the literature. (Though I completely agree that the terminology is a mess and everyone seems to use their own words - leading to confusing overlap in terms between papers) $\endgroup$
    – cbeleites
    Commented Oct 26, 2017 at 9:45
  • 1
    $\begingroup$ @coderrio: plain (not nested) cross validation is only an option here if you skip the inner (20-fold in Ami's example) cross validation and fix the number of neighbours in some other way. However, the choice of the number of folds is typically not a crucial parameter - so you may reduce computational effort by doing 5-fold outer CV and 5-fold inner CV. Also, I don't see how runtime can be so bad for data with 150 instances (bad as in: the nested CV won't finish say over weekend)? (FYI: on my admittely good desktop, KNN training 120 cases (1000 variates) and predicting 30 cases takes 10 ms) $\endgroup$
    – cbeleites
    Commented Oct 26, 2017 at 10:03
  • $\begingroup$ @cbeleites Can't I just do K-Fold CV on my training set for K = 5 or 10, and k = 1 to 50 and see for which k I get the highest (mean) classification rate? That's running 5-Fold or 10-Fold CV 50 times (once for each k). Then use the one standard error rule to find the k that is within 1 standard error of the k giving the highest (mean) classification rate, and use that k to test classification accuracy on testing set, and then combine both to create the final model. $\endgroup$
    – coderrio
    Commented Oct 26, 2017 at 15:47
  • $\begingroup$ @coderrio: you can do that (in the sense that you can train whatever model and not do a validation). But what you do not get this way is a valid estimate of the final model's performance. That needs independent test data - and the "inner test" sets used for optimization of $k$ are part of model training and are therefore training error estimates. $\endgroup$
    – cbeleites
    Commented Oct 26, 2017 at 18:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.