University:
California State University, Northridge
Course:
ME 595A-Z | Experimental Topics Courses in Mechanical Engineering
Academic year:

2011
Views:

446

Pages:

22
Author:

Samson Frank

Mining Frequent Patterns, Associations and Correlations Week 3 Part 1 Table 8.3 The substitution matrix of amino acids. Figure 8.8 Scoring two potential pairwise alignments, (a) and (b), of amino acids. 6 Figure 9.1 A sample graph data set. Figure 9.2 Frequent graph. 7 Figure 9.14 A ch hemical database e. 8 What Is Frequent Pattern Analysis? • Frequent pattern: a pattern for itemsets, subsequences, substructures, etc. that occurs frequently in a data set • First proposed by Agrawal, Imielinski, and Swami in 1993, in the context of frequent itemsets and association rule mining 9 Why Is Frequent Pattern Mining I Important? ? • Discloses an intrinsic and important property of data sets • Forms the foundation for many essential data mining tasks and applications – What products were often purchased together?— Beer and diapers? – What are the subsequent purchases after buying a PC? – What kinds of DNA are sensitive to this new drug? – Can we automatically classify web documents? 10 Topics of Frequent Pattern Mining (1) • Based on the kinds of patterns to be mined – Frequent itemset mining – Sequential pattern mining – Structured pattern mining 11 Topics of Frequent Pattern Mining (2) • Based on the levels of abstraction involved in the rule set – Single Single‐level level association rules – Multi‐level association rules 12 Topics of Frequent Pattern Mining (3) • Based on the number of data dimensions involved in the rule – Single Single‐dimensional dimensional association rules – Multi‐dimensional association rules 13 Association Rule Mining Process • Fi Find d allll frequent f i itemsets – Join steps – Prune steps • Generate “strong” association rules from the frequent itemsets 14 Basic Concepts of Frequent Itemsets • Let I = {I1, I2, …., Im} be a set of items • LLett D, D the th ttask‐relevant k l t data, d t be b a sett off database d t b transactions where each transaction T is a set of items such that T ⊆ I • Each transaction is associated with an identifier, called TID. • Let A be a set of items • A transaction T is said to contain A if and only if A ⊆ T 15 How to Generate Frequent Itemset? • Suppose the items in Lk‐1 are listed in an order • The join step: To find Lk, a set of candidate k‐itemsets, Ck, is generated by joining Lk‐1 with itself. Let l1 and l2 be itemsets in Lk‐1.The resulting itemset formed by joining l1 and l2 is l1[1], l1[2], [2] …, l1[k [k‐2] 2], l1[k [k‐1] 1], l2[k [k‐1] 1] • The prune step: Scan data set D and compare candidate support pp count of Ck with minimum support pp count. Remove candidate itemsets that whose support count is less than minimum support count, resulting in Lk. 16 Apriori Algorithm • Initially, I iti ll scan DB once to t gett ffrequentt 1 1‐itemset it t • Generate length (k+1) candidate itemsets from length k frequent itemsets • Prune length (k+1) candidate itemsets with Apriori property – Apriori property: All nonempty subsets of a frequent itemset must also be frequent • Test the candidates against g DB • Terminate when no frequent or candidate set can be g generated 17 Figure 5.4 The Apriori A alg gorithm fo or discove ering freq quent itemsets for mining Boole ean assoc ciation rulles. 18 Transactional Database TID List of item_IDs item IDs T100 I1, I2, I5 T200 I2, I4 T300 I2, I3 T400 I1, I2, I4 T500 I1,, I3 T600 I2, I3 T700 I1, I3 T800 I1 I2, I1, I2 I3, I3 I5 T900 I1, I2, I3 Table 5.1 5 1 Transactional data for an AllElectronics branch. branch 19 Minimum support count = 2 Figure 5.2 Generation of candidate itemsets and frequent itemsets, where the minimum support count is 2. 20 Generating Strong Association Rules • From the frequent q itemsets • For each frequent itemset l, generate all nonempty subset of l • For every nonempty subset s of l, • Output the rule “s (l – s)” • If support_count(l) t t(l) / support_count(s) t t( ) ≥ min_conf, i f where min_conf is the minimum confidence threshold • Rules that satisfy both a minimum support threshold and a minimum confidence threshold are called strong 1 Support • The rule A B holds in the transaction set D with support s – support, t s, probability b bilit that th t a ttransaction ti contains t i A and B – support (A B) = P (A B) 2 Confidence • The rule A B has confidence c in the transaction set D – confidence, fid c, conditional diti l probability b bilit th thatt a transaction having A also contains B – confidence (A B) = P (B | A) Confidence ( A ⇒ B ) = P ( B | A) = support ( A ∪ B ) support_count ( A ∪ B ) = support pp ( A) support pp _count ( A) 3 Generating Association Rules from Frequent Itemsets • Example p 5.4: Suppose pp the data contain the frequent q itemset l = {I1, I2, I5}. What are the association rules that can be generated from l? If the minimum confidence threshold is 70% then which rules are strong? 70%, – – – – – – I1 ^I2 ‐> I5, confidence = 2/4 = 50% I1 ^I5 ‐> I2, confidence = 2/2 = 100% I2 ^I5 ‐> I1, confidence = 2/2 = 100% I1 ‐> I2 ^ I5, confidence = 2/6 = 33% I2 ‐> I1 ^ I5,, confidence = 2/7 / = 29% I5 ‐> I1 ^ I2, confidence = 2/2 = 100% 1 Exercise 5.3 A database has five transactions. Let min_sup = 60% and min_conf = 80%. TID Items_bought T100 {M, O, N, K, E, Y} T200 {D O, {D, O N, N K, K E, E Y} T300 {M, A, K, E} T400 {M, U, C, K, Y} T500 {C, O, O, K, I, E} (a) Find all frequent itemsets. (b) List all of the strong association rules (with support s and confidence c) matching following meta‐rule, where X is a variable representing customers, and itemi denotes variables representing items (e.g., “A”, A , “B”, B , etc.): 4 ∀x ∈ transaction, buys( X , item1 ) ∧ buys ( X , item2 ) ⇒ buys( X , item3 ) [s, c] Challenges of Frequent Pattern Mining • Challenges – Multiple scans of transaction database – Huge uge number u be o of ca candidates d dates – Tedious workload of support counting for candidates • Improving Apriori – Reduce passes of transaction database scans – Shrink number of candidates – Facilitate support counting of candidates 5

Mining Frequent Patterns, Associations and Correlations, Part 1

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 3

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 4

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 5

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 6

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 7

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 8

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 9

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 10

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 11

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 12

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 13

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 14

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 15

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 16

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 17

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 18

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 19

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 20

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 21

Mining Frequent Patterns, Associations and Correlations, Part 1 - Page 22

of 22

Description

Free up your schedule!

Take 5 seconds to unlock