图数据库频繁模式挖掘关键技术研究

摘要

从图数据库挖掘频繁模式在化学信息学、计算生物学、WEB信息管理、社会网络分析等领域有着广泛的应用。因此本文重点研究了从图数据库中挖掘频繁模式的关键技术，并针对频繁模式挖掘所面临的效率瓶颈、结果集庞大以及高复杂、冗余性等问题，在本文中提出了基于随机化挖掘极大频繁子图的方法RMPM、挖掘具有代表性频繁子图的算法FRSM、InRSM。本文的主要研究成果有：
　　 1．随机化方法在挖掘海量数据集时非常高效，但是因为随机性，会造成结果的重复发现，势必造成很多重复和无用的子图同构计算。本文提出的基于随机化挖掘极大频繁子图的方法RMPM，通过对已挖掘到的结果建立索引，提高了随机算法的效率。在真实和模拟数据集上的实验结果也证实了RMPM算法是高效、可伸缩的。本文提出的随机算法的思想是通用的，可以应用于各种各样的模式，比如自由树、项集等，在真实数据集上挖掘极大频繁自由树的实验结果也证实了RMPM算法是通用的。
　　 2．为了压缩频繁模式集合，挖掘出更小、更有代表性的频繁模式集合，本文提出了挖掘具有代表性频繁模式的算法FRSM，算法第一步采用本文提出的效率更高的RMPM算法作为频繁模式挖掘算法，第二步在RMPM结果集上聚类，在聚类时，综合考虑频繁子图在事务空间上的相似性和模式空间上的相似性，使得聚类的质量更好，获得的模式更具代表性。在大量的实验上也证明了FRSM算法所得到的代表模式集合比不考虑或只考虑模式在事务空间上的相似性的聚类所得到的模式更具代表性。
　　 3．本文也提出直接从图数据库中挖掘代表模式集合的算法InRSM，它比两步算法FRSM更加高效，InRSM算法同样考虑了模式在事务空间上和模式空间上的相似性，大量的实验也证明了InRSM算法是高效的和可伸缩的。

目录

第1章 绪论

1.1 研究背景

1.1.1 数据挖掘概述

1.1.2 频繁模式挖掘的作用

1.2 国内外研究现状

1.3 本文主要研究工作

1.3.1 挖掘频繁子图面临的挑战

1.3.2 主要解决办法

1.3.3 本文主要研究成果

1.4 本文章节安排

第2章 频繁模式挖掘

2.1 引言

2.2 传统的FPM算法

2.2.1 频繁项集挖掘

2.2.2 频繁序列挖掘

2.2.3 频繁子树挖掘

2.2.4 频繁子图挖掘

2.3 采样和随机方法在FPM中的应用

2.4 压缩频繁模式

2.4.1 极大/闭频繁模式挖掘

2.4.2 TOP-K模式挖掘

2.4.3 基于聚类的代表模式集合挖掘

2.4.4 频繁图模式压缩

2.5 本章小结

第3章 挖掘极大频繁子图

3.1 引言

3.2 背景知识

3.3 极大频繁子图挖掘算法RMPM

3.3.1 算法的搜索空间

3.3.2 算法使用的数据结构

3.3.3 算法描述

3.3.4 子图查询

3.3.5 支持度计算

3.4 实验结果与分析

3.4.1 真实数据集上的实验结果与分析

3.4.2 模拟数据集上的实验结果与分析

3.5 极大频繁自由树挖掘实验结果与分析

3.6 本章小结

第4章 挖掘具有代表性的频繁模式

4.1 引言

4.2 背景知识

4.3 挖掘具有代表性的模式

4.3.1 相似度测量

4.3.2 FRSM算法

4.3.3 InRSM算法

4.4 实验结果与分析

4.4.1 实验设置

4.4.2 图相似度阈值对实验结果的影响

4.4.3 相似度测量函数对聚类质量的影响

4.4.4 权重系数对MN_SIM相似度测量函数的影响

4.4.5 InRSM和FRSM效率对比实验

4.4 本章小结

结论

参考文献

致谢

攻读硕士学位期间发表的学术论文

声明