基于聚类分区的序列模式挖掘算法研究

论文摘要

信息技术的日新月异使得各个领域的数据量激增,在此背景下诞生的知识发现和数据挖掘给人们提供了一种新的认识数据、理解数据的智能手段。序列模式发现是其中的一个重要研究课题。数据规模的增大对挖掘算法提出了更高的要求。本文针对目前序列模式发现研究中的一些问题展开研究,主要研究工作如下:(1)详细讨论了序列模式的基本模型以及经典的发现方法,展现了序列模式发现研究领域的应用前景及所面临的挑战。(2)针对PrefixSpan算法产生的投影数据库花费较多的存储空间及扫描时间,提出PSD算法,舍弃了对非频繁项的存储及对投影序列数小于最小支持数的投影数据库的扫描,减少了不必要的存储空间,提高了查询速度。实验证明,PSD算法比PrefixSpan算法具有更好的时空性能。(3)对较大数据集挖掘序列模式,提出基于分区的序列模式挖掘算法,以期克服有限存储问题,为并行处理及分布式处理做好基础。此外,当给出的分区数固定时,不同的分区性能可能存在较大差异,本文通过聚类方法对数据集预处理,以得到可以产生较少局部频繁序列的特定分区,最终得到较少的全局候选序列以减少第二遍扫描时间。理论分析和实验表明,本文所提出的方法可比普通分区方法得到更加优化的分区从而效率更高。

论文目录

• 摘要
• ABSTRACT
• 致谢
• 第一章 绪论
• 1.1 数据挖掘概述
• 1.1.1 数据挖掘的发展
• 1.1.2 数据挖掘的概念
• 1.1.3 数据挖掘的任务
• 1.1.4 数据挖掘的热点
• 1.2 序列模式挖掘技术
• 1.2.1 序列模式的提出
• 1.2.2 序列模式的研究概况
• 1.3 本文的内容与组织
• 第二章 序列模式概述
• 2.1 序列模式的定义
• 2.2 序列模式与关联规则的比较
• 2.2.1 关联规则概述
• 2.2.2 序列模式与关联规则的比较
• 2.3 序列模式挖掘算法
• 2.3.1 AprioriAll算法
• 2.3.2 GSP算法
• 2.3.3 PrefixSpan算法
• 2.4 本章小结
• 第三章 基于 PrefixSpan算法的改进算法 PSD的研究
• 3.1 PSD算法
• 3.1.1 PSD算法描述
• 3.1.2 实例说明
• 3.2 实验分析
• 3.2.1 实验数据
• 3.2.2 实验结果
• 3.3 本章小结
• 第四章 基于聚类预处理分区的序列模式挖掘研究
• 4.1 聚类概述
• 4.2 基于聚类预处理分区的序列模式挖掘算法
• 4.2.1 分区算法概述
• 4.2.2 基于聚类预处理分区的序列模式挖掘算法描述
• 4.2.3 实例说明
• 4.3 实验分析
• 4.4 本章小结
• 第五章 结束语
• 5.1 工作总结
• 5.2 工作展望
• 参考文献
• 附录一 攻读硕士学位期间发表论文