Inhzus

Tech blog of inhzus.

频繁项集算法 Apriori & FP-Growth

2019-04-22


问题与数据介绍

问题

数据集

共有两组数据集

算法介绍

Apriori

Apriori 算法基于先验规则: k 长度的频繁项集的所有 k-1 长度的子集也都是频繁项集. 从长度为 1 的频繁项集一直向上寻找.

算法改进

在第一次扫描数据的时候, 就将那些项包含哪些元素全部记录在 bitarray 中, 当进行筛选是否满足最小置信度的时候直接统计项中每个元素的 bitarray 进行与操作, 再统计其中 1 的个数即可知道是否符合最小支持度.

通过这一操作, 即可将原来时间复杂度为 m * k * n * p , 占用了算法大部分时间的过滤过程(k 为当前正在过滤的项集的长度, m 为长度为 k 的候选频繁项数量, n 为所有的项集数量, p 为项集的平均长度), 降为 m * k * n, 且其中遍历 n 的时间复杂度降低了非常多(原先需要读取项集的元素, 而优化后只需统计 01 即可)

代码实现基于 Efficient Apriori 并进行了以上的算法修改, 优化了过滤支持度的效率.

FP-Growth

代码实现基于 pyFP-growth 实现并进行了修改.

方法

比较

通过 CProfile 工具能够比较方便地对算法的时空复杂度进行分析.

记录数据

通过重载输出的记录值的 __repr__ 函数, 方便地打印并输出结果.

结果与分析

以下首先展示频繁项集的实验结果.

Groceries

在最小支持度为 0.05, 最小置信度为 0.2 情况下

Unix storage

在最小支持度 0.15, 最小置信度 0.8 情况下

分析

首先一定有: 不同的算法虽然实现不同, 但其结果一定是相同的.

同样对 Unix storage 数据使用两种算法进行分析.

使用 Apriori, 时间开销 271 ms:

使用 FP-Growth, 时间开销 409 ms:

使用 dummy 方法, 时间开销令人震惊的只有 286 ms. 我的 dummy 算法改自 Apriori 算法, 即将其中剪枝的过程去除. 由于这一算法继承了 Apriori 中 bitarray 的优秀设计, 所以时间复杂度也很好.

这一表现其实与预期的 apriori 算法的时间复杂度比 fp-growth 要高不符

但需要指出, Apriori 算法中我进行了优化: 即将查找当前项是否满足最低支持度转化为了使用 bitarray 进行计算(因为最初的版本效率过低), 才能够将时间复杂度提高到与 FP-Growth 算法时间开销基本相同, 因此依然可以得出结论, 即 FP-Growth 的时间复杂度在理论层面一定是比 Apriori 高的

总结

(如果没有本次实验中的对应优化) 传统 Apriori 算法的时间复杂度确实非常之低, 而 FP-Growth 算法通过空间换时间, 通过建树与一些先验知识对频繁项集的提取进行了简化, 提高了算法的效率.

不过通过一些优化(见上文的算法介绍部分), 能够从另一个角度将原有的 Apriori 算法优化到我们可以接受的程度.

代码

Apriori

FP-Growth