基于序列模式的频繁自由树挖掘算法研究

论文摘要

数据挖掘(Data Mining, DM)是从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在价值的信息或者模式。在数据挖掘概念提出以来十几年间,数据挖掘技术得到日益的重视和广泛的应用、研究。因此,作为数据挖掘重要分支的频繁项目集和关联规则的挖掘,更是引起了广泛的关注且得到的较大的研究、发展。随着数据挖掘应用领域的不断扩大和涉及到的数据种类的增多,特别是网络技术的发展,面向传统领域的结构化关系数据库和事务数据库的挖掘技术,不能满足非传统领域的数据挖掘技术的要求,比如:半结构化数据类型和非结构化数据类型。而这些数据类型在生物信息学、Web挖掘、化合物结构分析等领域有着广泛的应用。本文对面向非结构化数据——树和无环图的挖掘技术进行了深入的研究和分析。主要工作包括:首先,对数据挖掘技术的相关背景知识进行深入的介绍和分析。其中,重点阐述数据挖掘技术的一个重要分支——关联规则挖掘。综述关联规则挖掘的不同种类,并对其中的频繁项集挖掘做了全面深入的介绍。其次,对面向树结构的挖掘技术主要算法作了归类,并比较两大类算法的效率,得出结论深度优先的算法效率较高。这样为本文的研究方向找准了的切入点,在后面作者的算法采用的是面向深度优先,垂直搜索的方式。然后,分析当前采用深度优先算法中效率较高的两个经典算法,TreeMiner和FreeTreeMiner,总结和分析它们的优缺点,并为作者后续算法所用。然后,对面向无环图(自由树)类型的算法作了规划,共分4个步骤:(1)寻找自由树的中心点,对此,作者提出高效的LWA(Longest Way Algorithm)算法,并证明该算法的正确性和高效性。(2)对有根无序树作规范化,作者在这里提出规范化算法Canonicalization,并分析此算法的时间复杂度,证明其时间复杂度与当前效率最高的同类算法相当。(3)挖掘频繁序列模式,作者把“同分异构”的思想引入频繁序列挖掘,较大幅度的提高算法的速度效率。(4)引入索引的方法挖掘具有相同序列的不同结构的频繁子树。最后,本文用实验比较了算法SFTM(SequenceFreeTreeMiner)和类似的Chopper算法,FreeTreeMiner算法,验证了SFTM算法的高效性和正确性。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 研究背景
• 1.2 研究意义
• 1.3 国内外研究现状
• 1.4 本论文的创新之处
• 1.5 本论文的组织结构
• 2 树形结构挖掘相关背景知识介绍
• 2.1 频繁模式挖掘相关问题
• 2.1.1 频繁项集挖掘
• 2.1.2 序列模式挖掘
• 2.1.3 时间序列模式挖掘
• 2.1.4 频繁子图挖掘
• 2.2 树相关问题定义
• 2.3 子树同构、支持度和频繁度
• 2.4 频繁子树挖掘
• 2.4.1 基于支持度的频繁子树和基于频繁度的频繁子树
• 2.4.2 频繁子树挖掘的一般过程
• 2.5 树的编码表示
• 2.6 本章小结
• 3 树形结构挖掘经典算法研究
• 3.1 引言
• 3.2 FREETREEMINER 算法
• 3.3 TREEMINER 算法
• 3.3.1 产生候选子树
• 3.3.2 候选子树计数
• 3.3.3 算法描述
• 3.3.4 辖域表
• 3.3.5 候选模式生成
• 3.4 本章小结
• 4 SEQUENCEFREETREEMINER 研究与实现
• 4.1 引言
• 4.2 自由树（无环图）的有根无序化
• 4.2.1 LWA 算法的基本思想
• 4.2.2 LWA 算法
• 4.2.3 LWA 算法的正确性证明
• 4.3 有根无序树的有序化
• 4.3.1 无序树的范式编码
• 4.3.2 无序树的规范化（CANONICALIZATION）
• 4.3.3 规范化算法的复杂性分析
• 4.4 树扩展技术
• 4.4.1 算法的思想
• 4.4.2 频繁序列的产生
• 4.5 发现频繁树结构
• 4.6 本章小结
• 5 SFTM 算法试验分析
• 5.1 引言
• 5.2 跟CHOPPER 算法的对比
• 5.2.1 CHOPPER 算法的介绍
• 5.2.2 数据集的生成
• 5.2.3 数据集上的表现
• 5.3 SFTM 跟FREETREEMINER 的比较
• 5.3.1 数据集介绍
• 5.3.2 数据集上两种算法的对比
• 5.4 本章小结
• 6 总结与展望
• 6.1 总结
• 6.2 展望
• 致谢
• 参考文献
• 附录