Data Discretization and Concept Hierarchy Generation

1. Discretization — Definition and Need

Discretization reduces the number of values of a continuous attribute by partitioning its range into a finite number of intervals (labels). Needed because:

Many algorithms (Apriori, ID3 variants, rough sets, rule induction) require categorical attributes.
Fewer distinct values → smaller search space, faster learning, less overfitting.
Intervals like low / medium / high are interpretable to business users.

\text{Discretise}: x \in [\min,\max] \longrightarrow \{I_1, I_2, \dots, I_k\},\qquad I_i \cap I_j = \emptyset

2. Classification of Discretization Methods

 DISCRETIZATION METHODS
  |-- Unsupervised (no class label)
  |     |-- Binning: equal-width, equal-frequency
  |     |-- Histogram analysis
  |     |-- Clustering-based (k-means on the attribute)
  |-- Supervised (uses class label)
        |-- Entropy / information-gain based (MDLP - Fayyad & Irani)
        |-- ChiMerge / Chi2 (statistical merging of adjacent intervals)
        |-- Class-attribute contingency / rule based

3. Binning (unsupervised, simplest)

Data: sorted prices 4, 8, 15, 21, 21, 24, 25, 28, 34

Method	Rule	Result
Equal-width	width $=\dfrac{\max-\min}{k}=\dfrac{34-4}{3}=10$	[4-14], [14-24], [24-34]
Equal-frequency (depth 3)	same number of values per bin	(4,8,15), (21,21,24), (25,28,34)

Equal-width handles skewed data badly (empty/overfull bins); equal-frequency handles skew but breaks similar values apart.

4. Entropy-Based (Supervised) Discretization

Choose the cut point that maximises information gain (minimises class entropy after the split).

\text{Entropy}(S)=-\sum_{i=1}^{c} p_i \log_2 p_i,\qquad H(S) = 0 \text{ (pure)},\ \ 1 \text{ (2-class even)}

\text{Gain}(S,T)=H(S)-\frac{|S_1|}{|S|}H(S_1)-\frac{|S_2|}{|S|}H(S_2)

Numerical example — 8 records (5 Yes, 3 No) on attribute $x$ :

x	1	2	3	4	5	6	7	8
class	Y	Y	N	N	N	Y	Y	Y

H(S) = -\frac{5}{8}\log_2\frac{5}{8}-\frac{3}{8}\log_2\frac{3}{8}=0.954

Cut point	Left set	Right set	Weighted entropy	Gain
1.5	(1Y) H=0	(4Y,3N) H=0.985	0.862	0.092 (best)
3.5	(2Y,1N) H=0.918	(3Y,2N) H=0.971	0.951	0.003
4.5	(2Y,2N) H=1.000	(3Y,1N) H=0.811	0.906	0.048

Cut point 1.5 gives the highest gain, so the first boundary is 1.5; the recursion continues (MDLP stopping rule: $\text{Gain}(A,T) > \dfrac{\log_2(N-1)}{N}+\dfrac{\Delta(A,T)}{N}$ ).

5. ChiMerge (Supervised)

Start with each distinct value in its own interval.
Compute $\chi^2$ between every pair of adjacent intervals using class frequencies.
Merge the pair with the lowest $\chi^2$ .
Repeat until all pairs exceed the threshold (e.g. $\chi^2 > 4.61$ at 90% confidence for 1 d.o.f., 2 classes).

\chi^{2}=\sum_{i=1}^{2}\sum_{j=1}^{k}\frac{(o_{ij}-e_{ij})^{2}}{e_{ij}}

6. Concept Hierarchies

A concept hierarchy maps low-level values/attributes to higher, more general concepts, enabling roll-up, generalisation and multi-level mining.

Forms of hierarchies

Form	Example
Schema hierarchy (explicit in schema)	`street < city < state < country`
Set-grouping hierarchy	`{Urdu, Hindi, Tamil} ⊂ South-Asian languages`, `{English, Spanish} ⊂ European languages`
Operation-derived hierarchy	`email: abc@cs.xyz.edu → cs.xyz.edu → edu` (derived by parsing operations)
Rule-based hierarchy	`age < 20 = youth`, `20-40 = adult`, `> 40 = senior`

                  ALL
                   |
        ┌──────────┴──────────┐
      Asia                 Europe
    ┌───┴────┐           ┌────┴────┐
  India   China       France     Germany
   │                   │           │
 ┌─┴─┐               Paris      Berlin
Mumbai  Delhi
   │
Andheri(West)

Automatic generation of a schema hierarchy (nominal data)

Collect the set of attributes specified by the user (e.g. street, city, state, country).
For each attribute count the number of distinct values.
The attribute with the smallest number of distinct values goes highest in the hierarchy (most general); remove attributes with only one distinct value (no generalisation ability).
Sort remaining attributes by increasing distinct-value count.

Rule of thumb: at each level keep 5-10 intervals (Miller's 7 ± 2 limit for human comprehension).

Numeric → concept hierarchy: binning, histogram analysis, clustering, entropy-based discretization, plus range rules (low/medium/high), and network/segmentation rules.

7. Worked Conversion

age (numeric) → intervals → concepts, and salary grouped:

 age: 1..20 -> youth | 21..40 -> adult | 41..120 -> senior
 salary: 0-30k -> low | 30k-70k -> medium | above 70k -> high
 qty:        any x  -> {small (x<=10), medium (10<x<=50), large (x>50)}

8. Exam Points

Define discretization; explain binning (equal-width vs equal-frequency) with numerical — 5-7 marks (frequent).
Entropy-based discretization numerical (choose best split) — 5 marks.
Explain concept hierarchies with forms and automatic generation rules — 7-10 marks.
Short note on ChiMerge — 3-5 marks.

Data Discretization and Concept Hierarchy Generation