图的频繁子结构挖掘方法研究
Research on Graph Frequent Substructure Mining Method
随着互联网、数据库等信息技术的快速发展,网络上产生并积累了大量Xml文档、Web网页、化学化合物、生物分子等半结构化数据,这些结构复杂的数据往往隐藏了丰富的知识.频繁模式挖掘可以发现潜在的规律和模式,在实际应用中被广泛使用.图作为一种重要的数据结构,能够表达丰富的语义,适合用于半结构化数据建模.对半结构化数据的频繁模式挖掘可以转化为对图的频繁子结构挖掘.图的频繁子结构挖掘主要分为树(无环图)的频繁子结构挖掘和图(有环图)的频繁子结构挖掘两个方向.对于树的频繁子结构挖掘,目前主要有基于"候选子结构-计算支持度"和基于"投影数据库"思想的两类算法.本文针对基于"候选子结构-计算支持度"思想的相关算法不能生成所有候选子树而造成频繁子树信息遗漏,以及输出大规模且带有冗余信息的频繁子树进而影响后续分析效率的不足分别提出了GAST(Get All SubTrees)算法和MCRP(Mining Coverage Pattern)算法.GAST算法采用宽度孩子数编码方式对树中的结点进行编码,并在此基础上采用最大前缀编码序列进行边扩展生成所有候选子树,避免了信息的遗漏.MCRP算法在GAST算法基础上,只输出满足-覆盖条件的频繁子树,即覆盖模式,降低了输出频繁子树信息的冗余.对于图的频繁子结构挖掘,目前主要是基于"候选子结构-计算支持度"思想的算法.该类算法在计算候选子图支持度时涉及到子图同构判断,导致算法时间效率较低.针对这类算法的不足,本文借鉴树的频繁子结构挖掘中基于"投影数据库"的思想,提出了MFSGBPC(Mining Frequent SubGraph Based on Projection Coding)算法用于挖掘频繁子图.该算法将计算候选子图支持度的操作转换为了计算候选结点支持度的操作,避免了子图同构判断操作,在一定程度上提高了时间效率.理论分析和实验表明,与传统频繁子图挖掘算法相比,本文所提出的MCRP算法更加有效,能生成所有候选子树且避免冗余;MFSGBPC算法避免生成候选子图和计算候选子图支持度,在效率上有所提升.
- 作者：
- 李洪旭
- 学位授予单位：
- 重庆邮电大学
- 专业名称：
- 计算机科学与技术
- 授予学位：
- 硕士
- 学位年度：
- 2017年
- 导师姓名：
- 夏英
- 中图分类号：
- TP311.13
- 关键词：
- 图的子结构；频繁子树；频繁子图；宽度孩子数编码；最大前缀编码序列；覆盖模式；投影数据库
- substructure of graph； frequent subtree； frequent subgraph； width and child number coding； maximum prefix coding sequence； coverage pattern； projection database