# Understanding stratified cross-validation

What is the difference between stratified cross-validation and cross-validation?

Wikipedia says:

In stratified k-fold cross-validation, the folds are selected so that the mean response value is approximately equal in all the folds. In the case of a dichotomous classification, this means that each fold contains roughly the same proportions of the two types of class labels.

But I am still confused.

1. What does mean response value mean in this context?
2. Why is # 1 important?
3. How does one achieve #1 in practice?

Cross-validation article in Encyclopedia of Database Systems says:

Stratification is the process of rearranging the data as to ensure each fold is a good representative of the whole. For example in a binary classification problem where each class comprises 50% of the data, it is best to arrange the data such that in every fold, each class comprises around half the instances.

About the importance of the stratification, Kohavi (A study of cross-validation and bootstrap for accuracy estimation and model selection) concludes that:

stratification is generally a better scheme, both in terms of bias and variance, when compared to regular cross-validation.

• Can you describe, intuitively, why it's better that regular CV ? – MohamedEzz Feb 22 '15 at 15:40
• Perhaps include a paragraph that there are different degrees of stratification you can aim for and that they interfere to different degrees with the randomness of the folds. Sometimes, all you need is to make sure there is art least one record of each class in each fold. Then you could just generate the folds randomly, check if that condition is met and only in the unlikely case it isn't met reshuffle the folds. – David Ernst Sep 3 '17 at 17:30

Stratification seeks to ensure that each fold is representative of all strata of the data. Generally this is done in a supervised way for classification and aims to ensure each class is (approximately) equally represented across each test fold (which are of course combined in a complementary way to form training folds).

The intuition behind this relates to the bias of most classification algorithms. They tend to weight each instance equally which means overrepresented classes get too much weight (e.g. optimizing F-measure, Accuracy or a complementary form of error). Stratification is not so important for an algorithm that weights each class equally (e.g. optimizing Kappa, Informedness or ROC AUC) or according to a cost matrix (e.g. that is giving a value to each class correctly weighted and/or a cost to each way of misclassifying). See, e.g. D. M. W. Powers (2014), What the F-measure doesn't measure: Features, Flaws, Fallacies and Fixes. http://arxiv.org/pdf/1503.06410

One specific issue that is important across even unbiased or balanced algorithms, is that they tend not to be able to learn or test a class that isn't represented at all in a fold, and furthermore even the case where only one of a class is represented in a fold doesn't allow generalization to performed resp. evaluated. However even this consideration isn't universal and for example doesn't apply so much to one-class learning, which tries to determine what is normal for an individual class, and effectively identifies outliers as being a different class, given that cross-validation is about determining statistics not generating a specific classifier.

On the other hand, supervised stratification compromises the technical purity of the evaluation as the labels of the test data shouldn't affect training, but in stratification are used in the selection of the training instances. Unsupervised stratification is also possible based on spreading similar data around looking only at the attributes of the data, not the true class. See, e.g. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.469.8855 N. A. Diamantidis, D. Karlis, E. A. Giakoumakis (1997), Unsupervised stratification of cross-validation for accuracy estimation.

Stratification can also be applied to regression rather than classification, in which case like the unsupervised stratification, similarity rather than identity is used, but the supervised version uses the known true function value.

Further complications are rare classes and multilabel classification, where classifications are being done on multiple (independent) dimensions. Here tuples of the true labels across all dimensions can be treated as classes for the purpose of cross-validation. However, not all combinations necessarily occur, and some combinations may be rare. Rare classes and rare combinations are a problem in that a class/combination that occurs at least once but less than K times (in K-CV) cannot be represented in all test folds. In such cases, one could instead consider a form of stratified boostrapping (sampling with replacement to generate a full size training fold with repetitions expected and 36.8% expected unselected for testing, with one instance of each class selected initially without replacement for the test fold).

Another approach to multilabel stratification is to try to stratify or bootstrap each class dimension separately without seeking to ensure representative selection of combinations. With L labels and N instances and Kkl instances of class k for label l, we can randomly choose (without replacement) from the corresponding set of labeled instances Dkl approximately N/LKkl instances. This does not ensure optimal balance but rather seeks balance heuristically. This can be improved by barring selection of labels at or over quota unless there is no choice (as some combinations do not occur or are rare). Problems tend to mean either that there is too little data or that the dimensions are not independent.

The mean response value is approximately equal in all the folds is another way of saying the proportion of each class in all the folds are approximately equal.

For example, we have a dataset with 80 class 0 records and 20 class 1 records. We may gain a mean response value of (80*0+20*1)/100 = 0.2 and we want 0.2 to be the mean response value of all folds. This is also a quick way in EDA to measure if the dataset given is imbalanced instead of counting.