Apriori算法C++实现

最近完成了一门叫做数据挖掘的课程。在这门课上,老师介绍了两种算法,即Apriori算法和FP-growth算法,随后布置了一个上机实践作业,要求我们从retail.dat文件中提取出强关联规则,这些规则必须同时满足最小支持度和最小置信度的要求。

Apriori算法

在项目中提供了一个用于发现所有频繁模式集的C++实现代码示例。该代码的主要数据存储结构采用二维数组进行组织，整体设计较为简单。作为初步版本供参考使用。另外该版本是在初步开发阶段完成的自连接操作后未进行剪枝处理直接对数据库进行扫描因此运行效率较低。

在测试过程中采用的最低支持度设定为2, 该参数值相对较高主要归因于其对生成内容质量的影响因素考量因此其生成的结果表现得相对高效然而若将最低支持度设定在1, 以内的值时相应的生成速度可能会显著降低

经过改进后提升了修剪步骤的算法运行速度；当最小支持度较小时显著提高但仍然存在一定的延迟问题

观察到当最小支持度设为500时，在改进后的算法中实现了大约一分钟的性能提升；由此可见，在Apriori算法中剪枝操作扮演着十分关键的角色。

12.02更新

这两天原本打算完成修剪工作,却转而研究起FP-Growth算法的相关知识。然而,经过实践发现我对树的知识还不够熟练,因此决定先完成数据结构中树相关知识的练习题,并计划之后再进行写作。在这段时间里,我不断尝试进一步优化Apriori算法,终于通过阅读韩家伟教授著作后深入理解了利用散列函数处理二元集的方法,使效率得到了显著提升。在此基础上,我按照书中介绍的方式进行了具体实现

由于哈希函数（散列函数），在实际应用中也存在一定的局限性。经过一段时间的研究和尝试，在这里举一个基于二项集的例子来进行详细说明。

在优化前的代码逻辑中，在每一轮数据库扫描时都需要遍历整个二项集合中的每一项进行比较操作。假设该集合中有n个元素，则每次扫描就需要执行n次比较操作；这种处理方式显然会导致极低的运行效率。”

而对于一项集合，则采用了计数排序法的思想：即在整个数据集中进行一次扫描时，在每个数据点被读取后就对其对应的键值位置（如H[temp]）进行计数统计。”

显然地发现：如果能够将二项集合同样采用类似策略，则能显著提升系统的运行效率。”因此我们引入了所谓的桶式哈希方法：通过使用一个键值对(key1, key2)来唯一标识一组特定的数据点。”

当所有数据都被处理完毕后，则会得到一个完整的全量数据散列表（虽然我的实现还很初级）。”

接下来我们从候选二项集中选出那些满足最小支持度阈值Min_sup的所有项目组合C2。”

最后我们通过遍历每一个C2中的项目对{i,j}来计算其对应的位置散列值H[i][j] = hash(i,j)，并判断该位置对应的哈希值是否超过了预设的支持度阈值Min_sup。”这个过程可以通过一次遍历候选二项集C2就能高效地得到频繁出现的候选二项集合L2.”

为了更直观地理解这一过程，请看下面的一个简单示例：

如图6.2所示，我们可以通过公式 hash(x, y) = (x_{10} + y) \mod 7 来构建哈希数组。具体来说，在第一行中我们可以得到三个二项集 \{I₁, I₂\}、\{I₁, I₅\} 和 \{I₂, I₅\} 等等，并将它们依次存入哈希数组中：计算得到 key = hash(1, 2) = (1_{10} + 2) \mod 7 = 5 因此 H[5]++；同样地 hash(1, 5) = 1 所以 H[1]++；以及 hash(2, 5) =4 因此 H[4]++ 。每一个二项集都会对应到哈希数组中的一个唯一 key 值。接下来每一行的数据都可以按照这种方法进行处理

优化版算法在1%支持度下的扫描时间大幅缩短至7秒以内