数据挖掘apriori算法.pdfVIP

APRIORI Algorithm Professor Anita Wasilewska Lecture Notes The Apriori Algorithm: Basics The Apriori Algorithm is an influential algorithm for mining frequent itemsets for boolean association rules. Key Concepts : • Frequent Itemsets: The sets of item which has minimum support (denoted by Li for ith-Itemset). • Apriori Property: Any subset of frequent itemset must be frequent. • Join Operation: To find Lk , a set of candidate k-itemsets is generated by joining Lk-1 with itself. The Apriori Algorithm in a Nutshell • Find the frequent itemsets: the sets of items that have minimum support – A subset of a frequent itemset must also be a frequent itemset • i.e., if {AB} is a frequent itemset, both {A} and {B} should be a frequent itemset – Iteratively find frequent itemsets with cardinality from 1 to k (k-itemset) • Use the frequent itemsets to generate association rules. The Apriori Algorithm : Pseudo code • Join Step: Ck is generated by joining Lk-1with itself • Prune Step: Any (k-1)-itemset that is not frequent cannot be a subset of a frequent k-itemset • Pseudo-code: C : Candidate itemset of size k k L : frequent itemset of size k k L1 = {frequent items}; for (k = 1; Lk !=∅; k++) do begin C = candidates generated from L ; k+1 k for each transaction t in database do increment the count of all candidates in C k+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return ∪ L ; k k The Apriori Algorithm: Example TID