分布式序列模式挖掘算法研究

论文摘要

目前信息主导的时代,海量数据存储在数据库或者数据仓库中。面对这种“信息爆炸”的现实,如何从海量数据中提取有价值的信息已显得尤为重要。数据挖掘技术的出现和发展为人们解决了这一难题。所谓数据挖掘技术是利用各种分析工具从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中,提取潜在有用的信息和知识的过程。在本文中,我们对序列模式挖掘技术做了深入研究。序列模式挖掘是数据挖掘研究的一个重要课题,挖掘基于时间或者其他顺序出现频率高的模式,是对关联规则挖掘的进一步推广,但克服了关联规则中不能反映事件在时间顺序上的前后相关性。序列模式挖掘技术已在顾客购买行为的分析、网络访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、DNA序列模式的分析等方面广泛应用。在研究现有的单机和分布式序列模式挖掘算法的基础上,本文围绕着单机下基于位图序列模式挖掘、分布式序列模式挖掘以及分布式多维序列模式的近似挖掘等几方面做了深入研究,主要创新点如下:1)基于传统序列模式挖掘方法不能有效地解决候选序列费时难题,本文提出一种基于位图的序列模式挖掘方法SMBR（sequential patterns mining based onbitmap representation）。SMBR算法采用一种简化的位图表示结构表示数据库的方法。该方法首先由序列扩展和项扩展产生候选序列,然后通过原序列位图和被扩展项位图位置快速运算生成频繁序列,有效地获得序列模式。2)由于分布式环境下挖掘全局序列模式常常产生过多候选序列,加大了网络通信代价。为此提出一种基于分布式环境下的挖掘全局序列模式算法-FMGSP（fastmining of global sequential pattern）。FMGSP算法将各站点得到的局部序列模式压缩到一种语法序列树上,避免了重复的序列前缀传输;基于合并树中结点序列规则、简单的特点,提出一种I/S-E（Item Extension and Sequence Extension）剪枝策略,有效地约减了候选序列,减少了网络传输量,从而快速生成全局序列模式。3)提出一种多维序列模式近似挖掘算法AMSP（Approximate Mining of GlobalMultidimensional Sequential Patterns）,以解决分布式环境中大型数据库中多维序列模式挖掘问题。该方法不同于传统的分布式多维序列模式挖掘方法,具备较好的伸缩性。首先将维度信息嵌入相应序列中,使多维序列模式挖掘转化为序列模式挖掘;然后在各分站点对转换后序列聚类、概化和分析,采用有效的近似挖掘方法获得局部模式;最后集中所有局部模式,通过高频度序列模式模型挖掘全局多维序列模式,有效地解决通信代价大、维度高等难题。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究背景
• 1.2 课题引出
• 1.3 论文的主要工作
• 1.4 论文组织
• 第二章 基本理论
• 2.1 序列模式挖掘问题描述
• 2.1.1 序列模式挖掘
• 2.1.2 多维序列模式挖掘
• 2.1.3 基于位图序列模式挖掘
• 2.2 分布式频繁项目集挖掘
• 2.3 分布式序列模式挖掘
• 2.4 本章小结
• 第三章 基于位图序列模式挖掘算法SMBR
• 3.1 相关研究工作
• 3.2 SMBR算法涉及的基本概念
• 3.3 基于位图序列模式挖掘算法SMBR
• 3.3.1 位图结构
• 3.3.2 SMBR算法描述
• 3.3.3 SMBR算法流程
• 3.4 实验结果分析
• 3.5 本章小节
• 第四章 分布式序列模式挖掘算法FMGSP
• 4.1 相关研究工作
• 4.2 分布式序列模式挖掘技术
• 4.3 全局序列模式挖掘算法FMGSP
• 4.3.1 FMGSP算法描述
• 4.3.2 FMGSP算法实例分析
• 4.4 实验结果分析
• 4.4.1 FMGSP算法分析
• 4.4.2 FMGSP算法实验结果
• 4.5 本章小结
• 第五章 分布式多维序列模式近似挖掘算法AMSP
• 5.1 相关研究工作
• 5.2 AMSP算法涉及的基本概念
• 5.3 全局多维近似挖掘算法AMSP
• 5.3.1 多维信息处理
• 5.3.2 局部多维序列模式挖掘
• 5.3.3 全局多维序列模式挖掘
• 5.4 实验评估
• 5.4.1 算法有效性分析
• 5.4.2 算法伸缩性分析
• 5.5 本章小结
• 第六章 总结与未来工作
• 6.1 本文的主要研究成果
• 6.2 未来的研究方向
• 致谢
• 参考文献
• 攻读硕士期间撰写的主要论文
• 攻读硕士期间参加的科研项目