规则 S(L-S) 规则产生
• 本例中，我们有两个频繁3-项集 • {I1, I2, I3} • {I1, I2, I5}
• 以{I1, I2, I5}为例， 该项集的非空子集为： {I1, I2}, {I1, I5}, {I2, I5}, {I1}, {I2}, {I5} 根据：s-->L-s 得：{I1, I2}-->{I1, I2, I5}-{I1, I2}={I5}
X y 的置信度=Y中的项在包含X的事务中出现 的频繁性。(“包含前件与后件中所有项的事 务”与“包含前件中所有项的事务”的比。)
{牛奶，啤酒} {面包} (s=? c=?)
{牛奶，啤酒} {面包} (s=1/5=20% c=1/2=50%)
练习
• {牛奶， 尿布} {啤酒} （s=? C=?） • {牛奶，啤酒} {尿布} (s=? C=?) • {啤酒} {牛奶，尿布} (s=? C=？)
规则 {I1，I2}-->{I5} 的置信度 • =支持度(L)/支持度(s)=2/4=50%
练习
• 根据下表提供的数据，找出频繁3-项பைடு நூலகம்，并 且计算强关联规则。 （最小支持度=30%，最小置信度=80%）
• • • •
{牛奶，鸡蛋，面包} {牛奶，鸡蛋，薯片} {牛奶，面包，薯片} {鸡蛋，面包，薯片}
• 关联规则形式：
• {尿布}{啤酒}
• 这类信息形如 if-then的语句形式 • 与逻辑if-then规则不同，关联规则本质上是 概率规则。
• 对于商业企业而言，这条信息便是一条非常有价值 的信息。
• 零售商可以通过类似的，有价值的信息，来了解顾 客的购买行为，用来支持各种商务应用。比如捆绑 销售，市场促销等。
关联规则
• 数据： 大规模数据集快速增长 • e.g., • 广泛用于商业的自动数据收集设备每小时产生 几TB（terabytes）规模的数据。
• 核物理和天体物理领域的科学实验数量的增加 导致每月可能产生几PB（petabytes）规模数据。 • 已有的推理方法过时。 （数据量太大，内存问题）
数据挖掘技术的产生
产生关联规则的算法 Apriori
• Apriori 算法 （先验算法）， 1993，Agrawal & Srikant • 算法的思想： 从只包含一个项的频繁项集 (1-项集)开始， 递归产生具有两个项的频繁项集，然后产 生具有3个项的频繁项集，如此下去，直到 产生所有的频繁项集。
• Apriori 算法是用来挖掘布尔关联规则频繁 项集的算法。 • 该算法，利用的是Apriori性质： • 频繁项集的所有非空子集也必须是频繁的。
• 对于一个给定的项集，它所产生的所有规 则都具有相同的支持度。 • 但是置信度一般不同。
• 这里有9个事务，每个事务记录了一起购买的 商品代码，e.g., • 事务1是同时购买商品1、2和5。 • 事务2是同时购买商品2和4。
• 假设我们想得到该数据库中支持度计数至 少为2 （等价于百分比支持度2/9=22%）的 关联规则。 • 通过枚举，我们可以看出只有下面一些项 集的支持度计数，至少为2。
规则 S(L-S) 规则产生
例题
• 这里有9个事务，每个事务记录了一起购买 的商品代码，e.g., • 事务1是同时购买商品1、2和5。 • 事务2是同时购买商品2和4。
• 接下来，根据已经找到的频繁项集，计算 关联规则。
从频繁项集中产生强关联规则的法：
• 对于每一个频繁项集L， 计算所有的非空子 集 L=S+(L-S) • 对于每个非空子集 如果 支持度(L)/支持度(s)>=最小置信度
产生关联规则的原理
• 一旦我们得到具有所要求的支持度的所有 项集的列表， • 我们就可以通过考察列表中每个项集的所 有子集，
• 归纳出满足期望置信度的规则。
计算过程
• 由于集合的任何子集出现频率至少与该集 合一样，因此每个子集也在该列表中 • 可以直接根据项集的支持度（计数）和该 项集的每个子集的支持度（计数）之比计 算规则的置信度。
• 这则案例来自美国某地区的沃尔玛超市。他们利用 数据挖掘技术而得到这样一条信息。利用该信息， 这家超市便将尿布和啤酒这种在我们看来毫无联系 的商品摆放在一起销售，从而增加了销售量。
支持度与置信度
• 支持度 support (s)
X y 的支持度=包含x和y的事务所占的比例 • 置信度 confidence (c)
经过连接生成的 K项集：
•
{L1 [1], L1 [2], L1[3], … L1 [k-1], L2 [k-1]}
• 为了寻找 Lk ,通过Lk-1 与自己连接产生候选K项集的集合。该候选K项集记为Ck
• 并非所有的候选K项集都是频繁的K项集
• 从候选K项集中寻找频繁K项集 （剪枝的作用：通过扫描数据集，从候选集中 查找符合条件的频繁项集，为了节省计算空间， 可以利用Apriori算法的性质来进行求解： 如果k-1项集不是频繁项集，则通过连接组成的K 项集也不是频繁的。 ）
• 关联规则挖掘是研究 ‘什么与什么相伴’
• 购物篮分析(market basket analysis)
• 该问题，源于研究顾客事务数据库，以确 定购买商品之间的相关性。
• 购物篮数据：零售商收集和存储的大量销 售数据
• 数据：
• 超市中使用条码扫描器收集的数据 • 由大量事务记录组成 • 每个记录列出了顾客一次购物交易所购买 的所有商品
• 源自进行数据处理业务的企业和进行数据 处理研究的科学家需要找到有效的模式 （pattern）来自动处理海量数据。
• 模式可以是简单的数据汇总，数据划分， 数据内部的依赖模型。
数据挖掘，源于数据库学科，最初，被称为数据 库中知识发现 （KDD） knowledge discovery from data (KDD)
问题： 是否某些商品总是一起销售？
• • • • 改善商店布局 优化商品陈列 交叉销售、促销、分类设计 基于购买模式识别顾客组群。
• 示例：超市的收银台每天都会收集大量的 顾客购物数据。
• 关联规则的形式： 形如 x → y 的蕴涵表达式 • 其中 x, y 都是项集
• 在关联分析中，前件和后件都是不相交的（不 含公共项）项的集合（称作项集） • E.g., {牛奶，面包} → {啤酒} • 除前件 (if部分) 和后件(then部分)外，每个关联 规则还有两个数，用来表达规则的不确定程度。
• L1 和 L2 可以执行连接操作 L1 ∪ L2 的条件是：
• (L1 [1]= L2 [1]) ∧(L1[2]= L2[2]) ∧…(L1 [k-2]= L2 [k2]) ∧ (L1 [k-1]<> L2 [k-1])
• (L1 [k-1]<> L2 [k-1]) 的目的在于防止重复项目的 产生
• Apriori算法，利用频繁项集性质的先验知识 （priori Knowledge）通过逐层搜索的迭代方 法，也就是将K项集用于探索k+1项集来穷 尽数据集中的所有频繁项集。 • （所谓K项集，就是指含有K个项目的一个 集合。）
• 先找到频繁1-项集合， L1
• 然后利用 L1找出频繁2-项集合 L2 • 找出频繁3-项集合 L3 直到找不出频繁K项集 为止。 • 寻找每一个频繁项集 Lk 都需要一次数据集 的扫描。
• 做为知识发现过程，数据挖掘旨在从原始数据 中得到‘被证实的知识’。 • 数据挖掘的方法和算法 • 发现工具 vs 查询工具
• “进行数据挖掘的人会将90%的时间用于数据预 处理，只将约10%的时间用于数据挖掘方案和输 出评估” 《数据挖掘基础教程》
关联规则挖掘
• 关联规则，是由Agrawal等人，于1993年提出的。用于 数据库中某些项目集合中所蕴含的，潜在的，关联关系。 R. Agrawal, T.Imielinski, and A.Swami, Mining association rules between sets of items in large databases, in Proceedings of ACM-SIGMOD Conference, Washington, DC, 1993 • 是市场营销研究领域广泛引用的工具。(零售业，文本 挖掘) • 算法：Apriori
强关联规则
• 强关联规则：同时满足最小支持度和最小 置信度的才是强关联规则。
• 从频繁项集中产生的规则都满足支持度要 求。 • 规则AB 置信度的计算方法 =支持度(A∪B)/支持度(A)
从频繁项集中产生强关联规则的法：
• 对于每一个频繁项集L， 计算所有的非空子 集 L=S+(L-S) • 对于每个非空子集 如果 支持度(L)/支持度(s)>=最小置信度
• Apriori算法，由两个步骤组成：连接+剪枝 • 连接：为了寻找 Lk ,通过Lk-1 与自己连接产生候选K-项集 的集合。 • 该候选K项集记为Ck • 连接条件：2个K-1项集连成一个K项集的条件是：在这 两个k-1项集中，除了一个元素不同之外，其它的K-2个 元素都要相同。 • 最后得到的就是K-2个元素加上这2个不同的元素=k项集：
• 产生满足预定支持度和置信度的所有关联 规则问题可以分为两步： • 1：找出满足支持度要求的所有项集 （这些 项集称作频繁项集）
• 2：根据每个选出的项集产生满足置信度要 求的关联规则
• 大型数据库中的关联规则挖掘包含2个过程：
（1）找出所有频繁项集，大部分计算都集中 于此。 （2）由频繁项集产生强关联规则（即满足最 小支持度和最小置信度的规则）
• 换句话说，如果一个项集不是频繁的，则 它的所有超集都不可能是频繁的。
• A∪B的模式不可能比A更频繁的出现。 • Apriori算法是反单调的：即，一个集合如果 不能通过测试，则该集合的所有超集也不 能通过相同的测试。 • 该性质通过减少搜索空间，来提高频繁项 集逐层产生的效率。