Making data smaller without losing what matters: aggregation, attribute selection, compression, numerosity reduction and discretisation.
Data reduction produces a much smaller version of a data set that still gives nearly the same mining results. As a result, mining algorithms finish in minutes instead of days.
9.1 Data cube aggregation
In data cube aggregation, summaries are calculated in advance at the level of detail that the analysis needs.
ExampleShopMart has quarterly sales figures for 2023 to 2025, which makes 12 values, but its analysis needs only the annual totals. The table below shows both.
| Year | Q1 | Q2 | Q3 | Q4 | Annual (₹ crore) |
|---|---|---|---|---|---|
| 2023 | 220 | 240 | 230 | 310 | 1,000 |
| 2024 | 250 | 260 | 255 | 335 | 1,100 |
| 2025 | 270 | 290 | 280 | 360 | 1,200 |
ExplanationEach annual figure is the sum of its four quarters; for 2023, for example, 220 + 240 + 230 + 310 = ₹1,000 crore. The 12 quarterly values are therefore reduced to three annual values without losing anything that the question needs. In general, a query should use the smallest cuboid that can answer it.
9.2 Dimensionality reduction (attribute subset selection)
Dimensionality reduction keeps only the attributes that matter and removes the rest.
ExampleA bank that predicts loan defaults has 20 attributes, including the customer's name, phone number, income and credit score. In stepwise forward selection, it starts with no attributes and adds the best remaining attribute in each round, stopping when accuracy improves by less than 1 percentage point. With no attributes, simply predicting "repaid" for everyone is 60 per cent accurate. Adding income raises accuracy to 72 per cent, a gain of 12 points; adding credit score raises it to 81 per cent, a gain of 9 points; and adding the number of existing loans raises it to 85 per cent, a gain of 4 points. Adding age would raise it only to 85.3 per cent, a gain of 0.3 points, so the selection stops with three attributes. In stepwise backward elimination, it starts with all 20 attributes and removes the worst one in each round: first the phone number, then the name, then the branch code. In the combined method, each round adds the best attribute and removes the worst one at the same time. In decision-tree induction, it builds a decision tree and drops every attribute that does not appear in the tree, such as the name and the phone number.
ExplanationA customer's name and phone number carry no information about whether a loan will be repaid. Removing such attributes makes mining faster and often makes it more accurate, because irrelevant attributes only add noise.
9.3 Data compression
Data compression stores the data in a smaller encoded form. There are four main approaches.
Lossless compression allows the original data to be rebuilt exactly.
ExampleThe string "AAAAABBB" is stored as "5A3B", which is called run-length encoding.
ExplanationLossless compression is used for text and codes, where not even a small error is acceptable.
Lossy compression allows only an approximation of the original to be rebuilt.
ExampleA photograph is stored as a JPEG file.
ExplanationSome fine detail is lost, but the saving in space is large.
The wavelet transform converts the data into coefficients and keeps only the strongest of them.
ExampleThe Haar wavelet transform is applied to the eight values 2, 2, 0, 2, 3, 5, 4 and 4. At each level, neighbouring pairs are replaced by their average and half their difference. At level 1, the pairs (2, 2), (0, 2), (3, 5) and (4, 4) give the averages 2, 1, 4 and 4 and the half-differences (2 − 2) ÷ 2 = 0, (0 − 2) ÷ 2 = −1, (3 − 5) ÷ 2 = −1 and (4 − 4) ÷ 2 = 0. At level 2, the averages (2, 1) and (4, 4) give the averages 1.5 and 4 and the half-differences 0.5 and 0. At level 3, the pair (1.5, 4) gives the average 2.75 and the half-difference −1.25. The transformed data is therefore 2.75, −1.25, 0.5, 0, 0, −1, −1 and 0.
ExplanationThree of the eight coefficients are zero, so only five numbers need to be stored, and the original eight values can still be rebuilt exactly by reversing the steps. If the smallest non-zero coefficient, 0.5, were also dropped, only four numbers would be stored and the values could be rebuilt approximately. On a real series of 1,024 daily sales figures, keeping the 100 largest coefficients typically preserves the trends and peaks with under 10 per cent of the data.
Principal component analysis (PCA) replaces a set of correlated attributes with a smaller set of new, uncorrelated attributes called principal components.
ExampleFive customers have the heights and weights shown below.
| Customer | Height (cm) | Weight (kg) | Height − mean | Weight − mean |
|---|---|---|---|---|
| 1 | 150 | 50 | −15 | −12 |
| 2 | 160 | 57 | −5 | −5 |
| 3 | 165 | 63 | 0 | 1 |
| 4 | 170 | 66 | 5 | 4 |
| 5 | 180 | 74 | 15 | 12 |
The mean height is 825 ÷ 5 = 165 cm and the mean weight is 310 ÷ 5 = 62 kg. Dividing the sums of squared and multiplied deviations by n − 1 = 4 gives the variance of height, 500 ÷ 4 = 125; the variance of weight, 330 ÷ 4 = 82.5; and their covariance, 405 ÷ 4 = 101.25. The eigenvalues of this 2 × 2 covariance matrix are 207.21 and 0.29, so the first principal component carries 207.21 ÷ (207.21 + 0.29) = 207.21 ÷ 207.50 ≈ 99.86 per cent of the total variation. Its direction is about (0.78, 0.63), meaning it combines height and weight in roughly equal measure, so it could be called "body size".
ExplanationTwo attributes are replaced by one component that keeps 99.86 per cent of the information, so the data is halved in width with almost no loss. On a data set with 50 attributes, PCA might similarly keep only 8 components.
9.4 Numerosity reduction
Numerosity reduction replaces the data with a smaller representation. The parametric methods store a model instead of the data, while the non-parametric methods store a reduced version of the data itself.
Regression and log-linear models are parametric methods.
ExampleFive months of data record advertising spend (x) and sales (y), both in lakhs of rupees: (1, 53), (2, 56), (3, 59), (4, 63) and (5, 65). The least-squares line y = a + bx is found as follows. The means are x̄ = 15 ÷ 5 = 3 and ȳ = 296 ÷ 5 = 59.2. The deviations of x are −2, −1, 0, 1 and 2, and the deviations of y are −6.2, −3.2, −0.2, 3.8 and 5.8. The slope is b = Σ(x − x̄)(y − ȳ) ÷ Σ(x − x̄)² = (12.4 + 3.2 + 0 + 3.8 + 11.6) ÷ (4 + 1 + 0 + 1 + 4) = 31 ÷ 10 = 3.1. The intercept is a = ȳ − b x̄ = 59.2 − 3.1 × 3 = 49.9. The model is therefore sales = 49.9 + 3.1 × advertising spend.
ExplanationJust two numbers, 49.9 and 3.1, now stand in for the data, and the same two numbers would stand in for 1,000 months just as well. For example, the model predicts that ₹6 lakh of advertising would bring 49.9 + 3.1 × 6 = ₹68.5 lakh of sales.
Histograms store the number of values in each range instead of the values themselves.
ExampleTwelve product prices, in rupees, are 20, 35, 40, 60, 80, 95, 120, 150, 240, 480, 900 and 1,800. In an equal-width histogram with three buckets, each bucket covers (1,800 − 0) ÷ 3 = 600 rupees, so the buckets are ₹0–600, ₹601–1,200 and ₹1,201–1,800, and they hold 10, 1 and 1 prices. In an equal-frequency histogram with three buckets, each bucket holds 12 ÷ 3 = 4 prices, so the buckets are ₹20–60, ₹80–150 and ₹240–1,800.
ExplanationIn both cases, three bucket counts replace twelve prices; on ShopMart's full catalogue, three buckets would replace 2,300 prices. Equal-width buckets are simple, but here they put almost every price into the first bucket. Equal-frequency buckets describe skewed data like this much better.
Clustering stores one representative for each cluster instead of every record.
ExampleA set of 1,00,000 customers is reduced to 50 cluster centres, each stored with the number of customers it represents.
ExplanationEach customer is represented by the centre of the cluster that the customer belongs to. The data shrinks from 1,00,000 rows to 50, which is 50 ÷ 1,00,000 = 0.05 per cent of its original size.
Sampling uses a subset of the data in place of the whole.
ExampleFrom 50 lakh bills, a 1 per cent simple random sample taken without replacement gives 50,00,000 × 0.01 = 50,000 bills. A stratified sample instead takes 1 per cent of the bills from each region. If the North has 20 lakh bills, the South 15 lakh, the East 10 lakh and the West 5 lakh, the sample takes 20,000, 15,000, 10,000 and 5,000 bills from them, which again totals 50,000, but now every region is guaranteed its fair share.
ExplanationThe cost of mining a sample depends on the size of the sample, not on the size of the full data set.
9.5 Discretisation and concept hierarchy generation
Discretisation divides a continuous attribute into intervals and replaces each value with the label of its interval.
Example (simple discretisation)Ages from 0 to 17 are labelled "minor", ages from 18 to 59 are labelled "adult", and ages of 60 and above are labelled "senior".
Example (the 3-4-5 rule)Annual incomes range from ₹0 to ₹9,00,000. At the most significant digit, which is the lakh, this range covers (9,00,000 − 0) ÷ 1,00,000 = 9 distinct values. The 3-4-5 rule states that 3, 6, 7 or 9 distinct values give 3 intervals; 2, 4 or 8 distinct values give 4 intervals; and 1, 5 or 10 distinct values give 5 intervals. Income is therefore split into three intervals: 0 to 3 lakh, 3 to 6 lakh and 6 to 9 lakh.
ExplanationThe 3-4-5 rule produces natural, round boundaries that people find easy to understand. Entropy-based discretisation works differently, because it chooses the boundaries that best separate a class label, such as the income cut-offs that best separate defaulters from other customers.
A concept hierarchy arranges the values of an attribute into levels, from detailed to general. The figure below shows a hierarchy for the location dimension.
Each city belongs to one state, and each state belongs to one country. A roll-up operation climbs this tree from the cities towards the country.
Example (automatic hierarchy generation)In ShopMart's address data, the country attribute has 1 distinct value, the state attribute has 28, the city attribute has 4,000 and the street attribute has 6 lakh.
ExplanationThe attribute with the fewest distinct values is placed at the top, which automatically gives the hierarchy country, state, city and street. This heuristic can fail, however. For example, the weekday attribute has only 7 values but belongs below the month attribute, which has 12, so experts should check the result.
9.6 Decision tree (as a reduction tool)
A decision tree is a tree in which each internal node tests an attribute, each branch represents an outcome of that test, and each leaf holds a class label. It is built from the top down, and at each node it chooses the attribute that splits the data best, using a measure such as information gain, gain ratio or the Gini index. Figure 11.1 in Chapter 11 shows a complete example.
ExampleA tree that predicts whether a customer buys a computer is built from four attributes: age, income, student status and credit rating. The finished tree tests only age, student status and credit rating.
ExplanationIncome never appears in the tree, which shows that it is not relevant to this class, so it can be removed from the data set. In this way, a decision tree both classifies records and reduces the number of dimensions.
Exam points
- Stepwise forward selection adds the best attribute each round; backward elimination removes the worst.
- PCA replaces correlated attributes with a smaller set of uncorrelated components.
- Parametric reduction stores model parameters; non-parametric reduction uses histograms, clustering or sampling.
- Stratified sampling takes a share from every group, so small groups are not missed.
- The 3-4-5 rule splits a range into 3, 4 or 5 natural intervals based on the number of distinct values at the most significant digit.
- In automatic hierarchy generation, the attribute with the fewest distinct values goes at the top.
Independent study notes for learning purposes. Not affiliated with or endorsed by any university, publisher or course provider. Product and company names are trademarks of their respective owners.