单图中子图大小相关的近似频繁子图挖掘

论文摘要

图数据是大数据时代中十分重要的角色,其在各种场景中有着十分广泛的应用,如社交网络、蛋白质交互网络、合作关系网络等。本文主要研究的是图数据上的模式挖掘,研究目的是实现从图数据中挖掘频繁近似子图。目前在频繁子图挖掘领域的工作已经有很多,然而已有的工作要么没有考虑子图与其出现的相似程度,要么在考虑相似程度时忽略了候选子图大小对相似程度的影响。然而,根据人的感知,不同大小的图应具有不同程度的容错性,类似的,子图的大小对计算子图与其出现的相似程度也会有十分重要的影响。因此,本文设计了子图大小相关的频繁近似子图挖掘策略,提出了一种新的、快速的频繁近似子图挖掘算法。算法不仅在计算子图的频繁程度时考虑与子图的近似出现,同时在计算子图与其出现的相似程度时,考虑子图的大小对近似程度的影响。首先,对于候选频繁近似子图的生成,本文设计了一种不遗漏的遍历方式,遍历给定单图的全部子图。为了提高遍历的效率,降低候选频繁近似子图的数量,对频繁近似子图的大小上限进行了估算,并利用大小上限过滤遍历中的子图,对遍历过程进行剪枝。实验证明了子图的上限对遍历效率具有提升效果。其次,为提高算法效率,本文归纳出对于所有的频繁近似子图,其支持度符合“局部反单调性”,且在文中给出了证明。并利用该性质,设计了对候选频繁近似子图进行剪枝的策略,降低了需要进行近似匹配的候选子图的数量。实验证明,该性质对可以显著提升算法效率。再次,对于候选频繁近似子图的近似子图生成,本文设计了基于点和边的删除策略的近似子图生成算法。并通过理论证明,仅通过统计该算法产生的近似子图在给定图中的匹配,并计算这些匹配的支持度,可以得到与统计候选频繁近似子图的所有近似匹配相同的支持度。接着,通过与已有算法的实验对比,证明本文算法在效率上具有明显优势,同时,通过简单案例说明,本文算法能发现传统频繁子图挖掘算法无法发现的频繁子图,进一步表明在挖掘频繁子图时考虑近似关系,与子图大小对近似程度的影响的必要性。最后,修改本文算法,提出了针对频繁闭合近似子图和频繁极大近似子图的挖掘算法,提高了本文研究的完整性,扩展了算法应用场景,并通过实验证明了两种算法的有效性。

论文目录

摘要

abstract

第一章绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.2.1 图匹配

1.2.2 频繁图挖掘FSM

1.2.3 图近似程度计算

1.2.4 频繁近似子图挖掘

1.3 相关研究的空白

1.4 论文研究内容与主要创新

1.5 论文组织结构

第二章基础概念与理论

2.1 图匹配

2.2 频繁图挖掘

2.2.1 图集合中的频繁图挖掘

2.2.2 单图中的频繁图挖掘

2.2.3 特殊的频繁子图挖掘

2.3 近似模式匹配

2.3.1 基于编辑距离的计算方式

2.3.2 基于结构的计算方式

2.3.3 基于属性的计算方式

2.4 频繁近似子图挖掘

2.4.1 近似图同构

2.4.2 近似程度计算方式

2.5 本章小结

第三章候选子图生成

3.1 问题定义

3.1.1 概述

3.1.2 定义

3.2 候选子图生成算法及改进

3.3 频繁子图大小上限

3.4 本章小结

第四章候选子图近似匹配

4.1 问题定义

4.1.1 概述

4.1.2 相关定义

4.2 近似子图生成

4.3 近似子图匹配

4.4 支持度计算

4.5 本章小结

第五章特殊子图的挖掘

5.1 问题定义

5.2 频繁闭合近似子图挖掘

5.3 频繁极大近似子图挖掘

5.4 本章小结

第六章实验与分析

6.1 实验设置与数据集

6.1.1 真实数据

6.1.2 模拟数据

6.1.3 衡量指标

6.1.4 设置参数

6.1.5 对比算法

6.2普通频繁近似子图挖掘算法实验

6.2.1 剪枝策略效果

6.2.2 与AGraP-C算法对比

6.2.3 参数影响

6.2.4 频繁近似子图发现能力

6.3特殊频繁近似子图挖掘算法实验

6.3.1 算法挖掘时间对比

6.3.2 挖掘到的频繁近似子图数量对比

6.4 本章小结

第七章结论与展望

7.1 总结

7.2 下一步工作方向

参考文献

致谢

攻读硕士学位期间的学术成果

文章来源

类型: 硕士论文

作者: 窦建凯

导师: 林欣

关键词: 图数据挖掘,频繁子图挖掘,近似,剪枝,闭合近似子图,极大近似子图

来源: 华东师范大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 华东师范大学

分类号: O157.5;TP311.13

总页数: 101

文件大小: 4009K

下载量: 69

单图中子图大小相关的近似频繁子图挖掘

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢