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

频繁子图已成为数据挖掘领域研究的热点之一。在经典的Apriori算法的基础上,提出了一种图挖掘的新算法Apriori-Graph。首先给出了一种新的、用于计算图的邻接矩阵规范编码的结点排序策略,大大降低了求图规范编码的复杂度,并可加速子图规范编码序列匹配的速度。其次,对候选子图的生成进行了规范。最后,针对频繁性检验这一瓶颈过程,给出了若干性质,从而较大地降低了候选子图频繁性判断的代价。实验结果表明,Apriori-Graph算法具有较高的挖掘效率。

New efficient width-first algorithm for mining frequent subgraph

Frequent subgraph mining is an active research topic in the data mining field.Based on the 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.