基于MapReduce的分布式闭频繁模式发现方法研究

摘要

随着用户需求和网络的不断发展,人类社会积累的知识、数据急剧增加。如何从海量的事务数据中发现用户感兴趣的规则、有用的知识一直是数据挖掘领域研究者面临的一大难题,而这正是本课题研究希望解决的问题。由于关联规则挖掘领域计算量大,I/O交互集中的特点,原有的串并行方法在解决问题时都存在着一定的缺陷。本课题的研究目的就是改进现有的并行频繁模式挖掘算法使其能够突破现有算法的局限性。
　　本课题围绕着海量并行频繁模式发现问题,展开了深入研究,主要研究成果可归纳为以下几个方面:
　　本文在对现有串并行频繁模式挖掘方法进行了大量调研和深入分析基础上，归纳总结了各方法的优缺点;在MapReduce并行计算框架下,把频繁闭项集挖掘的优化策略引入挖掘过程中,为困扰研究者多年的海量数据下低支持度阀值的频繁模式发现问题提出了一种有效的解决方案,其剪枝、项集合并、项跳过等改进策略有效地优化了并行挖掘过程,提升了频繁模式发现算法的性能。
　　本文在并行闭模式发现的基础上进行了进一步的优化,提出一种挖掘中节点运行负载的评价标准,完善了并行集群分组方法,对集群分组方法进行了负载均衡的优化改进,避免了快节点等待慢节点运行所带来的性能损耗;深入分析了条件FP-tree的挖掘过程,将FP-Bonsai的α?剪枝应用于并行挖掘条件FP-tree过程中,有效简化了条件FP-tree的结构,使算法性能有了进一步的提升;引入了并行闭规则生成优化方法,完善了算法处理的全过程。
　　基于以上研究成果,本文设计并实现了并行闭频繁模式发现原型系统。系统包括预处理、频繁闭项集发现、闭规则产生、用户界面展示等四个模块,涵盖了并行频繁模式发现的全过程,服务于本课题的研究中,提供一个全面覆盖关联规则挖掘研究的实验平台。

目录

基于MapReduce的分布式闭频繁模式发现方法研究

RESEARCH ON DISTRIBUTED CLOSET FREQUENT PATTERN MINING BASED ON MAPREDUCE

摘 要

Abstract

目 录

第1章 绪 论

1.1 课题研究背景和意义

1.2 国内外相关研究和综述

1.2.1 串行关联规则挖掘算法

1.2.2 并行关联规则方法研究

1.3 研究问题概述

1.4 本文的结构安排

第2章 FP-GROWTH算法及MapReduce模型综述

2.1 关联规则基本概念

2.2 FP-GROWTH算法的基本概念

2.2.1 串行FP-GROWTH算法

2.2.2 并行FP-GROWTH算法

2.3 MapReduce框架介绍

2.3.1 MapReduce模式与框架简介

2.3.2 MapReduce的容错机制

2.3.3 Hadoop-MapReduce的开源实现

2.4 本章小节

第3章 基于MapReduce的并行闭频繁模式发现

3.1 闭频繁模式挖掘

闭项集定义

闭项集挖掘优化

3.2 并行闭频繁模式发现算法

3.2.1 数据预处理与分片

并行计数

项集分组

并行迭代挖掘

合并

算法总结

3.3 实验与分析

3.3.1 实验数据描述

3.3.2 算法评价指标

3.3.3实验结果分析

3.4 本章小节

第4章 并行闭频繁模式发现方法性能优化

4.1 优化策略

4.1.1 负载均衡的分组策略

4.1.2 基于FP-Bonsai的 剪枝优化

4.1.3 并行闭频繁模式规则生成优化

4.2 实验与分析

4.2.1 实验数据描述

4.2.2 算法评价

4.2.3 实验结果分析

4.3 本章小节

第5章 关联规则挖掘系统的设计与实现

5.1 系统功能与环境

5.1.1 开发意义与功能

5.2系统总体设计

5.3系统主要模块

5.3.1 数据预处理模块

5.3.2 频繁闭模式发现模块

5.3.3 规则生成模块

5.3.4 用户展示模块

5.4 本章小节

结 论

参考文献

哈尔滨工业大学学位论文原创性声明及使用授权说明

致 谢