K-Fold cross validation for multi class Let say I have train set of categories $C_1,\ldots,C_s$. Each category has different size. I want to divide the data to 10 subsets, each one is 10% of the train set and then perform 10 rounds of leaving out one subset for test and train on the other 9 subsets. (I.e. I want to perform 10-fold CV).
Now, there are two methods for dividing the data to 10 subsets of 10% (the categories are of different sizes):


*

*Divide randomly each category to 10 subsets of 10% and than each of the subsets for the 10-fold is concatenation of one subset from each category.

*Divide the data randomly to 10 subsets of 10% withot considering the different categories.
The main difference is that in method 1 every subset of the 10-fold has same distribution in terms of num of examples from each category and the distribution corresponds to the sizes of $C_1,\ldots,C_s$.
The question is which methos is better /more correct?
Also, which methos usally used?
 A: Making sure that the splits have (roughly) equal relative frequencies of each class is a form of stratification, so you're asking whether to do stratified resampling or not. 
Practically relevant differences between the two approaches will occur only for data where at least some class has very few cases. 
In such small-sample-size situations the answer is as usual: it depends. You need to think what it means in terms of your application and study and then decide whether or not to stratify. Also, you should report how and why you decided to do so.  The key is to think about to what situations exactly your generalization error should generalize.   


*

*To using the obtained classifier on data with the same relative frequencies as in the training data? => stratify 

*To using the obtained classifier on data with possibly slightly different relative frequencies? => do not stratify

*You use a classifier that you know to be rather insensitive wrt. to the relative frequencies (e.g. because you specify prior probabilities)? => stratification doesn't matter much. 

*You have information about the relative frequencies of the classes in the real world and your study is small but nevertheless set up in a way to closely resemble these? => stratification is sensible. 

*You are studying the classifier algorithm rather than the application? => In that case, it may make sense to do both, and see whether the algorithm is sensitive to slight changes in the relative frequencies of the classes. 
So IMHO more important than stratifying or not is to be think of the consequences. 
A: From purely intuitive viewpoint, imposing exactly the same distribution of classes across all the folds seems not justified: this way you take it as ground truth that the distribution will be the same in all datasets in the world that model may encounter in the future. 
To put differently, if $D$ is your data, $I$ is all your prior information about the world, and $f_{classes}$ is the frequency of classes in your dataset, $F_{classes}$ is the frequency of classes in the datasets you're about to see, then $Pr(F_{classes}=f_{classes} \big| D,I)$ is not 1. What does it equal to exactly depends on how you model it.
Then, if class distribution across all folds is forced to be the same, then cross-validated error estimate might be biased and not really estimate generalization error. So to say, we begin to use information that we don't really have -- it's a straight way to overfitting.
Nevertheless, it's only some intuitions, and I cannot derive it rigorously right away. Maybe I miss something important. Personally, I don't incur any restrictions on class distribution when sampling for CV, and know much research that also doesn't.
Of course, if the data is very imbalanced and some classes are very rare, than some restrictions is surely needed just to make sure that the observations of a given class are not too rare in absolute sense. Also, some more complicated CV schemes are used when, for example, comparing accuracy of different classifiers on one dataset, to find out if one of them is "significantly" better.
