摘 要：分析了并行关联规则挖掘算法存在的不足，提出了一种改进的关联规则挖掘的多核并行优化算法。该算法对Apriori算法的压缩矩阵进行了改造，并在多核平台下利用OpenMP技术和TBB技术对串行程序进行循环并行化和任务分配的并行化设计，最大限度地实现并行关联规则挖掘。
关键词：关联规则；Apriori算法；频繁项集矩阵；OpenMP；TBB；多核并行
海量数据中隐藏着大量的不为人知的模式和知识，寻找有价值的数据模式和知识是数据挖掘研究的主要内容[1]。关联规则的挖掘是数据挖掘中的一项重要的基础技术。经典的关联规则挖掘算法主要有Agrawal等提出的基于Apriori算法的频繁集方法，该算法以递归统计为基础，以最小支持度为依据剪切生成频繁集。随着数据容量的增加，为了提高关联规则的挖掘效率，研究人员提出了并行挖掘算法[2-3]。这些并行算法都是基于MPI和机群系统实现的，虽然具有速度快、容易实现、要求各节点间同步次数较少等优点，但仍然存在着可扩展性差、网络通信量大、负载不平衡、处理器空转、规则合成难度高等缺点。
目前市场上多核处理器已成为主流，比较有代表性的支持多核处理器的并行计算平台之一的线程构建模块TBB(Thread Building Blocking)，可以在其他多核化工具支持下对串行程序中的可并行化部分进行线程的并行化重构，提升多核处理器平台的效能，简化应用程序的并行化过程。本文针对TBB的多核并行编程的优势，结合OpenMP并行编程，提出了一种改进的关联规则挖掘多核并行优化算法。该算法对Apriori算法的压缩矩阵进行了改造，只需扫描一次数据库，并利用TBB技术最大限度地压缩矩阵，使矩阵的运算规模逐步减小。它不需要Apriori算法中的自联接和剪枝，直接通过支持矩阵行向量的按位“与”运算并行地找出频繁集，减少了数据移动带来的额外开销，提高关联规则挖掘效率。与分布式系统的Apriori并行算法相比，该算法采用多核TBB并行技术，不存在节点间的通信与同步、负载平衡和规则合成难度高等问题。实验证明该算法具有高效的并行挖掘效率和较高的多核CPU利用率。
1 挖掘关联规则的串行算法
关联规则的核心是基于两阶段频繁项集思想的递推算法。发现频繁项集是关联规则挖掘应用中的技术和步骤。支持度和置信度是关联规则挖掘中的两个重要指标，为了计算支持度，需要访问数据库。而Agrawal等人提出的挖掘关联规则串行算法Apriori是首先扫描数据库，计算每个数据项的支持度，并根据支持度阈值产生频繁1-项集L1；L1用于找频繁2-项集L2，L2而用于找L3，如此逐层迭代的搜索，直到不能找到频繁k-项集。Apriori算法存在一些难以克服的缺陷：(1)可能产生大量的候选项集，没有排除不应该参与组合的元素；(2)多次扫描数据库，大大增加系统的I／O开销，并且数据库有些可以删除的项或事务被多次扫描；(3)连接程序中相同的项重复较多。针对Apriori算法的缺点，参考文献[4]将事务数据库转换为基于内存的矩阵，在矩阵上找出所需的频繁项集，从而大大减少了数据库的扫描次数，但没有对矩阵进行压缩。参考文献[5-6]对矩阵进行了压缩，但不彻底，而且矩阵数据结构不合理，还额外增加了转置矩阵。
本文介绍一种改进的基于Apriori算法的挖掘关联规则的多核并行优化算法。本文改进了参考文献[4-5]中的矩阵的数据结构：在一个单纯的事务矩阵中，添加2个辅助行和1个辅助列，方便矩阵进行彻底的压缩，使矩阵的规模逐步减小，运算量也大为减少；同时为了配合查找频繁k-项集(k>=2)的运算，设置了一个简单的辅助二维数组，用来记录下标组合情况。
2 多核并行编程技术
OpenMP是共享存储系统编程的工业标准，它具有简单、移植性好和可扩展等优点。OpenMP规范了一系列的编译制导、运行时库函数和环境变量来说明共享存储结构的并行机制。OpenMP实现的是线程级的并行，线程间通过读/写共享变量实现，使用Fork-Join的并行执行模式。
TBB是针对多核平台开发的一组开源的C++的模板库，基于GPLv2开源证书，支持可伸缩的并行编程[7-8]。TBB的编程模式通过使用模板来提供常见的并行迭代模式，使程序员即使在不具备很专业的同步、负载平衡、缓存优化等专门知识的情况下，也能够实现自动调度的并行程序，使得CPU的多个核心处于高效运转之中。TBB完全支持嵌套的并行，程序员可以很容易地创建自己的并行组件，进而构建大型的并行程序。TBB并行编程指定的是任务，而不是线程[9]，并以高效的方式将任务自动映射到线程，程序容易实现，且具有更优的可移植性和可扩展性。
3 关联规则挖掘算法的多核并行优化
本文在改进算法的同时，运用多核平台并行编程的优势，配合采用OpenMP的工作分区sections和并行库TBB的tbb_parallel_for，可以实现每个工作段都由多个执行核并行执行和负载均衡的并行执行固定数目独立循环迭代体，用于提高查找频繁项集的效率。基本流程如图2所示。
4 实验及分析
为了验证基于多核并行技术的改进挖掘关联规则算法的性能，本文在Intel(R)Pentium(R)D CPU 3.0 GHz、 1.86 GHz、1 GB内存的双核处理器系统上测试了参考文献[8]的BBM算法，改进的挖掘关联规则串行算法(以下称本文串行算法)及改进的挖掘关联规则的多核并行优化算法(以下简称多核并行算法)。从参考文献[10]选择数据集进行实验，事务数据库共100 000条事务，事务的平均长度为12。实验测试结果见表1，其中，加速比=本文串行执行时间/多核并行执行时间，CPU运行效率=加速比/核数。
表1表明，支持度较高时，这三种算法的执行时间差别并不大；但当支持度逐渐降低时，与BBM算法相比，本文串行算法的执行时间要更短，而多核并行算法的执行时间几乎是本文串行算法的一半，具有高的并行挖掘效率。从加速比和CPU利用率分析，多核并行算法的多核CPU运行效率达到90%左右，充分调度了两个处理核心的资源，体现了计算机双核的优势。
关联规则技术是数据挖掘中的一种重要的基础算法，本文在深入研究Apriori算法的基础上，提出了一种改进的关联规则挖掘的多核并行优化算法，综合了布尔矩阵和多核并行编程的优点，节约了存储空间，减少了执行时间，具有较高的并行挖掘效率和多核CPU的利用率。本算法的设计方法对于相关算法的研究有较好的借鉴作用。
参考文献
[1] 何军，刘红岩，杜小勇．挖掘多关系关联规则[J].软件学报，2007，18(11)．
[2] Boeyen SX.509(2000)： 4th Edition Overview of PKI&PMI Frameworks. http： //www. entrust. com.
[3] 何中胜．基于向量的并行关联规则挖掘算法[J].计算机系统应用，2009，18(3)：42-45．
[4] 曾万聘，周绪波，戴勃，等．关联规则挖掘的矩阵算法[J].计算机工程，2006，32(2)：45-47．
[5] 张月琴．基于0-1矩阵的频繁项集挖掘算法研究[J].计算机工程与设计，2009，30(20)．
[6] 张素兰．一种基于事务压缩的关联规则优化算法[J].计算机工程与设计，2006，27(18)：3450-3453．
[7] Reinders J. Intel threading building blocks[M]. [s.l.]：O’REILLY出版社，2007.
[8]胡斌，袁道华．TBB多核编程及其混合编程模型的研究[J].计算机技术与发展，2009，19(2)：89-101.
[9] Intel threading building blocks 基于任务编程[OL]. http：//www. cppprog. com/2009/0401/96_2. html．
[10] ALMADEN I. Quest synthetic data generation code. http：//www. almaden. ibm. com/cs/quest/syndata. html.