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

1、Association 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 Mining,可伸缩的频繁模式挖掘方法,频繁模式向下闭的属性 一个频繁项集的任何子集都是频繁的 如果 beer, diaper, nut

2、s 是频繁的, 那么 beer, diaper也是 即，每笔有beer, diaper, nuts的交易也包含beer, diaper 可伸缩挖掘方法：三种主要方法 Apriori (Agrawal 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

3、+1 with min_support end return k Lk;,Important 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 L3 C4=abcd,How to Generate Candidates?,

4、假设在Lk-1的项目是按顺序列出的 Step 1: self-joining Lk-1 insert into Ck select p.item1, p.item2, , p.itemk-1, q.itemk-1 from Lk-1 p, Lk-1 q where p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1 Step 2: pruning forall itemsets c in Ck do forall (k-1)-subsets s of c do if (s is not in Lk-1) then delete

5、 c from Ck,频繁模式挖掘的挑战,挑战 交易数据库的多重扫描 大量的候选 候选项集支持度计算量大 改进的 Apriori: 大意 减少交易数据库的扫描 减少候选的数量 提高候选频繁项支持度计算效率,Partition: Scan Database Only Twice,任何一个在 DB是潜在的频繁项集，至少在DB的一个分区里也一定 是频繁的 扫描 1: 部分数据库，找到当地的频繁模式 扫描 2: 巩固全局频繁模式 A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining associati

6、on in large databases. In VLDB95,DHP: 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 effective hash-based algorithm for mining association rules

7、. In SIGMOD95,Sampling for Frequent Patterns,选择一个原始数据库的样本，用Apriori挖掘频繁模式 扫描数据库修正样本里找到的频繁项集。闭合频繁模式的唯一边界检查 例: 检查 abcd 而不是ab, ac, , 等. 再一次扫描数据库，找到遗漏的频繁模式 H. Toivonen. Sampling large databases for association rules. In VLDB96,DIC: Reduce Number of Scans,一旦A和D被确定频繁，AD计数开始 the counting of BCD begins一旦所有BC

8、D的长度为2的子集被确定为频繁的，就开始对BCD计数,ABCD,ABC,ABD,ACD,BCD,AB,AC,BC,AD,BD,CD,A,B,C,D,Itemset lattice,Apriori,Transactions,1-itemsets,2-itemsets,1-itemsets,2-items,3-items,DIC,S. Brin R. Motwani, J. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD97,频繁模式挖掘的瓶颈

9、,多次数据库扫描开销太大 挖掘长模式需要多次扫描，并产生大量的候选者 To find frequent itemset i1i2i100 # of scans: 100 # of Candidates: (1001) + (1002) + + (110000) = 2100-1 = 1.27*1030 ! 瓶颈: 候选生成和检验 我们能避免候选生成么?,没有候选生成的频繁模式挖掘,用局部频繁项从短模式生成长模式 “abc” 是一个频繁模式 得到所有含有“abc”的交易” “d” is a local frequent item in DB|abc abcd is a frequent patt

10、ern,Construct FP-tree from a Transaction Database,扫描DB一次，找到频繁1项集 用频率降序排序选择频繁项, f-list 再一次扫描DB，构建FP树,min_support = 3,TIDItems bought (ordered) frequent items 100f, a, c, d, g, i, m, pf, c, a, m, p 200a, b, c, f, l, m, of, c, a, b, m 300 b, f, h, j, o, wf, b 400 b, c, k, s, pc, b, p 500 a, f, c, e, l,

11、 p, m, nf, c, a, m, p,F-list=f-c-a-b-m-p,Benefits of the FP-tree Structure,Completeness（完备性） 保存完整的频繁模式挖掘信息 不要破坏任何交易的长模式 Compactness（紧致性） 去除不相关信息非频繁项不用处理 用频率降序排序的项目：更频繁地发生，更有可能被共享 不要比原始数据库更大（不计算节点的链接和计数字段）,Partition Patterns and Databases,根据F列表将频繁模式分成子集 F-list=f-c-a-b-m-p 含有 p的模式 含有m但是不含p的模式 含有c但是不含a

12、，b，m，p的模式 模式 f 完整性和非冗余性,Find Patterns Having P From P-conditional Database,从Fp树的频繁项头表开始 按照每个频繁项链接遍历FP-树 积累所有项目p的转换前缀路径，形成p的条件模式基,条件模式基 itemcond. pattern base cf:3 afc:3 bfca:1, f:1, c:1 mfca:2, fcab:1 pfcam:2, cb:1,From Conditional Pattern-bases to Conditional FP-trees,对于每个模式基 积累基里的每个项目的计数 为模式基里的频繁基

13、构建FP树,m-conditional pattern base: fca:2, fcab:1,All frequent patterns relate to m m, fm, cm, am, fcm, fam, cam, fcam,f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m:1,Header Table Item frequency head f4 c4 a3 b3 m3 p3,Recursion: Mining Each Conditional FP-tree,Cond. pattern base of “am”: (fc:3),Cond. patt

14、ern base of “cm”: (f:3),f:3,cm-conditional FP-tree,Cond. pattern base of “cam”: (f:3),f:3,cam-conditional FP-tree,A Special Case: Single Prefix Path in FP-tree,假定一个FP树有一个共享的单一前缀路径p 挖掘可以分解成两部分 单一的前缀路径还原成一个节点 串联两部分的挖掘结果,+,Mining Frequent Patterns With FP-trees,想法: 频繁模式生长 用模式和数据库分区递归生成频繁模式 方法 对于每一个频繁项，

15、构造它的条件模式基，然后它的条件FP-树 在每个新创建的条件FP-树重复这过程 直到产生FP-树是空的，或者它只包含一个单路径单一路径将产生的所有子路径组合，其中每个都是一个频繁模式,FP-growth Algorithm,FP树的构建过程 : 扫描交易数据库D一次，构建F列表 再一次扫描交易数据D 用 Insert_tree()构建FP树 procedure FP_growth(Tree, ) (1) if Tree contains a single path P then (2) for each combination ( ) of the nodes in the path P (3

16、) 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 base and then s conditional FP tree Tree ; (7) if ; then (8) call FP_growth( ; );,FP-G

17、rowth vs. Apriori: Scalability With the Support Threshold,Data set T25I20D10K,为何FP-Growth更优秀?,分治: 根据已获得的频繁模式分解挖掘任务和DB 集中搜集较小的数据库 其他因素 无候选生成，无候选检验 压缩数据库: FP树结构 整个数据库不进行重复扫描 基本OPS计数本地频繁物品和建设子FP-树，没有模式搜索和匹配,使用垂直数据格式挖掘频繁项集,水平数据格式: 事务数据格式 垂直格式: t(AB) = T11, T25, tid-list: list of trans.-ids containing an

18、 itemset 通过垂直交集求闭合模式 t(X) = t(Y): X and Y always happen together t(X) t(Y): transaction having X always has Y 使用diffset来加速挖掘过程 Only keep track 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 (Zak

19、i & HsiaoSDM02),挖掘闭频繁项集: CLOSET,Flist: 根据支持度升序列出所有频繁项集 Flist: d-a-f-e-c 分割搜索空间 有d的模式 有d但是没有a的模式 递归查找频繁封闭模式 每个有d的交易也有cfa cfad 事频繁封闭模式 J. Pei, J. Han & R. Mao. CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets, DMKD00.,Min_sup=2,挖掘闭频繁项集: CLOSET,在挖掘过程中直接搜索封闭频繁项 在挖掘中一旦确定封闭项，就修正搜索空间 修正规则 项目合并：如果每一个事务包含频繁项集X还包含项集Y但没有任何适当的Y的超集，那么XY就形成了一个频繁闭项集，没有必要搜寻任何含有X，但没有Y的项集.,挖掘闭频繁项集: CLOSET,子