开放科学（资源服务）标志码（OSID）：

0 概述

关联规则挖掘技术^[1]是数据挖掘领域的重要分支之一，其旨在找出各数据项之间的相互关系，被广泛应用于社交网络、精准营销等领域。然而，随着动态大数据的发展，数据维数逐渐升高。医疗数据、全球气候数据以及多媒体数据等均属于高维数据，且此类数据具有数据量大、数据特征丰富以及数据稀疏等特性^[2]。因此，大部分数据挖掘技术已经从单目标分析扩展为多目标融合分析^[3]。采用高效的方式准确捕捉高维复杂数据的特征属性，以及解决节点分布的负载均衡化问题，并有效提高频繁项集的紧凑程度^[4]成为研究热点。

本文提出基于MapReduce的高维数据频繁项集挖掘算法PARDG-MR。通过设计基于高维数据维度粒化以及节点负载均衡的数据预处理策略，并对复杂的高维数据进行特征属性捕捉，构建基于本地PJPFP-Tree树存储结构的算法步骤并行化方法。在此基础上，提出基于剪枝前缀推论（Pruning Prefix Lemma，PPL）的整合节点算法，从而提高算法整体运行速率，且减少算法执行时间和内存。

1 相关工作

高维数据预处理过程包括以特征提取和特征选择^[5]两种方式，在有效消除无关、冗余特征的同时也减小了特征挖掘空间，但是该方法忽略了数据的敏感性以及数据特征之间的关联性。为获得更优的数据特征属性挖掘结果，研究人员对高维数据进行维数约简。文献[6]提出基于图的大数据实体识别算法，并将高维数据关系映射在图中，其中边代表某些数据项间的关系，每条边的权值代表项间关联的程度。该方法避免了重复计算数据项维度属性间的关联程度，并在高维数据的约简^[7]方面取得了相应进展。但是此类方法在数据集中仍存在噪声数据，其是影响数据特征捕捉精确度的关键因素，并且高维数据分布在对应的低维空间中，也会缩短噪声数据与可用特征数据之间的距离，从而降低挖掘数据的价值。因此，在研究高维数据特征约简过程中，粒计算理论^[8]应运而生，其将输入的原始高维数据集分割成包含多个信息粒的小数据集，同时通过粒计算理论对大规模高维数据进行预处理。粒计算理论能够保证数据价值，且精准捕捉数据特征，从而降低数据复杂度。文献[9]提出邻域知识粒度概念用于评估高维数据特征的粒化能力，并将邻域知识粒度与邻域依赖度相结合作为启发式函数，用于数据属性约简。此外，文献[10]针对高维数据系统特征属性的粒度选择问题，分析了信息粒与粒度划分概念，准确地反映决策系统中数据维度粗糙化程度，从而弥补了在大数据环境中高维数据粒化时仅基于论域属性进行约简的不足。文献[11]提出通过对解析式模拟与信息粒进行替换，以定义邻域互补熵、邻域互补条件熵，进而得到非单调性高维数据属性粒化和非单调性高维数据属性约简。因此，通过粒计算理论对高维数据进行预处理，准确捕捉其数据特征成为挖掘高维数据的研究热点。

高维数据通过粒化降维能在一定程度上提高捕捉数据特征的精确度，但是在大数据环境中数据节点的负载均衡化也一直是研究人员关注的课题。文献[12]提出采用根据节点频繁度不同划分数据的负载均衡策略，通过估计节点的任务数对其进行平均分组，以解决数据倾斜、负载过重的问题。文献[13]提出TBLB算法，该算法结合节点能量和节点度，以形成根据路径性能评价因子进行路径选择的负载平衡树，该平衡树能够有效地均衡节点负载，降低节点能量消耗。目前，大部分负载均衡方法^[14]在分组过程中采用贪心策略，利用计算量模型公式来预估频繁项产生的负载量，将负载量大的项放在负载量总和最小的组以实现负载均衡，然而，计算量模型易造成节点在分布过程中所消耗的时间差异，使得算法的整体效率降低。因此，粒化后的高维数据特征集可以实现分组结果的负载均衡化，成为并行化计算思想发展过程中的主要研究方向。

大数据环境中的FP-growth算法^[15]在并行频繁项集的挖掘执行过程中，数据的频繁交互需要消耗大量资源，使得内存负载压力较大。为此，研究人员尝试将MapReduce数据处理模型与FP-growth挖掘算法相融合，提出了PFP-growth^[16]算法。该算法在执行针对频繁项集的挖掘行为时，每个计算节点无需互相等待或进行节点间的数据交换，均为相互独立的计算节点，从而提高频繁项集在并行挖掘过程中的效率。文献[17]提出MRPrePost算法，在第一次MapReduce任务执行结束后得到频繁1-项集的F-list，并生成PPC-Tree树，对分布在其上的多个计算节点进行频繁项集挖掘，且该过程不需要将PPC-Tree树保存在内存中，既提高了项集支持度的计算效率，又减少了算法在时间与空间方面的消耗。文献[18]提出仅包含单向频繁模式的UFP-Tree树，并引入被约束子树，分别通过递归和非递归方法对指向相同端点和不同端点的路径进行频繁项集挖掘。以上研究旨在减少数据间交互次数且避免消耗过多资源。因此，如何减少因数据频繁交互带来的影响逐渐成为研究热点。

在大数据环境下，数据挖掘效率的影响因素不仅包括数据维度及数据结构，还包括频繁项集紧凑化过程中的算法步骤。近年来，为简化频繁项集的紧凑化步骤，文献[19]提出深度路径优先搜索和长度超集优先检验的改进方法。该方法通过深度优先的路径递归搜索，连续完成最大频繁候选项集的挖掘，并根据路径长度对挖掘结果进行排序，并检验所挖掘的频繁项集超集，以减少候选项集的数量和挖掘次数，从而解决在数据量大、维度高时挖掘效率低的问题。文献[20]提出2FP-Forest算法，该算法通过第一次完全扫描数据集得到全部1-项集和2-项集的支持度，同时充分利用2-项集的剪枝作用，使得所构建树的深度、宽度均比FP-Tree树少。此类算法通过生成最大频繁候选项集以及缩短频繁模式树的构建时间，提高频繁项集的紧凑化程度，从而提升整体的挖掘效率，但是仍无法避免频繁项集在剪枝过程中的冗余搜索和无效计算。因此，如何在粒化后的高维数据特征集中最大程度提高频繁项集紧凑化程度仍是重要问题。

2 相关概念

定义1（N-list^[21-22]）   给出任意2个（k-1）-项集$ {X}_{A} $和$ {X}_{B} $，使其均为具有相同前缀的频繁项集，故对应的N-list结构分别表示为：

$ N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}\left({X}_{A}\right)=\\ \ \ \ \ \ \ \ \ \left\{\left({x}_{11}, {y}_{11}, {z}_{11}\right), \left({x}_{12}, {y}_{12}, {z}_{12}\right), \cdots , ({x}_{1m}, {y}_{1m}, {z}_{1m})\right\} $

$ N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}\left({X}_{B}\right)=\\ \ \ \ \ \ \ \ \ \left\{\left({x}_{21}, {y}_{21}, {z}_{21}\right), \left({x}_{22}, {y}_{22}, {z}_{22}\right), \cdots , ({x}_{2n}, {y}_{2n}, {z}_{2n})\right\} $

$ k- $项集$ {X}_{AB} $的$ N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $定义如下：

对于任意$ \left({x}_{1p}, {y}_{1p}, {z}_{1p}\right)\in N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}\left({X}_{A}\right) $，$ 1\le p\le m $，$ \left({x}_{2q}, {y}_{2q}, {z}_{2q}\right)\in N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}\left({X}_{B}\right) $，$ 1\le q\le n $，若满足条件$ {x}_{1p} < {x}_{2p} $，$ {y}_{1p} > {y}_{2p} $，则将$ \left({x}_{1p}, {y}_{1p}, {z}_{2q}\right) $加入到$ {X}_{AB} $的$ N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $中，得到初始$ N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $。

定义2（JPFP-Tree树^[23]）   一种树形数据结构，树中节点由节点名称（Item-name）、节点计数（Count）、子节点列表（Children-list）组成。

定义3（空间数据库^[24-25]）   由空间关系数据与对象关系数据集构成，实现空间数据的数据库化。空间数据库的设计过程包括数据库的逻辑结构设计以及空间数据的集成存储。其中，数据库的逻辑结构设计采用经典的实体-联系（Entity-Relation）图描述现实地理世界，各图层间的路径数与数据属性特征数成正比，具体设计如图 1所示。

定义4（剪枝性质^[26]）   如果项集$ X= ${$ {x}_{1}, {x}_{2}, \cdots , $$ {x}_{k} $}是频繁的，$ \forall \alpha \in X\bigcap \beta \in X\bigcap \alpha \ne \beta $，则2-项集$ \left\{\alpha ，\beta \right\} $一定频繁。相反，$ \exists \alpha \in X\bigcap \beta \in X\bigcap \alpha \ne \beta $，如果2-项集$ \left\{\alpha , \beta \right\} $不是频繁项集，则项集$ X $也一定非频繁。

3 PARDG-MR算法

本文提出的PARDG-MR算法的基本原理如下：

1）提出DGPL策略对数据进行预处理，使得复杂的高维数据完成特征属性的稳定捕捉，该方法首先提出基于属性精确度计算（Attribute Accuracy Calculation，AAC）方法和维度粒大小（Dimensional Grain Size，DGS）计算的维度粒化算法（Dimensional Granulation Algorithm，DGA），其次根据各特征属性的前缀长度，提出在粒化后的数据集中基于负载估计（Load Estimation，LE）策略的负载均衡算法（GPL），提高数据的特征属性捕捉精确度，从而解决划分中节点负载不均衡的问题。

2）在数据划分完成的基础上，设计了本地PJPFP-Tree树存储结构，并构建算法步骤并行化策略（PARM）来减少数据交互频度，降低磁盘I/O次数，减缓负载压力。

3）针对候选剪枝策略，提出基于剪枝前缀推论（Pruning Prefix Lemma，PPL）的整合节点剪枝算法（PJPFP），该策略将本地生成的PJPFP-Tree树中的频繁2-项集挖掘结果作为完全剪枝的剪枝条件，使得PJPFP-Tree中不存在非潜在候选3-项集，从而增强频繁项集紧凑化程度，实现算法整体速率的提高。

3.1 DGPL策略

大数据环境下的高维数据挖掘算法在进行数据预处理时，存在以下3个问题：

1）在数据属性特征捕获过程中属性划分通常仅基于部分相容的数据属性，而忽略其他数据造成数据的捕获结果不具备全局性。

2）在数据划分过程中，无法消除噪声数据，不能提取单个维度的属性，使得研究不具有针对性。

3）分类后的数据集无法将数据均匀分组至各数据节点，造成数据倾斜、负载不均衡，使得算法执行效率低。针对以上问题，本文先对数据集进行特征维度属性粒化处理，提出DGA。针对DGA算法处理后的数据集，提出基于LE的GPL算法，以实现在数据划分过程中的负载均衡化。

3.1.1 DGA算法

DGA算法主要是进行高维数据的预处理，通过将数据特征属性维度粒化，以准确地捕捉此类高维数据的特征，其主要分为2个阶段：

1）在高维复杂数据集中，将属性精确度计算方法AAC作为设置维度粒大小的参数，充分挖掘数据的质量，以避免产生过多噪音数据。

定义5（AAC方法）   若数据空间中第$ i $维度的数据点个数为$ N $，均方差为$ {S}_{i} $，均值为$ \mu $，属性精确度为$ {d}_{i} $，则AAC的计算如式（1）所示：

$ {d}_{i}=\frac{{S}_{i}}{\mu } $

(1)

证明  因为$ {S}_{i}=\surd {S}_{i}^{2}=\sqrt[]{\sum\limits _{i=1}^{n}{\left({n}_{i}-\mu \right)}^{2}} $，当第$ i $维中的属性值较集中时，即$ {n}_{i}\underset{}{\Rightarrow }\mu $，则有$ {S}_{i}\underset{}{\Rightarrow }0 $，故$ \frac{{S}_{i}}{\mu }\underset{}{\Rightarrow }0 $，即$ \frac{{S}_{i}}{\mu } $值越小，数据特征属性分布趋于集中，该属性精度越高；反之，$ \frac{{S}_{i}}{\mu } $值越大，数据特征属性分布越离散，该属性精度低，可用性差。此外，当数据在第i、j维度中的$ {S}_{i} $值相同，均值相差较大时，即$ {S}_{1}={S}_{2} $，$ {\mu }_{1}\underset{}{\Rightarrow }0 $，$ {\mu }_{2}\underset{}{\Rightarrow }\mathrm{\infty } $，则有$ {S}_{1}\underset{}{\Rightarrow }\sqrt[]{\sum\limits _{i=1}^{n}{\left({n}_{i}\right)}^{2}} $，$ {S}_{2}\underset{}{\Rightarrow }\sqrt[]{\sum\limits _{i=1}^{n}{\left({n}_{i}-\mathrm{\infty }\right)}^{2}} $，当属性值$ {n}_{i} $发生变化时，$ \Delta {S}_{1}\gg \Delta {S}_{2} $，因此$ \mu $越大，$ {d}_{i} $值越小，所得数据特征属性精度越高，数据扰动率越低；反之，属性精度越低，数据扰动率越高。

2）基于AAC方法根据维度相关性以及总体方差定义的原理，提出维度粒大小计算方法DGS。该策略定义如下。

定义6（DGS方法）   若数据空间中的总维度数为$ D $，各维度的属性精度值为$ {d}_{i} $，本文选取$ {d}_{i} $的均值$ \gamma $作为维度粒大小的选取参数，故维度粒大小的计算如式（2）所示：

$ P={D}^{\gamma } $

(2)

证明  因为$ \gamma =\frac{1}{n}\sum\limits _{i=1}^{n}{d}_{i} $，其中$ 0 < {d}_{i}\le 1 $，则$ 0 < \gamma \le 1 $，故$ P < D $，即$ P $所计算出的维度数是根据总体方差及估计精度来确定。该值可用于分析维度的数量以及衡量维度的粒化标准。

以上2个阶段实现了用最低的成本完成大量规模数据集粒化的目标，且相比单一的权重选择算法^[27]能较好地捕获特征维度间的相关性。DGA策略在一定程度上提高了算法的粒化效率，同时减少了数据集的维度数量，从而确保后续挖掘算法的可行性。因此，式（1）和式（2）作为维度粒大小的推理计算公式是合理的。

DGA算法实例：设论域$ U=\left\{{x}_{1}, {x}_{2}, \cdots , {x}_{6}\right\} $表示待处理的原始数据集，其中，$ A=\left\{{a}_{1}, {a}_{2}, {a}_{3}, {a}_{4}\right\} $为论域$ U $上的数据属性，将属性评价分为1、2、3、4、5类，分别表示优、良、中、合格、差，如表 1所示。

对于$ \forall {a}_{i}\in A $，属性$ {a}_{1} $包含的维度粒为：$ {A}_{1}=\left\{({a}_{1}, 1), ({x}_{1}, {x}_{4}, {x}_{6})\right\}, \left\{({a}_{1}, 2), ({x}_{2}, {x}_{5})\right\}, \left\{({a}_{1}, 3), \left({x}_{3}\right)\right\} $。属性$ {a}_{2} $包含的维度粒为：$ {A}_{2}=\left\{\left({a}_{2}, 1\right), \left({x}_{1}, {x}_{3}, {x}_{5}, {x}_{6}\right)\right\}, $ $ \left\{\left({a}_{2}, 5\right), \left({x}_{2}, {x}_{4}\right)\right\} $。属性$ {a}_{3} $包含的维度粒为$ {A}_{3}=\left\{\left({a}_{3}, 1\right), \left({x}_{1}, {x}_{2}, {x}_{3}, {x}_{4}, {x}_{5}, {x}_{6}\right)\right\} $。属性$ {a}_{4} $包含的维度粒为$ {A}_{4}=\{（{a}_{4}, 2）, （{x}_{2}, {x}_{3}, {x}_{5}）\}, $$ \left\{\right({a}_{4}, 3), ({x}_{4}\left)\right\}, \left\{\right({a}_{4}, 4), ({x}_{1}, {x}_{6}\left)\right\}\mathrm{。} $因此，可得数据集中的数据点个数$ N=6 $，属性$ {a}_{1}\mathrm{、}{a}_{2}\mathrm{、}{a}_{3}\mathrm{、}{a}_{4} $包含的维度粒均值分别为$ {n}_{1}=2, {n}_{2}=3, {n}_{3}=6, {n}_{4}=2, \mu =3.25 $，其均方差$ {S}_{i} $分别为$ 1.25\mathrm{、}0.25\mathrm{、}1.66\mathrm{、}1.25 $，可得属性精确度$ {d}_{i} $分别为$ 0.38\mathrm{、}0.08\mathrm{、}0.51\mathrm{、}0.38 $。由定义5可知，属性精度均值$ \gamma =0.337 \ 5 $，总维度数$ D=5 $，维度粒大小$ P\approx 2 $。因此，经计算后得到的属性$ \left\{1\right\}\mathrm{、}\left\{2\right\} $为数据特征属性维度粒化结果。

3.1.2 GPL算法

通过DGA算法完成特征属性维度的精确捕捉后，能够进一步提高分组效率。GPL算法在粒化后的数据集中执行一次MapReduce任务。基于DGA算法所得的粒大小，本文根据属性的前缀长度设计了负载估计策略LE，用于估算该粒所对应的结构路径长度，并进行负载均衡化分组，以确保每组分配到相同的负载量，从而实现整体的负载均衡，负载估计策略LE定义如下。

定义7（负载估计策略LE）   已知$ k $为节点在$ N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $中的位置，$ i $为维度粒大小的取整结果，则该节点路径长度的计算如式（3）所示：

$ L\left(p\right)=i\times {2}^{k-1} $

(3)

证明  对于频繁项$ \mathrm{i}\mathrm{t}\mathrm{e}\mathrm{m} $而言，假设其在$ N-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $中的位置为$ k $，其中最差的结果是$ \mathrm{i}\mathrm{t}\mathrm{e}\mathrm{m} $前任意$ k-1 $项的组合在该PJPFP-Tree树中均有相应的路径，该路径中含有$ \mathrm{i}\mathrm{t}\mathrm{e}\mathrm{m} $项，且此时的路径最多有$ {2}^{k-1} $条，空间数据库中路径数与维度数成正比，因此，式（3）作为路径长度估计函数是合理的。

DGPL策略的原理是根据DGA算法实现高维特征数据的维度粒化，得到属性精确度及数据可分析性均较高的特征属性捕捉结果，从而克服高维数据挖掘算法的局限性。针对粒化后的空间数据集，DGPL策略通过GPL算法对频繁1-项集进行均匀分组，生成P-list列表，实现了节点的均匀分布。

算法1   DGPL策略

输入  频繁1-项集$ N $-$ \mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $，维度数$ i $，分组数$ G $

输出  分组列表$ P $-$ \mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $

    计算$ P-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $中每一项的负载量

1.Foreach item in $ \mathrm{N}-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $ do

2.Compute $ \mathrm{i}\mathrm{t}\mathrm{e}\mathrm{m}\_\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d} $ by Eq.（3）

$3.\mathrm{P}-3.\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}=\mathrm{P}-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}\bigcup < \mathrm{k}\mathrm{e}\mathrm{y}=\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{m}, \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}=\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{m}.\mathrm{l}\mathrm{o}\mathrm{a}\mathrm{d} > $

4.End for

5.Sorted（$ \mathrm{P}-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $）//将$ \mathrm{P}-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $按照value值递减顺序排序

6.Return $ \mathrm{P}-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $

7.Function $ \mathrm{g}\mathrm{e}\mathrm{t}\mathrm{P}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}(\mathrm{P}-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}, \ \mathrm{G}) $

8.Return $ \mathrm{P}-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $

3.2 PARM策略

为进一步减少数据库的扫描次数和不必要的计算消耗，本文提出PARM策略以生成本地模式基表树，从而缓解因数据交互次数增多带来的负载压力。虽然PWARM算法^[28]省去了FP-Tree树和Head表的构建过程，但在Reduce阶段仍需统计Map阶段输出的项集加权支持度。该算法因磁盘I/O次数的增加导致计算速度缓慢，从而大幅降低挖掘效率。此外，基于给定项目属性权重的方法，在项目集不断更新过程中无法衡量项目权值，因此，在数据集研究过程中降低挖掘精度且增加了数据集的维护代价。PARM策略在构造完成P-list列表后，映射存储该列表中的频繁1-项集至本地，再正常调用MapReduce过程。

根据FP-growth原理，PARM策略对$ F $$ - $$ \mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $列表中的每个项集进行映射，映射规则为：设频繁1-项集$ {x}_{1}=\left\{a\right\}，{x}_{2}=\left\{d\right\}，{x}_{3}=\left\{b\right\}，{x}_{4}=\left\{e\right\}，{x}_{5}=\left\{c\right\} $，其支持度分别为7、8、5、5、4。由于列表会重复存储大量的不频繁项，并且读取一个完整事务时需遍历整个列表才能得到目标项集，这样会占用大量的存储空间且消耗大量的时间。因此，根据FP-growth原理，本文设计类似FP-Tree的树形数据结构PJPFP-Tree树。该树在Reduce阶段通过与$ P $$ - $$ \mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $列表映射构造得出，此步骤避免统计Map阶段输出集合的过程，并相对提高算法的性能。

定义8（PJPFP-Tree树）  是具有$ N(N\ge 0) $个节点的有限集合，当N=0时，称为空树。在任意一棵非空树中应满足以下2个条件：1）有且仅有一个名为null的节点作为根；2）当N > 1时，其余每1个节点均由频繁1-项集节点名称（Frequent 1-Itemset）和该节点支持度两部分组成。

该树作为一种逻辑结构，同时也是一种$ M(M=2) $层的分层结构，具有以下2个特点：1）该树的根节点没有前驱节点；2）树中除根节点外的其他所有节点仅以根节点为其前驱节点，且此类节点均没有后继节点。

生成PJPFP-Tree树的目的是在本地磁盘中加快频繁1-项集的合并速度，使其作为挖掘局部2-项集的本地模式基，同时大规模减少数据交互频度，从而缓解负载压力。相比PWARM算法的挖掘过程，PARDG-MR算法中的并行化实现仅基于频繁项集挖掘过程中的Reduce阶段，根据分组完成后的$ P-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $列表及在频繁项集生成过程中，该阶段构造得到本地频繁模式基PJPFP-Tree树，并有效利用分组完成后的数据，避免内存溢出。该过程不存在冗余步骤，为大数据环境下高维数据的挖掘应用提供了优势。

3.3 PJPFP策略

在大数据背景下生成的FP-Tree树规模较大，导致大部分算法忽略了在FP-Tree树中进行项集剪枝时带来的内存耗费，从而造成不完全剪枝，且频繁项集紧凑化程度低。因此，在利用PARM策略构造完成本地PJPFP-Tree树后，本节提出PJPFP策略，将PJPFP-Tree树中的频繁2-项集结果作为挖掘局部2-项集的本地模式基，该策略既考虑了减少再次扫描数据集的时间成本，又使得后续生成的项集中不存在非潜在候选3-项集。

PJPFP策略主要分为2个步骤：1）提出剪枝前缀推论PPL，同时利用PPL删除可能产生频繁2-项集的频繁1-项集，并在后续剪枝过程中将该推论作为$ (k-1) $项集阶段的剪枝标准，进而达到后续被整合的节点中不包含非潜在候选k-项集的目的；2）基于上述挖掘结果，根据频繁模式的支持度对其进行降序排列。

定义9（剪枝前缀推论PPL）  如果项集$ \left\{\alpha , \beta , \gamma \right\} $为非频繁项集，则以其为前缀的所有项集均为非频繁项集。

证明  根据剪枝定理可知，$ \exists \alpha \in X\bigcap \beta \in X\bigcap $ $ \alpha \ne \beta $，如果2-项集$ \left\{\alpha , \beta \right\} $不是频繁项集，则项集$ X $也一定是非频繁项集，即若$ \left\{\alpha , \beta , \gamma \right\} $为非频繁项集，则以项集$ \left\{\alpha , \beta , \gamma \right\} $为前缀的子集或超集，均是非频繁项集。

为更清晰地描述该推论，本节给出数据集I，1-项集和2-项集的支持度如表 2所示。

根据表 1的数据集统计结果，令数据集I的支持度$ \mathrm{m}\mathrm{i}\mathrm{n}\_\mathrm{s}\mathrm{u}\mathrm{p}=3 $。根据本节提出的剪枝推论PPL可推论得出应同时删除项目F，其他项目按降序排列，可得结果$ I'=\{D，A，B，E，C\} $。执行过程代码如下：

输入  数据集$ \mathrm{I} $，$ P-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $，$ \mathrm{m}\mathrm{i}\mathrm{n}\_\mathrm{s}\mathrm{u}\mathrm{p} $

输出  剪枝后的$ P-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t} $

1.Foreach $ \mathrm{t} \ \in \ \mathrm{I} ${

$ 2.{\mathrm{t}}'=\mathrm{s}\mathrm{o}\mathrm{r}\mathrm{t}(\mathrm{t} \ , \ \mathrm{I}') $

3.$ \mathrm{F}\mathrm{o}\mathrm{r} \ (\mathrm{i}=0;\mathrm{i} < \left|{\mathrm{I}}'\right|;\mathrm{i}++) $

4.$ \mathrm{F}\mathrm{o}\mathrm{r} \ (\mathrm{j}=\mathrm{i}+1;\mathrm{j} < \left|{\mathrm{I}}'\right|;\mathrm{j}++) $

5.$ \mathrm{I}\mathrm{f}\left(\mathrm{D}\right[{\mathrm{t}}_{\mathrm{i}}\left]\right[{\mathrm{t}}_{\mathrm{j}}] > =\mathrm{m}\mathrm{i}\mathrm{n} \ \_\mathrm{s}\mathrm{u}\mathrm{p}) $

6.$ \mathrm{F}\mathrm{o}\mathrm{r}\left(\mathrm{k}=\mathrm{j}+1;\mathrm{j} < \left|{\mathrm{I}}'\right|;\mathrm{k}++\right) $

7.$ \mathrm{I}\mathrm{f}\left(\mathrm{D}\right[{\mathrm{t}}_{\mathrm{i}}\left]\right[{\mathrm{t}}_{\mathrm{k}}]\ge \mathrm{m}\mathrm{i}\mathrm{n} \ \_\mathrm{s}\mathrm{u}\mathrm{p} \ \ \ \ \ \mathrm{A}\mathrm{N}\mathrm{D} \ \mathrm{D}[{\mathrm{t}}_{\mathrm{j}}\left]\right[{\mathrm{t}}_{\mathrm{k}}]\ge \mathrm{m}\mathrm{i}\mathrm{n} \ \_\mathrm{s}\mathrm{u}\mathrm{p}) $

8.$ \mathrm{W}\mathrm{h}\mathrm{i}\mathrm{l}\mathrm{e} \ \left(\mathrm{D}\right[{\mathrm{t}}_{\mathrm{k}-1}\left]\right[{\mathrm{t}}_{\mathrm{k}}] < \mathrm{m}\mathrm{i}\mathrm{n} \ \_\mathrm{s}\mathrm{u}\mathrm{p}) $

$ 9.{\mathrm{t}}_{\mathrm{k}-1}={\mathrm{t}}_{\mathrm{k}-1}.\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t} \text{；} $

$ 10.{\mathrm{t}}_{\mathrm{k}-1}={\mathrm{t}}_{\mathrm{k}}.\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t} \text{；} $

$ 11.{\mathrm{t}}_{\mathrm{k}}.\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}++; $}

3.4 PARDG-MR算法

PARDG-MR算法主要分为以下4个步骤。

步骤1  输入原始数据，通过式（1）和式（2）确定维度粒的大小，完成数据特征属性的精确捕捉。

步骤2  执行MapReduce任务，根据式（3）计算属性前缀长度，实现负载均衡分组，生成包含频繁1-项集的P-list列表。

步骤3  通过PARM方法将P-list列表中的频繁1-项集作为PJPFP-Tree树的频繁2-项集模式基。

步骤4  利用PJPFP策略实现后续频繁项集的紧凑化，从而完成全局频繁项集的挖掘。

3.5 算法的复杂度分析 3.5.1 时间复杂度分析

PARDG-MR算法由频繁1-项集的均匀分组、生成本地频繁模式基PJPFP-Tree树和频繁项集的并行挖掘过程3个部分组成，因此将本文算法3个阶段的时间复杂度分别记为$ {T}_{{c}_{1}} $、$ {T}_{{c}_{2}} $和$ {T}_{{c}_{3}} $。

在对高维数据进行特征属性捕捉及获得频繁1-项集P-list的过程中，本文算法需要获得各个记录的数据项中每个维度的属性值，例如每条项集包含的维度数是N，记录数是M，即在每条项集维度属性值获取过程中的时间复杂度为：

$ {T}_{{c}_{1}}=O(N\times M) $

在对频繁1-项集进行均匀分组，生成本地频繁模式基PJPFP-Tree树时，该步骤仅需在本地完成即可。因此，假设P-list的长度为P，目标分组产生的数量为N，则该阶段的时间复杂度为：

$ {T}_{{c}_{2}}=O(L/G) $

在频繁项集的并行挖掘过程中，时间复杂度的计算主要包含同一前缀的频繁（k-1）-项集合并成频繁k-项集的过程。假设频繁1-项集$ P-\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}=\{{I}_{1}，{I}_{2}，\cdots ，{I}_{n}\} $，以项$ {I}_{i} $作为结尾的频繁（k-1）-项集的结构长度为$ {L}_{i} $，则其时间复杂度为：

$ {T}_{{c}_{3}}=O\left(\sum \sum {L}_{a}+{L}_{b}\right)，a, b\in (0, l) $

因此，PARDG-MR算法的时间复杂度为：

$ {T}_{\mathrm{P}\mathrm{A}\mathrm{R}\mathrm{D}\mathrm{G}-\mathrm{M}\mathrm{R}}=O\left(N\times M+\frac{L}{G}+\sum \sum \left({L}_{a}+{L}_{b}\right)\right) $

在PWARM算法中，第一阶段的时间复杂度基本一致，但在后续分组过程中需要多次扫描数据库，依次比较列表间的元素，可得其时间复杂度为：

$ {T}_{\mathrm{P}\mathrm{W}\mathrm{A}\mathrm{R}\mathrm{M}}=O\left({\left(N\times M\right)}^{2}+\sum \sum ({L}_{a}\times {L}_{b})\right) $

在大数据环境中，$ {T}_{{c}_{1}} $、$ {T}_{{c}_{2}} $相比于$ {T}_{{c}_{3}} $的值较小，甚至可以忽略不计，并且一般情况下的频繁（k-1）-项集的长度远大于2，即$ {T}_{\mathrm{P}\mathrm{A}\mathrm{R}\mathrm{D}\mathrm{G}-\mathrm{M}\mathrm{R}}\gg {T}_{\mathrm{P}\mathrm{W}\mathrm{A}\mathrm{R}\mathrm{M}} $。因此，PARDG-MR算法的时间复杂度会低于PWARM算法。

3.5.2 空间复杂度分析

PARDG-MR算法的空间复杂度是通过计算频繁项集、P-list列表和频繁模式基树存储所需空间的总和。其中，采用模糊属性维度粒化方法使得各个节点的任务量基本相同，使得频繁项集列表结构规模大致相似。假设每个分组结果中平均有$ {g}_{k} $个频繁k-项集，其中每个频繁k-项集均占$ {b}_{1} $ Byte，故频繁k-项集P-list的长度均值为$ {L}_{k} $。频繁k-项集的每个P-list结构占$ {b}_{2} $ Byte，因此P-list结构的空间复杂度为$ O\left(\sum\limits _{i=1}^{k}({g}_{i}\times {b}_{1}+{L}_{i}\times {b}_{2})\right) $，然而模式基树存储所需要的空间只由频繁1-项集决定，其空间复杂度为$ O({b}_{1}\times {L}_{k}!) $，则PARDG-MR算法的空间复杂度为：

$ {M}_{\mathrm{P}\mathrm{A}\mathrm{R}\mathrm{D}\mathrm{G}-\mathrm{M}\mathrm{R}}=O\left(\sum\limits _{i=1}^{k}\left({g}_{i}\times {b}_{1}+{L}_{i}\times {b}_{2}\right)+{b}_{1}\times {L}_{k}!\right) $

PWARM算法在构建加权FP-Tree树时，通常会导致每组节点间存在不均衡负载的问题，且在算法的复杂度评估过程中一般选取最差的结果作为衡量算法复杂度的指标。因此假设分组结果中节点最多有$ {g}_{\mathrm{m}\mathrm{a}\mathrm{x}} $个频繁k-项集，则PWARM算法的空间复杂度为：

$ {M}_{\mathrm{P}\mathrm{W}\mathrm{A}\mathrm{R}\mathrm{M}}=O\left(\sum\limits _{i=1}^{k}{g}_{\mathrm{m}\mathrm{a}\mathrm{x}}\times ({b}_{1}+{b}_{2}\times {L}_{i})\right) $

在大数据背景中，加权FP-Tree树的构建远大于P-list列表和模式基树所占的存储空间，因此，PARDG-MR算法的空间复杂度小于PWARM算法。

4 实验与结果分析 4.1 实验环境

本文实验硬件方面包含4个节点，其中1个主节点，3个辅助节点。4个节点的CPU来自AMD Ryzen 7，其中CPU包含8个处理单元，内存均是16 GB。实验采用的4个计算节点都属于同一局域网，均由200 Mb/s的以太网互相连接。在软件方面，计算节点安装的均是2.7.4版本的Hadoop以及1.8.0版本的JDK，其所用的操作系统是Ubuntu 16.04版本。各节点的配置如表 3所示。

4.2 实验数据集

PARDG-MR算法使用的3个实验数据集均来自标准数据库，分别为Gisette数据集、NDC数据集和Webdocs数据集，数据集信息如表 4所示。其中Gisette数据集中包含手写数字识别问题的数据，该数据集样本数量为6 000，其特征数为5 000，具有数据量小、特征维度大的特点；NDC数据集中均为正态分布集群数据，该数据集样本容量为100 000，维度为32，具有数据量大、特征维度适中的特点，具有较强的代表性；Webdocs数据集中包含1 692 082条Web文档数据，每条数据包含5 267 656条不同属性，是一组数据量大、特征维度较大的数据集合。

4.3 评价指标

为评估PARDG-MR算法的运算效率，本文采用加速比作为算法性能的衡量指标。加速比^[29]是指在相同任务量的情况下，使用单一处理器进行运算与使用多个处理器运算所消耗时间的比值。加速比较大，则说明算法在并行计算过程中所消耗的时间越少，挖掘效率越高。

4.4 PARDG-MR算法可行性分析

本节通过对比算法的加速比，验证PARDG-MR算法挖掘执行的可行性。本文分别选取最小支持度阈值为1 000、3 000和5 000，在不同的支持度阈值下将PARDG-MR算法分别应用在数据集上，并单独执行15次，获得15次结果的平均值。在不同数据集上PARDG-MR算法的加速比对比如图 2所示。

从图 2可以看出，在支持度不小于3 000的情况中，PARDG-MR算法在数据量大、维度数高的数据集环境上执行时，会产生较高的加速比；相反，在类似NDC的小数据集中执行时，其加速比增量趋于平稳，而在Webdocs的大规模数据集上执行时，随着节点数量的增加，加速比呈上升趋势。当支持度值为5 000时，PARDG-MR算法在同一数据集各节点的加速比相较于该数据集中前一节点的加速比分别提升了0.91和0.99，其原因是在数据量较小、数据维度较低时，现有的数据量不能将集群处理的数据量最大化，此时将数据划分至各节点反而会增大时间开销。然而在大数据环境下，算法优化的关键在于能够完成数据集有效降维以及频繁项集准确合并，在一定程度上能够减少算法在数据集中的扫描次数，并提高算法整体的挖掘性能。在大规模高维度数据集上，PARDG-MR算法的挖掘加速比差距接近最大值1，说明该算法具有较强的全局挖掘潜力。实验结果表明，PARDG-MR算法能够适用于大数据背景中高维数据频繁项集的挖掘。

4.5 挖掘性能对比

本文分别在3个实验数据集上进行多次对比实验，在算法挖掘过程中将其与PWARM、PFP-growth、MRPrePost算法的运行时间分别进行对比。

为验证PARDG-MR算法的有效性，本文分别在Webdocs、Gisette、NDC这3个数据集上将PARDG-MR、PWARM、PFP-growth、MRPrePost算法的运行时间进行对比，如图 3所示。在独立运行15次后对其平均值进行分析，通过对比运行时间，评估PARDG-MR算法的性能。

从图 3可以看出，相比PFP-growth和PWARM算法，PARDG-MR算法在3个数据集上的整体执行时间均有不同程度的减少，其性能表现最佳。在NDC数据集上PARDG-MR算法的运行时间下降幅度最大，相比Webdocs数据集和Gisette数据集，其运行时间分别下降了20%和64%。在Gisette数据集上PARDG-MR算法的运行时间下降幅度持续稳定，保持为6%。相比PWARM算法在NDC数据集中3种支持度下的执行时间，PARDG-MR算法分别减少了28%、24%和38%。相比PFP-growth算法在Gisette数据集中3种支持度下的执行时间，PARDG-MR算法分别减少了28%、17%、15%。执行时间减少的原因在于PARDG-MR算法在进行频繁项集挖掘的分组过程中先进行了负载均衡化，并且在构建频繁模式基树时，将冗长的项集结构通过合并方法转化为辨识度较高的树结构，从而大幅缩短了运算时间。PWARM算法在获得频繁项集的过程中首先生成了加权FP-tree树，同时生成加权节点，该过程消耗了大部分时间；而PFP-growth算法在生成频繁项集的过程中需要多次扫描数据集，通过递归的形式构建频繁模式树，从而产生大量的计算开销。由于PARDG-MR算法的运行时间在NDC数据集上的下降幅度最大，该算法对于数据量大、维度高的数据适应能力最强，其在降低数据维度规模的同时利用频繁模式基结构加速节点的合并，避免了无效计算，在一定程度上提高了算法的挖掘执行效率，且降低了算法的运行时间。

5 结束语

本文提出基于维度粒化的并行挖掘算法。通过设计DGPL策略对高维数据进行预处理，以解决高维数据特征属性捕捉困难以及节点负载不均匀的问题。为进一步提升运行效率，提出PARM策略，在本地映射频繁1-项集列表上构建生成本地PJPFP-Tree树，以加快节点合并速度、减少数据交互频度并降低负载压力。在此基础上，将频繁2-项集作为完全剪枝的剪枝条件，构建PJPFP策略，从而增强频繁项集紧凑化程度，同时降低内存消耗。在Webdocs、NDC、Gisette 3个数据集上的实验结果验证了PARDG-MR算法的有效性，相比PFP-growth、PWARM等算法，PARDG-MR算法的挖掘效果更佳，能够提高挖掘效率。后续将利用维度间的相关性保留用户更感兴趣的关联规则信息，以提高数据挖掘结果的实用性。