一种高效频繁子图挖掘算法.2007,18(10)_2469-2480

格式：pdf
大小：403.11 KB
文档页数：12

下载文档原格式

/ 12

频繁子图挖掘算法的应用分类

频繁子图挖掘算法的应用分类作者：吴成凤来源：《电脑知识与技术》2020年第29期摘要：频繁子图挖掘属于数据挖掘领域的一部分，越来越受到研究学者的广泛应用，目前已经成功应用于生物学、化学、社会学等领域。

频繁子图算法的操作是从给定的图数据库中，根据同构测试及支持度计算判断出频繁子图。

本文整理出国内外学者基于频繁子图的应用文献。

根据文献，对这些应用进行分类，列表整理出各个应用领域的数据集的开源地址和图的顶点及边的标识含义。

关键词：频繁子图挖掘;应用场景;顶点;边中图分类号：TP311.12 文献标识码：A文章编号：1009-3044（2020）29-0040-021 引言在数据挖掘的领域中，频繁子图挖掘算法越来越受到国内外研究学者的关注。

频繁子图将各种数据处理成顶点到顶点的逻辑关系的表示，在该模型[1]中，顶点和对应的边关系可以具有与它们相关联的标签，这些标签不是唯一的。

使用这样的图表示，频繁模式的问题变成了在整个图上寻求频繁出现子图的问题，运用频繁子图算法挖掘其潜在的价值。

频繁子图挖掘算法即在给定的图中根据设定的支持度阈值，寻找出同构子图大于等于给定支持度阈值的子图。

频繁子图算法的发展历经二十年，基于频繁子图的应用也越来越广泛。

2 运用场景在由顶点和边构成的图中，顶点有其分类的标识，边亦有其分类的标识，我们需要在给定的图数据库中寻找出顶点标识和标识对应一致的子图，计算出支持度，若一旦支持度超过给定的阈值，便输出其子图，其子图便是一个频繁子图。

Lin W[2]等人认为频繁子图挖掘问题分为两个方面：在一个大图的不同区域挖掘子图适用于社交网络分析等领域;在大规模图集中挖掘子图适用于生物信息学和计算药理学等领域。

图集上的挖掘是指在多张图的图数据库中挖掘这些图中共现的子图。

在一张大图上的挖掘则是在一张图上挖掘图内出现的子图。

基于图事务集合的频繁子图挖掘算法与基于单个大图的频繁子图挖掘算法不同，在计算候选子图支持度的时候，基于图事务集合的频繁子图挖掘算法只需要计算候选子图与图事务集合中满足子图同构的小图的个数，而基于单个大图的频繁子图挖掘算法需要在这个大图中找出候选子图所有的同构的子图，计算用同构的子图的候选子图支持度[3]。

频繁子图挖掘算法

频繁子图挖掘算法一．算法定义与分类编辑按照模式挖掘算法的输入数据类型进行分类:分为graph-transaction和singie-graph两种类型。

graph-transaction型模式挖掘所处理的输入数据是由许多规模相对较小的图构成的集合，每个图可能只包含几十到几百个顶点;而single-graph型模式挖掘的对象则只有-个大图，这个大图包含成千上万个顶点。

这两种类型的区别还在于它们计算候选子图频度时所使用的策略。

graph-transaction型计算模式在图集合每个图中是否出现，不管它在同-个图中出现了多少次均计数-次，而single-graph型则计算模式在这个大图中不同位置出现的总次数。

根据两种类型的特征，解决graph-transaction类型的算法不能用来解决single-graph类型模式挖掘，但是Single-graph类型的算法却能方便应用于graph-transaction类型。

按照采用度量的不同进行分类:分为支持度(support)、支持度-置信度、MDL(minimumdescri-Ptionlength)三种。

支持度型挖掘是以子图在输入图中出现的次数来作为度量的，大部分算法都是基于支持度的;MDL型挖掘是以压缩输入数据的程度来度量，-般采用公式valuo(s，g)=dl(g)/(dl(g1)+dl(g2))来计算，其中:是子图，g是输入的图集合，dl(g)表示图集合g的存储空间，dl(g2)表示把g中所有出现:的地方都用同-个顶点替换后的图形所需的存储空间;支持度-置信度型挖掘是以既要满足最小支持度又要满足最小置信度来衡量的。

还有其它-些度量方法，这里就不再介绍了。

按照挖掘出的频繁子图的类型进行分类:分为一般子图、连通子图、诱导子图等。

二．算法思路编辑算法的思路比较简单，以递归计数为基础，可以挖掘出所有频繁子图。

但是对于包含较多图的输入集合来说执行效率非常低，主要是因为挖掘算法在生成候选子图时要判断是否存在相同的k-1子图，当川尺大时，这需要花费很长时间。

一种基于局部重构树的改进频繁子图挖掘算法

一
是一种高效的经典算法，然而两遍数据库扫描不
能适应数据流的无限性和流动性的特点。为了克
服该局限性，需要设计一种有效的全局数据结构，通过一次扫描就能包含所有数据库信息。笔者提出了一种新的一次扫描前缀树结构，称为局部重构ＯＰＦ。该结构是一种类似于ＦＰ—
根，路径上所有能与Ｏ连通的节点或者能与Ｏ连Ｌｔ通的节点将构成Ｏ条件图库中的一个图。这样Ｌ可以剔除那些既不与连通，不与Ｏ连通的又ｌ点。也可以避免同时考虑与连通的边和与
含一个点的频繁图集的标号顶点表，笔者引入了
为［Ｉ］其中ｔＴｔ，为第一个元素，为剩余元素而
的表，递归调用Ｉｅ —ｒｅ（Ｉ，ｒ）ｎｒｔＴｅ函数实现ｓｔｅＴｅ将元组对应的信息加入到Ｔｅｒｅ中，成树的完
Ｄｅ２１ｃ．０１
文章编号：０７—１４２１）６— ８４— ４１０４Ｘ（０１００６０
文献标志码：Ａ
一
种基于局部重构树的改进频繁子图挖掘算法
蒋廷耀，廖强
（三峡大学计算机与信息学院，湖北宜昌４３０）４０２
关键词：频繁子图；图挖掘；ｓ表；Ｐ—ｔｅＨａｈＦｒｅ
中图分类号：Ｐ９Ｔ３１ＤＩ１．９３ｊｉｎ１０Ｏ：０３６／．ｓ．０７—１４２１．６Ｏ４ｓ４Ｘ．０１０．０

一种基于极大完全子图的最大频繁项集并行挖掘算法

（２）对于，∈州』’）．如果，”ｎ／＇＝Ｏ；那么称，”是
，’上对于ｒ的一个局部最大频繁项集。定义７ｆ可能最大频繁项ＰＭＦＩ）给定，上的一个极大项集，’．事务数据库Ｄ．最小支持度计数ｍｉｎ＿ｓｕｐ。如果满足：（１）ｊ，”，，”Ｃ＿Ｉ’。包含，”的事务在Ｄ中出现的次数大于等于ｍｉｎ＿ｓｕｐ：（２）如果ｊ，Ｅ妒（，’），使得，”ｃ＿ｒ成立；那么称，”是，’上对于，的一个可能最大频繁项集。定义８（邻接最大频繁项集的超集ＳＭＦＩ）给定Ｊ上的一个极大项集，７．事务数据库ｒ．最小支持度计数ｒａｉｎ＿ｓｕｐ．如果满足：（１）ｊ，一。，”Ｅ，’，包含Ｊ”的事务在Ｄ中出现的次数大于等于ｍｉｔｔ＿ｓｕｐ：（２），∈妒（，’），如果，”ｎｒ≠ｏ；并且，”—，≠Ｏ；那么称Ｊ”是，’上对于ｒ的一个最大频鬟项集的超集。定理１给定项目集合，．，上极大项集的集合表示为中．对Ｖ，’￡垂．，’的邻接极大项集集合为妒（ｊ’）＝｛，Ｉ／－Ｅ圣，ｒｎｌ’≠Ｏ，，≠Ｊ’１，，’上的局部最大频繁项集、可能最大频繁项集和邻接最大频繁项集的超集分别记为ＬＭＦｌ（，’），ＰＭｌ：Ｉ（，’）和ＳＭＨ（Ｉ’），那么，上的所有最大频繁项集：
ｉｆ（ｒｏｏｔ．ｔａｉｌ＝Ｄ】ｆｏｒ
ｅａｃｈ，ｉｎ州ｒ００ｔ．ｈｅａｄ）
ｉｆ（Ｏ＜ｌｒｏｏｔｈｅａｄｆ－ｌＦｌ＜ｌ，ｎ／＇１）
把ｒｏｏｔ．ｈｅａｄ添加到ＰＭＨ’中：
ｅｌｓｅｉｆ（Ｉ／＇ｎ／＇ｌ≤ｉｎ：ｏｒ．ｈｅａｄｎｆｌ）
把ｒＯＯｔ．ｈｅａｄ添加到ＳＭＨ‘中：
ｅｌｓｅｉｆ（Ｉｒｏｏｔ．ｈｅａｄｎ／＇ｌ＝Ｏ）
“
输出：ＰＭＦＩ．ＳＭＦＩ和ＬＭＨ。
ｉｆ（ｓｕｐｅｒｓｅｔ（ｒｏｏｔ．ｈｅａｄＵｒｏｏｔ．ｔａｉ）￡（ＬＭＦＩＵＰＥＨＵＬＭＨ））ｒｅｔｕｍ；Ｎｏｄｅｒｍ，ｍａｏｄｅ；ｆｏｒｅａｃｈｉｉｎｒｏｏｔ．ｔａｉｌｆ

从不确定图中挖掘频繁子图模式

ISSN 1000-9825, CODEN RUXUEW Journal of Software, Vol.20, No.11, November 2009, pp.2965−2976 doi: 10.3724/SP.J.1001.2009.03473 © by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
本文中,不确定图是一种边带有权值的特殊加权图,边的权值表示该边在其两个端点之间实际存在的可能性.不确定图数据库是一个不确定图的集合.不确定图与确定图的不同之处在于,一个不确定图代表了由它蕴含的全部确定图上的概率分布.确定图 I 被不确定图 G 蕴含,若 I 和 G 具有相同的顶点集且 I 的边集是 G 的边集的子集.一个不确定图数据库则代表了由它蕴含的全部确定图数据库上的概率分布.确定图数据库 d={I1,I2,…,In}被不确定图数据库 D={G1,G2,…,Gn}蕴含,若对所有 1≤i≤n 有 Gi 蕴含 Ii.第 2 节将给出不确定图数据模型的详细定义.
摘要: 研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表
示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的 Apriori 性质,给出了一种基于
深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的
Abstract: This paper studies uncertain graph data mining and especially investigates the problem of mining frequent subgraph patterns from uncertain graph data. A data model is introduced for representing uncertainties in graphs, and an expected support is employed to evaluate the significance of subgraph patterns. By using the apriori property of expected support, a depth-first search-based mining algorithm is proposed with an efficient method for computing expected supports and a technique for pruning search space, which reduces the number of subgraph isomorphism testings needed by computing expected support from the exponential scale to the linear scale. Experimental results show that the proposed algorithm is 3 to 5 orders of magnitude faster than a naïve depth-first search algorithm, and is efficient and scalable. Key words: uncertain graph; graph mining; frequent subgraph pattern

一种有效的并行频繁子图挖掘算法

精心整理一种有效的并行频繁子图挖掘算法陈晓云赵娟陈鹏飞邢乔金刘国华（兰州大学信息科学与工程学院兰州730000）摘要：在分析并行频繁项集挖掘算法的基础上，提出了一种有效的并Keywords:parallel;frequentitemset;frequentsubgraph1.引言：频繁子图挖掘与其他比较成熟的频繁模式挖掘相比，图结构数据所包含的信息比一般的数据类型的数据量更大,其数据结构比线性表和树更为复杂。

在图形结构中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。

尽管其结构很复杂，但是由于基于图的应用越来越广泛，其已经渗入到诸如语言学、逻辑学、物理、化学、计算机科学及数学的这些分支学科中。

如通过对已有的生物分子结构与未知的生物结构的研究，来确定未知生物分子与已知生物分子之间的成的子树集分发到其他从处理节点。

第二部分将频繁子图边扩展及同构判断这部分频繁子图挖掘算法中时间复杂度最高的部分并行处理。

文章在最后通过实验验证了本算法的有效性和可行性。

2.并行频繁项集挖掘综述频繁模式挖掘的搜索空间可以被模拟成类似格的结构，其中由模式的大小来决定它处于格中的哪一层，每一层又以某种顺序进行排列。

模式格的维数决定了问题的指数级别。

例如，对于一个有着n 个不同项的事务数据库，可能的模式就会有2n。

也就是说，如果一个事务数据库有100个不同的项，搜索空间就达到2100 1030。

巨大点上共享的来避免假负现象。

建立这样的树大大减少了生成频繁项集的开销。

这些树上的频繁项都是交叉连接起来的（与FP-Tree中相同），并且总体上连接在一个全局头表上。

每块树森林（treeforest）被分配到各个处理节点上，分开后的FP-Tree在挖掘过程中被自下向上的顺序快速遍历。

树的位置降低了并行节点间由于错误的操作而覆盖其他节点更新的可能性，同时使得死锁的可能性最小化。

但是基于共享式内存的并行频繁项集不能够适用于广泛使用的集群系统，因此局限性比较大。

一种高效的凸连通子图枚举算法

1
1 Predecessors/Input ports
processor; cu定制指令设计过程中,需要提取热点代码数据流图的凸连通子图.为实现子图的快速
枚举,对有向无环图内的凸子图特性进行了研究.根据凸子图特性和节点邻接关系,提出了一种 AS(adjacent search)
算法用于枚举有向无环图内满足 I/O 端口约束的凸连通子图.实验数据显示,AS 算法比现有算法具有更高的效率,
U pred (v) v∈VS
\ VS ;S 的外部后继节点
( ) U 集记为 succ(S),有 succ(S) =
succ(v)
v∈VS
\ VS .
我们将子图的外部前驱节点叫做输入端口(input ports),外部前驱节点集称为输入端口集,记为 ip(S),即
ip(S)=pred(S);与外部后继结点相邻接的子图内节点叫做输出端口(output ports),它们组成的集合称为输出端口
(successor);若v∈VS且u∉VS,称u为S的外部前驱节点;若u∈VS且v∉VS,则称v为S的外部后继节点. 节点 v 的前驱节点集记为 pred(v),即 pred(v)={u|u∈V,(u,v)∈E};v 的前驱节点集记为 succ(v),即 succ(v)=
( ) {u|u∈V,(v,u)∈E}.对于子图 S,其外部前驱节点集记作 pred(S),则 pred (S) =
Received 2008-10-24; Revised 2009-03-30; Accepted 2009-07-07
薄拾等:一种高效的凸连通子图枚举算法
3107
可配置处理器利用定制指令(custom instructions,简称 CI)来加速原本不擅长的计算任务.为获得最佳优化效果,CI 往往针对目标应用的热点代码(hot-spot)进行设计.对于规模小且结构简单的应用程序,可以采用人工方式进行热点提取和分析.然而,当应用程序规模变大,则必须借助自动工具完成程序数据流图(dataflow graph,简称 DFG)的探索(如图 1).具体地说,热点代码 DFG 的子图集合中存在着一部分子图具有硬件实现的可能和价值, 设计者希望从 DFG 中提取这些子图.DFG 是一种典型的有向无环图(directed acyclic graph,简称 DAG),于是在 CI 的设计过程中需要解决 DAG 中特定类型子图的提取问题.

单图中的近似频繁子图挖掘算法

单图中的近似频繁子图挖掘算法作者：窦建凯林欣胡文心来源：《华东师范大学学报（自然科学版）》2019年第06期摘要：图数据的挖掘工作是数据挖掘工作中的重要组成部分，已经有许多人在这个领域进行了深入的研究.由于数据获取不可避免噪音数据，故在挖掘频繁图时考虑近似十分重要.然而许多此前的工作只考虑了子图间编辑距离（Graph Edit Distance，GED）的绝对值，而没有考虑子图间编辑距离与子图大小的相对关系.提出了一种在单图中进行近似频繁子图挖掘的新算法，并在计算近似程度时考虑当前子图的大小.该算法通过对近似频繁子图的大小上限进行预测，并通过局部反单调性进行剪枝，提高了算法的效率.实验表明，该算法能够挖掘出传统算法无法发现的近似频繁子图，且相比对比算法具有更好的时间性能.关键词：近似; 图;频繁子图挖掘;剪枝中图分类号：TP391.4文献标志码：ADOI： 10.3969/j.issn.1000-5641. 2019.06.0080 引言图是用来表示数据的一种特殊数据结构，它不仅可以用来表示实体本身的性质，同时还可以用来表示实体之间的关系.图的这种特点使得图在多种领域具有广泛应用，如生物信息学、网络分析等.随着社会和科学的发展，实体之间的关系越来越多样，实体的数量越来越多，使用图结构来表示实体间的关系显得尤为高效，从图数据中挖掘实用的模式亦显得越来越重要.然而图结构虽然能高效地表示实体间的关系，但其结构的复杂性使得从图中识别频繁的子图也变得困难.如在挖掘有用子图的过程中，同构图的识别问题，就被认为是一个NP（Non-deterministic Polynomia）完全问题.因此需要高效的频繁子图挖掘的方法.现有的从图结构数据中挖掘频繁子图的方法主要分为两种：准确频繁图挖掘和近似频繁图挖掘.准确频繁图挖掘指从给定图或图数据库中挖掘频繁子图，当记录每个子图的支持度时，只计算与当前子图完全一致的同构图的数量，如gSpan[1]和Grami[2]而近似频繁图挖掘与准确频图挖掘的主要区别为，除了完全一致的同构图，还同时记录与当前子图有一定区别的同构图的数量，如gApprox[3]与AGraP[4].由于获取数据的过程中，不可避免数据丢失或噪音，因此在实际应用中，近似频繁子图挖掘更加符合用户需求.已有的近似频繁子图挖掘算法在计算两个给定图的近似程度时，只关注其近似程度的绝对值，即从一个图转化为另一个图需要的操作数的绝对值;而在实际应用中，在衡量两个图的近似程度时，图本身的大小也是非常重要的衡量指标.针对以上现有的近似频繁子图挖掘算法的问题，本文提出了子图大小相关的近似频繁子图算法.该算法改进了子图近似程度的计算方式，使得近似程度的结果与当前候选子图的大小有关.算法首先通过一个基于深度优先搜索策略的算法，以及基于给定频繁程度和近似程度的子图大小上限算法，生成所有符合大小要求的候选子图;然后对每个候选子图生成一个最小的、需要搜索的近似子图集合，并对其中的每个近似子图进行图同构搜索;最后计算所有匹配的同构图中，互斥的同构图的数量并将其作为子图的近似支持度.本文算法的主要难点有：①随着给定图的大小增加，候选子图的数量呈指数增加，因此需要一个有效的搜索方式及early-stop的条件;②对任意一个候选子图，其近似子图的数量随候选子图的大小呈指数式增加，且由于图同构问题是一个NP完全问题，因此高效的识别同构图十分困难;③计算所有近似匹配中互斥匹配的数量，及候选子图的近似支持度的问题，可以转化为MIS（Maximum Independent Set）问题[5]，而MIS问题是一个公认的NP完全问题，因此计算子图的近似支持度是一个重要且困难的问题.基于以上算法的主要难点，本文的主要贡献如下.（1）基于深度优先搜索策略的候选子图生成算法、候选子图大小上限的计算方法.（2）提出了一个基于点和边的删除尝试策略的近似子图生成算法、高效的图匹配算法.（3）根据近似频繁子图的特点，利用候选子图的支持度上限，来代替候选子图的准确支持度，极大地提高了算法的效率.（4）实验证明，与对比算法相比，本文算法不仅高效，同时能发现对比算法无法发现的近似频繁子图.本文的结构如下：第1节介绍一些与本文提出算法及目标相关的工作;第2节介绍一些相关概念;第3节到第5节详细介绍本文算法的3大模块;第6节通过实验展现本文算法的有效性;第7节给出本文的总结与展望.1 相关工作频繁子图挖掘指的是，给定一个频繁程度下限，从给定的图或图集合中挖掘出全部的、符合频繁程度要求的子图.因此频繁子图挖掘问题主要分为两种：单图中的频繁子图挖掘和图集合上的频繁子图挖掘.图集合上的频繁子图挖掘已经有许多成熟的工作，如，gSpan算法[1]，在图集合中挖掘频繁子图，避免了候选子图的生成;Gaston算法[6]修改了搜索策略，从而使得算法速度加快.类似的算法还有gRed[7]和GraphSig[8].这些算法的不同及其优缺点在Cheng等的文章[9]和Krishna等的文章[10]中有详述的论述.近年来，随着数据规模的增大和需求的不断变化，一些特殊的频繁子图挖掘算法也不断被提出.如，Choudhury等研究了在动态不断变化的图中挖掘可扩展的子图[11]，他们提出的算法可以随着给定图的变化，动态地判定某个子图是否頻繁;Ingalalli等研究了在多重图中的频繁子图挖掘[12]，其所提出的算法的目的是适应不断丰富且复杂化的数据，除此之外，该算法在应用于简单图上时，也能取得良好的效果.虽然单图中的频繁子图挖掘工作已经在多种应用中被提及，如Alguliev等的工作[13]和Lima等的工作[14]，以及Elseidy等人提出的Grami算法[2]，都能有效地从单图中挖掘频繁子图.但对单图中的频繁子图挖掘的研究，仍然少于图集合中的频繁子图挖掘的研究.研究表明，单图中的频繁子图挖掘算法可以通过简单修改，应用于图集合上;然而图集合上的算法并不能应用于单图中[5].近似频繁子图挖掘是在频繁子图挖掘的基础上，当计算一个子图的支持度时，除了与该子图完全一致的匹配，同时计算满足一定近似程度的匹配.近似程度的计算通常有图的编辑距离[15]、结构区别[16]、特性区别[17]等几种方式.已经有一些近似频繁子图挖掘方面的工作，如Holder等在SUBDUE上设计了一种变形函数[18]，使计算支持度时可以计算有一定区别的近似匹配;Chen等的gApprox在无标签的图上，设计了函数计算图之间的编辑距离[18];Jia等的APGM通过相容性矩阵计算图之间的距离，从而允许子图的近似匹配与子图之间可以有点的区别[19].AGraP[4]算法在此基础上进行了改进，从而允许近似匹配与子图之间拥有点和边上的区别，包括缺失和替换等.Flores-Garrido等在AGraP上进行了修改，使算法挖掘全部近似频繁子图的子集CloseAFG[20].除此之外，Acosta-Mendoza等研究了在多重图上的近似频繁子图挖掘[21]，并利用范式的思想，使算法在时间成本和可扩展性上都有良好的效果.同时，Acosta-Mendoza等利用近似频繁子图挖掘算法，设计了新的图像分类算法[22]，他们利用近似频繁子图挖掘算法的结果，作为图像分类中图像的特征，从而实现了在过程中自动计算和获取需求的替换矩阵，并获得了令人满意的结果，再次证明了近似频繁子图算法具有实际的意义.同时，Acosta-Mendoza等也对近似频繁子图挖掘算法的结果，在图像聚类方面的应用做了研究[23]，并通过实验表明，以近似频繁子图作为聚类的特征，同样可以提升聚类的效果.然而已有的近似频繁子图的挖掘算法，在计算近似程度时，只考虑了编辑距离的绝对值，而忽略了图大小对近似程度的影响.因此，本文提出了子图大小相关的近似程度计算方式，并在此基础上设计了算法挖掘符合要求的近似频繁子图.2 基本概念定义1标签图一个标签图G是一个四元组G=（V，E，L，f），V表示图中所有点的集合，E表示边的集合，L是所有标签的集合，，：V，E一L是一个映射函数，将L中的标签映射到每个点和边上.这是一个被广泛应用的定义，图中的点表示实体，边表示实体之间有一定关系，点上的标签表示实体的属性或类别，边上的标签表示的是实体之间关系的类别.如在蛋白质相互作用图（PPI： Protein-Protein Interaction）中，点表示蛋白质，点上的标签可以表示蛋白质种类.因此有许多点具有相同的标签，边表示蛋白质之间可以发生相互作用，边的标签表示相互作用的种类.定义5子图的近似支持度δ给定图G和近似程度下限θ，图g在图G中的两个近似匹配如果不包含任何相同的点，则说这两个近似匹配是互斥的.图g在图G中的支持度δ指图g能在图G中找到的互斥的近似匹配的最大数.通过以上定义，可以对单图中的近似频繁子图挖掘问题给出形式化定义：给定单图G，支持度下限δ和近似程度下限θ，单图中的近似频繁子图挖掘的目的是，找出图G的所有近似支持度θ'≥δ的子图.定义6置信度ρ 给定图G和近似程度下限θ，图g和图g'是图G中的子图，其近似支持度分别为θ1和θ2，且g是g'的子图，则置信度ρ是指在子图g表示的实体间的关系成立的前提下，子图g'表示的实体间关系成立的概率，即p=θ2/θ1.例如圖1中图G（图1（b）），若设δ=2且θ=0.8，图G的所有近似频繁子图如图2所示.本文算法的框架如图3所示，算法主要分为3个部分：①第一部分遍历给定图的所有候选子图，由于子图数量过多，此处通过预测来确定可能的频繁子图的大小上限，提高遍历速度.②算法第二部分对每个子图生成所有的近似匹配，由于当近似程度下限为1时，寻找近似匹配的问题实际上是子图同构问题，二子图同构问题被广泛认为是一个NP-complete的问题，为了降低计算成本，算法利用生成和搜索过程，在生成阶段，对候选子图的每个结点和边进行尝试删除，生成所有符合近似要求，且不互相包含的近似子图;在搜索过程，对每个近似子图进行查询，③第三部分主要对子图的近似支持度进行计算.本文算法的原理和详细过程将在下面几节中详细阐述.3 候选子图生成定理1候选子图大小上限对给定图G，支持度下限δ和近似程度下限θ，有可能成为近似频繁子图的子图g的大小上限为（2）从图G中移除点1，然后回到步骤（1），任选另一个点开始，直到图G中没有点.为了实现策略中的步骤（1），本文设计了以下算法，具体步骤如下.（1）如图4所示，从点l开始，将点1标记为“必须的”.（2）以当前子图为起点，标记其所有邻居结点为被标记的，如图4中的点1，2，3.（3）使用邻居结点依次扩展当前子图，获得的子图依次为01，02，03.（4）每获得一个新子图，判断其大小是否超出候选子图大小上限.若不超出，以当前子图为新起点，重复步骤（2）.（5）若获得的子图大小超出候选子图大小上限，则终止当前扩展策略，尝试扩展下一个被标记的邻居结点.图4中，不考虑最小近似程度和支持度，所有获得的子图按顺序应为：0，01，012，0123，01234， 012345， 0123456， 012346， 01235， 0125-反单调性是提高挖掘效率的重要条件.在频繁图挖掘中，反单调性是指，给定图G中，若图g'是图g的子图，且图g'与图g这两图都是图G的子图，则图g在G中的支持度必然不超过g'在G中的支持度.在利用近似程度的绝对值，即点或边的缺失数量作为衡量指标时，反单调性是满足的.如图5中，若设最小支持度为3，最多缺失点或边的数量为2，则图5（a）和图5（b）在图G中都是近似频繁的.但本文中，反单调性并不能全局保持.如图5中，图5（a）是图5（b）的子图，但若设δ=2，θ=0.7，由于图5（a）的近似匹配可以允许最多1个点或边的缺失（由于任何点或边的缺失都会造成图的不连通，因此（a）没有任何近似子图），而图5（b）可以允许最多两个点或边的缺失，因此图5（b）拥有更多的近似匹配（如删除点A及相连的边），图5（b）是一个近似频繁子图，而图5（a）不是.本文提出部分反单调性的概念，定理如下.定理2局部反单调性给定图g和近似程度θ，图g'是图g的子图，在满足近似程度的前提下，若图g可允许的点和边的缺失数量，等于图g'可允许的点和边的缺失数量，即0≤（|g|-|g'|）×（1-θ）<1，则g'的支持度不超过g的支持度.证明当子图g'和图g允许缺失的点或边的数量相同时，图g的任意近似匹配必然是图g'的某个近似匹配的超图，而g'的互斥近似匹配的数量，即g'的支持度，必然不超过其互斥的超图的数量，即g的支持度.根据局部反单调性，可以在前述算法上继续剪枝，即在使用当前子图做新输入时，若当前子图的支持度不符合最小支持度的要求，则可以直接扩展当前子图，而不需要判断其是否频繁，直到可允许的点或边的数量发生改变.因此，不需要对每个候选子图生成近似匹配和支持度的计算，从而可以节省大量时间成本.同时，由局部反单调性的证明可知，当两个子图之间的关系符合局部反单调性的要求，则其中较大的图的所有近似匹配，必然是其子图的某个近似匹配的超图，因此可以通过记录子图的所有近似匹配，减少超图的近似匹配的搜索范围，从而节省大量时间成本.改进后算法流程如图6所示.4 近似匹配生成4.1 近似子图生成定义7近似子图给定图g，近似程度θ，当且仅当g的子图g'与g的相似度超过θ，即θ≤|g|- |g'|/|g|，则称g'是g的一个近似子图.为了查询每个候选子图的近似支持度，需要针对每个候选子图，找出其在图中的所有近似匹配.为此提出了一个定理，并在此基础上设计了一个基于点和边的删除的生成算法，来找出候选子图的所有符合近似条件的子图.定理3 给定图G和近似程度θ，图g是G的子图，图a和图b是g的子图，a 是b的子图，则任意b在G中的匹配，都与至少一个a 在G中的匹配有重复点.证明任意b在G中的匹配，是b的一个同构图，则a是此匹配的一个子图，因此此匹配包含a，即包含一个a在G中的匹配，因此任意b在G中的匹配，都与至少一个a在G中的匹配有重复点.根据定理3，可以确定对任意候选子图，其最小需要进行匹配的近似子图集合中，应不含两个图具有包含关系.基于以上定理，本文设计了一个基于点和边的删除的子图生成算法，生成给定候选子图的所有符合近似条件的子图，其基本思路如下，具体算法见算法1.（1）对所有点和边进行编号，并按编号排序，计算给定候选子图g在给定的近似条件θ下，可以允许的缺失的点或边的最大数量，即|g|×（1- 0）.（2）遍历所有编号，尝试删除编号对应的点或边，并判断结果是否连通.若连通，则将编号对应的点或边标记为已删除，并更新当前已删除的点或边的数量.若不连通，则跳过当前编号，继续尝试.（3）以步骤（2）的结果为新的起点，继续遍历剩余编号，直至已删除的点或边的数量到达最大数量，或剩余任意点或边的删除都会导致数量超出最大值，则当前结果即为一个近似子图.（4）跳过最后一个被删除的点或边，继续步骤（2），直到所有点或边的组合删除都被尝试过.步骤（3）的所有结果，即为最终需要进行匹配的候选子图的近似图，由于每个子图被删除的点或边的数量不超出最大值，保证了所有结果都是候选子图的近似图;同时，由于任意一个子图都删除了允许删除的最多的点或边，保证了任意两个结果不具有包含关系.4.2 近似子图匹配为了对每个候选子图，生成对应的近似匹配，本文设计了一种在单图中查询给定子图的所有同构图的算法.给定图G=（V， E，L，f），目的是找到一个合适的点的顺序，使得查找过程的时间花费最小，即在第i步，需要从未找到匹配的点中，选择一个点，使得该点一旦找到匹配，则已被匹配的图的大小增大最多，或使得可能匹配的数量减小到最小.为了完成上述要求，需要对所有的可能匹配进行最大的约束，使得算法能尽早过滤掉错误匹配.为此，本文设计了一种贪心算法，为给定图中的所有点，生成一個匹配顺序.算法首先初始化点的匹配顺序丁为空，从拥有最多邻居结点的点开始，若有多个点拥有相同的邻居数量，则根据点的标签，在目标图中拥有最少对应标签的点的点，作为起始点，插入匹配顺序丁，对剩余未插入匹配顺序的点，按照以下条件插入匹配顺序.获得匹配顺序后，算法根据匹配顺序，对任意一个未匹配的点，遍历目标图中的点，检测是否符合匹配要求，若符合要求，则记录该匹配，并按顺序寻找下一个未匹配点的匹配;若不符合，则跳过该点，尝试目标图中的下一个点进行匹配.算法通过匹配顺序，对任意一个未匹配的点，仅计算其前一个已匹配的点的所有对应点的邻居结点中，未被匹配到任何一个点上的点，具体见图7.5 支持度计算及结果展示5.1 支持度计算在获得了每个候选子图在给定图中的近似匹配后，需要判断一个候选子图是否是近似频繁图.根据子图的近似支持度的定义（定义5），一个候选子图的支持度应该是候选子图所有近似匹配中，可能的互斥的近似匹配的最大数量.然而，确定这个最大数量可以被转化为最大独立集（Maximum Independent Set，MIS）问题，这是一个NP-complete的问题，因此计算一个候选子图的准确近似支持度是十分耗时和困难的.然而，在本文的情况下，在计算子图的匹配时，已经利用的是子图的近似匹配，因此一个候选子图的准确近似支持度其实不是非常重要.此处本文参考了gApprox算法中支持度的计算方式，为每个候选子图的近似支持度计算了一个上限阈值，本文相信这个阈值在本文问题中已经足够可以作为参考，来判断一个候选子图是否近似频繁.计算方式如下.（1）将候选子图的一个匹配图的顶点作为一个集合，初始化近似支持度上限为0.（2）计算候选子图的所有匹配图的点集中的点的出现次数，即每个点出现在多少个匹配图中，并按数字从大到小排序.（3）选择出现次数最高的点，若有多个，则任选一个.将近似支持度上限加1，删除所有包含该点的匹配图的点集，并更新每个点的出现次数.（4）不断迭代第（3）步，直到所有的点集都被删除，假设有一个候选子图的所有近似匹配有{v1，v2），{v1，v3），{v2，v3），{v1，v4），{v4，v5），根据上述算法，初始化支持度上限为O，点V1出现在3个近似匹配中，是所有点中最多的，则删除所有包含v1的近似匹配;支持度上限加l，剩余的近似匹配为{v2，v3），{v4，v5），继续迭代，删除所有包含点v2的;上限加1，然后删除包含v4的匹配，上限加l;此时所有匹配已经被删除，停止迭代，得到最终上限为3.定理4 所有候选子图的真实近似支持度都不超过上述算法中的支持度上限.证明由于对于任意一个点，只记录一次近似匹配，即只将支持度上限加1，相当于记录了一个包含该点的近似匹配，则保证了记录的近似匹配至少在该点上是互斥的，但由于并不保证在所有点上都是互斥的，因此支持度上限必然大于或等于真实的近似支持度.5.2 结果展示通过上节算法计算，可以获得每一个候选近似频繁子图的近似支持度;在与给定的支持度阈值进行比较之后，可以最终确定一个候选近似频繁子图是否频繁.为了提高算法结果的展示效果，以及提高算法效率，对算法挖掘结果的展示作以下约束，第一，对具有相同结构，以及相同标签的结果图，只在结果中展示一次，第二，对于每个结果图，需展示其点的ID和标签，以及边的左右两点的ID和标签，其中ID是重新编辑的，第三，对于每个结果图，展示其近似频繁程度和全部对应.以上约束中，第一条的原因是在候选子图的生成中，可能有多个具有相同标签和结构的子图，由于其在给定单图中的位置不同，可能出现多次，如图8（a）中，点0和点1组成的图，与点4和点3组成的图结构和标签都相同，但在图中的位置不同，因此会在候选子图生成的过程中出现两次.为了提高算法效率，在记录候选子图时，仅记录其中一个，对生成的每一个候选子图，首先与已经被记录的候选子图作比较，若果有相同结构和标签的记录，则不再记录此子图，对于第二条与第三条约束，主要目的是为了更好地理解近似频繁子图的结构，以及更好地展示其近似匹配.如图8（a）中的点O和点2组成的子图，若其为近似频繁子图，则显示结果为图8（b）.6 实验本文设计了两种实验来证明本文算法的有效性，以及发现更多近似频繁子图的能力.第一种实验为有效性试验，实验分别在真实数据及人工数据上进行.第二种实验仅基于人工数据，用于证明本文算法与使用近似程度绝对值算法相比，本文算法可以发现更多的近似频繁子图.所有实验的真实数据抽取自PPI网络，PPI网络获取自DIP（Database of Interacting Proteins）数据库（http：//），人工数据由NetworkX工具（https：//networkx.github.io/ documentation/stable/）构建.所有实验都在1台Windows设备上完成，设备配置为CPU i5-4690，8 GB MEM.实验程序由Java完成.据本文所知，目前已有的与本文算法目的最接近的算法为AGraP，因此本文所有实验中的对比实验为AGraP算法，本文仅修改了AGraP中的近似度计算公式与支持度计算方式，使对比实验基于同一种相似度公式，从而降低不同相似度公式造成的影响.由于对比算法AGraP在使用子图大小相关的相似度时效率较低，算法时间和空间消耗随给定图大小的增长而增长过快，受条件限制，无法完成对普通大小的图的挖掘.因此本文通过NetworkX工具分别生成了7个、9个、11个、13个点的样本图（G7、G9、G11、G13），并在样本图上进行挖掘，取θ= 0.9，δ=2，结果表1所示.通过表l可知，本文算法相对于AGraP算法有较大优势，且由于AGraP算法时间消耗随图大小增长过快，因此不适于对较大的圖的挖掘，而本文算法随着图大小的增长，虽然时间消耗有所增加，但增长速度相对较为合理，除了在样本图上的对比实验，本文利用本文算法，对规模更大的图进行了挖掘，从而展示本文算法除了可以应用于十分小的样本图，同样可以应用于较大规模的图，本文在人工数据与真实数据上都进行了实验.人工数据同样由NetworkX工具生成，为了显示算法效率随图大小的变化，分别生成了100个、125个、150个、175个、200个点的不同大小的图.实验真实数据来自于PPI网络.PPI网络为蛋白质交互网络，其中包含多种已被发现的蛋白质及蛋白质交互反应.其中有多条蛋白质对拥有高于10-7的BLAST（Basic LocalAlignment Search Tool）相似度，本文认为这些蛋白质对具有极其相似的的性质，因此可以用相同的标签做标记，不同的蛋白质之间有不同种类的反应，每种反应可以用不同的标签进行标记，因此PPI网络可以转化为一个标签图，本文从中分别抽取了5个不同的250个点（GIOO、G125、G150、G175、G200、G250（真）），作为实验数据，并将其结果取平均数作为真实数据上的结果.实验结果如图9、图10所示.从图9、图10中可以发现，算法的时间消耗随近似支持度要求的提升不断降低，原因是随着近似支持度要求的提升，更多的候选子图在早期被过滤掉，根据局部反单调性的特点，其特定大小范围内的超图都不可能是频繁的，因此减少了需要生成近似子图及近似子图匹配的候选子图数量，大大节省了时间消耗.同样地，随着近似程度要求的降低，每个候选子图会拥有更多的近似子图，因此需要进行匹配的近似子图增加，同时，更多的候选子图被判定为频繁，因此时间消耗上升.除此之外，给定单图的大小对时间消耗也具有较大的影响，原因是随给定单图大小增加，其候选子图的数量呈指数上升，因此时间消耗上升.除上述實验，本文还在样本图上进行了对比实验，实验主要比较本文算法发现的近似频繁子图数量，与利用近似程度绝对大小的算法发现的近似频繁子图的数量的区别.实验利用的样本图为图8（a）.实验对比算法为本文算法的修改版，即近似程度计算公式为缺失的点或边的。

一种快速的频繁子图挖掘算法

一种快速的频繁子图挖掘算法摘要:提出了一种基于关联矩阵的频繁子图挖掘算法。

该算法通过对关联矩阵的标准化,有效地降低了子图同构判断的代价。

在此基础上,算法利用深度优先的思想,通过逐步扩展频繁边找出所有频繁子图。

实验结果表明,该算法比其他同类算法具有更快的速度和更好的稳定性。

关键词:图;关联矩阵;同构;数据挖掘Abstract:Analgorithmforminingfrequentsubgraphsbasedonassociatedmatrixwasproposed.Bynorm alizingtheassociatedmatrixofthegraph,thecomputationalcostonverifyingtheisomorphismofthesubgr aphswaseffectivelyreduced.Basedonthedepth2firstsearchingmethod,allthefrequentsubgraphscouldb esearchedbyaddingedgesprogressively.Experimentalresultsshowthatthealgorithmhashigherspeedan dbetterstabilitythanothersimilarones.Keywords:graph;associatedmatrix;isomorphism;datamining一引言伴随着生物信息学、社会网络学、XML文档分析的发展,传统的针对非结构型数据的挖掘方法[1]诸如频繁项集和序列模式的挖掘,已经不能胜任对半结构型、结构型数据的挖掘。

图作为结构型数据中的一个重要数据类型,能够表示诸如化学分子(化学原子表示为图中的节点,原子与原子之间的化学键表示为节点之间的边)、蛋白质结构、社会网络等众多应用领域的数据。

对于图挖掘方法的研究,可以有效地解决这些领域的难题。

因此,对于半结构型、结构型数据挖掘的研究已经具有越来越高的应用价值。

频繁子图挖掘研究综述_鲁慧民

26卷　第3期2009年3月微电子学与计算机M IC ROELECTRONICS &COM PUTERVol .26　No .3M arch 2009收稿日期:2008-05-30基金项目:国家“八六三”计划项目(2008AA 01Z 131)频繁子图挖掘研究综述鲁慧民,冯博琴,宋擒豹(西安交通大学电子与信息工程学院,陕西西安710049)摘　要:归纳了频繁子图挖掘方法的处理流程,分析评价了频繁子图挖掘的典型算法:广度优先搜索和深度优先搜索的频繁子图挖掘算法,概述了频繁子图挖掘研究的平台———图模型及其产生器,并对频繁子图挖掘方法未来研究方向进行了展望.关键词:子图同构;频繁子图挖掘;图模型;图产生器中图分类号:T P391 文献标识码:A 文章编号:1000-7180(2009)03-0156-06Survey of Frequent Subgraph Mining ResearchLU Hui -min ,FENG Bo -qin ,SONG Qin -bao(School of Electronic and Information Engineering ,Xi ′an Jiaotong U niversity ,Xi ′an 710049,China )A bstract :T he process of Frequent Subgr aph M ining is summarized in this paper .Broad First Search (BFS ),Depth First Search (DF S ),w hich are the typical mining algo rithms are analyzed and evaluated .T he g raph model and its generator ,w hich is the impo rtant research platform of frequent subg raph mining are introduced .O pen issues and fur ther research di -rections are also discussed .Key words :subg raph isomorphism ;frequent subg raph mining ;graph pa ttern ;g raph g enerator1　引言频繁子图挖掘与相对比较成熟的文本型频繁项挖掘相比,图的数据量大,结构复杂,对原始的图数据进行频繁子图挖掘难度较大.同时通过边或节点添加生成的候选子图集中往往存在大量的冗余,子图同构的NP 问题等都增加了候选子图支持度计算的复杂性,因此一般的文本数据挖掘方法不再适用于频繁子图挖掘,必须结合图数据格式的特点寻求新的挖掘算法.Akihiro 等人在2002年首先将Aprio ri 算法思想应用到频繁子图挖掘中,此后各种基于Aprio ri 思想,采用递归的方法来发现频繁子图的挖掘算法相继出现,主要包括AGM 、AcGM 、FSG 等.后来韩家炜等人将FP -grow th 思想应用到频繁子图挖掘中,使图挖掘得到了迅速的发展,主要包括gSpan 、CloseGraph 和FFSM 等,它们主要通过逐渐扩展频繁边得到频繁子图,但对边的扩展过程略有不同.此外还出现了一些其它的频繁子图挖掘算法,例如Wang 等于2005年提出了一种基于索引的频繁子图挖掘算法GraphMiner [1];2007年Zhu 等提出一种基于用户约束条件的频繁子图挖掘算法gPrune [2],Karste 等提出了适用于动态图挖掘的Dynamic G REW 算法[3]等.作为图挖掘研究的重点,频繁子图挖掘算法得到了广泛深入的研究,文中总结归纳了频繁子图挖掘的处理流程,对典型的频繁子图挖掘算法进行了分析评价,同时介绍了研究频繁子图挖掘的平台———图模型及其产生器,并展望了频繁子图挖掘的未来研究方向.2　频繁子图挖掘的处理流程频繁子图挖掘即从输入数据库中挖掘出所有的频繁子图.(1)频繁子图挖掘的基本概念设是频繁子图,则公式如下:S f rek ={K |∑ni =1X ik ≥m }(1)式中,X i k ∈{0,1},如果子图K 与图数据库中G i 子图同构,则X i k =1,否则X ik =0;m 是最小支持度.(2)频繁子图挖掘算法的处理流程频繁子图挖掘算法的基本步骤主要包括图标识、图数据库数据的简化、侯选子图的生成、侯选子图的剪枝、支持度计算等.处理流程如图1所示.图1　频繁子图挖掘的处理流程首先对图进行唯一标识以避免子图同构问题,对图数据进行简化,删除非频繁边或顶点.利用频繁子图挖掘算法挖掘候选子图,对其中的冗余子图进行剪切,计算候选子图的支持度,选择大于最小支持度的候选子图形成频繁子图集.3　频繁子图挖掘算法频繁子图挖掘算法按子图挖掘搜索路径分为广度优先搜索算法(Broad First Search ,BFS )和深度优先搜索算法(Depth First Search ,DFS )[4].广度优先搜索算法基于Aprio ri 思想实现,主要包括AGM 、AcGM 、FSG 等,深度优先搜索算法基于FP -g row th 思想实现,主要包括g Span 、CloseGraph 和FFSM 等.3.1　广度优先搜索算法AGM 算法是最早采用Apriori 思想的广度优先搜索算法,它采用邻接矩阵来表示图,根据邻接矩阵生成图编码,取其中的最小编码作为图的唯一标识,以解决子图同构的NP 问题.以频繁顶点作为初始集,利用Apriori 性质(一个项集是频集当且仅当它的所有子集都是频集),采用递归方法挖掘频繁子图.AGM 算法思想比较简单,但其存在明显的缺点:首先由频繁k -1-子图集进行自连接生成的候选频繁子图k -项集数量巨大,其次在验证候选频繁子图k -项集的时候需要对整个数据库进行扫描,非常耗时,因此不少研究者提出了改进算法:(1)基于划分的方法这种算法先把图数据库分成几个互不相交的单元,每次单独考虑一个单元并对它生成所有的频繁子图,然后把产生的频繁子图进行无损合并,用来生成所有可能的频繁子图集,最后计算这些子图集的支持度.Wang 等在2006年引入了一种基于划分的图挖掘方法PartMiner .该算法首先反复调用图划分算法将数据库中的每一个图划分成更小的子图,将其分组到单元,其次利用现有的基于内存的频繁子图挖掘算法发现每个单元的频繁子图集,通过合并连接操作将每个单元的频繁子图合并,重新得到整个图的频繁子集.(2)基于采样的方法先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则,然后对数据库的剩余部分验证这个结果.在图理论研究中,采样往往用来对图进行压缩,便于存储.2005年K rishnamurthy等提出了一种基于选择随机节点方法[5],抽样大小为源图的30%,此外还有通过随机边的选择来进行抽样的方法.Leskovec 和Faloutsos 在2006年提出了大图(Large Graph )的抽样方法:对静态图的抽样采用“随机行走(random w alks )”方法或类似病毒繁殖的方法选择具有代表性的节点,构建与源图拥有一致特征的抽样图.针对动态图则采用“森林火(Fo rest Fire )”方法进行采样.通过对大图的抽样,然后对其进行频繁子图的挖掘,可以大大减少候选频繁子集的数量,使大图的挖掘成为可能.(3)基于减少源图数量的方法减少用于未来扫描的图集的大小.一个基本原理就是当一个图不包含k 频繁子图,则必然不包含k +1的频繁子图集,从而可以将这些图移除,这样在下一遍的扫描中就可以减少要进行扫描的图集的个数.(4)基于边扩展与约束限制的方法———FSG 与AcGM 算法Kuramochi 和Kary pis 在2001年提出了一种基于扩展边来高效生成候选子图的算法FSG ,是对157　第3期鲁慧民,等:频繁子图挖掘研究综述AGM算法的改进,在候选子图的剪枝策略和计算频繁支持度方面进行了优化.2002年Inokuchi等提出了一种利用限制性条件生成诱导子图作为候选子图,对AGM进行性能改进的方法AcGM,其执行效率比AGM和FSG都高.此外马海兵等于2006年提出一种高效挖掘无序频繁子树的算法,利用最右路径扩展方法构造完整的模式增长空间,然后根据待增长模式的拓扑结构确定其增长点并构造相应投影库,从而挖掘出频繁子树.3.2　深度优先搜索算法Han等人在2002年针对类Apriori算法(如FSG、AGM、AcGM)连接和剪枝耗时很大的缺点,提出基于深度优先搜索的gSpan算法.gSpan算法是一种基于FP-grow th思想的频繁子图挖掘算法,其基本思想是利用最小DFS码对图进行唯一标识,以简化子图同构问题.利用最小DFS码作为空间树的一个节点进行最右路径扩展形成k-频繁子图,每次添加一条边,形成k+1-频繁子图,如果k+1 -频繁子图不是最小DFS码形式,则作为冗余删除掉.在支持度的计算上采用对k-频繁子图的事件(Occurrence)进行记录,k+1-频繁子图的支持度可以通过对k-频繁子图的所有Occurrence进行最右扩展得到.其核心算法如下[6]:Subgraph-M ining(G S,S,s)1.if s!=min(s)2.return;3.S→S∪{s};4.g enerate all s'potential children with one edge g rowth;5.Enumerate(s);6.for each c,c is s'child do7.If support≥min sup8.s→c9.Subgraph-M ining(G S,S,s);g Span算法对于大型数据库而言效率仍然很低.Yan和Han于2003年提出一种改进的CloseG-raph算法,主要是对频繁闭子图进行挖掘.CloseG-raph的算法思想与gSpan一致,只是在对候选子集进行剪枝的时候采用定理来判断是否进行最右路径扩展.gSpan算法和CloseGraph算法相对于Apriori 算法,它们通过引入新的方法和概念———DFS词典顺序(DFS lex icog raphic Order)、最小DFS码和最右扩展使得无需按Aprio ri算法的思想,而是直接生成频繁子图,大大提高了算法的效率.但gSpan算法和CloseGraph算法在挖掘结果集中考虑了图的标记,即具有不同标记的图被认为是不同的图.而很多情况下,标记不同的图具有相同的结构.为了解决“标记不同但结构相同的图被认为是不同的”的问题, 2005年重庆大学的康艳荣在论文中提出了两种新的算法[7]———极大完全子图挖掘算法(M ax-codeFMCG算法)和频繁子图结构挖掘算法(FSA算法),并将M axcodeFMCG算法与已有的频繁模式挖掘算法FP-Grow th算法相结合,产生一种基于图结构的频繁模式挖掘算法(M axcodeFP-Tree算法).该算法的主要优点是解决了FP-Grow th算法中存在的内存不足的问题,FSA算法则解决了以往的频繁子图挖掘算法中存在的“标记不同但结构相同的图被认为是不同的”的问题,有利于对结构挖掘进行更深入的研究.此外,2003年Huan等提出了FFSM算法,将图的标准形状变为树结构,并提出了树的一系列操作.首先该算法将图转化为标准的邻接矩阵表示,将子图的同构问题转化为矩阵的操作,图的扩展也转化为对矩阵的连接操作与矩阵的扩展操作.依据给定的参数首先通过枚举找到所有的近似频繁边,并移除在数据库中的非频繁边,接着用深度优先发现所有的最大近似频繁树,这可以通过递归增加一个新节点到已经存在的近似频繁树,直到候选树不再是近似频繁树或在前面已经存在该近似频繁树.FF-SM通过标准码来唯一标识图,避免了子图同构的问题,为每一频繁子图设计一个嵌入集合(Em bed-ding Set).在进行支持度计算时,只扫描嵌入集合即可避免重复扫描数据库,提高了计算支持度的速度和效率,但该算法中的FFSM-Join产生的候选具有不完整性,必须通过FFSM-Ex tension进一步产生候选子图,以保证挖掘结果的完整性.3.3　其它频繁子图挖掘算法除以上频繁子图挖掘算法以外,还有基于索引、用户约束、动态图的挖掘算法,以及为提高挖掘效率的并行挖掘处理等.(1)基于索引的算法Wang等于2005年提出一种基于索引的算法GraphMiner,用来挖掘频繁子图,利用高效的索引结构AID(Adjacency Index)从大图中挖掘频繁子图. AID索引一般有三层结构:边名表、连接的图编号列表、临近信息.三层结构的AID可以装入内存.一旦建立AID,那么在挖掘过程中,仅用索引来进行挖掘,不再访问源数据库.(2)基于并行多处理器算法2006年,Gregory等提出一种适合并行的图挖158微电子学与计算机2009年掘管理系统,用尽量少的内存但运行时间却得到改良,还为并行图挖掘设计了任务划分和包系统.任务划分与分配的目的是保证负载均衡,使每一个处理机都能高效率的工作直到挖掘任务完成.动态任务分配允许运行时进行任务分配,给予空闲的处理器额外负载.(3)基于用户约束的挖掘算法频繁子图的挖掘在有些算法中忽略了它的目的性,即有些算法针对的是所有的频繁子图的挖掘而往往没有与用户的具体要求结合起来,在实际应用中往往在挖掘时要加以条件限制,一方面可以减少候选频繁子图的数量,提高算法的效率,另一方面可以更清楚的发现与用户要求相联系的内容.2007年Zhu等人提出了一种基于用户约束条件的图挖掘算法gPrune.(4)基于动态图的挖掘算法多种频繁子图挖掘算法都是针对静态图挖掘的,不适用于动态图挖掘.Karsten等提出了对动态图进行挖掘的算法,并对动态图进行了定义,将图数据的动态变化分为两种.一种是所有的数据同步变化,另一种数据的变化是不同步的.他们对Grew[8]进行扩展,使其适用于动态图挖掘,提出Dynamic Grew算法.此外,针对大图的频繁子图挖掘,Kuramochi和Karypis于2004年提出了HSIGRAM和VSIGRAM 两种算法,该算法除了考虑子图同构问题外还考虑了同一个图的不同子图同构间的交迭(Overlap)问题,是对大图中所有频繁子图进行挖掘比较有效的方法.2004年Huan等人提出了一种基于挖掘最大频繁子图的算法SPIN,首先挖掘出源图数据所有的频繁树,然后再从挖掘出的频繁树挖掘最大频繁子图.该算法除了可以大大减少输出频繁子图的数目,还在很大程度上提高了挖掘速度.4　图模型及其产生器4.1　图模型频繁子图挖掘算法研究基于一定的图模型,因此需要有产生与自然界中的图特性相一致的抽象模型,图模型是进行图挖掘理论研究的基础,将现实世界中各种各样的图抽象出来归纳总结为图模型,便于分析和研究,也有利于在各领域实现研究思路和方法的统一.图模型可以帮助模拟研究现实中的图,将现实中的大图缩小成与其相匹配的小图便于研究、分析和计算.但要将现实中千差万别的图抽象成统一的图模型却比较困难,图模型的研究主要集中在有规律图形上,主要有幂指数规律(Power Laws)、小直径(Small Diameters)和社区效应(Community Effects)三种[9].此外2000年Broder等人将WWW 的图模型描述为蝶状(a bow tie)结构[10],如图2所示.将Web划分为SCC(Strong ly Connected Compo-nent)、IN、OUT、TENDRI LS四部分.Tauro等人在2001年提出Internet的水母(Jelly fish)结构图模型[11],由核心(Core)、层(Layers)、悬垂节点(Hang-ing Nodes)三部分构成,如图3所示.图2　WWW的蝶状结构图3　Internet的水母结构4.2　图产生器图产生器产生与自然界图匹配的图模型,为频繁子图挖掘算法的研究提供平台.根据生成图的模型不同,图产生器目前主要分五类:随机模式、择优连接模式、基于最优化模式、地理模式、特殊的In-ternet模式.(1)随机模式.Erdös和R′enyi早在1960年就提出随机图产生器[12],由用户提供一定数目的节点N,在每一对不同的节点间按一定概率p添加边.随机模式产生的图只能匹配度分布而不能匹配其它图模型.(2)择优连接模式.1999年Kleinberg等提出一种与择优连接模式很相似的边拷贝方法[13],主要适用一些聚类性强的图,例如在基于主题的WWW的Web站点,在加入新节点时,它拷贝了已存在的与它具有相似性的节点的边.Winick等在2002年采用“Rich Getting Richer”原则[14],即每次加入一个新节点都要优先连接到已经存在的度高(Hig h De-159　第3期鲁慧民,等:频繁子图挖掘研究综述g ree )的节点上.择优连接模式只通过几个简单的步骤即可使产生的图符合幂指数分布,且较低的直径和很好的恢复能力,是目前最流行的模式,但是它没有聚类效果.(3)基于最优化模式.1999年Carlson 和Doyle 提出HOT (Highly Optimized Tolerance )图产生器[15],HOT 能匹配幂指数规律并具有很强的恢复能力,它是考虑资源和效益两者折中的平衡方案,与现实世界中的好多受资源约束的图相符合,但它不能通过适当的参数值修改匹配实际图的特性.(4)地理模式.有的图模式结构受到地理位置的约束,例如Internet 中地理位置比较靠近的两个路由器之间的连接就很容易,这种图产生器主要有小世界模型(Sm all -World Model )和Waxman 模型(Waxm an Model )两种,如图4、图5所示.Small -World M odel 是在1998年由Watts 和Strogatz 提出的[16],节点安排在一个规则圆形的格子上,每个节点直接与它相邻的节点连接,用实线表示,某些距离远的节点用虚线连接.产生的图具有低直径、高聚类的特点,但不匹配幂指数规则.The Waxman Mod -el [17]是Wax man 在1998年提出的一种按节点间距离概率连接各节点的模型,通常随着距离的增大概率减小,新增加的节点连接到已经存在的距离近的节点.但它也不匹配节点度的幂指数分布,这种简单的思想在2000年被Medina 等应用到BRITE 图产生器来产生网络聚类.图4　小世界模型图5　Waxman 模型(5)特殊的Internet 模式.2002年Winick 和Jamin 发展了Internet 图产生器,但是仅匹配互联网自治系统(Internet Autonomous System ,IAS )拓扑中的几个特殊的特征,后来采用择优机制对其进行了改进.5　频繁子图挖掘研究展望目前频繁子图挖掘各个方面的研究都取得了很大的成绩,并应用到一些实际的系统中,取得了很好的效果,但对于频繁子图挖掘还有许多方面尚需进一步深入研究.(1)图模型.需要进一步研究新的图模型,以尽量多的匹配现实中的图结构,语义网图模型的构建是一个重要的研究方向.(2)图产生器.要求尽量匹配多的图模型,通过适当的参数值修改来匹配实际图的特性.(3)频繁子图挖掘算法方面.子图同构问题需要进一步研究;候选子图的冗余问题需要进一步解决;对大图的挖掘算法研究还比较少;对不精确的频繁子图、概念频繁子图、加权频繁子图等的挖掘的研究;对优化挖掘算法,减少时间空间的复杂度,采用并行、分布式技术处理也是一个很重要的研究方向;挖掘结果如何实现可视化的研究等.参考文献:[1]Wang W ,Wang C ,Zhu Y .GraphM iner :a structural pat -tern -mining system for large disk -based graph databases and its application [C ]//P ro ceedings o f the 2005ACM SIG M OD I nterna tio nal Co nference on M anagement of Da -ta .Baltimore ,M ary land :2005:879-881.[2]Zhu F ,Yan X ,Han J .gP rune :a co nstraint pushingframewo rk fo r g raph pattern mining [C ]//P roceedings of 2007Pacific -Asia Conference o n Knowledge Discovery and Da ta Mining (PAK DD '07).China :N anjing ,2007:388-400.[3]K arsten M ,Hans -Peter K ,Pe ter W .Pattern mining infrequent dy namic subg raphs [C ]//Proceedings o f the 6th Inter national Co nference on Data M ining (ICDM '06).HongKo ng :2006:818-822.[4]李先通,李建中,高宏.一种高效频繁子图挖掘算法[J ].软件学报,2007,18(10):2469-2480.[5]K rishnamurthy V ,F aloutsos M ,Chrobak M ,et al .Re -ducing large internet topologies for faster simulatio ns [C ]//Networ king 2005.Canada :Ontario ,2005:328-341.[6]王艳辉,吴斌,王柏.频繁子图挖掘算法综述[J ].计算机科学,2005,32(10):193-197.[7]康艳荣.基于图结构挖掘算法的研究与应用[D ].重庆:重庆大学,2005.[8]K uramochi M ,K ary pis G .Grew -a scalable frequent sub -g raph disco very algo rithm [C ]//The 4th I EEE Interna -tio nal Co nference on Data M ining .UK :Brighton ,2004:439-442.[9]Chakrabar ti D ,Faloutsos C .Graph mining :laws ,genera -tor s ,and algorithms [J ].A CM Computing Surveys ,2006,38(2):1-69.[10]A ndrei B ,Ravi K ,F arzin M .G raph structure in theweb :ex periments and models [C ]//9th World Wide Web160微电子学与计算机2009年Conference.New York,2000:309-320.[11]T auro S,Palmer C,Sig anos G.A simple co nceptualmodel for the internet topolog y[C]//Global Teleco mmuni-cations Conference,2001(G LOBECOM′01).U SA,I EEE,T exas.2001:1667-1671.[12]Erdös P,Rényi A.O n the evolution of random graphs[J].Publication of the M athema tical Institute of the Hun-garian A cademy of Science,1960(5):17-61.[13]K leinberg M,K umar R,Raghav an P.T he web as ag raph:measurements,models and methods[C]//I nterna-tional Computing and Combinatorics Co nference.Berlin,Springer,1999.[14]Pennock D,Flake G,Lawrence S.Winners don't takeall:characterizing the competition for links o n the web[J].N ational A cademy of Sciences,2002,99(8):5207-5211.[15]Carlson J,Doyle J.Highly optimized tolerance:a mecha-nism for power laws in designed sy stems[J].P hysical Rev,1999,60(2):1412-1427.[16]W atts D,Strogatz H.Collective dynamics of`small-world'networks[J].Na ture,1998(393):440-442. [17]Wax man B.Routing of multipoint connectio ns[J].IEEE.Select.A reas Comm,1988(6):1617-1622.作者简介:鲁慧民　女,博士研究生.研究方向为数据挖掘、知识管理.冯博琴　男,博士生导师,教授.研究方向为数据挖掘、智能网络.宋擒豹　男,博士,教授,博士生导师.研究方向为数据挖掘、知识工程.(上接第155页)存在的故障有一个准确的定位,集中精力排除主要故障.在电子设备等某些特殊机械设备的使用过程中,底事件的故障概率相当大.对于设备的故障概率进行近似计算,可以按照故障树建树原则,在正确建树的基础上,利用最优权因子[6]进行近似计算,以达到减小近似计算误差的目的.参考文献:[1]王国亮,孙新利.故障树法在弹头遥测可靠性分析中的应用[J].战术导弹技术,2005(5):21-23.[2]韩小涛,尹项根,张哲.故障树分析法在变电站通信系统可靠性分析中的应用[J].电网技术,2004(1):56-69.[3]绍延峰,薛红军.故障树分析法在系统故障诊断中的应用[J].中国制造业信息化,2007(1):72-74.[4]潘吉安.可靠性维修性可用性评估手册[M].北京:国防工业出版社,1995.[5]周璧华,陈彬,石立华.电磁脉冲及其工程防护[M].北京:国防工业出版社,2003.[6]孙东平,姚依.故障树分析法及其在导弹故障近似计算中的应用[J].装备环境工程,2006(4):64-67.作者简介:高　晶　女,(1983-),硕士研究生.研究方向为指挥自动化.161　第3期鲁慧民,等:频繁子图挖掘研究综述。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software , Vol.18, No.10, October 2007, pp.2469−2480 DOI: 10.1360/jos182469 Tel/Fax: +86-10-62562563 © 2007 by Journal of Software . All rights reserved.一种高效频繁子图挖掘算法∗李先通, 李建中+, 高宏(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨 150001)An Efficient Frequent Subgraph Mining AlgorithmLI Xian-Tong, LI Jiang-Zhong +, GAO Hong(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)+ Corresponding author: Phn: +86-451-86415827, E-mail: lijzh@, Li XT, Li JZ, Gao H. An efficient frequent subgraph mining algorithm. Journal of Software , 2007,18(10): 2469−2480. /1000-9825/18/2469.htmAbstract : With the successful development of frequent item set and frequent sequence mining, the technology of data mining is natural to extend its way to solve the problem of structural pattern mining —Frequent subgraph mining. Frequent patterns are meaningful in many applications such as chemistry, biology, computer networks, and World-Wide Web. In this paper we propose a new algorithm GraphGen for mining frequent subgraphs. GraphGen reduces the mining complexity through the extension of frequent subtree. For the best algorithm before, the complexity is O (n 3·2n ), n is the number of frequent edges in a graph dataset. The complexity of GraphGen is⎟⎟⎠⎞⎜⎜⎝⎛⋅n n O n log 25.2, which is improved )log (n n O ⋅ times than the best one. Experiment results prove this theoreticalanalysis.Key words : frequent pattern mining; subgraph isomorphism; subtree isomorphism; frequent subgraph; spanningtree摘要: 由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题——频繁子图挖掘.诸如化学、生物学、计算机网络和WWW 等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O (n 3·2n ),其中,n 是图集中的频繁边数.提出的算法时间复杂性是⎟⎟⎠⎞⎜⎜⎝⎛⋅n n O n log 25.2,性能提高了)log (n n O ⋅倍.实验结果也证实了这个理论结果.关键词: 频繁模式挖掘;子图同构;子树同构;频繁子树;生成树中图法分类号: TP311 文献标识码: A∗ Supported by the National Natural Science Foundation of China under Grant No.60473075 (国家自然科学基金); the Key ProgramNational Natural Science Foundation of China under Grant No.60533110 (国家自然基金重点项目); the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)); the Program for New Century Excellent Talents in University (NCET) under Grant No.NCET-05-0333 (国家教育部新世纪创新人才计划)Received 2006-09-08; Accepted 2006-11-142470 Journal of Software软件学报 V ol.18, No.10, October 2007由于图具有广泛的应用性,所以针对图挖掘的研究也越来越引起人们的重视.很多领域内的数据都可抽象为图,如给定物质的化学结构能被抽象为无向标号图(其中的节点对应着原子,而边则对应着原子间的化合键),生物学、XML、计算机网络和WWW中的数据也可抽象为图,用于进一步的研究.图挖掘可以粗略地分为频繁子图挖掘、图聚类与图分类等等.频繁子图挖掘的目的是找到在图集中频繁出现的子图.由于频繁子图挖掘结果可作为图聚类、图分类等其他图挖掘研究的基础,也使得频繁子图的挖掘工作具有更加深远的影响.目前,频繁子图的挖掘结果已经应用于一些应用领域内,如在PTE(predictive toxicology evaluation challenge)项目中的应用,其目的是找到频繁出现的与有毒物质具有相同子结构的物质.Borgelt和Berthold在文献[1]中证明了使用图描述和采用频繁子图挖掘技术对这个问题研究的有效性.其他的基于频繁子图挖掘的应用包括录像索引、提高结构化数据库的存储效率、高效索引技术和WEB信息管理等.但是随着图和图集规模的扩大,现有频繁子图挖掘算法在效率上已不能满足需求.在PTE项目中,图的规模还比较小(20个节点与边),节点度的平均值也较小(≤4),节点标号集却相对较大(>60).但在蛋白质研究领域内抽象出的图则大得多,虽然节点标号集相对较小(20个标号左右),但图的尺寸更大(100~1 000个节点或边),每个节点的度也更大(在某些例子中达到6~20).因此,要设计适合更大、更复杂图集的挖掘算法,提高频繁子图的挖掘效率势在必行.初期的频繁子图挖掘算法,将工作重点集中在近似技术(SUBDUE[2])和小规模数据库上(inductive logic programming).近期的频繁子图挖掘算法可以分为两类:一类是广度优先算法(broad first search,简称BFS).这类算法采用了类Apriori性质去枚举重复出现的子图.这类算法包括AGM[3,4]和FSG[5].AGM在图集中搜索所有“诱导”子图.图G的诱导子图G′的节点为V(G′)⊆V(G),G′的边为V(G′)中节点在图G中的所有边.FSG则利用边增长的方式查找所有图集中的频繁连通子图.因为采用了Apriori性质,即在扩展边的过程中,通过两个n条边候选图进行乘积以得到(n+1)条边的候选图,这样做会生成大量重复候选子图,降低了算法的整体效率.频繁子图挖掘算法的另一类是具有更好执行效率的深度优先算法(depth first search,简称DFS).这类算法包括gSpan,CloseSpan和FFSM等.所有算法均通过逐步扩展频繁边得到频繁子图,但每个算法对图的扩展过程略有不同.Yan和Han在文献[6]中提出的算法gSpan是典型的深度优先算法[7],频繁子图G是通过对其父亲子图G′增加一条新的频繁边而得到的.与枚举所有潜在子图不同,gSpan方法保存一个频繁子图G的子图同构列表,这样做的好处是能减少制约效率的同构测试次数.不过,gSpan并不能避免子图同构测试,边的扩展算法复杂性也很高,达到了O(2n),使总的时间复杂性高达O(2n·2n).在文献[8]中,Yan等人又提出了挖掘频繁闭图集的CloseSpan算法,虽然它在边的扩展与结果集的剪枝中采用了一些优化方法以减少计算时间,但总体的时间复杂性依然为O(2n·2n).Huan和Wang在文献[9]中提出了另一种频繁模式挖掘算法FFSM,将图的描述巧妙的转化为标准邻接矩阵(canonical adjacent matrix,简称CAM).这样,FFSM不但将子图同构问题转化成了对矩阵的操作,也将图扩展过程巧妙的转化为矩阵的联接操作与矩阵的扩展操作.但是,由于其图扩展的过程通过矩阵的联接与扩展完成,所以扩展边的时间复杂性为O(m2·n·2n)∗,图同构测试的时间复杂性为O(m2),总的时间复杂性降低至O(m4·n·2n).具有m个节点的完全图包含m(m−1)/2条边,因此,其时间复杂性转化为用频繁边数表示的情况为O(n3·2n).在表1中,我们给出了上述3种算法时间复杂性的比较,其中,n表示边数,m表示节点数,第2列给出了这些挖掘算法对频繁图中边进行扩展时的时间复杂性,第3列给出了这些算法进行子图同构测试的时间复杂性.由于在频繁子图的挖掘过程中,每次对边进行扩展都需要进行同构测试,因此,总的时间复杂性是边扩展的复杂性与同构测试复杂性的乘积,在第4列中给出.从表1中可以看出,在频繁子图挖掘算法中,两个对算法时间复杂性影响最大的问题是子图同构问题(子图同构问题已被证明是NP完全问题)和有效的图扩展方法.表1中的数据显示,以上3种算法对边的扩展过程均采∗算法本身是按先深搜索的方式对边进行扩展,其复杂性为O(2n).但由于在扩展过程中,使用了矩阵的联接操作与扩展操作形成新的CAM,使复杂性达到O(m2·n·2n).李先通等:一种高效频繁子图挖掘算法2471用先深搜索方式,但对子图同构测试的方式却不尽相同,FFSM 效率更高,它能回避图与图之间直接的同构测试,通过标准邻接矩阵的比较确定子图同构问题,达到相对较好的时间复杂性O (m 2).因此,无论提高扩展边的效率还是子图同构测试的效率,都会对降低整体算法的时间复杂性起到积极的作用.虽然近期也有部分挖掘技术研究成果[10−12],但这个问题仍然没有很好的解决.Table 1 Complexity of graph mining algorithms表1 图挖掘算法的时间复杂性分析扩展边的复杂性同构测试复杂性总复杂性gSpan O (2n ) O (2n ) O (2n ·2n )CloseSpan O (2n ) O (2n ) O (2n ·2n )FFSMO (m 2·n ·2n )O (m 2)O (n 3·2n )本文提出了一种新的频繁子图挖掘算法GraphGen,基本思想是将图挖掘过程分为两步:第1步是生成频繁子树,对边的扩展采用深度优先的方法,复杂性为O (2n ),但由于挖掘结果是树,其同构测试时间复杂性为⎟⎟⎠⎞⎜⎜⎝⎛n n O log 5.2[10].第2步是对第一步中生成的频繁子树进一步扩展以形成频繁图,边的扩展方式为广度优先,复杂性为O (n 2),进行子图同构测试的时间复杂性为O (2n ),这部分总的时间复杂性为O (n 2·2n ).由于这两部分是顺序完成的,因此,算法总体的时间复杂性为⎟⎟⎠⎞⎜⎜⎝⎛⋅n n O n log 25.2.本文第1节给出与频繁子图挖掘的相关术语及定义.第2节给出频繁子图挖掘算法(先给出图描述的标准化编码,然后给出图挖掘算法).第3节给出实验结果.第4节对全篇进行总结.1 基本概念在本文中,我们将问题集中于简单无向连通标号图.通过修改,本文提出的算法也适用于复杂无向连通标号图,即含有环或两节点间有多条边的情况.标号图作为一种通用的数据结构,能用于复杂模式的模型化工作.我们在这部分给出标号图的定义,同时给出的还有子图同构与频繁子图支持度的定义.基于这些定义,我们能对图进行准确的数学描述.定义1.1(标号图). 一个标号图是一个五元组,G ={V ,E ,ΣE ,ΣV ,L }.其中,V 代表图中节点的集合,E ⊆V ×V 代表图中边的集合.ΣV ,ΣE 分别代表节点标号的集合与边标号的集合.L 是标号函数,用于完成标号向节点和边的映射:V →ΣV 与E →ΣE .定义1.2(图的同构). 图的同构是一个双射f :V (G )↔V (G ′).对于图G ={V ,E ,ΣV ,ΣE ,L }与图G ′={V ′,E ′,ΣV ′,ΣE ′, L ′},若它们是同构的,则满足如下条件:∀u ∈V ,L (u )=L ′(f (u ))∀u ,v ∈V ,((u ,v )∈E )⇔((f (u ),f (v ))∈E ′),且 ∀(u ,v )∈E ,L (u ,v )=L ′(f (u ),f (v )).定义1.3(子图同构). 给定标号图G 与G ′,若G ′中存在子图G ″与图G 同构,则称G 与G ′是子图同构的,记为G ⊆G ′.子图同构问题是NP 完全问题.如何减少或降低子图同构的计算开销,是图挖掘工作研究人员的主要研究内容之一.定义1.4(支持度). 给定一个图的集合GD ,图G 的支持度记为SUP G ,计算方法为GD 中与G 存在子图同构的图G ′的个数与整个图集中图的个数的比值,表示如下:|||}|{|GD G G GD G SUP G ′⊆∈′=.一个图是否频繁,与该图在图集中的出现次数相关,同时也与预先定义的最小支持度阈值有关.设预先给定2472 Journal of Software 软件学报 V ol.18, No.10, October 2007的最小支持度阈值为min _sup ,则频繁图的定义如下:定义1.5(频繁图与频繁树). 给定一个图集GD ,GD ={G i |i =0,1,…,n },且给定最小支持度阈值为min _sup ,我们称图G 是频繁的,当且仅当G 的支持度不小于最小支持度阈值,即SUP G ≥min _sup .相应地,当图G 是频繁的且其中无回路时,我们称G 为频繁树.频繁子图挖掘问题是给定一个最小支持度阈值min _sup ,在图集GD 中找到所有支持度不小于min _sup 的子图.在以下章节中,使用大写字符表示集合,如“G ”,“E ”,“V ”等,而用小写字符表示元素,如“g ”,“e ”,“v ”等.2 挖掘频繁子图采用先深搜索的办法挖掘频繁子图,会在搜索的过程中形成一个树状的搜索空间(这个特点可以参照频繁项集中FP 树的定义),这棵树的根节点为空,由根至叶按边个数递增的顺序形成树,非根节点分别代表不同的频繁子图.整个挖掘过程是由根至叶的遍历过程.图1显示了这个树状的搜索空间.3-edge n -edge...Fig.1 Search space 图1 搜索空间图的标准化编码是对图的一种形式化描述.将图与标准化编码进行一一对应,可有效的避免同构图的不同遍历顺序引起的重复候选集的计算开销.确定了图的标准化编码,我们就可以只计算具有标准化编码的遍历,降低算法的复杂性. 2.1 图的标准化编码标号图的每一条边,都存在5个基本元素,即两个节点标识、两个节点标号和边标号,我们可直接使用该五元组对边进行描述,将边e =(v i ,v j )表示为(v i ,l i ,v j ,l j ,l e ),其中,v i ,v j 为节点标识,l i ,l j 为节点标号,l e 为边标号.例如图2(a)所示标号图,边(v 1,v 2)可表示为(v 1,B ,v 2,A ,b ),边(v 0,v 3)可表示为(v 0,A ,v 3,B ,c ).节点标识之间存在一种线性顺序:若在图的遍历过程中先遍历v i ,后遍历v j .则v i 和v j 之间的顺序关系为v i ≺v j .同样地,我们规定节点标号与边标号之间也存在一种序关系,即线性的字母序.由此,我们可定义边之间的线性关系.例如图2(a)中,我们可通过v 0≺v 1来确定(v 0,v 1)(v ≺1,v 2),但图2(a)与图2(b)中,边(v 0,v 1)中各项编码均相同,仅边的标号不同,我们可通过边的标号来确定其大小,由于a <b ,所以(v 0,v 1)a ≺(v 0,v 1)b ,其中,括号的下标表示图(a)或图(b).2323(a) (b) Fig.2 Representation of labeled graph图2 标号图的表示方法定义2.1(边的线性顺序). 给定标号图的任意两条边e a =(a 1,a 2,a 3,a 4,a 5),e b =(b 1,b 2,b 3,b 4,b 5),其线性顺序由下李先通等:一种高效频繁子图挖掘算法2473列条件决定:1) e a=e b,当且仅当a i=b i,i=1,2, (5)2) e a≺e b,当且仅当∃k,1≤k≤5,使a j=b j (1≤j<k),且a k≺b k;3) e b≺e a,其他情况.例如,图2所示为同一个图的3种不同遍历结果.图2(a)中的边(v1,v3)a可描述为(v1,B,v3,B,a),图2(b)中的边(v1,v3)b可描述为(v1,B,v3,B,a).由于这两个五元组完全相等,因此,这两条边的顺序关系是相同的.然而,虽然图2(a)中的边(v0,v1)a=(v0,A,v1,B,a)与图2(b)中的边(v0,v1)b=(v0,A,v1,B,b)前4个元素具有相同的顺序关系,但第5个元素的顺序关系为a b,依照定义2.1,边的顺序关系为(v≺0,v1)a≺(v0,v1)b.同理,图2(a)中的边(v0,v3)a=(v0,A,v3,B,c)与图2(b)中的边(v0,v3)b=(v0,A,v3,B,b)之间的大小关系为(v0,v3)b≺(v0,v3)a,而图2(a)中的边(v2,v3)a=(v2,A,v3,B,b)与图2(b)中的边(v2,v3)b=(v2,A,v3,B,c)之间的大小关系为(v2,v3)a≺(v2,v3)b.同样地,我们可给出图的线性顺序定义定义2.2(图的线性顺序). 给定两个标号图的DFS遍历编码g1={e11,e12,…,e1n},g2={e21,e22,…,e2m},其中,e ij表示图g i中DFS遍历第j条边的编码.图g1、图g2的线性顺序由下列条件决定:1) g1=g2,当且仅当m=n,且e1i=e2i,其中,1≤i≤m;2) g1≺g2,当且仅当下列条件之一成立:a) ∃k,1≤k≤min(n,m),使e1j=e2j (1≤j<k),且e1k≺e2k;b) n<m,且e1i=e2i (1≤i≤n)3) g2≺g1,其他情况.例如,表2的第2列~第4列分别对应图2中的3种遍历结果图2(a)~图2(c).通过定义2.1与定义2.2给出的线性顺序,我们得到g a≺g b≺g c.下面我们证明对任意图,其DFS编码值都存在最小值,且这个最小值是唯一的.Table 2DFS coding of graphs表2图的DFS编码Edge 图2(a) 图2(b) 图2(c)0 (v0,A,v1,B,a) (v0,A,v1,B,b)(v0,B,v1,B,a)1 (v1,B,v2,A,b) (v1,B,v2,A,a)(v1,B,v2,A,a)2 (v2,A,v3,B,b) (v2,A,v3,B,c)(v1,B,v3,A,b)3 (v3,B,v1,B,a) (v3,B,v1,B,a)(v2,A,v0,B,c)4 (v3,B,v0,A,c) (v3,B,v0,A,b)(v3,A,v0,B,b)定理2.1. 图的最小DFS编码是唯一的.证明:先证明其存在性.设图g为具有n条边的标号图,共有k种遍历方法,其编码的集合为G DFS={g1,g2,…,g k| g i={e i1,e i2,…,e in}(1≤i≤k)}.由定义2.2知,∀g i,g j∈G,g i和g j之间均存在线性顺序关系.因此,将G中的编码逐个比较,必然能找到g′∈G,且其线性顺序具有最小值,所以图的最小DFS编码存在.再证明其唯一性.设最小DFS编码不唯一.图g的不同遍历产生的DFS编码为G DFS={g1,g2,…,g k| g i={e i1,e i2,…,e in}(1≤i≤k)}.设g i与g j均为最小DFS编码,且g i≠g j.由定义2.2知,两个不同的DFS编码值,其相互关系仅有3种情况,若g i≠g j,则必有g i≺g j或g j≺g i之一成立.在不影响结果的前提下,不妨设g i≺g j成立,这与题设g i与g j 均为最小DFS编码矛盾,而导致这种矛盾的原因是假定最小DFS编码不唯一.所以,最小DFS编码是唯一的.综上所述,最小DFS编码存在,并且唯一. □定理2.1确定了图与最小DFS编码的一一对应关系.在进行图挖掘的过程中,由于同构图的遍历顺序不同,会形成不同的DFS编码.通过最小DFS编码与图的一一对应,我们在挖掘过程中可以放弃对其他DFS编码的继续操作而只考虑最小DFS编码,这样做既会保证得到完整的结果集,又可以避免扩展重复候选集所带来的额外计算开销.接下来,我们从频繁子图的生成过程着手,进一步分析挖掘过程中树与图之间的关系.定义2.3. 在图的扩展过程中,如果一条扩展边引入了一个新的节点,则称该扩展边为外边,由e o表示.若该扩展边未引入新的节点(扩展边的两个节点已存在于该图中),则称其为内边,用e w表示.2474 Journal of Software软件学报 V ol.18, No.10, October 2007图集中,节点与边的频率超过最小支持度阈值时,我们称其为频繁节点与频繁边.由此设定,当外边(内边)的频率不低于最小支持度阈值时,称其为频繁外边(频繁内边).例如,图2(a)的遍历过程如表2第2列所示,其中,用粗实线描述的边表示扩展过程中的外边,而用虚线表示的边则为内边.因此,我们可以将这些边分别加入两个集合:一个集合是外边集,为E o={(v0,v1),(v1,v2),(v2,v3)},另一个集合为内边集E w={(v3,v1),(v3,v0)}.定理2.2. 如果一个图仅由外边组成,那么它是一棵树(无回路).反之,如果一个图中至少含有一条内边,则它必含有回路.证明:我们通过对边进行归纳证明外边形成树.如果一个图g0仅含有一条边,显然,g0无回路,g0是一棵树.设图g n由n条外边组成且无回路,我们考虑加入一条新的外边的情况.假设被加入的外边为e=(v i,l i,v j,l j,l e),并假定节点v j为新引入的节点,即v j∉V(g n),e∉E(g n),因此,节点v j与图g n之间仅有一条路e与v i连通.通过题设我们知道,在引入节点v j之前,图g n中不存在回路,即由节点v i起始的路径集合P k={p k|(p k是g n中的路径)∧(p k起始于v i)}(其中,k=1,…,(i−1),(i+1),…,(n+1))中无回路.到达v j的路径必经过v i,即P j={p j|p j=p k+e},由于v j与g n之间仅有一条路e,因此得出∀p∈P j不是回路.所以,g n+1中无回路.现在我们考虑图g中存在至少一条内边的情况.设e=(v i,l i,v j,l j,l e)是内边,且图g在e加入之前由外边组成.由前面的证明知道,此时g是树,所以,它的所有节点都是连通的,因此,必然存在一条路径p起始于v i而终止于v j,记为p(i,j).e∉E(g n)且e连通节点v i与v j.因此,图g∪e中有回路,且该回路为(e+p(i,j)). □在图挖掘过程中,影响计算效率的原因来自两个方面:一方面是子图同构测试;另一方面是边的扩展.通过定理2.2,我们可将图的挖掘过程分为两个步骤:第1步生成频繁子树.与图的同构测试相比,子树同构测试的时间复杂性更低;第2步由频繁子树进一步扩展为频繁子图,这时,频繁子树在扩展过程中不引入新的节点,边扩展的时间复杂性降低至O(n2).但是,将挖掘过程分为两步,我们需要面对的另一个问题是,在频繁子树向频繁子图扩展的过程中,能否生成完整的结果集.定理2.3. 1) 一个图的先深搜索生成树的最小DFS编码是唯一的.2) 生成树的最小DFS编码确定,并给定频繁内边集,扩展之后的图也是唯一的.证明:1) 树是无回路的图.定理2.1保证了生成树的最小DFS编码不但存在,而且唯一.2) 假设图g为最小DFS树t所扩展.令E′=E(g)−E(t)为给定的频繁内边集.同时,根据图中生成树的定义, ∀v∈V(g)⇒v∈V(t),即生成树t包含图g的所有节点.因此,∀e∈E′,e=(v i,l i,v j,l j,l e),都能在树t中找到对应的v i∈V(t), v j∈V(t),即边e的两个节点均在t中出现,并且,由于我们考虑的是简单图,任意两节点间存在的边数不会大于1,所以,此对应关系为一一对应.综上所述,DFS树确定,且后向边集确定,得到的图也是唯一的. □定理 2.3说明,最终结果集中的任一频繁子图都存在一棵频繁子树与之对应,在由树向图的扩展过程中,由于内边的逐条加入,会形成一个完整的搜索空间.2.2 FTGen作为频繁子树挖掘算法,FTGen(frequent subtree generation)的输入条件为图集GD,频繁子树t(程序开始运行的时候是频率最高且DFS编码最小的边),频繁边集E.频繁边集E可通过对图集GD的扫描与边的统计得到,同时,E中的边按频率的降序排列.算法的详细定义如下:算法1. FTGen.输入:图集GD,频繁子树t,频繁边集E;输出:频繁子树集T.(1) if t≠min(t) then return; /*检查t是否具有最小DFS编码*/(2) E′←{e是频繁外边};(3) for E′中的每条边李先通等:一种高效频繁子图挖掘算法 2475(4) E ′←E ′−e ;(5) if (t ◊e )存在于图集中; (6) then t ←t ◊e ;(7) if (T 中无t 的同构子树) then T ←T ∪t ; (8) FTGen (GD ,t ,E ,T ); (9) endfor;算法在第1行判断频繁子树是否为最小DFS 编码.若当前子树不是最小DFS 编码,则放弃操作,以避免对重复生成的子树做进一步扩展.在生成频繁子树之前,算法在第2行找到子树t 的所有频繁外边,这样,可以保证新边加入后,t 中依然无回路.算法的第4行到第8行,循环处理子树的每一条外边,第5行检验当前外边e 能否加入t 中(扩展后的子树出现在图集GD 中,符号“◊”的意义为将外边e 加入子树t ),并将这样的边与子树联接生成新的子树.若无重复的子树生成,继续对t 扩展,直至频繁外边集为空或T 中存在t 的同构子树.同时,将生成的频繁子树在第7行中加入到频繁子树的集合中.FTGen 的挖掘结果是图集GD 中出现的频繁子树,储存在集合T 中.频繁子树将被用于进一步对边扩展以形成图,同时,频繁子树作为图的一种,是最终挖掘结果的子集.FTGen 主要的计算开销由两部分组成:一是子树同构的测试.虽然目前有很多关于子树同构测试的研究工作[13−17],但我们采用文献[13]中提供的方法,将时间复杂性控制在⎟⎟⎠⎞⎜⎜⎝⎛n n O log 5.2;二是频繁外边的扩展,由于采用了先深搜索,这部分的时间复杂性为O (2n),即算法总的时间复杂性为⎟⎟⎠⎞⎜⎜⎝⎛⋅n n O n log 25.2.同时,定理2.1与定理2.2保证了算法的正确性.定理2.1确定了剪枝的基础,即通过DFS 最小编码与图之间的一一对应,对不符合最小DFS 编码的中间结果直接删除而不影响最终结果.定理2.2确定了外边、内边的扩展顺序与树和图之间的关系.我们在算法的挖掘过程中只增加外边,从而确保生成结果是树. 2.3 频繁子图挖掘算法(GraphGen )算法GraphGen 用于挖掘图集中的频繁子图,其挖掘过程是先生成频繁子树,再由频繁子树扩展为频繁子图.其中,频繁子树挖掘算法采用本文算法1描述的FTGen.由树向图扩展内边的特点是,随着边数的增加,节点数保持不变.根据这个特点,我们在GraphGen 中将边扩展的时间复杂性降低至O (n 2).下面给出算法GraphGen 的详细定义:算法2. GraphGen.输入:图集GD , 最小支持度阈值min _sup ; 输出:频繁子图集合FG .(1) 扫描图集并找到图集GD 中所有频繁边; (2) 删除所有非频繁边; (3) E ←{GD 中所有频繁边};(4) 将E 中的边按DFS 编码顺序和频率的降序进行排列; (5) T ←NULL ; /*T 为频繁子树集合*/(6) t ←e 1; /*E 中的第一条边作FTGen 的初始值*/ (7) FTGen (D ,t ,E ,T );(8) 将集合T 中的元素按节点数与DFS 编码顺序进行排序; (9) FG ←T ; (10) for T 中的每棵树 (11) g ←t ;(12) E ′←{e 是频繁边,且e 是内边,并能在图集中找到(g ◊e )};2476 Journal of Software 软件学报 V ol.18, No.10, October 2007(13) for E ′中的每条边 (14) E ′←E ′−e ; (15) g ←g ◊e ;(16) if g ≠min(g ) then break;(17) if FG 中无g 的同构子图 then FG ←FG ∪g ; (18) endfor; (19) endfor; (20) return FG ;GraphGen 分为3个部分,算法2给出了这个算法的细节.算法在第1部分(第1行~第6行)对图集GD 进行预处理.作为图挖掘的基础,必须从图集中提取出必要的信息,如频繁边集、频繁节点集等.在这个部分中,GraphGen 扫描图集GD 并得到频繁边集,将频繁边集按频率递减与DFS 编码值递增的顺序进行排列,供算法进一步计算.算法在第2部分(第7行)进行频繁子树的挖掘工作,具体的挖掘过程见2.2节.算法的第3部分(第8行~第19行)是由树向图的扩展过程.针对每一棵频繁子树,从频繁边集中找出能与之联接的内边,逐一加入到该树,从而形成频繁子图.算法在第12行找到所有能与图g 联接的频繁内边,并将这些边在第13行~第17行的子循环中加入到图g 中.算法的执行结果为频繁子图集合FG .与FTGen 相似,算法GraphGen 主体的时间复杂性也分为两部分:一部分是子图同构的时间复杂性.由于子图同构的测试是NP 完全问题,算法在第17行进行的图同构测试,其时间复杂性为O (2n );另一部分是扩展边的时间复杂性.由于我们仅向频繁图中加入内边,通过两层循环完成,因此,这部分时间复杂性为O (n 2).边的每一次扩展,都需要检验所生成的图是否与结果集的元素重复,因此,算法总的时间复杂性为O (2n ·n 2).在本算法中,仅考虑在稳定的图集中进行频繁子图挖掘.因此,图集GD 及GD 中的频繁边集都是确定的.由定理2.3可知,GraphGen 的挖掘结果集是完整的.由于算法1与算法2是顺序完成的,因此,算法的整体时间复杂性为⎟⎟⎠⎞⎜⎜⎝⎛⋅n n O n log 25.2.表3给出了FTGen 和GraphGen 与其他算法时间复杂性的比较值.可以看出,本算法的优点是将整体挖掘过程分为两个部分.在挖掘频繁子树的部分,我们的算法在子图同构的计算上节省了时间;而在由树向图扩展的过程中,我们在扩展边的过程中节省了时间,使整体时间复杂性与其他算法相比提高了)log (n n O ⋅倍.Table 3 Complexity of graph mining algorithms表3 图挖掘算法的时间复杂性分析扩展边的复杂性同构测试复杂性总复杂性 n n n n CloseSpan O (2n ) O (2n ) O (2n ·2n ) FFSM O (m 4·n ·2n )O (m 2) O (n 3·2n ) FTGen O (2n ) ⎟⎟⎠⎞⎜⎜⎝⎛n n O log 5.2⎟⎟⎠⎞⎜⎜⎝⎛⋅n n O n log 25.2GraphGenO (n 2)O (2n )O (n 2·2n )2.4 算法的优化算法2的第3部分,在边的扩展方式上较之前的算法进行了较大的改进,但仍然需要进行大量的子图同构验证(第17行).由于我们的算法是由频繁子树向图的扩展,因此对具有不同节点数的子树,不会产生相同的频繁子图.基于这个特点,我们可以对算法2进行相应调整,使其在生成频繁子图的过程中,对同构子图的检验次数降至最低.算法3. 对GraphGen 同构测试部分的改进. (1) k ←0; /*k 用于存储树的节点数*/。