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

什么是关联规则挖掘？ 关联规则挖掘： 应用： 从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。 应用： 购物篮分析、分类设计、捆绑销售等

“尿布与啤酒”——典型关联分析案例 采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。

购物篮分析 如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（0001001100，这种方法丢失了什么信息？） 关联规则的两个兴趣度度量 支持度 置信度 支持度和置信度分别是衡量实用性和确定性的指标 ％2的支持度指的是所有的事务（购买记录）中的2％同时购买了计算机和软件 置信度60％意味着购买了计算机的人中，60％也购买了软件

关联规则：基本概念 给定： 则关联规则是如下蕴涵式： 项的集合：I={i1,i2,...,in} 任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得 每个事务由事务标识符TID标识； A,B为两个项集，事务T包含A当且仅当 则关联规则是如下蕴涵式： 其中 并且 ，规则 在事务集D中成立，并且具有支持度s和置信度c

基本概念——示例 D 项的集合 I={A,B,C,D,E,F} 每个事务T由事务标识符TID标识，它是项的集合 比如：TID(2000)={A,B,C} 任务相关数据D是数据库事务的集合 D

规则度量：支持度和置信度 对所有满足最小支持度和置信度的关联规则 假设最小支持度为50%，最小置信度为50%，则有如下关联规则 Customer buys both Customer buys diaper 对所有满足最小支持度和置信度的关联规则 支持度s是指事务集D中包含 的百分比 置信度c是指D中包含A的事务同时也包含B的百分比 假设最小支持度为50%，最小置信度为50%，则有如下关联规则 A  C (50%, 66.6%) C  A (50%, 100%) Customer buys beer

大型数据库关联规则挖掘 (1) 基本概念 k－项集：包含k个项的集合 项集的频率是指包含项集的事务数 {牛奶，面包，黄油}是个3－项集 项集的频率是指包含项集的事务数 如果项集的频率大于（最小支持度×D中的事务总数），则称该项集为频繁项集

大型数据库关联规则挖掘 (2) 大型数据库中的关联规则挖掘包含两个过程： 找出所有频繁项集 由频繁项集产生强关联规则 大部分的计算都集中在这一步 由频繁项集产生强关联规则 即满足最小支持度和最小置信度的规则

关联规则挖掘分类 (1) 关联规则有多种分类： 根据规则中所处理的值类型 根据规则中涉及的数据维 布尔关联规则 量化关联规则（规则描述的是量化的项或属性间的关联性） 根据规则中涉及的数据维 单维关联规则 （仅涉及buys这个维） 多维关联规则

关联规则挖掘分类 (2) 根据规则集所涉及的抽象层 根据关联挖掘的各种扩充 单层关联规则 多层关联规则 （在不同的抽象层发现关联规则） 挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的） 挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c’，使得每个包含c的事务也包含c’） （最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项集）

由事务数据库挖掘单维布尔关联规则 最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。 对规则A  C，其支持度 =50% 置信度 最小支持度 50% 最小置信度 50% 对规则A  C，其支持度 =50% 置信度

Apriori算法 (1) Apriori算法是挖掘布尔关联规则频繁项集的算法

Apriori算法 (2) Apriori算法利用频繁项集性质的先验知识（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中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk 。 为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。

Apriori算法——示例 Database TDB L1 C1 1st scan C2 C2 L2 2nd scan C3 L3 最小支持计数：2 Itemset sup {A} 2 {B} 3 {C} {D} 1 {E} Database TDB Itemset sup {A} 2 {B} 3 {C} {E} L1 C1 Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E 1st scan C2 Itemset sup {A, B} 1 {A, C} 2 {A, E} {B, C} {B, E} 3 {C, E} C2 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} L2 2nd scan Itemset sup {A, C} 2 {B, C} {B, E} 3 {C, E} C3 L3 Itemset {B, C, E} 3rd scan Itemset sup {B, C, E} 2

使用Apiori性质由L2产生C3 1 ．连接： C3=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}} 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}}

由频繁项集产生关联规则 同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算： 每个关联规则可由如下过程产生： 对于每个频繁项集l，产生l的所有非空子集； 对于每个非空子集s，如果 则输出规则“ ”

{Logi. mouse, Ergoway wrist pad} 多层关联规则 (1) All Computer accessory computer software printer 数据项中经常会形成概念分层 底层的数据项，其支持度往往也较低 这意味着挖掘底层数据项之间的关联规则必须定义不同的支持度 desktop laptop financial edu. color mouse wrist pad b/w IBM Microsoft HP Sony Logitech Ergoway TID 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}

多层关联规则 (2) 在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的 通常，事务数据库中的数据也是根据维和概念分层来进行储存的 这为从事务数据库中挖掘不同层次的关联规则提供了可能。 在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力

挖掘多层关联规则的方法 通常，多层关联规则的挖掘还是使用置信度－支持度框架，可以采用自顶向下策略 请注意：概念分层中，一个节点的支持度肯定不小于该节点的任何子节点的支持度 由概念层1开始向下，到较低的更特定的概念层，对每个概念层的频繁项计算累加计数 每一层的关联规则挖掘可以使用Apriori等多种方法 例如： 先找高层的关联规则：computer -> printer [20%, 60%] 再找较低层的关联规则：laptop -> color printer [10%, 50%]

多层关联——一致支持度 一致支持度：对所有层都使用一致的最小支持度 优点：搜索时容易采用优化策略，即一个项如果不满足最小支持度，它的所有子项都可以不用搜索 缺点：最小支持度值设置困难 太高：将丢掉出现在较低抽象层中有意义的关联规则 太低：会在较高层产生太多的无兴趣的规则

多层关联——递减支持度 使用递减支持度，可以解决使用一致支持度时在最小支持度值上设定的困难 递减支持度：在较低层使用递减的最小支持度 每一层都有自己的一个独立的最小支持度 抽象层越低，对应的最小支持度越小 Computer [support=10%] Laptop [support=6%] Desktop [support=4%] min_sup = 5% min_sup = 3% min_sup = 5%

多层关联——搜索策略 (1) 具有递减支持度的多层关联规则的搜索策略 逐层独立：完全的宽度搜索，没有频繁项集的背景知识用于剪枝 层交叉单项过滤：一个第i层的项被考察，当且仅当它在第（i-1）层的父节点是频繁的（P165, 图6-14） (computer)( laptop computer, desktop computer) 层交叉k项集过滤：一个第i层的k项集被考察，当且仅当它在第(i-1)层的对应父节点k-项集是频繁的（P165, 图6-15） (computer, printer)(( laptop computer, color printer), (desktop computer, b/w printer) …)

多层关联——搜索策略 (2) 搜索策略比较 逐层独立策略条件松，可能导致底层考察大量非频繁项 层交叉k项集过滤策略限制太强，仅允许考察频繁k-项集的子女 层交叉单项过滤策略是上述两者的折中，但仍可能丢失低层频繁项（图6-14)

level_passage_support = 8% 受控的层交叉单项过滤策略 层交叉单项过滤策略的改进版本 设置一个层传递临界值，用于向较低层传递相对频繁的项。 即如果满足层传递临界值，则允许考察不满足最小支持度临界值的项的子女 用户对进一步控制多概念层上的挖掘过程有了更多的灵活性，同时减少无意义关联的考察和产生 min_sup = 12% level_passage_support = 8% Computer [support=10%] Laptop [support=6%] Desktop [support=4%] min_sup = 3%

检查冗余的多层关联规则 挖掘多层关联规则时，由于项间的“祖先”关系，有些发现的规则将是冗余的 上例中，我们说第一个规则是第二个规则的“祖先” 例如： desktop computer => b/w printer [sup=8%, con=70%] (1) IBM desktop computer => b/w printer [sup=2%, con=72%] (2) 上例中，我们说第一个规则是第二个规则的“祖先” 如果规则(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”) 在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。k-谓词集是包含k个合取谓词的集合。 例如：{age, occupation, buys}是一个3-谓词集

挖掘多维关联规则的技术 数据属性可以分为分类属性和量化属性 挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法： 分类属性 具有有限个不同值，值之间无序 量化属性 数值类型的值，并且值之间有一个隐含的序 挖掘多维关联规则的技术可以根据量化属性的处理分为三种基本方法： 1. 量化属性的静态离散化 使用预定义的概念分层对量化属性进行静态地离散化 2. 量化关联规则 根据数据的分布，将量化属性离散化到“箱” 3. 基于距离的关联规则 考虑数据点之间的距离，动态地离散化量化属性

多维关联规则挖掘——使用量化属性的静态离散化 量化属性使用预定义的概念分层，在挖掘前进行离散化 数值属性的值用区间代替 如果任务相关数据存在关系数据库中，则找出所有频繁的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-维量化关联规则的方法：关联规则聚类系统(ARCS) 一种源于图像处理的技术，该技术将量化属性对映射到满足给定分类属性条件的2-D栅格上，然后通过搜索栅格点的聚类而产生关联规则

关联规则聚类系统(ARCS) (1) ARCS过程中的步骤包括 1. 分箱（根据不同分箱方法创建一个2-D数组），本步骤的目的在于减少量化属性相对应的巨大的值个数，使得2-D栅格的大小可控 等宽分箱 等深分箱 基于同质的分箱（每个箱中元组一致分布） 2. 找出频繁谓词集 扫描分箱后形成的2-D数组，找出满足最小支持度和置信度的频繁谓词集

关联规则聚类系统(ARCS) (2) 3. 关联规则聚类 将上一步得到的强关联规则映射到2-D栅格上，使用聚类算法，扫描栅格，搜索规则的矩形聚类

ARCS的局限性 所挖掘的关联规则左手边只能是量化属性 规则的左手边只能有两个量化属性（2-D栅格的限制） 一种不基于栅格的，可以发现更一般关联规则的技术，其中任意个数的量化属性和分类属性可以出现在规则的两端 等深分箱动态划分 根据部分完全性的度量进行聚类

挖掘基于距离的关联规则 因为未考虑数据点之间或区间的相对距离，分箱方法不是总能紧扣区间数据的语义 等宽划分将很近的值分开，并创建没有数据的区间 等深划分将很远的值放在一组 基于距离的关联规则挖掘考虑属性值的接近性，紧扣区间数据的语义，并允许值的类似 基于距离的关联规则挖掘的两遍算法： 1. 使用聚类找出区间或簇 2. 搜索频繁的一起出现的簇组，得到基于距离的关联规则

关联规则的兴趣度度量 客观度量 主观度量 挖掘了关联规则后，哪些规则是用户感兴趣的？强关联规则是否就是有趣的？ 两个流行的度量指标 支持度 置信度 主观度量 最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果： 它是出人意料的 可行动的（用户可以使用该规则做某些事情） 挖掘了关联规则后，哪些规则是用户感兴趣的？强关联规则是否就是有趣的？

对强关联规则的批评（1） 例1：(Aggarwal & Yu, PODS98) 在5000个学生中 3000个打篮球 3750个喝麦片粥 2000个学生既打篮球又喝麦片粥 然而，打篮球 => 喝麦片粥 [40%, 66.7%]是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高 打篮球 => 不喝麦片粥 [20%, 33.3%]这个规则远比上面那个要精确，尽管支持度和置信度都要低的多

对强关联规则的批评（2） 例1：(书P172，表6-4) 上述数据可以得出 buys(X, “computer games”) => buys(X, “videos”) [40%, 60%] 但其实全部人中购买录像带的人数是75%，比60%多；事实上录像带和游戏是负相关的。 由此可见A => B的置信度有欺骗性，它只是给出A,B条件概率的估计，而不度量A,B间蕴涵的实际强度。

由关联分析到相关分析 我们需要一种度量事件间的相关性或者是依赖性的指标 当项集A的出现独立于项集B的出现时，P(A∪B)=P(A)P(B)，即corrA,B＝1，表明A与B无关， corrA,B >1表明A与B正相关， corrA,B <1表明A与B负相关 将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性为： P({game, video})/(P({game})×P({video}))=0.4/(0.75×0.6)=0.89 结论：录像带和游戏之间存在负相关