问题与数据介绍

问题

• 计算数据集的频繁项集并找出关联规则.

• 比较计算频繁项集的不同算法之间的时空复杂度.

• 发现关联规则之间的某些规律并讨论.

数据集

共有两组数据集

• Groceries: 购买物品
• Unix: 用户在 terminal 中使用的指令

算法介绍

Apriori

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

算法改进

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

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