数据挖掘与数据仓库（共享）

 

Aprior算法

 

[P1] 上一节我们给大家讲了基本的关联规则挖掘算法，最后我们也看到了，传统的算法会面临 项目集空间 数据量爆炸 的情况，以至于无法实际执行，在这里，我们就给大家介绍一种优化的 Aprior算法。

 

[P2] 这一章节中，我们分两步介绍 Apriori算法。第一部分介绍 Apriori 算法的性质，第二部分介绍具体的算法实现。

 

[P3]  Apriori 算法是由 Agrawal 等人于 1993 年提出的，它采用逐层搜索策略产生所有的频繁项集。我们之前说过，一个集合 I 里面有 m 个选项，那么就可以产生 2 的 m 次方个集合，这么庞大的集合数量，如果每一个都需要去搜索是否为频繁项集，那搜索的代价就太大了，Apriori 算法的目标就是减少需要搜索的项集。

 

[P4]  Apriori 的第一个规律，如果A是一个频繁项集，那么A的每一个子集都是一个频繁项集。这里我们可以证明一下这个规律。我们用 sup_count() 来表明项集在数据库中事务出现的次数。简单的说，sup_count(面包、牛奶) 代表的意思就是数据库中同时购买了 面包、牛奶 的订单数量。根据前提，A是一个频繁项集，所以A的支持度就是大于等于支持度最小阈值，也就是大于等于 min_sup。对于A的任意非空子集B，一定有 sup_count(B) 大于等于 sup_count(A)，这个好理解，如果同时购买 面包、牛奶 这个组合的订单有10个，那买过面包的订单数量既包括买了 面包、牛奶 组合的订单，也包括只买面包不买牛奶的订单，所以 面包 这个子集的订单数量肯定是大于等于 面包、牛奶 这个组合的订单的。既然子集B 的 sup_count(B) 的数量是大于等于 A的，那根据支持度计算公式，sup_count(B)除以数据库事务总数n，那么B的支持度肯定要大于等于A的支持度。所以，结论，A如果是频繁项集，那么它所有的非空子集一定也都是频繁项集。那这个结论有什么用呢？ 大家记得前面说过，我们挖掘强关联规则，需要对所有的项集去遍历数据库，判断它是不是频繁项集，如果项集特别多，那对数据库的遍历次数就非常多。根据现在这个规律，如果我们发现一个项集，它不是频繁集，那所有由它衍生的项集也就肯定不是频繁项集，也就没必要搜索了。比如，我们发现同时购买 面包 和 衬衫 这个组合的人太少，这个组合不是频繁项集，那我们也就没必要去计算同时购买 面包 和 衬衫 和牛奶这个组合了，因为子集不是频繁项集，由这个子集衍生出来的项集也不可能是频繁项集。这样在实际的挖掘计算中，我们就可以跳过很多无用的项集而不用去扫描数据库计算，大大节省了数据库的访问量。

 

[P5]  第二个定义是超集，一个项集，我们给它添加1个新的元素，就形成了一个更大的项集，我们称作超集，这个被称作直接超集。如果我们添加多个元素，就形成更多的超集。这是一个简单的定义，用于在关联挖掘中从一个项集生成更多的项集。

 

[P6] Apriori 性质具有反单调性。我们前面说过，一个项集如果是频繁的，那么它所有的子集也都是频繁的。反单调性就是规律反过来，如果一个项集不是频繁的，那么它所有的超级也一定是不频繁的。这个证明和前面的证明类似，超级 C 的 sup_count() 必定小于等于 A 的 sup_count()，这个也好理解，买了面包的人有 10个，那同时买了面包又买了牛奶的人必定小于等于 10，因而计算支持度的时候肯定也会小于等于A的支持度。A本身都不频繁，那更小支持度的C肯定也不频繁。下面的例子，若 {ac} 不是频繁的，则 {abc}、{acd} 也一定不是频繁的。通过这个规律，我们可以排除掉很多项集，不用对这些项集去计算支持度了，可以节省很多的计算消耗。

 

[P7] 基本的 Apriori 算法。我们先从最简单的 单个元素的项集开始，从中找出频繁的项集 L1。注意，由于一开始只有 1个元素，所以只需要单独计算每个元素的支持度就可以找出谁是频繁项集。第二步，我们由 L1 频繁项集，去生成 2个元素的超集，就是把 L1 中的项集，两两组合，得到一系列的超集 C2。第三步，我们验证 C2 中的所有项集，看看哪些是频繁项集，把这些频繁项集筛选出来作为 L2。这样我们就实现了 L1 到 L2 的挖掘。重复这个过程，直到我们再也找不出新的频繁项集为止。在这个过程中，从 Ck 到 Lk ，我们都需要对数据库做一次扫描。

 

[P8] 具体的算法如下：首先扫描数据库 D，得到 只有1个元素的频繁项集 L1。然后 k 循环，k从2开始，先从 Lk-1 得到超集 Ck，方法是把  Lk-1中的元素相互合并组合得到下一层的超集 Ck。接着扫描一遍数据库，计算 Ck 中每一个项集的支持度，如果支持度大于最低阈值，这就是一个频繁集，我们加入到结果 Lk 中。循环完成，我们就得到了新的频繁集 Lk。最终的频繁集是把 L1 到 Lk 全部合并得到。

 

[P9] 这是一个具体例子，我们假设支持度的阈值为 2 条记录。左边是数据库的事务表，右边是我们详细的计算过程。最上方那个图表是第一步，我们计算 C1，扫描数据库事务得到项集｛i1｝到｛i5｝分别的计数，用计数和支持度阈值 2 对比，得到 L1，可以看到 L1 中的项集都是频繁项集。接下来图表是第二步，我们用 L1 生成 C2，也就是用 L1 中的项集进行两两组合，得到2个元素的超集 C2。有了 C2 之后，我们扫描数据库D，对每个项集计数得到中间的计数表。我们用计数表和支持度阈值 2 对比，去除掉低于阈值的项集，得到 L2 表。L2 里都是频繁项集。然后是第三步，我们用 L2 生成 C3，也是把里面的项集进行两两组合，得到有 3个元素的项集 C3。再次扫描数据库 D，得到每个项集的计数，然后比对阈值，筛选出支持度高于阈值的频繁项集得到 L3。可以看到，随着层级的增加，频繁项集明显减少，毕竟，同时购买多件商品的人肯定比购买单件的要少。接下来第四步，我们用 L3 依然是两两合并 生成 C4，注意这里 C4 就只剩下 1个项集了。我们扫描数据库 D 对 C4 中的项集计数，最后发现唯一的 项集的支持度已经低于阈值，所以 C4 不存在任何频繁项集了，结果是 L4 为空，算法结束。最后，我们合并 L1 , L2, L3 得到最终的频繁项集，返回结果。 这个例子完整的演示了 Apriori 算法的计算过程。

 

[P10] 上面算法描述了我们整体的逻辑运算过程，但是，还有两个具体的细节没有给出。在算法里面，我们还有两个实际的问题，就是我们有了一个频繁项集 Lk-1，怎么用这个来构建下一级的 Ck 超集呢？也就是说，我们现在分别有 面包、牛奶、啤酒，这三个频繁项集，那怎么构造  面包 加 牛奶，面包 加 啤酒，以及  牛奶 加 啤酒 这样的两两组合？你数据量很小的时候当然好办，一眼就看出来了，但是在实际问题中，数据量往往很大，这种情况下应该怎么有效的生成下一级的组合呢？这是第一个问题。那第二个问题，我们有了 Ck 项集，算法中说，扫描数据库然后计算支持度得到 Lk，那具体怎么一个扫描方法呢？ 接下来，我们就来解决这两个实际的问题。

 

[P11] 第一个问题，我们怎么从频繁项集 Lk-1 生成下一层的超集 Ck。在这里，我们用表的连接来操作，这个表的连接和我们数据库中的 inner join 是一样的原理。看下面的例子，表 R 和 S，我们做表的连接，连接条件是 R 的第三列 和  S 的第二列 值必须相同，然后两条记录才可以合并。比如，R的第一条记录 1,2,3 和 S的第一条记录 2,3,2 ，它们的 C 列都是 3，于是可以合并为 1,2,3,2,3,2。一样的道理，R 的第二条记录 4,5,6 和 S 的第二条记录 5,6,3 ，正好C列都是6，于是可以合并为 4,5,6,5,6,3。R 的第三条记录 7,8,9，在 S 中找不到 C列为 9的数据，所以没有数据可以合并，最终我们得到的结果就是右边图片显示的数据。

 

[P12] 我们从 Lk-1 生成 Ck 的时候，用的是一样的表连接方法。在这里，我们用 Lk-1 和 它自己做连接来生成 Ck。在做 Lk-1 和 Lk-1 自身做表连接的时候，我们规定前面 k-2 个值得都是一样的，第 k-1 个值从小到大排序，然后我们把 k-1 中比当前记录更大的值，拎上来作为第 k 个值，这样就实现了  Lk-1 到 Ck 的转变。这样说可能有点抽象，我们来看一个具体例子。

 

[P13] 如果所示，我们是用 L3 来生成 C4。这里，L3 和 L3 自身连接，前面算法描述，要求 k-2 个值都相同，然后只针对 k-1 这列做数据的合并，所以 k 是4，我们就要求 前面 2列 的数据都是相同的记录才能做合并。注意看图，例子中前面两列正好都是 1,2 ，数据正好都一致，这样就省事了。然后，针对第 k-1 列，也就是 第三列，数据排序，从小到大，把大的数据拎上来作为第 K 个值，也就是作为第 4 列。所以，第一行，1,2,1 然后把下面比第三列 1 大的值挨个拎上来作为第 4 列，我们得到 1,2,1,2 和 1,2,1,3。也就是 第一行生成了 2行C4中的数据。然后，我们接着看第二行，一样的做法，把比它的第三列更大的数字拎上来作为 第4列，所以我们得到  1,2,2,3 这一行数据。再往后，已经没有更大的数据了，所以我们最终一共得到 三条记录，前两条记录是由第一行生成的，第三条记录是由第二行生成的。至此，我们通过这样的算法就可以快速由 Lk-1 生成 Ck。

 

[P14] 我们解决了从 Lk-1 生成 Ck 的操作。接下来，我们需要从 Ck 生成 Lk。也就是从一堆项集中，找出里面的频繁项集，去除不频繁的。最简单的方法，当然是对里面所有的项集挨个去查一次数据库，计算他们的支持度，然后判断是不是频繁项集。这种最简单方法代价也很大，就是对数据的访问比较大，算法性能也就差。实际上，根据 Apriori 的性质，一些项集根本就不可能是频繁项集，也没必要去查询数据库。从 Ck 中直接找出这些 不可能是频繁项集的项，然后把它们去除掉，这个过程称为剪枝操作。Apriori 性质，如果一个项集是 非频繁的，那么它所有的超集也一定是 非频繁的。利用这个规律，我们对 Ck 中所有的项集，去判断它的子集是否都在 Lk-1，如果有子集不在，就说明这个项集必定是非频繁的，可以直接删除它，不需要去数据库查询。

 

[P15] 我们来看一个具体的例子。我们已经有 L3 了，里面都是频繁项集。我们通过表连接的方式得到 C4。C4 里面有 2个项集，第一个项集是 i1, i2, i3, i4 ，我们检查它所有的 3层子集，可以看到，它所有的 3层子集，都属于 L3，都是频繁项集，那这个项集我们保留，留待后面去查询数据库再确认它是否真的是频繁项集。第二个项集是 i1, i3, i4, i5 。我们检查它所有的 3层子集，可以发现 子集 i3, i4, i5 不在 L3 中，既然有一个子集不是频繁项集，那所有的超集都肯定不是频繁项集，这个项集可以 剪枝 剪掉了，不用再去查询数据库了。从这个例子我们可以看出，通过剪枝操作，我们可以大大降低数据库的查询量，从而提升算法的整体执行效率。

 

[P16] 这里我们用树形结构图来展示剪枝的效果。数据库 D 中包含 a,b,c,d 四项，其中通过扫描数据库计算支持度，我们知道  b, c , d 是频繁项集，我们用灰色标明频繁项集。接下来，我们用这些项集，去扩展 二层的项集。由于 a 之前计算不属于频繁项集，所以用 a 做的所有组合都肯定不会是频繁项集，我们可以直接跳过这些项集的检测，如图 左边所示，等同于是从 a 这里把下面的树枝都剪掉了，这就是剪枝的操作。

 

[P17] 在右边，我们对二层的项集计算支持度，得到 cd 不属于频繁项集，所以把 cd 往下都剪掉了，不用再去计算它下面的项集。所以，最终我们得到所有的频繁项集是 一层的 b,c,d 和 二层的 bc, bd ，也就是所有标为灰色的项集。从这个图可以看到，剪枝可以有效的减少我们需要计算的数据量，从而大大提高算法执行的效率。

 

[P18]  通过剪枝，我们可以减少需要计算支持度的项集的数量。但是，对于没有被剪枝的项集，我们依然是需要挨个计算他们的支持度，从而决定它们是不是频繁项集。按照传统的方法，我们会对每一个项集，去扫描一次数据库中的记录，看看是否有事务包含这个项集，如果包含就计数加1，最后得到这个项集的支持度，从而判断它的支持度是否超过最低阈值，最终确定它是否属于频繁项集。这个过程逻辑比较直接，但是，如果我们有 1000个这样的项集，就需要扫描1000次数据库，代价实在太大了。这里，我们有更高效的计算方法，假设我们现在计算的项集是第 k 层，现在的项集是 Ck，比如 k 是 3，那我们扫描数据库，把所有订单记录里面购买 低于3个商品的全都忽略，而对大于等于3个商品的订单，我们分解出它每3个项组成的所有子集，然后判断子集是否在 Ck 中，如果在，就把 Ck 中对应的项集计数加1，扫描完一次数据库之后，Ck 中的所有的项集都有了计数，我们根据这个计数就可以判断它是否为频繁项集。这样，整个算法只需要读取一次数据库，就可以完成支持度的计算，效率大大提升。

 

[P19]  接下来，我们用一个实际的例子来计算支持度。这是一个数据库中的事务记录，或者叫订单记录，我们完整的扫描一次这些记录，然后来实现支持度计算。

 

[P20] 这里是详细的计算过程。第一步，计算图片最上方的 C1，扫描左边数据库记录，事务挨个读取出来，比如第一条记录读取出来 i1, i2, i5，拆分成 3 个子集，分别是 i1，I2，i5 三个子集。对应 C1 里面，这三个子集计数都加 1。重复这个过程，挨个事务读取出来，拆分子集，然后对应计数加 1 。整个数据库事务都读取一遍之后，我们就得到了图片 C1 的结果。把计数与最小支持度阈值对比，筛选出大于最小支持度的项集，就得到了 频繁项集 L1。接下来，从 L1 通过表的自连接 和 剪枝的方法，我们得到第二层的项集 C2。然后扫描数据库所有事务，对 C2中所有项集计算支持度，最后得到  C3。重复这个过程，最后我们就能得到所有的频繁项集。

 

[P21] 接下来是对算法的代码描述。我们输入是事务数据库 D，和最小支持度阈值 min_sup，输出是所有的频繁项集。

 

[P22] 在这个代码演示的算法中，我们用了一个函数 apriori_gen() ，这个方法实现了 Lk-1 通过表的自连接生成 Ck ，并且完成剪枝操作。对于生成的 Ck，前面说的扫描数据库的方式，我们挨个计算里面项集的支持度，从而确定项集是否为频繁项集。最后把所有的频繁项集合并返回结果。

 

[P23] 这页代码演示了 apriori_gen() 的实现，上半部分是实现了表的自连接，下半部分实现了剪枝操作。通过自连接和剪枝操作，我们可以从 Lk-1 得到 Ck。 

 

[P24] 总结一下，这章我们一共讲了两部分内容，Apriori性质  和  Apriori算法。Apriori性质主要就是证明了两个定理，如果一个项集是频繁项集，那么它所有的非空子集也一定都是频繁项集。相反，如果一个项集不是频繁项集，那么由它参与组合的任何超集也一定不会是频繁项集。这两个定理是我们后续算法的基本原理。Apriori算法是基于以上两个定理的具体实现，我们首先扫描数据库得到L1频繁集，然后由L1根据表的连接操作得到C2，再次扫描数据库事务得到C2的频繁项集L2，重复这个过程，直到找出所有的频繁项集。