6.1关联分析的概念
关联分析的概念
[P1] 大家好，今天我们给大家介绍数据挖掘中 关联分析 的一些基本概念
[P2] 这一章节我们分为4部分，前三部分主要是定义一些基本概念，包括 关联、关联的规则及其度量、频繁项集，最后一节是介绍挖掘关联规则的基本操作以及对应的算法。我们先从概念说起
[P3] 关联分析是指关联规则挖掘，它是数据挖掘中一个重要的、 高度活跃的分支，它的目标是发现数据库中不同项之间的联系，这些联系 构成的规则 可以帮助用户 找出 某些行为特征，以便进行企业决策。比如，一个商店可以通过购物订单分析得知“大部分顾客会在一次购物中同时购买面包和牛奶”，那么这个商店就可以通过 降价促销面包 的同时 提高面包和牛奶 的销量。关联规则挖掘近些年来在实际应用中取得了很好的效果，它是数据挖掘其他研究分支的基础。关联规则挖掘最早是由 Agrawal 等人在1993年提出的。最初提出的动机是针对购物分析问题，其目的是为了研究和发现顾客的购买行为，即 数据库中 顾客购买的不同商品之间的联系规则。
[P4] 关联规则挖掘的对象是事务数据库，也就是我们平时用的关系型数据库，比如 Oracle、SQL-Server 以及开源的 MySql，在我们做关联分析之前，需要做一些基础性的定义。首先是一个全局项的集合 I，里面每一项就是一个商品，这个集合里面包含了商店里所有的商品。其中任意几个商品可以组成一个组合，我们称为项集 itemset 。我们这里约定所有项集中的项都是默认排好序的。
[P5] 接下来有一个事务型数据库，我们定义 D 为事务的集合，也就是所有订单的集合。每一个事务都对应上一页的项集。也就是一个订单中，包含哪些商品。
[P6] I 是全部商品集合，D 是所有顾客的购物清单，每个元组 即事务 是一次购买商品的集合。那么表中就列出了每一笔订单 对应购买的商品集合。比如第一笔订单 t1 购买了 3个不同商品，分别是 i1, i2, i5
[P7] 接下来我们用这些集合来表示一个购物篮，每个商品一个布尔变量，如果一笔交易中购买了这个商品，变量值就是 true，否则 就是 false，那么我们就可以分析这些布尔变量来得到它们之间的 关联关系。比如 课件图片中显示的，不同顾客购买了不同商品，有牛奶、面包、鸡蛋、黄油 等，我们通过对这些订单的分析，得出不同商品购买之间的 关联关系。
[P8] 对于两个商品之间的关联，我们应该怎么样 来衡量呢？在这里，我们需要定义 关联的规则。我们用 X 推导 Y 这样的表达式来代表 关联关系，其中 X 和 Y 交集为空，X称为规则的前件，Y称为规则的后件。例如，谷物和牛奶这个集合推导出对水果的关联购买，这里谷物和牛奶的集合就是前件，而水果就是后件
[P9] 两个集合有关联，接下来就需要确定这个关联到底强弱如何。表示关联强弱，我们需要两个指标，一个支持度，一个置信度。我们首先看一下支持度的定义，给定一个数据库 D，一个全局项集 I， 那么支持度就是 包含 I1 的事务在 D 中所占的百分比。这个怎么理解呢？简单的说，就是100个订单，其中有20个订单买了面包，所以面包 订单占比就是 20%，所以支持度就是 0.2 。如果采用概率的方式来等价表达，那 X推导出Y 的支持度，就是 Y在X 的前提下出现的概率。
[P10] 从支持度的定义来看，它其实就是所占百分比。这样来看，我们就能很自然的得出 X推导出Y 的支持度，和 Y推导出X 的支持度 应该是相等的。我们看这个数据库的事务表，一共9条记录，这里面同时包含 i1 和 i2 的记录为 4 条，所以 i1 推导出 i2 的支持度，等于 i2 推导出 i1 的支持度，都是 4 除以 9 等于 0.44
[P11] 支持度是一种 重要性度量，表明 X推导出Y的关联有多强。如果支持度这个数值太小，那可能只是纯粹偶然事件，并不代表什么规律。比如，100个订单买了牛奶，其中一个订单额外买了一双鞋子，购买牛奶到购买鞋子的支持度是 0.01，这只是一个偶然事件，不代表二者之间有什么关联，我们可以忽略它。在这种低支持度的情况下，你指望通过降低牛奶的价格促销，从而带动鞋子的销售是不可能的。
[P12] 支持度是一种情况发生的百分比的占比。我们还需要另外一个指标 置信度 ，给定一个全局项集 I 和事务数据库 D，假设我们已经存在一个关联 X推导出Y，那置信度的定义就是，同时包含 X和Y 的事务数 与 包含X的事务数之比。用概率的条件来表示，其实就是 在 X已经发生的前提下，Y随后发生的概率是多少，也就是 Y在给定 X下的条件概率。下面我们来看一个具体例子。
[P13] 看这个表，里面包含了 i1 的订单数一下，一共有 6条记录，然后，我们再数一下 同时包含了 i1 和 i2 订单，一共有 4条记录，所以 i1推导出i2 的 置信度就是，在 i1 已经发生的前提下，i2发生的概率，也就是 4 除以 6，为 0.47。这就是 i1 推导出 i2 的置信度。从这个计算过程，我们可以看出，i1 推导出 i2 的置信度，和 i2 推导出 i1 的置信度是不一样的。这里再计算一下 i2 推导出 i1 的置信度，我们数一下表格，包含 i2 记录一共有 7条，同时包含 i2 和 i1 的记录有 4条，所以 i2推导出 i1 的置信度为 4除以7，也就是 0.57 。这里我们明确的看出，置信度是不对等的，需要分别单独计算。置信度表明了，在一个情况已经发生了，另外一个情况发生的概率，也就是一个条件概率。
[P14] 对于 支持度 和 置信度，我们有一个简单的规则，就是 支持度 总是 小于等于 置信度的。这个也好理解，100个订单中，同时买了牛奶和面包的有30个，支持度就是0.3。那买了牛奶的人，再同时购买了牛奶和面包的置信度，就是 30除以买了牛奶的订单，很明显，这个分母肯定小于等于总订单100，所以置信度一定大于等于对应的支持度。
[P15] 有了支持度和置信度这两个指标，接下来我们就可以用这两个指标把一些关联性强的特征给筛选出来。我们制定两个标准，最低支持度 和 最低置信度，只有同时满足这两个最低值的关联我们才考虑，我们称他们为 强关联规则。注意，满足这两个指标的关联，只表明他们同时出现的概率，不代表他们一定有必然的因果关系。比如，彩票投注站大部分人都会同时购买体彩和福彩，在投注站，这二者的支持度和置信度指标就非常高，但是，体彩和福彩并没有什么必然的因果联系。所以，数据指标只表明概率，具体背后的逻辑原因还需要具体分析，不能简单的依靠数字就下结论。
[P16] 接下来，我们定义一个概念，频繁项集。如果一个项集，它的支持度大于最低支持度标准，我们就称这个项集为频繁项集。项集你可以简单的理解为商品集合，比如 面包、牛奶、啤酒，同时购买了这三个商品的订单比例超过20%，我们就称 面包、牛奶、啤酒 组成的这个集合为频繁项集。项集是可以衍生组合的，比如 面包、牛奶、啤酒，每个商品单独挑出来可以做一个项集，每两两组合也可以成为新的项集，比如 面包、牛奶 这两个商品就可以做一个项集，其它也一样。所以，如果一个项集 I 里面有 m 个元素，那它可以产生2的m次方个非空项集。之所以要定义这么多的项集，主要目的是我们需要挖掘各种组合，从中发现一些关联性特别强的组合，所以需要遍历所有组合。
[P17] 对于一个项集 I，从中任意挑出 k 个元素组成新的项集，这批所有的项集都称为 K项集。如果某个项集的支持度大于我们规定的最低标准，这个项集就被称为 频繁项集。
[P18] 数据挖掘中的挖掘关联规则，主要就是对数据库中所有记录计算，找出支持度和置信度都超过最小标准的强关联规则。这些强关联规则才是我们需要真正关注的。
[P19] 挖掘强关联规则一般分为两个步骤，第一步是找出频繁项集，也就是搜索所有的组合，把支持度大于最低标准的组合全部找出来，这个过程可能需要搜索的项集非常多，呈现指数爆炸的搜索数量。我们后面算法的重点也都在这一步，尽可能减少需要搜索的项集，从而提高算法效率。有了第一步搜索出来的结果，我们对这些频繁项集再做二次计算，在项集中计算关联规则的置信度，只保留高于最小置信度的关联规则。最终，这些同时满足最小支持度和最小置信度的关联规则，就是我们要找的强关联规则。
[P20] 这是算法的代码描述，输入是数据库 D，里面是所有的事务记录，还有一个最小置信度的阈值。输出是所有的频繁项集。算法的过程是这样的，首先我们得到整个数据库 D 的记录总数为 n，对于每一个 子集 遍历整个数据库，查找有多少事务包含这个子集，得到这个子集出现的次数 i，如果 i 除以 n 的数值大于最低支持度阈值，这个子集就是频繁项集，我们加入到结果集合中。循环这个过程，最终我们会得到一批这样的频繁项集。这个算法，我们用具体的例子来说，就是数据库一共有 1000个订单，现在我们有一个商品组合 面包、牛奶、啤酒，我们挨个查询订单，看看哪些订单同时购买了这三个商品。最后我们得到一共有200个订单同时购买了这三个商品，于是三个商品组成的项集的支持度就是 200 除以 1000 也就是 0.2，大于我们的最低支持度0.1，那 面包，牛奶、啤酒、这三个商品的组合就属于频繁项集。重复这个过程，面包 加 牛奶 两个商品的组合属于频繁项集吗？面包 加 啤酒 呢？ 牛奶 加 啤酒 呢？
[P21] 前面的算法可以看到，如果 项集 I 里面的元素特别多，比如有 m 个元素，那么它能组合出来的项集就有 2的m 次方这么多，对每一个项集，都要去扫描整个数据库的事务记录，这个算法的复杂度就是 O(2的m次方 乘以 n)，这是一个指数级增长的数字，如果项特别多，几乎就是有无穷个项集，基本上无法计算了。所以，接下来我们会给大家介绍，怎么优化这个算法。
[P22] 最后总结一下，这章节我们介绍了数据关联和关联规则的基本概念。数据关联指的是数据之间的某个概率上的联系，不代表必然的因果关系。表明关联强弱有两个指标，一个是支持度，一个是置信度。一个项集，如果它的支持度和置信度同时大于最低阈值，我们就说这个项集是一个频繁项集。数据挖掘关联规则的过程一般是分为两步，第一步是对所有项集计算他们的支持度，把支持度大于最低阈值的项集都找出来。第二步，对前面找出来的项集，扫描数据库计算他们的置信度，对于置信度也大于阈值的项集返回为最终结果。我们最终挖掘出来结果的就是所有的频繁项集。