频繁子树挖掘及其在XML挖掘中的应用研究

论文摘要

频繁模式挖掘是数据挖掘领域中的一个重要问题,其研究范围包括事务、序列、树和图。频繁子树挖掘在生物信息学,Web挖掘,化合物结构分析等领域具有十分重要的应用价值,因此受到研究人员的高度重视。XML己经成为Intemet上数据描述和交换的标准。如何从XML数据中挖掘有价值的知识是一个具有挑战性的研究课题。本文就频繁子树挖掘方法、最大频繁Embedded子树挖掘、基于可变支持度约束的最大频繁Induced与Embedded子树挖掘、以及频繁子树挖掘在XML挖掘中的应用等方面作了深入的研究。本文的主要研究工作包括以下几个方面:（1）对近些年来提出的频繁子树挖掘算法进行综述与分析。论述了各种频繁子树挖掘算法的思想,并对典型算法的性能进行了实验分析与比较。（2）提出了一种高效的最大频繁Embedded子树挖掘算——CMPETreeMiner,该算法采用带节点范围的先序遍历序列存储树,并采用伪投影技术对频繁子序列进行投影,对投影序列中的每个节点编码。在挖掘带编码频繁子序列过程中使用剪枝技术尽早删除最终不能通过投影编码生成最大频繁Embedded子树的带编码频繁子序列.大大降低了搜索空间,节省了时间与空间的代价。实验结果表明CMPETreeMiner具有较高的效率。（3）提出了快速挖掘可变支持度约束的闭合与最大频繁Induced子树算法——SCCMTreeMiner,采用最右扩展技术枚举候选子树,并利用最小有效扩展性质进行剪枝,在变化的支持度约束下求出所有闭合频繁子树以及最大频繁子树。实验结果表明,SCCMTreeMiner算法不仅能够有效地减少所产生子树的数量,而且在执行时间上也大大少于使用固定支持度的同类算法。（4）提出了快速挖掘可变支持度约束的闭合与最大频繁Embedded子树算法——SCCMETreeMiner,通过对频繁k-子树的每个增长点构造投影数据库,将投影数据库中的频繁节点添加到频繁k-子树上直接得到频繁（k+1）-子树,无冗余的构造了Embedded子树的增长空间。并利用最小有效扩展性质进行剪枝,得到所有满足约束的闭合频繁子树以及最大频繁子树。实验结果表明,其不仅执行时间少,最关键的是,得到了用户感兴趣的模式。（5）提出了一种基于频繁子树模式的XML文档结构聚类算法——GCFS。该算法采用基于后退的先序序列表示XML文档树,挖掘XML文档集合中的闭合与最大频繁Induced子树,并将其作为聚类特征,根据频繁子树的大小赋予不同的权值,采用余弦函数定义相似度,利用K-Means算法聚类XML文档。实验结果表明,GCFS不仅能够得到维数较小的聚类特征空间,而且在聚类效率和精度上也高于同类算法。（6）提出了一种改进的XML文档结构聚类算法——GCFS*。该算法通过挖掘XML文档集合中的最大频繁Induced子树构造聚类特征空间,在频繁子树挖掘过程中自动生成较好的最小支持度,无需用户设置:优化聚类特征空间:并采用CLOPE算法聚类XML文档,聚类过程中自动生成簇的个数。实验结果表明,GCFS*不仅取得了较好的聚类效率,而且其聚类精度较GCFS高。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究背景及意义
• 1.2 研究现状
• 1.3 本文研究内容
• 1.4 本文的组织结构
• 第二章 频繁子树挖掘概述
• 2.1 相关概念与理论
• 2.2 频繁Bottom-up子树挖掘
• 2.3 频繁Induced子树与频繁Embedded子树挖掘
• 2.3.1 基于候选生成-测试的方法
• 2.3.2 基于模式-增长的方法
• 2.3.3 典型算法分析
• 2.4 约束频繁子树挖掘
• 2.4.1 闭合与最大频繁子树挖掘算法
• 2.4.2 基于子树约束的频繁子树挖掘算法
• 2.4.3 基于层次约束的频繁子树挖掘算法
• 2.5 实验与性能分析
• 第三章 最大频繁Embedded子树挖掘
• 3.1 算法思想
• 3.2 CMPETreeMiner算法描述
• 3.3 实验与性能分析
• 第四章 可变支持度下挖掘最大频繁子树
• 4.1 相关概念及理论
• 4.2 可变支持度约束下的最大频繁Induced子树挖掘算法
• 4.2.1 候选子树枚举过程
• 4.2.2 闭合与最大频繁Induced子树的剪枝方法
• 4.2.3 基于可变支持度约束的剪枝方法
• 4.2.4 SCCMTreeMiner算法描述
• 4.2.5 实验与性能分析
• 4.3 可变支持度约束下的最大频繁Embedded子树挖掘算法
• 4.3.1 固定最小支持度下挖掘最大频繁Embedded子树
• 4.3.2 可变支持度下挖掘最大频繁Embedded子树
• 4.3.3 SCCMETreeMiner算法描述
• 4.3.4 实验与性能分析
• 第五章 频繁子树挖掘在XML挖掘中的应用
• 5.1 XML频繁模式挖掘
• 5.1.1 XML数据及其DOM树表示
• 5.1.2 频繁子树挖掘在XML频繁模式挖掘中的应用实例
• 5.2 XML结构聚类
• 5.3 基于频繁子树模式的XML结构聚类算法GCFS
• 5.3.1 XML文档预处理
• 5.3.2 特征提取及表示
• 5.3.3 GCFS算法描述
• 5.3.4 实验与性能分析
• *'>5.4 一种改进的XML结构聚类算法GCFS^*
• 5.4.1 自动获得最小支持度
• 5.4.2 最优特征提取及表示
• *算法描述'>5.4.3 GCFS^*算法描述
• 5.4.4 实验与性能分析
• 第6章 结束语
• 6.1 总结
• 6.2 后续工作
• 参考文献
• 致谢
• 附录