没有合适的资源?快使用搜索试试~ 我知道了~
频繁子图挖掘的Gaston工具及其效果
理论计算机科学电子笔记127(2005)77-87www.elsevier.com/locate/entcs频繁子图挖掘的Gaston工具Siegfried Nijssen和Joost N. 角LIACS,Universiteit Leiden,Niels Bohrweg 1,2333 CA Leiden,TheNetherlandssnijssen@liacs.nl摘要给定一个图的数据库,结构挖掘算法搜索满足最小频率、最小置信度、最小兴趣和最大频率等约束的所有子结构。为了提高频繁子图挖掘的效率,我们提出了增加搜索步骤的复杂性。我们提出了GrAph/Sequence/Tree extractiON(GASTON)工具它通过首先搜索频繁路径,然后是频繁自由树和最终循环图来实现这一思想。我们给出了大型分子数据库的结果。保留字:频繁子图,数据挖掘1介绍近年来,对图、树、分子、XML文档和关系数据库等结构的数据挖掘吸引了大量的研究。尤其是最近发现所有频繁子结构的思想导致了大量用于挖掘路径、树和图的专门算法。频繁的子结构提供了有关数据库的有趣信息。这些信息可以以多种不同的方式使用,例如用于分类。例如,图1显示了在HIV抑制剂数据库中常见但在另一个数据库中不常见的分子片段,从而提供了区分两个数据库的特征;最左上方的片段是AZT(一种核苷逆转录酶抑制剂)的主要成分,并用于许多抗HIV治疗药物中。我们的工具完全自动计算这些片段。1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.12.03978S. Nijssen,J.N.Kok/Electronic Notes in Theoretical Computer Science 127(2005)77图1.一、分子数据库的实验表明,在这样的数据库中,最大数量的频繁子结构实际上是自由树。自由树是比一般的循环图简单得多的结构,并且存在有效的算法。因此,我们将频繁路径,树和图挖掘器集成到一个工具中称为GASTON,以获得效率。开发GASTON工具的主要挑战是如何将发现过程分为几个阶段。理想情况下,该工具在面对自由树数据库时应该表现得像一个专门的自由树挖掘器,但也应该能够有效地处理图形数据库。我们的频繁结构挖掘主页http://hms.liacs.nl/包含更多的参考资料、概述论文和我们工具的源代码2基础我们将只简单地讨论数学上的定义:这些定义与其他关于频繁结构挖掘的论文中使用的定义类似,例如[2,13,14,15]。 一个标号图G由一个有限的节点集V,一个边集E<$V×V和一个标号函数l组成:V<$E→ L,它指定从L到所有边和节点的标签我们只考虑无向图,也就是说,(v1,v2)与(v2,v1)是同一条边。当图G与图GJ是子图同构时,我们用G<$GJ表示。我们假设数据库D由一组图组成。图G在D中的频率定义为freq(G,D)= #{GJ∈ D|G<$GJ},图的支集由support(G,D)= freq(G,D)/|D|. 任务S. Nijssen,J.N.Kok/Electronic Notes in Theoretical Computer Science 127(2005)7779图二. 图的精化是找到所有支持(G,D)≥minsup的图,对于用户指定的某个预定义阈值minsup一个重要的性质是G1<$G2意味着freq(G1,D)≥freq(G2,D)。这个性质的一个结果是,任何包含一个(较小)图的(大)图不经常的,也不能经常。这个Apriori属性是许多频繁结构挖掘算法的基础。使用此属性从搜索空间中删除图形的过程称为(基于频率的)修剪。如果对于两个连通图G1<$G2,不存在G3使得G1<$G3<$G2,我们称G2为G1的一个加细。我们可以证明G2是G1的精化,仅当存在一个G3≠G2,其中G3通过以下两个运算之一从G1• 节点细化:在G1上添加一个新节点,该节点通过一条新边(有时也称为前向边)连接到G1• 循环闭合细化:在G1上,在已经通过路径连接的节点之间添加一条新的边(有时也称为后向边)。将[2]中的术语扩展到循环图,我们将对图进行细化的操作称为腿。图G=(V,E,l)的一条节点精化腿由V中的一个节点、一个边标号和一个节点标号组成。节点细化分支的示例是图2中的l1、l2、l3和l4。一个周期结束精炼段由两个不同的路径L5循环图L4GL3a a av1v2v31LL2l1 =(v1,,a)l2 =(v3,,a)l3 =(v2,,a)免费树木80S. Nijssen,J.N.Kok/Electronic Notes in Theoretical Computer Science 127(2005)77DFGraphMiner(一个图 代码C,一条腿l,一组 腿L)(1)C:=ρ(C,l)(2)如果CJ不是正则,则返回J(3)输出图CJ(4) L :={l|L 是C的一个必要支,支撑(ρ(C,l),D)≥minsup,lJ∈L,或lJ连接到由l引入的节点,如果l是节点精化}(5) 对于所有的lJ∈LJ做DFGraphMiner(CJ,lJ,LJ)J JJ J J JJ图三. 深度优先图挖掘算法V中的节点和边标签。一个例子是图2中的腿15。精化算子ρ(G,l)通过添加边l来精化图G。图2中图形之间的边缘对应于细化步骤。注意,对于图G的腿l1和l3,l3也是ρ(G,l1)的腿,而l1是ρ(G,l3)的腿。实际上,ρ(G,l1)中唯一不是G的分支的分支是连接到由l1引入ρ(G,l1)中的节点的分支。进一步注意,由于G中的自同构,两条腿l1和l2将图G精化为同构图。我们可以证明,对于每个图,同构图可以使用一个节点精化序列,然后是一个闭合精化序列来构造。图3中给出了深度优先图挖掘算法的概述。使用代码来表示图形。图代码是一个字符串,它明确地定义了一系列细化步骤,这些步骤导致某个图。图码的k-前缀是仅包含由该码定义的前k个细化步骤的码已经提出了不同的码,其中DFS码(在gSpan [15]中),邻接矩阵(在FFSM [6]中) 和具 有回溯 符号的 树码( 在FreeTreeMiner [2] 和TreeMiner [16]中)。为了确保算法不发出两个同构图,在行(2)中,确定对应于图G的当前代码CJ是否是图G的所有可能代码中的最低(或最高)代码;因此,图挖掘算法仅输出规范代码中的图。如果它的代码不是规范的,则图不会进一步细化。为了保证搜索仍然可以潜在地考虑所有可能的图,图挖掘器中使用的图代码因此应该具有这样的属性,即规范代码的每个k前缀也是规范的。为了限制算法必须考虑的分支数量,大多数深度优先矿工都会不断地维护一组可行分支。利用基于频率的修剪原理,一旦发现一条腿是不频繁的,则该腿不应被视为任何细化图中的腿。因此,在行(4)中,仅考虑是先前图的腿或者连接到最后添加到图的节点的腿。为了获得所有可能的腿S. Nijssen,J.N.Kok/Electronic Notes in Theoretical Computer Science 127(2005)7781如果一个新的节点可以被添加到一个新的节点,则有必要通过数据库传递图CJ对于每一次出现,都应该确定新节点的分支。对于算法的正确性来说不需要但对其性能至关重要的条件是第(4)行的第一个条件,该条件规定仅应计算必要的支路并将其添加到LJ。如果在当前图代码的所有后代中,CJ,则至少有一个规范图码只能通过应用由该分支定义的精化来获得。理想情况下,这个条件可以在常数时间内计算,并且通过立即应用每个必要的分支l得到的代码ρ(CJ,l)也是规范的:在这种情况下,可以删除第(2)行中的测试,并且每个图的支持度将被精确计算一次。通过将搜索分为三个阶段,我们在许多情况下避免了行(2)的检查。更确切地说,我们对自由树进行建模,以便可以在恒定时间内确定必要的分支。此外,所有这些腿都是典型的细化。3枚举为了增加复杂性,我们将介绍我们用于每类结构的规范字符串。路径枚举的主要问题是路径可以有两个方向,例如:axaxb和bxaxa。每条路径都有两个潜在的前代,可以通过删除每个端点来获得。在这样得到的两条路径中,我们只考虑从相反方向删除节点的边。然后,我们定义这两个代码中字典上最低的字符串是代码的唯一前身。然而,不幸的是,我们将看到路径的每一条腿都是自由树挖掘阶段的必要腿。因此,不可能预先修剪行(4)中的分支;因此,一些路径将被评估两次。 在行(2)中,路径被认为如果它是从它的前身代码中增长出来的,那么它就是规范的。如果此前驱是对称的,则可以将类似的支路添加到两个端点,没有结构上的原因来优先选择一个端点,只有连接到最近添加的节点的分支是规范的我们在这里定义的自由树代码是基于[1]和[12]独立提出的根树代码,并且与[10]中提出的无标记自由树方法有很强的相似性。每个有根树都可以用深度序列编码,例如82S. Nijssen,J.N.Kok/Electronic Notes in Theoretical Computer Science 127(2005)77不规范:0xb1xa2xb2xb3xb2xa1xa2xb3xb2xb0 b1xa2xb3xb2xa2xb1xa2xb3xb2xbBX一XXX一<一Canonical:XXXBxBB ab b a2xa0 xb1xa2xb3xb2xb2xa1xa2xb3xb2xb 1xa3xbXBB下一个前缀节点最右路径前缀图四、一个无序的有根树,它的一些深度序列和腿在图4中给出。树的深度序列是通过执行前序深度优先遍历获得的;每次第一次访问一个节点时,首先发出它的深度,然后是进入该节点的边的标签,最后是该节点的标签;我们称这种组合为深度序列元组。显然,深度序列取决于访问树中节点的子节点的顺序。对于一棵无序的有根树,规范深度序列被定义为该树的所有可能深度序列中字典上最高的深度序列作为对无序根树的细化,它只考虑连接到树的最右边路径的分支,如图4所示。一条腿是否可以连接到最右边的路径可以在常数时间内使用下一个prefix节点和新节点的左兄弟节点来确定。对于最右边路径的每一个分支,都有一个对应的深度元组,它将被附加在深度序列之后。这个新的元组可能不会高于下一个前缀节点的元组,这是通过考虑深度序列的最大子集来定义的,该最大子集是对应的左兄弟子树的前缀。此外,新节点可能没有比其左兄弟节点更高的标签。我们可以证明,通过只考虑立即产生规范深度序列的分支,不会丢弃以后需要作为细化的分支。例如,如果一条腿是在其他几个细化步骤之后添加的,则其节点标签必须仍然低于或等于其左兄弟节点的标签。因此,人们可以有效地描述必要的腿。为了在自由树枚举中使用这些原则,我们使用以下设置。 首先,对于每个自由树,我们定义一个路径前导,如下所示。 自由树的一个著名性质是可以指出一个(双)-中心;如果树中的任何最长路径具有奇数长度,则自由树具有由该路径上的两个中间节点组成的双中心;否则树具有中心(见图5)。一棵中心树可以被看作是一棵单根树,一棵双中心树可以被看作是两棵独立的有根树,它们的根是相互连接的。现在考虑所有从(每个)树的根开始的最大长度的有向路径。从这些最大路径中的每一个代码S. Nijssen,J.N.Kok/Electronic Notes in Theoretical Computer Science 127(2005)7783BCCentre/bicentrecTaXaXxB XBxXB XB XBX B XBbXx一一Xx一X一XC骨干字符串:bxbxbbxbxc骨干字符串:bxbxabxbxb骨干:bxbxbxbxc骨干:公司简介图五. 自由树、(双)中心和主干可以获得由节点和边上的标签组成的。 在中心树中,字典上最高的两个路径码,出现在只有共同根的路径中,称为主干串自由之树 在双中心树中,两个根树中的每一个中的字典上最高的路径码被定义为该根树的主干串。通过将一个主干串的反向与另一个主干串连接起来,得到一条路径,我们称之为自由树的主干。我们安排我们的过程,使这条路是自由树的前身。为了细化给定的路径,我们使用以下想法。首先,通过移除中间两个节点之间的边缘(在奇数长度路径的情况下)或通过移除单个中间节点(在偶数长度路径中)将路径分成两部分每个生成的路径都是有根树。使用深度序列的原理,为这些初始根树中的每一个生长根树;通过最终再次组合根树,获得自由树。为了保证自由树只从其主干路径生长,不允许对每个根树进行细化,这将导致最终自由树中的不同主干。为了严格地将频繁图发现过程划分为多个阶段,我们只考虑最后一个阶段中的循环闭合细化所有的循环闭包细化连接树中的两个现有节点;在我们的设置中,在前两个阶段,所有频繁闭包的集合总是树立政治意识一旦应用了这样的闭包,树就变成了循环图。我们通过连接两个独立的代码来定义循环图的代码。第一个代码由对应于自由树的深度序列组成这个自由树是图的生成树。 序列中的每个元组在自由树中引入一个新的节点;树的节点可以按照它们在这个序列中的出现顺序进行编号。代码的第二部分由一个形式为(vi,vj,l)的元组序列组成;每个元组定义了两个与边相连的节点vi百分之十五246.67s3,637百分之十295.77s12,283百分之五596.21s12,751见图9。 NCI'99中AID2DA 99活性物质与化合物之间的差异代表了广泛的分子,我们有兴趣发现活性化合物的常见片段,这些片段在总NCI数据库中具有显著不同的支持。我们对AID2DA99的已知活性化合物进行了该实验。结果总结见图9。6结论GASTON工具可以在树和图数据库中找到所有频繁的子结构。它是一个有趣的工具,具有非常有竞争力的运行时间,特别是对于大型分子数据库。该工具的背后是一种创新的算法,它可以在许多复杂性不断增加的阶段中找到频繁的子结构。该工具的未来工作包括结果的智能修剪。秒Number秒秒秒Number秒Number秒S. Nijssen,J.N.Kok/Electronic Notes in Theoretical Computer Science 127(2005)7787引用[1] T. Asai,H. Arimura,T. Uno和S.中野发现大型无序树中的频繁子结构。九州大学技术报告,(216),2003年。[2] Y.奇,Y.扬河,巴西-地R.孟茨HybridTreeMiner:一个高效的挖掘频繁根树和自由树的算法。2004年第16届科学与统计数据库管理国际会议(SSDBM)论文集[3] L. Dehaspe,H. Toivonen和R. D.王 寻找化合物中常见的亚结构。 在SIGKDD会议记录,第30[4] M. R. Garey和D. S.约翰逊计算机和棘手性:NP完备性理论指南,1979年。[5] H.赫塞利角Borgelt和M. R. 贝特霍尔德 大规模挖掘具有通配符的分子片段。在智能数据分析的进展V,第380-389页[6] J. Huan,W. Wang和J. Prins。存在同构时频繁子图的高效挖掘。《ICDM会议记录》,2003年。[7] A.猪口湾Washio和H.元田从图中完全挖掘频繁模式:挖掘图数据。机器学习50(3),第321-354页,2003年[8] M. Kuramochi和G.卡瑞皮斯频繁子图发现。在ICDM会议记录中,第313-320页[9] B. D.麦凯实用图同构30:45[10] S. Nakano和T. Uno.自由树的一个简单常数时间枚举算法。见IPSJ SIGNotes AL出租,编号091[11] 国家癌症研究所(NCI)。DTP/2D和3D结构信息,http://cactus.nci.nih.gov/ncidb2/download.html网站。1999年[12] S. Nijssen和J.N.阿角频繁无序树的有效发现。第一届国际挖掘图、树和序列研讨会,第55-64页[13] L. D. Raedt和S.克莱默层次版本空间算法及其在分子片段搜索中的应用。在第十七届IJCAI会议记录中,第853[14] 联合 RückeertandS. Kramer. Fre eet reetredi s coveryingraph数据。InSpeciaITrackonDataMining,ACM Symposium on Applied Computing,第564-570页,2004年。[15] X. Yan和J.韩CloseGraph:挖掘封闭的频繁图模式。在SIGKDD会议记录中,第286-295页[16] M.扎基有效地挖掘森林中的频繁树。在SIGKDD会议记录中,第71-80页,2002年。
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)