《大型数据库中的关联规则挖掘ppt课件》由会员分享，可在线阅读，更多相关《大型数据库中的关联规则挖掘ppt课件（41页珍藏版）》请在金锄头文库上搜索。
1、13-14王 灿数据挖掘 0703004大型数据库中的关联规则 挖掘什么是关联规则挖掘？n关联规则挖掘：q从事务数据库，关系数据库和其他信息存储中的大 量数据的项集之间发现有趣的、频繁出现的模式、 关联和相关性。n应用：q购物篮分析、分类设计、捆绑销售等“尿布与啤酒”典型关联分析案例n采用关联模型比较典型的案例是“尿布与啤酒” 的故事。在美国，一些年轻的父亲下班后经常 要到超市去买婴儿尿布，超市也因此发现了一 个规律，在购买婴儿尿布的年轻父亲们中，有 30%40%的人同时要买一些啤酒。超市随后 调整了货架的摆放，把尿布和啤酒放在一起， 明显增加了销售额。同样的，我们还可以根据 关联规则在商品销
2、售方面做各种促销活动。购物篮分析n如果问题的全域是商店中所有商品的集合，则对每 种商品都可以用一个布尔量来表示该商品是否被顾 客购买，则每个购物篮都可以用一个布尔向量表示 ；而通过分析布尔向量则可以得到商品被频繁关联 或被同时购买的模式，这些模式就可以用关联规则 表示（0001001100，这种方法丢失了什么信息？）n关联规则的两个兴趣度度量q支持度q置信度关联规则：基本概念n给定：q项的集合：I=i1,i2,.,inq任务相关数据D是数据库事务的集合，每个事务T则 是项的集合，使得q每个事务由事务标识符TID标识；qA,B为两个项集，事务T包含A当且仅当n则关联规则是如下蕴涵式：q其中 并且
3、 ，规则 在事 务集D中成立，并且具有支持度s和置信度c基本概念示例n项的集合 I=A,B,C,D,E,Fn每个事务T由事务标识符TID标识，它是项的集合 q比如：TID(2000)=A,B,Cn任务相关数据D是数据库事务的集合规则度量：支持度和置信度Customer buys diaperCustomer buys bothCustomer buys beern对所有满足最小支持度和 置信度的关联规则q支持度s是指事务集D中包 含 的百分比q置信度c是指D中包含A的事 务同时也包含B的百分比n假设最小支持度为50%， 最小置信度为50%，则有 如下关联规则qA C (50%, 66.6%)q
4、C 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（仅涉及bu
5、ys这个维）n多维关联规则关联规则挖掘分类 (2)q根据规则集所涉及的抽象层n单层关联规则n多层关联规则 （在不同的抽象层发现关联规则）q根据关联挖掘的各种扩充n挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）n挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超 集c，使得每个包含c的事务也包含c）n（最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频 繁项集）由事务数据库挖掘单维布尔关联规则n最简单的关联规则挖掘，即单维、单层、布尔关联规 则的挖掘。最小支持度 50% 最小置信度 50%n对规则A C，其支持度 =50%n置信度Apriori算法 (1)nApriori算法是挖
6、掘布尔关联规则频繁项集的算法nApriori算法利用的是Apriori性质：频繁项集的所有非 空子集也必须是频繁的。q 模式不可能比A更频繁的出现qApriori算法是反单调的，即一个集合如果不能通过测试，则 该集合的所有超集也不能通过相同的测试。qApriori性质通过减少搜索空间，来提高频繁项集逐层产生的 效率Apriori算法 (2)nApriori算法利用频繁项集性质的先验知识（ prior knowledge），通过逐层搜索的迭代方法 ，即将k-项集用于探察(k+1)-项集，来穷尽数 据集中的所有频繁项集。q先找到频繁1-项集集合L1,然后用L1找到频繁2-项集 集合L2，接着用L2
7、找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删除。Aprio
8、ri算法示例Database TDB1st scanC1L1L2C2C2 2nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsup A, B1 A, C2 A, E1 B, C2 B, E3 C, E2Itemsetsup A, C2 B, C2 B, E3 C, E2ItemsetB, C, EItemsetsup B, C, E2最小支持计数：2使用Apiori性
9、质由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由频繁项集产
10、生关联规则n同时满足最小支持度和最小置信度的才是强关 联规则，从频繁项集产生的规则都满足支持度 要求，而其置信度则可由一下公式计算：n每个关联规则可由如下过程产生：q对于每个频繁项集l，产生l的所有非空子集；q对于每个非空子集s，如果 则输出规则“ ”多层关联规则 (1)n数据项中经常会形成 概念分层n底层的数据项，其支 持度往往也较低q这意味着挖掘底层数据 项之间的关联规则必须 定义不同的支持度AllComputer accessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSon
11、ywrist padLogitechTID Items T1IBM D/C, Sony b/w T2 Ms. edu. Sw., Ms. fin. Sw. T3 Logi. mouse, Ergoway wrist pad T4IBM D/C, Ms. Fin. Sw. T5IBM D/CErgoway多层关联规则 (2)n在适当的等级挖掘出来的数据项间的关联规则 可能是非常有用的n通常，事务数据库中的数据也是根据维和概念 分层来进行储存的q这为从事务数据库中挖掘不同层次的关联规则提供了 可能。n在多个抽象层挖掘关联规则，并在不同的抽象 层进行转化，是数据挖掘系统应该提供的能力挖掘多层关联规则
12、的方法n通常，多层关联规则的挖掘还是使用置信度支持度 框架，可以采用自顶向下策略q请注意：概念分层中，一个节点的支持度肯定不小于该节点 的任何子节点的支持度q由概念层1开始向下，到较低的更特定的概念层，对每个概 念层的频繁项计算累加计数q每一层的关联规则挖掘可以使用Apriori等多种方法q例如：n先找高层的关联规则：computer - printer 20%, 60%n再找较低层的关联规则：laptop - color printer 10%, 50%多层关联一致支持度n一致支持度：对所有层都使用一致的最小支持度q优点：搜索时容易采用优化策略，即一个项如果不满 足最小支持度，它的所有子项都
13、可以不用搜索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逐层独立：
14、完全的宽度搜索，没有频繁项集的背景知识用于 剪枝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逐层
15、独立策略条件松，可能导致底层考察大量非频 繁项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
