Support Vector Machines

Associative Classification

1. Basic Idea

Associative classification (AC) builds a classifier from class association rules (CARs) — the frequent/strong rules that have a class label as the consequent. It combines association-rule mining (Apriori/FP-growth) with classification, and usually beats C4.5 because it can use any subset of attributes in the antecedent.

Rules are mined with the standard constraints: $supp \ge min\_sup$ and $conf \ge min\_conf$ (often only 1-2% support and 50% confidence are needed).

2. Why AC is More Powerful than Rule Induction

 Decision-tree/rule-induction path:   outlook=sunny AND humidity=high AND wind=weak -> No play
                                        (a fixed chain of tests)

 Class association rule:              humidity=high AND wind=weak -> No play
                                        (only the truly relevant conditions; no ordering constraint)

ACalso finds rules that a greedy separate-and-conquer learner would never grow, e.g. {temp=mild, windy=true} → play=yes without mentioning outlook.

3. Step 1 — Mining Class Association Rules (worked example)

Training set (class: buys_computer):

rid	age	income	student	credit	buys
1	youth	high	no	fair	no
2	youth	high	no	excellent	no
3	middle	high	no	fair	yes
4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes
6	senior	low	yes	excellent	no
7	middle	low	yes	excellent	yes

With $min\_sup = 2$, $min\_conf = 60\%$, candidates mined include:

RCAR (rule item)	Support count	Support %	Confidence
age=youth, student=no → buys=no	2	28.6	100%
income=low, student=yes → buys=no	1	-	(below min_sup)
age=senior, credit=fair → buys=yes	2	28.6	100%
student=yes, credit=excellent → buys=no	1	-	reject (min_sup)
income=low → buys=yes	2	28.6	66.7%
age=middle → buys=yes	2	28.6	100%

Mining is done as rule-item (ritem) enumeration with support counting (the consequent is fixed per class tree), and pruning uses the Apriori property plus pessimistic error pruning on confidence.

4. Step 2 — Pruning into a Classifier

More than one rule may match a test tuple → conflict resolution is decided by the rule ranking:

CBA (Classification Based on Associations, Liu et al.) — rules ordered by descending $\langle confidence, support\rangle$, and an unordered rule set is kept (rules that match a test case vote). Standard rule pruning removes rules whose pessimistic error (with a Laplace-type adjustment) is higher than the majority-class default rule.

CMAR (Classification based on Multiple Association Rules, Li et al.) — stores rules in an CR-tree, prunes with weighted $\chi^2$ testing and prune-by-coverage, then classifies with weighted voting:

The class with the largest total score wins (CMAR's $\chi^2$ pruning removes a rule $r_1$ that is a subset of a higher-confidence $r_2$ when both have the same consequent and $\chi^2$ shows no significant difference).

5. Rule Ranking / Scoring Measures for AC

Measure	Formula	Use
Support	$\frac{|X\cup c|}{|D|}$	Frequency
Confidence	$\frac{|X\cup c|}{|X|}$	Reliability, primary sort key
Laplace / expected error	$\frac{|X\cup c|+1}{|X|+k}$	Compensates small support
$\chi^2$	contingency statistic	Removes statistically redundant rules
Lift	$\frac{conf}{P(c)}$	Interest, useful for the minority class

Preference when confidence ties: more general (shorter, higher-support) rule first.

6. Classifying an Unseen Tuple

 t = (age=youth, income=high, student=no, credit=fair)
 Matching CARs (confidence, support):
   age=youth AND student=no  -> buys=no   (100%, 28.6%)
   age=youth                 -> buys=no   (75% , 42.9%)
   income=high               -> buys=no   (66.7%, 42.9%)
 → CBA picks the first (highest confidence)                  => buys = no
 → CMAR weighted vote: no gets 1.0^2/cov + 0.75^2/cov + ... => buys = no (largest score)

7. Advantages and Limitations

Advantages

• Uses frequent itemset search → can find rules with arbitrary attribute subsets (including rules that ignore irrelevant attributes).
• Generally more accurate than C4.5 on many UCI datasets; particularly good on high-dimensional and multi-class data.
• Produces interpretable IF-THEN rules with support and confidence, so prediction comes with a justification (ranked evidence).
• Naturally handles numeric attributes after discretisation, and can be tuned with the support/confidence thresholds.
• Easy to incorporate cost-sensitive/weighted items (weighted AC) and to train on only the top-k rules.

Limitations

• Rule explosion: mining all CARs is expensive; a huge number of rules must be pruned and stored (memory/time). FPGrowth-based and rule-item pruning (CBA's rule-item tree, CMAR's FP-tree) are used to control this.
• Conflicts: overlapping rules need a ranking/voting scheme; the effects of the thresholds are hard to predict.
• Sensitive to the choice of $min\_sup$ / $min\_conf$; low thresholds hurt speed, high thresholds lose rules.
• Training is slower (multiple phases: mining + pruning + ranking) than decision-tree induction; incremental/online training is not natural.

8. Comparison Table

Aspect	Decision tree (C4.5)	Rule induction (RIPPER)	Associative classification (CBA, CMAR)
Search	Greedy, one path at a time	Greedy separate-and-conquer	Global frequent-itemset search
Rules found	Root-to-leaf paths	One rule at a time, negatives removed	All CARs above thresholds
Conflict handling	No conflict (single path)	Ordered rule set	Ranking + voting
Accuracy	Baseline	Similar to C4.5	Often higher
Cost	Fast	Medium	Slowest training
Interpretability	High	High	High (rules + support/confidence)

9. Exam Points

• Define class association rules and explain how associative classification differs from rule-based classification — 7-10 marks (frequent).
• Mine CARs for a small given table with $min\_sup/min\_conf$ and classify a test tuple — 10 marks.
• Explain CBA vs CMAR (rule ranking, $\chi^2$ pruning, weighted voting formula) — 7 marks.
• Advantages and limitations of associative classification — 5 marks.