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

13-14王 灿数据挖掘 sjwj@0703004大型数据库中的关联规则 挖掘什么是关联规则挖掘？n关联规则挖掘：q从事务数据库，关系数据库和其他信息存储中的大 量数据的项集之间发现有趣的、频繁出现的模式、 关联和相关性n应用：q购物篮分析、分类设计、捆绑销售等“尿布与啤酒”——典型关联分析案例n采用关联模型比较典型的案例是“尿布与啤酒” 的故事在美国，一些年轻的父亲下班后经常 要到超市去买婴儿尿布，超市也因此发现了一 个规律，在购买婴儿尿布的年轻父亲们中，有 30%～40%的人同时要买一些啤酒超市随后 调整了货架的摆放，把尿布和啤酒放在一起， 明显增加了销售额同样的，我们还可以根据 关联规则在商品销售方面做各种促销活动购物篮分析n如果问题的全域是商店中所有商品的集合，则对每 种商品都可以用一个布尔量来表示该商品是否被顾 客购买，则每个购物篮都可以用一个布尔向量表示 ；而通过分析布尔向量则可以得到商品被频繁关联 或被同时购买的模式，这些模式就可以用关联规则 表示（0001001100，这种方法丢失了什么信息？）n关联规则的两个兴趣度度量q支持度q置信度关联规则：基本概念n给定：q项的集合：I={i1,i2,.,in}q任务相关数据D是数据库事务的集合，每个事务T则 是项的集合，使得q每个事务由事务标识符TID标识；qA,B为两个项集，事务T包含A当且仅当n则关联规则是如下蕴涵式：q其中 并且 ，规则 在事 务集D中成立，并且具有支持度s和置信度c基本概念——示例n项的集合 I={A,B,C,D,E,F}n每个事务T由事务标识符TID标识，它是项的集合 q比如：TID(2000)={A,B,C}n任务相关数据D是数据库事务的集合规则度量：支持度和置信度Customer buys diaperCustomer buys bothCustomer buys 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 scanC1L1L2C2C2 2nd scanC3L33rd scanTidItems10A, 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使用Apiori性质由L2产生C3n1 ．连接：qC3=L2 L2= {{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}}n2．使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的 ，对候选项C3，我们可以删除其子集为非频繁的选项：q{A,B,C}的2项子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素， 所以删除这个选项；q{A,C,E}的2项子集是{A,C},{A,E},{C,E}，其中{A,E} 不是L2的元素 ，所以删除这个选项；q{B,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这意味着挖掘底层数据 项之间的关联规则必须 定义不同的支持度AllComputer accessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywrist padLogitechTID Items T1{IBM D/C, Sony b/w} T2 {Ms. edu. Sw., Ms. fin. Sw.} T3 {Logi. mouse, Ergoway wrist pad} T4{IBM D/C, Ms. Fin. Sw.} T5{IBM D/C}Ergoway多层关联规则 (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%]Laptop [support=6%]Desktop [support=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=7。