郏奎奎，刘海滨

(中国航天系统科学与工程研究院，北京 100048)

0 引 言

数据挖掘被称为数据集中的知识发现，是在大量数据集中提取对于决策过程有用的知识的过程。数据挖掘自20世纪90年代被提出后，在许多领域得到了很好的应用。关联规则挖掘是数据挖掘的重要组成部分。1993年，R.Agrawal等[1]提出了关联规则的概念及模型，该模型主要是对一个事物和其他事物相互关联的一种描述。目前，主要的关联规则挖掘算法有Apriori和FP-growth，二者都是串行化的算法。Apriori[2]算法需要多次扫描数据集，过程中产生了大量候选集，测试这些候选集需消耗大量时间。FP-growth算法是一种基于频繁模式树的挖掘算法。该算法可以有效挖掘频繁模式，并且比Apriori算法快大约一个数量级。但是随着数据量的增大和数据集中的有用信息变得越来越稀疏，在建立FP-tree时会消耗大量的内存空间，以至于内存不够用，无法完成挖掘任务[3-4]。Park等[5]提出利用系统抽样的方法进行数据挖掘，然而单纯只依靠抽样的数据进行数据挖掘很容易造成结果的畸形和不准确。因此，学者们开始考虑通过并行计算环境来解决上述问题。文献[6]采用基于多线程的并行算法，虽然缓解了存储及计算的压力，但是内存资源的局限制约了算法的扩展能力；文献[7-8]中对MPI并行环境进行了详细的叙述，然而该环境使用进程间通信的方式协调并行计算，导致并行效率较低、内存开销大并且很难解决多节点的扩展性问题。并行算法通常具有较大的进程间的调度和通信开销，并且很难将构建FP-tree的任务进行分割。……