利用数据变换与并行运算的闭频繁项集挖掘方法*

党红恩，　赵尔平，　刘　炜，　雒伟群

(西藏民族大学 信息工程学院，陕西 咸阳 712082)

海量信息的爆发式增长已成为当今世界最主要的特点.在这些形式各异、容量极大的数据中，如何准确提取关键信息，帮助各类决策者了解、掌握瞬息变换的客观世界，是非常重要的[1].信息技术和硬件技术的快速进步，已经使得用户生产并处理海量的事务数据(即大数据)成为可能，大数据处理的核心就是数据挖掘技术[2].然而，在物理世界中不断涌现的闭频繁项集(closed frequent itemset, CFI)加大了大数据挖掘的难度，降低了数据挖掘结果的实时性和可靠性.

闭频繁项集的概念最早见于文献[3]，此后出现了大量的闭频繁项集挖掘算法[4-7].在处理小数据集或高支持阈值的CFI挖掘问题时，现有的方法表现出了良好的性能.这些算法通过将搜索空间限制在闭频繁项集而不是整个集合的幂集，将寻找频繁项集简化为挖掘闭频繁项集.但是，当数据集范围增大或支持度阈值变低时，内存占用和通信成本的急剧增大使得现有方法的可行性和运行速率变低.一些研究试图通过并列运行的方式加快CFI挖掘算法的速度，但却产生了一些如数据划分和通信成本最小化等问题，需要进一步改进.然而，不可否认的是，并行方案确实是一种解决CFI大规模挖掘的行之有效的方法.目前，针对闭频繁项集并行挖掘算法的研究相对较少.[8]基于MapReduce平台的CFI，提出一种基于贪婪策略的CFI并行平衡挖掘算法，并通过实验证明了所提算法在大规模CFI挖掘中的可靠性和快速性.[9]提出了一种充分利用频繁模式增长算法固有并行特征的多处理器顺序展开结构，实验结果表明提出的结构可以大幅度提高运算速度.[10]提出一种运行于多核处理器上的SAT并行算法，通过路径指引来分解枚举过程，大大提高了CFI挖掘的动态性能.

为充分利用并行框架Spark在计算和存储等方面的优势，本文提出一种基于数据变换与并行运算(data transformation and parallel computing, DTPC)的CFI挖掘方法：利用平方和开方运算将数据集的项转化为质数，进而成频繁项集.利用3 000万篇文章组成的大数据集进行了相关实验，实验结果证明本文算法在可靠性、准确性和动态响应速度等方面大大优于现有的算法.

1　DTPC算法

本文提出的DTPC闭频繁项集挖掘方法包括两个步骤：第一步，进行数据转换，生成频繁项列表，并在Spark中进行降序排列；第二步，在Spark中挖掘闭频繁项集.在介绍本文具体算法之前，先对闭频繁项集的一些相关概念进行简单的介绍.

定义1提取上下文：指一个三元组κ=(O,I,R)，式中O表示对象的有限集合，I为项的有限集合，R为二元(关联)关系(即R⊆O×I)，每对(o,i)∈R表示对象o∈O包含项i∈I.

定义2闭项集：项i∈Ι是闭环的，当且仅当I″=I；S(I)代表i的支持，其值等于κ中包含i的项数；如果S(i)比S(I)的最小值大，则认为i是频繁的.

定义2中，(″)表示闭包算子，由ψ:P(i)→P(O)s.t.ψ(i)={o∈O|∀i∈I,(o,i)∈R}和φ:P(O)→P(i)s.t.φ(O)={i∈I|∀o∈O,(o,i)∈R}共同定义.闭包算子将项的幂集分割成了互不相连的子集.

我们提出一种数据转换方法来生成频繁项列表，同时使用Spark[11]依据项支持的降序分类该列表.

定义3质数：一个整数Z>1是质数，当且仅当其仅能被自身和1整除.

在定义3和定义4的基础上，给出一种新型的数据变换方法(定义5)，用来将输入数据变换为频繁项集.

定义5事务转换：假设T={ij,…,ik}为事务，项ir∈T，通过将质数pr分配给每个项ir，并用方程

(1)

进行计算，可以完成数据转换过程，得到事务转换后的新数值VT.

表1数据变换示例

Tab.1Exampleofdatatransformation

表1给出了数据转换的示例，其中：表1(a)为提取上下文κ；表1(b)为κ中按照降序分类的项，以及这些项的质数和支持；表1(c)为上下文κ经数据转换后得到的结果.完成数据转换后，需要在Spark中提取闭频繁项集的完整集合，从而建立完整的DTPC闭频繁项集挖掘方法.

定义6条件上下文：给定提取上下文[12]κ，令i为κ中的频繁项，当省略了所有频繁项、项i和跟随i之后的项时，i的条件上下文定义为包含i的转换子集.令j为频繁项X的条件上下文中的一个频繁项，当省略了所有频繁项、项j和跟随j之后的项时，jX条件上下文定义为包含j的、X的条件上下文中的转换子集.

将频繁项按支持度的大小进行降序分类，对于每个i，DTPC只包含i的数据转换中的条件上下文.为了加快对这些子上下文的搜索，本文定义了与每个上下文关联的指示表，该表列举了按项支持度降序分裂的，包含在其相应条件上下文中的项.在本文算法中，提取闭频繁项集不需要使用此表.本文研究的项集X具有以下特征：(1) 从上下文中提取的闭项集X，是通过连接与X同样频繁的项发现的.(2) 无需设计包含在闭频繁项集的项集Y的条件上下文，来使S(X) =S(Y).

定理1(最大公约数闭包)令X条件上下文为包含X的转换集，X条件上下文中的最大公约数所有事务的闭包.

将项及其事务转换为质数后，通过计算条件上下文的所有事务的最大公约数，可以很简单地计算出闭包，而且这并不需要存储条件上下文包含的项的支持度.通过将闭包与连接候选项进行连接(即将该候选项的质数与闭包的数值相乘)，即可得到闭频繁项集.本文将该闭频繁项集表示为一个数，并将该数添加到最终得到的集合中.

综上，可得DTPC算法的具体步骤：(1) 对输入数据进行基于质数平方/开方的数据转化预处理；(2) 并行挖掘闭频繁项集，即利用并行最大公约数方法挖掘局部闭频繁项集；(3) 获取输出结果，即闭频繁项集.基于以上三步，即可以正确、快速地挖掘出闭频繁项集的完整集合.事实上，在预处理阶段后，DTPC已经开始基于Spark计算项的支持度，并将项按照支持度降序进行，得到相应的列表.在正式开始挖掘闭频繁项集时，DTPC算法使用第二个Spark,通过将上下文分割为一个新的数据集，并将其作为输入数据的条件上下文.此时，DTPC算法通过应用新的闭包操作，计算条件上下文之间所有事务的最大公约数，进而提取并获取闭环.

2　实验分析

为了验证提出的DTPC算法的有效性，本文在两个数据集上进行测试.第一个数据集为“Google Article”，表示将Google转换为事务数据集的转换集合，每一行为一篇文章.Google Article包含5 352 741个事务，合计4 305 928个不同的项目.在这些事务中，事务的最大长度为102 394，整个数据集的尺寸为3.2 GB.第二个数据集为“Clue Web”，包含10种语言、约10亿种网页，收集于2017年1月，该数据集包含43 783 550个事务、9 802 501个项，这些事务的最大长度为403 521，整个“Clue Web”的尺寸为19.5 GB.

采用高性能消息传递库OpenMPI[13]作为实验平台，选取15个节点的聚类进行实验：将一个节点选为主节点，负责在不同节点之间调度执行任务；将其他节点设置为从节点，负责并行计算.

为验证该算法的优越性，将DTPC算法与[14]和[15]中的算法进行比较，结果如图1所示.

图1(a)为最小支持度值小于数据库整体规模3%时，三种算法在“Google Article”上测试的实验结果.由实验结果可知，提出的DTPC算法明显优于其他算法.这是因为“Google Article”包含数量众多的项，项数几乎等于事物数.当最小支持度的值足够低时，文献[14]、[15]中的两种算法都会生成许多的候选者和条件上下文.因此，在这两种算法中所使用的方法非常复杂，进而导致挖掘性能变差.DTPC算法基于质数，通过简单的平方/开方运算即可生成条件上下文，因而计算起来非常简便.此外，每个条件上下文中的最大公约数消除了候选者和其闭包之间的支持度检验，从而省略了闭包频率的计算.

图1(b)为在“Clue Web”上的实验结果，通过减少最小支持度值，闭频繁项数变化并不明显；匹配候选者事务的数量却快速增加，这样会导致项集的候选者生成较大的条件上下文.然而，在这种情况下，本文提出的DTPC算法仍能获得较好的计算性能，这是因为本文的算法避免了从每个条件上下文中产生闭包的冗余计算，而文献[14]、[15]中的两种算法则不具备这种能力.

[1]赵海燕, 王向前, 马艺. 量子密码学结合Grover搜索的大数据安全认证方案[J]. 湘潭大学自然科学学报, 2016, 38(4): 76-79.

[2]史玉珍, 吕琼帅. 基于进化模糊规则的Web新闻文本挖掘与分类方法[J]. 湘潭大学自然科学学报, 2016, 38(2): 99-103.

[3]PASQUIER N,BASTIDE Y,TAOUIL R, et al. Discovering frequent closed itemsets for association rules[J]. Lecture Notes in Computer Science, 1999, 1540: 398-416.

[4]SUTHA M J,DHANASEELAN F R. An efficient method for detection of breast cancer based onclosed frequent itemsets mining[J]. Journal of Medical Imaging & Health Informatics, 2015, 5(5): 45-56.

[5]TAN J. Efficient data streams based closed frequent itemsets mining algorithm[J]. Applied Mechanics & Materials, 2013, 256-259: 2910-2913.

[6]LUCCHESE C,ORLANDO S,PEREGO R. Fast and memory efficient mining of frequent closed itemsets[J]. IEEE Transactions on Knowledge & DataEngineering, 2006, 18(1): 21-36.

[7]王黎明, 张卓. 基于iceberg概念格并置集成的闭频繁项集挖掘算法[J]. 计算机研究与发展, 2007, 44(7): 1184-1190.

[8]CHEN G P,YANG Y B,ZHANG Y. MapReduce-based balanced mining for closed frequent itemset[C]//International Conference on Web Services, 2012: 652-653.

[9]IONESCU C M,COPOT D,COPOT C, et al.Parallel architecture for implementation of frequent itemset mining using FP-growth[C]//International Conference on Signals and Systems, 2017: 92-98.

[10]DLALA IO,JABBOUR S,SAIS L, et al. Parallel SAT based closed frequent itemsets enumeration[C]//IEEE/ACS 12th International Conference of Computer Systems and Applications, 2015: 1-8.

[11]陈洁, 褚龙现, 夏栋梁. 一种支持并行处理的矢量数据存储与查询方法[J]. 电子设计工程, 2017, 25(10): 31-33.

[12]HAN J,PEI J,YIN Y, et al. Mining frequent patterns without candidate generation: a frequent-pattern tree approach[J]. Data Mining & Knowledge Discovery, 2004, 8(1): 53-87.

[13]PERKS O,BECKINGSALE D A,DAWES A S, et al. Analysing the influence of InfiniBand choice on OpenMPI memory consumption[C]//International Conference on High Performance Computing and Simulation, 2013: 186-193.

[14]唐颖峰, 陈世平. 一种基于后缀项表的并行闭频繁项集挖掘算法[J]. 计算机应用研究, 2014, 31(2): 373-377.

[15]李海峰. 基于GPU的闭合频繁项集挖掘方法[J]. 计算机工程, 2011, 37(14): 59-61.