东北大学数据挖掘第5章.ppt

Formal definition of association rule I= {i1, i2, …, im} is an itemset, i.e. a set of items D is the task relevant data, which is a set of transactions where each transaction T is an itemset such that T?I if A is an itemset, we say T contains A iff A?T an association rule is of the form A?B, where A?I, B?I, and A?B =? the rule holds in D with support(A?B) = Prob(AB) confidence (A?B) = Prob(B|A) rules satisfying both min_sup and min_conf are strong an itemset contains k items is a k-itemset the number of transactions that contain an itemset is the frequency (or support count) of the itemset if an itemset satisfies min_sup, then it is a frequent itemset (or large itemset) Frequent, closed, and maximal itemset Frequent itemset An itemset X is frequent in a data set S if X satisfies min_sup Closed itemset An itemset X is closed in a data set S if there exists no proper super-itemset Y such that Y has the same support count as X in S. An itemset X is a closed frequent itemset in set S if X is both and frequent in S. Maximal frequent itemset An itemset X is a maximal frequent itemset in set S if X is frequent, and there exists no super-itemset Y such that X?Y and Y is frequent in S. Categories of association rules Based on the types of values Boolean association rule buys(X, “diapers”) ? buys(X, “beers”) [0.5%, 60%] quantitative association rule age(X, “30-39”)?income(X, “42-48K”)?buys(X, “computer”) [1%, 5%] Based on the dimensions of data single-dimensional association rule buys(X, “diapers”) ? buys(X, “beers”) [0.5%, 60%] multidimensional association rule age(X, “30-39”)?income(X, “42-48K”)?buys(X, “computer”) [1%, 75%] Based on the levels of abstractions single-level association rule age(X, “30-34”) ? buys(X, “computer”) [1%, 75%] multilevel association rule age(X, “30-32”) ? buys(X, “laptop computer”) [0.5%, 80%] age(X, “30-34”) ? buys(X, “computer”) [1%, 75%] Categories of association rules Two-step process of association rule