第四章关联规则挖掘年

第四章关联规则挖掘年第1页，共35页，2023年，2月20日，星期三“尿布与啤酒”——典型关联分析案例采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。第2页，共35页，2023年，2月20日，星期三一、基本概念给定：项的集合：I={i1,i2,...,in}T={t1,t2…tn}是数据库中事务的集合，每个事务ti则是项的集合，使得则为T中的关联规则。其中并且第3页，共35页，2023年，2月20日，星期三规则度量：支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer对所有满足最小支持度和置信度的关联规则支持度s是指事务集T中包含的百分比置信度c是指T中包含A同时也包含B的事务占包含A的事务的百分比最小支持度min_sup最小置信度min_conf第4页，共35页，2023年，2月20日，星期三强关联规则：如果事务集合T中的关联规则AB同时满足support(AB)>min_sup,confidence(AB)>min_conf,则AB称为T中的强关联规则。关联规则挖掘就是在事务集合中挖掘强关联规则。

第5页，共35页，2023年，2月20日，星期三k－项集：包含k个项的集合{牛奶，面包，黄油}是个3－项集如果K—项集的频率(即支持计数)大于最小支持计数（最小支持度×T中的事务总数n），则称该项集为频繁K—项集第6页，共35页，2023年，2月20日，星期三二、关联规则挖掘步骤大型数据库中的关联规则挖掘包含两个过程：找出所有频繁项集大部分的计算都集中在这一步由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则第7页，共35页，2023年，2月20日，星期三Apriori算法定理一如果某k-项集不是频繁k-项集，则包含IK的(k+1)--项集也不是频繁(k+1)--项集。该性质称为Apriori性质。第8页，共35页，2023年，2月20日，星期三由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。最小支持度50%最小置信度50%对规则A

C，其支持度置信度第9页，共35页，2023年，2月20日，星期三Apriori算法思想一.扫描一次事务集合，找出频繁1项集集合L1；二.基于L1，产生候选2项集集合C2，再扫描一次事务集合，比较候选支持计数与最小支持计数，找出频繁2项集L2；三.基于L2，找出C3，作剪枝运算，得到剪枝后的C3，再扫描一次事务集合，确定L3；四.以此类推，直至找出频繁项集为止。最后在所有频繁项集中产生强关联规则。第10页，共35页，2023年，2月20日，星期三Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2最小支持计数：2第11页，共35页，2023年，2月20日，星期三使用Apiori性质由L2产生C31．连接：C3=L2L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项：{A,B,C}的2项子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以删除这个选项；{A,C,E}的2项子集是{A,C},{A,E},{C,E}，其中{A,E}

不是L2的元素，所以删除这个选项；{B,C,E}的2项子集是{B,C},{B,E},{C,E}，它的所有2－项子集都是L2的元素，因此保留这个选项。3．这样，剪枝后得到C3={{B,C,E}}第12页，共35页，2023年，2月20日，星期三由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算：每个关联规则可由如下过程产生：对于每个频繁项集l，产生l的所有非空子集；对于每个非空子集s，如果 则输出规则“ ”第13页，共35页，2023年，2月20日，星期三多层关联规则(1)数据项中经常会形成概念分层底层的数据项，其支持度往往也较低这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度AllComputeraccessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywristpadLogitechTIDItemsT1{IBMD/C,Sonyb/w}T2{M.Sw.,Ms.fin.Sw.}T3{Logi.mouse,Ergowaywristpad}T4{IBMD/C,Ms.Fin.Sw.}T5{IBMD/C}Ergoway第14页，共35页，2023年，2月20日，星期三多层关联规则(2)在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的通常，事务数据库中的数据也是根据维和概念分层来进行储存的这为从事务数据库中挖掘不同层次的关联规则提供了可能。在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力第15页，共35页，2023年，2月20日，星期三挖掘多层关联规则的方法通常，多层关联规则的挖掘还是使用置信度－支持度框架，可以采用自顶向下策略请注意：概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度由概念层1开始向下，到较低的更特定的概念层，对每个概念层的频繁项计算累加计数每一层的关联规则挖掘可以使用Apriori等多种方法例如：先找高层的关联规则：computer->printer[20%,60%]再找较低层的关联规则：laptop->colorprinter[10%,50%]第16页，共35页，2023年，2月20日，星期三多层关联——一致支持度一致支持度：对所有层都使用一致的最小支持度优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索缺点：最小支持度值设置困难太高：将丢掉出现在较低抽象层中有意义的关联规则太低：会在较高层产生太多的无兴趣的规则第17页，共35页，2023年，2月20日，星期三多层关联——递减支持度使用递减支持度，可以解决使用一致支持度时在最小支持度值上设定的困难递减支持度：在较低层使用递减的最小支持度每一层都有自己的一个独立的最小支持度抽象层越低，对应的最小支持度越小min_sup=5%min_sup=5%min_sup=3%Computer[support=10%]Laptop[support=6%]Desktop[support=4%]第18页，共35页，2023年，2月20日，星期三多层关联——搜索策略(1)具有递减支持度的多层关联规则的搜索策略逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝层交叉单项过滤：一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的（P165,图6-14）(computer)(laptopcomputer,desktopcomputer)层交叉k项集过滤：一个第i层的k项集被考察，当且仅当它在第(i-1)层的对应父节点k-项集是频繁的（P165,图6-15）(computer,printer)((laptopcomputer,colorprinter),(desktopcomputer,b/wprinter)…)第19页，共35页，2023年，2月20日，星期三多层关联——搜索策略(2)搜索策略比较逐层独立策略条件松，可能导致底层考察大量非频繁项层交叉k项集过滤策略限制太强，仅允许考察频繁k-项集的子女层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层频繁项（图6-14)第20页，共35页，2023年，2月20日，星期三受控的层交叉单项过滤策略层交叉单项过滤策略的改进版本设置一个层传递临界值，用于向较低层传递相对频繁的项。即如果满足层传递临界值，则允许考察不满足最小支持度临界值的项的子女用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生min_sup=12%level_passage_support=8%min_sup=3%Computer[support=10%]Laptop[support=6%]Desktop[support=4%]第21页，共35页，2023年，2月20日，星期三检查冗余的多层关联规则挖掘多层关联规则时，由于项间的“祖先”关系，有些发现的规则将是冗余的例如：desktopcomputer=>b/wprinter[sup=8%,con=70%] (1)IBMdesktopcomputer=>b/wprinter[sup=2%,con=72%](2)上例中，我们说第一个规则是第二个规则的“祖先”如果规则(2)中的项用它在概念分层中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，则(1)是冗余的。第22页，共35页，2023年，2月20日，星期三多维关联规则——概念单维关联规则：buys(X,“milk”)＝buys(X,“bread”)多维关联规则：涉及两个或多个维或谓词的关联规则维间关联规则：不包含重复的谓词age(X,”19-25”)∧occupation(X,“student”)=>buys(X,“coke”)混合维关联规则：包含某些谓词的多次出现age(X,”19-25”)∧buys(X,“popcorn”)=>buys(X,“coke”)在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。k-谓词集是包含k个合取谓词的集合。例如：{age,occupation,buys}是一个3-谓词集第23页，共35页，2023年，2月20日，星期三挖掘多维关联规则的技术数据属性可以分为分类属性和量化属性分类属性具有有限个不同值，值之间无序量化属性数值类型的值，并且值之间有一个隐含的序挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法：1.量化属性的静态离散化使用预定义的概念分层对量化属性进行静态地离散化2.量化关联规则根据数据的分布，将量化属性离散化到“箱”3.基于距离的关联规则考虑数据点之间的距离，动态地离散化量化属性第24页，共35页，2023年，2月20日，星期三多维关联规则挖掘——使用量化属性的静态离散化量化属性使用预定义的概念分层，在挖掘前进行离散化数值属性的值用区间代替如果任务相关数据存在关系数据库中，则找出所有频繁的k-谓词集将需要k或k+1次表扫描数据立方体技术非常适合挖掘多维关联规则n-维方体的单元用于存放对应n-谓词集的计数或支持度，0-D方体用于存放任务相关数据的事务总数如果包含感兴趣的维的数据立方体已经存在并物化，挖掘将会很快，同时可以利用Apriori性质：频繁谓词集的每个子集也必须是频繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)第25页，共35页，2023年，2月20日，星期三挖掘量化关联规则(1)量化关联规则中，数值属性将根据某种挖掘标准，进行动态的离散化例如：最大化挖掘规则的置信度和紧凑性为了简化量化关联规则挖掘的讨论，我们将聚焦于类似以下形式的2-维量化关联规则：Aquan1

Aquan2Acat（两个量化属性和一个分类属性间的关联）例如：age(X,”30-39”)income(X,”42K-48K”)buys(X,”highresolutionTV”)第26页，共35页，2023年，2月20日，星期三挖掘量化关联规则(2)找出这类2-维量化关联规则的方法：关联规则聚类系统(ARCS)一种源于图像处理的技术，该技术将量化属性对映射到满足给定分类属性条件的2-D栅格上，然后通过搜索栅格点的聚类而产生关联规则第27页，共35页，2023年，2月20日，星期三关联规则聚类系统(ARCS)(1)ARCS过程中的步骤包括1.分箱（根据不同分箱方法创建一个2-D数组），本步骤的目的在于减少量化属性相对应的巨大的值个数，使得2-D栅格的大小可控等宽分箱等深分箱基于同质的分箱（每个箱中元组一致分布）2.找出频繁谓词集扫描分箱后形成的2-D数组，找出满足最小支持度和置信度的频繁谓词集第28页，共35页，2023年，2月20日，星期三关联规则聚类系统(ARCS)(2)3.关联规则聚类将上一步得到的强关联规则映射到2-D栅格上，使用聚类算法，扫描栅格，搜索规则的矩形聚类第29页，共35页，2023年，2月20日，星期三ARCS的局限性所挖掘的关联规则左手边只能是量化属性规则的左手边只能有两个量化属性（2-D栅格的限制）一种不基于栅格的，可以发现更一般关联规则的技术，其中任意个数的量化属性和分类属性可以出现在规则的两端等深分箱动态划分根据部分完全性的度量进行聚类第30页，共35页，2023年，2月20日，星期三挖掘基于距离的关联规则等宽划分将很近的值分开，并创建没有数据的区间等深划分将很远的值放在一组基于距离的关联规则挖掘考虑属性值的接近性，紧扣区间数据的语义，并允许值的类似基于距离的关联规则挖掘的两遍算法：1.使用聚类找出区间或簇2.搜索频繁的一起出现的簇组，得到基于距离的关联规则因为未考虑数据点之间或区间的相对距离，分箱方法不是总能紧扣区间数据的语义第31页，共35页，2023年，2月20日，星期三关联规则的兴趣度度量客观度量两个流行的度量指标支持度置信度主观度量最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果：它是出人意料的可行动的（用户可以使用该规则做某些事情）挖掘了关联规则后，哪些规则是用户感兴趣的？强关联规则是否就是有趣的？第32页，共35页，2