摘 要：频繁项集挖掘是数据挖掘过程中的重要部分，传统数据挖掘算法中常用Apriori算法和FP增长算法来挖掘频繁项集。在实际应用中，传统算法往往不能用于频繁更新的数据库，采用IMBT数据结构能从不断更新的数据库中挖掘频繁项集，但是这将导致存储空间不足和运行效率低下的问题。基于MapReduce的增量数据挖掘能够有效解决这些问题，通过对比基于MapReduce的增量数据挖掘和传统增量数据挖掘的运行时间可以证明，基于Mapeduce的增量数据挖掘更高效。
关键词：增量数据挖掘；MapReduce；增量挖掘二叉树；频繁项集

　目前，数据挖掘[1]在计算机领域正飞速发展。数据库系统领域的发展主要在数据收集、数据库创建、数据管理、数据分析、数据挖掘、数据仓库等方面。在数据挖掘中，挖掘关联规则是相当重要的部分。该部分的主要研究集中在挖掘算法上。国内外对频繁项集挖掘算法一直都有着很深的研究，例如：Apriori算法[1]，FP增长算法[1-2]。
　但是，现实应用中新的事务会不断地录入数据库，这使得许多挖掘算法不能处理动态的数据。数据库随机变动，这些算法不能有效应对数据的增添、删除等操作，这使得增量数据挖掘[3-5]变得尤为重要。
1 增量数据挖掘的必要性
　在现实应用中，事务数据库常处于动态更新状态，这需要对传统关联规则挖掘算法做进一步改进，因此出现了一些新的关联规则。一些传统的批量挖掘算法通过反复扫描数据库来发现是否有新的事物添加到数据库中，但是这样做需要大量的运算时间。
　实际应用中，由于新的事务不停地添加到数据库中，原先产生的频繁项集将被淘汰掉，基于新的数据库会产生新的频繁项集。增量挖掘算法能有效避免这样的问题。增量数据挖掘以之前挖掘的结果为基础，利用新增的事务来进行增量挖掘。
2 增量挖掘发展现状
2.1 基于IMBT的增量挖掘
　为了能更好地利用现成的挖掘结果，采用了一种新的树形结构来代替FP树。该结构叫做增量挖掘二叉树（IMBT）[2]，在事务添加到数据库中或从数据库中删除后，它能给出每个项集的支持度计数。与之前的在数据库更新后通过反复扫描数据库得出的频繁项集支持度计数相比，该算法一次只处理一条事务并且记录数据集结构中可能的频繁项集，节约了大量的时间。

2.4 在数据库更新后挖掘频繁项集
　给定一个项集X，如果X在事务数据库中出现的频率大于或等于预设的最小支持度，X则称为频繁项集。如果项集X不是频繁项集，它的左半部分的子项集也不是频繁的，该算法会停止处理左半部分的子项集，这样可以提高挖掘效率。构建好IMBT树后，需要遍历该树来找出满足最小支持度阈值的频繁项集，挖掘结果被保存在一张表中以便将来使用。由于IMBT树的构建不需要支持度阈值，所以可以在数据库更新后以任何支持度阈值挖掘频繁项集。
　该方法采用IMBT树结构，重用从源数据库中挖掘出来的结果挖掘新增事务，使得性能有大幅度提升。但是该方法仍面临内存空间不够的问题。随着程序运行，IMBT树将会逐渐扩大，这使得内存空间容纳不下IMBT树，运行效率也将大大降低。采用并行机制来改进现有的串行挖掘算法将在性能上有很大地飞跃。
3 问题解决方案
3.1 并行算法
　在并行计算[6-7]中，数据会被分发到不同的计算机节点中去，并行过程中每台计算机对不同的数据块执行相同的任务。
　由于真实环境中的数据库通常非常大，把整个数据库保存在每个节点计算机上将造成存储空间过多的浪费。将数据库拆分则能成功地将子数据库分发在不同的计算机节点上。由于每台计算机都保存子数据库，节约了大量的存储空间。
3.2 并行算法的优势
　随着数据的增加，当数据量超过了GB的时候，串行数据挖掘算法将很难在短时间内给出挖掘结果。而且单台电脑没有足够的内存来容纳全部的数据。在并行条件下，由于聚集了多台计算机的存储空间和处理能力，因此并行算法能很好地解决运行效率低下，存储空间不足的问题。
3.3 MapReduce工作流程
　要顺利实现并行算法需用MapReduce框架[8]。MapReduce是由谷歌开发的标准软件架构，主要用于处理大数据操作任务。该架构由Map和Reduce组成。
　当有数据输入时，输入数据被分割成块发送到各个节点计算机上，被分配了任务的节点计算机读取并处理收到的输入数据块。Map函数处理完数据后输出中间数据：键值对，输出的中间键值对暂时缓冲到内存，这些内存中的的键值对将会写入到本地硬盘，然后将中间键值对在本地硬盘的位置信息发送给主节点计算机，主节点计算机负责向执行Reduce函数的计算机发送位置信息，这些计算机通过位置信息远程从运行Map函数的计算机硬盘上读取中间键值对，并将中间键值对按键分类，拥有相同键的值都分在一起，由Reduce函数处理后输出最终结果[8]。图4给出了其工作流程图。

4 提出系统
4.1 系统思路
　针对上述内存空间和运行效率的问题，提出了一种并行构建IMBT树挖掘频繁项集的方法。该方法主要完成两项工作：并行构建IMBT树及频繁项集计数。由于单台计算机内存和处理器能力有限，该算法不适用于单台电脑上运行。为了让算法的性能更高，就需要尽量减少计算机之间数据的传输并且避免过多的处理过程。
4.2 系统设计
　首先将输入文件分为若干独立文件块。然后并行处理输入的每一个文件块。由于该方法需要用到基本数据结构IMBT进行增量挖掘，不需要为IMBT树定义最小支持度阈值。当本地IMBT树在各个节点计算机中生成后，每个项集将会在独立的节点计算机中进行支持度计数。然后将生成的局部频繁项集结合起来，在全局数据库中生成一个全局的频繁项集。最后，由用户定义一个最小支持度阈值，并将其用于全局频繁项集从而计算出真正的频繁项集。MapReduce框架的工作模式能很好地实现该方法，该方法的设计流程图如图5所示。

5 性能仿真与结果分析
　为了对比基于MapReduce的增量数据挖掘和传统增量数据挖掘的运行效率，实验选取一个拥有85 643条事务的数据库，数据库中每条事务的项目数平均为7个，项目总共有1 300种，实验用计算机总共3台，配置均为双核CPU AMD Athlon（tm）64 X2 Dual Core Processor 4000+，内存为2 GB，安装Ubuntu10.10与Window XP双系统，其中传统IMBT挖掘算法在单台电脑上用XP系统运行，基于MapReduce的IMBT在3台电脑上用Ubuntu10.10运行，其中1台计算机配置为namenode，另外2台配置为datanode。由于是实验，所以没有配置second namenode。
　在数据挖掘进行之前，数据库中预存有30 000条事务，在基于MapReduce的IMBT算法中，这30 000条事务被平均分配到3台电脑上，实验开始后不断地向数据库录入事务数，两种算法均取支持度阈值为800。图6给出在不断向数据库中添加事务时，两种算法的耗时对比。
　从图6中可以看出，基于MapReduce的IMBT算法的运行效率几乎比传统IMBT算法快一倍，图中的运行时间并非完全线性增长，这是由于数据库中每条事务的项目种类和项目数量不一致导致的。理论上基于MapReduce的IMBT算法采用2台计算机同时进行挖掘任务，效率应该快一倍，图中结果并未达到一倍是因为整个MapReduce过程需要频繁传递信息，namenode需要一定的响应时间，导致实际效率与理论效率存在一定误差。但基于MapReduce的增量数据挖掘算法在运行效率上比传统数据挖掘算法仍然有了质的提升。

　传统数据挖掘技术：Apriori、FP树等算法，虽然都能有效地找出频繁项集，但不能适用于真实环境下动态的数据。所以出现了增量数据挖掘，本文给出了一种基于IMBT结构的增量数据挖掘算法，该算法能够在新事务添加到数据库或从数据库中删除后有效地列举出每一个项集的支持度计数。由于在树的构建过程中不需要预设最小支持度阈值，该算法允许用户以任何支持度阈值挖掘频繁项集。结合之前从数据库中挖掘出来的结果，该算法能够挖掘更新后的数据库，效率上有很大的提升。但是IMBT树在单台计算机中运行时，该算法面临存储空间不足的问题，随着算法的进行，IMBT树逐渐扩展，会造成内存溢出，效率降低。
为此提出了一种新的方法，该方法采用MapReduce框架，将数据库分为若干子数据库然后发向多个节点计算机，由于计算机集群聚集了多台计算机的存储能力和计算能力，在存储空间上可以动态的增加，并且能够并行处理数据，从而解决了运行效率和存储空间的问题，因此该方法比传统的非并行增量算法更高效。
参考文献
[1] 范明，孟小峰.数据挖掘概念与技术[M].北京：机械工业出版社，2012.
[2] 蒋翠清，胡俊妍.基于FP-tree的最大频繁项集挖掘算法[J].合肥工业大学学报（自然科学版），2010，33（9）：387-1391.
[3] HONG T P， WANG C Y， TAO Y H. A new incremental data mining algorithm using pre-large itemsets[J]. Intelligent Data Analysis， 2001， 5（2）： 111-129.
[4] HONG T P， LIN C W， WU Y L. Incrementally fast updated frequent pattern trees[J]. Expert Systems With Applications，2008，34（4）：2424- 2435.
[5] YANG C H， YANG D L. IMBT-a binary Tree for Efficient Support Counting of Incremental Data Mining[J]. 2009 International Conference on Computational Science & Engineering， 2009，1（1）：324-329.
[6] 刘鹏.云计算[M].北京：电子工业出版社，2011.
[7] 高岚岚.云计算与网格计算的深入比较研究[J].海峡科学，2009（2）：56-57.
[8] LAM C， 韩冀中.Hadoop实战[M].北京：人民邮电出版社，2012.