"twinning" in cross validation

Question

The Wikipedia article on cross validation states

[...] cross-validation can be misused [...] By allowing some of the training data to also be included in the test set – this can happen due to "twinning" in the data set, whereby some exactly identical or nearly identical samples are present in the data set. Note that to some extent twinning always takes place even in perfectly independent training and validation samples. This is because some of the training sample observations will have nearly identical values of predictors as validation sample observations. And some of these will correlate with a target at better than chance levels in the same direction in both training and validation when they are actually driven by confounded predictors with poor external validity.

While I do not completely understand this paragraph (e.g. what is "better than chance levels"?), it makes sense to me that samples with "similar" input values should be all in the test set or all in the training set when doing cross-validation. Are there any published results on (1) how the groups for $k$-fold cross-validation should be chosen, and (2) how the cross-validated estimate may get worse when $k$ increases?

Answer 1

Don't have time to write a full answer right now, but here's a start.

• how the cross-validated estimate may get worse when k increases?

  Short answer is: it doesn't -- with the possible exception of $k = n$, i.e. leave-one-out.
  LOO always tests with a class that is underrepresented in training. Some classifiers take relative frequencies of cases into account - testing always with a class that is underrepresented can then lead to pessimistic bias.
  We observed this e.g. with PLS-DA and discuss it in this paper:
  Beleites, C.; Baumgartner, R.; Bowman, C.; Somorjai, R.; Steiner, G.; Salzer, R. & Sowa, M. G. Variance reduction in estimating classification error using sparse datasets, Chemom Intell Lab Syst, 79, 91 - 100 (2005). Even that may better be described as lack of stratification which is a side-effect of excluding a single case that makes the splitting not representative of the whole data in one particular and important aspect.

• how the groups for k-fold cross-validation should be chosen

  I've mostly been working with medical diagnostic data with spectroscopic data sets that can contain > 1000 spectra per patient. Key-words would be that the data is clustered or hierarchical in nature.
  In our context, we've been writing that the splitting into training and test subsets needs to be done patient-wise (e.g. Beleites et al.: Classification of human gliomas by infrared imaging spectroscopy and chemometric image processing, Vib Spec 38 (2005) 143-149. DOI:10.1016/j.vibspec.2005.02.020)
  Particularly for deeply nested data structures as are common in biology (but also occur in process control and in the chemical lab), the key is to split at the highest possible confounder below the factor in question. Splitting also needs to be independent of crossed confounders wrt. the factor in question (this has been presented at conferences, but is not yet published as paper).

Assuming you read German, you can find more readable summaries in my thesis (C. Beleites: Raman-spektroskopische Diagnostik von primären Hirntumoren mit Hilfe weicher chemometrischer Klassifikationsmethoden, 2015, FSU Jena), see the "Validierung" section in the Introduction and part II "Entwicklungen und Untersuchungen zur Validierung von chemometrischen Modellen im Rahmen der Dissertation".

Feel free to contact me if you have questions.