Holdout and cross validation

The accuracy of a classifier is the percentage of test tuples correctly classified. It must be measured on records not used for training, otherwise the estimate is too optimistic.

Holdout method

• The data are randomly divided into two independent sets: a training set (usually two-thirds, 66-70%) used to build the model, and a test set (one-third) used to estimate accuracy.
• Simple and fast, but the estimate depends on the particular split; the training set is smaller than the full data.
• Random subsampling repeats holdout k times and averages the accuracies, reducing this variance.

Data --> [ Training 2/3 ] --> build model --+
     --> [ Test 1/3     ] --> accuracy  <---+

k-fold cross-validation

1. Randomly divide the data into k mutually exclusive subsets (folds) D₁, …, D_k of about equal size (k = 10 is usual).
2. Perform k rounds. In round i, use Dᵢ as the test set and the remaining k − 1 folds as the training set.
3. Accuracy = total number of correct classifications over the k rounds / total number of tuples. (Or the average of the fold accuracies.)

Every tuple is used once for testing and k − 1 times for training, so the estimate is less biased and more reliable than holdout.

Variations

• Leave-one-out: k = number of tuples; each fold has one tuple. Good for small data, costly for large.
• Stratified cross-validation: each fold keeps approximately the class distribution of the whole data.
• Bootstrap: sample with replacement; about 63.2% of tuples go to training, and the rest to testing.

Cross-validation takes about k times more computation than holdout.