dm.cs.tu-dortmund.de/en/mlbits/frequent-pattern-apriori-algorithm/
Apriori Algorithm – Lecture Notes
\(p\lt{}q\) , that match on their first \(k-2\) elements
\(p \in F_{k-1}:\)
( 1 2 3)
\(\downarrow\)
( 1 2 3 4) \(\in C_k\)
\(\uparrow\)
\(q \in F_{k-1}:\)
( 1 2 4)
Step 2: Pruning
Remove all candidate itemsets [...] itemsets. Need to check only the \(k-2\) itemsets not used in join.
Example:
\(F_3 = \{ (1~ 2~ 3), (1~ 2~ 4), (1~ 3~ 4), (1~ 3~ 5), (2~ 3~ 4)\}\)
After join:
\(\{ (1~ 2~ 3~ 4), (1~ 3~ 4~ 5)\}\)
pruning step: [...] w\)
\(C_2\)
{ A B }
{ A D }
{ A E }
{ B D }
{ B E }
{ D E }
scan \(D\)
\(\longrightarrow\)
\(C_2\)
{ A B }
7
{ A D }
5
{ A E }
4
{ B D }
7
{ B E }
6
{ D E }
4
filter
\(\longrightarrow\)
\(F_2\)
{ A B …
