基于对gSpan改进的有向频繁子图挖掘算法

作     者：周溜溜 业宁 

作者机构：南京林业大学信息技术学院南京210037 

出 版 物：《南京大学学报（自然科学版）》 (Journal of Nanjing University（Natural Science）)

年 卷 期：2011年第47卷第5期

页      面：532-543页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(30671639) 江苏省自然科学基金(BK2009393) 江苏省青蓝工程学术带头人项目 

主　　题：有向图挖掘 gSpan 频繁子图 适用性扩展 

摘      要：提出的新算法对gSpan算法做了适用性改进,算法所采用的图编码技术与传统的频繁子图挖掘(FSG),快速频繁子图挖掘(FFSM),基于先验的图挖掘(AGM)等算法对图结构的编码均不同,由于对有向图进行了新的二维特征定义,因此可使算法适用范围有效地扩展至对有向图的学习,称之为基于对gSpan改进的有向频繁子图挖掘算法(DFSS);因目前为止,一系列频繁子图的挖掘大都是基于无向图上的知识发现,对直接作用于有向图的挖掘尚且很少.并且所设计算法较先前基于Apriori思想的FSG,AGM等一系列频繁图挖掘算法,在时间复杂度方面有了一定程度的改进,使得挖掘效率得以提升;实验结果表明在不损失挖掘完整度的前提下,其效率是FFSM算法的70～80倍.