I'm working on a binary classification task, and I've been running into problems generalizing from my cross-validation to my test set (model does great on cross validation, very poorly on test set).
I decided to try using some synthetic data to see if my tuning and validation procedure was reasonable. I thought that I should generate some fake, completely random data and if my methodology is sound, the cross-validation should NOT find any good models because, well, the data is random. So, I:
- Created a set of randomly generated data, 1 binary target variable, 10 features (from a normal distribution)
- Ran cross validation using k-NN (K-nearest neighbors) algorithm. I did grid-search hyperparameter tuning and feature selection simultaneously in cross validation (again, all columns of data are randomly generated from normal distribution)
- Compared best model found in CV to the baseline model (which predicts the same class every time).
What I found is that even though the data is totally randomly generated, I find that the "best" model that gives an accuracy of 60% on cross validation, when the baseline accuracy (on CV) is 55%.
How can I avoid this? I can't possibly rely on a cross validation if the model finds "patterns" in completely random data.
I would greatly appreciate any ideas or advice on this issue!
EDIT: My real dataset is about 700 rows, so I created my synthetic data to also have 700 rows. I decided to increase this dramatically to see if the problem persists, so I created a synthetic dataset of 10,000 rows and tried the above procedure again. The cross validation error was much closer to the baseline (52% vs. 51%). So it looks like initially, I really did try too many things on too little data and got lucky.
My question then becomes this: on my smaller dataset, what could I do to keep cross-validation useful? I mean, if it's going to overfit every time, how can I combat that to give a more reasonable model or error estimation?
Is the answer nested cross validation?
EDIT: I tried nested cross validation, and that's exactly what I needed to do. I forgot about the separation of model selection and model evaluation. K-fold cross validation provides a best model (model selection), but can't give an accurate estimation of that model's out-of-sample performance. So, with nested cross validation, I saw that no models selected through cross validation on this dataset was able to generalize to the test-sets, which is exactly what I expected.
Thank you all for your advice, discussions and responses.