第5讲-关联规则挖掘

第五章关联规则挖掘什么是关联规则挖掘？关联规则挖掘：从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。应用：购物篮分析、分类设计、捆绑销售和亏本销售分析“尿布与啤酒”——典型关联分析案例采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。购物篮分析如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示（0001001100）；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示关联规则的两个兴趣度度量支持度置信度关联规则：基本概念给定：项的集合：I={i1,i2,...,in}任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得每个事务由事务标识符TID标识；A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：其中并且，规则在事务集D中成立，并且具有支持度s和置信度c规则度量：支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer对所有满足最小支持度和置信度的关联规则支持度s是指事务集D中包含的百分比置信度c是指D中包含A的事务同时也包含B的百分比假设最小支持度为50%，最小置信度为50%，则有如下关联规则AC(50%,66.6%)CA(50%,100%)大型数据库关联规则挖掘过程基本概念k－项集：包含k个项的集合{牛奶，面包，黄油}是个3－项集项集的频率是指包含项集的事务数如果项集的频率大于（最小支持度×D中的事务总数），则称该项集为频繁项集大型数据库中的关联规则挖掘包含两个过程：找出所有频繁项集大部分的计算都集中在这一步由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则关联规则挖掘——一个线路图关联规则有多种分类：根据规则中所处理的值类型布尔关联规则量化关联规则根据规则中设计的数据维单维关联规则多维关联规则根据规则集所涉及的抽象层单层关联规则多层关联规则根据关联挖掘的各种扩充挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c`，使得每个包含c的事务也包含c`）由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。最小支持度50%最小置信度50%对规则A

C，其支持度=50%置信度Apriori算法Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将k-1项集用于探察k项集，来穷尽数据集中的所有频繁项集。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。Apriori性质：频繁项集的所有非空子集也必须是频繁的。（

模式不可能比A更频繁的出现）Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。Apriori算法步骤Apriori算法由连接和剪枝两个步骤组成。连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。Lk-1中的两个元素L1和L2可以执行连接操作的条件是Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk

。为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。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使用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}}由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由以下公式计算：每个关联规则可由如下过程产生：对于每个频繁项集l，产生l的所有非空子集；对于l的每个非空子集s，如果 则输出规则“ ”(P155)提高Apriori算法的有效性(1)Apriori算法主要的挑战要对数据进行多次扫描；会产生大量的候选项集；对候选项集的支持度计算非常繁琐；解决思路减少对数据的扫描次数；缩小产生的候选项集；改进对候选项集的支持度计算方法方法1：基于hash表的项集计数将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。提高Apriori算法的有效性(2)方法2：事务压缩（压缩进一步迭代的事务数）不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除。方法3：划分挖掘频繁项集只需要两次数据扫描D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。第一次扫描：将数据划分为多个部分并找到局部频繁项集第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集提高Apriori算法的有效性(3)方法4：选样（在给定数据的一个子集挖掘）基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式可以通过一次全局扫描来验证从样本中发现的模式可以通过第二此全局扫描来找到遗漏的模式方法5：动态项集计数在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。多层关联规则数据项中经常会形成概念分层底层的数据项，其支持度往往也较低在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的通常，事务数据库中的数据也是根据维和概念分层来进行储存的在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力ComputeraccessorylaptopfinancialmousecolorprintercomputerdesktopIBMedu.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}ErgowayAllsoftware挖掘多层关联规则的方法通常，多层关联规则的挖掘还是使用置信度－支持度框架，可以采用自顶向下策略由概念层1开始向下，到较低的更特定的概念层，对每个概念层的频繁项计算累加计数可以使用Apriori等多种方法请注意：概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度例如：先找高层的关联规则：computer->printer[20%,60%]再找较低层的关联规则：laptop->colorprinter[10%,50%]交叉层关联规则跨越概念层边界的规则：Computer=>b/wprinter使用较低层的最小支持度值多层关联——一致支持度VS.递减支持度一致支持度：对所有层都使用一致的最小支持度优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索缺点：最小支持度值设置困难太高：将丢掉出现在较低抽象层中有意义的关联规则太低：会在较高层产生太多的无兴趣的规则递减支持度：在较低层使用递减的最小支持度抽象层越低，对应的最小支持度越小min_sup=5%min_sup=5%min_sup=3%多层关联——搜索策略具有递减支持度的多层关联规则的搜索策略逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝层交叉单项过滤：一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的层交叉k项集过滤：一个第i层的k项集被考察，当且仅当它在第(i-1)层的对应父节点k-项集是频繁的搜索策略比较逐层独立策略条件松，可能导致底层考察大量非频繁项层交叉k项集过滤策略限制太强，仅允许考察频繁k-项集的子女层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层频繁项受控的层交叉单项过滤策略设置一个层传递临界值，用于向较低层传递相对频繁的项。即如果满足层传递临界值，则允许考察不满足最小支持度临界值的项的子女用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生min_sup=12%level_passage_support=8%min_sup=3%检查冗余的多层关联规则挖掘多层关联规则时，由于项间的“祖先”关系，有些发现的规则将是冗余的例如：desktopcomputer=>b/wprinter[sup=8%,con=70%] (1)IBMdesktopcomputer=>b/wprinter[sup=2%,con=72%](2)上例中，我们说第一个规则是第二个规则的“祖先”如果规则(2)中的项用它在概念分层中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，则(1)是冗余的。多维关联规则——概念单维关联规则：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-谓词集挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法：1.量化属性的静态离散化使用预定义的概念分层对量化属性进行静态地离散化2.量化关联规则根据数据的分布，将量化属性离散化到“箱”3.基于距离的关联规则考虑数据点之间的距离，动态地离散化量化属性多维关联规则挖掘——使用量化属性的静态离散化量化属性使用预定义的概念分层，在挖掘前进行离散化数值属性的值用区间代替如果任务相关数据存在关系数据库中，则找出所有频繁的k-谓词集将需要k或k+1次表扫描数据立方体技术非常适合挖掘多维关联规则n-维方体的单元用于存放对应n-谓词集的计数或支持度，0-D方体用于存放任务相关数据的事务总数如果包含感兴趣的维的数据立方体已经存在并物化，挖掘将会很快，同时可以利用Apriori性质：频繁谓词集的每个子集也必须是频繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)挖掘基于距离的关联规则等宽划分将很近的值分开，并创建没有数据的区间等深划分将很远的值放在一组基于距离的关联规则挖掘考虑属性值的接近性，紧扣区间数据的语义，并允许值的类似基于距离的关联规则挖掘的两遍算法：1.使用聚类找出区间或簇2.搜索频繁的一起出现的簇组，得到基于距离的关联规则因为未考虑数据点之间或区间的相对距离，分箱方法不是总能紧扣区间数据的语义关联规则的兴趣度度量客观度量两个流行的度量指标支持度置信度主观度量最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果：它是出人意料的可行动的（用户可以使用该规则做某些事情）挖掘了关联规则后，哪些规则是用户感兴趣的？强关联规则是否就是有趣的？对强关联规则的批评（1）例1：(Aggarwal&Yu,PODS98)在5000个学生中3000个打篮球3750个喝麦片粥2000个学生既打篮球又喝麦片粥然而，打篮球=>喝麦片粥[40%,66.7%]是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高打篮球=>不喝麦片粥[20%,33.3%]这个规则远比上面那个要精确，尽管支持度和置信度都要低的多对强关联规则的批评（2）例1：(书P168，表5-7)上述数据可以得出buys(X,“computergames”)=>buys(X,“videos”)[40%,60%]但其实全部人中购买录像带的人数是75%，比60%多；事实上录像带和游戏是负相关的。由此可见A=>B的置信度有欺骗性，它只是给出A,B条件概率的估计，而不度量A,B间蕴涵的实际强度。由关联分析到相关分析我们需要一种度量事件间的相关性或者是依赖性的指标当项集A的出现独立于项集B的出现时，P(A∪B)=P(A)P(B)，即corrA,B＝1，表明A与B无关，corrA,B>1表明A与B正相关，corrA,B<1表明A与B负相关将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性为：P({game,video})/(P({game})×P({video}))=0.4/(0.75×0.6)=0.89结论：录像带和游戏之间存在负相关基于约束的关联挖掘如何对海量数据进行交互性的，解释性的挖掘？充分的利用各种约束条件知识类型约束数据约束维/层约束兴趣度约束规则约束指定要挖掘的规则形式，可以用元规则来表示，说明规则的前件和后件中谓词的最大和最小个数，或属性、属性值和/或聚集之间的联系关联规则的元规则制导挖掘（1）元规则使得用户可以说明他们感兴趣的规则的语法形式例：在AllElectronics数据库中挖掘时使用一个元规则表达顾客的特点和他购买的商品之间的关联（具有哪两种特点的顾客会买educationalsoftware?）P1(X,Y)∧P2(X,W)=>buys(X,"educationalsoftware")Y,W分别取赋给谓词变量P1,P2的属性值一般，元规则形成一个用户希望探察的假定，而系统则寻找与该元规则匹配的规则，例如：age(X,"30-39")income(X,"42K-60K")buys(X,"educationalsoftware")关联规则的元规则制导挖掘（2）假定我们希望挖掘的元规则形式为：P1∧P2∧…∧Pl=>Q1∧Q2∧…∧Qr设元规则中谓词的个数为p=l+r，则找出符合该模板的关联规则需以下两步骤：找出所有的频繁p-谓词集Lp计算Lp中的l-谓词子集的支持度，然后计算由Lp导出的规则的置信度数据立方体具有存放聚集维值的能力，适合多维关联规则的挖掘，在n维数据立方体中(n>=p)挖掘上述