基于元素增长搜索策略的频繁闭模式挖掘算法的研究与实现

论文摘要

随着数据库技术的飞速发展以及人们获取数据手段的多样化,人类所拥有的数据急剧增加,如何从规模越来越大的数据库中提取出人们感兴趣的信息以及知识,即数据挖掘技术早已成为计算机科学的热门研究领域。关联规则挖掘是数据挖掘研究领域中的重要分支,用于挖掘反映数据库中一组数据项之间的某种潜在关系的规则,具有重要的研究价值以及应用价值。频繁模式挖掘技术是关联规则挖掘技术中的关键步骤,其效率对整个关联规则挖掘的效率起着决定作用。以往的研究工作主要集中在基于深度优先搜索策略的挖掘算法的研究上,而对其它搜索策略下的挖掘算法以及频繁模式存储结构的研究很有限。针对以上的研究现状,本文首先提出了两种新的存储频繁模式的数据结构：后缀树和有序图,并且提出了在后缀树和有序图上进行集合的查找、添加以及删除操作的算法,经实验证明,这两种存储的结构的性能优于以往的频繁模式存储结构。本文还提出了一个新的挖掘频繁闭模式的算法：EISAM算法。EISAM算法没有采用传统的深度优先或广度优先的搜索策略,而是提出了一种新的搜索策略：元素增长搜索策略,从而使算法具有增量维护的特性。为了进一步提高算法的性能,还提出了高效的削减策略以及预处理优化技术,使算法具有更加广泛的适用性。实验结果表明,EISAM算法的性能优于以往的频繁闭模式挖掘算法。本文首先对相关背景知识以及以往的研究工作进行简要介绍,然后提出后缀树和有序图的存储结构以及有关操作的算法,接着提出了基于元素增长搜索策略的EISAM算法,最后通过实验测试了提出的存储结构以及算法的性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 数据挖掘技术概述
• 1.1.1 数据挖掘的概念及主要研究方向
• 1.1.2 数据挖掘技术的应用
• 1.2 关联规则挖掘技术概述
• 1.2.1 关联规则挖掘的基本概念
• 1.2.2 关联规则挖掘的研究方向
• 1.2.3 关联规则挖掘面临的挑战
• 1.3 论文组织结构
• 第二章 相关研究工作
• 2.1 频繁模式挖掘技术概述
• 2.1.1 频繁模式挖掘在关联规则挖掘中的重要性
• 2.1.2 频繁模式挖掘的研究现状
• 2.2 频繁模式挖掘算法
• 2.2.1 Apriori算法
• 2.2.2 FP-Growth算法
• 2.2.3 CLOSET算法
• 2.2.4 D-Miner算法
• 2.3 频繁模式挖掘的研究方向以及面临的挑战
• 2.4 本章小结
• 第三章 频繁模式的存储结构
• 3.1 频繁模式的概念
• 3.2 频繁模式的后缀树存储结构
• 3.2.1 后缀树的结构
• 3.2.2 后缀树的操作
• 3.2.3 后缀树的性能分析
• 3.3 频繁模式的有序图存储结构
• 3.3.1 有序图的结构
• 3.3.2 有序图的操作
• 3.3.3 有序图的性能分析
• 3.4 本章小结
• 第四章 频繁闭模式挖掘算法EISAM
• 4.1 频繁闭模式挖掘的问题描述
• 4.2 EISAM算法概述
• 4.2.1 EISAM算法的搜索策略
• 4.2.2 EISAM算法与以往算法的比较
• 4.3 EISAM算法的削减规则
• 4.3.1 削减规则的提出
• 4.3.2 削减规则对算法性能的提升
• 4.3.3 削减规则的实现
• 4.4 EISAM算法提高性能的预处理技术
• 4.4.1 选择枚举对象
• 4.4.2 按项目支持度递增排序
• 4.4.3 处理特殊的项目
• 4.5 本章小结
• 第五章 实验及结果分析
• 5.1 实验环境及实验数据集
• 5.2 存储结构性能测试
• 5.2.1 压缩效率测试
• 5.2.2 操作效率测试
• 5.3 削减规则及预处理性能测试
• 5.4 EISAM算法与其它算法性能比较
• 5.4.1 改变阈值参数
• 5.4.2 改变数据集规模
• 5.5 本章小结
• 第六章 结论
• 6.1 本文工作总结
• 6.2 今后工作展望
• 参考文献
• 致谢
• 攻读硕士期间发表的论文