国家级论文发表基于MapReduce和AprioriAll的分布式序列挖掘算法

　　国家级论文发表推荐期刊《信息与电脑》国家新闻出版总署批准，国内外公开发行的计算机类优秀期刊。1989年创刊，国内统一刊号：CN11-2697/TP，国际标准刊号：ISSN1003-9767，邮发代号：82-454。《信息与电脑》杂志在零售流通领域有着广泛的盛誉，鉴于“中国第一本全力推动流通领域信息化刊物”权威性的要求，杂志的主要特点就是汇集流通业IT业内专家和企业管理者最新的言论和观点，以及他们的实践经验与体会分享，为流通领域的企业提供理论指导和实践参考。
　　摘要：序列挖掘技术，能够从大量杂乱的数据中挖掘出用户的潜在访问模式。然而，传统的挖掘技术，由于其性能和扩展性的诸多限制，并不适合现今大数据下的挖掘任务。本文基于传统的挖掘算法AprioriAll，在结合国内外研究进展的基础上引入分布式概念格模型，提出了分布式序列挖掘算法PAHDP。通过在分布式系统上构建算法原型，并加以评估，本文证明了该算法的正确性和有效性，具有一定的应用价值。

　　关键词：数据挖掘,分布式计算,概念格,Hadoop

　　分布式计算的思想，可以将仅仅由单个计算机难以计算和维护的计算任务分为很多小的、相互独立的部分，然后把这些部分分配给很多台计算机进行处理。在这个基础上，利用分布式系统架构MapReduce，用户可以在不了解分布式底层细节的情况下，充分利用其框架下集群的高传输率与容错率的优点进行计算与存储。

　　正是在这种背景下，采用分布式计算以实现庞大数据集的数据挖掘，成为了目前国内外的研究热点。利用分布式计算，人们可以把庞大的数据集分为小的、相对独立的部分，并部署于集群的计算机中进行计算，最后将结果综合。本文在此基础上，对传统的数据挖掘算法AprioriAll进行了分布式探索，并针对影响性能的多个因素进行了分析与改进。

　　1 基于AprioriAll的分布式挖掘算法设计与实现

　　1.1 AprioriAll算法

　　AprioriAll算法是由R.Agrawal等人提出的，该算法采用迭代增长的思想，首先在数据库中找出所有频繁项集，并在每一次迭代过程中，将上一次得到的序列相互链接以生成新序列。接着，在扫描数据库的同时去掉不满足最小支持度阈值的序列，并将结果作为下一次迭代的候选，直到无法再产生更长的新序列为止。最后，扫描生成的频繁序列，去除包含于其它序列的子序列，留下来的就是最终的结果。该算法结构简单，然而面临着重复扫描哦数据库、难以并行化等问题，需要进行优化。

　　1.2 算法概述

　　分布式序列模式挖掘的基本思想是将数据划分为一个个数据分片，再将每个独立的数据分片上进行数据挖掘，最后将所得的数据合并。结合这样的思路，本算法的基本流程则为：(1)数据转换与有机分割。本算法的第一步，就是完成数据源到形式背景的转换。由于输入数据为大量的交易记录，因此此步操作可以在集群系统上完成。对于每一个集群节点，其输入的数据则为交易数据库的一部分，接着，集群节点保存输入的交易信息，并记录其中出现的交易(对象)与商品(属性)。待所有节点完成输入与处理，将每一个形式背景分片合并，即可得到由原数据库转化而得到的形式背景。(2)分布式建格。待数据转化和分割完成之后，各节点即可根据输入的子全概念和其对应的形式背景构造子全格。本算法采用了Bordat算法作为建格算法，其实现简单，且效率较高。(3)频繁1-序列生成。待节点建立好了子全格之后，即可进行频繁1-序列的生成。由于在第1步实现了数据的相对独立分割，因此，此处仅需执行本地操作，无需与外界通信。由于概念格的每一个节点与概念一一对应，而概念则反映了项集(商品集)与其购买记录之间的联系。因此，仅需遍历概念格，对每一个节点计算其外延的支持度，并收集支持度大于最小阈值的概念，其内涵即为频繁项集，也就是频繁1-序列。(4)数据再分配与频繁序列挖掘。待所有节点完成计算，将所有频繁1-序列进行合并，即可得到所有的频繁1-序列，这就是频繁序列挖掘的基础。对于挖掘出的频繁序列集来说，可以按照序列的首元素进行分组，对每一个节点设定其目标序列，所有节点仅需挖掘以目标序列开头的频繁序列。待所有节点对频繁序列的挖掘完毕，即可进行合并，并将最终结果输出。

　　1.3 改进点分析

　　针对传统的AprioriAll算法，这个算法做出的改进在于：(1)将传统的串行算法并行化，利用了集群计算的优势提高计算效率。通过将算法部署于MapReduce框架，实现了分布式计算任务的自动部署和负载管理;(2)引入了分布式概念格的思想，避免了AprioriAll算法对数据库的频繁访问，通过对数据的一次访问，即可建立起数据之间的内在联系，为之后的序列挖掘提供了所有的必需信息，从而减少了节点之间的通信;(3)在序列生成上，将传统的挖掘任务分离，通过采用目标序列的办法实现了分布式挖掘，在提高效率的同时减少了冗余数据的出现。

　　2 实验评测

　　实验时，共对三种情况下的序列模式挖掘(AprioriAll算法，伪分布式环境下的PAHDP算法与分布式环境下的PAHDP算法)进行了比较与测试。实验设置8组交易数据，其中顾客数目与商品数目相等，并从20增长到2000。顾客平均交易数目与平均每次购买商品数目分别固定为8与2.5。结果如下图所示：

　　图1 实验结果

　　通过对比可以发现，当顾客数目与商品数目相等，且交易数据小于9000时，PAHDP算法执行时间远远大于AprioriAll的单机算法。而当数据量继续提升时，AprioriAll的执行时间则随之从53.385秒增加到了405.418秒(记录数为18906)，并超过了PAHDP算法。当数据量继续增长时，AprioriAll算法内存溢出而无法计算，而PAHDP算法增速较缓(伪分布式节点的计算时间仅从116秒增长到了153秒，增长率为31.9%)。从对比实验可以看出，传统的AprioriAll算法在顾客数目小于商品数目的时候，其计算时间的增长比顾客数目大于商品数目的情况下更为缓慢，因此该算法对于数据的内在结构是敏感的。而对于PAHDP算法来说，则在三种情况下的运行速度差异不大，因此其对于数据是不敏感的。

　　3 结束语

　　本文深入分析了AprioriAll算法的实现流程和相关局限，从而提出了新算法的改进目标。基于这些改进点，本文提出了分布式挖掘算法PAHDP，并对整个算法的流程和其中的关键技术进行了阐述。本文证明了PAHDP算法的有效性，论述了在较大规模数据库的情况下PAHDP算法所具有的优势。作为集群化序列挖掘的一个有效解决方案，本文设计的算法能够在大规模序列挖掘领域具备研究价值。

　　参考文献：

　　[1]王红侠.基于分布式概念格的序列模式发现研究[D].合肥：合肥工业大学.2007

　　[2]吕峰等.4种序列模式挖掘算法的特性研究[J].武汉理工大学学报，2006，28(2)：57-60

　　[3]周嘉伟等.新多维序列挖掘算法：对AprioriAll算法的改进[J].科技经济市场，2006，4：26～27

　　[4]吴汉燕等.基于改进的AprioriAll算法的Web序列模式挖掘研究[J].计算机工程与设计，2010(05)：921-1034

　　[5]王宇.序列模式挖掘的并行算法研究[D].哈尔滨.哈尔滨理工大学.2007

　　作者简介：周游(1990-)，男，四川南充人，研究生，研究方向：分布式数据挖掘。