序列模式第4讲

1关联规则Miningvariouskindsofassociationrules本讲内容2MiningVariousKindsofAssociationRulesMiningmulti-levelassociationMimingmulti-dimensionalassociationMiningquantitativeassociationMininginterestingcorrelationpatterns3Multi-levelARmining在多维空间中，由于数据通常比较稀疏，很难在较低概念层发现有用的关联规则，数据项之间的关系通常出现在相对高的层中.如:IBMComputer和HPPrinter之间可能找不出什么关联,但Computer和Printer之间却有关联但是，对某一个用户具有含义的规则对另一用户可能并没有什么用，所以数据挖掘应该给用户提供可以在多个抽象层挖掘的能力并能在多维空间中漫游。4多层挖掘算法自顶向下,逐层挖掘使用统一的minisupp优点:简单缺点:如果minisupp过大,低层会丢失很多规则如果minisupp过小,高层会产生很多无用规则使用不同的minisupp5使用不同的minisupp，方法1Levelbylevel：每一层独立地进行挖掘例如：如果“ComputerFurniture”不频繁，则大多数情况下用不着再考察“ComputerChair”。缺点：效率低，不利用背景知识，要考察很多不可能频繁的项目6使用不同的minisupp，方法2Level-crossFilteringbyk-itemset：如果父结点是频繁的k-itemset，则进一步考察孩子结点是否是频繁的k-itemset，否则修剪掉P249图缺点：丢掉了一些有用的规则7使用不同的minisupp，方法3Level-crossFilteringbysingleitem：如果父结点是频繁项目，则进一步考察孩子结点，否则修剪掉缺点：由于minisupp不同，父结点不频繁，子节点有可能频繁，可能丢掉规则8使用不同的minisupp，方法4改进Level-crossFilteringbysingleitem：增加一个“levelpassagethreshold”，如果父结点不频繁，但满足passingdown条件，则需要进一步考察子结点。“levelpassagethreshold”：一般设置为当前层的minisupp和下一层的minisupp之间的一个值。9去掉冗余的多层规则例如：DesktopComputer→b/wprinter（support=0.08,confidence=0.7）IBMDesktopComputer→b/wprinter(support=0.02,confidence=0.72)(冗余)如果一条规则的支持度和可信度接近于它的预期值，则说它是冗余的。预期值是由它的祖先规则和子项目在父项目中所占的比例决定的。例如：上例中IBMDesktopComputer占DesktopComputer比例为0.25的话，则“预期”支持度为0.02.10MiningMulti-DimensionalAssociationSingle-dimensionalrules:buys(X,“milk”)buys(X,“bread”)Multi-dimensionalrules:2dimensionsorpredicatesInter-dimensionassoc.rules(norepeatedpredicates)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)hybrid-dimensionassoc.rules(repeatedpredicates)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)CategoricalAttributes:finitenumberofpossiblevalues,noorderingamongvalues—datacubeapproachQuantitativeAttributes:numeric,implicitorderingamongvalues—discretization,clustering,andgradientapproaches11MiningQuantitativeAssociations按照对待数值属性的不同方法,分为:1.静态方法:数值属性根据预先定义好的概念层次被离散化。离散化发生在挖掘之前.静态例如：收入被离散化为“0-20k”，“21-30k”,等等2.动态方法:数值属性根据数据的分布被离散到多个“bins”中。这些“bins”在数据挖掘的过程中可以进一步结合起来。动态3.基于距离的AR:数值属性的离散化是为了捕捉数据间的语义.动态离散过程考虑数据点之间的距离，故称为基于距离的AR12MiningQuantitativeAssociations数值属性在挖掘之前被离散为以区间段表示的分类属性，如果需要的话分类属性还可以用更一般的高层概念取代。1.从关系表中挖掘Apriori算法稍作修改就可以用来找到所有的频繁谓词集合（用所有的相关属性而不止是buys一个属性）。可以用hashing，partitioning，sampling等策略来提高性能。2.从cube中挖掘相关cube可能已经存在，这时可以使用Apriori中用到的策略，可以用来减少候选谓词集合的数目。当相关的cube不存在的情况下，则必须先构建此cube，已经有很多快速计算cube的方法，可以修改一下，在cube构建的同时查找频繁谓词集合。13MiningQuantitativeAssociations在挖掘的过程中用动态离散方法来离散数值属性以满足某些挖掘标准，例如挖掘出来的规则的可信度或紧密度（compactness）最大。例如：两维AR，左边具有两个量化属性，右边具有一个分类属性age(X,“30-39”)∧income（X,“4000-4900”）→buys（X,“colorTV”）14MiningQuantitativeAssociations将属性对映射到一个二维的格子中，然后在该格子中查找点群，再由此点群得到关联规则。共分三步.第一步:bining：将数据属性离散化为区间等宽：每个bin的距离间隔一样。等深：每个bin所具有的元组的数目相等。等质：bin的大小决定后，每一个bin中的元组是统一分布的ARCS采用等宽划分,用所有的bin组合创建一个二维数组，数据元素为每个分类进行计数15MiningQuantitativeAssociations16第二步:扫描二维数组,寻找频繁谓词集,产生关联规则第三步:借用cluster方法,合并关联规则如:age(X,34)∧income（X,“3000-4000”）→buys（X,“colorTV”）age(X,34)∧income（X,“4000-4900”）→buys（X,“colorTV”）age(X,35)∧income（X,“3000-4000”）→buys（X,“colorTV”）age(X,35)∧income（X,“4000-4900”）→buys（X,“colorTV”）合并为:age(X,“34-35”)∧income（X,“3000-4900”）→buys（X,“colorTV”）MiningQuantitativeAssociations17MiningQuantitativeAssociations前面的方法没有捕捉到数据之间的语义联系.基于距离的AR,捕捉数据之间的语义并允许近似的数据值.如:Item_type(X,“electronic”)∧Manufacturer(X,“foreign”)→Price(X,$200)某个foreignelectronicitem可以近似于20018MiningQuantitativeAssociations基于距离的AR挖掘包括两个阶段:1.在每个维上运用cluster方法划分区间(离散化)2.寻找频繁的clustergroup19CorrelationAnalysis用support+confidence挖掘出的规则有时无用，某些商品是被随机放入购物篮中的例如：类似这样的规则，{牛奶，黄油}—〉面包，它的可信度非常大，可能是因为很多人都购买面包，象这样的规则是无用的。前后之间并没有因果关系20CorrelationAnalysis相关分析：根据项目的相关性来寻找项目之间的相互关系相关性：如果CorrA,B1,A和B负相关,互相排斥如果CorrA,B=1,A和B不相关,互相独立如果CorrA,B1,A和B正相关,互相吸引)()|()()()()()()(,BPABPBPApBAPBPAPBAPCorrBA21CorrelationandLiftP(B|A)/P(B)iscalledtheliftofruleA=B22CorrelationAnalysis举例P(game)=0.6,P(video)=0.75P(game,video)=0.4CorrA,B=P(game,video)/P(game)*P(video)=0.4/(0.6*0.75)=0.891,game和video负相关,互相排斥gamegameallvideo400035007500video20005002500all600040001000023CorrelationruleMining重要属性:upwardClosed如果项目集S是相关的,则S的所有超集都是相关的.RandomWalkAlgorithm:开始,项目集为空,然后,每次增加一个项目,看该项目集是否相关,一旦相关,则算法停止24Constraint-basedAssociationMining一般来说,给定相关数据,从中挖掘出的无用规则太多,为此由用户提供一些限制,引导挖掘1.Knowledgeconstraints:指定要挖掘的知识的类型,如AR2.Dataconstraints:指定相关的数据3.Dimension/levelconstraint:指定挖掘时所用的维或层4.Interestingnessconstraint:指定用来度量规则是否有用的统计值,如support和confidence5.Ruleconstraint:指定要挖掘的规则的形式,如metarule25Metarule-GuidedMiningofARMetarule是一种规则模板,用来指定用户所兴趣的规则的语法形式,进而引导挖掘过程,提高挖掘效率例如:某市场推销人员可能想知道具有哪两个特点的人倾向于购买教育软件,为此,设定如下规则模板:P1(X,Y)∧P2(X,Y)→buys(X,“educationalsoftware”)与之相匹配的一条规则如下:P1(X,“30-39”)∧P2(X,“4000-5000”)→buys(X,“educationalsoftware”)26Metarule-GuidedMiningofAR假设需要挖掘如下的关联规则:P1∧P2∧…∧Pm→Q1∧Q2∧…∧Qn1.找出所有的频繁谓词集L(m+n)(满足最小支持度)2.计算L(m+n)的子集Lm的支持度(满足最小可信度)这是典型的多维查询,但这里只需要使用(m+n)维的cuboid和m维的cuboid,其他的不需要.所以,如果这两类cuboid没有实体化的话,则需要现计算27MiningGuidedbyAdditionalRuleConstraint可以用一个associationminingquery来设定更多的限制例如一个电器商店具有下面的数据库表:Sales(customer-name,item-name,transaction-id)Lives(customer-name,region,city)Item(it