频繁项集的产生(2)

约 1855 字大约 6 分钟

2024-05-15

在上一节中我们简单介绍了先验原理以及该算法中的两个关键步骤: 候选集的产生和剪枝.

本节将继续介绍支持度的计数以及计算复杂度, 这样关于频繁项集的产生的内容就全部介绍完毕.

支持度计数

支持度计数的作用: 确定在候选剪枝步骤中保留下来的每个候选项集出现的频繁程度. 支持度计数出现在伪代码的第 6~11 步实现.

暴力方法

将每个事务与所有的候选项集进行比较, 并更新包含在事务中的候选项集的支持度.

这种方法的计算开销十分高, 尤其是事务和候选项集的数目都很大时.

枚举方法

枚举每个事务所包含的项集, 并利用其更新对应的候选项集的支持度.

例如, 考虑事务 $t$ , 它包含 5 个项 {1,2,3,5,6}. 对于想要考察的候选 3-项集来说, 事务 $t$ 中共有 $C_5^3=10$ 个 3-项集, 其中一定有部分项集是与候选 3-项集重合的, 此时增加其支持度, 而不对应的子集则可以忽略.

下图给出了一个系统地枚举事务 $t$ 中所有 3-项集的方法.

将所有项按照字典顺序排列.
针对于需要生成的 k-项集, 选出 k 个最小项, 其他较大项跟随在后面.
例如, 给定 $t=\{1,2,3,5,6\}$ 的 3-项集一定以项 1、2、3生成的. 1 $\fbox{2 3 5 6}$ 表示的3-项集是: 从 1 开始, 后随两个取自集合 $\{2,3,5,6\}$ 的项.
下一层的生成重复 2 的动作, 但是前缀的数量加一.

Hash树方法

刚刚提到的枚举方法中我们知道了如何系统地枚举事务所包含的项集. 但是如果要进行支持度计数, 则还需要将候选项集与生成的 k-项集进行匹配, 如果候选项集与枚举出来的项集匹配则支持度加一. 那么下面我们将解释如何使用 Hash 树来进行匹配这个动作, 这种存储候选集的结构可以大大减少比较的次数. 因为不在需要每个事务和每个候选集进行比较, 而是每个事务和 Hash 树中特定的候选集进行比较.

我们仍然以书中的例子来看. 假设我们已经有了候选 3-项集, 一共 15 个. 候选集如下: $\{1,4,5\},\{1,2,4\},\{4,5,7\},\{1,2,5\},\{4,5,8\},\{1,5,9\},\{1,3,6\},\{2,3,4\},$ $\{5,6,7\},\{3,4,5\},\{3,5,6\},\{3,5,7\},\{6,8,9\},\{3,6,7\},\{3,6,8\}$

1. 建立 Hash 树

前置准备

确定 Hash 函数.
例如书中选用的函数: $h(p)=(p-1)\ mod\ 3$ , 这会把与 3 取余之后结果相同的数值分到一个 Hash 分支中.

最大叶子节点数.
如果一个叶子节点中所包含的数据个数超过最大叶子节点数, 则说明该叶子节点需要进一步的分裂. 此处将该数值设定为 3.

接下来我们需要开始建立这棵树.

详情

对于项集 $\{1,4,5\}$ 来说, 第一项为 1, 根据 Hash 函数, 我们应该将其放在左子树上.
同理, $\{1,2,4\}$ 也放在左子树.
我们继续看下一个候选项 $\{4,5,7\}$ . 根据第一项 4 可以判断其也应该放在左子树, 但是此时左子树的数据数量以及达到最大叶子节点数, 所以需要进行分裂. 我们根据这三个候选集的第二项进行 Hash 处理, 可得到分裂的结果为:
再下一个候选项 $\{1,2,5\}$ 的第一项是 1 应该在第一层的左子树, 第二项 2 应该在第二层的中间子树. 此时第二层的中间子树数据个数又一次超过最大叶子节点数, 所以该节点再一次分裂成:
根据以上的规律, 不断将候选项加入到树中, 我们最终可以得到一棵完整的 Hash 树: