关键词:数据挖掘;频繁子图;同构类;规范化形式;前缀节点
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
在化学信息学、生物信息学、网络结构分析等领域,频繁子图挖掘算法是一个热点研究问题。与其他的频繁模式挖掘算法类似,一般的频繁子图挖掘算法都分为候选模式生成和模式频繁判定两步[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
在上述扩展方法中,若扩展边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
在一个最小频繁模式图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中的第一个深度元组。
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]//第二十四届
中国论文网(www.lunwen.net.cn)免费学术期刊论文发表,目录,论文查重入口,本科毕业论文怎么写,职称论文范文,论文摘要,论文文献资料,毕业论文格式,论文检测降重服务。 返回电子论文列表