《大型数据库中的关联规则挖掘》由会员分享，可在线阅读，更多相关《大型数据库中的关联规则挖掘（33页珍藏版）》请在金锄头文库上搜索。
1、第四章 关联规则挖掘 关联规则挖掘： 从事务数据库，关系数据库和其他信息存储中 的大量数据的项集之间发现有趣的、频繁出现 的模式、关联和相关性。 应用： 购物篮分析、分类设计、捆绑销售等“尿布与啤酒”典型关联分析案例 采用关联模型比较典型的案例是“尿布与啤 酒”的故事。在美国，一些年轻的父亲下班 后经常要到超市去买婴儿尿布，超市也因 此发现了一个规律，在购买婴儿尿布的年 轻父亲们中，有30%40%的人同时要买 一些啤酒。超市随后调整了货架的摆放， 把尿布和啤酒放在一起，明显增加了销售 额。同样的，我们还可以根据关联规则在 商品销售方面做各种促销活动。一、基本概念 给定： 项的集合：I=i1,i
2、2,.,in T=t1,t2tn是数据库中事务的集合，每个事务ti 则是项的集合，使得 则 为T中的关联规则。 其中 并且规则度量：支持度和置信度Customer buys diaperCustomer buys bothCustomer buys beer 对所有满足最小支持度 和置信度的关联规则 支持度s是指事务集T中 包含 的百分比 置信度c是指T中包含A 同时也包含B的事务占包 含A的事务的百分比 最小支持度 min_sup 最小置信度 min_conf 强关联规则：如果事务集合T中的关联规则 A B同时满足support(AB)min_sup, confidence(AB)min_c
3、onf, 则AB称为T中的强关联规则。 关联规则挖掘就是在事务集合中挖掘强关 联规则。 k项集：包含k个项的集合 牛奶，面包，黄油是个3项集 如果K项集的频率(即支持计数)大于最小支持 计数（最小支持度T中的事务总数n），则称 该项集为频繁K项集二、关联规则挖掘步骤 大型数据库中的关联规则挖掘包含两个过 程： 找出所有频繁项集 大部分的计算都集中在这一步 由频繁项集产生强关联规则 即满足最小支持度和最小置信度的规则 Apriori算法 定理一 如果某k-项集不是频繁k-项集，则 包含IK的(k+1)-项集也不是频繁(k+1)-项集 。该性质称为Apriori性质。由事务数据库挖掘单维布尔关联规
4、 则 最简单的关联规则挖掘，即单维、单层、布尔关 联规则的挖掘。最小支持度 50% 最小置信度 50% 对规则A C，其支持度 置信度Apriori算法思想 一.扫描一次事务集合，找出频繁1项集集合L1； 二.基于L1，产生候选2项集集合C2，再扫描一次事务 集合，比较候选支持计数与最小支持计数，找出频繁 2项集L2； 三.基于L2，找出C3，作剪枝运算，得到剪枝后的C3 ，再扫描一次事务集合，确定L3； 四.以此类推，直至找出频繁项集为止。最后在所有频 繁项集中产生强关联规则。Apriori算法示例Database TDB1st scanC1L1L2C2C2 2nd scanC3L33rd
5、scanTidItems 10A, C, D 20B, C, E 30A, B, C, E 40B, EItemsetsup A2 B3 C3 D1 E3Itemsetsup A2 B3 C3 E3Itemset A, B A, C A, E B, C B, E C, EItemsetsup A, B1 A, C2 A, E1 B, C2 B, E3 C, E2Itemsetsup A, C2 B, C2 B, E3 C, E2Itemset B, C, EItemsetsup B, C, E2最小支持计数：2使用Apiori性质由L2产生C3 1 连接： C3=L2 L2= A,C,B,C,
6、B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,E 2使用Apriori性质剪枝：频繁项集的所有子集必须是频 繁的，对候选项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多层关联规则 (1) 在适当的等级挖掘出来的数据项间的关联规 则可能是非常有
7、用的 通常，事务数据库中的数据也是根据维和概 念分层来进行储存的 这为从事务数据库中挖掘不同层次的关联规则提 供了可能。 在多个抽象层挖掘关联规则，并在不同的抽 象层进行转化，是数据挖掘系统应该提供的 能力挖掘多层关联规则的方法 通常，多层关联规则的挖掘还是使用置信度支 持度框架，可以采用自顶向下策略 请注意：概念分层中，一个节点的支持度肯定不小于 该节点的任何子节点的支持度 由概念层1开始向下，到较低的更特定的概念层，对每 个概念层的频繁项计算累加计数 每一层的关联规则挖掘可以使用Apriori等多种方法 例如： 先找高层的关联规则：computer - printer 20%, 60% 再
8、找较低层的关联规则：laptop - color printer 10%, 50%多层关联一致支持度 一致支持度：对所有层都使用一致的最小支持 度 优点：搜索时容易采用优化策略，即一个项如果不 满足最小支持度，它的所有子项都可以不用搜索 缺点：最小支持度值设置困难 太高：将丢掉出现在较低抽象层中有意义的关联规则 太低：会在较高层产生太多的无兴趣的规则多层关联递减支持度 使用递减支持度，可 以解决使用一致支持 度时在最小支持度值 上设定的困难 递减支持度：在较低 层使用递减的最小支 持度 每一层都有自己的一 个独立的最小支持度 抽象层越低，对应的 最小支持度越小Computer support=
9、10%Laptop support=6%Desktop support=4%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-1)层的对应父节点k-项集是频繁的（P165, 图6-1
10、5） (computer, printer)( laptop computer, color printer), (desktop computer, b/w printer) )多层关联搜索策略 (2) 搜索策略比较 逐层独立策略条件松，可能导致底层考察大量 非频繁项 层交叉k项集过滤策略限制太强，仅允许考察频 繁k-项集的子女 层交叉单项过滤策略是上述两者的折中，但仍 可能丢失低层频繁项（图6-14)受控的层交叉单项过滤策略 层交叉单项过滤策略的改进版本 设置一个层传递临界值，用于向较低层传递相对频繁的 项。 即如果满足层传递临界值，则允许考察不满足最小支持度 临界值的项的子女 用户对进一
11、步控制多概念层上的挖掘过程有了更多的灵活 性，同时减少无意义关联的考察和产生Computer support=10%Laptop support=6%Desktop support=4%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
12、) 上例中，我们说第一个规则是第二个规则的“祖先 ” 如果规则(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
13、(X, “coke”) 在多维关联规则挖掘中，我们搜索的不是频繁项 集，而是频繁谓词集。k-谓词集是包含k个合取谓 词的集合。 例如：age, occupation, buys是一个3-谓词集挖掘多维关联规则的技术 数据属性可以分为分类属性和量化属性 分类属性 具有有限个不同值，值之间无序 量化属性 数值类型的值，并且值之间有一个隐含的序 挖掘多维关联规则的技术可以根据量化属性的处 理分为三种基本方法： 1. 量化属性的静态离散化 使用预定义的概念分层对量化属性进行静态地离散化 2. 量化关联规则 根据数据的分布，将量化属性离散化到“箱” 3. 基于距离的关联规则 考虑数据点之间的距离，动态地
14、离散化量化属性多维关联规则挖掘使用量化属 性的静态离散化 量化属性使用预定义的概念分层，在 挖掘前进行离散化 数值属性的值用区间代替 如果任务相关数据存在关系数据库中 ，则找出所有频繁的k-谓词集将需要k 或k+1次表扫描 数据立方体技术非常适合挖掘多维关 联规则 n-维方体的单元用于存放对应n-谓词集 的计数或支持度，0-D方体用于存放任 务相关数据的事务总数 如果包含感兴趣的维的数据立方体已 经存在并物化，挖掘将会很快，同时 可以利用Apriori性质：频繁谓词集的 每个子集也必须是频繁的(income)(age)()(buys)(age, income)(age,buys) (income,buys)(age,income,buys)挖掘量化关联规则 (1) 量化关联规则中，数值属性将根据某种挖掘标准 ，进行动态的离散化 例如：最大化挖掘规则的置信度和紧凑性 为了简化量化关联规则挖掘的讨论，我们将聚焦 于类似以下形式的2-维量化关联规则：Aquan1 Aquan2 Acat （两个量化属性和一个分类属性间的关联） 例如： age(X,”30-39”) income(X,”42K - 48K”) buys(X,”high resolution TV”)挖掘量化关联规则 (2) 找出这类2-维量化关联规则
