Data Reduction & Discretization

1Why reduce data at all?

Real datasets are huge — millions of rows and hundreds of columns. Mining algorithms on such data are slow and need a lot of memory. Data reduction produces a much smaller version of the dataset that still gives the same (or almost the same) analytical results.

Two benefits are named in the notes:

1. Less time and memory needed by data-mining algorithms.
2. Data becomes easier to visualise.

Where this fits — the four preprocessing tasks

This lesson is the third member of the data-preprocessing family introduced in Week 3:

The five data-reduction strategies

Memorise these five — they are the outline of the whole lesson:

2Data cube aggregation

A data cube stores multidimensional aggregated information. (Cubes are covered in detail in Week 5 – Data Warehousing; here you only need the idea.)

Picture sales data with three dimensions — item type, branch and year. Instead of storing every single sale, each cell of the cube holds an aggregate value (e.g. total sales of computers at Branch B in 2008).

One "slice" of a sales cube: annual sales per item type for each branch (values illustrative).

• Each attribute can have a concept hierarchy — e.g. branches can be grouped into regions based on their address — so you can analyse at multiple levels of abstraction.
• Cubes give fast access to pre-computed, summarised data, which benefits both OLAP (on-line analytical processing) and data mining.

3Attribute subset selection

Datasets may contain hundreds of attributes, many irrelevant or redundant.

Why not keep everything? Leaving out relevant attributes or keeping irrelevant ones confuses the mining algorithm → poor-quality patterns. A domain expert could pick attributes by hand, but that is slow and hard when the data's behaviour is not well known.

Extra benefit: fewer attributes in the discovered patterns → patterns are easier to understand.

Heuristic (greedy) methods

Trying every subset of n attributes means 2ⁿ possibilities — impossible for large n. So we use greedy heuristics: at each step make the choice that looks best right now (a locally optimal choice) hoping it leads to a globally optimal solution. In practice they come close to the optimum.

The four basic methods (Figure 3-2 in the notes):

4Dimensionality reduction

Here data encoding or transformations are applied to get a compressed representation of the original data.

• Wavelet transform – converts the data vector into a vector of wavelet coefficients; keeping only the strongest coefficients gives a compressed approximation.
• PCA – finds a small number of new axes (principal components) that capture most of the variation in the data, then represents each record using only those few components.

5Numerosity reduction

Replace the data with an alternative, smaller representation. Two families:

Regression

In linear regression the data are modelled to fit a straight line:

• y = response variable, x = predictor variable
• w (slope) and b (intercept) are the regression coefficients.

So instead of storing 10,000 (x, y) pairs you store just two numbers, w and b. That's the reduction.

Histograms

Histograms use binning to approximate the data distribution — a very popular form of data reduction. A histogram for attribute A splits A's values into disjoint subsets called buckets.

• Singleton bucket – a bucket holding just one attribute-value/frequency pair.
• Usually buckets represent continuous ranges of the attribute.

Partitioning rules — know all four:

We work through all of these with numbers in section 7.

Clustering and sampling (for completeness)

• Clustering – group similar records into clusters; store only the cluster representations (e.g. centre + diameter) instead of every record.
• Sampling – represent a large dataset by a much smaller random sample (e.g. simple random sample without/with replacement, cluster sample, stratified sample).

6Discretization & concept hierarchies

Discretization reduces the number of values of a continuous attribute by dividing its range into intervals. Interval labels then replace the actual values.

Ways to classify discretization methods

Concept hierarchies

Doing discretization recursively on an attribute gives a hierarchical (multiresolution) partitioning — a concept hierarchy. It lets you mine at multiple levels of abstraction.

A concept hierarchy replaces low-level concepts (numeric age values) with higher-level concepts (youth, middle-aged, senior).

Figure 3-3 — a concept hierarchy for price:

                        ($0 … $1000]
      ┌──────────┬───────────┼───────────┬────────────┐
 ($0…$200]  ($200…$400]  ($400…$600]  ($600…$800]  ($800…$1000]
  ┌───┴───┐   ┌───┴───┐     …            …            …
($0…$100] ($100…$200] ($200…$300] ($300…$400] …

Why bother, if detail is lost?

• Generalised data is more meaningful and easier to interpret.
• Gives a consistent representation of results across multiple mining tasks.
• Mining a reduced dataset needs fewer I/O operations → more efficient.

7Binning: equal-width vs equal-depth

The lecture video opens with why: data mining looks for hidden frequent patterns. If an attribute has a very large range of values, the same exact value rarely repeats, so patterns are hard to find. Breaking the range into bins (partitions) makes values "collide" so frequent patterns appear 00:00.

Equal-width partitioning (uniform grid) 00:37

Divide the range into N intervals of equal size. If A is the lowest value and B is the highest:

Bins: [A, A+W), [A+W, A+2W), … up to B. Simple and straightforward.

Equal-depth (equal-frequency) partitioning 01:44

Divide into N intervals each containing approximately the same number of samples. Good data scaling; but managing categorical attributes can be tricky.

8Smoothing noisy data with bins

Data can contain noise (random errors). After binning, we can smooth each bin 04:16. Using the price bins above:

1. Smoothing by bin means 04:30

Replace every value in a bin by the bin's mean.

2. Smoothing by bin medians 05:07

Same idea but replace by the median.

3. Smoothing by bin boundaries 05:18

The minimum and maximum of each bin are its boundaries. Every value is replaced by the closest boundary; the boundaries themselves stay.

9Histogram partitioning — a full worked example

The video then applies the histogram rules 06:29. Equal-width and equal-frequency work exactly like the binning above; V-Optimal chooses the partition with the least histogram variance; MaxDiff cuts at the β − 1 largest adjacent differences 07:21.

10Also asked in self-assessments: entropy-based discretization and the 3-4-5 rule

These two methods aren't in this week's PDF, but the 2024 cohort's Self-Assessment 4 asked about them (they're from the Han & Kamber textbook). Learn the idea and one example of each.

Entropy-based discretization (supervised)

The 3-4-5 rule (natural partitioning)

11Self-assignment (2024): binning in practice

12Quick revision sheet