Data Reduction Strategies: Dimensionality Reduction, Principal Component Analysis (PCA), and Numerosity Reduction

1. The Curse of Dimensionality in Modern Enterprise Data

When datasets contain hundreds or thousands of attributes (dimensions)—as commonly encountered in genomic research, text mining, and high-frequency trading—mining algorithms encounter the Curse of Dimensionality. As dimensionality increases:

• The volume of space grows exponentially, causing data points to become extremely sparse.
• Euclidean distance metrics collapse: the distance between the closest pair of points becomes indistinguishable from the distance between the furthest pair.
• Computational complexity and memory consumption explode, causing algorithms to become intractable.

Data Reduction techniques obtain a reduced representation of the dataset that is much smaller in volume yet closely maintains the integrity of the original data, producing identical (or near-identical) analytical results.

2. Taxonomy of Data Reduction Strategies

Data reduction methodologies fall into three primary strategic categories:

3. Principal Component Analysis (PCA): Mathematical Foundations

Principal Component Analysis (PCA) is the premier unsupervised linear dimensionality reduction technique. It searches for (k) orthogonal (n)-dimensional vectors (where (k le n)) that best capture the variance in the data:

• Step 1 (Centering): Normalize input data so that each attribute has a mean of zero and standard deviation of one.
• Step 2 (Covariance Matrix): Compute the (n imes n) Covariance Matrix (C) to measure pairwise attribute variance and covariance.
• Step 3 (Eigen Decomposition): Compute the eigenvalues ((lambda_1, lambda_2, dots, lambda_n)) and corresponding orthogonal eigenvectors ((e_1, e_2, dots, e_n)) of matrix (C).
• Step 4 (Sorting & Selection): Sort eigenvectors in descending order of their eigenvalues. The eigenvector with the largest eigenvalue is the First Principal Component ((PC_1)), capturing the maximum variance in the data. (PC_2) captures the second-highest variance while remaining strictly orthogonal (uncorrelated) to (PC_1).
• Step 5 (Projection): Retain the top (k) principal components that together capture 90%–95% of total variance, discarding remaining components. Project the original data points onto this new (k)-dimensional subspace.

4. Numerosity Reduction: Parametric versus Non-Parametric

Numerosity reduction shrinks the number of tuples:

• Parametric Models: Fit the data to mathematical models (such as Multiple Linear Regression: (Y = w_0 + w_1 X_1 + w_2 X_2)). Once parameters (w) are estimated, only the equation parameters need to be stored, discarding raw data tuples entirely.
• Non-Parametric Histograms: Partition continuous values into buckets, storing only bucket counts and boundary ranges.
• Clustering as Reduction: Replace thousands of raw records with the coordinates of the cluster centroids.

5. Sampling Methodologies in Data Mining

Sampling enables mining algorithms to execute on representative subsets rather than millions of records:

• Simple Random Sample Without Replacement (SRSWOR): Each tuple has an equal probability of selection ((1/N)); once selected, it cannot be chosen again.
• Stratified Sampling: If the dataset is partitioned into mutually exclusive demographic or class strata (e.g., 95% non-fraud, 5% fraud), stratified sampling draws samples from each stratum independently, preserving the minority class ratio in the training sample.