XML数据频繁模式挖掘技术研究

论文摘要

XML具有简单性、结构化、可扩展性、互操作性、开放性、通用性、灵活性等特点,因而在数据交换、数据集成、数据发布、数据存储、数据管理、知识管理、信息检索等诸多领域获得广泛应用。XML数据的快速发展迫切需要与之相适应的、能有效处理XML数据的数据挖掘技术。然而传统数据挖掘技术主要处理关系数据库或数据仓库中的结构化数据,无法解决具有复杂层次结构的XML数据挖掘问题。目前关于XML数据频繁模式挖掘技术的研究尚处于起步阶段,虽然研究人员已经提出了一些面向XML数据的频繁模式挖掘算法,但由于XML数据具有结构变化、不规则、没有完全固定模式等特点,且XML数据中可挖掘结构繁多,因而至今缺乏一个统一的、抽象的模型去描述XML数据的频繁模式挖掘过程。本文在研究XML数据结构模型特征、表示方法的基础上,提出了一个统一、抽象的XML频繁模式挖掘框架系统。并在此框架基础上分别就XML数据的频繁标签序列挖掘技术、频繁查询子树离线挖掘技术、频繁查询子树在线挖掘技术、文档历史版本变化结构挖掘技术进行了讨论和研究:面向XML文档聚类的频繁XML标签序列挖掘技术研究采用分而治之的思想,提出了基于概念格的XML频繁标签序列挖掘算法。算法将XML标签数据按照共同前缀序列分成不相交等价类:通过在每个等价类中分别实施挖掘过程获取频繁标签序列。在标签序列挖掘技术基础上,研究了基于频繁标签序列的XML文档聚类技术。该技术采用频繁标签序列表示文档特征,通过考虑标签序列包含关系,并引入标签路径长度、标签路径在XML文档中连续状况等特性,提高XML文档相似性估量准确度及聚类质量。面向XML查询缓存的频繁XML查询子树离线挖掘技术研究分析XML查询结构的特点,提出了基于全局树视图的、自底向上的频繁查询子树挖掘算法BUXMiner和最大频繁查询子树挖掘算法BUMXMiner。通过构建全局树视图,使得候选子树的频度计算可直接从全局树视图中获得,而不再依赖于扫描XML文档数据集。借鉴频繁查询子树挖掘算法,给出了基于频繁查询子树的XML查询框架系统。XML查询系统中,为处理相似但不相同的XML查询树,介绍了四种XML查询树关系并给出了相似查询重写过程。大量实验表明BUXMiner算法在性能上优于原有查询子树挖掘算法;相比于传统缓存技术LRU、MRU,应用频繁查询的缓存技术可获得更好的XML查询效率。（?）基于滑动窗口的频繁XML查询子树在线挖掘技术研究通过引入滑动窗口模型,提出了面向XML查询数据流的频繁查询子树在线挖掘算法。算法以全局Trie树为数据缓存结构管理和维护缓存池的数据流,采用自下而上、基于前缀等价类的遍历方式快速产生所有带根查询子树和标准查询子树。实验结果表明该算法具有挖掘速度快、内存消耗稳定等特点,可以有效、平稳地处理XML查询数据流。（?）基于双位图B-DOM结构的XML文档历史版本变化结构挖掘技术研究在研究XML动态数据挖掘问题及XML版本变化结构挖掘框架的基础上,提出了动态变化结构挖掘算法DXSM,用于有效提取频繁变化结构及基于此的频繁插入变化结构和频繁删除变化结构。通过构建存储、管理数据动态变化信息的双位图结构B-DOM有效地解决了各种变化结构提取问题。实验结果表明该变化结构挖掘算法能快速、有效地提取XML版本序列中的变化结构信息。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 引言
• 1.2 研究思路与内容
• 1.3 论文组织
• 第2章 相关研究综述
• 2.1 引言
• 2.2 为什么需要XML数据挖掘
• 2.3 XML频繁模式挖掘技术及其应用
• 2.3.1 频繁标签序列挖掘技术
• 2.3.2 频繁子树离线挖掘技术
• 2.3.3 频繁子树在线挖掘技术
• 2.3.4 频繁变化结构挖掘技术
• 2.4 XML频繁模式相关研究项目
• 2.5 现有问题和不足
• 2.6 本章总结
• 第3章 XML数据频繁模式挖掘框架
• 3.1 引言
• 3.2 XML频繁模式挖掘框架研究的必要性、意义和研究方法
• 3.3 XML数据模型
• 3.3.1 树模型
• 3.3.2 XML频繁模式
• 3.4 XML频繁模式挖掘框架
• 3.5 本章总结
• 第4章 面向XML文档聚类的频繁XML标签序列挖掘
• 4.1 引言
• 4.2 序列挖掘算法
• 4.2.1 基于Apriori的序列挖掘算法
• 4.2.2 基于WAP-树的序列挖掘算法
• 4.2.3 基于等价类的序列挖掘算法
• 4.3 频繁标签序列挖掘算法XSM
• 4.3.1 XML数据转换
• 4.3.2 构建垂直数据库
• 4.3.3 基于概念格理论的序列枚举
• 4.3.4 连接等价类产生频繁序列
• 4.3.5 完整标签序列挖掘算法
• 4.4 算法应用-XML文档聚类
• 4.4.1 XML文档聚类算法FTSC框架
• 4.4.2 文档约简
• 4.4.3 文档相似度评估模型
• 4.4.4 XML文档聚类算法FTSC
• 4.5 实验结果及聚类效果评估
• 4.5.1 频繁标签序列挖掘算法XSM实验结果
• 4.5.2 XML文档聚类实验结果
• 4.6 本章总结
• 第5章 面向XML缓存的频繁XML查询子树离线挖掘
• 5.1 引言
• 5.2 基本概念
• 5.2.1 频繁查询子树
• 5.2.2 全局树视图（GTG）
• 5.2.3 查询子树挖掘问题
• 5.3 频繁带根查询子树挖掘算法BUXMINER
• 5.3.1 算法总体结构
• 5.3.2 全局树视图构建
• 5.3.3 频繁带根查询子树产生
• 5.3.4 等价类合并
• 5.3.5 算法效率分析
• 5.4 最大频繁带根查询子树挖掘算法BUMXMINER
• 5.4.1 算法总体结构
• 5.4.2 最大频繁带根查询子树产生
• 5.4.3 算法效率分析
• 5.5 算法应用-XML查询缓存
• 5.5.1 XML查询缓存框架
• 5.5.2 XML查询重写
• 5.5.3 XML缓存替换
• 5.6 实验结果及性能评估
• 5.6.1 数据集
• 5.6.2 BUXMiner算法实验结果
• 5.6.3 BUMXMiner算法实验结果
• 5.6.4 XML缓存实验结果
• 5.7 本章总结
• 第6章 基于滑动窗口的频繁XML查询子树在线挖掘
• 6.1 引言
• 6.2 查询子树在线挖掘问题
• 6.3 查询子树在线挖掘框架
• 6.4 全局查询池（GRP）
• 6.4.1 全局Trie树（GTrie）
• 6.4.2 面向XML查询数据流的滑动窗口模型
• 6.4.3 查询子树产生
• 6.5 查询子树在线挖掘算法
• 6.6 算法应用-在线替换XML查询缓存和WEB用户访问模式挖掘
• 6.6.1 在线替换XML查询缓存
• 6.6.2 Web用户访问模式挖掘
• 6.7 实验结果及性能评估
• 6.7.1 数据集
• 6.7.2 在线子树挖掘算法实验结果
• 6.7.3 XML查询缓存和用户Web访问模式挖掘实验结果
• 6.8 本章总结
• 第7章 基于双位图结构的XML版本变化结构挖掘
• 7.1 引言
• 7.2 XML变化结构挖掘框架
• 7.3 XML变化结构挖掘问题
• 7.3.1 XML变化结构度量准则
• 7.3.2 XML频繁变化结构挖掘问题
• 7.4 XML变化结构挖掘算法
• 7.4.1 基于DOM的双位图结构B-DOM
• 7.4.2 频繁变化结构挖掘算法
• 7.4.3 算法效率分析
• 7.5 算法应用-动态关联结构发现
• 7.6 实验结果及性能评估
• 7.6.1 数据集及参数设置
• 7.6.2 变化结构挖掘算法实验结果
• 7.7 本章总结
• 第8章 结论和展望
• 8.1 论文主要工作总结
• 8.1.1 论文主要工作概述
• 8.1.2 论文创新点
• 8.2 缺点与不足
• 8.3 未来工作展望
• 参考文献
• 致谢
• 作者简历