浅析一种基于前缀节点的频繁子图挖掘算法

1、浅析一种基于前缀节点的频繁子图挖掘算法    Abstract:Based on the prefix node method in frequent tree mining algorithms, adopting core-braches-connecting vector partition on graphs, this paper provided a new algorithm CBE. The CBE algorithm could accomplish canonical determining in constant time on c

2、andidate pattern graphs expanded from branches. Performance testing proves that the efficiency of subgraphs mining is improved by CBE algorithm. Key words:data mining; frequent subgraph; isomorphism class; canonical form; prefix node 在化学信息学、生物信息学、 网络 结构分析等领域,频繁子图挖掘算法是一个 热点 研究问题。与其他的频繁模式挖掘算法类似,一般的频繁子

3、图挖掘算法都分为候选模式生成和模式频繁判定两步1。在频繁子图的挖掘过程中,会生成大量的候选模式图。对每一个新产生的候选模式图,在进行频繁判定之前,都要首先判断它与前面产生的模式图是否同构。而图的同构判定是一个复杂度介于P与NP之间的问题25。受此限制,目前出现的子图挖掘算法的效率还不是很高,特别是与频繁子树挖掘算法相比。频繁子树的挖掘也会生成大量的候选模式树,但基于一种称为前缀节点的方法,可以在常数时间内解决候选模式树的同构判定问题。 本文针对这种情况,基于频繁子树挖掘算法中的前缀节点思想,提出了一种在部分候选模式图上能够在常数时间内完成同构判定的方法,并以此方法为核心给出了一种新的高效频繁子

4、图挖掘算法图核分支扩展算法(CBE)。 1 基于次前缀节点的频繁子树挖掘算法 频繁子树挖掘算法分为候选模式子树生成和子树频繁判定两步。候选模式子树可以通过在一棵频繁子树的任一个节点上扩展任一条边得到,但这种扩展会产生大量同构的模式子树。一种朴素的筛选方法是检查新生成的模式子树是否与先前生成的某棵模式子树同构。若存在同构的模式子树,则当前扩展是无效的;否则当前扩展生成一棵新的有效的模式子树。因此,候选子树的生成,本质是要遍历所有的子树同构类。对每一类同构的子树,只需生成一棵代表子树即可。这棵代表子树也成为该同构类的规范形式。同构类的规范形式有多种不同的定义方法,在子树挖掘算法中,通常的做法是6:

5、 在一棵树T中,用深度元组t=(d,le,lv)表示一条边e。其中:d为e的终点v的深度;le为e的标记;lv为v的标记。在深度元组间可定义偏序<t:当且仅当d1>d2,或d1=d2且le1<LV2时,(D1,LE1,LV1)<T(D2,LE2,LV2)。对树T进行深度优先遍历,则可以得到不同的深度元组序列。在偏序<T的基础上,可以定义深度元组序列间的偏序<S,当且仅当:A)S2是S1的前缀;B)对S1和S2的第一个不同的深度元组T1和T2,有T1<TT2时,S1<SS2。为了讨论方便,更准确地将情况A)记做S1<S(P)S2。设树T所在同

6、构类中,在去掉一棵最小有序树的最后一条边,得到的仍是一棵最小有序树。因此要扩展得到新的最小有序树,只需在已得到的频繁最小有序树的最右路径上进行扩展。考察一棵有序树的最右路径上的一个节点v,以v为根的子树subtree(v),v的左兄弟记为presibling(v),以该左兄弟为根的子树记为subtree(presibling(v)。若深度序列l(subtree(v)为l(subtree(presibling(v)的前缀,则称v为树T的一个前缀节点。若v0为深度最小的前缀节点,则称v0为树T的最低前缀节点。称l(subtree(presibling(v)中,紧跟在前缀l(subtree(v)后的

7、深度元组t为v对应的次前缀深度元组。v0所对应的次前缀元组为树T的最低次前缀元组t0。如图1所示,树T的前缀节点有v6、v0,次前缀深度元组为边(v7,v8),(v1,v5)对应的深度元组。最低前缀节点为v0,最低次前缀深度元组为边(v1,v5)对应的深度元组t0=(2,x,c)。 <LV2时,(D1,LE1,LV1)<T(D2,LE2,LV2)。对树T进行深度优先遍历,则可以得到不同的深度元组序列。在偏序<T的基础上,可以定义深度元组序列间的偏序<S,当且仅当:A)S2是S1的前缀;B)对S1和S2的第一个不同的深度元组T1和T2,有T1<TT2时,S1<

8、SS2。为了讨论方便,更准确地将情况A)记做S1<S(P)S2。设树T所在同构类中,在 在一棵最小有序树的最右路径上扩展,有以下结论,当且仅当:a)最低深度元组t0存在,新增的深度元组t tt0,且t tt(t为t在最右路径上的左兄弟元组);b)或t0不存在,且ttt,则扩展得到的必定是一棵最小有序树6,7。简单证明如下:对于最右路径上的前缀节点,由深到浅记为vi,vi-1, ,v0,所对应的次前缀深度元组为ti,ti-1,t0。由次前缀深度元组的定义易得t0tt1ttti。若添加的深度元组t tt0,则新的有序树中,subtree(vk)S subtree(presibling(vk)

9、(k=1,i)。对最右路径上的非前缀节点v,始终有subtree(vk)>S subtree(presibling(vk)。因此,扩展得到的是一棵最小有序树。若添加的深度元组t <tt0,则新的有序树中,subtree(v0)和subtree(presibling(v0)交换后,可得到更小的有序树。因此扩展得到的不是一棵最小有序树。例如图1中,扩展边(v0,v10),(v6,v12)满足条件a)b),为有效扩展;扩展边(v0,v11),(v6,v13)不满足条件b),不是有效扩展;扩展边(v9,v14)不满足条件a),也不是有效扩展。 在上述扩展方法中,若扩展边t=tt0tt,新的

10、最小有序树T的最低前缀节点仍为T的最低前缀节点v0,最低次前缀深度元组为T中紧跟在t0后的深度元组。若t =t >tt0,则新的最小有序树T的最低前缀节点为扩展边t的起点,最低次前缀深度元组为t。若t>tt0且t>tt,则新的最小有序树T不存在前缀节点和次前缀深度元组。 2 子图挖掘算法 图和树的区别在于图有回溯边。在图的深度优先遍历中,遍历边可分为回溯边和前进边。在CBE算法中,规定回溯边始终优先于前进边,即在某一个节点上,遍历完该节点出发的所有回溯边后,才能遍历该节点出发的前进边5,810。这样的遍历即图的回溯深度优先遍历。与树的深度优先遍历一样,仍用深度元组t=(d,l

11、e,lv)表示一条边e。若e是一条前进边,则d为e的深度;若e是一条回溯边,则d<0,|d|为e回溯的深度。在深度元组上重新定义偏序<t,当且仅当:(d1)补>(d2)补,或d 1=d2且le1为了利用前缀节点的思想,在对图进行深度优先遍历之前,还需要首先对图进行图核分支的划分。依次剥除图G中所有的叶边,最后剩下的连通图称为G的图核core(G)。而被剥除的所有边所组成的有根树森林,称为G的分支森林branchs(G)。CBE算法遍历一个图G时,首先对core(G)进行深度优先遍历,然后再依次对branchs(G)中的每棵子树进行深度优先遍历。这样的遍历即图G的图核分支深度优

12、先遍历。对图G进行图核分支深度优先遍历,可得到图G的图核分支三元组CBT=(l(core(G),l(branchs(G),cv)。其中:l(core(G)为图核的深度序列;l(branchs(G)为分支的深度序列;cv为分支的连接向量,由branchs(G)中每棵有根树在core(G)中的连接点序号组成,在该向量上也可按字典序定义偏序。可在图的三元组上定义偏序<G,当且仅当:l(core(G1)<Sl(core(G2);或l(core(G1)=l(core(G2),且l(branchs(G1)<Sl(branchs(G2);或l(core(G1)=l(core(G2),l(b

13、ranchs(G1)=l(branchs(G2),且cv1<CV2时,有(L(CORE(G1),L(BRANCHS(G1),CV1)<G(L(CORE(G2),L(BRANCHS(G2),CV2)。设图G所在同构类中,在 在一个最小频繁模式图G0上进行扩展。若G0的叶节点数为0(即branchs(G0)为空),或叶节点数为1 (即branchs(G0)中只有一棵路径树),则可由G0生成新的图核;否则,扩展不能改变G0的图核。如图2所示,对branchs(G0)的扩展,只能在branchs(G0)的最右分支的最右路径上进行,或在core(G0)的空节点(即没有连接分支的图核节点)上进

14、行。在branchs(G0)最右分支的最右路径上进行扩展时,必须满足:a)扩展边ttt0;b)ttt (t为t在最右路径上的左兄弟元组)。在core(G0)的空节点上进行扩展时,必须满足:c)t tt0(t0为最右分支中的第一个深度元组)。当在最右分支的最右路径上进行扩展时,若扩展后最右分支大于次右分支,则产生的候选模式图G,其连接向量不变,因此G无须进行规范化判定。图2中的扩展边(v2,v11),(v10,v12),(v1,v13),(v0,v14)都是可能的扩展边,但(v10,v12)不满足条件a),(v0,v14)不满足条件c),却不是有效扩展。扩展边(v2,v11)是有效扩展边,但扩展

15、后的候选模式图G的最右分支等于次右分支,因此需要检查G的规范形式的连接向量,才能判断G是否是一个规范化的最小模式图。 CBE算法具体描述如下: Expand(G) 输入:模式图G 输出:无 1:if G不是频繁子图then 2:return 3:if G的叶节点数为0 then 4:for G最右路径上的每个节点v do 5: for从v出发的每条回溯边t do 6:if G是最小模式图then 7:Expand(G) 8:if G的叶节点数为1 then 9:设G的叶节点为v 10: for从G的叶节点v出发的每条回溯边t do 11:if G是最小模式图 then 12:Expand(G)

16、 13:if br<S(p) br then 14: for br最右路径上每条tt t0,且t t t do 15:if br <S br then 16:Expand(G) 17:else if G是最小模式图 then 18:Expand(G) 19:else if br<S br then 20: for br最右路径上每条ttt0,且t t t do 21:Expand(G) 22:for core(G)的每个空节点v do 23: for 从v出发的每条t t t0 do 24:if G是最小模式图 then 25:Expand(G) 其中:t为扩展边对应的深度元

17、组;G=G+t为扩展得到的候选模式图;br为分支森林core(G)中的次右分支;br为core(G)中的最右分支;t0为最低次前缀深度元组;t为t在最优路径上的左兄弟深度元组;t0为br中的第一个深度元组。 在人工数据集上,不同的N、I、T组合下,三种算法的运行时间比较如图3所示。 在DTP和AID2DA99两种真实数据集上,取不同的最小支持度,三种算法的运行时间和占用内存的大小比较如图4、5所示。 由测试结果可以看出,CBE算法的运行效率比Gaston算法有近1倍的提高,比gSpan算法有近5倍的提高。另外,在测试中还发现,由于CBE算法使用出现了列表,其内存的占用与Gaston算法相近,比

18、gSpan算法要多。 4 结束语 本文提出了一种高效的频繁子图挖掘算法CBE。它将模式图分为图核、分支和连接向量,图核和分支分别用深度元组序列表示。对模式图的扩展只在图核的空节点和最右分支的最右路径上进行。在扩展中使用前缀节点的方法,要求扩展的边不能小于最低深度元组。当在最右分支上进行扩展时,若扩展后最右分支大于次右分支,则产生的候选模式图无须进行规范化判定。因此,这时能够在常数时间内得到一个有效的候选模式图,从而显著地提高挖掘算法效率,并且在人工数据集和真实数据集上的性能测试证明了这一提高。 参考文献: 1李继腾.最大频繁子图挖掘算法研究D.长沙:国防科学技术大学,2009. 2李先通,李建

19、中,高宏.一种高效频繁子图挖掘算法J. 软件 学报,2007,17(10):2469-2480. 3周杨,王峰.FSM基于子图同构和结构同构的频繁子图挖掘算法C/第二十四届中国数据库学术会议.2007:296-301. 4AGRAUAL R,STRIKAUT R.Fast algorithm for mining association rule in large databasesC/Proc of the 20th International Conference on Very Large Data Bases.1994:487-499. 5INOKUCHI A,WASHIO T,MOT

20、ODA H.An apriori-based algorithm for mining frequent substructures from graph dataC/Proc of the 4th European Conference on Principle of Data Mining and Knowledge Discovery.London:Springer-Verlag,1998:13-23. 6NIJSSEN S,KOK J.A quickstart in frequent structure mining can make a differenceC/Proc of ACM

21、 SIGKDD of International Conference on Knowledge Discovery and Data Mining.2004:647-652. 7CHI Yun,MUNTZ R R,NIJESSN S,et al.Frequent subtree mining an overviewJ.Fundamenta Infomaticae:Special Issue on Graph & Tree Mining,2005,66(1-2):161-198. 8KURAMOCHI M,KARYPIS G.Frequent subgraph discoveryC/Proc of International Conference on Data Mining.San Jose:s.n.,2001:313-320. 9YAN Xi-feng,HAN Jia-w Ei .gSpan:graph-based substruct