安建瑞，王海鹏，张龙波，金　超，怀　浩

(山东理工大学 计算机科学与技术学院，山东 淄博　255049)



一种基于MapReduce的压缩矩阵关联规则挖掘算法

安建瑞，王海鹏，张龙波，金超，怀浩

(山东理工大学 计算机科学与技术学院，山东 淄博255049)

摘要：提出一种基于MapReduce的压缩矩阵关联规则挖掘算法FMA_Mining。该算法将数据库映射为布尔矩阵，在矩阵映射过程中引入Flag标识，对于连续出现的项用Flag标识标明，简化矩阵元素的读取和列向量运算。针对大数据应用中事务和项目规模较大的情况，算法引入了矩阵分割和并行化处理思想。在Hadoop平台采用WebDocs数据集对算法性能进行测试，从理论分析和实验结果两方面证明了FMA_Mining算法的有效性。

关键词：压缩矩阵；关联规则； MapReduce；Hadoop

关联规则(association rule)是数据挖掘的重要研究领域之一，能够通过对数据库中频繁项集的挖掘，找出不同项目之间的联系。文献[1]中Huang等首次提出基于矩阵的关联规则挖掘算法，称之为BitMatrix Algorithm。该算法把数据库中的事务和项转化为布尔矩阵，只需要扫描一次数据库，不会产生大量的候选集。

文献[2]中Krajca等提出了一种基于因式分解的类布尔矩阵算法，利用频繁闭项集作为候选因子项，然后计算增量连接项目的剩余因素项。该算法能够在保持高准确度的前提下，最大限度地减少数据集的维度。文献[3]中提出了基于MapReduce的矩阵算法，通过Hadoop平台实现矩阵运算的并行化，能够处理规模较大的数据，算法执行效率较高。

文献[4]提出了一种利用压缩矩阵的方法产生频繁项集的算法，在原有的布尔矩阵的基础上，引入了新行Vs和新列Hs，分别表示某一项目的支持度和某一事务中存在的项目个数。……