大型数据库中的关联规则挖掘

《大型数据库中的关联规则挖掘》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、13-14王灿数据挖掘sjwj@dlc.zju.edu.cn0703004大型数据库中的关联规则挖掘什么是关联规则挖掘？关联规则挖掘：从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。应用：购物篮分析、分类设计、捆绑销售等“尿布与啤酒”——典型关联分析案例采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市

2、随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。购物篮分析如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（0001001100，这种方法丢失了什么信息？）关联规则的两个兴趣度度量支持度置信度关联规则：基本概念给定：项的集合：I={i1,i2,...,in}任

3、务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得每个事务由事务标识符TID标识；A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：其中并且，规则在事务集D中成立，并且具有支持度s和置信度c基本概念——示例项的集合I={A,B,C,D,E,F}每个事务T由事务标识符TID标识，它是项的集合比如：TID(2000)={A,B,C}任务相关数据D是数据库事务的集合规则度量：支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer对

4、所有满足最小支持度和置信度的关联规则支持度s是指事务集D中包含的百分比置信度c是指D中包含A的事务同时也包含B的百分比假设最小支持度为50%，最小置信度为50%，则有如下关联规则AC(50%,66.6%)CA(50%,100%)大型数据库关联规则挖掘(1)基本概念k－项集：包含k个项的集合{牛奶，面包，黄油}是个3－项集项集的频率是指包含项集的事务数如果项集的频率大于（最小支持度×D中的事务总数），则称该项集为频繁项集大型数据库关联规则挖掘(2)大型数据库中的关联规则挖掘包含两个过程：找出所有频繁项集

5、大部分的计算都集中在这一步由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则关联规则挖掘分类(1)关联规则有多种分类：根据规则中所处理的值类型布尔关联规则量化关联规则（规则描述的是量化的项或属性间的关联性）根据规则中涉及的数据维单维关联规则（仅涉及buys这个维）多维关联规则关联规则挖掘分类(2)根据规则集所涉及的抽象层单层关联规则多层关联规则（在不同的抽象层发现关联规则）根据关联挖掘的各种扩充挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在

6、其真超集c’，使得每个包含c的事务也包含c’）（最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项集）由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。最小支持度50%最小置信度50%对规则AC，其支持度=50%置信度Apriori算法(1)Apriori算法是挖掘布尔关联规则频繁项集的算法Apriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。模式不可能比A更频繁的出现Apriori算法是反单调的，即一个集合如果不能通过测试，则该

7、集合的所有超集也不能通过相同的测试。Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率Apriori算法(2)Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。Apriori算法步骤Apriori算法由连接和剪枝两个步骤组成。连接：为了找L

8、k，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。Lk-1中的两个元素L1和L2可以执行连接操作的条件是Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk。为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。Aprio