6.3提高Apriori算法的有效性
提高Apriori算法的有效性
[P1] 上一章节，我们介绍了 Apriori 算法的逻辑，通过剪枝我们可以大大减少需要计算支持度的项集数量。通过扫描一次数据库就完成计算支持度，我们可以大大减少对数据库的读取操作。在这一章节里，我们会介绍实际操作中如何进一步提高算法的效率，让 Apriori 算法更加高效。
[P2] 在之前的算法里，我们需要多次扫描数据库来完成支持度的计算。数据库的扫描是代价很大的操作，我们应该尽量减少数据库的扫描，这样才能让算法运行更有效。在这章，我们会介绍 基于Hash的优化技术。
[P3] 基于 Hash 的技术，主要目标是提升计算过程的效率。我们之前说过算法，从 Ck-1 通过扫描 数据库 得到 Lk-1频繁项集，然后对 Lk-1 自身做表连接额外加剪枝，得到 Ck 项集。这在之前的算法里面是两个独立的步骤。在这里，我们可以利用 Hash 表来操作，把两个过程合并到一起完成，提高效率。
[P4] 这里我们来看一个具体的例子。对于第一个项集 C1 里面包含了 i1 到 i5 一共5个子集。现在我们需要从 C1 生成第二层的 C2，并且还要同时完成剪枝操作。在这里，我们定义一个 Hash 函数，H(ia，ib)=(a×10+b) mod 7
，在这里 你先不用管这个 模 7 是怎么来的，我们先看计算步骤。
[P5] 这里左边的数据库的事务，我们扫描一遍所有事务，根据前面的 Hash 函数挨个计算两两组合的 hash 值。比如第一行事务，包含 i1, i2, i5 ，我们计算两两组合的 hash 值。因为我们 hash 函数定义的是 模 7，所以我们有一个 hash 存储空间，一共是 7 个位置，下一页 PPT 会看到，这一页PPT放不下这个图。那么 i1, i2 计算 hash值，就是 (1 x 10 + 2) mod 7 = 5 ，所以 i1, i2 这个组合就应该放到 hash 空间的 5号 位置。继续这个过程，i1, i5 这个组合的 hash 值就是 (1 x 10 + 5) mod 7 = 1，所以这个组合就应该放到 hash 空间的 1 号 位置。我们一直重复这个过程，可以完成所有的 2项 组合都存放到 hash 空间中。接下来，我们看计算的结果。
[P6] 在这页PPT里，我们可以看到上面是 hash 空间保存的前面计算的 2层 组合项集。我们给定支持度阈值为 2，接下来，我们扫描这个 hash 空间来生成 C2。对 hash 空间中每个不同的项集分别计数，大于支持度阈值 2 的保留，小于这个值的就抛弃。最终我们得到 C2 的值为， i1,i5 2次，i2,i3 4次， i2,i4 2次，i2,i5 2次， i1,i2 4次，i1,i3 4次。在这里，我们实际上一次性完成了 C1 到 L1 再到 C2 的过程，并且同时还完成了剪枝的过程。整个过程利用了 hash 函数和 hash 空间来一次性完成计算，让计算效率大幅提升。这里的方法可以看到，关键点是 hash 函数 怎么定，以及那个 模 7 是怎么确定的？实际上这些都是靠经验自己定，如果选项规模非常大，那 hash 函数非常难定，模几更难估计。
[P7] 第二种方法，可以利用 hash 树来对 Ck 的项集做计数，从而判断 Ck 中哪些项集是频繁项集。在这里，我们先解决第一个问题，给你一个事务订单，比如订单同时购买了 i1,i2,i3,i4,i5,i6 这6种商品，让你找出它所有的三项子集，比如 i1,i2,i3 或者 i2,i3,i4 或者 i3,i4,i5 等等。如果项特别多，生成这样的子集就会有比较大的麻烦，我们这里先介绍一种算法，可以有效的枚举所有这种子集。
[P8] 我们看这个例子，一个订单事务，包含6个商品，1 到 6。我们需要生成包含 3个商品的所有子集。首先，对这个事务排序，确保1 到 6 是从小到大排好序的，接下来进入枚举过程。我们取数据，都是只是取比当前更大的数，不取比当前小的数，这样可以防止生成重复的项。第一步，取第一个数，分别可以取 1,2,3， 但是不能取5,6，因为5,6 后面没有数字了，没法凑成 3个数的子集。取了第一个数之后，形成第一层级。第二步，我们再取第二个数，注意，第二个数只能取比当前数字更大的数字，所以 1 之后第二个数字只能取 2,3,5， 2之后只能取 3,5。继续这个过程，第三步取第三个数字，依然是只能取比当前更大的数字，最后我们得到所有 3项的 子集。这个算法采用树形结构来生成子集，效率比较高，算法稳定也不会出现重复子集的情况。
[P9] 有了方法从事务 t 中快速生成所有子集，接下来就是用这些子集去和 Ck 中的候选集进行比较，如果匹配就把对应的候选集计算加 1 ，这样扫描一遍之后，就可以得到 Ck 中所有候选集的计数，也就可以得到它们的支持度。但是，在这里会有一个实际的问题，就是对 Ck 中的候选集去比对的时候，如果候选集数量特别大，比如有 10万个候选集，那么每次比对的代价会比较大。于是，我们可以考虑把 Ck 构建一个 hash 树来做这个比对。例子是 3层 的子集，所以我们定义一个 hash 函数，对子集中的 每一位数字，做 模 3 的操作，用这个结果来决定子集应该放在 hash 树的哪一个树枝上。
[P10] 这个图展示了 hash 树的构造过程。首先扫描 C3 中的各项集，对每一个子集的，第一个数字，做 hash 运算，也就是 模 3 得到余数的运算，根据这个结果，决定把子集分配到哪个树枝上。如图所示，第一位数字模3余数为1的，都在 1 这条分支上， 后面是 2 的分支，0的分支。
[P11] 接下来，用同样的方法计算每个子集 第二个 数字模3的余数，然后形成树形结构的第二层。当叶子节点包含的子集数量足够少的时候我们就不再细分了，比如我们这里是节点包含3个子集或者以下，就不再细分。如果节点包含的子集多于3个，我们就继续细分，对每个子集中第三项数字模3取余数，然后细分，最终得到我们课件上的这个 hash 树形图。
[P12] 当 Ck 的 hash 树构造好之后，我们扫描数据库，对数据库中每一笔事务 t 都枚举子集，然后用枚举的子集去 hash 树中查找，如果匹配，就把 hash 树中对应的子集计数加 1 。例如，对于事务子集 3,5,6 ，我们在 hash 树中查找。同样的方法，先把第一个数字 3 模3 得到余数0，于是在 0 这条树枝上往下找。接下来，对第二个数字 5 模 3 得到余数 2，然后继续往下一层的 2 这条树枝上找。到了叶子节点我们只需要挨个比对叶子节点包含的子集，找到匹配的 3,5,6 这个子集，然后对它的计数加 1。重复上面的过程，我们对所有的数据库事务，挨个去查找 hash 树，然后匹配计数，就可以得到 Ck 所有项集的计数，从而得到它们的支持度，最终确定哪些项集是频繁的，哪些是不频繁的。
[P13] 上述方法中，我们是先把事务的子集枚举出来，然后构建 Ck 的 hash 树，最后把事务的子集挨个到 hash 树上去匹配。实际上这两个过程是可以合并的。我们首先构建 Ck 的 hash 树，然后对每一个事务，我们都做枚举，一边枚举，一边进行 hash 计算去和 hash 树上的子集匹配，这样可以更加节省操作步骤。
[P14] 如图所示，这个图就是一边枚举一边在 hash 树匹配的结果，完成了枚举，我们也同时完成了在 hash 树上的匹配和计数，直接就得到了 Ck 中所有项集的 计数结果，从而得到了 支持度。
[P15] 所以，采用 hash 树组织 Ck 之后，我们扫描数据库然后匹配 Ck 中的项集，完成支持度计数的效率大幅提高。
[P16] 总结一下，这一章我们给大家演示了 Hash 技术在算法中的应用。算法在实际编码的时候，我们考虑到实际情况，采用hash技术来减少计算空间和计算步骤，可以大大提升算法的效率。