宽度优先的频繁子图高效挖掘新算法  

New efficient width-first algorithm for mining frequent subgraph

作　　者：王映龙[1] 杨炳儒[1] 宋威[1] 宋泽锋[1] 

机构地区：[1]北京科技大学信息工程学院

出　　处：《系统工程与电子技术》2008年第3期548-552,共5页Systems Engineering and Electronics

基　　金：国家自然科学基金资助课题(60675030)

摘　　要：频繁子图已成为数据挖掘领域研究的热点之一。在经典的Apriori算法的基础上,提出了一种图挖掘的新算法Apriori-Graph。首先给出了一种新的、用于计算图的邻接矩阵规范编码的结点排序策略,大大降低了求图规范编码的复杂度,并可加速子图规范编码序列匹配的速度。其次,对候选子图的生成进行了规范。最后,针对频繁性检验这一瓶颈过程,给出了若干性质,从而较大地降低了候选子图频繁性判断的代价。实验结果表明,Apriori-Graph算法具有较高的挖掘效率。Frequent suhgraph mining is an active research topic in the data mining field. Based on tne classical Apriori algorithm, a novel graph mining algorithm, Apriori-Graph, is proposed. Firstly, to lower the complexity of computing canonical codes of the adjacency matrix of graphs, a new vertex sorting strategy is introduced. Meanwhile, the sorting strategy can also speed the matching process of sequences of canonical codes. Secondly, aiming at the frequent subgraph, the process of generation for candidates is standareized. Finally, to ease the burden of frequency-checking, which is the bottle-neck of Apriori-inspired algorithms, several properties are discussed. Thus, the cost of frequency-checking is lowered. Experimental results show the proposed algorithm is efficient.

关 键 词：数据挖掘 频繁子图 邻接矩阵 规范编码 APRIORI算法 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]