Data Reduction in Data Mining

Data reduction shrinks a dataset — fewer rows, fewer columns, or a more compact representation entirely — while preserving enough of its structure that mining it still produces essentially the same results as mining the full original. Sampling (covered with a stratified-sampling worked example in the lesson on partitioning methods in data mining), PCA and feature selection (covered with a worked example in the lesson on data preprocessing techniques), and data cube aggregation via roll-up (covered with a worked example in the lesson on data warehouses and OLAP technology) are each covered in depth elsewhere in this series. This lesson works through the one reduction technique not covered anywhere else: the wavelet transform, using a real, hand-computed example rather than describing it only in the abstract.

A Worked Haar Wavelet Transform

The simplest wavelet transform, the Haar transform, reduces a sequence of numbers by repeatedly replacing adjacent pairs with their average (capturing the shared trend) and their difference (capturing what's left over, unique to that pair). Take a short signal of four values: [8, 4, 6, 2]:

Pair 1: (8, 4)  ->  average = (8+4)/2 = 6,  difference = (8-4)/2 = 2
Pair 2: (6, 2)  ->  average = (6+2)/2 = 4,  difference = (6-2)/2 = 2
Transformed representation: [6, 4 | 2, 2]
   (6, 4 = "approximation" coefficients — the coarse trend)
   (2, 2 = "detail" coefficients — what the averages left out)

This transform is exactly reversible with no information lost at all — the original values can be recovered perfectly from the transformed ones:

Pair 1: 6 + 2 = 8 (recovers the first original value), 6 - 2 = 4 (recovers the second)
Pair 2: 4 + 2 = 6 (recovers the third original value),  4 - 2 = 2 (recovers the fourth)

The actual data reduction happens in the next step, not this one: because the two detail coefficients here are small (2 and 2, compared to the approximation values 6 and 4), they can often be discarded or rounded to zero with only a small loss of accuracy, keeping just the two approximation coefficients — [6, 4] — as a compressed stand-in for the original four values. A smoother original signal (one where adjacent values are closer together) produces even smaller detail coefficients, meaning smoother data compresses more aggressively under this technique with less information actually lost — which is exactly the property that makes wavelet transforms useful for reducing data that has an underlying trend, such as sensor readings or time series, rather than data with no structure to exploit at all. In practice, this averaging-and-differencing step is applied recursively to the approximation coefficients from the previous level, producing further reduction at the cost of progressively coarser detail.

Where the Rest of Data Reduction Is Covered

• Dimensionality reduction (PCA, which builds new combined features, versus attribute subset selection, which keeps a subset of the original ones) — covered with a worked example in the lesson on data preprocessing techniques, with the filter/wrapper/embedded feature-selection strategies covered further in the lesson on preprocessing in data mining.
• Sampling (random, stratified, and the class-imbalance techniques SMOTE/oversampling/undersampling) — covered with a worked example in the lesson on partitioning methods in data mining.
• Data cube aggregation (roll-up, collapsing detailed records like daily sales into a coarser summary like annual totals) — covered with a worked example in the lesson on data warehouses and OLAP technology.
• Discretization (converting continuous values into ranges, both the equal-width and equal-frequency approaches) — covered with worked examples in the lesson on data preprocessing techniques and the lesson on preprocessing in data mining; an entropy-based approach, working bottom-up by merging adjacent ranges only when doing so doesn't reduce class purity, uses the same entropy calculation covered in the lesson on attribute selection measures, applied to deciding bin boundaries rather than tree splits.
• Data compression (lossless methods like run-length encoding, which recover the exact original, versus lossy methods like JPEG, which discard detail permanently in exchange for a smaller file) — a standard distinction, and the same trade-off the wavelet transform above makes when its small detail coefficients are discarded.