大数据数据挖掘培训讲义-关联规则.ppt

Association Rules and Frequent Item Analysis Outline Transactions Frequent itemsets Subset Property Association rules Applications Transactions Example Transaction database: Example, 1 Transaction database: Example, 2 Definitions Item: attribute=value pair or simply value usually attributes are converted to binary flags for each value, e.g. product=“A” is written as “A” Itemset I : a subset of possible items Example: I = {A,B,E} (order unimportant) Transaction: (TID, itemset) TID is transaction ID Support and Frequent Itemsets Support of an itemset sup(I ) = no. of transactions t that support (i.e. contain) I In example database: sup ({A,B,E}) = 2, sup ({B,C}) = 4 Frequent itemset I is one with at least the minimum support count sup(I ) = minsup SUBSET PROPERTY Every subset of a frequent set is frequent! Q: Why is it so? A: Example: Suppose {A,B} is frequent. Since each occurrence of A,B includes both A and B, then both A and B must also be frequent Similar argument for larger itemsets Almost all association rule algorithms are based on this subset property Association Rules Association rule R : Itemset1 = Itemset2 Itemset1, 2 are disjoint and Itemset2 is non-empty meaning: if transaction includes Itemset1 then it also has Itemset2 Examples A,B = E,C A = B,C From Frequent Itemsets to Association Rules Q: Given frequent set {A,B,E}, what are possible association rules? A = B, E A, B = E A, E = B B = A, E B, E = A E = A, B __ = A,B,E (empty rule), or true = A,B,E Classification vs Association Rules Classification Rules Focus on one target field Specify class in all cases Measures: Accuracy Association Rules Many target fields Applicable in some cases Measures: Support, Confidence, Lift Rule Support and Confidence Suppose R : I = J is an association rule sup (R) = sup (I ? J) is the support count support of itemset I ? J (I or J) conf (R) = sup(J) / sup(R) is the confidence of R fraction of transactions with I ? J that have J Association ru