Data Reduction

1. Definition

Data reduction obtains a reduced representation of the data that is much smaller in volume but produces the same (or almost the same) analytical results. Benefits: faster mining, less memory, better generalisation.

Three families of strategies:

 DATA REDUCTION
   |-- Dimensionality reduction   (fewer ATTRIBUTES: PCA, wavelet, feature selection)
   |-- Numerosity reduction       (fewer ROWS: regression, histograms, clustering, sampling, cube aggregation)
   |-- Data compression           (lossless Huffman/LZW, lossy wavelet/PCA/JPEG)

2. Dimensionality Reduction

(a) Attribute subset selection (feature selection) — find the minimum set of attributes such that the resulting probability distribution of classes is close to the original.

Steps: (i) search method → forward selection, backward elimination, stepwise/decision-tree-induction hybrid; (ii) evaluation criterion → information gain, Gini index, $\chi^2$ , accuracy.

 Forward selection:            Backward elimination:
 {} -> {best} -> {best,2nd}    {all} -> drop worst -> ... -> {best subset}
 (greedy, additive)            (greedy, subtractive)

(b) Wavelet transform — represent data as a sum of basis functions; keep only the largest-magnitude coefficients (lossy).

Example with Haar wavelets on [2, 2, 0, 2, 3, 5, 4, 4]:

 Level 1 averages : 2 , 1 , 4 , 4        Level 1 details: 0, -1, -1, 0
 Level 2 averages : 1.5 , 4              Level 2 details: 0.5, 0
 Level 3 average  : 2.75                 Level 3 detail : -1.25
 Compressed form  : [2.75, -1.25, 0.5, 0, 0, -1, -1, 0]
 Keep top-k largest -> e.g. k = 3 -> [2.75, -1.25, 0.5] (approx. original data)

(c) Principal Component Analysis (PCA) — find $k$ orthonormal vectors (principal components) capturing most variance; original data projected onto them.

X_{n \times m} \xrightarrow{\text{eigen decomposition of } \Sigma} \text{top-}k \text{ components},\qquad \text{variance retained}=\frac{\sum_{i=1}^{k}\lambda_i}{\sum_{i=1}^{m}\lambda_i}

PCA is lossy but unsupervised (no class label needed).

3. Numerosity Reduction

(a) Parametric methods — assume a model, store only model parameters:

Linear regression: $y = a + bx$
Multiple regression: $y = w_0 + w_1x_1 + \dots + w_mx_m$
Log-linear model (for multi-dimensional sparse data, probability estimates)
Outliers are removed before fitting (regression is sensitive to them).

(b) Non-parametric methods

Histograms: partition attribute values into buckets; store bucket sums. Types — equal-width, equal-frequency, V-optimal (minimum variance within buckets).

 Equal-width (width 10):   [0-10): 20   [10-20): 15   [20-30): 8
 Equal-frequency (4 vals):  bin1: 4,8,15,21  bin2: 21,24,25,28  bin3: 34
 V-optimal: bucket boundaries chosen to minimise  Σ variance within buckets

Clustering: store cluster representatives (centroids) instead of all points — e.g. 1,000,000 points → 50 centroids.
Sampling: a small random sample represents the whole set.
- SRSWOR (simple random sample without replacement)
- SRSWR (with replacement)
- Stratified sampling — sample from each stratum (class/group), good for skewed data
- Cluster sampling — randomly pick clusters (e.g. city blocks), use all members
Variance of the sample mean for SRSWOR:

\sigma_{\bar x}^{2}=\frac{\sigma^{2}}{n}\left(1-\frac{n}{N}\right)

Progressive/adaptive sampling scans the data and stops when the sample is large enough.

Data cube aggregation: store pre-computed cuboids — the cuboid with the fewest dimensions (most aggregated) answers the query with least I/O.

4. Data Compression

Type	Idea	Examples	Effect on mining result
Lossless	Perfect reconstruction	Huffman coding, LZW, run-length	Identical results
Lossy	Approximate reconstruction; high compression	Wavelet, PCA, JPEG, MP3	Slightly different but acceptable results

String compression ratio:

\text{Compression ratio}=\frac{\text{size before}}{\text{size after}},\qquad \text{e.g. }\frac{1000 \text{ MB}}{100 \text{ MB}} = 10:1

5. Choosing a Strategy

Situation	Preferred reduction
Very many attributes, distance-based algorithm	PCA / feature selection
Very many rows, aggregate queries	Cube aggregation, histograms
Skewed data with rare classes	Stratified sampling
Data with many zeros / sparse	Wavelet, sparse-matrix, log-linear model
Need exact answers	Lossless compression, careful sampling with adequate $n$

6. Exam Points

Explain dimensionality reduction and numerosity reduction with techniques — 10 marks (frequent).
Wavelet transform numerical (Haar) — 5 marks.
Explain SRSWOR, SRSWR, stratified and cluster sampling with example — 5-7 marks.
Difference between lossless and lossy compression in data mining — 3 marks.

Data Reduction

Data Reduction

1. Definition

2. Dimensionality Reduction

3. Numerosity Reduction

4. Data Compression

5. Choosing a Strategy

6. Exam Points

Pocketly on Android