Mining Various Kinds of Association Rules

Basic boolean association rules ( $A \Rightarrow B$ ) are only the simplest case. Real warehouses need multi-level, multi-dimensional, quantitative, negative, rare and sequential rules.

1. Multi-Level Association Rules

Concept hierarchies (e.g. milk → dairy → food) allow rules at several levels of abstraction.

        ALL
         |
   ┌─────┴─────┐
 food       electronics
   |             |
 ┌─┴─┐         ┌─┴──┐
milk bread   computer phone
 │
 ┌┴──────┐
2% milk  skim milk

Approaches

Approach	Idea	Note
Uniform support (same min_sup at all levels)	One threshold for all levels	Low-level frequent itemsets are hard to find; high-level mining misses specific knowledge
Reduced support (level-by-level, decreasing min_sup)	$min\_sup(l+1) = min\_sup(l)/k$ or based on level cardinality	Ensures descendants of frequent ancestors are examined; extra passes/ancestor filtering needed

Rules mined: milk ⇒ bread at level 1, and skim milk ⇒ whole wheat bread at level 2 (more specific/useful).
Filtering / redundancy check: a rule at a lower level is redundant if an ancestor rule has similar support (i.e. its ancestor rule already covers it — same measure and support). Redundant rules are pruned.

Direct vs indirect data-mining

Direct: mine from the level-1 encoded (generalised) data.
Indirect: mine at the level-1 encoded data and then derive the higher-level ancestor rules.

2. Multi-Dimensional Association Rules

Attributes are divided into dimensions (predicates). Example: age(X,"20..29") ∧ occupation(X,"student") ⇒ buys(X,"laptop").

Type of rule	Predicates (dimensions)	Example
Single-dimensional (intra-dimensional)	Repeated same predicate	`buys(X,"milk") ⇒ buys(X,"bread")`
Multi-dimensional (inter-dimensional)	Different predicates	`age ∧ occupation ⇒ buys`
Hybrid	Repeats some dimensions	`age ∧ buys("milk") ⇒ buys("bread")`

Quantitative attributes (age, income) must be discretized — static discretization (pre-binned intervals) or dynamic discretization (bins adjusted during mining). Methods: ARCS (it uses dynamic discretization) and association rule clustering system, or quantitative rules on ranges.

Data structures

Multidimensional data cube: each dimension pair becomes an (n-D) cuboid; mining is done per cuboid — n-dimensional cube search space, cuboids are mined separately, one pass with a shared approach.
Datacube-based mining reduces the multiple database scans of Apriori and gives support/confidence from cube cells directly.

3. Quantitative Association Rules

Rule whose attributes include numeric ones: age(X, "30..39") ∧ income(X,"42K..48K") ⇒ buys(X,"high resolution TV").
Handling approaches:

Discretize numeric attributes into intervals (equal width/frequency, entropy, clustering).
Mine with Apriori on the discretized table; dynamic adjustment of interval boundaries during mining improves quality.
Combinations of dimensions with few distinct values (e.g. city, occupation) give more generalizable rules than many distinct values (e.g. item_id).

4. Negative Association Rules (Rare / Negative Patterns)

The absence of an item can also be informative: {bread} ⇒ ¬{milk} means customers who buy bread usually do not buy milk.
Two kinds: A ⇒ ¬B and ¬A ⇒ ¬B.

Why ordinary Apriori fails: most itemsets with a negated item are infrequent (the item is usually absent), and support is anti-monotone, so they are pruned early. Solutions: minimal support-based measures that ignore the negation component, e.g.

\text{sup}( eg A)=\frac{(|D|-|A|)}{|D|}\ \text{is large, so use}\ supp_{\text{minimal}}(A)=\frac{\sigma(A)}{|D|}\ \text{for both the positive and negated items}

Practical method: fix the positive itemset as frequent, then test candidate negations with a correlation measure such as lift — keep the rule only if it is negatively correlated:

\text{lift}(A, eg B)=\frac{P(A\cup eg B)}{P(A)P( eg B)} < 1

Other measures for the negation test: $\chi^2$ test, all-confidence, max-confidence, Kulczynski, cosine, interest factor. Generic uses are for the rare patterns that are pruned by a single high min_sup: use multiple minimum supports (MS-Apriori) where each item has its own min_sup, with the minimum of the two thresholds governing a rule's support (the "support of the antecedent bound" rule for antisupport), plus the Rare Item Penalty / item rarity / C(θ) of the a priori-like extension.

5. Mining Rare Patterns and Negative Patterns — Multiple Support Apriori

Each item $i_j$ has its own $MS(i_j)$ ; a rule's minimum support is:

\text{MS}(\text{itemset})=\min_{i \in \text{itemset}} MS(i) \quad \text{(or the largest such that it can still be generated)}

$\Rightarrow$ frequent itemsets with a rare item are no longer automatically pruned, and "if a rare item's min_sup is met by its own supersets only..." → the support difference constraint filters misleading rules:

|supp(A)-supp(B)| \le \phi \quad(\text{user-set max support difference, e.g. } \phi = 0.05)

6. Sequential / Time-Series Pattern Mining

Sequences are ordered lists of itemsets with time stamps; rules have the form A ⇒ B with a time gap:

\text{X} \Rightarrow_{\ (g_1,g_2)\ } \text{Y}:\quad \text{transactions } X \text{ and } Y \text{ occur at least } g_1 \text{ and at most } g_2 \text{ apart}

Measures: support = number of data sequences containing the pattern (frequency), and confidence as with association rules. Algorithms for frequent sequential patterns: GSP (generalised sequential pattern), PrefixSpan (pattern-growth), SPADE (vertical), CloSpan for closed sequences; time-series analyses add cyclic/seasonal patterns (association rules with periodicity constraints: e.g.

P = \{ \text{seasonal}, \text{partial}, \text{full} \}

periodicity classification).

Findings are often represented in a pattern graph / DS-graph, and the underlying structure can widen into a subsequence cover in the analysis.

Example: sequence <{a,b}{c}{a,d,e}> and pattern <{a}{d,e}> — the pattern is a subsequence/subset sequence.
A sequence $s$ is a subsequence of $s'$ if every itemset of $s$ is a subset of some itemset of $s'$ in order.

7. Mining Frequent Subgraphs and Other Structured Patterns

Graph structures: enumeration of frequent subgraphs/subtrees; rules over them (e.g. chemical compounds: C-C-C ⇒ ring structure); used in bioinformatics, cheminformatics, social networks and XML/JSON tree mining. The same anti-monotone pruning applies with a subgraph isomorphism test as the join predicate, and canonical ordering to avoid duplicates.

8. Summary Table

Rule kind	Form	Key extra requirement
Boolean association	`X ⇒ Y`	min_sup, min_conf
Multi-level	`X_{li} ⇒ Y_{lj}`	concept hierarchy, level-wise/ancestor pruning
Multi-dimensional	`P_1 ∧ P_2 ⇒ Q`	n-dimensional cube/array, predicate splits
Quantitative	numeric ranges	dynamic discretization
Negative / rare	`X ⇒ ¬Y`	min_sup per item / lift < 1 / rare-item penalty
Sequential	`X ⇒_{\ g\ } Y`	transaction order and time gaps
Subgraph / tree	graph patterns	isomorphism tests, canonical representation

9. Exam Points

Explain multi-level association rules with uniform vs reduced support and redundancy filtering — 10 marks.
Explain multi-dimensional / quantitative rules and how numeric attributes are handled — 5-7 marks.
Explain sequential pattern mining (GSP idea) with time-gap constraints — 5-7 marks.
Short notes on negative/rare pattern mining and multiple minimum supports — 5 marks.
Mining frequent subgraphs and structured patterns — 3-5 marks.

Mining Various Kinds of Association Rules