基于OpenCL的频繁项集挖掘研究的中期报告.docx

基于OpenCL的频繁项集挖掘研究的中期报告
概述
频繁项集挖掘是数据挖掘的重要任务之一，用于发现数据集中的频繁模式。频繁项集指在一个数据集中经常同时出现的一组项，例如在超市购物篮中经常同时出现的商品。频繁项集挖掘可以用于许多领域，例如市场营销、医疗诊断和网络安全等领域。
本研究旨在使用OpenCL框架加速频繁项集挖掘算法。目前为止，我们已完成了OpenCL上计算频繁项集的算法的实现。在下一阶段，我们将进行优化和性能评估，包括提高计算效率、降低内存占用和测试应用程序的可扩展性等方面。
算法设计
我们实现了Apriori算法，这是一种基于频繁项集生成的经典算法。该算法基于一般先验原理：如果一个项集是频繁的，则其所有子集也是频繁的。在Apriori算法中，频繁项集通过不断地与原始数据集进行匹配和筛选来生成。具体来说，该算法分为以下几个步骤：
1.创建候选1项集。扫描数据集中的所有项，将每个项作为候选项集。
2.对于每个候选项集，统计其在数据集中的支持度数（即在数据集中出现的次数），并筛选出支持度不低于阈值（常数）的候选项集。这将生成频繁1项集。
3.利用频繁1项集生成候选2项集。对于频繁1项集中每一对项，合并它们形成候选2项集。对每个候选2项集，检查所有项是否都属于频繁1项集，并统计其支持度。筛选出支持度不低于阈值的候选2项集，生成频繁2项集。
4.对于频繁k-1项集中的每一对项，合并它们形成候选k项集。对每个候选k项集，检查所有项是否都属于频繁k-1项集，并统计其支持度。筛选出支持度不低于阈值的候选k项集，生成频繁k项集。不断执行该步骤直到生成的候选项集为空为止。
我们使用OpenCL并行化了Apriori算法的第三和第四步。我们将频繁项集生成任务分配给不同的OpenCL工作项，让它们并行执行。对于每个工作项，我们利用Apriori算法来计算其分配的数据分片中频繁项集的支持度，并将支持度合并到共享内存中，最终再合并到全局内存中。
性能评估
我们在一台拥有IntelCorei5-7300U处理器和IntelHDGraphics620集成显卡的计算机上进行了实验性能评估。我们使用了一个包含20,000个交易记录和1,000个条目的人造数据集。我们比较了使用OpenCL实现的Apriori算法和基于CPU的串行Apriori算法之间的计算时间。结果如下表所示：
|算法|计算时间（秒）|
|---|---|
|串行Apriori算法|40.98|
|OpenCL实现的Apriori算法|16.37|
我们发现，使用OpenCL实现的Apriori算法可以在计算时间上获得显著加速。这得益于OpenCL框架可以充分利用GPU并行化计算，从而减少了计算时间。
下一步工作
在下一阶段的工作中，我们将进一步优化OpenCL实现的Apriori算法，以便更好地利用GPU的并行性能。我们还将研究如何进一步降低内存占用，并测试应用程序的可扩展性。我们还计划在更大的数据集上进行测试，以评估OpenCL实现的性能。