Choice of K in K-fold cross-validation I've been using the $K$-fold cross-validation a few times now to evaluate performance of some learning algorithms, but I've always been puzzled as to how I should choose the value of $K$.
I've often seen and used a value of $K = 10$, but this seems totally arbitrary to me, and I now just use $10$ by habit instead of thinking it over. To me it seems that you're getting a better granularity as you improve the value of $K$, so ideally you should make your $K$ very large, but there is also a risk to be biased.
I'd like to know what the value of $K$ should depend on, and how I should be thinking about this when I evaluate my algorithm. Does it change something if I use the stratified version of the cross-validation or not?
 A: The choice of $k = 10$ is somewhat arbitrary. Here's how I decide $k$:


*

*first of all, in order to lower the variance of the CV result, you can and should repeat/iterate the CV with new random splits.  This makes the argument of high $k$ => more computation time largely irrelevant, as you anyways want to calculate many models. I tend to think mainly of the total number of models calculated (in analogy to bootstrapping). So I may decide for 100 x 10-fold CV or 200 x 5-fold CV.

*@ogrisel already explained that usually large $k$ mean less (pessimistic) bias. (Some exceptions are known particularly for $k = n$, i.e. leave-one-out).

*If possible, I use a $k$ that is a divisor of the sample size, or the size of the groups in the sample that should be stratified.

*Too large $k$ mean that only a low number of sample combinations is possible, thus limiting the number of iterations that are different. 


*

*For leave-one-out: $\binom{n}{1} = n = k$ different model/test sample combinations are possible. Iterations don't make sense at all.

*E.g. $n = 20$ and $k = 10$: $\binom{n=20}{2} = 190 = 19 ⋅ k$ different model/test sample combinations exist. You may consider going through all possible combinations here as 19 iterations of $k$-fold CV or a total of 190 models is not very much. 


*These thoughts have more weight with small sample sizes. With more samples available $k$ doesn't matter very much. The possible number of combinations soon becomes large enough so the (say) 100 iterations of 10-fold CV do not run a great risk of being duplicates. Also, more training samples usually means that you are at a flatter part of the learning curve, so the difference between the surrogate models and the "real" model trained on all $n$ samples becomes negligible. 
A: Larger K means less bias towards overestimating the true expected error (as training folds will be closer to the total dataset) but higher variance and higher running time (as you are getting closer to the limit case: Leave-One-Out CV).
If the slope of the learning curve is flat enough at training_size = 90% of total dataset, then the bias can be ignored and K=10 is reasonable.
Also higher K give you more samples to estimate a more accurate confidence interval on you estimate (using either parametric standard error assuming normality of the distribution of the CV test errors or non parametric bootstrap CI that just make the i.i.d assumption which is actually not very true as CV folds are not independent from one another).
Edit: underestimating => overestimating the true expected error
Edit: the part of this reply about higher variances for large K or LOOCV is probably wrong (not always true). More details with simulations in this answer: Bias and variance in leave-one-out vs K-fold cross validation (thanks Xavier Bourret Sicotte for this work).
A: I don't know how K affects accuracy and generalization, and this may depend on the learning algorithm, but it definitely affects the computational complexity almost linearly (asymptotically, linearly) for training algorithms with algorithmic complexity linear in the number of training instances. The computational time for training increases K-1 times if the training time is linear in the number of training instances. So for small training sets I'd consider the accuracy and generalization aspects, especially given that we need to get the most out of a limited number of training instances.
However, for large training sets and learning algorithms with high asymptotical comutational complexity growth in the number of training instances (at least linear), I just select K=2 so that there is no increase in computational time for a training algorithm with asymptotic complexity linear in the number of training instances.
A: Solution:
K = N/N*0.30



*

*N = Size of data set

*K = Fold


Comment: We can also choose 20% instead of 30%, depending on size you want to choose as your test set.

Example: If data set size: N=1500; K=1500/1500*0.30 = 3.33; We can choose K value as 3 or 4 

Note:
Large K value in leave one out cross-validation would result in over-fitting. Small K value in leave one out cross-validation would result in under-fitting. 
Approach might be naive, but would be still better than choosing k=10 for data set of different sizes.   
