6、大型数据库中关联规则挖掘.ppt

大型数据库中的关联规则挖掘什么是关联规则挖掘？n关联规则挖掘：q从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。n应用：q购物篮分析、分类设计、捆绑销售等“尿布与啤酒”典型关联分析案例n采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。购物篮分析n如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（0001001100，这种方法丢失了什么信息？）n关联规则的两个兴趣度度量q支持度q置信度关联规则：基本概念n给定：q项的集合：I=i1,i2,.,inq任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得q每个事务由事务标识符TID标识；qA,B为两个项集，事务T包含A当且仅当n则关联规则是如下蕴涵式：q其中 并且 ，规则 在事务集D中成立，并且具有支持度s和置信度c基本概念示例n项的集合 I=A,B,C,D,E,Fn每个事务T由事务标识符TID标识，它是项的集合 q比如：TID(2000)=A,B,Cn任务相关数据D是数据库事务的集合规则度量：支持度和置信度Customerbuys diaperCustomerbuys bothCustomerbuys beern对所有满足最小支持度和置信度的关联规则q支持度s是指事务集D中包含 的百分比q置信度c是指D中包含A的事务同时也包含B的百分比n假设最小支持度为50%，最小置信度为50%，则有如下关联规则qA C (50%,66.6%)qC A (50%,100%)大型数据库关联规则挖掘(1)n基本概念qk项集项集：包含k个项的集合n牛奶，面包，黄油是个3项集q项集的频率项集的频率是指包含项集的事务数q如果项集的频率大于（最小支持度D中的事务总数），则称该项集为频繁项集频繁项集大型数据库关联规则挖掘(2)n大型数据库中的关联规则挖掘包含两个过程：q找出所有频繁项集n大部分的计算都集中在这一步q由频繁项集产生强关联规则n即满足最小支持度和最小置信度的规则关联规则挖掘分类(1)n关联规则有多种分类：q根据规则中所处理的值类型n布尔关联规则n量化关联规则（规则描述的是量化的项或属性间的关联性）q根据规则中涉及的数据维n单维关联规则n（仅涉及buys这个维）n多维关联规则关联规则挖掘分类(2)q根据规则集所涉及的抽象层n单层关联规则n多层关联规则（在不同的抽象层发现关联规则）q根据关联挖掘的各种扩充n挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）n挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c，使得每个包含c的事务也包含c）n（最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项集）由事务数据库挖掘单维布尔关联规则n最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。最小支持度 50%最小置信度 50%n对规则A C，其支持度 =50%n置信度Apriori算法(1)nApriori算法是挖掘布尔关联规则频繁项集的算法nApriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。q 模式不可能比A更频繁的出现qApriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。qApriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率Apriori算法(2)nApriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。q先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。Apriori算法步骤nApriori算法由连接连接和剪枝剪枝两个步骤组成。n连接：连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选候选k项集项集记为Ck。qLk-1中的两个元素L1和L2可以执行连接操作 的条件是nCk是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk。q为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。Apriori算法示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A,C,D20B,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最小支持计数：2使用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，我们可以删除其子集为非频繁的选项：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对于每个非空子集s，如果 则输出规则“”多层关联规则(1)n数据项中经常会形成概念分层n底层的数据项，其支持度往往也较低q这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度AllComputeraccessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.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/CErgoway多层关联规则(2)n在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的n通常，事务数据库中的数据也是根据维和概念分层来进行储存的q这为从事务数据库中挖掘不同层次的关联规则提供了可能。n在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力挖掘多层关联规则的方法n通常，多层关联规则的挖掘还是使用置信度支持度框架，可以采用自顶向下策略q请注意：概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度q由概念层1开始向下，到较低的更特定的概念层，对每个概念层的频繁项计算累加计数q每一层的关联规则挖掘可以使用Apriori等多种方法q例如：n先找高层的关联规则：computer-printer 20%,60%n再找较低层的关联规则：laptop-color printer 10%,50%多层关联一致支持度n一致支持度：对所有层都使用一致的最小支持度q优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索q缺点：最小支持度值设置困难n太高：将丢掉出现在较低抽象层中有意义的关联规则n太低：会在较高层产生太多的无兴趣的规则多层关联递减支持度n使用递减支持度，可以解决使用一致支持度时在最小支持度值上设定的困难n递减支持度：在较低层使用递减的最小支持度q每一层都有自己的一个独立的最小支持度q抽象层越低，对应的最小支持度越小Computer support=10%Laptopsupport=6%Desktopsupport=4%min_sup=5%min_sup=5%min_sup=3%多层关联搜索策略(1)n具有递减支持度的多层关联规则的搜索策略q逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝q层交叉单项过滤：一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的（P165,图6-14）n(computer)(laptop computer,desktop computer)q层交叉k项集过滤：一个第i层的k项集被考察，当且仅当它在第(i-1)层的对应父节点k-项集是频繁的（P165,图6-15）n(computer,printer)(laptop computer,color printer),(desktop computer,b/w printer)多层关联搜索策略(2)n搜索策略比较q逐层独立策略条件松，可能导致底层考察大量非频繁项q层交叉k项集过滤策略限制太强，仅允许考察频繁k-项集的子女q层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层频繁项（图6-14)受控的层交叉单项过滤策略n层交叉单项过滤策略的改进版本n设置一个层传递临界值，用于向较低层传递相对频繁的项。q即如果满足层传递临界值，则允许考察不满足最小支持度临界值的项的子女q用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生Computer support=10%Laptop support=6%Desktop support=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)是冗余的。多维关联规则概念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在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。k-谓词集是包含k个合取谓词的集合。q例如：age,occupation,buys是一个3-谓词集挖掘多维关联规则的技术n数据属性可以分为分类属性和量化属性q分类属性n具有有限个不同值，值之间无序q量化属性n数值类型的值，并且值之间有一个隐含的序n挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法：q1.量化属性的静态离散化n使用预定义的概念分层对量化属性进行静态地离散化q2.量化关联规则n根据数据的分布，将量化属性离散化到“箱”q3.基于距离的关联规则n考虑数据点之间的距离，动态地离散化量化属性多维关联规则挖掘使用量化属性的静态离散化n量化属性使用预定义的概念分层，在挖掘前进行离散化n数值属性的值用区间代替n如果任务相关数据存在关系数据库中，则找出所有频繁的k-谓词集将需要k或k+1次表扫描n数据立方体技术非常适合挖掘多维关联规则qn-维方体的单元用于存放对应n-谓词集的计计数或支持度数或支持度，0-D方体用于存放任务相关数据的事务总数n如果包含感兴趣的维的数据立方体已经存在并物化，挖掘将会很快，同时可以利用Apriori性质：频繁谓词集的每个子集也必须频繁谓词集的每个子集也必须是频繁的是频繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)挖掘量化关联规则(1)n量化关联规则中，数值属性将根据某种挖掘标准，进行动态的离散化q例如：最大化挖掘规则的置信度和紧凑性n为了简化量化关联规则挖掘的讨论，我们将聚焦于类似以下形式的2-维量化关联规则维量化关联规则：Aquan1 Aquan2 Acatq（两个量化属性和一个分类属性间的关联）q例如：age(X,”30-39”)income(X,”42K-48K”)buys(X,”high resolution TV”)挖掘量化关联规则(2)n找出这类2-维量化关联规则的方法：关联规则聚类系统(ARCS)q一种源于图像处理的技术，该技术将量化属性对映射到满足给定分类属性条件的2-D栅格上，然后通过搜索栅格点的聚类而产生关联规则关联规则聚类系统(ARCS)(1)nARCS过程中的步骤包括q1.分箱（根据不同分箱方法创建一个2-D数组），本步骤的目的在于减少量化属性相对应的巨大的值个数，使得2-D栅格的大小可控n等宽分箱n等深分箱n基于同质的分箱（每个箱中元组一致分布）q2.找出频繁谓词集n扫描分箱后形成的2-D数组，找出满足最小支持度和置信度的频繁谓词集关联规则聚类系统(ARCS)(2)q3.关联规则聚类n将上一步得到的强关联规则映射到2-D栅格上，使用聚类算法，扫描栅格，搜索规则的矩形聚类ARCS的局限性n所挖掘的关联规则左手边只能是量化属性n规则的左手边只能有两个量化属性（2-D栅格的限制）n一种不基于栅格的，可以发现更一般关联规则的技术，其中任意个数的量化属性和分类属性可以出现在规则的两端q等深分箱动态划分q根据部分完全性部分完全性的度量进行聚类挖掘基于距离的关联规则n等宽划分将很近的值分开，并创建没有数据的区间n等深划分将很远的值放在一组n基于距离的关联规则挖掘考虑属性值的接近性，紧扣区间数据的语义，并允许值的类似n基于距离的关联规则挖掘的两遍算法：q1.使用聚类找出区间或簇q2.搜索频繁的一起出现的簇组，得到基于距离的关联规则n因为未考虑数据点之间或区间的相对距离，分箱方法不是总能紧扣区间数据的语义关联规则的兴趣度度量n客观度量q两个流行的度量指标n支持度n置信度n主观度量q最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果：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：(书P172，表6-4)q上述数据可以得出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 1表明A与B负相关q将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性为：qP(game,video)/(P(game)P(video)=0.4/(0.750.6)=0.89q结论：录像带和游戏之间存在负相关