并行挖掘频繁项目集新算法

摘要：基于列存储的Eclat算法比基于行存储的频繁项目集挖掘算法如Apriori和FPGrowth等算法挖掘效率更高。

针对Eclat算法在挖掘海量数据中的频繁项目集时存在的内存和计算资源不足等问题，提出了基于Map/Reduce计算模型的并行挖掘算法――MREclat。首先，将水平型数据库转换成垂直型数据库；然后，将转换后的数据按2项集的前缀分发到各个计算节点上，且在分发数据时引入了均衡策略；接着，在各个计算节点上求出以某一前缀开头的所有频繁项目集；最后，合并各个节点的结果得到所有频繁项目集。介绍了MREclat的设计思想，研究了算法的运行性能。实验结果表明，MREclat算法效率大约是PEclat算法的2倍，加速比性能比PEclat算法提高了64%。

关键词：频繁项目集；并行挖掘算法；列存储；Map/Reduce；Eclat算法

中图分类号： TP311.13

文献标志码：A

Abstract： Eclat algorithm mines frequent itemsets from vertical layout databases. It is more efficient than those algorithms based on horizontal layout databases， such as algorithm Apriori and FPGrowth.

Aiming at the problem that the memory and computational capability is insufficient while using Eclat algorithm to mine frequent itemsets from massive dataset， a parallel mining algorithm based on Map/Reduce framework， called MREclat（MapReduce Eclat）， was proposed. Firstly， MREclat algorithm converted the horizontal database into a vertical one. Secondly， it redistributed the converted dataset according to the first item of each frequent 2itemset and loadbalance was taken into consideration while distributing datasets. Then， all the frequent itemsets prefixed by the same item were computed in each computing node. Finally， MREclat algorithm collected the result of each computing node and generated the whole frequent itemsets. In this paper， the idea of MREclat was introduced and the performance of the algorithm was studied. The experimental results show that MREclat algorithm is twice as efficient as PEclat algorithm， and the speedup performance of MREclat algorithm is 64% higher than that of PEclat.

Key words： frequent itemset； parallel mining algorithm； columnstore； Map/Reduce； Eclat algorithm

0引言

频繁项目集挖掘是数据挖掘领域的重要研究内容，它同时广泛应用于如购物篮分析、网络入侵检测和疾病诊断等领域。频繁项目集挖掘算法根据其所挖掘的数据源呈现形式分为两类：1）基于水平型（即事务型）数据库的算法，所谓水平型是指每条记录在磁盘中按行存储。这类算法中最典型的就是Apriori算法[1]和FPGrowth（Frequent Pattern Growth）算法[2]，这类算法常需要多次扫描数据库。2）基于垂直型数据的算法，垂直型的本质是记录在磁盘上以列存储方式存储。Eclat算法[3]是这类算法中的代表，它只需扫描数据库一次。在列存储的数据库中，数据库管理系统（Database Management System， DBMS）只需读取那些跟查询相关的列，避免了读取不必要的列。而在行存储的数据库中，一次查询往往需要遍历大量的数据记录，因此垂直型数据库在处理数据库“读取”操作上具有较好的优势。实验结果[3-5]显示Eclat算法运行效率高于第一类的算法。

近年来，随着信息社会的飞速发展，人们拥有和积累的数据越来越多。在某些领域如天文、地理、气象、智能商业以及互联网等领域，它们所积累的数据已经达到PB级，这预示着“大数据”[6]时代的来临，如何从“大数据”中有效地挖掘出有价值的信息，成为目前的研究热点。传统的串行算法已不能满足人们处理数据的需求，目前以“云计算”为代表的并行和分布式计算为从大数据中挖掘信息提供了可能。

Eclat算法具有良好的执行效率，因此将其并行化具有较高的可行性和研究价值。目前，频繁项目集的并行策略主要有CD（Count Distribution）、CaD（Candidate Distribution）和DD（Data Distribution）[7]等，但这些策略在通信和同步方面需要大量的额外开销。Zaki等[8]提出了多种基于MC（Memory Channel）的Eclat并行算法，由于这些方法均需将数据加载进入内存，导致其在对大数据进行频繁项目集挖掘时缺乏可行性。基于Map/Reduce计算模型的Eclat并行化研究文献目前较少，文献[9]提出了基于Map/Reduce的Eclat并行算法――PEclat（Parallel Eclat）算法。该算法需要多次迭代运行Map/Reduce任务，导致性能较低，同时算法没有考虑负载均衡等问题。本文提出了一种基于前缀分组的并行挖掘算法――MREclat（MapReduce Eclat），它将项目按前缀进行分组，在分组的过程中考虑了负载的均衡性。实验结果表明，MREclat算法有着较好的可扩展性和加速比，且比文献[9]的PEclat算法效率更高。

1.2行存储和列存储

目前，数据存储有两种方案可供选择：行存储和列存储。在行存储的架构中，磁盘将一条记录的所有字段的数据聚合存储，行存储所对应的数据库称为水平型数据库[3]。行存储架构的数据库在执行“写”操作时具有较高的性能，在类似于OLTP（OnLine Transaction Processing）的应用中具有较好的应用效果；与此相对的，列存储将同一字段的数据聚合存储。与行存储相比，列存储有以下两个优点：1）每个字段的数据聚集存储，在查询只需要少数几个字段的时候，能大幅度减少读取的数据量；2）可以为列存储设计出压缩/解压算法，来减少数据的存储量[10]。在频繁项目集挖掘概念中，将行存储所实现的数据库称为水平型数据库，水平型数据库的每个元组（又称事务）由事务唯一标识符（TID）和项目（item）组成，一条事务可以包含一个或多个项目。列存储所对应的数据库称为垂直型数据库，垂直数据中每个记录由项目集和所有包含该项目集的事务标识组成。传统的频繁项目集挖掘算法如Apriori和FPGrowth算法针对水平型数据表示，它们往往需要多次扫描数据库以完成对项目集频繁的统计。Eclat是一种典型的基于垂直数据的频繁项目集挖掘算法，它只需扫描数据库一次就能完成频繁项目集求解。

1.4Map/Reduce框架

Map/Reduce[12]是Google提出的一种用于处理大规模数据集的并行编程模型，它是无共享软件架构的典型实现。它采用“Divide & Conquer”思想，把对大规模数据的操作分发到一个主节点管理下的各分节点共同完成，然后通过整合各分节点的中间结果，得到最终结果。它把所有的运算过程，高度抽象成map和reduce这两个函数，所以用户不必考虑如工作调度、容错处理、网络通信、负载平衡等细节。

Map/Reduce程序在执行过程时首先把数据集分成若干固定大小的独立数据块（block），同时为每个数据块保存多个副本。Map/Reduce在每个数据块上运行一个独立的Mapper任务，由于每个数据块的大小固定，因此运行的Mapper数由数据源大小决定。Mapper将输入的每个元组通过map函数转换成〈key，value〉形式的键值对并输出，所有的键值对根据其key的值被Hash分送到不同的Reduce运算节点上。由于所有的Mapper采用相同的Hash函数，key值相同的键值对会被分送到同一个Reduce节点，同时，同一个Reduce节点可能会收到多个不同key值的键值对（它们Hash后值相同）。在每个Reduce计算节点上运行一个Reducer任务用于处理Mapper发送过来的数据，Reducer的reduce函数每次将一个key值对应的所有键值对转换成新的键值对，Reducer的输出键值对集合即为本文所需结果。

2MREclat算法设计与实现

MREclat算法主要分为两步：1）初始化步骤。该步骤用于将行存储的水平型数据库转换成列存储的垂直型数据库。2）并行挖掘步骤。首先，将第1）步获得的数据按项目集的前缀（项目集排序后的第一个item）分发到不同的计算节点上，为了获得较好的负载平衡，本文将所有的前缀（1项频繁集）进行均衡分组；然后，使用改进的Eclat算法在各计算节点上求解其所对应的分组中item开头的所有频繁项目集。

2.1初始化

由于所获得商务数据源往往采用水平数据库，因此需要先将水平数据库转换成垂直数据库。目前已有的方法直接将水平数据库变成以每个频繁1项集为列的垂直数据库，这样做主要有3个缺点：1）本身转换需要时间；2）转换后的1项集所对应的列长度较大；3）由1项集求解2项集时需要较多的交运算。

4结语

本文提出了一种基于Map/Reduce框架的MREclat并行算法。MREclat算法先将水平型数据库，转换成适合Map/Reduce模型的垂直型数据库；然后将数据按前缀进行重新分组，使前缀相同的能够被分发到同一个节点上进行计算。MREclat引入了均衡的分组方案以获得较好的负载平衡。实验结果表明，MREclat算法有着很好的加速比和良好的可扩展性，运行效率比文献[9]的算法更高。

参考文献：

[1]AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules [C]// Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann Publishers， 1994： 487-499.

[2]HAN J W， PEI J， YIN Y. Mining frequent patterns without candidate generation [C]// Proceedings of the 2000 ACM SIGMOD International Conference on Management of data. New York： ACM Press， 2000： 1-12.

[3]ZAKI M J， PARTHASARATHY S， OGIHARA M， et al. New algorithms for fast discovery of association rules [C]// Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. Menlo Park： AAAI Press， 1997： 283-286.

[4]LI Z， LIU X， CAO X. A study on improved Eclat data mining algorithm [J]. Advanced Materials Research， 2011， 328/329/330： 1896-1899.

[5]KOTIYAL B， KUMAR A， PANT B， et al. User behavior analysis in Web log through comparative study of Eclat and Apriori [C]// Proceedings of the 7th International Conference on Intelligent Systems and Control. Piscataway： IEEE Press， 2013： 421-426.

[6]HOWE D， COSTANZO M， FEY P， et al. Big data： the future of biocuration [J]. Nature， 2008， 455（7209）： 47-50.

[7]ASHRAFI M Z， TANIAR D， SMITH K. ODAM： an optimized distributed association rule mining algorithm [J]. IEEE Distributed Systems Online， 2004， 5（3）： 1-18.

[8]ZAKI M J， PARTHASARATHY S， OGIHARA M， et al. Parallel algorithms for discovery of association rules [J]. Data Mining and Knowledge Discovery， 1997， 1（4）： 343-373.

[9]LI W， ZHAO H， ZHANG Y， et al. Research on massive data mining based on MapReduce [J]. Computer Engineering and Applications， 2013， 49（20）： 112-117.（李伟卫，赵航，张阳，等.基于MapReduce的海量数据挖掘技术研究[J].计算机工程与应用，2013，49（20）：112-117.）

[10]STONEBRAKER M， ABADI D J， BATKIN A， et al. Cstore： a columnoriented DBMS [C]// Proceedings of the 31st International Conference on Very Large Data Bases. New York： ACM Press， 2005： 553-564.

[11]ZAKI M J， GOUDA K. Fast vertical mining using diffsets [C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press， 2003： 326-335.

[12]DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters [J]. Communications of the ACM， 2008， 51（1）： 107-113.

[13]LUCCHESE C， ORLANDO S， PEREGO R， et al. WebDocs： a reallife huge transactional dataset [EB/OL]. [20131210]. http：//fimi.ua.ac.be/data/webdocs.pdf.