Information Technology Reference
In-Depth Information
Database DB
C
1
L
1
Items
Sups.
Sups.
TID
Itemset
Itemset
100 A C D
200 B C E
300 A B C E
400 B E
{A} 2
{B} 3
{C} 3
{D} 1
{E} 3
{A} 2
{B} 3
{C} 3
{E} 3
Scan DB
L
2
C
2
C
2
Itemset
Sups.
Itemset Sups.
{A B} 1
{A C} 2
{A E} 1
{B C} 2
{B E} 3
{C E} 2
Itemset
{A B}
{A C}
{A E}
{B C}
{B E}
{C E}
{A C} 2
Scan DB
{B C} 2
{B E} 3
{C E} 2
L
3
C
3
C
3
Sup.
Sup.
Itemset
Itemset
Itemset
Scan DB
{B C E} 2
{B C E} 2
{B C E}
Fig. 12.1. Generation of candidate sets of items and sets of items
A DB is devided by M blocks in DIC algorithm. The first around of Apriori algorithm is
executed in the first block. The first and the second around of Apriori algorithm is executed in the
second block. The first, the second and the third around of Apriori algorithm is executed in the
third block and so on till the end of the DB. Return to the head of DB, the second and after around
is executed in the first block. the third and after around is executed in the second block and so on
till all frequent itemsets are confirmed. There is a dynamic adjusting procedure on frequent itemsets
and candidate itemsets. Another version of DIC algorithm is executed with random sampling.
12.3 FP-Growth Algorithm
Apriori algorithm or Apriori-like approach, which is based on an anti-monotone
Apriori heuristic: if any length
k
pattern is not frequent in the database, its length
