Associative Classification

1. Motivation

Both classification and association mining are central data mining tasks and they share much in common — a rule of the form

\text{IF } \underbrace{\text{age}=youth \wedge income=high \wedge student=yes}_{X \text{ (itemset/antecedent)}} \text{ THEN } \underbrace{buys=yes}_{y \text{ (class)}}

Associative classification mines the class association rules (CARs) and then uses a selected subset as a classifier. It exploits the strong, interpretable rules of association mining while building a predictive model.

2. Class Association Rules (CARs)

\text{CAR} = \{X \Rightarrow y\},\qquad X \subseteq I \text{ (non-empty itemset)}, \ y \in C \text{ (class label)}

The rule set is usually restricted to rules whose consequent is a class attribute, which reduces the search space dramatically compared to general association rule mining.

Measure	Definition	Use
Support	$\dfrac{\sigma(X \cup \{y\})}{\|D\|}$	Frequency threshold (min support)
Confidence	$\dfrac{\sigma(X\cup\{y\})}{\sigma(X)}$	Reliability threshold (min confidence)
All-confidence / lift	as in association rules	Prune non-interesting rules

\text{min\_sup} \wedge \text{min\_conf} \text{ thresholds} \longrightarrow \text{only "strong" class rules kept}

3. General Framework (three phases)

 PHASE 1  MINE       : discover strong CARs (Apriori / FP-growth variant, e.g. CBA-RG, CMAR-CRG)
 PHASE 2  PRUNE      : reduce the rule set (database coverage, chi-square, pessimistic error pruning)
 PHASE 3  CLASSIFY   : predict the class of a new tuple using the retained rules
                         - by voting (rank rules by support/confidence, weighted votes)
                         - by a best-rule decision list / class-based ordering

4. Algorithms

Algorithm	Mining method	Rule selection / pruning	Classification strategy
CBA (Classification Based on Associations)	Apriori-style CAR mining, multiple rules per item	TDB (Total Description length) + database coverage, keep the best rules	Rules sorted by confidence, support, rule size → best rule wins (a decision list)
CMAR (Classification based on Multiple Association Rules)	FP-tree based, class-distribution rules	Chi-square pruning + coverage pruning, then generalised rule matching (top- $k$ covering rules)	Weighted voting among the top- $k$ matched rules (weights = confidence × support)
CPAR (Classification based on PRedictive Association Rules)	Grows rules directly like FOIL (no candidate generation)	Rule-growth with expected accuracy; stops when all positives covered or accuracy < threshold	Best- $k$ rules, weighted Laplace voting

5. Worked Example

Data (14 tuples, class buys_computer). Confidence of candidate rules:

CAR	support	confidence	kept (min_sup = 20%, min_conf = 60%)?
age=youth → buys=no	3/14 = 21.4%	3/5 = 60%	Yes
student=no → buys=no	4/14 = 28.6%	4/7 = 57%	No
income=high ∧ student=yes → buys=yes	2/14 = 14.3%	2/2 = 100%	No (support too low)
income=medium → buys=yes	4/14 = 28.6%	4/6 = 67%	Yes
age=mid ∧ income=high → buys=yes	2/14 = 14.3%	100%	No (support)

After pruning by database coverage (each training tuple must be covered by a rule; discard redundant rules that add no new coverage), the final ordered decision list might be:

1. IF student=yes AND income=low  THEN buys=yes   (conf 0.80)
2. IF income=medium               THEN buys=yes   (conf 0.67)
3. IF age=youth                   THEN buys=no    (conf 0.60)
default: buys=no

Classify tuple (student=yes, income=low, age=youth): rule 1 fires first → buys=yes.

6. Why Associative Classification Works Well

Completeness of search: association mining systematically explores the whole itemset lattice (with pruning), so multi-attribute interactions are found that greedy tree induction may miss.
Interpretability is retained — the model is still a readable IF-THEN rule set.
Rules can be ranked and filtered by two independent thresholds (support and confidence), giving fine control over the accuracy/coverage trade-off.
Empirical studies (CBA/CMAR/CPAR, Liu et al.) report accuracy comparable to or better than C4.5, especially on many-attribute or correlated data.

7. Difficulties

Rule explosion — a large number of CARs may satisfy both thresholds; mining and pruning are expensive (mitigated by pruning with chi-square, database coverage, expected accuracy).
Overlapping/conflicting rules for the same tuple → classification strategy (best rule vs weighted voting) strongly affects accuracy.
Long rules with low support can overfit; rare classes may be under-represented in the mined rules (class-imbalance problem), though class-based mining helps.
Choosing the optimal min_sup/min_conf is data dependent; noisy data degrade the rule set (careful rule pruning needed).

8. Comparison

Aspect	Associative classification	Decision tree	Rule induction (sequential covering)
Search	Complete itemset lattice (Apriori/FP)	Greedy attribute selection	Greedy rule growth
Rule form	Multiple rules per class, unordered	One path per leaf	Ordered/separate-and-conquer
Thresholds	Support and confidence	Information gain / Gini	Foil gain, accuracy
Interpretability	High	High	High
Cost	Higher (mining + pruning)	Low	Medium
Typical result	Often more accurate on correlated data	Fast and simple	Moderate

9. Exam Points

Define associative classification and CARs; explain the three-phase framework with algorithms (CBA, CMAR, CPAR) — 10 marks (frequent).
Compare associative classification with decision tree induction and rule induction — 5 marks.
Explain rule pruning by database coverage — 5 marks.
Worked example: find CARs from a small table given support/confidence — 5-7 marks.

Associative Classification