基于布尔矩阵和 MapReduce 的 FP-Growth 算法

doi:10.3969/j.issn.1000-565X.2014.01.023

华南理工大学学报（自然科学版） ›› 2014, Vol. 42 ›› Issue (1): 135-141.doi: 10.3969/j.issn.1000-565X.2014.01.023

基于布尔矩阵和 MapReduce 的 FP-Growth 算法

陈兴蜀张帅童浩崔晓靖

四川大学计算机学院，四川成都 610065

收稿日期:2013-05-06 修回日期:2013-10-22 出版日期:2014-01-25 发布日期:2013-12-01
通信作者: 陈兴蜀(1968-)，女，教授，博士生导师，主要从事信息安全、计算机网络研究． E-mail:chenxsh@scu.edu.cn
作者简介:陈兴蜀(1968-)，女，教授，博士生导师，主要从事信息安全、计算机网络研究．
基金资助:
国家自然科学基金面上项目(61272447)

FP- Growth Algorithm Based on Boolean Matrix and MapReduce

Chen Xing- shu Zhang Shuai Tong Hao Cui Xiao- jing

College of Computer,Sichuan University,Chengdu 610065,Sichuan,China

Received:2013-05-06 Revised:2013-10-22 Online:2014-01-25 Published:2013-12-01
Contact: 陈兴蜀(1968-)，女，教授，博士生导师，主要从事信息安全、计算机网络研究． E-mail:chenxsh@scu.edu.cn
About author:陈兴蜀(1968-)，女，教授，博士生导师，主要从事信息安全、计算机网络研究．
Supported by:
国家自然科学基金面上项目(61272447)

摘要/Abstract

摘要： 关联规则挖掘是数据挖掘的一个重要组成部分．为提高关联规则的挖掘效率，提出了一种基于布尔矩阵和 MapReduce 的 FP- Growth 算法( BPFP) ，分析了算法的时间和空间复杂度．该算法使用 Hadoop 框架和布尔矩阵以减少对事务数据的扫描次数，利用两次MapReduce 来实现频繁项集的挖掘．在多个数据集上的实验结果表明，与原 FP- Growth 算法相比，BPFP 算法具有更高的执行效率、更好的加速比.

关键词: 数据挖掘, 关联规则, 布尔矩阵, MapReduce, FP- Growth 算法

Abstract:

Association rules mining is an important part of data mining.In order to improve the efficiency of associ-ation rules mining,an FP- Growth algorithm based on Boolean matrix and MapReduce,which is marked as BPFP,is proposed,with its time and space complexity being also analyzed.In BPFP algorithm,Hadoop framework andBoolean matrix are used to reduce the number of scans of transaction data,and twice Map- Reduce is adopted tomine frequent item sets.Experimental results on multiple data sets show that the improved FP- Growth algorithm issuperior to the original one due to its high execution efficiency and speedup.

Key words: data mining, association rules, Boolean matrix, MapReduce, FP- Growth algorithm

陈兴蜀张帅童浩崔晓靖. 基于布尔矩阵和 MapReduce 的 FP-Growth 算法[J]. 华南理工大学学报（自然科学版）, 2014, 42(1): 135-141.

Chen Xing- shu Zhang Shuai Tong Hao Cui Xiao- jing. FP- Growth Algorithm Based on Boolean Matrix and MapReduce[J]. Journal of South China University of Technology (Natural Science Edition), 2014, 42(1): 135-141.

[1]	蔡晓东洪涛曹艺. 基于极化关系表述与低维数据间关联学习的推荐模型[J]. 华南理工大学学报（自然科学版）, 2022, 50(1): 122-131.
[2]	张子烨, 李明畅, 梁凌睿, 等. 推荐系统信息跨领域的改进迁移学习算法[J]. 华南理工大学学报（自然科学版）, 2020, 48(11): 99-106.
[3]	吴文静景鹏贾洪飞张铭航. 基于 K 均值聚类与随机森林算法的居民低碳出行意向数据挖掘[J]. 华南理工大学学报（自然科学版）, 2019, 47(7): 105-111.
[4]	蔡泽祥马国龙孙宇嫣黄昱翰. 基于数据挖掘的电力设备运维与决策分析方法[J]. 华南理工大学学报（自然科学版）, 2019, 47(6): 57-64,71.
[5]	洪晓斌子文江余蓉罗宗强何振威. 大型钢结构无损云检测的可信度融合评估[J]. 华南理工大学学报（自然科学版）, 2019, 47(3): 70-77.
[6]	罗永刚陈兴蜀杨露. 基于内存优化配置的MapReduce 性能调优[J]. 华南理工大学学报（自然科学版）, 2017, 45(1): 102-111.
[7]	郑晓峰徐建闽卢凯. 基于属性维划分和MapReduce 的道路运输信息系统数据聚类[J]. 华南理工大学学报（自然科学版）, 2014, 42(8): 122-128,135.
[8]	陈吉荣乐嘉锦. SingleMapReduce:单一输出 HDFS 文件的 MapReduce编程模型[J]. 华南理工大学学报（自然科学版）, 2014, 42(5): 135-142.
[9]	郑晓峰王曙. 基于粗糙集与关联规则的道路运输管理信息数据挖掘方法[J]. 华南理工大学学报（自然科学版）, 2014, 42(2): 132-138.
[10]	梁瑾罗飞许玉格. 基于决策表的模糊粗糙单调依赖算法及其应用[J]. 华南理工大学学报（自然科学版）, 2011, 39(7): 7-12.
[11]	张福勇齐德昱胡镜林. 基于IRP的未知恶意代码检测方[J]. 华南理工大学学报（自然科学版）, 2011, 39(4): 15-20.
[12]	奚建清游进国汤德佑肖伟吉. 基于MapReduce的封闭立方体并行计算方法[J]. 华南理工大学学报（自然科学版）, 2009, 37(1): 91-95,112.
[13]	贾西平彭宏郑启伦石时需江焯林. 基于主题的文档检索模型[J]. 华南理工大学学报（自然科学版）, 2008, 36(9): 37-42.
[14]	金义富朱庆生. 一种离群数据集延伸知识发现框架[J]. 华南理工大学学报（自然科学版）, 2008, 36(9): 31-36.
[15]	李学俊李龙澍徐怡. 基于SOFM 网络的多层模糊关联规则挖掘算法[J]. 华南理工大学学报（自然科学版）, 2007, 35(5): 81-85.

基于布尔矩阵和 MapReduce 的 FP-Growth 算法

FP- Growth Algorithm Based on Boolean Matrix and MapReduce

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价