半结构化数据频繁模式挖掘相关技术研究

摘要

数据挖掘技术在进步的同时，也遇到了许多挑战，面对非传统的数据，如含有半结构化、非结构化文本和超链接的Web页面集、XML文档、具有序列和三维结构的DNA数据、时间序列测量值的气象数据等，其结构以及数据之间包含的许多复杂联系，而这也正是我们挖掘模式、发现知识的关键所在，舍此别无选择。为了挖掘这些半结构化和非结构化数据，算法就需要考虑数据间的联系，如时间和空间的自相关性、图的连通性、半结构化、非结构化文本中元素之间的联系。树、图和格作为常用的半结构化数据表达方式，通过节点和边表达实体、属性，以及实体之间的联系，因此可借助它们来描述研究对象的关系，便于半结构化数据的处理。
　　 本文对半结构化数据频繁模式挖掘的若干技术进行了研究。重点研究了以下几个问题：首先源于以树结构描述XML文档的简洁性，研究树结构数据频繁模式和基于约束的树结构数据频繁模式的挖掘方法；然后针对具有复杂链接关系的XML文档结构数据标记的缺失问题，研究部分标记图结构数据的频繁模式挖掘方法，以及基于支持度弱化约束的图结构数据频繁模式挖掘方法。本文研究内容和创新工作主要包括以下五个方面：
　　 ①基于子树编码聚类的频繁诱导子树挖掘算法。
　　 提出频繁诱导子树挖掘算法XML Miner，将模式增长方法应用于频繁子树模式挖掘算法中。采用了一种新的基于子树编码聚类的最小一般概化，对树进行关系编码，计算其最小一般概化，找出最大公共子树。算法直接构造频繁子树，无须多次扫描树集，利用编码把对子树挖掘转移到对聚类集合的挖掘；由于避免了树匹配操作，降低了算法时间复杂度。
　　 ②基于项集表达的频繁嵌入子树挖掘算法。
　　 提出频繁嵌入子树挖掘算法EXML Miner。算法基于频繁子树编码序列增长的方法，先将初始树集作为项集，通过路径交运算，生成带子树特征的频繁项，并在频繁项上挖掘带有频繁特征的子树，然后将频繁子树结构进行压缩，还原成真实子树形式并计算其支持度。算法基于最右路径扩展技术在有序树中发现所有频繁模式，只在树的最右分支上增加新节点生成新树，同时充分利用已生成的频繁模式信息，使得产生的候选模式数量较少。
　　 ③部分标记频繁子图挖掘算法。
　　 提出一种模式增长的部分标记频繁子图挖掘有效算法PLSM。其特点是：建立gIDX索引结构，提高访问效率。通过弱化操作，构造部分标记候选模式，通过计算支持度找出频繁模式；采用深度优先，最右模式增长的策略，挖掘任务只在部分标记图上进行。
　　 ④约束条件下树结构数据频繁模式挖掘算法。
　　 提出一种基于约束的频繁子树挖掘算法CTreeMiner。基于给出的约束定义，利用约束的简洁性在数据预处理阶段对数据进行修剪，如基于项约束的原则设置权重支持度，根据权重支持度和频繁度检查模式项是否满足约束要求。在挖掘过程中，根据约束集的要求对搜索空间进行修剪，降低匹配测试代价；同时，为了进一步减少生成模式的数量，将需求限制在闭模式的挖掘上。
　　 ⑤约束条件下图结构数据的频繁模式挖掘。
　　 具有较高的支持度但仅包含几个子图的小模式与支持度较低的大模式都可能是有趣的。因此在频繁子图挖掘过程中，利用支持度约束弱化来针对性地生成所需要的子图是一个较好的解决办法。提出一个基于模式弱化支持度约束和基于近似最大频繁独立集度量支持度的部分标记频繁子图挖掘方法，其思想是将支持度约束应用到挖掘的过程中，使得大小不等的子图可以在挖掘结果中匹配较为合适的支持度，满足用户的需求。

目录

文摘

英文文摘

1 绪论

1.1 研究动机

1.2 研究内容

1.3 研究目标

1.4 论文的组织

2 相关研究综述

2.1 引言

2.2 半结构化数据挖掘相关研究问题

2.3 频繁模式挖掘技术

2.4 现有问题与不足

2.5 小结

3 频繁子树挖掘

3.1 引言

3.2 基本概念和问题定义

3.3 用FREQT算法挖掘频繁子树

3.3.1 问题定义

3.3.2 挖掘算法

3.3.3 算法分析

3.4 基于子树编码聚类的频繁诱导子树挖掘算法

3.4.1 树的关系编码

3.4.2 基于最右路径扩展子树

3.4.3 XMLMiner算法

3.4.4 实验和算法的性能分析

3.5 基于项集表达的频繁嵌入子树挖掘算法

3.5.1 基本思想

3.5.2 EXMLMiner算法

3.5.3 实验和算法的性能分析

3.6 小结

4 基于约束的频繁子树挖掘

4.1 引言

4.2 基本概念和问题定义

4.2.1 树的基本概念

4.2.2 基于约束挖掘的定义

4.2.3 基于约束的频繁闭子树挖掘

4.3 基于约束的频繁诱导子树挖掘算法CTreeMiner

4.3.1 CTreeMiner算法

4.3.2 约束检查过程

4.4 实验与性能分析

4.5 小结

5 部分标记频繁子图挖掘

5.1 引言

5.2 相关工作

5.3 基本概念和问题定义

5.4 用Vanetik的算法挖掘部分标记频繁子图

5.4.1 相关定义

5.5 部分标记频繁子图挖掘算法PLSM

5.5.1 gIDX索引结构

5.5.2 基于gIDX索引结构的PLSM算法

5.5.3 时间复杂度的分析

5.6 实验与性能分析

5.7 小结

6 基于约束的部分标记频繁子图挖掘

6.1 引言

6.2 相关研究

6.3 基于约束的图模式

6.3.1 模式弱化支持度约束

6.3.2 支持度度量和最小允许扩展

6.4 使用模式弱化支持度约束挖掘标记子图

6.4.1 标记子图挖掘

6.4.2 SCMiner的剪枝方法

6.5 实验与性能分析

6.5.1 人工数据集

6.5.2 真实数据集

6.6 小结

7 结论与展望

7.1 总结

7.2 进一步的工作

致谢

参考文献

附 录

A.作者在攻读学位期间发表的论文目录

B.作者在攻读学位期间取得的科研成果目录