关联分析-频繁项集的产生(2)

1849字约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树:

2. 计算出一个事务可能的候选项集

很显然我们在上一节候选项集的产生中已经详细介绍过方法.

3. 使用Hash树进行计数

我们仍然以事务 $\{1,2,3,5,6\}$ 为例.

所有3-项集中候选项的首项为1的对左子树进行比较, 而首项为2的则选择中间子树.首项为3的则选择右子树.接下来继续分析项集的第二项, 然后根据其数值选择下一层的子树分支.

最后每个候选项必然走到一个叶子节点, 其仅仅需要与该节点上的数据进行比较从而计算支持度即可.

关联分析-频繁项集的产生(2)

支持度计数

暴力方法

枚举方法

Hash树方法

1. 建立Hash树

2. 计算出一个事务可能的候选项集

3. 使用Hash树进行计数

计算复杂度

支持度阈值

项数(维度)

事务数

事务的平均宽度