Trang 3
Definition: Frequent Itemset • Itemset – A collection of one or more items TID Items • Example: {Milk, Bread, Diaper} – k-itemset 1 Bread, Milk • An itemset that contains k items 2 Bread, Diaper, Beer, Eggs • Support count () 3 Milk, Diaper, Beer, Coke – Frequency of occurrence of an itemset 4 Bread, Milk, Diaper, Beer – E.g. ({Milk, Bread,Diaper}) = 2 5 Bread, Milk, Diaper, Coke • Support – Fraction of transactions that contain an itemset – E.g. s({Milk, Bread, Diaper}) = 2/5 • Frequent Itemset – An itemset whose support is greater than or equal to a minsup threshold 3
Trang 4
Frequent Itemsets Mining TID Transactions • Minimum support level 100 { A, B, E } 50% 200 { B, D } – {A},{B},{C},{A,B}, {A,C} 300 { A, B, E } 400 { A, C } • How to link this to Data 500 { B, C } Cube? 600 { A, C } 700 { A, B } 800 { A, B, C, E } 900 { A, B, C } 1000 { A, C, E }
Trang 5
Three Different Views of FIM • Transactional Database TID Items 1 Bread, Milk – How we do store a transactional 2 Bread, Diaper, Beer, Eggs database? 3 Milk, Diaper, Beer, Coke • Horizontal, Vertical, Transaction-Item 4 Bread, Milk, Diaper, Beer Pair 5 Bread, Milk, Diaper, Coke • Binary Matrix • Bipartite Graph • How does the FIM formulated in these different settings? 5
Trang 6
Frequent Itemset Generation null A B C D E AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE Given d items, there are 2d possible candidate itemsets ABCDE 6
Trang 7
Frequent Itemset Generation • Brute-force approach: – Each itemset in the lattice is a candidate frequent itemset – Count the support of each candidate by scanning the database Transactions List of Candidates TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs N 3 Milk, Diaper, Beer, Coke M 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke – Match each transaction against every candidatew – Complexity ~ O(NMw) => Expensive since M = 2d !!! 7
Trang 8
Reducing Number of Candidates • Apriori principle: – If an itemset is frequent, then all of its subsets must also be frequent • Apriori principle holds due to the following property of the support measure: X,Y :(X Y) s(X) s(Y) – Support of an itemset never exceeds the support of its subsets – This is known as the anti-monotone property of support 8
Trang 9
Illustrating Apriori Principle nullnull AA BB CC DD EE ABAB ACAC ADAD AEAE BCBC BDBD BEBE CDCD CECE DEDE Found to be Infrequent ABCABC ABDABD ABEABE ACDACD ACEACE ADEADE BCDBCD BCEBCE BDEBDE CDECDE ABCDABCD ABCEABCE ABDEABDE ACDEACDE BCDEBCDE Pruned supersets ABCDEABCDE 9
Trang 10
Illustrating Apriori Principle Item Count Items (1-itemsets) Bread 4 Coke 2 Milk 4 Itemset Count Pairs (2-itemsets) Beer 3 {Bread,Milk} 3 Diaper 4 {Bread,Beer} 2 (No need to generate Eggs 1 {Bread,Diaper} 3 candidates involving Coke {Milk,Beer} 2 or Eggs) {Milk,Diaper} 3 {Beer,Diaper} 3 Minimum Support = 3 Triplets (3-itemsets) If every subset is considered, Itemset Count 6C + 6C + 6C = 41 {Bread,Milk,Diaper} 3 1 2 3 With support-based pruning, 6 + 6 + 1 = 13 10
Trang 11
Apriori R. Agrawal and R. Srikant. Fast algorithms for mining association rules. VLDB, 487-499, 1994
Trang 13
How to Generate Candidates? • Suppose the items in Lk-1 are listed in an order • Step 1: self-joining Lk-1 insert into Ck select p.item1, p.item2, …, p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, …, p.itemk-2=q.itemk-2, p.itemk-1 < q.itemk-1 • Step 2: pruning forall itemsets c in Ck do forall (k-1)-subsets s of c do if (s is not in Lk-1) then delete c from Ck 13
Trang 14
Challenges of Frequent Itemset Mining • Challenges – Multiple scans of transaction database – Huge number of candidates – Tedious workload of support counting for candidates • Improving Apriori: general ideas – Reduce passes of transaction database scans – Shrink number of candidates – Facilitate support counting of candidates 14
Trang 15
Alternative Methods for Frequent Itemset Generation • Representation of Database – horizontal vs vertical data layout Horizontal Data Layout Vertical Data Layout TID Items A B C D E 1 A,B,E 1 1 2 2 1 2 B,C,D 4 2 3 4 3 3 C,E 5 5 4 5 6 4 A,C,D 6 7 8 9 5 A,B,C,D 7 8 9 6 A,E 8 10 7 A,B 9 8 A,B,C 9 A,C,D 10 B 15
Trang 16
ECLAT • For each item, store a list of transaction ids (tids) Horizontal Data Layout Vertical Data Layout TID Items A B C D E 1 A,B,E 1 1 2 2 1 2 B,C,D 4 2 3 4 3 3 C,E 5 5 4 5 6 4 A,C,D 6 7 8 9 5 A,B,C,D 7 8 9 6 A,E 8 10 7 A,B 9 8 A,B,C 9 A,C,D 10 B TID-list 16
Trang 17
ECLAT • Determine support of any k-itemset by intersecting tid-lists of two of its (k-1) subsets. A B AB 1 1 1 4 2 → 5 5 5 7 6 7 8 7 8 8 10 9 • 3 traversal approaches: – top-down, bottom-up and hybrid • Advantage: very fast support counting • Disadvantage: intermediate tid-lists may become too large for memory 17
Trang 20
FP-growth Algorithm • Use a compressed representation of the database using an FP-tree • Once an FP-tree has been constructed, it uses a recursive divide-and-conquer approach to mine the frequent itemsets 20
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!