《大型数据库中的关联规则挖掘讲义教材》由会员分享，可在线阅读，更多相关《大型数据库中的关联规则挖掘讲义教材（41页珍藏版）》请在金锄头文库上搜索。
1、,13-14,王 灿,数据挖掘,0703004,大型数据库中的关联规则挖掘,什么是关联规则挖掘？,关联规则挖掘： 从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。 应用： 购物篮分析、分类设计、捆绑销售等,购物篮分析,如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（0001001100，这种方法丢失了什么信息？） 关联规则的两个兴趣度度量 支持度 置信度,关联规则：
2、基本概念,给定： 项的集合：I=i1,i2,.,in 任务相关数据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是数据库事务的集合,D,规则度量：支持度和置信度,Customer buys diaper,Customer buys both,Customer buys bee
3、r,对所有满足最小支持度和置信度的关联规则 支持度s是指事务集D中包含 的百分比 置信度c是指D中包含A的事务同时也包含B的百分比 假设最小支持度为50%，最小置信度为50%，则有如下关联规则 A C (50%, 66.6%) C A (50%, 100%),大型数据库关联规则挖掘 (1),基本概念 k项集：包含k个项的集合 牛奶，面包，黄油是个3项集 项集的频率是指包含项集的事务数 如果项集的频率大于（最小支持度D中的事务总数），则称该项集为频繁项集,大型数据库关联规则挖掘 (2),大型数据库中的关联规则挖掘包含两个过程： 找出所有频繁项集 大部分的计算都集中在这一步 由频繁项集产生强关联规
4、则 即满足最小支持度和最小置信度的规则,关联规则挖掘分类 (1),关联规则有多种分类： 根据规则中所处理的值类型 布尔关联规则 量化关联规则（规则描述的是量化的项或属性间的关联性） 根据规则中涉及的数据维 单维关联规则 （仅涉及buys这个维） 多维关联规则,关联规则挖掘分类 (2),根据规则集所涉及的抽象层 单层关联规则 多层关联规则 （在不同的抽象层发现关联规则） 根据关联挖掘的各种扩充 挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的） 挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c，使得每个包含c的事务也包含c） （最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频
5、繁项集）,由事务数据库挖掘单维布尔关联规则,最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。,最小支持度 50% 最小置信度 50%,对规则A C，其支持度 =50% 置信度,Apriori算法 (1),Apriori算法是挖掘布尔关联规则频繁项集的算法 Apriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。 模式不可能比A更频繁的出现 Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。 Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率,Apriori算法 (2),Apriori算法利用频繁项
6、集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。 先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。,Apriori算法步骤,Apriori算法由连接和剪枝两个步骤组成。 连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。 Lk-1中的两个元素L1和L2可以执行连接操作 的条件是 Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通
7、过扫描数据库，通过计算每个k-项集的支持度来得到Lk 。 为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。,Apriori算法示例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,最小支持计数：2,使用Apiori性质由L2产生C3,1 连接： C3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,E 2使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选
8、项C3，我们可以删除其子集为非频繁的选项： A,B,C的2项子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以删除这个选项； A,C,E的2项子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以删除这个选项； B,C,E的2项子集是B,C,B,E,C,E，它的所有2项子集都是L2的元素，因此保留这个选项。 3这样，剪枝后得到C3=B,C,E,由频繁项集产生关联规则,同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算： 每个关联规则可由如下过程产生： 对于每个频繁项集l，产生l的所有非空子集； 对于每个非空子集s
9、，如果 则输出规则“ ”,多层关联规则 (1),数据项中经常会形成概念分层 底层的数据项，其支持度往往也较低 这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度,All,Computer accessory,software,laptop,financial,mouse,color,printer,computer,desktop,IBM,edu.,Microsoft,b/w,HP,Sony,wrist pad,Logitech,TID,Items,T1,IBM D/C, Sony b/w,T2,Ms. edu. Sw., Ms. fin. Sw.,T3,Logi. mouse, Erg
10、oway wrist pad,T4,IBM D/C, Ms. Fin. Sw.,T5,IBM D/C,Ergoway,多层关联规则 (2),在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的 通常，事务数据库中的数据也是根据维和概念分层来进行储存的 这为从事务数据库中挖掘不同层次的关联规则提供了可能。 在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力,挖掘多层关联规则的方法,通常，多层关联规则的挖掘还是使用置信度支持度框架，可以采用自顶向下策略 请注意：概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度 由概念层1开始向下，到较低的更特定的概
11、念层，对每个概念层的频繁项计算累加计数 每一层的关联规则挖掘可以使用Apriori等多种方法 例如： 先找高层的关联规则：computer - printer 20%, 60% 再找较低层的关联规则：laptop - color printer 10%, 50%,多层关联一致支持度,一致支持度：对所有层都使用一致的最小支持度 优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索 缺点：最小支持度值设置困难 太高：将丢掉出现在较低抽象层中有意义的关联规则 太低：会在较高层产生太多的无兴趣的规则,多层关联递减支持度,使用递减支持度，可以解决使用一致支持度时在最小支
12、持度值上设定的困难 递减支持度：在较低层使用递减的最小支持度 每一层都有自己的一个独立的最小支持度 抽象层越低，对应的最小支持度越小,min_sup = 5%,min_sup = 5%,min_sup = 3%,多层关联搜索策略 (1),具有递减支持度的多层关联规则的搜索策略 逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝 层交叉单项过滤：一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的（P165, 图6-14） (computer)( laptop computer, desktop computer) 层交叉k项集过滤：一个第i层的k项集被考察，当且仅当它在第(i
13、-1)层的对应父节点k-项集是频繁的（P165, 图6-15） (computer, printer)( laptop computer, color printer), (desktop computer, b/w printer) ),多层关联搜索策略 (2),搜索策略比较 逐层独立策略条件松，可能导致底层考察大量非频繁项 层交叉k项集过滤策略限制太强，仅允许考察频繁k-项集的子女 层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层频繁项（图6-14),受控的层交叉单项过滤策略,层交叉单项过滤策略的改进版本 设置一个层传递临界值，用于向较低层传递相对频繁的项。 即如果满足层传递临界值，则
14、允许考察不满足最小支持度临界值的项的子女 用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生,min_sup = 12% level_passage_support = 8%,min_sup = 3%,检查冗余的多层关联规则,挖掘多层关联规则时，由于项间的“祖先”关系，有些发现的规则将是冗余的 例如： desktop computer = b/w printer sup=8%, con=70% (1) IBM desktop computer = b/w printer sup=2%, con=72% (2) 上例中，我们说第一个规则是第二个规则的“祖先” 如
15、果规则(2)中的项用它在概念分层中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，则(1)是冗余的。,多维关联规则概念,单维关联规则： buys(X, “milk”) buys(X, “bread”) 多维关联规则：涉及两个或多个维或谓词的关联规则 维间关联规则：不包含重复的谓词 age(X,”19-25”) occupation(X,“student”) = buys(X,“coke”) 混合维关联规则：包含某些谓词的多次出现 age(X,”19-25”) buys(X, “popcorn”) = buys(X, “coke”) 在多维关联规则挖掘中，我们搜索的不是
16、频繁项集，而是频繁谓词集。k-谓词集是包含k个合取谓词的集合。 例如：age, occupation, buys是一个3-谓词集,挖掘多维关联规则的技术,数据属性可以分为分类属性和量化属性 分类属性 具有有限个不同值，值之间无序 量化属性 数值类型的值，并且值之间有一个隐含的序 挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法： 1. 量化属性的静态离散化 使用预定义的概念分层对量化属性进行静态地离散化 2. 量化关联规则 根据数据的分布，将量化属性离散化到“箱” 3. 基于距离的关联规则 考虑数据点之间的距离，动态地离散化量化属性,多维关联规则挖掘使用量化属性的静态离散化,量化属性使用预定义的概念分层，在挖掘前进行离散化 数值属性的值用区间代替 如果任务相关数据存在关系数
