数据挖掘[6-5]Cluster-HierMeth (21)

1、Data Mining (Spring 2012), Tsinghua University0Association and Correlations Association and Correlations Efficient and Scalable Frequent Itemset Mining Methods Mining Various Kinds of Association Rules From Association Mining to Correlation Analysis Constraint-based Association MiningData Mining (Sp

2、ring 2012), Tsinghua University1可伸缩的频繁模式挖掘方法 频繁模式向下闭的属性频繁模式向下闭的属性 一个频繁项集的任何子集都是频繁的一个频繁项集的任何子集都是频繁的 如果如果 beer, diaper, nuts 是频繁的是频繁的, 那么那么 beer, diaper也是 即，每笔有即，每笔有beer, diaper, nuts的交易也包含的交易也包含beer, diaper 可伸缩挖掘方法：三种主要方法可伸缩挖掘方法：三种主要方法 Apriori (Agrawal & SrikantVLDB94) Freq. pattern growth (FPgro

3、wthHan, Pei & Yin SIGMOD00) 垂直数据格式方法垂直数据格式方法(CharmZaki & Hsiao SDM02)Data Mining (Spring 2012), Tsinghua University2算法：一个候选的生成算法：一个候选的生成-验证方法验证方法 算法修正原则算法修正原则: 如果有任何不频繁的项集，它的子集就不生成如果有任何不频繁的项集，它的子集就不生成/检验检验 (Agrawal & Srikant VLDB94, Mannila, et al. KDD 94) 方法方法: 起初，扫描起初，扫描 DB 得到频繁得到频繁1项集

4、项集 从长度从长度K的频繁项集生成长度为（的频繁项集生成长度为（K+1）的候选项集）的候选项集 在在DB中检验候选频繁项集中检验候选频繁项集 没有频繁或候选集生成时就终止没有频繁或候选集生成时就终止Data Mining (Spring 2012), Tsinghua University3The Apriori AlgorithmAn ExampleDatabase TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3Itemsetsu

5、pA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2whyHow？Supmin = 2Data Mining (Spring 2012), Tsinghua University4The Apriori AlgorithmPseudo-code:Ck: Candidate itemset of size kLk : frequent itemset of size

6、kL1 = 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 = candidates in Ck+1 with min_support endreturn k Lk;Data Mining (Spring 2012), Tsinghua Universi

7、ty5Important Details of Apriori 怎样生成候选集怎样生成候选集? Step 1: self-joining Lk Step 2: pruning 如何计算候选项集的支持度如何计算候选项集的支持度 候选生成的例子候选生成的例子L3=abc, abd, acd, ace, bcd 连接步连接步: L3*L3-abcd from abc and abd-acde from acd and ace 剪枝步剪枝步:-acde is removed because ade is not in L3C4=abcdData Mining (Spring 2012), Tsingh

8、ua University6How to Generate Candidates? 假设在假设在Lk-1的项目是按顺序列出的的项目是按顺序列出的 Step 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 q.itemk-1 Step 2: pruningforall itemsets c in Ck doforall (k-1)-s

9、ubsets s of c doif (s is not in Lk-1) then delete c from CkData Mining (Spring 2012), Tsinghua University7频繁模式挖掘的挑战频繁模式挖掘的挑战 挑战挑战 交易数据库的多重扫描交易数据库的多重扫描 大量的候选大量的候选 候选项集支持度计算量大候选项集支持度计算量大 改进的改进的 Apriori: 大意大意 减少交易数据库的扫描 减少候选的数量减少候选的数量 提高候选频繁项支持度计算效率提高候选频繁项支持度计算效率Data Mining (Spring 2012), Tsinghua Univ

10、ersity8Partition: Scan Database Only Twice 任何一个在任何一个在 DB是潜在的频繁项集，至少在是潜在的频繁项集，至少在DB的一个分区里也一定的一个分区里也一定 是频繁是频繁的的 扫描扫描 1: 部分数据库，找到当地的频繁模式部分数据库，找到当地的频繁模式 扫描扫描 2: 巩固全局频繁模式 A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. In VLDB95 Data Mining (S

11、pring 2012), Tsinghua University9DHP: Reduce the Number of Candidates 一个一个K项集，其相应哈希桶计数低于门槛数的不会是频繁的项集，其相应哈希桶计数低于门槛数的不会是频繁的 候选者候选者: a, b, c, d, e Hash entries: ab, ad, ae bd, be, de 频繁频繁1项集项集: a, b, d, e Ab不是一个候选的不是一个候选的2项集，如果项集，如果 ab, ad, ae 的计数总和低于支持门槛的计数总和低于支持门槛 J. Park, M. Chen, and P. Yu. An effe

12、ctive hash-based algorithm for mining association rules. In SIGMOD95Data Mining (Spring 2012), Tsinghua University10Sampling for Frequent Patterns 选择一个原始数据库的样本，用选择一个原始数据库的样本，用Apriori挖掘频繁模式挖掘频繁模式 扫描数据库修正样本里找到的频繁项集。扫描数据库修正样本里找到的频繁项集。闭合频繁模式的唯一边界检查例: 检查检查 abcd 而不是而不是ab, ac, , 等等. 再一次扫描数据库，找到遗漏的频繁模式再一次扫描

13、数据库，找到遗漏的频繁模式 H. Toivonen. Sampling large databases for association rules. In VLDB96Data Mining (Spring 2012), Tsinghua University11DIC: Reduce Number of Scans 一旦A和D被确定频繁，AD计数开始 the counting of BCD begins一旦所有BCD的长度为2的子集被确定为频繁的，就开始对BCD计数ABCDABCABDACD BCDABACBCADBDCDABCDItemset latticeAprioriTransacti

14、ons1-itemsets2-itemsets1-itemsets2-items3-itemsDICS. Brin R. Motwani, J. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD97Data Mining (Spring 2012), Tsinghua University12频繁模式挖掘的瓶颈多次数据库扫描开销太大挖掘长模式需要多次扫描，并产生大量的候选者 To find frequent itemset i1i2i100-

15、 # of scans: 100- # of Candidates: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 !瓶颈瓶颈: 候选生成和检验候选生成和检验我们能避免候选生成么我们能避免候选生成么?Data Mining (Spring 2012), Tsinghua University13没有候选生成的频繁模式挖掘没有候选生成的频繁模式挖掘 用局部频繁项从短模式生成长模式用局部频繁项从短模式生成长模式 “abc” 是一个频繁模式是一个频繁模式 得到所有含有得到所有含有“abc”的交易的交易” “d” is a local freque

16、nt item in DB|abc abcd is a frequent patternData Mining (Spring 2012), Tsinghua University14Construct FP-tree from a Transaction Database扫描扫描DB一次，找到频繁一次，找到频繁1项集项集 用频率降序排序选择频繁项用频率降序排序选择频繁项, f-list 再一次扫描再一次扫描DB，构建，构建FP树树min_support = 3TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf,

17、 c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, o, wf, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, pf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3F-list=f-c-a-b-m-pData Mining (Spring 2012), Tsinghua University15Benefits of the FP-tree

18、Structure Completeness（完备性）（完备性） 保存完整的频繁模式挖掘信息 不要破坏任何交易的长模式不要破坏任何交易的长模式 Compactness（紧致性）（紧致性） 去除不相关信息去除不相关信息非频繁项不用处理非频繁项不用处理 用频率降序排序的项目：更频繁地发生，更有可能被共享 不要比原始数据库更大（不要比原始数据库更大（不计算节点的链接和计数字段）Data Mining (Spring 2012), Tsinghua University16Partition Patterns and Databases 根据根据F列表将频繁模式分成子集列表将频繁模式分成子集 F-li

19、st=f-c-a-b-m-p 含有含有 p的模式的模式 含有含有m但是不含但是不含p的模式的模式 含有含有c但是不含但是不含a，b，m，p的模式的模式 模式模式 f 完整性和非冗余性完整性和非冗余性Data Mining (Spring 2012), Tsinghua University17Find Patterns Having P From P-conditional Database 从从Fp树的频繁项头表开始树的频繁项头表开始 按照每个频繁项链接遍历FP-树 积累所有项目积累所有项目p的转换前缀路径，形成的转换前缀路径，形成p的条件模式基的条件模式基条件模式基itemcond. pa

20、ttern basecf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3Data Mining (Spring 2012), Tsinghua University18From Conditional Pattern-bases to Conditional FP-trees 对于每个模式基对于每个模式基 积累基里的每个项目的计数积累基里的每个项目的计数 为模式基里的频繁基构建为模式基里的频繁基构建FP树树

21、m-conditional pattern base:fca:2, fcab:1f:3c:3a:3m-conditional FP-treeAll frequent patterns relate to mm, fm, cm, am, fcm, fam, cam, fcamf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3Data Mining (Spring 2012), Tsinghua University19Recursion: Mining Each Conditional FP-

22、treef:3c:3a:3m-conditional FP-treeCond. pattern base of “am”: (fc:3)f:3c:3am-conditional FP-treeCond. pattern base of “cm”: (f:3)f:3cm-conditional FP-treeCond. pattern base of “cam”: (f:3)f:3cam-conditional FP-treeData Mining (Spring 2012), Tsinghua University20A Special Case: Single Prefix Path in

23、FP-tree 假定一个假定一个FP树有一个共享的单一前缀路径树有一个共享的单一前缀路径p 挖掘可以分解成两部分挖掘可以分解成两部分 单一的前缀路径还原成一个节点 串联两部分的挖掘结果a2:n2a3:n3a1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=Data Mining (Spring 2012), Tsinghua University21Mining Frequent Patterns With FP-trees 想法想法: 频繁模式生长频繁模式生长 用模式和数据库分区递归生成频繁模式 方法方法 对于每

24、一个频繁项，构造它的条件模式基，然后它的条件FP-树 在在每个新创建的条件FP-树重复这过程 直到产生FP-树是空的，或者它只包含一个单路径单一路径将产生的所有子路径组合，其中每个都是一个频繁模式Data Mining (Spring 2012), Tsinghua University22FP-growth AlgorithmFP树的构建过程树的构建过程 :扫描交易数据库扫描交易数据库D一次，构建一次，构建F列表列表再一次扫描交易数据再一次扫描交易数据D用用 Insert_tree()构建构建FP树树 procedure FP_growth(Tree, ) (1) if Tree conta

25、ins a single path P then (2) for each combination ( ) of the nodes in the path P (3) generate pattern with support count = minimum support count of nodes in ; (4) else for each ai in the header of Tree (5) generate pattern = ai with support count = ai.support; (6) construct s conditional pattern bas

26、e and then s conditional FP tree Tree ; (7) if ; then (8) call FP_growth( ; ); TreeTreeData Mining (Spring 2012), Tsinghua University23FP-Growth vs. Apriori: Scalability With the Support Threshold010203040506070809010000.511.522.53Support threshold(%)Run time(sec.)D1 FP-grow th runtimeD1 Apriori run

27、timeData set T25I20D10KData Mining (Spring 2012), Tsinghua University24为何为何FP-Growth更优秀更优秀? 分治分治: 根据已获得的频繁模式分解挖掘任务和根据已获得的频繁模式分解挖掘任务和DB 集中搜集较小的数据库集中搜集较小的数据库 其他因素其他因素 无候选生成，无候选检验无候选生成，无候选检验 压缩数据库压缩数据库: FP树结构树结构 整个数据库不进行重复扫描整个数据库不进行重复扫描 基本OPS计数本地频繁物品和建设子FP-树，没有模式搜索和匹配Data Mining (Spring 2012), Tsinghua

28、 University25使用垂直数据格式挖掘频繁项集使用垂直数据格式挖掘频繁项集 水平数据格式水平数据格式: 事务数据格式事务数据格式 垂直格式垂直格式: t(AB) = T11, T25, tid-list: list of trans.-ids containing an itemset 通过垂直交集求闭合模式通过垂直交集求闭合模式 t(X) = t(Y): X and Y always happen together t(X) t(Y): transaction having X always has Y 使用使用diffset来加速挖掘过程来加速挖掘过程 Only keep trac

29、k of differences of tids t(X) = T1, T2, T3, t(XY) = T1, T3 Diffset (XY, X) = T2 Eclat/MaxEclat (Zaki et al. KDD97), VIPER(P. Shenoy et al.SIGMOD00), CHARM (Zaki & HsiaoSDM02)Data Mining (Spring 2012), Tsinghua University26挖掘闭频繁项集挖掘闭频繁项集: CLOSET Flist: 根据支持度升序列出所有频繁项集根据支持度升序列出所有频繁项集 Flist: d-a-f-

30、e-c 分割搜索空间分割搜索空间 有有d的模式的模式 有有d但是没有但是没有a的模式的模式 递归查找频繁封闭模式 每个有每个有d的交易也有的交易也有cfa cfad 事频繁封闭模式事频繁封闭模式 J. Pei, J. Han & R. Mao. CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets, DMKD00.TIDItems10a, c, d, e, f20a, b, e30c, e, f40a, c, d, f50c, e, fMin_sup=2Data Mining (Spring 2012), Tsinghua University27挖掘闭频繁项集挖掘闭频繁项集: CLOSET 在挖掘过程中直接搜索封闭频繁项在挖掘过程中直接搜索封闭频繁项 在挖掘中一旦确定封闭项，就修正搜索空间在挖掘中一旦确定封闭项，就修正搜索空间 修正规则修正规则 项目合并：如果每一个事务包含频繁项集X还包含项集Y但没有任何适当的Y的超集，那么XY就形成了一个频繁闭项集，没有必要搜寻任何含有X，但没有Y的项集.Data Mining (Spring 2012