频繁子图挖掘算法gSpan的设计与实现.doc

频繁子图挖掘算法 gSpan 的设计与实现郭玉林，刘勇（黑龙江大学 计算机科学技术学院，哈尔滨 150080）摘 要：由于大部分图挖掘算法都需要利用频繁子图，频繁子图挖掘逐渐成为了数据挖掘领域中的热点研究内容。 目前，很多高效的频繁子图挖掘算法已经被提出。 其中，gSpan 算法是目前公认的最好的频繁子图挖掘算法。 然而，在化合物数据集上，还可以利用化合物的特殊结构进 一步优化 gSpan 算法的性能。 文献利用了化合物分子结构的对称性和原子类型分布的不均衡性， 提出了一些新的优化策略， 进一步改进了 gSpan 的性能。 鉴于 gSpan 算法在图挖掘领域乃至整个数据挖掘领域的重要性，设计并实现 gSpan 算法。 同时，采用文献4中的优化策略，进一 步提高 gSpan 算法在化合物数据集上的运行效率。关键词：gSpan； 频繁子图； DFS 编码； 词典序中图分类号：TP311文献标识码： A文章编号：20952163（2011）03005503Design and Implementation of A Frequent Subgraph Mining Algorithm gSpanGUO Yulin, LIU Yong（School of computer science and technology, Hei Longjiang University, Harbin 150080, China ）Abstract: Since most of the graph mining algorithms are needed to make frequent subgraph,frequent subgraph mining is gradually becoming the hotspot in the field of research. At present, many efficient frequent subgraph mining algorithms have been proposed. Among them, gSpan algorithm is currently accepted as the best frequent subgraph mining algorithm. However, in the compound datasets, the performance of gSpan algorithm based on the special structure could be further optimized. The paper uses the symetry of the molecular structure of compounds and the unequilibrium of the dis- tribution of atomic types, and puts forward some new optimization strategy, so as to further improve the performance of gSpan algorithm. Because gSpan algorithm is very vital in graph mining areas and the entire data mining field, this paper designes and implementes gSpan algorithm. Mean- while, the paper also prepares to adopt the optimization strategy in the literature4, further improves the gSpan algorithm operation efficiency in com-pound datasets.Key words:gSpan; Frequent Subgraphs; DFS Code; Dictionary Order0引言由于大部分图挖掘算法13都需要利用频繁子图，频繁子 图挖掘逐渐成为了数据挖掘领域中的热点研究内容。 目前， 很多高效的频繁子图挖掘算法已经被提出。 其中，gSpan 算法 是目前公认的最好的频繁子图挖掘算法。 该算法利用模式增 长(patterngrowth) 策略， 采用深度优先方式遍历模式搜索空 间。 在某个频繁子图 p 的基础上，扩展产生 p 的孩子(p 的超 模式) 并计算其支持度 ， 对 p 的每个频 繁 孩 子 ， 以 深 度 优 先 方式继续扩展，直到发现全部频繁子图为止。然而，在化合物数据集上 ， 还可以利用化合物的特殊结 构进一步优化 gSpan 算法的性能。 文献4利用了化合物分子 结构的对称性和原子类型分布的不均衡性，提出了一些新的 优化策略，进一步改进了 gSpan 的性能。本文内容安排如下:第 1 节给出问题定义; 第 2 节给出 算法描述; 第 3 节给出实验结果;第 4 节总结全文。1问题定义本节首先介绍预备知识，然后给出问题的形式化定义。本文主要考虑连通的无向标号简单图。 通过简单修改，收稿日期：20110722本文的 gSpan 算法也适用于有向图， 无标号图和不连通图。如无特别说明，本文中的图均指连通的无向标号图。 一个图 G 定义为一个四元组 G( V，E，l )， 其 中 ，V 是 顶 点 集 合 ， E哿VV 是边集合， 是标号集合， l：VE 是一个函数， 用来对顶点和边分配标号。定义 1 （图同构）：图的同构是一个双射 f: V(G)圮V(G)。 对于图 G邀V，E，V，E，L妖与图 G邀V，E，V，E，L妖，若 G 与 G是同构的，则满足如下条件:（ 1 ） 坌 u V ， L ( u ) L ( f ( u ) ) ；（ 2 ） 坌 u ， v V ， ( ( u ， v ) E ) 圳 ( ( f ( u ) ，f ( v ) ) E ) ， 且 坌 ( u ， v ) E ， L ( u ， v ) L ( f ( u ) ， f ( v ) ) 。定义 2 （子图同构）：给定两个图 G (V， E， ， l)和 G (V ， E， ， l)， 一个从 G 到 G的子图同构是一个单 射函数 f: VV，满足:（1）坌 u V ， l ( u ) l ( f ( u ) ) ；（2）坌 ( u ， v ) E ， ( f ( u ) ， f ( v ) ) E 并 且 l ( u ， v ) l ( f( u ) ， f ( v ) ) 。单射函数 f 也称为 G 在 G中的一个嵌入。基金项目：国家自然科学基金资助项目（60973081），黑龙江省自然科学基金项目（F201011），黑龙江省教育厅科学技术研究面上项目（11551352，12511401）。作者简介：郭玉林（1986），男，黑龙江齐齐哈尔人，本科生，主要研究方向：数据库；刘 勇（1975），男，河北昌黎人，博士，副教授，硕士生导师，主要研究方向：数据库、数据挖掘。通讯作者：刘 勇如果存在一个从 G 到 G的子图同构，则 G 称为 G的子图， G称为 G 的超图，记为 G哿G。 如果 G哿G且 GG，则 G 称为 G的真子图， G称为 G 的真超图，记为 G奂G。 子图 同构测试已被证明是一个 NP完全问题 如果 G哿G， 也称 G包含 G。给定一个图集合 D 邀 G 1 ， G 2 ， ， G n 妖 和 一 个 图 模 式 P，（2）移除不频繁的点与边;（3）移除后，余下的频繁的点与边重新标号，进行降序排列;（4）把集合 GS 中的频繁一边图存于集合 S1 中;（5）按 DFS 词典序，对集合 S1 进行排序;（6）把集合 S1 中元素存于集合 S 中;（7）遍历集合 S1 中单边 e（8）用边 e 初始化 s，遍历集合 GS 中的 g， 凡是包含边 e的图 g，赋予 s 的 GS 中(只记录 g 的 ID);P 在 D 中的支持集定义为 D 中包含 P 的图集合，记为 D supp( P ) 邀 Gi P 哿G i ， G i D 妖 。 D supp ( P ) 称为 P 在 D 中的支持度，记为 supp ( P ; D ) 。 D supp ( P ) D 称为 P 在 D 中的相对支 持度。 支持度度量具有反单调性质:如果 P 1 哿P 2 ， 则 supp ( P 1 ;（9）（10）（11）（12）SubgraphMining(GS，S，s);在集合 GS 中删除边 e;如果集合 GS 中 g（graph）的个数小于 minSup;停止;对于用户给定的 一个最小支持度阈值 D ) supp ( P 2 ; D ) 。minsup，如果 supp ( P ; D ) minsup ，称 P 在 D 中是频繁的。D 中所有频繁图模式集合 记 为 FS 邀 P supp ( P ; D ) minsup 妖 。本文要解决的频繁子图挖掘问题可描述为：给定一个图 数据库 D，一个用户指定的最小支持度阈值 minsup，挖掘该 图数据库上的所有频繁子图。要使用 gSpan 算法完成该任务，需要实现 gSpan 算法中 的如下关键技术：（1）为图模式设计一种唯一性编码方案 ， 使得每个图模 式都对应唯一一个的编码;（2）为高效遍历图模式搜索空间 ， 设计了一种深度优先 枚举框架;（3）基于支持度的反单调性质 ， 使用分支限界算法对图 模式搜索空间进行剪枝，以提高挖掘效率;（4）计算图模式支持度时，设计一些优化策略，在某些条 件下，使用嵌入链表方式可以明显改善挖掘效率;（5） 利用化合物 的 特 殊 结 构(分子化合物中存在很多对 称结构，分子化合物中原子类型分布不均衡)来设计 gSpan 算 法的优化策略。2算法本算法通过 main 函数传递参数，参数包括m i、p、t、minSup、inputfile 和 outputfile 等。m i： 在挖掘子图过程 中 ， 只针对规模小于或等于 i 的 频繁图进行挖掘。p：只保留线性结构。t：只保留树形结构。minSup：指定最小支持度的参数，为整形变量。inputfile：输入数据文件名。outputfile：输出数据文件名。本算法首先使用 preprocessDB 函数进行数据导入处理， 并创建与存储相关的数据结构。 此后算法采用递归调用，进 行深度优先挖掘。深度优先挖掘是算法的核心，主要包含以下三个函数和 子 程 序 ：GraphSetProjection (GS，S)，SubgraphMing (GS，S，s)， Enumerate(s)。函数：GraphSetProjection(GS，S)（1） 从集合 GS（graphSet） 中读图数据， 对点与边按频度 进行排序;子程序 1：SubgraphMining(GS，S，s)（1）如果 s 不是 min(s)返回；（2）（3）把集合 s 加入集合 S 中；（4）添加一条边，生成集合 s 的孩子，即超模式；（5）Enumerate(s)；（6）依次遍历集合 s 的孩子 c如果 c 的支持度大于等于 minSup就把 c 赋予 s 中；SubgraphMining(GS，S，s);（7）（8）（9）子程序 2：Enumerate(s)（1）依次遍历 s 的所有超图 g（2）（3）在图 g 中枚举 s 的扩展，即孩子；依次遍历 s 的孩子 c，同时 c 是图 g 的子图把图 g 作为 c 的超图，链入 c 的超图链表中；如果图 g 覆盖了 s 的所有孩子，break；（4）细节流程见图 1。3实验程序在 VC60 5 环境下开发。 运行环境如下：Microsoft Windows XP Professional 版 本 2002 Service Pack 3，AMD Athlon （tm）64 X2 Dual Core Processor 4200 220 GHz，100GB 的内存，80GB 的硬盘。 实验结果显示：随着支持度的加 大，频繁子图数目在减小，最大的频繁子图规模在减小。 如图2 所示。以 下 关 于 Chemical340， 内 含 340 个 连 通 图 ， 每 个 图 规 模不一，以下为 minSup15 的测试数据。输入：gSpan 15 Chemical340 output340txt输出：Start最小支持度: 15频繁子图数目: 4 984所有频繁子图中，最大的子图大小: 15End总花费耗时 3921 000s以下关于 Compound422，内含 422 个连通图，每个图规模 不 一 ， 以 下 为 minSup50 的 测 试 数 据 ， 同 时 maxFragSize5，即只保留规模小于等于 5 的频繁图。输入：gSpan m 5 50 Compound422 output422txt输出：Start最小支持度: 50频繁子图数目: 462所有频繁子图中，最大的子图大小: 5End总花费耗时 0281 000simon Fraser University， SIGMOD，2000 3 KURAMOCHI M ，KARYPIS G An efficient algorithm for dis covering frequent subgraphsR USA:Department of Computer Science Army HPC Research Center ，University of Minnesota ， In IEEE Computer Society，2002 4 AGRAWAL R，SRIKANT R Fast algorithms for mining association rulesR California :IBM Almaden Research Center，VLDB，1994 5 杨永国 Visual C 60 开发技巧与实例教程M 北京:清华大学 出版社，2004:2345 6 JAHN K，KRAMER S Optimizing gSpan for molecular datasets R Germany:Technische Universit覿t Mnchen ， LudwigMaxim iliansUniversit覿t Mnchen 7 BORGELT C，MEINL T，BERTHOLD M Advanced pruning st rategies to speed up closed molecular fr