Need for cross-validation in KNN

Question

I read that we need cross-validation in KNN algorithm as the K value that we have found from the TRAIN-TEST of KNN might not be generalizable on unseen data.

The logic given was that, the TEST data set was used in finding K value, and thus the KNN-ALGORITHM is having information of the TEST dataset because K was found by using TEST dataset. And it is not same as unseen data.

But YES, the K value was found from the TEST dataset and thus we get our KNN-Algorithm, but the testing on TEST data was carried out without knowledge of TEST data and and yes we picked K from that but irrespective of our picking that k or not, KNN was giving that accuracy on TEST data that was blind.

So why need for cross-validation because of this?

Answer 1

It is a best practice to use crossvalidation to find the best hyperparameter values.

If you test several different hyperparameter values (like some different K values for KNN) it is custom to have:

• a training data set:

  The train data set is split in k folds to apply crossvalidation

  You do crossvalidation and get the metric with different values of k

  Then you select the best k for you final model

• a testing data set:

  With all the model and hyperparameters chosen you do a final measure on the test set to check if your model and hyperparameters are good on unseen data

This way you are sure to keep some unseen data for the final model evaluation, and avoid data leakage while choosing and selecting the best hyperparameter value k.

Answer 2

In addition to what Malo said.

Cross validation actually solves another problem. We used to split the data into 3 sets. A training set to fit the model, a test set to fine tune the parameters and a validation set for the final test. If you do this split only once then the model learns only with the training set provided. So the learning depends on how you decide to split the dataset. The dataset to learn with gets very small. With cross validation you split the dataset multiple times and you learn and fine tune on every k-fold. With every iteration you might get new information from the dataset and you increase the data you can use for training and fine tuning. In the graph below you can think of the orange test data as validation data.

(from https://scikit-learn.org/stable/modules/cross_validation.html )

If you want to test a pupil you'll make sure that the pupil doesn't have access to the exam answers, right? You want to know if the pupil can perform well on an exam which he/she hasn't seen before. It's the same thing here. If you train and fine tune a model on a dataset you want to make sure that it performs well on a new unseen test set.

Let's stay with the pupil analogy here. Let's assume each row of the matrix in the graph is a week of learning for a final exam. The final exam is the orange test data. Every week the pupil studies with the study materials (green) and does a training test (blue). The next week the study material changes slightly and the pupil has a new training test (blue). Once all weeks of learning are complete the pupil takes the final exam(orange) which has never seen before questions.

See this post for a detailed explanation difference-test-validation-datasets/

Answer 3

and yes we picked K from that but irrespective of our picking that k or not, KNN was giving that accuracy on TEST data that was blind.

Yes, and this is why the selection process isn't completely useless; we picked the hyperparameter(s) based on performance on unseen data.

But that selection still introduces bias to the score. To see that, pretend that your hyperparameter actually does nothing, so that the scores on the test folds vary only due to randomness in your model fitting procedure (OK, so something other than kNN). Then the test scores are just random numbers with some distribution around the true/asymptotic performance. The selection method selects the hyperparameter displaying the maximum value from this random sample. That's obviously higher than the true expected performance, which lies somewhere around the mean of your sample values.