第6章挖掘大型数据库中的关联规则数据挖掘概念与技术教学课件.ppt

2023/3/11,Data Mining:Concepts and Techniques,1,第6章：挖掘大型数据库中的关联规则,6.1 关联规则挖掘,关联规则挖掘寻找给定数据集中项之间的有趣联系。,2023/3/11,Data Mining:Concepts and Techniques,2,2023/3/11,Data Mining:Concepts and Techniques,3,2023/3/11,Data Mining:Concepts and Techniques,4,6.1.2 基本概念:频繁模式和关联规则,Itemset（项集）X=x1,xk找出满足最小支持度和置信度的所规则 XY：支持度,s,事务包含 XY 的概率 置信度,c,事务含 X 也包含 Y 的条件概率.,设 min_support=50%,min_conf=50%:A C(50%,66.7%)C A(50%,100%),2023/3/11,Data Mining:Concepts and Techniques,5,挖掘关联规则一个例子,规则 A C:支持度=support(AC)=50%置信度=support(AC)/support(A)=66.6%,最小支持度 50%最小置信度 50%,2023/3/11,Data Mining:Concepts and Techniques,6,6.1.3 关联规则挖掘：一个路径图,2023/3/11,Data Mining:Concepts and Techniques,7,2023/3/11,Data Mining:Concepts and Techniques,8,2023/3/11,Data Mining:Concepts and Techniques,9,2023/3/11,Data Mining:Concepts and Techniques,10,6.2 单维关联规则挖掘算法,最简单形式的关联规则挖潜方法：关联规则是单维、单层、布尔关联规则。,2023/3/11,Data Mining:Concepts and Techniques,11,6.2.1 Apriori:一种候选产生-测试方法,Apriori性质：频繁项集的任何子集必须是频繁的。如果 beer,diaper,nuts 是频繁的,beer,diaper也是。每个包含 beer,diaper,nuts的事务 也包含 beer,diaper。Apriori 剪枝原则:如果一个项集不是频繁的,将不产生/测试它的超集反单调性。方法:由长度为k的频繁项集产生长度为(k+1)的候选项集,并且根据 DB测试这些候选。性能研究表明了它的有效性和可伸缩性。Agrawal&Srikant 1994,Mannila,et al.1994,2023/3/11,Data Mining:Concepts and Techniques,12,Apriori算法：通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集Lk的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。,2023/3/11,Data Mining:Concepts and Techniques,13,1.Apriori 算法 一个例子,数据库 TDB,第1次扫描,C1,L1,L2,C2,C2,第2次扫描,C3,L3,第3次扫描,最小支持度=2,2023/3/11,Data Mining:Concepts and Techniques,14,2.Apriori 算法,算法伪代码:Ck:长度为 k的候选项集Lk:长度为k的频繁项集L1=频繁项;for(k=1;Lk!=;k+)do begin Ck+1=由 Lk产生的候选;for each 数据库中的事务 t do 增加包含在t 中的所有候选Ck+1的计数 Lk+1=Ck+1 中满足 min_support的候选 endreturn k Lk;,2023/3/11,Data Mining:Concepts and Techniques,15,3.Apriori的重要细节,如何产生候选?步骤 1:Lk的自连接 步骤 2:剪枝入何对候选的支持度计数?候选产生的例子L3=abc,abd,acd,ace,bcd自连接:L3*L3abcd：由 abc 和 abdacde：由 acd 和 ace剪枝:acde 被删除,因为 ade 不在 L3C4=abcd,L4的每个频繁项的子集都应在L3中。,2023/3/11,Data Mining:Concepts and Techniques,16,4.如何产生候选?,假定 Lk-1 中的项集已排序步骤 1: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在p和q中，前K-2项相同，且p的第k-1项少于q的第k-1项值。Step 2:剪枝forall itemsets c in Ck doforall(k-1)-subsets s of c doif(s is not in Lk-1)then delete c from Ck,2023/3/11,Data Mining:Concepts and Techniques,17,5.完整的Apriori算法,(1)L1=频繁1项集;(2)for(k=2;Lk-1;k+)do begin(3)Ck=apriori_gen(Lk-1);/新的潜在频繁项集(4)for all transactions tD do begin(5)Ct=subset(Ck,t);/t中包含的潜在频繁项集(6)for all candidates cCt do(7)c.count+;(8)end;(9)Lk=cCk|c.countminsup(10)end;,2023/3/11,Data Mining:Concepts and Techniques,18,D：,2023/3/11,Data Mining:Concepts and Techniques,19,2023/3/11,Data Mining:Concepts and Techniques,20,6.2.2 由频繁项集产生关联规则,2023/3/11,Data Mining:Concepts and Techniques,21,2023/3/11,Data Mining:Concepts and Techniques,22,关联规则的可视化:Pane Graph,2023/3/11,Data Mining:Concepts and Techniques,23,关联规则的可视化:Rule Graph,2023/3/11,Data Mining:Concepts and Techniques,24,6.2.3 提高Apriori算法的有效性,频繁模式挖掘的挑战,挑战事务数据库的多遍扫描数量巨大的候选候选支持度计数繁重的工作量改进 Apriori:基本思想减少事务数据库的扫描遍数压缩候选数量便于候选计数,2023/3/11,Data Mining:Concepts and Techniques,25,1.基于Hash的技术,一种基于Hash的技术可以用于压缩候选k项集Ck（k1）。,2023/3/11,Data Mining:Concepts and Techniques,26,由C1中的候选1项集产生1项集L1时，可以对每个事务产生所有的2项集。,Hash函数：h(Ii,Ij)=(i*10+j)mod 7,若支持度=3，则0、1、3和4桶中的项集不可能是频繁的。频繁项：I2,I3:4、I1,I2:4、I1,I3:4,2023/3/11,Data Mining:Concepts and Techniques,27,2.事务压缩,不包含任何k项集的事务不可能包含任何k+1项集。这样，这种事务在其后的考虑时，可以加上标记或删除。因为为产生j项集（jk），扫描数据库时不再需要它们。,2023/3/11,Data Mining:Concepts and Techniques,28,3.划分:只扫描数据库两次,项集在DB中是频繁的,它必须至少在DB的一个划分中是频繁的扫描 1:划分数据库,并找出局部频繁模式。扫描 2:求出全局频繁模式。,2023/3/11,Data Mining:Concepts and Techniques,29,4.选样计算频繁模式,选取给定数据库D的随机样本S，然后，在S而不是D中找频繁项集。牺牲一些精度换取了有效性。,2023/3/11,Data Mining:Concepts and Techniques,30,5.动态项集计数,将数据库划分为标记开始点的块。不像Aprior仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。,2023/3/11,Data Mining:Concepts and Techniques,31,频繁模式挖掘的瓶颈,多遍数据库扫描是 昂贵的。挖掘长模式需要很多遍扫描,并产生大量候选。挖掘频繁模式 i1i2i100扫描次数:100候选个数:(1001)+(1002)+(110000)=2100-1=1.27*1030!瓶颈:候选产生-测试。能够避免候选产生吗?,6.2.4 不产生候选挖掘频繁项集,2023/3/11,Data Mining:Concepts and Techniques,32,挖掘频繁模式而不产生候选,使用局部频繁的项,由短模式增长产生长模式“abc”是频繁模式得到包含“abc”的所有事务:DB|abc“d”是 DB|abc 中的局部频繁项 abcd 是频繁模式,2023/3/11,Data Mining:Concepts and Techniques,33,由事务数据库构造FP树（FrequentPattern tree）,min_support=3,TIDItems 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,o,wf,b400 b,c,k,s,pc,b,p500 a,f,c,e,l,p,m,nf,c,a,m,p,扫描 DB 一次,找出频繁 1-itemset(单个项的模式)按频率的降序将频繁项排序,得到 f-list再次扫描 DB,构造 FP树,F-list=f-c-a-b-m-p,2023/3/11,Data Mining:Concepts and Techniques,34,FP树结构的优点,完全性 保留频繁模式挖掘的完整信息。不截断任何事务的长模式。压缩性压缩无关信息非频繁的项被删除。项按频率的降序排列:越是频繁出现,越可能被共享。绝对不比原来的数据库大(不计结点链和计数字段)。对于Connect-4 DB,压缩率超过 100。,2023/3/11,Data Mining:Concepts and Techniques,35,基本思想(分而治之)用FP-tree地归增长频繁集方法 对每个项，生成它的 条件模式库,然后是它的 条件 FP-tree。对每个新生成的条件FP-tree，重复这个步骤。直到结果FP-tree为空,或只含维一的一个路径(此路径的每个子路径对应的项集都是频繁集)。,2023/3/11,Data Mining:Concepts and Techniques,36,为FP-tree中的每个节点生成条件模式基。用条件模式基构造对应的条件FP-tree。递归构造条件 FP-trees 同时增长其包含的频繁集如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。,挖掘 FP-tree的主要步骤,2023/3/11,Data Mining:Concepts and Techniques,37,条件 模式基itemcond.pattern basecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1,步骤1:从 FP-tree 到条件模式基,从FP-tree的头表开始。按照每个频繁项的连接遍历 FP-tree。列出能够到达此项的所有前缀路径，得到条件模式基。,2023/3/11,Data Mining:Concepts and Techniques,38,FP-tree支持条件模式基构造的属性,节点链接任何包含ai,的可能频繁集，都可以从FP-tree头表中的ai沿着ai 的节点链接得到。前缀路径要计算路径P 中包含节点ai 的频繁集，只要考察到达ai 的路径前缀即可，且其支持度等于节点ai 的支持度。,2023/3/11,Data Mining:Concepts and Techniques,39,对于每个条件模式基累计条件模式基中每个项的计数。构造模式基中频繁项的FP树。,m-条件 模式基:fca:2,fcab:1,涉及 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,头表Item frequency head f4c4a3b3m3p3,min_support=3,步骤2:建立条件 FP-tree,2023/3/11,Data Mining:Concepts and Techniques,40,通过建立条件模式基得到频繁集,2023/3/11,Data Mining:Concepts and Techniques,41,“am”的条件模式基:(fc:3),“cm”的条件模式基:(f:3),f:3,cm-条件 FP树,“cam”的条件模式基:(f:3),f:3,cam-条件 FP树,第3步:递归挖掘条件FP-tree,2023/3/11,Data Mining:Concepts and Techniques,42,使用FP树挖掘频繁模式,基本思想:频繁模式增长通过模式和数据库划分递归地增长频繁模式。方法 对于每个频繁项,构造它的条件模式基,然后构造它的条件 FP树。在新构造的条件FP树上重复这一过程。直到结果条件 FP树为空,或者它只包含一条路径单个路径将产生其子路径的所有组合,每个子路径是一个频繁模式。,2023/3/11,Data Mining:Concepts and Techniques,43,FP增长算法,2023/3/11,Data Mining:Concepts and Techniques,44,2023/3/11,Data Mining:Concepts and Techniques,45,6.2.5 FP树的存放,FP树不能放在内存,怎么办?数据库投影数据库投影首先将数据库划分成一组投影 数据库。然后对每个投影数据库构造并挖掘FP树。并行投影 vs.划分投影 技术。并行投影空间花费很大。,2023/3/11,Data Mining:Concepts and Techniques,46,基于划分的投影,并行 投影 需要大量磁盘空间划分投影 节省,2023/3/11,Data Mining:Concepts and Techniques,47,FP增长 vs.Apriori:随支持度增长的可伸缩性,Data set T25I20D10K,2023/3/11,Data Mining:Concepts and Techniques,48,FP增长 vs.树-投影:随支持度增长的可伸缩性,Data set T25I20D100K,2023/3/11,Data Mining:Concepts and Techniques,49,6.3 挖掘各种关联/相关规则,多层关联规则是这样的一些规则：它们涉及多个抽象层中的项。,2023/3/11,Data Mining:Concepts and Techniques,50,项常常形成层次结构。灵活的支持度设定:较低层中的项一般具有较低的支持度。事务数据库可以基于维和层进行编码。探测共享的多层挖掘。,6.3.1 多层关联规则,2023/3/11,Data Mining:Concepts and Techniques,51,一种自顶向下,逐步深入的方法:首先挖掘最高层的频繁模式:milk(15%),bread(10%)然后挖掘它们下层“较弱的”频繁模式:50%milk(5%),wheat bread(4%)多层之间的不同的最小支持度阈值导致不同的算法:如果不同层之间采用相同的min_support则丢弃 t 如果 t的任意祖先是非频繁的.如果在较低层采用递减的 min_support则只考察其祖先为频 繁的项集.,6.3.2 挖掘多层关联规则的方法,2023/3/11,Data Mining:Concepts and Techniques,52,一致的支持度,Milksupport=10%,2%Milk support=6%,Skim Milk support=4%,层 1min_sup=5%,层 2min_sup=5%,对于所有层使用一致的最小支持度（一致支持度）,2023/3/11,Data Mining:Concepts and Techniques,53,Milksupport=10%,2%Milk support=6%,Skim Milk support=4%,Level 1min_sup=5%,Level 2min_sup=3%,递减的支持度,对于所有层使用一致的最小支持度（一致支持度）,2023/3/11,Data Mining:Concepts and Techniques,54,逐层独立完全是宽度搜索，没有频繁项集的背景知识用于剪枝。,2023/3/11,Data Mining:Concepts and Techniques,55,层交叉单项过滤一个第i层的项被考虑，当且仅当它在第i-1层的父节点是频繁的。,2023/3/11,Data Mining:Concepts and Techniques,56,层交叉k项集过滤一个第i层的k项集被考虑，当且仅当它在第i-1层的对应父节点k项集是频繁的。,均被考察,2023/3/11,Data Mining:Concepts and Techniques,57,6.3.3 多层关联:冗余过滤,由于项之间的“祖先”联系,有些规则可能是多余的。例如：milk（牛奶）wheat bread support=8%,confidence=70%50%milk（含50的牛奶）wheat bread support=2%,confidence=72%我们可以说第一个规则是第二个规则的祖先。一个规则是冗余的,如果根据规则的祖先,其支持度接近于“期望”值。,2023/3/11,Data Mining:Concepts and Techniques,58,6.4 挖掘多维关联的技术,搜索频繁 k-谓词集:例:age,occupation,buys 是一个 3-谓词集。可以按如何处理 age 对技术分类。使用量化属性的静态离散化使用预先定义的概念分层,对量化属性静态地离散化。量化关联规则根据数据的分布,将量化属性离散化到“箱”。基于距离的关联规则是一种动态的离散化过程,它考虑数据点之间的距离。,2023/3/11,Data Mining:Concepts and Techniques,59,6.4.1 多维关联规则,单维规则:buys(X,“milk”)buys(X,“bread”)多维规则:维或谓词 2 维间关联规则(不含重复谓词)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)混合维关联规则(含重复谓词)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)分类属性有限个不同值,值之间无序。量化属性数值的,值之间隐含次序。,2023/3/11,Data Mining:Concepts and Techniques,60,6.4.2 量化属性的静态离散化,使用概念分层,在挖掘之前离散化。数值值用区间值替换。在关系数据库中,找出所有的频繁 k-谓词集需要k 或 k+1 次表扫描。数据方非常适合挖掘。n-维单元 对应于谓词集合的方体。从数据方挖掘可以快得多。方体是多维数据结构，可以存放任务相关的数据。,n维方体的单元用于存放对应n谓词集的计数或支持度。,2023/3/11,Data Mining:Concepts and Techniques,61,6.4.3 挖掘量化关联规则,数值属性动态地离散化使得挖掘的规则的置信度或紧凑性最大化。2-D 量化关联规则:Aquan1 Aquan2 Acat使用2-D方体单元,对“相邻的”关联规则聚类形成一般关联规则.例:age(X,”30-34”)income(X,”24K-48K”)buys(X,”high resolution TV”),2023/3/11,Data Mining:Concepts and Techniques,62,6.4.4 挖掘基于距离的关联规则,分箱方法不能紧扣区间数据的语义。基于距离的划分,更有意义的离散化考虑:区间内点的密度/数量。区间内点的“紧密性”。,等宽分箱分深分箱基于同质的分箱,2023/3/11,Data Mining:Concepts and Techniques,63,6.5 由关联挖掘到相关分析,play basketball eat cereal 40%,66.7%是误导吃谷类食品的学生所占的百分比为75%,比 66.7%还高.play basketball not eat cereal 20%,33.3%更准确,其支持度和置信度都较低,强关联规则不一定是有趣的,2023/3/11,Data Mining:Concepts and Techniques,64,依赖/相关事件的度量:,corrA,B表示A和B的出现之间的相关性。该值小于1，则A的出现和B的出现是负相关的；该值等于1，则A和B是独立的，它们之间没有相关性。,2023/3/11,Data Mining:Concepts and Techniques,65,6.6 基于约束的关联挖掘,自动地找出数据库中的所有模式?不现实!模式可能太多,并不聚焦!数据挖掘应当是一个 交互的 过程 用户使用数据挖掘查询语言(或图形用户界面)指导需要挖掘什么。基于约束的挖掘用户灵活性:提供挖掘的 约束 系统优化:考察限制,寻找有效的挖掘基于约束的挖掘。,2023/3/11,Data Mining:Concepts and Techniques,66,6.6.1 数据挖掘的约束,知识类型约束:分类,关联,等。数据约束 使用类 SQL查询找出 Vancouver 2000年12月份一起销售的产品对。维/层约束关于 region,price,brand,customer category规则(或模式)约束小额销售(价格$200)。兴趣度约束强规则:min_support 3%,min_confidence 60%。,2023/3/11,Data Mining:Concepts and Techniques,67,6.6.2 受约束的挖掘 vs.基于约束的搜索,受约束的挖掘 vs.基于约束的搜索/推理二者都旨在减小搜索空间。找出满足约束的 所有模式 vs.AI中基于约束的搜索,找出 某些(或某个)解。约束推进 vs.启发式搜索。如何将二者集成,是一个有趣的研究问题。受约束的挖掘 vs.DBMS的查询处理数据库查询需要找出所有的。受约束的模式挖掘与查询处理的推进选择的思想类似。,2023/3/11,Data Mining:Concepts and Techniques,68,6.6.3 受约束的挖掘:挖掘查询优化问题,给定频繁模式挖掘查询,和约束集C,算法应当可靠的:仅发现满足给定约束C的频繁模式。完全的:发现满足给定约束C的所有频繁模式。一种朴素的方法首先找出所有的频繁模式,然后检查它们是否满足约束。更有效的方法:分析约束的性质。尽可能推进约束 到频繁模式的计算中。,2023/3/11,Data Mining:Concepts and Techniques,69,6.6.4 基于约束挖掘的反单调性,反单调性当项集 S 违反约束时,它的任何超集合也违反约束sum(S.Price)v 是反单调的sum(S.Price)v 不是反单调的例.C:range(S.profit)15是反单调的项集 ab 违反约束 C。ab的每个超集也违反约束C。,TDB(min_sup=2),反单调性：如果一个项集不满足该规则约束，则它的任何超集也不可能满足该规则约束。,2023/3/11,Data Mining:Concepts and Techniques,70,哪些约束是反单调的?,2023/3/11,Data Mining:Concepts and Techniques,71,基于约束挖掘的单调性,单调性当项集 S 满足约束时,它的任何超集合也满足约束。sum(S.Price)v 是单调的min(S.Price)v 是单调的例.C:range(S.profit)15项集 ab 满足 Cab的每个超集合也满足C,TDB(min_sup=2),2023/3/11,Data Mining:Concepts and Techniques,72,哪些约束是单调的?,2023/3/11,Data Mining:Concepts and Techniques,73,简洁性,简洁性:给定满足约束C 的项的集合 A1,则满足C 的任意集合S 都基于 A1,即,S 包含一个属于A1 的子集。思想:不查看事务数据库,项集S 是否满足约束C可以根据选取的项确定。min(S.Price)v 是简洁的sum(S.Price)v 不是简洁的优化:如果 C 是简洁的,C 是预计数可推进的(pre-counting pushable)。,简洁性：可以列出并且仅仅列出所有确保满足该约束的集合。,2023/3/11,Data Mining:Concepts and Techniques,74,哪些约束是简洁的?,2023/3/11,Data Mining:Concepts and Techniques,75,Apriori 算法 一个例子,Database D,Scan D,C1,L1,L2,C2,C2,Scan D,C3,L3,Scan D,2023/3/11,Data Mining:Concepts and Techniques,76,朴素算法:Apriori+约束,Database D,Scan D,C1,L1,L2,C2,C2,Scan D,C3,L3,Scan D,约束:SumS.price 5,最小支持度=2,2023/3/11,Data Mining:Concepts and Techniques,77,受约束的Apriori 算法:推进反单调约束,Database D,Scan D,C1,L1,L2,C2,C2,Scan D,C3,L3,Scan D,约束:SumS.price 5,最小支持度=2,2023/3/11,Data Mining:Concepts and Techniques,78,受约束的Apriori 算法:推进简洁约束,Database D,Scan D,C1,L1,L2,C2,C2,Scan D,C3,L3,Scan D,约束:minS.price 5,最小支持度=2,2023/3/11,Data Mining:Concepts and Techniques,79,约束的分类,可转变反单调,可转变单调,强可转变,不可转变的,简洁,反单调,单调,