关联规则挖掘实用教案

1、内容内容(nirng)提纲提纲I.关联规则挖掘简介(jin ji)II.关联规则基本模型III.关联规则挖掘的经典算法IV.Apriori V.FP-GrowthVI.参考文献第1页/共101页第一页，共102页。. 关联规则关联规则(guz)简介简介 关联规则反映一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物发生就能够预测与它相关联的其它事物的发生。 关联规则挖掘的经典范例：购物篮（Market Basket）分析。通过发现顾客放入购物篮中商品之间的同现关系来分析顾客的购买(gumi)习惯，从而实现商品的交叉销售和推荐。 第2页/共

2、101页第二页，共102页。事务事务(shw)与规则与规则 Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction购物篮事物购物篮事物(shw)集合：集合：关联规则关联规则(guz)示例：示例：Diaper Beer,Milk, Bread Eggs,Coke,Beer, Bread Milk,Implication means co-occurrence, not

3、causality!蕴含意味着同现而非因果关系！事务集合：所有事务集合事务集合：所有事务集合T=t1,t2, tN项集：所有项的集合项集：所有项的集合I=i1, i2, id事务事务: 若干项组成的集合若干项组成的集合tj=ij1, ij2, , ijk第3页/共101页第三页，共102页。Frequent Itemset 频繁频繁(pnfn)项集项集 Itemset 项 A collection of one or more items Example: Milk, Bread, Diaper k-itemset k-项 An itemset that contains k items Su

4、pport count () 支持度计数(j sh) Frequency of occurrence of an itemset E.g. (Milk, Bread,Diaper) = 2 Frequent Itemset 频繁项集 An itemset whose support is greater than or equal to a minsup threshold 最小支持度计数(j sh)(),iiiXt Xt tT第4页/共101页第四页，共102页。Association Rule 关联关联(gunlin)规则规则()()XYs XYNnAssociation RulenAn

5、implication expression of the form X Y, where X and Y are itemsetsnExample: Milk, Diaper Beer nRule Evaluation MetricsnSupport (s) 支持支持(zhch)度度nFraction of transactions that contain both X and YnConfidence (c) 置信度置信度nMeasures how often items in Y appear in transactions thatcontain X()()()XYc XYX第5页/

6、共101页第五页，共102页。Definition: Association RuleExample:BeerDiaper,Milk4 . 052|T|)BeerDiaper,Milk(s67. 032)Diaper,Milk()BeerDiaper,Milk,(cnAssociation RuleAn implication expression of the form X Y, where X and Y are itemsetsExample: Milk, Diaper Beer nRule Evaluation MetricsSupport (s)nFraction of transa

7、ctions that contain both X and YConfidence (c)nMeasures how often items in Y appear in transactions thatcontain X第6页/共101页第六页，共102页。规则规则(guz)度量：支持度与置信度信度度量：支持度与置信度信度 规则 X Y 的支持度和可信度 支持度 s：一次交易中同时包含(bohn)X 、 Y 的可能性 置信度 c ：包含(bohn)项X 的交易中同时也包含(bohn)Y的条件概率交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F设最小支持度

8、为0.5, 最小可信度为 0.5, 则可得到关联(gunlin)规则A C (0.5, 0.67)C A (0.5, 1)买尿布的客户买尿布的客户二者都买的二者都买的客户客户买啤酒的客户买啤酒的客户第7页/共101页第七页，共102页。什么什么(shn me)是关联规则挖掘是关联规则挖掘关联规则挖掘 首先被IBM公司Almaden研究中心的R. Agrawal, Imielinski and Swami在1993年的SIGMOD会议上提出在事务(shw)、关系数据中发现频繁项集和关联规则频繁项集: 事务(shw)数据中支持度大于最小支持度阈值minsup的所有项集关联规则：事务(shw)数据中

9、支持度大于最小支持度阈值minsup且置信度大于最小置信度阈值minconf的所有规则第8页/共101页第八页，共102页。什么是关联规则什么是关联规则(guz)挖掘挖掘 关联规则挖掘的意义(yy): 发现数据中的规律 超市数据中的什么产品会一起购买？ 啤酒和尿布 在得知某用户买了一台PC之后，预测他同时还会购买什么商品?第9页/共101页第九页，共102页。关联规则关联规则(guz)挖掘挖掘 Given a set of transactions T, the goal of association rule mining is to find all rules having suppor

10、t minsup threshold confidence minconf threshold Brute-force approach 蛮力方法: List all possible association rules Compute the support and confidence for each rule Prune rules that fail the minsup and minconf thresholds 计算开销(ki xio)极大，无法应用于大规模数据集!第10页/共101页第十页，共102页。关联规则关联规则(guz)挖掘挖掘Example of Rules:Mil

11、k,Diaper Beer (s=0.4, c=0.67)Milk,Beer Diaper (s=0.4, c=1.0)Diaper,Beer Milk (s=0.4, c=0.67)Beer Milk,Diaper (s=0.4, c=0.67) Diaper Milk,Beer (s=0.4, c=0.5) Milk Diaper,Beer (s=0.4, c=0.5)Observations 观察(gunch)到的现象: All the above rules are binary partitions of the same itemset: Milk, Diaper, Beer Ru

12、les originating from the same itemset have identical support but can have different confidence Thus, we may decouple the support and confidence requirements第11页/共101页第十一页，共102页。关联规则关联规则(guz)挖掘挖掘Two-step approach: Frequent Itemset Generation 产生频繁项集Generate all itemsets whose support minsupRule Genera

13、tion 产生规则Generate high confidence rules from each frequent itemset, where each rule is a binary partitioning of a frequent itemsetFrequent itemset generation is still computationally expensive 产生频繁项集的计算(j sun)代价依然很高第12页/共101页第十二页，共102页。产生产生(chnshng)频繁项集频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDAC

14、EADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEGiven d items, there are 2d possible candidate itemsets第13页/共101页第十三页，共102页。产生产生(chnshng)频繁项集频繁项集 Brute-force approach 蛮力(mn l)法: Each itemset in the lattice is a candidate frequent itemset Count the support of each candidate by scanning the database Match ea

15、ch transaction against every candidate Complexity O(NMw) = Expensive since M = 2d !第14页/共101页第十四页，共102页。计算计算(j sun)复杂度复杂度 Given d unique items: Total number of itemsets = 2d Total number of possible association rules: 1231111dddkkdjjkdkdRIf d=6, R = 602 rules第15页/共101页第十五页，共102页。频繁频繁(pnfn)项集产生算法项集产生

16、算法1：Apriori Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。 Apriori算法将发现关联规则的过程分为两个步骤： 检索出事务数据库中的所有频繁项集，即支持度不低于用户设定最小支持度计数阈值的项集； 利用频繁项集构造(guzo)出满足用户最小信任度的规则。 挖掘并产生所有频繁项集是该算法的核心，占整个计算量的大部分。 第16页/共101页第十六页，共102页。频繁频繁(pnfn)项集的性质：项集的性质： 性质(xngzh)1：频繁项集的子集必为频繁项集。 性质(xngzh)2：非频繁项集的超集一定是非频繁的。 Apriori算法运用性质(xngzh)1，通

17、过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。 第17页/共101页第十七页，共102页。Found to be Infrequent频繁频繁(pnfn)项集的性质：项集的性质：Pruned supersets第18页/共101页第十八页，共102页。Apriori算法算法(sun f) (1) L1=频繁1项集; (2) for(k=2;Lk-1;k+) do begin (3) Ck=apriori_gen(Lk

18、-1); /新的潜在(qinzi)频繁项集 (4) for all transactions tD do begin (5) Ct=subset(Ck,t); /t中包含的潜在(qinzi)频繁项集 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.countminsup (10) end; (11) Answer= kkL第19页/共101页第十九页，共102页。实例实例(shl)Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C,

19、D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2第20页/共101页第二十页，共102页。Visualization of Association Rules: Pane Graph第21页/共101页第二十一页，共102页。Visualizatio

20、n of Association Rules: Rule Graph第22页/共101页第二十二页，共102页。提高提高Apriori算法算法(sun f)性能的方法性能的方法 Hash-based itemset counting（散列项集计数） Transaction reduction（事务(shw)压缩） Partitioning（划分） Sampling（采样）第23页/共101页第二十三页，共102页。 用Frequent-Pattern tree (FP-tree) 结构压缩数据库, 高度浓缩，同时对频繁集的挖掘(wju)是完备的 避免代价较高的数据库扫描 开发一种高效的基于FP

21、-tree的频繁集挖掘(wju)算法 采用分而治之的方法学：分解数据挖掘(wju)任务为小任务 避免生成关联规则: 只使用部分数据库!频繁频繁(pnfn)项集产生算法项集产生算法2：FP-growth第24页/共101页第二十四页，共102页。构建构建(u jin)FP-treeTIDItems1A,B2B,C,D3A,C,D,E4A,D,E5A,B,C6A,B,C,D7B,C8A,B,C9A,B,D10B,C,EnullA:1B:1nullA:1B:1B:1C:1D:1After reading TID=1:After reading TID=2:第25页/共101页第二十五页，共102页。

22、构建构建(u jin)FP-TreenullA:7B:5B:3C:3D:1C:1D:1C:3D:1D:1E:1E:1TIDItems1A,B2B,C,D3A,C,D,E4A,D,E5A,B,C6A,B,C,D7B,C8A,B,C9A,B,D10B,C,EPointers are used to assist frequent itemset generationD:1E:1Transaction DatabaseItemPointerABCDEHeader table第26页/共101页第二十六页，共102页。f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item

23、frequency head f4c4a3b3m3p3最小支持最小支持(zhch)度度 = 0.5TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, of, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, p步骤(bzhu):扫描数据库一次，得到频繁1-项集把项按支持度递减排序再一次扫描数据库，建立FP-tree建

24、立(jinl)简化的FP-tree树：示例第27页/共101页第二十七页，共102页。 基本思想 (分治) 用FP-tree递归增长频繁集 方法 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree 对每个新生成的条件FP-tree，重复这个步骤 直到结果(ji gu)FP-tree为空, 或只含唯一的一个路径 (此路径的每个子路径对应的项集都是频繁集)用FP-tree挖掘(wju)频繁集第28页/共101页第二十八页，共102页。 从FP-tree的头表开始 按照每个频繁项的连接(linji)遍历 FP-tree 列出能够到达此项的所有前缀路径，得到条件模式库条件条件(tioj

25、in)模式库模式库itemcond. pattern 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 f4c4a3b3m3p3步骤1: 从 FP-tree 到条件(tiojin)模式库第29页/共101页第二十九页，共102页。 对每个模式(msh)库 计算库中每个项的支持度 用模式(msh)库中的频繁项建立FP-treem-条件条件(tiojin)模式库模式库:fca:2, fcab:1f:3c:3a:3m-cond

26、itional FP-treeAll frequent patterns concerning mm, fm, cm, am, fcm, fam, cam, fcamf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p3步骤(bzhu)2: 建立条件 FP-tree第30页/共101页第三十页，共102页。 完备: 不会打破交易中的任何模式 包含了频繁模式挖掘所需的全部信息 紧密 去除不相关信息不包含非频繁项 支持(zhch)度降序排列: 支持(zhch)度高的项在FP-tree中共享的机会也高 决不会比原数据

27、库大（如果不计算树节点的额外开销)FP-tree 结构(jigu)的优点第31页/共101页第三十一页，共102页。32The Frequent Pattern Growth Mining Method Idea: Frequent pattern growth 频繁(pnfn)模式增长 Recursively grow frequent patterns by pattern and database partition Method For each frequent item, construct its conditional pattern-base, and then its co

28、nditional FP-tree Repeat the process on each newly created conditional FP-tree Until the resulting FP-tree is empty, or it contains only one pathsingle path will generate all the combinations of its sub-paths, each of which is a frequent pattern第32页/共101页第三十二页，共102页。33FP-Growth vs. Apriori: Scalabil

29、ity With the Support Threshold010203040506070809010000.511.522.53Support threshold(%)Run time(sec.)D1 FP-grow th runtimeD1 Apriori runtimeData set T25I20D10K第33页/共101页第三十三页，共102页。2021年11月30日星期二Data Mining: Concepts and Techniques34FP-Growth vs. Tree-Projection: Scalability with the Support Threshold

30、02040608010012014000.511.52Support threshold (%)Runtime (sec.)D2 FP-growthD2 TreeProjectionData set T25I20D100K第34页/共101页第三十四页，共102页。产生关联产生关联(gunlin)规则规则 任务描述：给定频繁项集Y, 查找Y的所有非空真子集X Y，使得 X Y X 的置信度超过最小置信度阈值minconf 例子：If A,B,C is a frequent itemset, 候选规则如下： AB C, AC B, BC AA BC,B AC, C AB 如果(rgu) |Y|

31、= k, 那么会有 2k 2 个候选关联规则 (不包括 Y and Y)第35页/共101页第三十五页，共102页。产生产生(chnshng)关联规则关联规则 How to efficiently generate rules from frequent itemsets? 通常(tngchng)，置信度不满足反单调性（anti-monotone property ），例如：c(ABC D) 可能大于也可能小于 c(AB D) 但是，针对同一个频繁项集的关联规则，如果规则的后件满足子集关系，那么这些规则的置信度间满足反单调性 e.g., Y= A,B,C,D: c(ABC D) c(AB CD

32、) c(A BCD)第36页/共101页第三十六页，共102页。Rule Generation for Apriori AlgorithmLattice of rulesPruned RulesLow Confidence Rule第37页/共101页第三十七页，共102页。针对针对(zhndu)Apriori 算法的规则产生方法算法的规则产生方法 Candidate rule is generated by merging two rules that share the same prefixin the rule consequent join(CD=AB,BD=AC)would pro

33、duce the candidaterule D = ABC Prune rule D=ABC if itssubset AD=BC does not havehigh confidenceBD=ACCD=ABD=ABC第38页/共101页第三十八页，共102页。IV.参考文献参考文献Agrawal R, Imielinski T, and Swami A. Mining association rules between sets of items in large databases. SIGMOD, 207-216, 1993.Agrawal R, and Srikant R. Fast

34、 algorithms for mining association rules in large databases. VLDB, 478-499, 1994. Han J W, Pei J, Yin Y W. Mining frequent patterns without candidate generation. SIGMOD, 1-12, 2000.Han J W, Pei J, Yin Y W, and Mao R Y. Mining frequent patterns without candidate generation: a frequent-pattern tree ap

35、proach. Data Mining and Knowledge Discovery. 8, 53-87, 2004第39页/共101页第三十九页，共102页。课程课程(kchng)安排安排I.通过垂直数据格式挖掘关联规则(guz)II.ECLATIII.挖掘最大、闭合关联规则(guz)模IV.MaxMinerV.CLOSETVI.CLOSETVII.CHARM第40页/共101页第四十页，共102页。第一部分通过垂直数据格式挖掘关联(gunlin)规则ECLAT第41页/共101页第四十一页，共102页。基本概念基本概念n水平(shupng)数据格式：TID:itemsetn垂直(chuz

36、h)数据格式：item:TID_setTID商品IDT100I1 I2 T200I2 I4T300I2 I3T400I1 I2 I3项TID集I1T100，T400I2T100，T200，T300，T400I3T300，T400I4T200第42页/共101页第四十二页，共102页。ECLAT:ECLAT:使用垂直数据格式进行使用垂直数据格式进行(jnxng)(jnxng)挖掘挖掘 ECLAT：生成-检测模型 剪枝策略：子集不频繁剪枝 算法步骤：1、扫描事务数据库TDB，将水平数据格式转化成垂直数据格式。2、通过对集合(jh)操作，得到满足最小支持度域值min_sup的频繁1项集。3、通过频繁

37、k项集产生候选k+1项集，通过集合(jh)求交来产生频繁K+1项集。4、直到不再生成候选项集或不再产生频繁项集，程序结束。第43页/共101页第四十三页，共102页。算法算法(sun f)实例实例例：TIDList of item IDsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3第44页/共101页第四十四页，共102页。构造构造(guzo)垂直数据垂直数据格式：格式：itemsetTID_setI1T100,T400,T500,T700,T80

38、0,T900I2T100,T200,T300,T400,T600,T800,T900I3T300,T500,T600,T700,T800,T900I4T200,T400I5T100,T800ECLAT第45页/共101页第四十五页，共102页。构造(guzo)频繁1项集（min_sup=2）:itemsetTID_setI1T100,T400,T500,T700,T800,T900I2T100,T200,T300,T400,T600,T800,T900I3T300,T500,T600,T700,T800,T900I4T200,T400I5T100,T800ECLAT第46页/共101页第四十六

39、页，共102页。itemsetTID_setI1,I2T100,T400,T800,T900I1,I3T500,T700,T800,T900I1,I4T400I1,I5T100,T800I2,I3T300,T600,T800,T900I2,I4T200,T400I2,I5T100,T800I3,I5T800构造(guzo)频繁2项集(min_sup=2):ECLAT第47页/共101页第四十七页，共102页。ECLAT第48页/共101页第四十八页，共102页。直到没有频繁项集或候选项集产生，算法(sun f)结束第49页/共101页第四十九页，共102页。课程课程(kchng)安排安排第二部

40、分挖掘最大、闭合关联规则(guz)模式 MaxMiner、CLOSET、CLOSET+、CHARM第50页/共101页第五十页，共102页。 DB = , min_sup=2;问题(wnt)：频繁项集有哪些呢250-1 ！？第51页/共101页第五十一页，共102页。基本概念基本概念 最大频繁(pnfn)项集最大频繁(pnfn)项集是这样的频繁(pnfn)项集，它的直接超集都是不频繁(pnfn)的。最大频繁最大频繁(pnfn)项集项集第52页/共101页第五十二页，共102页。基本概念基本概念 闭项集项集X是闭的，如果它的直接超集都不具有和它相同的支持(zhch)度计数。 频繁闭项集如果项集X

41、是闭的，并且它的支持(zhch)度计数大于或等于最小支持(zhch)度阈值min_sup，则项集X是频繁闭项集。第53页/共101页第五十三页，共102页。最大项集最大项集VS闭频繁闭频繁(pnfn)项集项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE12412312342453451212424412323243445122244423424闭频繁(pnfn)项集闭频繁(pnfn)项集且最大频繁(pnfn)项集TID项1abc2abcd3bce4acde5deminsu

42、p=2TDB第54页/共101页第五十四页，共102页。频繁频繁(pnfn)(pnfn)项集、最大频繁项集、最大频繁(pnfn)(pnfn)项集和频项集和频繁繁(pnfn)(pnfn)闭项集之间的关系闭项集之间的关系第55页/共101页第五十五页，共102页。MaxMiner：挖掘：挖掘(wju)最大模式最大模式 完全集合(jh)枚举树A (BCD)B (CD)C (D)D ()AB (CD)AC (D)AD ()BC (D)BD ()CD ()ABC (C)ABCD ()ABD ()ACD ()BCD () (ABCD)设TDB中包含(bohn)有项ABCD第56页/共101页第五十六页，共

43、102页。MaxMiner 剪枝原理子集不频繁剪枝：任何非频繁项集的超集都是非频繁项集；超集频繁剪枝：任何频繁项集的子集都是频繁项集； 搜索策略广度优先(yuxin)搜索完全集合枚举树第57页/共101页第五十七页，共102页。MaxMiner算法算法(sun f)实例实例(1/4)TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyABCDEF0A2B2C3D3E2F1Min_sup=2Max patterns:A (BCDE)B (CDE)C (DE)E ()D (E)第58页/共101页第五十八页，共102页。MaxM

44、iner算法算法(sun f)实例实例(2/4)TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyABCDE1AB1AC2AD2AE1Min_sup=2A (BCDE)B (CDE)C (DE)E ()D (E)AC (D)AD ()Max patterns:Node A第59页/共101页第五十九页，共102页。MaxMiner算法算法(sun f)实例实例(3/4)TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyBCDE2BCBDBEMin_su

45、p=2A (BCDE)B (CDE)C (DE)E ()D (E)AC (D)AD ()Max patterns:BCDENode B第60页/共101页第六十页，共102页。MaxMiner算法算法(sun f)实例实例(4/4)TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F (ABCDEF)ItemsFrequencyACD2Min_sup=2A (BCDE)B (CDE)C (DE)E ()D (E)AC (D)AD ()Max patterns:BCDEACDNode AC第61页/共101页第六十一页，共102页。CLOSET ：高效的挖掘：高效的挖掘(

46、wju)频繁闭项集算法频繁闭项集算法 频繁项集列表（f_list） 给定事务数据库TDB和最小支持度计数阈值min_sup，将所有的频繁项按照支持度计数递减(djin)顺序构成的表。 条件数据库（conditional database） 给定一个事务数据库TDB，若项i是一个频繁项。 项i的条件数据库(用TDB|i表示)，是TDB中包含项i的交易构成的子集，并且所有出现的非频繁项、项i和f_list中项i后面的项都删除。第62页/共101页第六十二页，共102页。构造构造(guzo)f_listTIDItems10a,c,d,e,f20a,b,e30c,e,f40a,c,d,f50c,e,f

47、则由f_list定义(dngy)得到：f_list:设有如下(rxi)事物数据库TDB(min_sup=2)：首先计算出每个项的支持度计数：a:3,b:1,c:4,d:2,e:4,f:4, 第63页/共101页第六十三页，共102页。条件条件(tiojin)数据库的构造数据库的构造TDBcefadeacefcfadceff_list:d-cond DB(d:2)cefacfaa-cond DB(a:3)cefecff-cond DB(f:4)ce:3ce-cond DB(e:4)c第64页/共101页第六十四页，共102页。CLOSET算法算法(sun f) 引理1挖掘所有频繁闭项集的问题可以

48、被分解成n个子问题；第j个问题是找到包含项in+1-j但是不包含ik (n+1-jkn)的完全频繁闭项集。 引理2如果项集X是一个频繁闭项集，则在X条件数据库中不存在项i，使得项i出现(chxin)在所有的事务中。 引理3在项集X的条件数据库中，Y是每一个事务都出现(chxin)的项构成的最大的集合，如果X没有以相同的支持度计数被已发现的频繁闭项集融合，则X是一个频繁闭项集。第65页/共101页第六十五页，共102页。 引理 项融合(rngh)(item merging)项集X是一个频繁项集，如果每个包含项集X的事务中都包含有项集，而不是项集的任何一个直接超集，则XY构成频繁闭项集并且没有必要

49、再搜索任何包含项集而不含项集的项集。第66页/共101页第六十六页，共102页。CLOSE算法算法(sun f)实例实例(1/3)选择(xunz)的事务数据库TIDTIDItems10a,c,d,e,f20a,b,e30c,e,f40a,c,d,f50c,e,f最小支持(zhch)度计数min_sup=2第67页/共101页第六十七页，共102页。CLOSE算法算法(sun f)实例实例(2/3) 1、构造f_list计算(j sun)TDB中每个项的支持度计数，得到：a:3 b:1 c:4 d:2 e:4 f:4 min_sup=2f_list:第68页/共101页第六十八页，共102页。C

50、LOSE算法算法(sun f)实例实例(3/3) 2、构造(guzo)条件数据库TDBcefadeacefcfadceff_list:a-cond DB(a:3)cefecff-cond DB(f:4)ce:3ce-cond DB(e:4)cd-cond DB(d:2)cefacfaOutput: cfad:2Output: a:3Output: cf:4;cef:3Output: e:4ea-cond DB(ea:2)cOutput: ea:2第69页/共101页第六十九页，共102页。 CLOSET+ ：高效：高效(o xio)的挖掘频繁闭项集方的挖掘频繁闭项集方法法 混合树投影技术(hy

51、brid tree-projection method)1、自底向上物理的树投影(bottom-up physical tree-projection)-高密度的数据(shj)集2、自顶向下伪树投影(top-down pseudo tree-projection)-稀疏数据(shj)集第70页/共101页第七十页，共102页。Bottom-up physical tree-projectionf4c4a3b3m 3p3rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1(a)Global FP-treec3f2a2m 2f:2c:3m:2a:2root(b)Project

52、ed FP-tree with prefix pfcam:2cb:1第71页/共101页第七十一页，共102页。Top-down pseudo tree-projectionrootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1fcabmp443333(a)Pseudo tree for prefix ffcabmp443333rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1(b)Pseudo tree for prefix cHH第72页/共101页第七十二页，共102页。Top-down pseudo tree-projection for f

53、:4cabmp32232rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1Hf:4amp332rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1Hfc:3=Hfcam:3(a)(b)第73页/共101页第七十三页，共102页。Top-down pseudo tree-projection for f:4amp332rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1Hfc:3=Hfcam:3amp332rootf:4c:3c:1m:2b:1b:1b:1p:1a:3p:2m:1Hfc:3=Hfcam:3(c)(d)第74页/共

54、101页第七十四页，共102页。CLOSET+算法算法(sun f) 引理1：项的跳跃(Item skipping)若局部频繁项i，在不同层次的一些头表(header tables)中有相同的支持度计数，则可以安全地将项i从较高的层次的头表(header tables)中移除。 定理1：子集检测(Subset checking)在分治框架下，使用项集融合剪枝方法，通过CLOSET+算法(sun f)得到的频繁项集，如果它不能被其它的任何已找到的频繁闭项集融合，则该项集是频繁项集。第75页/共101页第七十五页，共102页。CLOSET+算法算法(sun f) 加速子集检测(jin c)方法：(

55、1)两层哈希索引结果树(2)基于向上检测(jin c)的伪投影第76页/共101页第七十六页，共102页。CLOSET+算法算法(sun f) CLOSET+算法步骤：1、扫描事务数据库，构造f_list。2、使用f_list，通过扫描事务数据库建立FP-tree。3、使用分治策略和深度优先搜索方法，(1)当数据集是稀疏时，使用自顶向下方法挖掘FP-tree来寻找频繁闭项集。(2)当数据集是密集(mj)时，使用自底向上的方法挖掘FP-tree来寻找频繁闭项集。4、当全局头表上的所有项都被挖掘了，算法结束。第77页/共101页第七十七页，共102页。CHARM算法算法(sun f) 定义 对于项

56、集X，定义X对应(duyng)的事务id集合(tidset)为t(X):t(X)=xXt(x)对于事务id集合，定义对应(duyng)的项集(itemset)为i(Y):i(Y)= yYi(y)第78页/共101页第七十八页，共102页。CHARM:使用使用(shyng)垂直数据格式挖掘闭项集垂直数据格式挖掘闭项集 IT-Tree:Itemset-Tidset Search TreeTIDitems1ACTW2CDW3ACTW4ACDW5ACDTW6CDT设事务(shw)数据库TDB为：第79页/共101页第七十九页，共102页。IT-Tree则对应(duyng)的IT-Tree为：第80页/

57、共101页第八十页，共102页。 等价类(Equivalence Classes)等价类P=l1,l2,ln,其中P是父节点（前驱(qinq)），且每个li表示单独的项。例如：前面IT-Tree中根节点的等价类为： =A,C,D,T,W 项集的闭包项集X的闭包是包含项集X的最小的闭集。c(X) = i t(X) = i(t(X). 结论：项集X是闭的，当且仅当X=c(X)。第81页/共101页第八十一页，共102页。CHARM算法算法(sun f) 定理1设Xit(Xi)和Xjt(Xj)是类P的任意两个成员，如果满足XifXj，其中f表示一个全序关系(如，按字典顺序或者基于支持度的顺序)。存在

58、如下(rxi)四条性质：1.如果t(Xi)=t(Xj)，则c(Xi)=c(Xj)=c(XiXj)2.如果t(Xi) t(Xj)，则c(Xi) c(Xj)，但是满足c(Xi)=c(XiXj)3.如果t(Xi)?t(Xj)，则c(Xi) c(Xj),但是满足c(Xj)=c(XiXj)4.如果t(Xi) t(xj)，则c(Xi) c(Xj)c(Xi Xj)第82页/共101页第八十二页，共102页。 定理产生的启发信息：1、由于c(Xi) = c(Xj) = c(Xi Xj)，所以可以用Xi Xj替换掉Xi，并且将Xj从等价类中移除。2、由于c(Xi Xj) = c(Xi) c(Xj )，所以可以用

59、Xi Xj替换掉Xi；但是(dnsh)由于c(Xi) c(Xj )，所以不能将元素Xj从等价类中移除。3、与2相似。4、由于c(Xi)c(Xj)c(XiXj)，所以Xi和Xj都能各自产生不同的闭包，所以不能删除任何元素。第83页/共101页第八十三页，共102页。CHARM算法算法(sun f)实例实例(1/6)TIDitems1ACTW2CDW3ACTW4ACDW5ACDTW6CDT 事务(shw)数据库TDB：最小支持(zhch)度计数min_sup=3第84页/共101页第八十四页，共102页。CHARM算法算法(sun f)实例实例(2/6)项TID集合A1,3,4,5C1,2,3,4

60、,5,6D2,4,5,6T1,3,5,6W1,2,3,4,51、转换成垂直(chuzh)数据格式：定义(dngy)项X的权重：w(X)=XYF2?(XY) 其中，F2表示由所有频繁2项集构成的集合， ?(XY)表示项集XY的支持度计数。4+3+4=11?(AC)=4?(AD)=2?(AT)=3?(AW)=4min_sup=3W(A)=第85页/共101页第八十五页，共102页。CHARM算法算法(sun f)实例实例(3/6)2、计算所有项的权重得到：w(A)=11,w(C)=17,w(D)=7,w(T)=10,w(W)=15按权重值递增的顺序排序得到：DTAWC3、初始化根类 =D2456,