国内国际新闻社会生活新闻采编中心

1、Mining Association RulesPart IIbtbo精选网址 alds7/btbo/Data Mining OverviewData MiningData warehouses and OLAP (On Line Analytical Processing.)Association Rules MiningClustering: Hierarchical and Partitional approachesClassification: Decision Trees and Bayesian classifiersSequential Patterns MiningAdvan

2、ced topics: outlier detection, web miningProblem StatementI = i1, i2, , im: a set of literals, called itemsTransaction T: a set of items s.t. T IDatabase D: a set of transactionsA transaction contains X, a set of items in I, if X TAn association rule is an implication of the form X Y, where X,Y IThe

3、 rule X Y holds in the transaction set D with confidence c if c% of transactions in D that contain X also contain YThe rule X Y has support s in the transaction set D if s% of transactions in D contain X YFind all rules that have support and confidence greater than user-specified min support and min

4、 confidenceProblem Decomposition1. Find all sets of items that have minimum support (frequent itemsets)2. Use the frequent itemsets to generate the desired rulesMining Frequent Itemsets: the Key StepFind the frequent itemsets: the sets of items that have minimum supportA subset of a frequent itemset

5、 must also be a frequent itemseti.e., if AB is a frequent itemset, both A and B should be a frequent itemsetIteratively find frequent itemsets with cardinality from 1 to k (k-itemset)Use the frequent itemsets to generate association rules.The Apriori AlgorithmLk: Set of frequent itemsets of size k (

6、those with min support)Ck: Set of candidate itemset of size k (potentially frequent itemsets)L1 = frequent items;for (k = 1; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = can

7、didates in Ck+1 with min_support endreturn k Lk;How to Generate Candidates?Suppose the items in Lk-1 are listed in orderStep 1: self-joining Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 = 10Compute iceberg queries efficiently by Apriori:F