Completely different results after each cross validation I'm running some classification algorithms in MATLAB and validating them with a 10-fold cross validation. The problem is that every time I execute the cross validation, it gives a very different result. I see that it is normal the result to be a bit different each time, as the folds are created in a random way, but.. The result varies a lot. 
How can I rely on my results seeing this behavior? Does this mean that the number of folds is too less or too much? What should I do?
All suggestions are welcome!
Thanks!
 A: I think, you need to provide more information, as there are a lot of possible causes:


*

*you have a small dataset, for example (extreme one) only 10 points

*your classifier depends strong on randomness, for example the random forest

*you are using a bad metric with an unbalanced dataset (say accuracy)


What you should do:


*

*ensure, the dataset is big enough and you don't use (by a bug for example) only a small part of your data

*try other classifiers, which work completely different (XGBoost, Random Forest, AdaBoost, Gradient Boost, SVM etc.) if that is easy to implement

*use another metric (ROC AUC should generally do a good job)

*use the same integer all the times to feed the pseudo-random number generator


Is anything special about your data/classifier compared to other classification problems you have done?
A: @Mayou's answer and @Halil's comment point out typical situations in which you observe such behaviour. 
Let me add that you observe model instability - this should give you a search term to start looking up what can be done.

How can I rely on my results seeing this behavior? 

These validation results tell you that you cannot rely on the predictions of your model: the models are so unstable that predictions for the same test case (each case is tested once during each run) are all over the place. 
This may be a valid result in case you're doing an exploratory analysis, but if your task is to set up a classifier for prediction, you need to go back to classifier modeling. See below.

Does this mean that the number of folds is too less or too much? 

No. Typically the problem is not the cross validation setup but the modeling.
(You may have unstable surrogate models for the cross validation but a reasonably stable model of the whole data set if the surrogate models are trained on a small fraction of all cases. In practice, I've never seen that repeated/iterated cross validation indicates huge instability in situations where the whole data model isn't unstable as well: noone does 2-fold CV in situations where low but reasonable numbers of cases are available.)

What should I do?

Go a bit deeper into measuring model stability with repeated/iterated cross validation. The overall indicator is no very sensitive detector for model instability. Here's one of our papers discussing how to measure stability of the prediction with repeated/iterated cross validation: Beleites, C. & Salzer, R.: Assessing and improving the stability of chemometric models in small sample size situations, Anal Bioanal Chem, 390, 1261-1271 (2008). DOI: 10.1007/s00216-007-1818-6
Read up on model stability. 
You can improve model stability by e.g.:


*

*not doing data driven model optimization (i.e. decide hyperparameters without the use of an inner cross validation loop)

*use stronger regularization

*use model aggregation,
e.g. random forest instead of a decision tree. You can also aggregate the cross validation surrogate models as we did in the paper linked above.

*consider using a classification algorithm that is more stable (stronger regularization, fewer hyperparameters/hyperparameters that can more easily be set by expert knowledge or experience or other non-data-dependent indicators)

*more samples will always beat all kinds of fancy heuristics 

