Data sampling methods

Data sampling selects a subset of the data objects to represent the whole data set. Mining a sample is faster and cheaper, and it works well if the sample is representative, i.e. has approximately the same properties of interest as the full data. Sampling is used both for data selection and for data reduction. Sample size matters: too small a sample misses patterns, while too large a sample reduces the savings.

Sampling methods

Let N be the number of tuples and n the sample size.

1. Simple random sampling without replacement (SRSWOR): draw n distinct tuples; each tuple has equal probability 1/N of being drawn and, once drawn, cannot be drawn again.
2. Simple random sampling with replacement (SRSWR): a drawn tuple is put back, so it can be selected more than once.
3. Stratified sampling: divide the data into disjoint groups (strata), such as age groups or classes, and draw a random sample from each stratum, usually in proportion to its size. It guarantees that small groups are represented and is used on skewed data.
4. Cluster sampling: tuples are grouped into clusters (e.g. cities, disk pages), and a random set of whole clusters is chosen.
5. Systematic sampling: select every k-th tuple after a random start (k = N/n).
6. Progressive (adaptive) sampling: start with a small sample and increase its size until the model accuracy stops improving.