摘 要:基于频繁子树挖掘算法中的前缀节点思想,将模式图分为图核—分支—连接向量三个部分,提出了cbe算法。对在分支上扩展得到的候选模式图,cbe算法能够在常数时间内完成规范化判定。通过实验证明cbe算法的子图挖掘效率有显著提高。
关键词:数据挖掘;频繁子图;同构类;规范化形式;前缀节点
frequent subgraphs mining algorithm based on prefix node
li hai-bo,wang yuan-zhen
(research institute of database & multimedia, school of computer science & technology, huazhong university of science & technology, wuhan 430074, china)
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 candidate 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
在化学信息学、生物信息学、网络结构分析等领域,频繁子图挖掘算法是一个热点研究问题。WwW.133229.cOm与其他的频繁模式挖掘算法类似,一般的频繁子图挖掘算法都分为候选模式生成和模式频繁判定两步[1]。在频繁子图的挖掘过程中,会生成大量的候选模式图。对每一个新产生的候选模式图,在进行频繁判定之前,都要首先判断它与前面产生的模式图是否同构。而图的同构判定是一个复杂度介于p与np之间的问题[2~5]。受此限制,目前出现的子图挖掘算法的效率还不是很高,特别是与频繁子树挖掘算法相比。频繁子树的挖掘也会生成大量的候选模式树,但基于一种称为前缀节点的方法,可以在常数时间内解决候选模式树的同构判定问题。
本文针对这种情况,基于频繁子树挖掘算法中的前缀节点思想,提出了一种在部分候选模式图上能够在常数时间内完成同构判定的方法,并以此方法为核心给出了一种新的高效频繁子图挖掘算法——图核—分支扩展算法(cbe)。
1 基于次前缀节点的频繁子树挖掘算法
频繁子树挖掘算法分为候选模式子树生成和子树频繁判定两步。候选模式子树可以通过在一棵频繁子树的任一个节点上扩展任一条边得到,但这种扩展会产生大量同构的模式子树。一种朴素的筛选方法是检查新生成的模式子树是否与先前生成的某棵模式子树同构。若存在同构的模式子树,则当前扩展是无效的;否则当前扩展生成一棵新的有效的模式子树。因此,候选子树的生成,本质是要遍历所有的子树同构类。对每一类同构的子树,只需生成一棵代表子树即可。这棵代表子树也成为该同构类的规范形式。同构类的规范形式有多种不同的定义方法,在子树挖掘算法中,通常的做法是[6]:
在一棵树t中,用深度元组t=(d,le,lv)表示一条边e。其中:d为e的终点v的深度;le为e的标记;lv为v的标记。在深度元组间可定义偏序<t:当且仅当d1>d2,或d1=d2且le1
去掉一棵最小有序树的最后一条边,得到的仍是一棵最小有序树。因此要扩展得到新的最小有序树,只需在已得到的频繁最小有序树的最右路径上进行扩展。考察一棵有序树的最右路径上的一个节点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))后的深度元组t为v对应的次前缀深度元组。v0所对应的次前缀元组为树t的最低次前缀元组t0。如图1所示,树t的前缀节点有v6、v0,次前缀深度元组为边(v7,v8),(v1,v5)对应的深度元组。最低前缀节点为v0,最低次前缀深度元组为边(v1,v5)对应的深度元组t0=(2,x,c)。
在一棵最小有序树的最右路径上扩展,有以下结论,当且仅当:a)最低深度元组t0存在,新增的深度元组t′ ≥tt0,且t′ ≥tt″(t″为t′在最右路径上的左兄弟元组);b)或t0不存在,且t′≥tt″,则扩展得到的必定是一棵最小有序树[6,7]。简单证明如下:对于最右路径上的前缀节点,由深到浅记为vi,vi-1, …,v0,所对应的次前缀深度元组为ti,ti-1,…,t0。由次前缀深度元组的定义易得t0≥tt1≥t…≥tti。若添加的深度元组t′ ≥tt0,则新的有序树中,subtree(vk)≥s subtree(presibling(vk))(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′=tt0≥tt″,新的最小有序树t′的最低前缀节点仍为t的最低前缀节点v0,最低次前缀深度元组为t中紧跟在t0后的深度元组。若t′ =t″ >tt0,则新的最小有序树t′的最低前缀节点为扩展边t′的起点,最低次前缀深度元组为t″。若t′>tt0且t′>tt″,则新的最小有序树t′不存在前缀节点和次前缀深度元组。
2 子图挖掘算法
图和树的区别在于图有回溯边。在图的深度优先遍历中,遍历边可分为回溯边和前进边。在cbe算法中,规定回溯边始终优先于前进边,即在某一个节点上,遍历完该节点出发的所有回溯边后,才能遍历该节点出发的前进边[5,8~10]。这样的遍历即图的回溯—深度优先遍历。与树的深度优先遍历一样,仍用深度元组t=(d,le,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的图核—分支深度优先遍历。对图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(branchs(g1))=l(branchs(g2)),且cv1
在一个最小频繁模式图g0上进行扩展。若g0的叶节点数为0(即branchs(g0)为空),或叶节点数为1 (即branchs(g0)中只有一棵路径树),则可由g0生成新的图核;否则,扩展不能改变g0的图核。如图2所示,对branchs(g0)的扩展,只能在branchs(g0)的最右分支的最右路径上进行,或在core(g0)的空节点(即没有连接分支的图核节点)上进行。在branchs(g0)最右分支的最右路径上进行扩展时,必须满足:a)扩展边t′≥tt0;b)t′≥tt″ (t″为t′在最右路径上的左兄弟元组)。在core(g0)的空节点上进行扩展时,必须满足:c)t′ ≥tt′0(t′0为最右分支中的第一个深度元组)。当在最右分支的最右路径上进行扩展时,若扩展后最右分支大于次右分支,则产生的候选模式图g′,其连接向量不变,因此g′无须进行规范化判定。图2中的扩展边(v2,v11),(v10,v12),(v1,v13),(v0,v14)都是可能的扩展边,但(v10,v12)不满足条件a),(v0,v14)不满足条件c),却不是有效扩展。扩展边(v2,v11)是有效扩展边,但扩展后的候选模式图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′)}
13:if br′<s(p) br then
14: for br最右路径上每条t′≥t 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最右路径上每条t′≥tt0,且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′为扩展边对应的深度元组;g′=g+t′为扩展得到的候选模式图;br′为分支森林core(g)中的次右分支;br为core(g)中的最右分支;t0为最低次前缀深度元组;t″为t′在最优路径上的左兄弟深度元组;t0′为br中的第一个深度元组。
在cbe算法中,要判断一个模式图g是否为频繁子图,需要对g和数据库d中的每个数据图d进行子图判定。对由g扩展得到的模式图g′,只有当g在d中出现时,g′才可能在d中出现。cbe算法采用出现列表ol(g)记录模式图g在数据库中的每个出现。对每个出现ol∈ol(g),ol=(tid,i1,i2,…,ik)。其中:tid是d中数据图d的序号,i 1,i2,…,ik是g的每个节点在d中对应的序号。要判断g的扩展g′是否频繁,需要求得ol(g′)。根据ol(g),可以在o(mn)时间内求得ol(g′)。其中m为ol(g)中的出现数,n为数据库d中数据图d的最大边数。因此,尽管子图判定是一个复杂度为np的问题,但在子图挖掘算法中,可以在多项式时间内完成判定,只需提供较大的存储代价即可。
3 测试结果
本文进行性能测试的平台是一台安装2.2 ghz的intel酷睿2 cpu,4 gb内存的pc机,操作系统为redhat linux 9.0。算法用c++语言实现,编译器为g++ 3.3.2,代码优化级别为-o3。本文将cbe算法与子图挖掘gspan和gaston算法进行比较[8,11]。
本文采用了人工数据集和真实数据集进行测试。人工数据集采用文献[5]中的图数据库生成器产生,使用的参数为:数据图个数d=10 000;预定义子图数目l=200;最小支持度σ= 0.01;标记数目n=5,10;预定义子图平均边数i=5,7;数据图平均边数t=10,20,40。真实数据集采用了两个真实的分子结构数据库:dtp和aid2da’99。dtp含有422个分子结构图,aid2da’99含有42 689个分子结构图。
在人工数据集上,不同的n、i、t组合下,三种算法的运行时间比较如图3所示。
在dtp和aid2da’99两种真实数据集上,取不同的最小支持度,三种算法的运行时间和占用内存的大小比较如图4、5所示。
由测试结果可以看出,cbe算法的运行效率比gaston算法有近1倍的提高,比gspan算法有近5倍的提高。另外,在测试中还发现,由于cbe算法使用出现了列表,其内存的占用与gaston算法相近,比gspan算法要多。
4 结束语
本文提出了一种高效的频繁子图挖掘算法cbe。它将模式图分为图核、分支和连接向量,图核和分支分别用深度元组序列表示。对模式图的扩展只在图核的空节点和最右分支的最右路径上进行。在扩展中使用前缀节点的方法,要求扩展的边不能小于最低深度元组。当在最右分支上进行扩展时,若扩展后最右分支大于次右分支,则产生的候选模式图无须进行规范化判定。因此,这时能够在常数时间内得到一个有效的候选模式图,从而显著地提高挖掘算法效率,并且在人工数据集和真实数据集上的性能测试证明了这一提高。
参考文献:
[1]李继腾.最大频繁子图挖掘算法研究[d].长沙:国防科学技术大学,2009.
[2]李先通,李建中,高宏.一种高效频繁子图挖掘算法[j].软件学报,2007,17(10):2469-2480.
[3]周杨,王峰.fsm——基于子图同构和结构同构的频繁子图挖掘算法[c]//第二十四届
