Efficient and Scalable Frequent Itemset Mining Methods

Efficient and Scalable Frequent Itemset Mining Methods

1. Basic Concepts

Let $I = \{i_1, i_2, \dots, i_m\}$ be a set of items and $D$ a set of transactions, each transaction being a subset of $I$.

Term	Definition
Itemset	A set of one or more items; a $k$-itemset has $k$ items
Support count $\sigma(X)$	Number of transactions containing itemset $X$
Support	$supp(X) = \sigma(X)/|D|$
Frequent itemset	$supp(X) \ge min\_sup$ (a user-given threshold)
Association rule	$A \Rightarrow B$ where $A, B \subset I$ and $A \cap B = \emptyset$
Confidence	$conf(A \Rightarrow B) = \dfrac{\sigma(A \cup B)}{\sigma(A)} = \dfrac{supp(A\cup B)}{supp(A)}$

Apriori (downward-closure) property: every non-empty subset of a frequent itemset is also frequent; equivalently, if an itemset is infrequent, all of its supersets are infrequent.

This anti-monotone property is what makes pruning possible.

Number of possible itemsets:

2. Apriori Algorithm

Apriori(D, min_sup):
  L1 = {frequent 1-itemsets}
  for (k = 2; L(k-1) != empty; k++) do
      Ck = apriori_gen(L(k-1))          // JOIN  +  PRUNE
      for each transaction t in D do     // one full DB scan per level
          Ct = subset(Ck, t)
          for each c in Ct: c.count++
      Lk = { c in Ck  |  c.count >= min_sup }
  return union of all Lk

• Join step: $L_{k-1} \bowtie L_{k-1}$ — join pairs sharing the first $k-2$ items to form $k$-itemsets.
• Prune step: delete a candidate if any of its $(k-1)$-subsets is not in $L_{k-1}$.

3. Worked Example (min_sup = 2, i.e. 20%)

Transactions: T1 {I1,I2,I5}, T2 {I2,I4}, T3 {I2,I3}, T4 {I1,I2,I4}, T5 {I1,I3}, T6 {I2,I3}, T7 {I1,I3}, T8 {I1,I2,I3,I5}, T9 {I1,I2,I3}

Level	Candidates (with count)	Frequent itemsets kept
C1	I1:6, I2:7, I3:6, I4:2, I5:2	L1 = {I1:6, I2:7, I3:6, I4:2, I5:2}
C2	I1I2:4, I1I3:4, I1I4:1, I1I5:2, I2I3:4, I2I4:2, I2I5:2, I3I4:0, I3I5:1, I4I5:0	L2 = {I1I2:4, I1I3:4, I1I5:2, I2I3:4, I2I4:2, I2I5:2}
C3	I1I2I3:2, I1I2I5:2 (after pruning I1I3I5, I2I3I4, I2I3I5, I2I4I5 because of infrequent subsets)	L3 = {I1I2I3:2, I1I2I5:2}
C4	I1I2I3I5 — pruned because {I1,I3,I5} ∉ L3	L4 = ∅ → stop

Rule generation from {I1, I2, I5} (support count 2, min_conf = 70%):

Rule	Confidence	Kept?
I1 ∧ I2 ⇒ I5	2/4 = 50%	No
I1 ∧ I5 ⇒ I2	2/2 = 100%	Yes
I2 ∧ I5 ⇒ I1	2/2 = 100%	Yes
I1 ⇒ I2 ∧ I5	2/6 = 33%	No
I2 ⇒ I1 ∧ I5	2/7 = 29%	No
I5 ⇒ I1 ∧ I2	2/2 = 100%	Yes

4. Efficiency-Based Improvements on Apriori

Technique	Idea
Hash-based itemset counting (DHP)	Hash the $k$-itemsets into buckets; an infrequent bucket prunes all its candidates
Transaction reduction	Delete transactions containing no $k$-frequent itemset — they cannot contain $(k+1)$-frequent itemsets
Partitioning (SON)	Partition DB, mine local frequent itemsets in parallel passes, then verify globally — only 2 DB scans
Sampling	Mine on a sample of the data; verify results against the full DB
Dynamic itemset counting (DIC)	Add candidates at different points in the scan rather than level-by-level; fewer passes

Apriori bottlenecks: (i) generates a huge number of candidates at each level, (ii) scans the whole database once per level, (iii) counting work is proportional to number of candidates × transactions.

5. FP-Growth (Frequent Pattern Growth) — no candidate generation

Step 1 — build the FP-tree (2 DB scans):

1. Scan 1: count item frequencies; discard items below $min\_sup$.
2. Sort each transaction by descending frequency, drop infrequent items.
3. Scan 2: insert each transaction into the tree, sharing common prefixes; maintain a header table with node links.

Ordered for our example (I2:7, I1:6, I3:6, I4:2, I5:2): T1 {I2,I1,I5}, T2 {I2,I4}, T3 {I2,I3}, T4 {I2,I1,I4}, T5 {I1,I3}, T6 {I2,I3}, T7 {I1,I3}, T8 {I2,I1,I3,I5}, T9 {I2,I1,I3}

                       { }  (root)
                        |
                      [I2:7]
                    /    |    \
              [I1:4]   [I4:1] [I3:2]
             /     \             |
        [I5:1]  [I3:2]         [I3:2]
          |
       [I4:1] ...   (header links: I1, I3, I4, I5 chains)
   Header table:  I2:7 -> link | I1:6 -> link | I3:6 -> link | I4:2 -> link | I5:2 -> link

Step 2 — mine recursively by conditional pattern bases:

Suffix (frequent item)	Conditional pattern base	Conditional FP-tree	Frequent itemsets found
I5	{I2,I1}:1, {I2,I1,I3}:1	<I2:2, I1:2>	{I2,I5}:2, {I1,I5}:2, {I2,I1,I5}:2
I4	{I2,I1}:1, {I2}:1	I2:2	{I2,I4}:2
I3	{I2,I1}:2, {I2}:2, {I1}:2	<I2:4, I1:2>	{I2,I3}:4, {I1,I3}:4, {I2,I1,I3}:2
I1	{I2}:4	I2:4	{I2,I1}:4

Advantages: only 2 database scans, no candidate generation, compact tree, faster than Apriori on dense/many-pattern data; disadvantage: recursion cost and memory for a large tree (solved by parallel/partitioned FP-growth).

6. Eclat — vertical data format (tidsets)

Convert each item into a tidset (list of transaction ids containing it), then intersect tidsets.

 I1: {1,4,5,7,8,9}     I2: {1,2,3,4,6,8,9}     I3: {3,5,6,7,8,9}     I4: {2,4}     I5: {1,8}

Itemset	Intersection	Support
{I1,I2}	{1,4,8,9}	4
{I1,I3}	{5,7,8,9}	4
{I1,I5}	{1,8}	2
{I2,I3}	{3,6,8,9}	4
{I2,I4}	{2,4}	2
{I2,I5}	{1,8}	2
{I1,I2,I3}	{8,9}	2
{I1,I2,I5}	{1,8}	2

Eclat mines depth-first over equivalence classes; diffset variants reduce memory. Cost is dominated by tidset intersection $\bigcap$, so compressed bit-vectors speed it up greatly.

7. Scalability Comparison

Method	DB scans	Candidate generation	Data structure	Strength
Apriori	$k_{max}+1$	Yes	Horizontal (tids)	Simple, widely taught
Apriori + hashing/partitioning/DIC	2-3	Yes	Various	Reduces passes
FP-growth	2	No	FP-tree (prefix)	Fast on dense data, no candidates
Eclat	2	No	Vertical tidsets	Fast support counting via intersections

8. Exam Points

• State the Apriori property and run Apriori on a given transaction table with $min\_sup$ — 10 marks (very frequent numerical).
• Generate association rules with confidence from the frequent itemsets — 5 marks.
• Explain FP-tree construction and FP-growth with the given data — 10 marks.
• Compare Apriori, FP-growth and Eclat — 5 marks.
• Techniques to improve Apriori efficiency (hash, partition, sampling, DIC) — 5-7 marks.