第5讲-关联规则挖掘课件.ppt

1、第五章 关联规则挖掘什么是关联规则挖掘？n关联规则挖掘：q从事务数据库，关系数据库和其他信息存储中的大量数据的项集项集之间发现有趣有趣的、频繁出现的模式频繁出现的模式、关联关联和相关性相关性。n应用：q购物篮分析、分类设计、捆绑销售和亏本销售分析“尿布与啤酒”典型关联分析案例n采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。

2、购物篮分析n如果问题的全域全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量布尔量来表示该商品是否被顾客购买，则每个购物篮购物篮都可以用一个布尔向量表示（布尔向量表示（0001001100）；而通过分析布尔分析布尔向量向量则可以得到商品被频繁关联频繁关联或被同时购买同时购买的模式，这些模式就可以用关联规则表示n关联规则的两个兴趣度度量q支持度q置信度关联规则：基本概念n给定：q项的集合：项的集合：I=i1,i2,.,inq任务相关数据任务相关数据D是数据库事务事务的集合，每个事务事务T则是项的集合，使得q每个事务由事务标识符TID标识标识；qA,B为两个项集，事务T包含A当且仅当n则关

3、联规则是如下蕴涵式：q其中 并且 ，规则 在事务集D中成立，并且具有支持度s和置信度cIT TA ,csBA IBIA,BABA 规则度量：支持度和置信度Customerbuys diaperCustomerbuys bothCustomerbuys beern对所有满足最小支持度和置信度的关联规则q支持度支持度s是指是指事务集事务集D中包中包含含 的百分比的百分比q置信度c是指D中包含A的事事务务同时也包含B的百分比n假设最小支持度为50%，最小置信度为50%，则有如下关联规则qA C (50%,66.6%)qC A (50%,100%)BA)()(supBAPBAport)(/)()|()

4、(APBAPABPBAconfidence大型数据库关联规则挖掘过程n基本概念qk项集项集：包含k个项的集合n牛奶，面包，黄油是个3项集q项集的频率项集的频率是指包含项集的事务数q如果项集的频率大于（最小支持度D中的事务总数），则称该项集为频繁项集频繁项集n大型数据库中的关联规则挖掘包含两个过程：q找出所有频繁项集n大部分的计算都集中在这一步q由频繁项集产生强关联规则n即满足最小支持度和最小置信度的规则关联规则挖掘一个线路图n关联规则有多种分类：q根据规则中所处理的值类型值类型n布尔关联规则n量化关联规则q根据规则中设计的数据维数据维n单维关联规则n多维关联规则q根据规则集所涉及的抽象层抽象层

5、n单层关联规则n多层关联规则q根据关联挖掘的各种扩充n挖掘最大的频繁模式最大的频繁模式（该模式的任何真超模式都是非频繁的）n挖掘频繁闭项集频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c，使得每个包含c的事务也包含c）),()48.42 ,()39.30 ,(computerXbuyskkXincomeXage),(),(softwareXbuyscomputerXbuys)_ ,()39.30 ,(computerlaptopXbuysXage),()39.30 ,(computerXbuysXage由事务数据库挖掘单维布尔关联规则n最简单的关联规则挖掘，即单维、单层、布尔关联规则的

6、挖掘。Transaction ID Items Bought2000A,B,C1000A,C4000A,D5000B,E,FFrequent Itemset SupportA75%B50%C50%A,C50%最小支持度 50%最小置信度 50%n对规则A C，其支持度 =50%n置信度%6.66)(sup/)(sup)(/)()|()(AportCAportAPCAPACPCAconfidence)()(supCAPCAportApriori算法nApriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-1项集用于探察k项集，来穷尽数据集中

7、的所有频繁项集频繁项集。q先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。nApriori性质：频繁项集的所有非空子集也必须是频繁频繁项集的所有非空子集也必须是频繁的。（的。（模式不可能比模式不可能比A更频繁的出现）更频繁的出现）qApriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。BAApriori算法步骤nApriori算法由连接连接和剪枝剪枝两个步骤组成。n连接连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选候选k项集项集记为Ck。q

8、Lk-1中的两个元素L1和L2可以执行连接操作 的条件是nCk是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk。q为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。)1 1()22(.)22()1 1(21212121klklklklllll21ll Apriori算法示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A,C,D20B

9、,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使用Apiori性质由L2产生C3n1 连接：qC3=L2 L2=A,C,B,C,B,EC,E A,C,B,C,B,EC,E=A,B,C,A,C,E,B,C,En2使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频

10、繁的选项：qA,B,C的2项子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以删除这个选项；qA,C,E的2项子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以删除这个选项；qB,C,E的2项子集是B,C,B,E,C,E，它的所有2项子集都是L2的元素，因此保留这个选项。n3这样，剪枝后得到C3=B,C,E由频繁项集产生关联规则n同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由以下公式计算：n每个关联规则可由如下过程产生：q对于每个频繁项集l，产生l的所有非空子集；q对于l的每个非空子集s，如果 则输出规则“”(P15

11、5)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls提高Apriori算法的有效性(1)nApriori算法主要的挑战q要对数据进行多次扫描；q会产生大量的候选项集；q对候选项集的支持度计算非常繁琐；n解决思路q减少对数据的扫描次数；q缩小产生的候选项集；q改进对候选项集的支持度计算方法n方法1：基于hash表的项集计数q将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。

12、提高Apriori算法的有效性(2)n方法2：事务压缩（压缩进一步迭代的事务数）q不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除。n方法3：划分q挖掘频繁项集只需要两次数据扫描qD中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。n第一次扫描：将数据划分为多个部分并找到局部频繁项集n第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集提高Apriori算法的有效性(3)n方法4：选样（在给定数据的一个子集挖掘）q基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式q通过牺牲精确度来减少算法开销，为了提

13、高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式n可以通过一次全局扫描来验证从样本中发现的模式n可以通过第二此全局扫描来找到遗漏的模式n方法5：动态项集计数q在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。多层关联规则n数据项中经常会形成概念分层n底层的数据项，其支持度往往也较低n在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的n通常，事务数据库中的数据也是根据维和概念分层来进行储存的n在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供

14、的能力ComputeraccessorylaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywristpadLogitechTID ItemsT1IBM D/C,Sony b/wT2 Ms.edu.Sw.,Ms.fin.Sw.T3 Logi.mouse,Ergoway wrist padT4IBM D/C,Ms.Fin.Sw.T5IBM D/CErgowayAllsoftware挖掘多层关联规则的方法n通常，多层关联规则的挖掘还是使用置信度支持度框架，可以采用自顶向下策略q由概念层1开始向下，到较低的更

15、特定的概念层，对每个概念层的频繁项计算累加计数q可以使用Apriori等多种方法q请注意：概念分层中，一个节点的支持度肯定不小于该节点一个节点的支持度肯定不小于该节点的任何子节点的支持度的任何子节点的支持度q例如：n先找高层的关联规则：computer-printer 20%,60%n再找较低层的关联规则：laptop-color printer 10%,50%n交叉层关联规则q跨越概念层边界的规则：Computer=b/w printerq使用较低层的最小支持度值多层关联一致支持度 VS.递减支持度n一致支持度：对所有层都使用一致的最小支持度q优点：搜索时容易采用优化策略，即一个项如果不满足

16、最小支持度，它的所有子项都可以不用搜索q缺点：最小支持度值设置困难n太高：将丢掉出现在较低抽象层中有意义的关联规则n太低：会在较高层产生太多的无兴趣的规则n递减支持度：在较低层使用递减的最小支持度q抽象层越低，对应的最小支持度越小Computer support=10%Laptopsupport=6%Desktopsupport=4%min_sup=5%min_sup=5%min_sup=3%多层关联搜索策略n具有递减支持度的多层关联规则的搜索策略q逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝q层交叉单项过滤：一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的q层交叉

17、k项集过滤：一个第i层的k项集被考察，当且仅当它在第(i-1)层的对应父节点k-项集是频繁的n搜索策略比较q逐层独立策略条件松，可能导致底层考察大量非频繁项q层交叉k项集过滤策略限制太强，仅允许考察频繁k-项集的子女q层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层频繁项受控的层交叉单项过滤策略n设置一个层传递临界值，用于向较低层传递相对频繁的项。q即如果满足层传递临界值，则允许考察不满足最小支持度临界值的项的子女q用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生Computer support=10%Laptop support=6%Desktop s

18、upport=4%min_sup=12%level_passage_support=8%min_sup=3%检查冗余的多层关联规则n挖掘多层关联规则时，由于项间的“祖先”关系，有些发现的规则将是冗余的q例如：ndesktop computer=b/w printer sup=8%,con=70%(1)nIBM desktop computer=b/w printer sup=2%,con=72%(2)n上例中，我们说第一个规则是第二个规则的“祖先”n如果规则(2)中的项用它在概念分层中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，则(1)是冗余的。多维关联多维关联规

19、则概念n单维关联规则：qbuys(X,“milk”)buys(X,“bread”)n多维关联规则：涉及两个或多个维或谓词的关联规则q维间关联规则：不包含重复的谓词nage(X,”19-25”)occupation(X,“student”)=buys(X,“coke”)q混合维关联规则：包含某些谓词的多次出现nage(X,”19-25”)buys(X,“popcorn”)=buys(X,“coke”)n分类属性q具有有限个不同值，值之间无序n量化属性q数值类型的值，并且值之间有一个隐含的序挖掘多维关联规则的技术n在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集频繁谓词集。k-谓词集是

20、包含k个合取谓词的集合。q例如：age,occupation,buys是一个3-谓词集q挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法：n1.量化属性的静态离散化q使用预定义的概念分层对量化属性进行静态地离散化n2.量化关联规则q根据数据的分布，将量化属性离散化到“箱”n3.基于距离的关联规则q考虑数据点之间的距离，动态地离散化量化属性多维关联规则挖掘使用量化属性的静态离散化n量化属性使用预定义的概念分层，在挖掘前进行离散化n数值属性的值用区间代替n如果任务相关数据存在关系数据库中，则找出所有频繁的k-谓词集将需要k或k+1次表扫描n数据立方体技术非常适合挖掘多维关联规则qn-维

21、方体的单元用于存放对应n-谓词集的计计数或支持度数或支持度，0-D方体用于存放任务相关数据的事务总数n如果包含感兴趣的维的数据立方体已经存在并物化，挖掘将会很快，同时可以利用Apriori性质：频繁谓词集的每个子集也必须频繁谓词集的每个子集也必须是频繁的是频繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)挖掘基于距离的关联规则n等宽划分将很近的值分开，并创建没有数据的区间n等深划分将很远的值放在一组n基于距离的关联规则挖掘考虑属性值的接近性，紧扣区间数据的语义，并允许值的类似n基于距离的关联规

22、则挖掘的两遍算法：q1.使用聚类找出区间或簇q2.搜索频繁的一起出现的簇组，得到基于距离的关联规则Price($)Equi-width(width$10)Equi-depth(depth 2)Distance-based70,107,207,72011,2022,5020,222221,3051,5350,535031,405141,505351,60n因为未考虑数据点之间或区间的相对距离，分箱方法不是总能紧扣区间数据的语义关联规则的兴趣度度量n客观度量q两个流行的度量指标n支持度n置信度n主观度量q最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个

23、规则（模式）是有趣的，如果：n它是出人意料的n可行动的（用户可以使用该规则做某些事情）n挖掘了关联规则后，哪些规则是用户感兴趣的？强关联规则是否就是有趣的？对强关联规则的批评（1）n例1：(Aggarwal&Yu,PODS98)q在5000个学生中n3000个打篮球n3750个喝麦片粥n2000个学生既打篮球又喝麦片粥q然而，打篮球=喝麦片粥 40%,66.7%是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高q打篮球=不喝麦片粥 20%,33.3%这个规则远比上面那个要精确，尽管支持度和置信度都要低的多对强关联规则的批评（2）n例1：(书P168，表5-7)q上述数

24、据可以得出buys(X,“computer games”)=buys(X,“videos”)40%,60%q但其实全部人中购买录像带的人数是75%，比60%多；事实上录像带和游戏是负相关的。q由此可见A=B的置信度有欺骗性，它只是给出A,B条件概率的估计，而不度量A,B间蕴涵的实际强度。由关联分析到相关分析n我们需要一种度量事件间的相关性或者是依赖性的指标n当项集A的出现独立于项集B的出现时，P(AB)=P(A)P(B)，即corrA,B1，表明A与B无关，corrA,B 1表明A与B正相关，corrA,B buys(X,educational software)nY,W分别取赋给谓词变量P1

25、,P2的属性值n一般，元规则形成一个用户希望探察的假定，而系统则寻找与该元规则匹配的规则，例如：qage(X,30-39)income(X,42K-60K)buys(X,educational software)关联规则的元规则制导挖掘（2）n假定我们希望挖掘的元规则形式为：qP1P2Pl=Q1Q2Qrn设元规则中谓词的个数为p=l+r，则找出符合该模板的关联规则需以下两步骤：q找出所有的频繁p-谓词集Lpq计算Lp中的l-谓词子集的支持度，然后计算由Lp导出的规则的置信度n数据立方体具有存放聚集维值的能力，适合多维关联规则的挖掘，在n维数据立方体中(n=p)挖掘上述规则可以用以下步骤：q扫描

26、p-D方体，将每个单元中的计数和最小支持度计数比较，得到Lpq考察l-D方体，返回与元规则匹配的强关联规则用附加的规则约束制导的挖掘n在数据挖掘中，与元规则一起使用的约束还有集合/子集联系，变量初始化和聚集函数等，它们将使挖掘过程更有效mine associations as lives(C,_,Vancouver)sales+(C,?I,S)=sales+(C,?J,T)from saleswhere S.year=1999 and T.year=1999 and I.category=J.categorygroup by C,I.categoryhaving sum(I.price)=50

27、0with support threshold=1%with confidence threshold=50%P176挖掘过程中使用的规则约束n通常的数据挖掘中，知识类型和数据约束在挖掘前使用，其它约束在挖掘后用来过滤规则，但这使挖掘过程非常低效。n什么类型的规则约束可以在挖掘过程中使用，以缩小规则搜索空间？n对于频繁项集挖掘，在挖掘过程中使用的约束包括以下五种类型：q反单调的q单调的q简洁的q可转变的q不可转变的反单调的和单调的约束n如果一个项集不满足该规则约束，则它的任何一个超集都不可能满足该约束；具有这种性质的规则称为是反单调的反单调的。n如果一个项集满足该约束，则它的所有超集也满足该约束；具有这种性质的规则称为是单调单调的。的。简洁性约束n一个约束是简洁的，如果我们可以列出并仅仅列出所有确保满足该约束的集合；利用简洁性约束，我们可以在计数前进行剪枝，从而避免产生测试方式的过大开销。可转变的和不可转变的约束n有些约束不属于前面三类，但是如果项集中的项以特定的次序排列，则对于频繁项集挖掘的全过程，约束可能成为单调的或者是反单调的。例：avg(I.price)n不可转变的约束是数据挖掘中较难处理的部分，但这种约束往往较少。总结