基于哈希树的并行关联规则挖掘算法研究∗

吉 祥 黄树成

（江苏科技大学计算机学院 镇江 212003）

1 引言

关联规则是数据挖掘研究中的一个热门话题，它的主要作用是发现海量数据中隐藏着的有趣的关联和有意义的联系。Apriori 算法是经典关联规则挖掘算法，其本质是在项集的幂集中利用统计学的基本原理，通过多次扫描数据库找出频繁项集，再根据已找到的频繁项集生成关联规则［6］。近年来，国内外许多学者对关联规则挖掘算法进行了大量的研究，其主要工作是提高挖掘算法的效率。如Savasere 等提出的基于数据分割的Partition 算法，Park 等提出的基于散列的哈希算法以及国内学者于守健等提出利用前缀项集的存储方式，通过哈希表快速查找来提高查找效率［1］。这些算法都在一定程度或不同侧重点上对Apriori算法进行了优化，但这些算法并没有充分发挥多核CPU的优势，因而在实际应用中仍不够理想。本文首先对Apriori 算法的挖掘过程进行详细概述与论证，研究候选项集的剪枝和支持度计数过程，针对支持度计数过程，提出一种基于Hash 树的并行计数算法，改进算法可以有效提高支持度计数的速度，从而提高关联规则的挖掘效率。

2 经典关联规则挖掘算法Apriori算法

Apriori 算法是由Agrawal等在1993年提出的非常有影响力的挖掘布尔关联规则频繁项集的算法［7］。Apriori 算法是一种广度优先的搜索算法，它通过迭代查找来挖掘频繁项集，比如用频繁k-项集探索候选k+1 项集。首先，算法扫描一次数据集生成候选1-项集C1，对C1做筛选，删除C1中支持度小于给定下限值minsup 的候选项得到频繁1-项集L1。对L1做连接运算并去除不必要的项集产生候选2-项集C2，将C2中支持度不满足的项删除得到频繁2-项集L2。对以上叙述的过程进行有限步的循环，若没有新的频繁项集出现，算法终止。

现具体阐述Apriori算法的主要步骤：

1）扫描事务数据集，产生候选1-项集的集合C1；

2）统计C1中每个候选集的计数值，剔除不符合下限值的项，生成频繁1-项集的集合L1；

3）设定初始值n=1；

4）对Ln作Ln∞Ln的连接运算，再剪掉运算结果不必要的项集，生成候选n+1项集Cn+1；

5）统计Cn+1中每个候选集的计数值，剔除不符合下限值的项，生成频繁n+1项集的集合Ln+1；

6）若Ln+1≠Ø，对n 作增1 操作，返回4）；否则，转7）；

7）从频繁集中寻找规则，删除小于给定置信度的规则，算法结束。

从上述步骤来看，Apriori 算法存在三个缺点：1）候选项集的规模较大，尽管采用了剪枝技术，但仍存在不必要的候选项集；2）计算候选集支持度时，效率太低，算法每次将数据记录与所有候选集对比了一次；3）计算支持度时，算法每次读取了事务数据集，系统时间开销较大。针对上述缺点，本文提出了基于Hash 树并行计算支持度的优化算法。该算法对前两个缺点进行改进，对于第三个缺点，国内外已有很多文献做了进一步的研究，本文不做研究。

3 基于Hash 树的并行计数的改进算法-Apriori_ParallelCount

为了优化Apriori算法，以下性质将作为优化依据。

性质1：k 项集lk是频繁项集的必要条件是它所有的k-1子项集lk-1也是频繁项集［6］。

证明：设有一k 频繁集lk，则Support(lk)不小于支持度下限。对于lk的任意一个k-1 项子集lk-1，Support(lk-1)≥Support(lk)，那么Support(lk-1)也必然不小于支持度下限。又因lk-1可以是lk的任何k-1子项集。故而命题得证。

性质2：如果k-项集lk的任意一个k-1 子项集lk-1不是频繁项集，则k-项集lk不是频繁k-项集［6］。

证明：现有一k-项集lk，它存在一个k-1 项子集lk-1不是频繁项集，那么Support(lk-1)一定比支持度下限值小，而Support(lk-1)≥Support(lk)，所以Support(lk)也小于支持度下限值。也就是说，lk是非频繁集。命题得证。

性质3：如果k-项集lk是频繁k-项集，则其每一个项在频繁k-1 项集Lk-1中出现的次数一定不小于k-1次［7］。

证明：设有一k频繁集lk。由性质1知，它的全部k-1 项子集都是频繁的，又lk共有k 个k-1 子项集，所以，这k 个k-1 子项集都在频繁k-1 项集Lk-1中出现。那么，对于项集lk来说，它的每一个项在Lk-1中都至少出现了k-1次。命题得证。

性质3 为改进算法缩减候选项集规模提供了有力的依据。在改进算法中应用该性质可以进一步对频繁k-1项集Lk-1进行筛选，使参与连接的频繁项集数量大大缩减，从而降低了候选项集的数目，提升了算法的挖掘性能。

本文应用以上性质对Apriori算法进行改进，主要体现在两个方面。

1）降低候选项集规模。由频繁k-项集Lk求候选k+1 项集Ck时先统计Lk中每个元素的频数，由性质3知元素频数少于k的项集是不可能自连接得到频繁k+1 项集，所以可以在连接前将其删除，减少频繁k-项集的数量，进而缩小连接产生的候选k+1项集的规模。

2）组织候选集成Hash 树结构，并行计算支持度。在对候选项集Ck进行支持度计数时，为了减少比较次数，可以利用Hash 树达到此目的。将Ck组织成Hash 树，存放在不同的桶中，计数时，将事务中的所有项集也散列到对应的桶中。这种方法不是将事务中的每个项集与所有候选项集比较，而是将它们与同一桶内候选项集进行匹配［5］。另外，考虑到现在的CPU几乎都是多核的，这就使多线程并行成为可能。对于事务数据集D，可以将其均匀的划分为若干块子数据集S，为每个子数据集S 创建线程，线程在该子数据集S 上对候选项集进行支持度计数，其结果存放在当前线程内部数组中。待得所有线程执行完毕，取出各线程内部数组数据相加得到候选项集Ck在整个事务数据集D 上的支持度计数。

改进的Apriori_ParallelCount 算法的执行步骤如下：

1）扫描事务数据集，产生候选1-项集的集合C1；

2）将候选1-项集C1组织成Hash 树结构，对C1中的候选集并行计数，具体过程如步骤5）所示，删除小于给定支持度的项生成频繁1-项集L1；

3）设定初始值i=1；

4）对频繁项集Li中每个项出现的次数进行统计，根据性质3，若某一项出现的次数小于i，则删除包含该项的项集得到，然后由经过连接步和剪枝步生成候选i+1项集Ci+1；

5）将候选项集Ci+1组织成Hash 树结构。扫描事务数据集D，将数据集D 均匀划分为若干块，利用多线程技术并行计算候选项集Ci+1在各个块上的支持度，最后，归并各个块上的支持度获得Ci+1在数据集D上的支持度。删除不符合阈值的项，生成频繁i+1项集的集合Li+1；

6）若Li+1≠Ø，对i作增1操作，返回4）；否则，转7）；

7）从频繁集中寻找规则，删除小于给定置信度的规则，算法结束。

举例来阐述改进算法。设有一零食售货商店，假设5 位客户购买了5 种商品。5 位客户记为T1～T5。5 种商品为巧克力、果冻、饼干、面包、牛奶，为方便，5种商品记为1～5。给定的支持度为3，算法将数据集D 均匀分割为2 块，创建两个线程并行计算候选项集的支持度。则优化后的算法执行过程如图1所示。

具体解释如下：算法扫描数据集D 产生候选1-项集C1，将数据集D 划分为D1和D2，创建两个线程对候选1-项集并行计数，合并候选1-项集在D1和D2上的计数结果得到候选1-项集在数据集D 上的计数结果。对C1进行筛选，将计数结果小于3 的候选集剔除掉得到频繁集L1，对L1作连接和剪枝运算产生候选2-项集L2。对以上叙述的过程进行有限步的循环，若没有新的频繁项集出现，算法终止。注意L2中由于项2和3的个数均小于2，故由性质3 知包含2 或3 的候选项全部剔除。对于支持度计数，将候选项集组织成特殊的树状结构Hash 树，然后散列数据记录到Hash 树中进行比对。以上图C2为例，构建Hash树并散列事务T2，如图2所示。

图1 改进算法挖掘频繁项集过程

图2 在Hash树根节点散列事务

支持度计数过程中，算法首先根据C2构建Hash 树，Hash 函数为h（p）=p mod 3，然后枚举事务T2 形成2-项集，最后将事务T2 所包含的2-项集散列到Hash 树中进行匹配。由于事务中的项集只与同一桶内的候选项集比较，因而有效降低了计算支持度所花费的时间开销。

4 实验与分析

为了比较改进算法Apriori_ParallelCount 和经典算法Apriori的效率，本节以实验为基础对两个算法进行详细阐述。本实验的测试环境如下：采用Inter Core i3-2350M 2.30GHz 的CPU，4GB内存，Windows 8.1 专业版操作系统，使用Java 编程语言，编程工具为Eclipse Photon 2018。

实验所采用的数据集是从GitHub 社区上下载的retail文本文件，该文件共有88162条事务记录。

实验1：本次实验比较Apriori 算法和创建一个线程的Apriori_ParallelCount 算法的时间效率。给定支持度值为2%，4%，6%，8%，10%。从数据集文件retail 中选取前10000 条记录来测试两个算法的运行时间。其执行时间（单位：ms）的结果见表1。

表1 不同支持度两个算法执行时间比较

将实验结果以点线图的形式表示出来，如图3所示。

图3 不同支持度两算法执行时间比较

从上图可以看出，改进算法Apriori_Parallel-Count相较于经典算法Apriori时间性能有较明显的提升，Apriori 算法执行时间集中在12000ms 左右，改进算法多集中在3000ms 左右。另外，两个算法运行所花费的时间整体上都是伴随着支持度的增大而降低。这是因为，支持度的增大会使频繁项集数目出现一定程度的缩减，从而提高算法的效率。从曲线的前半部分可以看出，支持度从2%增大到4%时，两个算法的执行时间都出现大幅度的下降，尤其是改进算法Aproiri_ParallelCount。出现这个现象的原因可能与数据集本身有关，本实验采用的数据集在支持度设定为2%到4%时，频繁项集的规模会大大的减少。再看曲线后半部分，当支持度为10%时，改进算法的执行时间有所增加。这个情况主要考虑是存在误差，由于支持度设定为8%和10%时，算法执行时间差距不大，因而可能会产生细微的误差。整体来看，改进算法的挖掘效率较经典算法具备显著优势。

实验2：本实验继续比较Apriori 算法和创建一个线程的Apriori_ParallelCount_算法的执行时间。设给定的支持度值为10%，从数据集文件retail中分别取1000条、5000条、10000条、50000条和80000条事务记录来测试两个算法的运行时间。测试结果（单位：ms）如表2所示。

表2 不同记录数两个算法执行时间比较

将表格转换为曲线图，如图4所示。

图4 不同记录数两个算法执行时间比较

从图4 可以看出，改进算法的执行时间普遍比Apriori 算法少，尤其是当数据量很大时，改进算法的性能更显著。随着记录数的增加，我们可以看到经典算法的执行时间增长幅度很快，几乎呈指数级增长，而改进算法的增长幅度较慢，有放缓的趋势。这说明改进算法相较于经典Apriori 算法更适合处理十万级甚至更大的数据量，有一定的实用价值。另外，在记录数只有1000条时，我们发现Apriori 算法的执行时间比改进算法更短。这是因为，改进算法读取事务数据集形成候选1-项集时，需要按字典序对候选项集排序，这个过程会花费一些时间。总的来说，尽管改进算法花费了一些时间排序，但在面对急剧增长的数据量情况下，改进算法的时间效能是优越于经典算法Apriori的。

实验3：本实验比较不同线程版本Apriori_ParallelCount 算法的运行效率。设给定的支持度值为10%，从数据集文件retail中选取前50000条记录来测试不同线程数的改进算法的运行时间。实验结果（单位：ms）如表3所示。

表3 不同线程数改进算法执行时间比较

将此表以曲线图表示，如图5所示。

从图5 可以看出，随着线程数的增多，改进算法的执行时间整体在降低。这是因为，实验所采用的CPU 是双核四线程且操作系统是基于线程调度的，所以多个线程会被调度到多个核心上运行，使线程并行执行，从而降低算法的执行时间。尤其是当创建的线程数从1 变为它的两倍2 时，算法执行时间大幅下降。当线程数从4 增加到5 时，算法执行时间有所上升。这是因为，线程数多于核心数，线程上下文切换需要花费时间。总体来说，改进算法充分利用了多核CPU的优势，其效率较经典算法也有明显提高。

图5 不同线程数改进算法执行时间比较

5 结语

本文提出了一种基于Hash 树的并行计数的关联规则优化算法，通过实验来验证改进算法与经典算法之间的性能差异。改进算法对候选项集的数目进一步做了裁剪，同时利用多线程技术并行计算各个候选项集的支持度，进而提高算法挖掘频繁模式的速度。实验结果表明，改进算法相对于Aprori算法是十分高效的，尤其对在海量数据中挖掘关联规则具备优势。