数据挖掘导论关联分析学习教案.pptx

《数据挖掘导论关联分析学习教案.pptx》由会员分享，可在线阅读，更多相关《数据挖掘导论关联分析学习教案.pptx（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据挖掘导论数据挖掘导论(do ln)关联分析关联分析第一页，共110页。6.1 问题问题(wnt)定义定义n n关联分析n n频繁项集n n关联规则n n关联规则强度：n n支持度n n置信度n n关联规则发现(fxin)n n挖掘关联规则的策略第1页/共110页第二页，共110页。定义定义(dngy):关联分析关联分析（association analysis）n n关联分析用于发现隐藏在大型数据集中(jzhng)的令人感兴趣的联系，所发现的模式通常用关联规则或频繁项集的形式表示。n n关联分析可以应用于生物信息学、医疗诊断、网页挖掘、科学数据分析等Rules Discovered

2、:Diaper-Beer第2页/共110页第三页，共110页。定义定义(dngy):频繁项集频繁项集（Frequent Itemset）n n项集（项集（项集（项集（ItemsetItemset）n n包含包含包含包含0 0个或多个项的集合个或多个项的集合个或多个项的集合个或多个项的集合n n例子例子例子例子:Milk,Bread,Diaper:Milk,Bread,Diapern nk-k-项集项集项集项集n n如果一个项集包含如果一个项集包含如果一个项集包含如果一个项集包含k k个项个项个项个项n n支持度计数（支持度计数（支持度计数（支持度计数（Support count Support

3、 count）()n n包含特定项集的事务个数包含特定项集的事务个数包含特定项集的事务个数包含特定项集的事务个数n n例如：例如：例如：例如：(Milk,Bread,Diaper)=2(Milk,Bread,Diaper)=2 n n支持度（支持度（支持度（支持度（SupportSupport）n n包含项集的事务数与总事务数的比值包含项集的事务数与总事务数的比值包含项集的事务数与总事务数的比值包含项集的事务数与总事务数的比值n n例如：例如：例如：例如：s(Milk,Bread,Diaper)=2/5 s(Milk,Bread,Diaper)=2/5n n频繁频繁频繁频繁(pnfn)(pnf

4、n)项集（项集（项集（项集（Frequent ItemsetFrequent Itemset）n n满足最小支持度阈值（满足最小支持度阈值（满足最小支持度阈值（满足最小支持度阈值（minsup minsup ）的所有）的所有）的所有）的所有项集项集项集项集第3页/共110页第四页，共110页。定义定义:关联关联(gunlin)规则规则（Association Rule）Example:l关联规则关联规则是形如 X Y的蕴含表达式,其中 X 和 Y 是不相交的项集例子:Milk,Diaper Beer l关联规则的强度支持度 Support(s)u确定项集的频繁程度置信度 Confidence(

5、c)u确定Y在包含X的事 务中出现的频繁程度第4页/共110页第五页，共110页。关联规则关联规则(guz)发现发现n n关联规则发现：给定事务的集合 T,关联规则发现是指找出支持度大于等于 minsup并且置信度大于等于minconf的所有规则,minsup和minconf是对应的支持度和置信度阈值n n关联规则发现的一种原始方法是：Brute-force approach:n n计算每个可能规则的支持度和置信度n n这种方法计算代价过高，因为可以从数据集提取的规则的数量(shling)达指数级n n从包含d个项的数据集提取的可能规则的总数n nR=3d-2d+1+1，如果d等于6，则R=6

6、02第5页/共110页第六页，共110页。挖掘挖掘挖掘挖掘(wju)(wju)关联规则（关联规则（关联规则（关联规则（Mining Association RulesMining Association Rules）的策略）的策略）的策略）的策略n n大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务(rn wu)分解为如下两个主要的子任务(rn wu):n n频繁项集产生（Frequent Itemset Generation）n n其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。n n规则的产生（Rule Generation）n n其目标是从上一步发现的频繁项

7、集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。第6页/共110页第七页，共110页。6.2 频繁频繁(pnfn)项集的产生项集的产生n n6.1 问题定义n n6.2 频繁(pnfn)项集的产生第7页/共110页第八页，共110页。频繁频繁频繁频繁(pnfn)(pnfn)项集产生（项集产生（项集产生（项集产生（Frequent Itemset GenerationFrequent Itemset Generation）格结构（格结构（lattice structure）格结构用来枚举所有格结构用来枚举所有(suyu)可能项可能项集集第8页/共110页第九页，共110

8、页。频繁频繁频繁频繁(pnfn)(pnfn)项集产生（项集产生（项集产生（项集产生（Frequent Itemset GenerationFrequent Itemset Generation）n nBrute-force 方法:n n把格结构中每个项集作为候选项集n n将每个候选项集和每个事务进行(jnxng)比较，确定每个候选项集的支持度计数。n n时间复杂度 O(NMw)，这种方法的开销可能非常大。第9页/共110页第十页，共110页。降低产生降低产生降低产生降低产生(ch(ch nshng)nshng)频繁项集计算复杂度的方法频繁项集计算复杂度的方法频繁项集计算复杂度的方法频繁项集计算

9、复杂度的方法n n减少候选项集的数量(M)n n先验(apriori)原理n n减少比较的次数(NM)n n替代将每个候选项集与每个事务相匹配，可以使用更高级的数据结构，或存储(cn ch)候选项集或压缩数据集，来减少比较次数第10页/共110页第十一页，共110页。6.2 频繁频繁(pnfn)项集的产生项集的产生n n6.2.1 先验(xin yn)原理第11页/共110页第十二页，共110页。先验先验(xin yn)原理（原理（Apriori principle）n n先验原理:n n如果一个项集是频繁(pnfn)的，则它的所有子集一定也是频繁(pnfn)的第12页/共110页第十三页，共

10、110页。先验先验(xin yn)原理（原理（Apriori principle）n n先验原理:n n如果一个项集是频繁的，则它的所有子集一定也是频繁的n n相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的:n n这种基于支持度度量修剪指数搜索空间的策略称为(chn wi)基于支持度的剪枝（support-based pruning）n n这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过它的子集的支持度。这个性质也称为(chn wi)支持度度量的反单调性（anti-monotone）。第13页/共110页第十四页，共110页。非频繁项集例子例子例子例子(l

11、 zi)(l zi)被剪枝的超集第14页/共110页第十五页，共110页。6.2 频繁频繁(pnfn)项集的产生项集的产生n n6.2.1 先验原理(yunl)n n6.2.2 Apriori算法的频繁项集产生第15页/共110页第十六页，共110页。Apriori算法算法(sun f)的频繁项集的频繁项集产生产生第16页/共110页第十七页，共110页。Apriori算法的频繁算法的频繁(pnfn)项集产项集产生生Items(1-itemsets)Pairs(2-itemsets)Triplets(3-itemsets)支持度阈值(y zh)=60%最小支持度计数=3枚举所有项集将产生 个候

12、选而使用先验原理，将较少为 =13第17页/共110页第十八页，共110页。Apriori 算法算法(sun f)第18页/共110页第十九页，共110页。Apriori 算法算法(sun f)n nApriori算法的频繁项集产生的部分有两个重要的特点：n n它是一个逐层算法。即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层n n它使用产生-测试策略来发现频繁项集。在每次迭代，新的候选(hu xun)项集由前一次迭代发现的频繁项集产生，然后对每个候选(hu xun)的支持度进行计数，并与最小支持度阈值进行比较。n n该算法需要的总迭代次数是kmax+1，其中kmax是频繁项集的最大

13、长度第19页/共110页第二十页，共110页。6.2 频繁频繁(pnfn)项集的产生项集的产生n n6.2.1 先验原理(yunl)n n6.2.2 Apriori算法的频繁项集产生n n6.2.3 候选的产生与剪枝第20页/共110页第二十一页，共110页。候选的产生候选的产生(chnshng)与剪枝与剪枝(构造构造apriori-gen函数函数)n n候选项集的产生与剪枝(构造apriori-gen函数)包含2个步骤：n n候选项集的产生：由频繁(pnfn)（k-1）-项集产生新的候选k-项集n n候选项集的剪枝：采用基于支持度的剪枝，删除一些候选k-项集第21页/共110页第二十二页，共

14、110页。候选的产生与剪枝候选的产生与剪枝(构造构造(guzo)apriori-gen函数函数)n n蛮力方法n n蛮力方法把所有的k-项集都看作可能的候选，然后使用候选剪枝除去不必要的候选n n第k层产生的候选项集的数目为 。（d为项的总数）n n虽然(surn)候选产生是相当简单的，但是候选剪枝的开销极大，因为必须考察的项集数量太大。n n设每一个候选项集所需的计算量为O（k），这种方法n n 的总复杂度为第22页/共110页第二十三页，共110页。候选候选(hu xun)的产生与剪枝的产生与剪枝第23页/共110页第二十四页，共110页。Items(1-itemsets)Pairs(2-

15、itemsets)Triplets(3-itemsets)支持(zhch)度阈值=60%最小支持(zhch)度计数=3枚举所有项集将产生 6C1+6C2+6C3=41个候选而使用先验(xin yn)原理，将较少为6+6+1=13第24页/共110页第二十五页，共110页。候选的产生与剪枝候选的产生与剪枝(jin zh)（Fk-1XF1方法）方法）n n n n这种方法用其他频繁项来扩展每个频繁（这种方法用其他频繁项来扩展每个频繁（k-1k-1）-项集项集n n这种方法将产生这种方法将产生(ch(ch nshng)nshng)个候选个候选k-k-项集，其中项集，其中|Fj|Fj|表示频繁表示频繁

16、j-j-项集的个数。这种方法总复杂度是项集的个数。这种方法总复杂度是n n这种方法是完全的，因为每一个频繁这种方法是完全的，因为每一个频繁k-k-项集都是由一个频繁项集都是由一个频繁（k-1k-1）-项集和一个频繁项集和一个频繁1-1-项集组成的。因此，所有的频繁项集组成的。因此，所有的频繁k-k-项集是这种方法所产生项集是这种方法所产生(ch(ch nshng)nshng)的候选的候选k-k-项集的一部分。项集的一部分。n n然而，这种方法很难避免重复地产生然而，这种方法很难避免重复地产生(ch(ch nshng)nshng)候选项集。候选项集。n n 如：如：面包，尿布，牛奶面包，尿布，牛

17、奶 不仅可以由合并项集不仅可以由合并项集 面包，尿面包，尿布布 和和 牛奶牛奶 得到，而且还可以由合并得到，而且还可以由合并 面包，牛奶面包，牛奶 和和 尿布尿布 得到，或由合并得到，或由合并 尿布，牛奶尿布，牛奶 和和 面包面包 得到。得到。第25页/共110页第二十六页，共110页。候选的产生与剪枝候选的产生与剪枝(jin zh)（Fk-1XF1方法）方法）第26页/共110页第二十七页，共110页。候选候选(hu xun)的产生与剪枝的产生与剪枝（Fk-1XF1方法）方法）n n避免产生重复的候选项集的一种方法是确保每个避免产生重复的候选项集的一种方法是确保每个频繁项集中的项以字典序存储

18、，每个频繁（频繁项集中的项以字典序存储，每个频繁（k-1k-1）-项集项集X X只用字典序比只用字典序比X X中所有的项都大的频繁项进中所有的项都大的频繁项进行扩展行扩展n n 如：项集如：项集 面包，尿布面包，尿布 可以用项集可以用项集 牛奶牛奶 扩展，扩展，因为因为“牛奶牛奶”（milkmilk）在字典序下比）在字典序下比“面包面包”（BreadBread）和）和“尿布尿布”（DiapersDiapers）都大。）都大。n n尽管这种方法比蛮力方法有明显改进，但是仍然尽管这种方法比蛮力方法有明显改进，但是仍然产生大量不必要的候选。产生大量不必要的候选。n n 例如例如(lr)(lr)，通过

19、合并，通过合并 啤酒，尿布啤酒，尿布 和和 牛奶牛奶 而得到的候选是不必要的。因为它的子集而得到的候选是不必要的。因为它的子集 啤酒，啤酒，牛奶牛奶 是非频繁的。是非频繁的。n n【每个【每个K-K-项集，它的每一个项必须至少在项集，它的每一个项必须至少在k-1k-1个个（k-1k-1）项集中出现，否则，）项集中出现，否则，这个这个K-K-项集是非频繁项集是非频繁项集】项集】第27页/共110页第二十八页，共110页。候选的产生与剪枝候选的产生与剪枝(jin zh)（Fk-1XFk-1方法）方法）n n n n这种方法合并一对频繁（这种方法合并一对频繁（k-1k-1）-项集，仅当它们的前项集，

20、仅当它们的前k-2k-2个项个项都相同。都相同。n n 如频繁项集如频繁项集 面包，尿布面包，尿布 和和 面包，牛奶面包，牛奶 合并，形成了候合并，形成了候选选3-3-项集项集 面包，尿布，牛奶面包，尿布，牛奶。算法不会合并项集。算法不会合并项集 啤酒，尿啤酒，尿布布 和和 尿布，牛奶尿布，牛奶，因为它们的第一个项不相同。，因为它们的第一个项不相同。n n然而，由于每个候选都由一对频繁（然而，由于每个候选都由一对频繁（k-1k-1）-项集合并而成，项集合并而成，因此，需要因此，需要(xyo)(xyo)附加的候选剪枝步骤来确保该候选的其余附加的候选剪枝步骤来确保该候选的其余k-2k-2个子集是频

21、繁的。个子集是频繁的。第28页/共110页第二十九页，共110页。候选候选(hu xun)的产生与剪枝的产生与剪枝（Fk-1XFk-1方法）方法）第29页/共110页第三十页，共110页。6.2 频繁频繁(pnfn)项集的产生项集的产生n n6.2.1 先验(xin yn)原理n n6.2.2 Apriori算法的频繁项集产生n n6.2.3 候选的产生与剪枝n n6.2.4 支持度计数第30页/共110页第三十一页，共110页。支持支持(zhch)度计数度计数n n支持度计数过程确定在apriori-gen函数的候选项剪枝步骤保留下来的每个候选项集出现的频繁(pnfn)程度。计算支持度的主要

22、方法:n n一种方法是将每个事务与所有的候选项集进行比较，并且更新包含在事务中的候选项集的支持度计数。这种方法是计算昂贵的，尤其当事务和候选项集的数目都很大时。n n另一种方法是枚举每个事务所包含的项集，并且利用它们更新对应的候选项集的支持度。第31页/共110页第三十二页，共110页。枚举枚举(mi j)事务事务t的所有包含的所有包含3个个项的子集项的子集第32页/共110页第三十三页，共110页。产生产生(chnshng)Hash树树2 3 45 6 71 4 51 3 61 2 44 5 71 2 54 5 81 5 93 4 53 5 63 5 76 8 93 6 73 6 81,4,

23、72,5,83,6,9Hash functionHash函数函数h(p)=p mod 3假设假设(jish)有有15个候选个候选3-项集项集:1 4 5,1 2 4,4 5 7,1 2 5,4 5 8,1 5 9,1 3 6,2 3 4,5 6 7,3 4 5,3 5 6,3 5 7,6 8 9,3 6 7,3 6 8第33页/共110页第三十四页，共110页。Hash树结构树结构1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash FunctionCandi

24、date Hash TreeHash on 1,4 or 7第34页/共110页第三十五页，共110页。Hash树结构树结构1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash FunctionCandidate Hash TreeHash on 2,5 or 8第35页/共110页第三十六页，共110页。Hash树结构树结构1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2

25、 54 5 81,4,72,5,83,6,9Hash FunctionCandidate Hash TreeHash on 3,6 or 9第36页/共110页第三十七页，共110页。使用使用Hash树进行树进行(jnxng)支持支持度计数度计数1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81 2 3 5 61+2 3 5 63 5 62+5 63+1,4,72,5,83,6,9Hash Functiontransaction第37页/共110页第三十八页，共110页。使用使用Hash树进行

26、树进行(jnxng)支持支持度计数度计数1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44 5 71 2 54 5 81,4,72,5,83,6,9Hash Function1 2 3 5 63 5 61 2+5 61 3+61 5+3 5 62+5 63+1+2 3 5 6transaction第38页/共110页第三十九页，共110页。使用使用(shyng)Hash树进行支持树进行支持度计数度计数1 5 91 4 51 3 63 4 53 6 73 6 83 5 63 5 76 8 92 3 45 6 71 2 44

27、5 71 2 54 5 81,4,72,5,83,6,9Hash Function1 2 3 5 63 5 61 2+5 61 3+61 5+3 5 62+5 63+1+2 3 5 6transaction15个项集中(jzhng)的9个与事务进行比较第39页/共110页第四十页，共110页。存放在被访问的叶结点中的候选项集与事务进行比较，如果候选项集是该事务的子集(z j)，则增加它的支持度计数。在该例子中，访问了9个叶子结点中的5个。15个项集中的9个与事务进行比较第40页/共110页第四十一页，共110页。6.2 频繁频繁(pnfn)项集的产生项集的产生n n6.2.1 先验原理n n6

28、.2.2 Apriori算法(sun f)的频繁项集产生n n6.2.3 候选的产生与剪枝n n6.2.4 支持度计数n n6.2.5 计算复杂度第41页/共110页第四十二页，共110页。计算计算(j sun)复杂度复杂度n n支持度阈值支持度阈值n n 降低支持度阈值通常将导致更多的项集是频繁的。计算复降低支持度阈值通常将导致更多的项集是频繁的。计算复杂度增加杂度增加n n随着支持度阈值的降低，频繁项集的最大长度将增加，导随着支持度阈值的降低，频繁项集的最大长度将增加，导致算法需要扫描数据集的次数也将增多致算法需要扫描数据集的次数也将增多n n项数项数n n 随着项数的增加，需要更多的空间

29、随着项数的增加，需要更多的空间(kngjin)(kngjin)来存储项的来存储项的支持度计数。如果频繁项集的数目也随着数据项数增加而支持度计数。如果频繁项集的数目也随着数据项数增加而增长，则由于算法产生的候选项集更多，计算量和增长，则由于算法产生的候选项集更多，计算量和I/OI/O开销开销将增加将增加n n事务数事务数n n 由于由于AprioriApriori算法反复扫描数据集，因此它的运行时间随着算法反复扫描数据集，因此它的运行时间随着事务数增加而增加事务数增加而增加n n事务的平均宽度事务的平均宽度n n频繁项集的最大长度随事务平均宽度增加而增加频繁项集的最大长度随事务平均宽度增加而增加

30、n n随着事务宽度的增加，事务中将包含更多的项集，这将增随着事务宽度的增加，事务中将包含更多的项集，这将增加支持度计数时加支持度计数时HashHash树的遍历次数树的遍历次数第42页/共110页第四十三页，共110页。第43页/共110页第四十四页，共110页。6.3 规则规则(guz)的产生的产生n n6.1 问题定义(dngy)n n6.2 频繁项集的产生n n6.3 规则的产生 第44页/共110页第四十五页，共110页。规则规则(guz)产生产生n n忽略那些(nxi)前件或后件为空的规则，每个频繁k-项集能够产生多达2k-2个关联规则n n关联规则的提取：将一个项集 Y划分成两个非空

31、的子集 X 和Y-X，使得X Y X满足置信度阈值。n n如果 A,B,C,D 是频繁项集,候选项集为:n nABC D,ABD C,ACD B,BCD A,A BCD,B ACD,C ABD,D ABCAB CD,AC BD,AD BC,BC AD,BD AC,CD AB,n n这样的规则必然已经满足支持度阈值，因为它们是由频繁项集产生的。第45页/共110页第四十六页，共110页。规则规则(guz)产生产生n n怎样有效的从频繁项集中产生关联规则?n n一般，计算关联规则的置信度并不需要再次扫描事务数据集。规则A,B,C D的置信度为(ABCD)/(ABC)。因为这两个项集的支持(zhch

32、)度计数已经在频繁项集产生时得到，因此不必再扫描整个数据集n n如果规则X Y-X不满足置信度阈值，则形如XY-X的规则一定也不满足置信度阈值，其中X是X的子集。n n 例如：c(ABC D)c(AB CD)c(A BCD)n n 因为(AB)(ABC)，则(ABCD)/(ABC)(ABCD)/(AB)，则c(ABC D)c(AB CD)n n 第46页/共110页第四十七页，共110页。Apriori 算法算法(sun f)中规则的产中规则的产生生被剪枝的被剪枝的规则规则低置信度规则(guz)第47页/共110页第四十八页，共110页。Apriori 算法中规则算法中规则(guz)的产生的产

33、生第48页/共110页第四十九页，共110页。6.4 频繁频繁(pnfn)项集的紧凑表示项集的紧凑表示n n6.1 问题定义n n6.2 频繁项集的产生n n6.3 规则(guz)的产生 n n6.4 频繁项集的紧凑表示第49页/共110页第五十页，共110页。频繁频繁频繁频繁(pnfn)(pnfn)项集的紧凑表示项集的紧凑表示项集的紧凑表示项集的紧凑表示n n由事务数据集产生的频繁项集的数量可能非常大。因此，从中识别出可以推导出其他所有由事务数据集产生的频繁项集的数量可能非常大。因此，从中识别出可以推导出其他所有(su(su y y u)u)的频繁的频繁项集的，较小的，具有代表性的项集是有用

34、的。项集的，较小的，具有代表性的项集是有用的。n n频繁项集的数量频繁项集的数量n n需要紧凑的表示需要紧凑的表示第50页/共110页第五十一页，共110页。极大极大极大极大(j d)(j d)频繁项集（频繁项集（频繁项集（频繁项集（Maximal Frequent ItemsetMaximal Frequent Itemset）频繁频繁(pnfn)项集的边界项集的边界不频繁不频繁(pnfn)项项集集极大频繁项极大频繁项集集极大频繁项集是这样的频繁项集，它的直接超集都不是频繁的极大频繁项集是这样的频繁项集，它的直接超集都不是频繁的非频繁的非频繁的频繁的频繁的第51页/共110页第五十二页，共1

35、10页。极大极大极大极大(j d)(j d)频繁项集的特点频繁项集的特点频繁项集的特点频繁项集的特点n n优点：极大频繁项集有效地提供了频繁项集的紧凑表示。n n 换句话说，极大频繁项集形成了可以导出所有频繁项集的最小的项集的集合。n n从图中，可以看出，所有的频繁项集是极大频繁项集 A,D,A,C,E,B,C,D,E的子集n n缺点：尽管极大频繁项集提供了一种(y zhn)紧凑表示，但是它却不包含它们子集的支持度信息。第52页/共110页第五十三页，共110页。频繁频繁(pnfn)闭项集（闭项集（Closed Frequent Itemset）n n闭项集（闭项集（Closed Itemse

36、tClosed Itemset）：项集）：项集X X是闭的，如果它的直接超集都不具有和它相同是闭的，如果它的直接超集都不具有和它相同(xin(xin tntn)的支持度计数。的支持度计数。n n换句话说，如果至少存在一个换句话说，如果至少存在一个X X的直接超集，其支持度计数与的直接超集，其支持度计数与X X相同相同(xin(xin tn tn)，X X就就不是闭的。不是闭的。n n频繁闭项集频繁闭项集:一个项集是频繁闭项集，如果它是闭的，并且它的支持度大于或等于最一个项集是频繁闭项集，如果它是闭的，并且它的支持度大于或等于最小支持度阈值。小支持度阈值。第53页/共110页第五十四页，共110

37、页。频繁频繁(pnfn)闭项集闭项集Transaction IdsNot supported by any transactions第54页/共110页第五十五页，共110页。频繁频繁(pnfn)闭项集闭项集minsup=40%#Closed Frequent Itemset=9#Maximal Frequent itemset=4第55页/共110页第五十六页，共110页。频繁项集、极大频繁项集、极大频繁项集、极大频繁项集、极大(j d)(j d)频繁项集和频繁闭项集之间的关系频繁项集和频繁闭项集之间的关系频繁项集和频繁闭项集之间的关系频繁项集和频繁闭项集之间的关系第56页/共110页第五十

38、七页，共110页。使用使用(shyng)频繁闭项集进行频繁闭项集进行支持度计数支持度计数第57页/共110页第五十八页，共110页。6.5 产生频繁产生频繁(pnfn)项集的其他项集的其他方法方法n n6.1 问题(wnt)定义n n6.2 频繁项集的产生n n6.3 规则的产生 n n6.4 频繁项集的紧凑表示n n6.5 产生频繁项集的其他方法第58页/共110页第五十九页，共110页。产生频繁产生频繁产生频繁产生频繁(pnfn)(pnfn)项集的其他方法项集的其他方法项集的其他方法项集的其他方法n n项集格遍历项集格遍历n n一般到特殊一般到特殊 vs vs 特殊到一般。特殊到一般。n

39、n一般到特殊：适合于频繁一般到特殊：适合于频繁(pnfn)(pnfn)项集的最大长度不是太长的时候。项集的最大长度不是太长的时候。n n特殊到一般：适合于处理频繁特殊到一般：适合于处理频繁(pnfn)(pnfn)项集的最大长度较长的时候项集的最大长度较长的时候第59页/共110页第六十页，共110页。产生产生产生产生(ch(ch nshng)nshng)频繁项集的其他方法频繁项集的其他方法频繁项集的其他方法频繁项集的其他方法n n项集格遍历项集格遍历n n等价类：将格划分为两个不相交的节点组（或等价类）。频繁项集产生等价类：将格划分为两个不相交的节点组（或等价类）。频繁项集产生(ch(ch n

40、shng)nshng)算法依算法依次在每个等价类内搜索频繁项集次在每个等价类内搜索频繁项集n nAprioriApriori算法采用的逐层策略可以看作根据项集的大小划分格。等价类也可以根据项集的前缀算法采用的逐层策略可以看作根据项集的大小划分格。等价类也可以根据项集的前缀或后缀来定义。或后缀来定义。第60页/共110页第六十一页，共110页。产生产生(chnshng)频繁项频繁项集的其他方法集的其他方法n n项集格遍历项集格遍历n n宽度优先与深度优先宽度优先与深度优先n n通常通常(tngchng)(tngchng)，深度优先搜索方法是用于发现极大频繁项集的算法，深度优先搜索方法是用于发现极

41、大频繁项集的算法第61页/共110页第六十二页，共110页。产生产生(chnshng)频繁项频繁项集的其他方法集的其他方法n n事务数据集的表示(biosh)n n水平数据分布（horizontal data layout）n n垂直（vertical data layout）第62页/共110页第六十三页，共110页。6.6 FP增长增长(zngzhng)算法算法n n6.1 问题定义n n6.2 频繁项集的产生n n6.3 规则(guz)的产生 n n6.4 频繁项集的紧凑表示n n6.5 产生频繁项集的其他方法n n6.6 FP增长算法第63页/共110页第六十四页，共110页。FP增长

42、增长(zngzhng)算法（算法（FP-growth Algorithm）n n该算法采用完全不同的方法来发现频繁项集。n n该算法不同于Apriori算法的“产生-测试”范型。而是使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集。n nFP树是一种输入(shr)数据的压缩表示，它通过逐个读入事务，并把每个事务映射到FP树中的一条路径来构造。第64页/共110页第六十五页，共110页。构造构造(guzo)FP树树n n扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序n n算法第二次扫描数据集，构建FP树。读入第一个事务a，b之后，创建标

43、记为a和b的结点。然后形成null-a-b路径，对该事务编码。该路径上的所有结点的频度计数为1.n n读入第二个事务b，c，d之后，为项b，c和d创建新的结点集。然后，连接结点null-b-c-d，形成一条代表(dibio)该事务的路径。该路径上的每个结点的频度计数也等于1.尽管前两个事务具有一个共同项b，但是它们的路径不相交，因为这两个事务没有共同的前缀。第65页/共110页第六十六页，共110页。构造构造(guzo)FP树树nullA:1B:1nullA:1B:1B:1C:1D:1读入事务读入事务(shw)TID=1后后:读入事务读入事务(shw)TID=2后后:第66页/共110页第六十

44、七页，共110页。n n第三个事务a，c，d，e与第一个事务共享一个共同的前缀项a，所以第三个事务的路径null-a-c-d-e与第一个事务的路径null-a-b部分重叠。因为它们的路径重叠，所以结点a的频度(pn d)计数增加为2.n n继续该过程，直到每个事务都映射到FP树的一条路径。第67页/共110页第六十八页，共110页。构造构造(guzo)FP树树D:1E:1nullA:1B:1B:1C:1D:1读入事务读入事务(shw)TID=3后后:C:1第68页/共110页第六十九页，共110页。构造构造(guzo)FP树树nullA:8B:5B:2C:2D:1C:1D:1C:3D:1D:1

45、E:1E:1D:1E:1Header table第69页/共110页第七十页，共110页。构造构造(guzo)FP树树n n通常(tngchng)，FP树的大小比未压缩的数据小，因为购物篮数据的事务常常共享一些共同项。如果共同项较少，FP树对存储空间的压缩效果将不明显。n nFP树的大小也依赖于项如何排序。一般按照支持度计数递减序可以导致较小的FP树。但也有一些例外。n nFP树还包含一个连接具有相同项的结点的指针列表。这些指针有助于方便快捷地访问树中的项。第70页/共110页第七十一页，共110页。构造构造(guzo)FP树树第71页/共110页第七十二页，共110页。FP增长增长(zngz

46、hng)（FP-growth）算法）算法n nFP增长是一种以自底向上方式探索(tn su)树，由FP树产生频繁项集的算法。n n由于每一个事务都映射到FP树中的一条路径，因而通过仅考察包含特定结点（例如e）的途径，就可以发现以e结尾的频繁项集。使用与结点e相关联的指针，可以快速访问这些路径。第72页/共110页第七十三页，共110页。FP增长增长(zngzhng)（FP-growth）算法）算法第73页/共110页第七十四页，共110页。FP增长增长(zngzhng)（FP-growth）算法）算法第74页/共110页第七十五页，共110页。FP增长增长(zngzhng)（FP-growth

47、）算法）算法第75页/共110页第七十六页，共110页。6.7 关联关联(gunlin)模式的评估模式的评估n n6.1 问题定义n n6.2 频繁项集的产生n n6.3 规则(guz)的产生 n n6.4 频繁项集的紧凑表示n n6.5 产生频繁项集的其他方法n n6.6 FP增长算法n n6.7 关联模式的评估第76页/共110页第七十七页，共110页。关联关联(gunlin)模式的评估模式的评估（Pattern Evaluation）n n关联分析算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。因此，建立一组广泛接受的评价关联模式质量的标准是非常重要的。n n第一组标准可以通过

48、统计论据建立。涉及相互独立的项或覆盖少量事务(shw)的模式被认为是不令人感兴趣的，因为它们可能反映数据中的伪联系。n n这些令人感兴趣的模式可以使用客观兴趣度度量来排除。第77页/共110页第七十八页，共110页。n n第二组标准可以通过主观论据建立。一个模式被主观认为是无趣的，除非它能够揭示料想不到的信息或提供导致有益的行动的有用信息。n n例如：黄油 面包可能不是有趣的，尽管有很高的支持度和置信度，但是它表示的关系显而易见。另一方面，规则尿布 啤酒是有趣的，因为这种联系十分(shfn)出乎意料，并且可能为零售商提供新的交叉销售机会。n n将主观知识加入到模式的评价中是一项困难的任务，因为

49、需要来自领域专家的大量先验信息。下面是一些将主观信息加入到模式发现任务中的方法。第78页/共110页第七十九页，共110页。兴趣兴趣兴趣兴趣(xngq)(xngq)度客观度量（度客观度量（度客观度量（度客观度量（objective interestingness measureobjective interestingness measure）n n客观兴趣度度量使用从数据推导出的统计量来确定模式是否是有趣的。n n客观兴趣度度量的例子包括支持度、置信度、相关性。n n给定一个规则(guz)X Y,我们可以构建一个相依表（contingency table）。YY Xf11f10f1+X f0

50、1f00fo+f+1f+0|T|Contingency table for X Y第79页/共110页第八十页，共110页。支持支持(zhch)度度-置信度框架的局置信度框架的局限性限性n n现有的关联规则的挖掘算法依赖于支持度和置信度来除去现有的关联规则的挖掘算法依赖于支持度和置信度来除去没有意义的模式。没有意义的模式。n n例子：假定例子：假定(ji(ji dng)dng)希望分析爱喝咖啡和爱喝茶的人之希望分析爱喝咖啡和爱喝茶的人之间的关系。收集一组人关于饮料偏爱的信息，并汇总到下间的关系。收集一组人关于饮料偏爱的信息，并汇总到下表表6-86-8。CoffeeCoffeeTea150502