Association Mining to Correlation Analysis

Association Mining to Correlation Analysis

1. The Problem with Support and Confidence

Support and confidence alone are not sufficient — they can report a strong, "interesting" rule that is in fact misleading because the two items are statistically negatively correlated (they avoid each other).

Classic counter-example. 10,000 transactions about games: 6,000 contain computer games, 7,500 contain videos, 4,000 contain both.

• Rule: computer games ⇒ videos
• support $= 4000/10000 = 40\%$ (high), confidence $= 4000/6000 = 66\%$ (high) → Apriori calls this a strong rule.
• But $P(\text{videos}) = 75\%$, so buying videos is more likely when not buying computer games (or 75% overall).

The rule is misleading: computer games and videos are actually substitutes, but confidence hid that.

2. Correlation Measures

(a) Lift (interest / improvement)

• $=1$ → $A$ and $B$ are independent; $>1$ → positively correlated; $<1$ → negatively correlated.
  Limitation: lift is not symmetric-friendly and can be inflated for rare itemsets with very low support; it can be large even for itemsets with small support (instability).

(b) $\chi^2$ (chi-square) test — the standard test of independence for nominal data. Build a $2\times2$ contingency table for $A$ and $B$:

	$B$	$\bar B$	Row total
$A$	$o_{11}$	$o_{12}$	$a$
$\bar A$	$o_{21}$	$o_{22}$	$c$
Col total	$b$	$d$	$N$

For the games example (A = games, B = videos), with 2000 buying neither:

	videos	¬videos	total
games	4000	2000	6000
¬games	3500	500	4000
total	7500	2500	10000

Degrees of freedom $=(2-1)(2-1)=1$; the critical value at 0.05 significance is 3.841. Since $555.6 \gg 3.841$, reject independence → the two items are strongly correlated — and because observed < expected in the $(A,B)$ cell, the correlation is negative.
Limitation of $\chi^2$: it indicates correlation but not the direction (positive/negative) or the strength; also sensitive to the number of tuples.

(c) Cosine / all-confidence-type measures (null-invariant)

Null-invariance property: the measure should not be affected by the number of transactions containing neither item (the ¬A, ¬B count) — important because real transaction data is extremely sparse, and $\chi^2$/lift behave badly there.

Measure	Formula	Null-invariant?
Lift	$P(A\cup B)/(P(A)P(B))$	No
$\chi^2$	as above	No
Cosine	$P(A\cup B)/\sqrt{P(A)P(B)}$	Yes
Kulczynski (Kulc)	$\frac{1}{2}\left(P(A|B)+P(B|A)\right)$	Yes
All-confidence	$\frac{P(A\cup B)}{\max\{P(A),P(B)\}}$	Yes
Max-confidence	$\max\{P(A|B),P(B|A)\}$	Yes

3. Null-Invariance Example (why it matters)

Two datasets, 100 transactions each (min_sup = 30%):

Dataset	$P(A,B)$	$P(A,\bar B)$	$P(\bar A,B)$	Lift	$\chi^2$	Cosine	Kulc
$D_1$ (few nulls)	0.25	0.05	0.05	10.0	500	0.79	0.83
$D_2$ (many nulls)	0.25	0.05	0.05	10.0	500	0.79	0.83
$D_3$ (very many nulls, e.g. 1,000,000 txns)	0.25	0.05	0.05	~1.0	huge/thin	high	0.83

The actual behaviour: for a dataset where only 0.25% of a million tuples contain $A$ and $B$ jointly, lift and $\chi^2$ change dramatically with the null count, while cosine, Kulczynski, all-confidence and max-confidence stay stable. That is why a balanced combination is recommended:

4. Recommended Practice — Imbalance Ratio (IR)

For the contingency table of $A$ and $B$:

Decision rule using Kulczynski + IR

Kulczynski	IR	Interpretation
high (close to 1)	low	Strong positive correlation — interesting rule
high	high	One item is much rarer than the other (a one-way implication, e.g. coke ⇒ ¬sprite type patterns)
low	any	No/weak or negative correlation — prune

If Kulc ≈ 0.5 and IR ≈ 0, the two items are independent and the rule should be discarded even if its confidence is high.

5. Why Confidence Can Be Misleading — Formal Note

confidence(A⇒B) = P(B|A) ignores $P(B)$. Adding the correlation test converts a "strong" rule into an "interesting" rule. Hence the mining flow becomes:

 frequent itemsets (Apriori/FP-growth)
        |
        v
 strong rules  (support >= min_sup, confidence >= min_conf)
        |
        v
 correlation / interestingness filter  (lift, chi^2, Kulc + IR, cosine)
        |
        v
 truly interesting rules -> knowledge

6. Other Rule Interestingness Measures

Measure	Formula	Notes
Support	$P(A\cup B)$	Coverage
Confidence	$P(B|A)$	Reliability, ignores $P(B)$
Lift	ratio	Symmetric
Conviction	$\dfrac{1-P(B)}{1-conf(A\Rightarrow B)}$	$\infty$ for perfect rule; sensitive to $P(B)=1$
Leverage	$P(A\cup B)-P(A)P(B)$	Difference from independence
Jaccard	$\dfrac{P(A\cup B)}{P(A)+P(B)-P(A\cup B)}$	Null-invariant
Interest (PS)	$\sqrt{\text{lift}\times\text{support}}$	Combines both
Gini / $\phi$-coefficient	variants	Symmetric association

Lift vs support example: A lift of 2 with support 0.01 is less reliable than lift of 1.5 with support 0.20, so many systems use an interest factor combining both.

7. Exam Points

• Explain with example why support and confidence alone are insufficient; compute lift and $\chi^2$ to show negative correlation — 10 marks (very frequent).
• Define and compare cosine, Kulczynski, all-confidence and the null-invariance property; explain the imbalance ratio — 5-7 marks.
• Short notes: lift, conviction, leverage — 3-5 marks.
• Draw the flow "frequent itemsets → strong rules → correlation filter" — 3 marks.