Data reduction and discretisation
Study notes on data reduction and discretisation: why they are used, main methods (numerosity reduction, dimensionality reduction, binning, supervised and unsupervised discretisation), formulas, worked examples (equal-width, equal-frequency, ChiMerge), common mistakes and exam guidance.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Data reduction and discretisation let engineers make large, noisy, or high-dimensional datasets smaller and easier to process without losing the information needed for modelling. You use these methods when preparing data for mining algorithms (classification, association, clustering) or for storing/querying large warehouses where speed and model accuracy matter.
Key ideas
Define every key term before using it.
Data reduction — a set of methods that produce a reduced representation of the original data while preserving its analytical value. Assumption: reduced representation keeps patterns relevant to the task.
Dimensionality reduction — a subtype of data reduction that reduces the number of attributes (columns). Assumption: some attributes are redundant or noisy. (See the later topic Principal component analysis for a specific method.)
Numerosity reduction — a subtype of data reduction that reduces the number of records (rows) or the data volume using models, sampling, or aggregation.
Feature selection (or attribute subset selection) — choose a subset of original attributes; assumption: some attributes are irrelevant or redundant for the task.
Discretisation — the process of converting a continuous attribute into a finite set of intervals (bins). It produces a categorical attribute from numeric values. Assumption: the discretised values capture the relevant differences for learning or summarisation.
Unsupervised discretisation — methods that use only the attribute values (no class labels). Examples: equal-width binning and equal-frequency (quantile) binning, clustering-based discretisation, histogram construction.
Supervised discretisation — methods that use class labels when creating intervals, aiming to preserve class purity inside bins. Examples: entropy-based discretisation, ChiMerge, MDL (minimum description length) discretisation.
Binning — dividing the range of a continuous attribute into consecutive, non-overlapping intervals (bins). Two common strategies:
- Equal-width binning — each bin has the same numeric width.
- Equal-frequency binning — each bin has (roughly) the same number of records.
Histogram — a graphical summary of numeric data using bins on the x-axis and frequencies on the y-axis. To draw: x-axis labelled with bin ranges; y-axis labelled with frequency or density; draw bars whose heights equal frequency.
Exact statement used in many exams (ChiMerge):
- ChiMerge algorithm (exact description): start with each distinct value as its own interval. Repeatedly compute the Chi-square statistic for every pair of adjacent intervals; merge the pair with the smallest Chi-square if that value is less than a pre-chosen threshold (critical value for Chi-square with degrees of freedom = (#classes − 1)). Stop when no adjacent pair has Chi-square below threshold or when the desired number of intervals is reached. Assumptions: class labels are correct; initial ordering by attribute value is meaningful.
Where derivations are asked: derive the Chi-square value for two adjacent intervals by constructing a 2-D contingency table (interval × class) and using the Pearson Chi-square statistic (see Formulas). In exams you should show the contingency table and the four expected counts for two classes, then compute the sum (O−E)^2/E over cells.
Note on supervised vs unsupervised choice: use supervised discretisation when the downstream task is classification and class labels exist; use unsupervised when labels are absent or when you want an unbiased summary.
Formulas
width = (max − min) / k — width of each bin in equal-width binning. Symbols: max = maximum attribute value (same units as data), min = minimum value, k = number of bins (unitless). Applies for numeric continuous attributes. Choosing k (rules of thumb): k = ⌈1 + log2 n⌉ (Sturges), k ≈ ⌈2·n^{1/3}⌉ (Rice), or use Freedman–Diaconis bin width h = 2·IQR·n^{−1/3} and set k ≈ (max − min)/h.
n_k ≈ n / k — approximate number of records per bin in equal-frequency binning. Symbols: n = total records (unitless), k = number of bins (unitless).
x̄ = (1/n) · Σ_{i=1..n} x_i — sample mean. Symbols: x̄ = sample mean (same units as x), n = sample size (unitless), x_i = ith value (units). Applies to any numeric sample.
s^2 = (1/(n−1)) · Σ_{i=1..n} (x_i − x̄)^2 — sample variance. Symbols: s^2 = sample variance (units^2), x̄ = sample mean.
χ^2 = Σ_{cells} (O − E)^2 / E — Pearson Chi-square statistic for contingency table. Symbols: O = observed count in a cell (unitless), E = expected count (unitless). Degrees of freedom for two-class, two-interval table = (rows−1)·(cols−1) = 1. Use the appropriate Chi-square critical value (e.g. 3.841 for α=0.05 with df=1) when deciding merges.
Entropy(S) = − Σ_{c in classes} p_c · log2(p_c) — entropy of set S. Symbols: p_c = fraction of records in S with class c (unitless). Used in entropy-based supervised discretisation. Convention: terms with p_c = 0 contribute 0.
Information gain of a cut: Gain = Entropy(parent) − Σ_{i} (|child_i|/|parent|) · Entropy(child_i) — used to choose best split.
Worked examples
Example 1 — Equal-width binning (numerical, step-by-step) Data (age in years): 22, 25, 47, 35, 46, 23, 40, 28, 30, 33. Choose k = 3 bins.
- Sort (optional): 22, 23, 25, 28, 30, 33, 35, 40, 46, 47.
- Compute min = 22 years, max = 47 years, range = 25 years.
- Compute bin width:
width = (47 − 22)/3 = 25/3 = 8.333... years. - Define bins (closed on left, open on right except last): Bin1: [22.000, 30.333) Bin2: [30.333, 38.667) Bin3: [38.667, 47.000]
- Assign values to bins: Bin1 = {22,23,25,28,30} (5 records), Bin2 = {33,35} (2 records), Bin3 = {40,46,47} (3 records).
- Optionally label bins by midpoints: Midpoint1 = (22 + 30.333)/2 ≈ 26.166 years; Midpoint2 ≈ 34.5 years; Midpoint3 ≈ 42.833 years. Final discretised result: values replaced by bin ids or midpoints. Bold answer: Bin counts = 5, 2, 3.
Example 2 — Equal-frequency (quantile) binning on same data with k = 3
- Sorted data: 22, 23, 25, 28, 30, 33, 35, 40, 46, 47 (n=10).
- Target per bin ≈ n/k = 10/3 ≈ 3.33 → use 3, 3, 4 records.
- Bins: Bin1 = {22,23,25} ; Bin2 = {28,30,33} ; Bin3 = {35,40,46,47}.
- Cut points are between 25 and 28, and between 33 and 35. Final bin sizes: 3, 3, 4.
Example 3 — ChiMerge supervised discretisation (small trace) Data: (value, class) pairs sorted: (2,P), (3,P), (5,P), (6,N), (8,N), (9,N). P = positive class, N = negative class.
- Start with each distinct value as an interval: I1={2:P}, I2={3:P}, I3={5:P}, I4={6:N}, I5={8:N}, I6={9:N}.
- Compute χ^2 for each adjacent pair and merge the pair with smallest χ^2 if it is below threshold (use α=0.05, df=1 → critical ≈ 3.841).
- χ^2(I1,I2) = 0 (both P), merge → new I12={2,3 : P,P}.
- χ^2(I12,I3) = 0 (all P), merge → new I123={2,3,5 : P,P,P}.
- χ^2(I123,I4): compute contingency table. Observed counts: left P=3 N=0; right P=0 N=1. Combined totals: P=3 N=1. Expected left P = 3·3/4 = 2.25; left N = 1·3/4 = 0.75; right P = 3·1/4 = 0.75; right N = 1·1/4 = 0.25. Compute χ^2 = (3−2.25)^2/2.25 + (0−0.75)^2/0.75 + (0−0.75)^2/0.75 + (1−0.25)^2/0.25 = 0.25 + 0.75 + 0.75 + 2.25 = 4.0.
- Compare to critical 3.841: 4.0 > 3.841 → do NOT merge I123 and I4.
- For the right side, merge I5 and I6 since both are N: χ^2=0 → I56={8,9:N,N}.
- Now consider merging I4 (6:N) with I56 (8,9:N,N): both N so χ^2=0 → merge → I456={6,8,9 : N,N,N}. Final intervals: {2,3,5} labelled P and {6,8,9} labelled N. Bold final discretisation: two intervals with high class purity.
Common mistakes
- Using equal-width when data are highly skewed; this produces empty or overloaded bins.
- Forgetting to recalc expected counts correctly in Chi-square: E = (row_total·col_total)/grand_total.
- Treating the Chi-square critical value as fixed without noting the degrees of freedom and significance level.
- Applying χ^2 when expected counts in any cell are too small (rule of thumb: each expected count ≥ 5); merge or combine bins first, or use an exact test in small samples.
- Trying to teach PCA here in full; PCA belongs to the later topic Principal component analysis for data reduction — reference it instead.
For your exam
Question types you will see:
- Definitions and short notes: define discretisation, numerosity reduction, compare equal-width vs equal-frequency.
- Method description: step-by-step description (and pseudo-code) of ChiMerge or equal-width binning.
- Derivations: derive the Chi-square formula for two-by-two tables and show how to compute expected counts.
- Numericals: compute binning cut points, assign values to bins, compute Chi-square between adjacent intervals.
- Programs/algorithms: write or trace pseudocode for binning or ChiMerge on small data. What a full-marks answer includes:
- Clear definitions (bold the term), assumptions, and the algorithm steps.
- For numericals: show every step (sort data, compute min/max, width, assignments), show intermediate numbers and the final discretised values.
- For ChiMerge/entropy: show contingency tables, expected counts, χ^2 or entropy computations and thresholds used.
Quick check
- What is the formula for equal-width bin size for a numeric attribute?
- Give one advantage of equal-frequency binning over equal-width binning.
- In ChiMerge, what is the degrees of freedom for a two-class comparison of two adjacent intervals and the commonly used α=0.05 critical χ^2 value (check in verify)? Answers: 1) width = (max − min)/k. 2) It guarantees roughly equal record counts per bin (handles skew). 3) df = 1; commonly used critical χ^2 ≈ 3.841 (α=0.05, df=1).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?