论文部分内容阅读
近年来,数据挖掘在科学研究和实际应用领域都取得了巨大的成功。随着数据挖掘技术的发展和实际应用的需要,数据挖掘的对象逐渐由传统的项目集数据扩展到了结构化的数据,如路径,树,图等复杂结构,因此,图形挖掘成为了当前数据挖掘研究领域的热点。和传统数据集挖掘中频繁项目集是挖掘任务的基础一样,图形挖掘任务中,频繁子图(即图集数据库中最频繁的子结构)是图形挖掘的基础。但是频繁子图挖掘的复杂性要远远大于项目集挖掘,因为频繁子图挖掘的核心问题是同构测试,而图的同构测试已经被证明是一个NP完全问题。随着研究的深入,迄今为止人们已经提出了许多高效和可伸缩的频繁子图挖掘算法,如gSpan, Gaston等.但是,目前的算法大多都是对有标记图进行数据挖掘,对部分标记图要么无法挖掘,要么没有对部分标记图做特定优化处理,为此,本文提出了一种基于部分标记图的频繁子图挖掘算法:PLSG(Partially Labeled based Structural Graph Mining)。PLSG算法提出了部分标记图的精确匹配和模糊匹配的概念,并据此对部分标记图进行预处理,首先将部分标记图转换为全部标记图,再对其进行频繁子图挖掘。为了达到算法的高效性和可伸缩性,PLSG使用了很多优化方法,诸如用规范化标记避免子图同构测试、采用边→路径→树→图的候选子图生成策略达到尽早剪枝等。本文通过大量的实验结果表明:(1)对部分标记图挖掘时,无论是精确匹配还是模糊匹配,PLSG都能对部分标记图进行高效的挖掘。(2)对全部标记图进行挖掘时,PLSG算法在一定程度上优于Gaston算法。