0 引言

自从著名的关联规则Apriori算法^[1]被提出以来，该算法日益被人们接受并不断完善^[2-3]，它已在个性化推荐系统^[4]、商业领域^[5]、网络安全^[6]、社会管理^[7]等领域取得了成功应用。

但是，传统Apriori算法在生成关联规则算法时，面临的瓶颈之一是遍历数据库由候选2-项集C₂生成频繁2-项集L₂，因为未经处理的C₂规模较大，而且很多不能生成频繁2-项集L₂。为了解决这一问题，直接哈希修剪(Direct Hashing and Pruning,DHP)算法^[8-9]提出利用Hash表删减C₂中无用的候选项集以提高C₂遍历数据库时的速率，研究结果表明，DHP算法较Apriori算法有更好的性能。

随着互联网技术的发展，使得要挖掘的数据呈GB、TB级甚至是PB级增长，面临如此庞大的数据，即使是改进的Apriori算法DHP也不能胜任，而并行处理算法被认为是解决这一问题的有效手段。但传统(Message Passing Interface, MPI)等并行编程模型^[10]又不能处理节点失效等问题，并且给程序员编写程序带来很重负担。Hadoop平台的出现，为Apriori算法与DHP算法处理大规模数据提供了平台支撑。Hadoop平台具有高容错性和高扩展性，以及对节点失效的自动处理等许多优良特性^[11-12]。为了提高DHP算法对海量数据关联规则的高效处理，本文提出了用并行处理的方法来改进DHP，即H_DHP算法。本文首先对DHP算法并行化的可行性进行了理论证明；其次，基于Hadoop平台与Hbase数据库，把Hash表H₂的生成以及频繁项集L₁、L₃~L_k的生成方法进行了并行实现，并生成关联规则；最后给出了仿真实验结果与分析。

1 DHP算法并行化理论证明 1.1 频繁1-项集L₁并行化生成的理论证明

对于原始数据库D，假设I₁，I₂，…，I_n为频繁项，且计数为CI₁，CI₂，…，CI_n，根据最小支持度得到频繁1-项集L₁。

1) 当D划分为n=1个数据子集时，即D₁=D时，I₁，I₂，…，I_n的计数为CI₁，CI₂，…，CI_n，根据最小支持度得到频繁1-项集L₁，与D得到的结果相同。

2) 假设D划分为n=k个数据子集时，即划分为D₁+D₂+…+D_k=D时，根据最小支持度可得频繁1-项集L₁，L₁与D得到的结果相同，则：

在子数据集D₁上：I₁，I₂，…，I_n的计数分别为：CI₁₁，CI₂₁，…，CI_n1；

在子数据集D₂上：I₁，I₂，…，I_n的计数分别为：CI₁₂，CI₂₂，…，CI_n2；

…

在子数据集D_k上：I₁，I₂，…，I_n的计数分别为：CI_1k，CI_2k，…，CI_nk；

那么，数据项I₁总的计数为D₁，D₂，…，D_k的计数之和CI₁₁+CI₁₂+…+CI_1k，且CI₁₁+CI₁₂+…+CI_1k=CI₁。

那么，数据项I₂总的计数为D₁，D₂，…，D_k的计数之和CI₂₁+CI₂₂+…+CI_2k，且CI₂₁+CI₂₂+…+CI_2k=CI₂。

…

于是，数据项I_n总的计数为D₁，D₂，…，D_k的计数之和CI_n1+CI_n2+…+CI_nk，且CI_n1+CI_n2+…+CI_nk=CI_n。

3) 当D划分为n=k+1个数据子集D₁，D₂，…，D_k，D_k+1时，I₁，I₂，…，I_n的计数为：

子数据集D₁：I₁，I₂，…，I_n的计数分别为：CI₁₁^*，CI₂₁^*，…，CI_n1^*；

子数据集D₂：I₁，I₂，…，I_n的计数分别为：CI₁₂^*，CI₂₂^*，…，CI_n2^*；

…

子数据集D_k：I₁，I₂，…，I_n的计数分别为：CI_1k^*，CI_2k^*，…，CI_nk^*；

子数据集D_k+1：I₁，I₂，…，I_n的计数分别为：CI_1(k+1)^*，CI_2(k+1)^*，…，CI_n(k+1)^*，则数据项I₁总计数为D₁，D₂，…，D_k，D_(k+1)的计数之和 CI₁₁^*+CI₁₂^*+…+CI_1k^*+CI_1(k+1)^*。根据n=k时的结论有CI₁₁^*+ CI₁₂^* +…+CI_1k^*+CI_1(k+1)^*=CI₁成立。

那么，数据项I₂总的计数为D₁，D₂，…，D_k，D_k+1的计数之和 CI₂₁^*+CI₂₂^*+…+CI_2k^*+CI_2(k+1)^*，根据n=k时的结论有CI₂₁^*+ CI₂₂^* +…+CI_2k^*+CI_2(k+1)^*=CI₂成立。

…

那么，数据项In总的计数为D₁，D₂，…，D_k，D_k+1的计数之和 CI_n1^*+CI_n2^*+…+CI_nk^*+CI_n(k+1)^*，根据n=k时的结论有CI_n1^*+ CI_n2^* +…+CI_nk^*+CI_n(k+1)^*=CI_n成立。

由数学归纳法可知：D划分后得到最小支持度的频繁项集与D得到的频繁项集相同。

1.2 Hash表H₂并行化生成的理论证明

Apriori算法的性能瓶颈在于产生L₂时候选2-项集C₂对数据库的扫描。DHP算法由此提出了使用Hash表H₂的方法来减少C₂的数据项。H_DHP算法中提出了生成H₂时将数据集进行划分，在每个子数据集中并行生成子Hash表，然后将每个子Hash进行合并，得到总的Hash，最后对C₂进行删减的方法。下面给出这一方法并行化的理论证明。

假设原始数据库D，Hash表中有p个桶，桶编号依次为0，1，…，p-1。选择一个合适的哈希函数，其中2项数据项有J₁，J₂，…，J_n，J_n+1，…J_2n，J_2n+1，…，J_pn，则生成的总Hash表如表 1所示。

1) 当D划分为n=1个数据子集时即D₁=D，所得哈希表和原哈希表一样。

2) 设当划分为n=k个数据子集时，即D₁+D₂+…+D_k=D时，得到的Hash表与原始数据库D的相同，则在数据集D₁、D₂与D_k上生成的哈希表如表 2所示。

根据表 2，很容易得到结论：当D得划分为n=k+1个数据子集时，由k+1个子数据集所得的哈希表与D相同。

由数学归纳法可知：DHP算法中Hash表能并行化计算处理。

1.3 Hash表H2并行化生成的理论证明

频繁项集L₃~L_k并行化生成的理论证明过程与频繁1-项集L₁并行化生成的证明过程相同，在此不再赘述。

综上所述：DHP算法可以基于Hadoop平台并行化改进。

2 H_DHP算法并行化策略及实现

假设有原始数据集D，最小支持度计数为2，执行Map任务的节点为3个，执行Reduce任务的节点为2个，D的记录如表 3所示。

设将数据集平均分成3个数据子集D₁、D₂与D₃，其内容如表 4所示，并把它们分别发到3个Map节点。

H_DHP算法的并行化策略描述如下：

步骤1 进行数据预处理，给每个数据项A、B、C、F、E 分别编号1、2、3、4、5。

步骤2 计算最小支持度计数。

1) Map函数的设计。

Map函数的输入：事务编号为key值，每条事务为value值。

Map函数的输出：将所有数据项的key值都设置为{count}，value值都为1。

Map函数的输入与输出见表 5。

2) Reduce函数的设计。

Reduce函数的输入：为1)中Map节点的输出。

Reduce函数的输出：因为所有Map节点的key值均相同，所以所有Map节点的〈key，value〉对均被发送到同一个Reduce节点。Reduce节点的输出格式为：〈{item}，count〉。

3) 根据最小支持度和D中所有数据项的总数计算最小支持度。

步骤3 生成频繁1-项集L₁，并将L₁及各L₁中各频繁项的计数存入Hbase表中。

1) Map函数的设计：Map函数的输入与输出同步骤2。

2) Map节点Combiner函数的设计

Combiner输入：即为步骤2中Map节点的输出，见表 5。

Combiner输出：key值相同的数据项进行合并，value值统计数据项个数，结果见表 6。

3) Reduce函数的设计。

Reduce函数的输入：将Combiner函数的结果按照事先约定的规则发送到不同的Reduce节点。本文根据数据项的序号，将key值奇数序号发送到节点1，偶数序号发送到节点2。接着这2个Reduce节点对收到的中间结果进行〈key，value〉对的划分。

Reduce函数的输出：数据项为key值，数据项计数为value值。

Reduce函数的输入、输出见表 7。

若value值小于最小支持度计数2，则将该项删除。于是，两个节点上的频繁项集L₁₁={{A}，{C}，{E}}，L₁₂={{B}}。然后，将两个节点各自的频繁项集进行合并，得到频繁1-项集L₁={{A}，{C}，{E}，{B}}，并将L₁及其各频繁项的支持度计数存入Hbase表中。

步骤4 生成并行哈希表，以及对应的向量X，用于删减不满足条件的二项项集，得到最终候选二项集。

生成并行哈希表时，设使用的哈希函数为h{x，y}=((order of x)*10+(order of y)) mod 7，其中x为数据项，order of x 是x所在序列中的序号，y为另一个数据项，order of y 为y所在序列中的序号。

Map函数的输入如步骤2中表 5所示，Map函数的输出如表 8所示。

将桶编号为奇数的中间结果发到Reduce节点1，偶数的发到Reduce节点2，并为每个桶设置一个用于统计桶中元素个数的计数器counter，每增加一个元素就counter值就加1，每个Reduce节点的key值为Map节点输出时的key值，value值即为每个桶对应的计数器counter的值。

1) Reduce函数的设计。

Reduce函数的输入：Map节点的输出。

Reduce函数的输出：桶的counter值(即value)，输出结果如表 9。

2) 生成并行Hash表。

将表 9进行合并，得到总的并行Hash表{3，1，2，0，2，2，3}。

3) 生成位向量X。

将每个桶计数器counter的值和最小支持度计数进行比较，若计数器的值大于等于最小支持度计数，则位向量X[key]为1，否则为0。于是，H₂对应的位向量X^[1~7]={1，0，1，0，1，1，1}。

步骤5 将位向量X或是并行哈希表发送到每个节点，用于快速生成L₂。

1) 将生成的L₁进行自连接，生成2-项集C₂′={{AB}，{AC}，{AE}，{BC}，{BE}，{CE}}。分别将C₂′中每个项集的每个项的序号代入已经设定好的哈希函数中，计算得出C₂′中每个项集的哈希地址，分别为{5，6，1，2，4，0}，同时，根据位向量X的取值，将不符合的项集删除，得到最终候选项集C₂={{AB}{BC}{BE}{CE}}。

2) 由C₂扫描D，依据最小支持度计数，生成频繁2-项集L₂。将C₂发送到每个Map节点，子数据集D₁、D₂、D₃分别发送到3个节点。

①Map函数的设计。

Map函数的输入：如步骤2中表 5所示。

Map函数的输出：以每条事务的2项子集为key值，将value值全部设定为1。

②Map节点Combiner函数的设计。

Combiner函数的输入：即为①中Map函数的输出。

Combiner函数的输出：将Map函数输出key值相同的项进行合并作为Combiner函数输出的key值，key的计数作为value值，输出结果如表 10所示。

③Reduce函数的设计。

Reduce函数的输入：为Combiner函数的输出。

Reduce函数的输出：将Combiner函数key值相同的项进行合并，key的计数作为value值。

④得到频繁2-项集L₂={{AB}，{BE}，{BC}，{CE}}。

步骤6 生成频繁项集L₃~L_k。

在生成频繁项集L₃~L_k时，Map函数与Reduce函数设计如下：

1) Map函数：将频繁项集L_k-1的每个频繁项的前k-2项作为key，最后一项作为value。

2) Combiner函数：key相同的value全部合并，并且保持key不变。

3) Reduce函数：键值key分别和value值的所有2-项子集进行组合得到候选项集。然后，根据最小支持度计数生成频繁项集，并把频繁项集存入Hbase表中。

3 关联规则的生成

由第2章可知：H_DHP算法生成的频繁项集L₁~L_k已存入Hbase表中，所以在生成关联规则时，只需从Hbase表中查询相应的频繁项集和其支持度计数。若非频繁1-项集，则求出该频繁项集的非空真子集，计算其置信度并与最小置信度阈值进行比较，若计算的置信度满足最小置信度阈值，则为所生成的关联规则。

根据Hbase表中的频繁项集，关联规则的生成步骤如下：

步骤1 取出Hbase表中的键值，判断是否为频繁1-项集L₁。

步骤2 若键值不是频繁1-项集L₁，则查询该键值的支持度计数并找到该键值的所有非空真子集。

步骤3 根据频繁项集的生成规则，它所有非空真子集也是频繁项集，因此查询Hbase表，得到非空真子集的支持度计数。

步骤4 根据置信度的定义，计算“真子集的势=>该键值”的置信度。将所得的置信度与置信度阈值进行比较，满足条件的将用于生成最后的关联规则，即非空真子集=>该键值。

4 实验结果与分析

从前面的理论分析可知：H_DHP算法与DHP算法生成的关联规则是完全一致的,因此主要测试H_DHP算法的并行性能指标。

首先在http://archive.ics.uci.edu/ml/datasets.html下载一组含有多个文件的超市消费者购买记录数据集并进行多次复制,其中数据集记录了每一位顾客购买的物品名称。

1) 运行时间对比。

实验目的：比较DHP算法与H_DHP算法的运行效率。

实验方法：当集群节点一定时，H_DHP算法与串行DHP算法在处理相同规模数据集时所花费的时间。

实验步骤如下：

步骤1 当Hadoop集群节点为1时，分别记录DHP算法和H_DHP算法处理相同规模数据时的运行时间。

步骤2 当Hadoop集群节点为2时，分别记录DHP算法和H_DHP算法处理相同规模数据时的运行时间。

步骤3 当Hadoop集群节点为3时，记录DHP算法和H_DHP算法处理相同规模数据时的运行时间。

实验结果如图 1示。

从图 1可以看出：当Hadoop集群节点为1时，数据规模较小即集群处理数据的时间小于集群中Job任务启动、交互等时间时，处理相同规模的数据，并行H_DHP算法的运行时间大于串行DHP算法。

当集群节点为2时，可看出数据规模较小时，DHP算法的运行时间少于H_DHP，但是，随着数据规模的增大，DHP算法的运行时间逐渐比H_DHP算法的运行时间长。另外，随着数据规模的增大，DHP算法的处理时间折线比H_DHP算法的陡峭，说明DHP算法运行时间的增长速率比较快，这是因为H_DHP算法是将任务分配到2个节点并行完成，每个节点处理的数据规模都比DHP算法在单机上处理的数据规模小，所用的时间较少，所以在集群上运行时间增长的速率较慢。

当Hadoop集群节点为3时，折线图和集群节点为2时相似。但是，当数据集大小逐渐增大时，随着节点数的增加，图中两个算法的时间折线图的垂直差越来越大，H_DHP算法的运行时间不仅比DHP算法的少，而且速率越来越快，说明H_DHP算法在处理大数据集时，效果比DHP算法好。

实验结果表明：

①当数据集规模较小时，DHP算法的效率高于H_DHP算法，因为H_DHP算法运行于Hadoop平台上，Hadoop平台处理数据时要对数据进行加载，集群上的Job任务不但要进行启动，而且它们之间还要进行信息交互。同时，集群上的Map节点向Reduce节点传递数据时，也有时间代价，最后才能得到最终的处理结果，这都将消耗大量的时间，远远超过了集群中真正处理数据所花费的时间。

②当数据规模增大时，集群处理数据的时间大于集群Job启动、交互等的时间，H_DHP算法的效率将高于DHP算法，因为并行算法将任务分配到了多个节点上同时进行处理，而且随着集群节点的增加，运行时间减少的速率越来越快。

2) 加速比实验。

加速比是指当数据集规模相同时，使用H_DHP算法对其进行处理，测试节点为1所耗费的时间与节点为多个所消耗的时间的比率。

实验方法：数据集规模一定，集群节点不同时，分别计算H_DHP在节点为1时所耗费的时间与多个节点所耗费的时间比率。该实验中集群1节点所花费的时间和集群多节点所花费的时间分别为T_DHP表示T_H_DHP。

实验步骤如下：

步骤1 当数据集大小为4 045 KB时，增加Hadoop集群的节点，记录T_DHP与T_H_DHP的比率。

步骤2 当数据为9 005 KB时，增加Hadoop平台的节点，记录T_DHP与T_H_DHP的比率。

步骤3 当数据为50 065 KB时，增加Hadoop平台的节点，记录T_DHP与T_H_DHP的比率。

实验结果如图 2所示。从图 2可以看出：当数据集较小时，因为集群Job任务启动和交互的时间大于对数据集处理的时间，故Hadoop集群中每增加一个节点，时间可能就会增加，加速比小于1，且逐渐减小，T_DHP仍然大于T_H_DHP。

当数据集增大到一定程度时，即Hadoop集群上Job任务的启动和交互的时间小于Hadoop集群对数据处理的时间，随着Hadoop节点的增加，T_H_DHP增加的速率逐渐小于T_DHP增加的速率，加速比逐渐上升。

当数据集增大到一定程度时，加速比增大的趋势较快。这说明，当处理大数据集时，随着Hadoop集群的节点增加，T_H_DHP不仅逐渐小于T_DHP，而且增加的速率增逐渐小于T_DHP，加速比大于1。

实验结果说明：处理大数据集时，随着Hadoop集群节点的增加，H_DHP算法可以有效地提高对数据的处理能力和处理效率，有很好的加速比。

3) 扩展性实验。

实验目的：逐步增加集群节点数，测试H_DHP算法对数据的处理能力。

实验方法：使用3个规模的数据集，测试随着节点增加，H_DHP处理数据所花费的时间T_H_DHP。

实验步骤如下：

步骤1当数据集大小为289 716 KB时，随着节点数的增加，记录时间折线图。

步骤2当数据集大小为579 432 KB时，随着节点数的增加，记录时间折线图。

步骤3当数据集大小为1 448 580 KB时，随着节点数的增加，记录时间折线图。

实验结果如图 3所示。

从图 3可以看出，当数据集大小一定时，随着Hadoop集群节点的不断增加，T_D_DHP不断减小；另一方面，当时间规定在相同大小时，随着节点的增加，H_DHP算法处理的数据规模不断增大，说明H_DHP算法具有很好的可扩展性。

5 结语

本文首先介绍了DHP算法的并行改进策略，并对DHP算法并行化策略的可行性进行了理论分析。接着，提出了基于Hadoop平台，把Hash表H₂的生成以及频繁项集L₁、L₃~L_k的生成方法进行了并行实现，并借助Hbase数据库生成关联规则的方法，最后从运行时间效率，加速比，可扩展性三个方面对并行H_DHP算进行性能测试。测试结果表明： H_DHP算法在数据的处理时间效率、处理数据集的规模大小，以及加速比和可扩展性等方面都有较好的性能。下一步工作将把本文研究成果应用于电子商务个性化推荐系统中。