（计算机应用技术专业论文）基于相似性度量的图模式挖掘研究.pdf

摘要 随着人们利用信息技术生产和搜集数据的能力大幅提高，数据资料的规模急速 膨胀，我们已经被淹没在数据的汪洋大海中。作为大规模数据处理和决策支持的 关键步骤之一，数据挖掘受到了人们的广泛关注，而频繁模式挖掘是其中一个重 要的研究课题，其研究重点是发现数据中的特征信息，即模式。近年来，频繁模 式挖掘技术已经广泛运用于各个领域，但是，随着数据挖掘越来越多的运用于新 的领域，原来的频繁模式挖掘方法已经无法适应问题的需要。这是因为这些方法 都以项集为基本操作对象，而现实生活中万物皆有内在的联系，彼此之间构成一 张复杂的网，因此用图模型来抽象相关领域的问题更加符合真实情况。在图模型 下，频繁模式的挖掘即是在图中寻找频繁出现的子图。本文在分析已有图模式挖 掘算法的基础上，提出了基于相似性度量的图模式挖掘方法s b p m ( s i m i l a r i t yb a s e d p a t t e r nm i n i n g ) ，它首先利用一个高效的枚举算法找出图中所有规定大小的子图， 然后基于图的顶点及顶点周围结构的相似性度量两个图之间的相似性，在获得的 相似性基础上对这些子图进行聚类分析，将相似子图聚为不同的类别，最后从频 繁的相似子图类别中诱导出图模式。该方法能够直接找到指定大小的模式，并且 通过相似性度量避免了子图同构操作，有效地提高了模式挖掘的效率。通过多种 真实网络数据的验证，s b p m 算法能够准确、高效地挖掘出图中蕴含的模式。 关键词：数据挖掘图模式挖掘图相似性模式 a b s t r a c t w i t hd r a m a t i c a l l yi n c r e a s i n ga b i l i t yo fp r o d u c i n ga n dc o l l e c t i n gd a t a , t h es i z eo f d a t a e x p a n d e dr a p i d l ya n dt h ee x p l o s i v eg r o w t ho fd a t ah a sf l o o d e du sw i t ha t r e m e n d o u sa m o u n to fi n f o r m a t i o n a so n eo ft h ek e ys t e p so fl a r g e s c a l ed a t a p r o c e s s i n ga n dd e r i s i o ns u p p o r t ，d a t am i n i n gh a sa t t r a c t e dag r e a td e a lo fa t t e n t i o n f r e q u e n tp a t t e mm i n i n gi sas i g n i f i c a n tr e s e a r c ht o p i ci nt h i sf i e l d ，w h i c hf o c u s e so n d i s c o v e r i n gc h a r a c t e r i s t i ci n f o r m a t i o ni nd a t a o v e r t h ey e a r s ，f r e q u e n ti t e m s e t d i s c o v e r ya l g o r i t h m sh a v eb e e nu s e dt of i n di n t e r e s t i n gp a t t e r n si nv a r i o u sa p p l i c a t i o n a r e a s h o w e v e r , a sd a t am i n i n gt e c h n i q u e sa r eb e i n gi n c r e a s i n g l y a p p l i e d t o n o n t r a d i t i o n a ld o m a i n s e x i s t i n gf r e q u e n tp a t t e r nd i s c o v e r ya p p r o a c h e sc a n n o tb cu s e d t h i si sb e c a u s em o s to ft h e s ew o r k sp r o c e s st h es i n g l ei t e m ，w h i l et h e r ea r em a n y r e l a t i o n sa m o n go b j e c t si nt h er e a lw o r l d am o r es u i t a b l ew a yo fm o d e l i n gt h eo b j e c t s i nt h e s ea r e a si st o r e p r e s e n tt h e mu s i n gg r a p h s w i t h i nt h a tm o d e l ，o n ew a yo f f o r m u l a t i n gt h ef r e q u e n tp a t t e r nd i s c o v e r yp r o b l e mi st h a to fd i s c o v e r i n gs u b g r a p h st h a t o c c n rf r e q u e n t l yi nt h eg r a p h i nt h i sp a p e r , w ep r e s e n ta na l g o r i t h mb a s e do ng r a p h s i m i l a r i t y , c a l l e ds b p m ，f o rf i n d i n gt h eg r a p hp a t t e mi nas i n g l el a r g ed i r e c t e dg r a p h t h ei d e ai st os t a r tw i t ham e t h o dt h a te f f i c i e n t l ye n u m e r a t e sa l ls i z e - ks u b g r a p h s t h e n t h ea l g o r i t h mc o m p u t e st h es i m i l a r i t yb e t w e e nt w og r a p h sb a s e do nt h es i m i l a r i t yo f t h e i rn o d e sa n dt h es t r u c t u r e sa r o u n dt h en o d e s w et h e nu s et h es i m i l a r i t yv a l u e sf o r c l u s t e r i n gt h e s es u b g r a p h st od i f f e r e n tc a t e g o r i e s f i n a l l y , t h eg r a p hp a t t e r n sa l eg i v e n b yt h ef r e q u e n tc l u s t e r si nw h i c ht h es u b g r a p h sa l es i m i l a rw i t he a c ho t h e r t h i s a p p r o a c ha l l o w sp e o p l et od i s c o v e r yt h es p e c i a ls i z ep a t t e ma n da v o i d st h es u b g r a p h i s o m o r p h i s mp r o b l e mb ym e a s u r i n gt h eg r a p hs i m i l a r i t y e x p e r i m e n t a le v a l u a t i o no n r e a ln e t w o r kd a t af r o mv a r i o u sd o m a i n ss h o w st h a ts b p ma l g o r i t h ma c h i e v e sg o o d p e r f o r m a n c e k e y w o r d ：d a t am i n i n gg r a p hp a t t e r nm i n i n gg r a p hs i m i l a r i t yp a t t e r n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期胪z ) 明 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书 本人签名：碱 导师签名：商互敬 日期和工1 砑 i e i 期j 劲7 2 ，彩 第一章绪论 第一章绪论 1 1 研究背景 自2 0 世纪6 0 年代以来，数据库和信息技术己经系统地从原始的文件处理演 化到复杂而功能强大的数据库系统。尤其在e e c o d d 成功地提出了关系模型后， 为数据库的大发展奠定了坚实的理论基础。几十年过去了，随着计算机硬件存储 能力和软件环境的提高，数据膨胀的时代已经到来。现在，数据的快速增长已经 远远超出了人们理解它们的能力，大量的数据被描述为“数据丰富，知识匾乏”， 人们迫切需要强有力的数据分析工具帮助他们从海量数据中提取有价值的知识。 近1 0 年来，数据挖掘己经引起了信息产业界的极大关注，其主要原因就是数 据挖掘技术可以帮助人们将存在的大量数据转换成有用的信息和知识。获取的知 识可以迅速地反馈到应用领域，并及时指导管理者，赋予了他们更多的领域“智 能”。目前数据挖掘的部分成果己经被广泛地应用于商务管理、生产控制、市场分 析、工程设计、科学探索和国家安全等领域。同时，作为一个新兴的交叉领域， 数据挖掘还受到了人工智能与机器学习、数据库、统计学、生物信息学、社会学 等多学科的关注，涉及从基础的算法理论到具体的实际应用这样广泛的范围。任 何人都不可能对所有的这些方面进行深入的研究，这也使得数据挖掘的研究存在 着不同的角度。 数据挖掘与知识发现这个概念在1 9 8 9 年8 月举行的第1 1 届国际联合人工智 能学术会议i l j 上被首次提出，自此引发了数据挖掘研究的新篇章。上世纪9 0 年代 早期，大部分数据挖掘研究者来自于数据库领域，他们主要是为数据库系统建立 有效的数据分析工具。随后，更多领域的专家加入数据挖掘研究中，考虑问题的 角度也被极大的拓宽，提出了包括关联规则、聚类、分类、例外等数据挖掘方向， 这些方向的建立也更好地推动了数据挖掘的前进。在数据挖掘发展的前期，r a g r a w a l 作出了巨大的贡献，在1 9 9 4 年提出的a p r i o r 算法1 2 l 对以后数据挖掘领域 的工作起了重要的引导作用。在之后的几年间，a p r i o r i 算法被应用于数据挖掘的 各个方向，并作为主要比较对象，也引发了更多优秀的数据挖掘算法的提出。2 0 0 0 年，j i a w e ih a r t 提出了f p g r o w t h 算法i ”，革命性地突破了a p r o n 算法的桎梏， 为数据挖掘领域指引出了新的研究方法。 随着研究的深入，越来越多的问题呈现在我们面前，也提出了更高的要求。 如a p i i o r i 和f p g r o w t h 提出时，主要针对无结构化( 集合) 数据挖掘的研究，提高 挖掘的效率和性能。而目前，复杂类型数据的挖掘需求上升，越来越多的专家学 !基于相似性度量的图模式挖掘研究 者开始关注这方面的新应用和理论研究，并试图利用以往在无结构化数据挖掘方 面的经验和方法论来帮助解决新问题。而针对图结构数据的挖掘与处理就是本文 所致力研究的问题。 1 2 图模式挖掘的研究历史和现状 在绝大多数应用环境中，对象之间或对象内部的关系是错综复杂的，它们很 难用简单的数据结构表述。这就为数据挖掘研究提出了新的课题，即挖掘复杂的 图结构数据。图结构是最通用的数据结构类型，它可以描述世界万物之间错综复 杂的联系。在社会网络分析中，人与人之间、人与物之间的联系是复杂的。通过 抽象方法，可以将整个社会变成一个网络拓扑图，其中每个人可以是图中的节点， 而人与人之间的联系则可以看作为图中的边。对社会人群的分析，自然就可以转 化为对社会网络结构的挖掘。在生物技术领域，生物学家发现蛋白质基因结构配 位实验是费时费力费钱的工作。他们希望引入数据挖掘技术，以减轻结构匹配实 验的代价。蛋白质结构可以被描述为图结构，其中的原子是图中的硬点，而原子 问的价位则是图中对应的边。通过对蛋白质结构图集的挖掘，可以预先发现蛋白 质结构之间的内在关系或共享模式。这些共享模式可以反过来指导基因配位实验， 降低实验的代价。正是由于这些应用的紧迫要求，图结构数据挖掘的研究成为目 前数据挖掘领域的一个重要研究方向。目前，这方面的研究成果很多，主要有： 1 9 9 4 年，l b h o l d e r 等人【4 】提出了著名的子图挖掘算法s u b d u e ，随后还继续提 出了若干改进的方法。s u b d u e 采用最小描述长度原则压缩原始图，并利用启发 式的搜索策略挖掘频繁子图，但不能保证结果集的完整性。算法使用了模糊计算 的方法，从而减少了挖掘时间，提高了挖掘效率。算法的主要目标是针对生物应 用领域的特殊问题。 1 9 9 4 年，k y o s h i d a 等人f 5 l 提出了一个子图挖掘算法g b i ，它类似s u b d u e 算法，但采用了不同的启发式搜索策略。 1 9 9 8 年，l d c h a s p e 等人f 6 】同样提出了在生物化合物分子库中挖掘频繁子结构 的算法。 2 0 0 0 年，a i n o k u c h i 等人 7 1 提出了一个基于a p r i o r i 思想的频繁子图模式挖掘 算法a g m 。该算法与以往的近似算法不一样，它是挖掘频繁模式完全集的。算 法采用顶点增长的方法，利用矩阵计算，逐层挖掘频繁子图。随后在2 0 0 2 年，他 们f 8 j 在a g m 算法的基础上，又提出了挖掘连通的频繁子图算法a c g m ，同样也 是采用了a p r i o r i 思想以及顶点增长的方式。 2 0 0 1 年，m k u r a m o c h i 等人1 9 幌出了一个频繁子图模式挖掘算法f s g 。f s g 算法与a c g m 算法一样，采用了a p r i o r i 思想。但不同之处在于通过边增长的方式， 第一章绪论 ! 逐层挖掘频繁子图。因此，在挖掘性能上，f s g 算法优于a c g m 算法。随后在 2 0 0 4 年，他们1 1 0 l 又提出了一个新的子图挖掘问题，即在1 个稀疏的超大规模的图 中( 包含数以十万计的顶点和边的图) ，挖掘不相邻的子图模式。并提出了2 个算 法h s i g r a m 和v s i g 黜w ，分别采用了宽度优先遍历和深度优先遍历的方法挖 掘子图。 2 0 0 2 年，s g h a z i z a d e h 等人1 1 1 】提出了一种“摘要”的数据结构，用以有损压缩 原始图。“摘要”将图中所有相同标号的顶点集中在一起，使其能快速修剪搜索空 间。作者也指出这种压缩方法比较适用于由较小且较密的结构组成的图。同时， 他们还基于“摘要”方法，提出了相应的子图挖掘算法s e u s 。 2 0 0 2 年，c b o r g e l t 等人1 1 2 1 提出了在化合物分子结构集中挖掘相关的频繁结构 的方法。 2 0 0 2 年，n v a n e t i k 等人i ”l 提出了在稀疏图中挖掘频繁子图的算法，该算法利 用不相邻的路径数量来表达子图特征，逐层计算并生成子图模式。 2 0 0 2 年，x y a h 等人i “i 提出了一个新颖的深度优先搜索图空间的方法，并在 此基础上给出了频繁子图挖掘算法g s p a n 。g s p a n 算法与a c g m 算法、f s g 算法 不同，它没有采用a p d o r i 思想，而是利用边模式增长的方式深度优先挖掘频繁子 图。g s p a n 算法的模式增长思想起源于频繁项集挖掘算法f p g r o w t h ，它具有更好 的挖掘性能。随后在2 0 0 3 年，他们1 1 5 j 在g s p a n 算法的基础上，进一步提出了挖 掘频繁闭合子图的算法c l o s e g r a p h ，频繁闭合子图集是频繁子图集的压缩表达方 式。它可以有效地去除冗余的频繁子图，减少结果集大小，并能保证不丢失任何 信息。在有还原需求时，可将频繁闭合子图集还原成为频繁子图集。 2 0 0 3 年，j h u a n 等人1 1 6 l 提出了一个新的子图扩展策略，并在此基础上形成了 频繁子图挖掘算法f f s m 。算法主要依赖子图“交”和“扩展”这2 种操作，深 度逐层递归挖掘频繁子图。并在实验分析中给出实验结果，说明f f s m 算法优于 g s p a n 算法。随后在2 0 0 4 年，他们旧在f f s m 算法的基础上，更进一步提出了最 大频繁子图挖掘算法s p i n 。最大频繁子图集是频繁子图集的一种近似压缩表达方 式。在生物技术应用领域中，往往不需要所有精确的频繁子图结果，只需要少数 有代表性的子图模式即可，如最大频繁子图模式。因此，最大频繁子图模式挖掘 仍是有应用价值的。 除了上述这些图模式挖掘的通用算法外，研究人员还提出了大量运用于实际 问题的图模式挖掘算法1 1 8 , 1 9 瑚 。综上所述，图模式挖掘算法多种多样，应用广泛。 虽然，由于问题本身的复杂度导致现有算法的效率还不尽如人意，但是该领域的 研究已经展现出广阔的发展空间和蓬勃的生机。 4 基于相似性度量的幽模式挖掘研究 1 3 论文研究目的及主要内容 图模式挖掘算法已被广泛应用于数据挖掘的各个领域，成为解决领域问题的 关键所在，要进一步提高数据挖掘的效率，必须针对特定领域研究更高效的图模 式挖掘算法。研究表明 1 0 l 在一个大规模的图中挖掘图模式是更一般的情况，并且 有更广泛的应用领域。因此，本文的研究集中在一个图中进行模式挖掘，在此基 础上提出了一种高效的图模式挖掘算法。 先前的大多数图模式挖掘算法致力于找出所有的精确频繁子图，但是在许多 应用领域并不需要所有的子图模式，只需要少数有代表性的予图模式即可。同时 在许多实际问题中，研究人员对一组相似但并不完全相同的子图更感兴趣，因为 这更能反映真实的客观世界。比如生物领域的进化行为导致生物结构的变异，使 得变异的结构相似但并不精确相同，映射到模式挖掘上，即是寻找不精确的子图 模式。据此，本文提出了基于相似性的图模式挖掘算法，即挖掘指定大小的相似 子图，并将所有相似的子图抽象为一个子图模式。 本文以下各章节的基本内容组织如下： 第二章：在简要介绍数据挖掘的定义，及目前常用的各种数据挖掘技术的基 础上，重点阐述了进行数据挖掘研究的目的，最后给出了进行数据挖掘的一般过 程。 第三章：详细介绍目前已有的各种图模式挖掘算法。首先介绍了图模式挖掘 的基本概念，并给出了问题的数学定义。接着根据图模式挖掘算法的研究侧重点 将众多的算法进行了简要的分类，在这基础上着重分析了基于a p r i o r i 思想和基于 f p g r o w t h 思想的图模式挖掘算法，然后讨论了现有各种算法的不足之处，引入 基于相似性度量的方法进行图模式挖掘。 第四章：提出基于相似性度量进行图模式挖掘的方法。首先给出了算法的基 本思想和总体框架，然后详细介绍了候选予图的生成策略，接着根据图相似的基 本思想并结合解决的实际问题推导出计算图相似性的迭代公式，在此基础上利用 c h a m e l e o n 聚类算法将相似的子图聚为不同的类别，最后采用与序列模式发现相 类似的方式从频繁的相似子图集合中抽象出最终的图模式。通过大量的仿真实验 研究表明，该算法能够高效的挖掘需要大小的图模式。 第五章：总结了本文的主要内容，以及自己在图模式挖掘方面所作的研究工 作，并且明确了以后的研究方向。 本文的研究分别得到国家自然科学基金项目：生物分子网络数据分析中相关 图问题及其算法研究( n o 6 0 5 7 4 0 3 9 ) 和基于自装配的分子计算模型及算法研究 ( n o 3 0 4 7 0 4 1 4 ) 的资助。 第二章数据挖掘简介 第二章数据挖掘简介 2 1 数据挖掘的定义和分类 目前，对数据挖掘( d a t am i n i n g ) 有广义的和狭义的两种理解。广义的理解认为 数据挖掘即数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 。即从 大规模的数据库中抽取非平凡的、隐含的、未知的、有潜在使用价值的信息的过 程。狭义的理解认为数据挖掘是k d d 的一个步骤。k d d 为从数据中识别正确的、 新颖的、有潜在使用价值的、最终可理解的模式的非平凡的过程。它包括数据选 取、数据预处理和数据清洗、数据挖掘、知识评估等多个步骤。数据挖掘是其中 对经过预处理的数据进行处理，抽取知识的过程。 j i a w e ih a r t 在d a t am i n i n g ：c o n c e p t & t e c h n i q u e s ) 1 2 1 l 中将目前的数据挖掘技 术主要分为以下几类：概念描述、关联分析、分类和预测、聚类分析、例外分析、 趋势分析。 概念描述( 特性描述和区分) 数据可以由一定的概念和类来抽象表示人们对其关心的那部分的性质。简单 明了地描述这些概念和类显然是非常有用的。关于这些概念的描述称为概念描述 ( c o n c e p td e s c r i p t i o n ) ，它包括了特性描述和区分。 关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 是在一个给定的数据集中发现经常同时发生 的多个属性值条件( 一般称为关联规则) 的过程，常用于市场销售和事物数据分析。 但目前，其应用范围也日益拓展。 分类和预测 分类( c l a s s i f i c a t i o n ) 是指为了能够使用模型预测类标签( c l a s sl a b e l ) 还未知的 对象所属的类，而寻找可以描述和区分类或概念的模型的过程，其中类标签指用 来区分类的属性。包括两个步骤：通过分析训练数据空间中的数据，运用分类算 法，建立分类模型；用测试数据空间中的数据估计己建立模型的预测准确性，如 果用户可以接受，则用该模型对未知类别的数据进行分类预测。所谓预侧 ( p r e d i c t i o n ) ，专指对丢失或无效的数据的值的预测。 聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) 是一个将指定数据集中的数据进行归类的过程。 其遵循的原则是每个类内部各对象间的相似性尽可能最大，而不同类对象间的相 似性尽可能最小。在具体实现中，一般用计算对象属性的距离( 欧几里德距离、曼 5 !基于相似性度量的图模式挖掘研究 哈顿距离等) 来体现对象间的相似度。 例外分析 一个数据库中的数据可能不都遵循总的数据模型的行为，这些数据称为例外 ( o u t l i e r ) 。通常数据挖掘方法把例外作为垃圾而抛弃，不过在一些场合下，比如 欺诈检测中，例外却成为了最受关注的焦点。例外分析大致有统计、基于距离、 基于偏差三种方法。 趋势分析 数据趋势分析( e v o l u t i o n a n a l y s i s ) 描述对象行为随时间变化的趋向和规律。这 个概念和特性描述、关联分析、分类、与时间相关的数据的聚类都有些类似，然 而前者更强调对时序( t i m e r i 路) 数据的分析、有序和周期性模式的匹配、基于相 似度的数据分析。 2 2 数据挖掘的目的 数据挖掘的任务是从大量数据中发现知识。那么什么是知识? 这些知识是以 何种形式表达出来? 又是怎样被利用的呢? 知识是人类认识的成果或结晶，包括 经验知识和理论知识。从工程角度定义，知识是有助于解决问题的有格式可复用 的信息。在传统的决策支持系统中，知识库中的知识和规则是由专家或程序人员 建立的，是由外部输入的。而数据挖掘的任务是发现大量数据中尚未被发现的知 识，是从系统内部自动获取知识的过程。对于那些决策者明确了解的信息，可以 用查询、联机分析处理( o l a p ) 或其它工具直接获取，比如“列出各子公司在上 个月的销售情况”。而另外一些隐藏在大量数据中的关系、趋势，即使是管理这些 数据的专家也是没有能力发现的。这些信息对于决策可能又是至关重要的，现在 就让数据挖掘来对付这类问题吧。 数据挖掘发现的知识通常是用以下形式表示： ( 1 ) 概念( c o n c e p t s ) ( 2 ) 规则( r u l e s ) ( 3 ) 规律( r e g u l a r i t i e s ) ( 4 ) 模式( p a t t e r n s ) ( 5 ) 约束( c o n s t r a i n t s ) ( 6 ) 可视化( v i s u a l i z a t i o n s ) 这些知识可以直接提供给决策者，用以辅助决策过程：或者提供给领域专家， 修正专家已有的知识体系；也可以作为新的知识体系转存到应用系统的知识存储 机构中，比如专家系统( e x p e r t s y s t e m ) 、规则库( r u l e b a s e ) 等。 第二章数据挖掘简介 2 3 数据挖掘的过程 数据挖掘过程一般由三个主要的阶段组成：数据准备、采掘操作、结果表达 和解释。知识的发现可以描述为这三个阶段的反复过程。如图2 1 所示。 图2 1 数据挖掘的过程 数据准备 这个阶段又可进一步分成三个子步骤：数据集成、数据选择、数据预处理。 数据集成将多文件或多数据库运行环境中的数据进行合并处理，解决语义模糊性、 处理数据中的遗漏和清洗脏数据等。数据选择的目的是辨别出需要分析的数据集 合，缩小处理范围，提高数据挖掘的质量。预处理是为了克服目前数据挖掘工具 的局限性。 数据挖掘 这个阶段进行实际的采掘操作。包括的要点有： ( 1 ) 要先决定如何产生假设，是让数据挖掘系统为用户产生假设，还是用户自 己对于数据库中可能包含的知识提出假设。前一种称为发现型 ( d i s c o v e r y d r i v e n ) 的数据挖掘；后一种称为验证型( v e r i f i c a t i o n d r i v e n ) 的数据挖掘： ( 2 ) 选择合适的工具： ( 3 ) 发掘知识的操作； ( 4 ) 证实发现的知识。 结果表述和解释 7 ! 基于相似性度量的图模式挖掘研究 根据最终用户的决策目的对提取的信息进行分析，把最有价值的信息区分出 来，并且通过决策支持工具提交给决策者。因此，这一步骤的任务不仅是把结果 表达出来( 例如采用信息可视化方法) ，还要对信息进行过滤处理。如果不能令决 策者满意，则需要重复以上数据挖掘的过程。 第三章图模式挖掘算法 第三章图模式挖掘算法 从数据集中挖掘频繁模式是数据挖掘研究的关键任务。对于不同的数据模式， 频繁模式的具体产生方式往往是不同的。先前的主要研究工作只针对独立的数据 集，如购物篮分析中的项集。然而现实世界中，事物之间往往有着紧密的联系， 如果将结构信息引入频繁模式的产生过程中，将使得新的频繁模式生成过程具有 更好的使用性和扩展性。因此，图模式的挖掘更是数据挖掘研究的热点。本章详 细介绍图模式挖掘算法的相关内容，通过对现有挖掘算法的分析，指出解决图模 式挖掘问题的瓶颈，为后续的内容做铺垫。 3 1 基本概念和问题描述 9 定义3 1 标号图 标号图可以被表示成4 元组，g 一( 矿，e ，厶，) 。其中，矿是顶点集；e 是边集， 且e v v ；l 是标号集：，则是一组从标号到顶点和边的映射，如，：矿u e 一工。 定义3 2 连通图 给定无向图g ，如果图中任意两个顶点问都存在路径可达，那么图g 被称为 连通图。本文所研究的内容即是基于连通图的，因此在本文中提到的图都属于连 通图范畴。 定义3 3 子图 给定标号图g 一( v ，e ，l ，) 和h - i y 。，l f ) ，h 为g 的子图当且仅当 i ) v c _ v ，i o v v , ，v ，y ，砖，v ， e e e ，v ， e ，i i i ) l ( v i ) - i ( q ) ，l ( v j ) - l ( ) 。 定义3 4 图的同构 给定标号图g 1 一( k ，巨，l ，) 和g 2 一( 屹，易，l ，1 2 ) ，g i 和g 2 同构当且仅当存在 一个双射，：k k ，使得t 口，b e l 当且仅当t ，( 口) ，f ( b ) e 2 并且 ( 口) 乞( ，( n ) ) ，f l ( 6 ) - l ：( f t b ) ) 。 目前，还没有工作能证明图的同构是p 还是n p 一完全的。从直觉上讲，图的 同构可以利用穷举法进行判别，但这显然不是个实用的算法。 另一个与同构相关的概念是规范化标记( c a n o n i c a ll a b e l i n g ) 。众所周知，图 可以用关联矩阵来表示。例如，图g 的n 矩阵为m a i j , ( 1 s i ，js ) ，则g 的 编码如下出( g ) = 口。：口。，n 。q 4 2 d 。a n m 。图的规范化标记i 磁冽是一个特殊的序 列，在一定条件下它是唯一的。c o d e ( 6 1 是指g 的所有可能编码中按字典序最大 竺基f 相似性度量的图模式挖掘研究 或最小的一个。因此任何两个图同构当且仅当它们的规范化标记相同。可以知道， 求解规范化标记的过程与同构判定的过程是等价的。 定义3 5 频繁子图挖掘 假定连通标号图的集合d 一 g i i o 1 ，以 ，给定一个最小支持度阈值 m i n s u p ，规定：如果子图g 与g 子图同构，贝i j o ( g ，g ) 一1 ，否则d ( g ，g ) 一0 ， 6 ( g ，d ) d ( g ，g j ) ，如果6 ( g ，d ) z m i n s u p ，则g 是一个频繁子图。频繁子图 6 ：黝 挖掘就是要从输入的连通标号图集合中找出所有频繁子图。 3 2 图模式挖掘算法的类型 为了后续讨论的方便，我们将图模式挖掘算法按照不同情况进行分类： ( 1 ) 按照模式挖掘算法的输入数据类型进行分类：分为g r a p h t r a n s a c t i o n 和 s i n g l e g r a p h 两种类型。g r a p h - t r a n s a c t i o n 型模式挖掘所处理的输入数据是由许多规 模相对较小的图构成的集合，每个图可能只包含几十到几百个顶点；而 s i n g l e g r a p h 型模式挖掘的对象则只有一个大图，这个大图包含成千上万个顶点。 这两种类型的区别还在于它们计算候选子图频度时所使用的策略。 g r a p h t r a n s a c t i o n 型计算模式在图集合每个图中是否出现，不管它在同一个图中出 现了多少次均计数一次，而s i n g l e g r a p h 型则计算模式在这个大图中不同位置出现 的总次数。根据两种类型的特征，解决g r a p h t r a n s a c t i o n 类型的算法不能用来解决 s i n g l e g r a p h 类型模式挖掘。但是s i n g l e g r a p h 类型的算法却能方便应用于 g r a p h t r a n s a c t i o n 类型。 ( 2 ) 按照采用度量的不同进行分类：分为支持度( s u p p o r t ) 、支持度一置信度、 m d l ( m i n i m u md e s c r i p t i o nl e n g t h ) 三种。支持度型挖掘是以子图在输入图中出现 的次数来作为度量的，大部分算法都是基于支持度的；m d l 型挖掘是以压缩输入 数据的程度来度量，一般采用公式阳m e ( 最g ) 一讲( g ) ( 讲( s ) + d f ( g i s ) ) 来计算， 其中s 是子图，g 是输入的图集合，d l ( g ) 表示图集合g 的存储空间，d l ( g i s ) 表 示把g 中所有出现s 的地方都用同一个顶点替换后的图形所需的存储空闯；支持 度一置信度型挖掘是以既要满足最小支持度又要满足最小置信度来衡量的。还有 其它一些度量方法，这里就不再介绍了。 ( 3 ) 按照挖掘出的频繁子图的类型进行分类：分为一般子图、连通子图、诱导 子图等。 第三章图模式挖掘算法 3 3 基于a p r i o r i 思想的频繁子图挖掘 a p r i o r i 思想的核心是g e n e r a t i o n a n d t e s t ：用k 频繁子集生成大小为k + l 的子集， 根据d o w n w a r dc l o s u r ep r o p e r t y 性质( 如果k + l 子集的任何一个k 子集是非频繁的， 贝j j k + l 子集一定也是非频繁的) 进行剪枝，生成k + l 候选集，然后通过对输入数据 进行扫描判断候选子集中哪些是频繁的。如此下去，直到不能找到频繁子集为止。 当前，主要有两种基于a p r i o r i 思想的频繁子图挖掘算法，它们之间的主要区 别在于操作对象的方式不同。一种是以a g m l 7 1 和a c g m 8 j 为代表的对顶点进行逐 层构造求解的算法，另一种是通过对边的操作以达到同样目的算法，如f s g 。 最早将a p r i o r i 思想用于频繁子图挖掘的是a g m 算法，该算法能在 g r a p h t r a n s a c t i o n 型输入图集合中挖掘出满足最小支持度和最小置信度的所有频 繁诱导子图。a g m 算法采用邻接矩阵来表示图，利用规范化标记进行编码，从 而避免直接进行复杂的子图同构计算。a g m 算法的具体步骤如下： ( 1 ) 根据a p r i o r i 算法的思想，首先将频繁顶点作为初始集，然后判断大小为k 的子图g ，是否包含同一个大小为k 一1 的子图- 1 ，如果包含则将，h 中 c o d e 大的作为第二个操作因子，生成候选子图c “1 - + 日。这样通过每次添加 一个顶点来生成候选k + l 子图c “1 。 ( 2 ) 根据d o w n w a r dc l o s u r ep r o p e r t y 性质进行剪枝。如果c “1 的k 子图中有任 何一个是非频繁的，那么c “1 也一定是非频繁的，那么可以将它剪掉。 ( 3 ) 计算候选子图的支持度就是找出候选子图包含在输入图集合中哪些图中， 即进行子图同构的判断。由于子图同构是一个n i 问题，为避免直接计算子图同 构，a g m 引入了m i l l ( c o d e ) 来唯一标识一个图，从而计算出每一个候选子图的支 持度。 总的说来，a g m 算法的思路比较简单，以递归计数为基础，可以挖掘出所 有频繁子图。但是对于包含较多图的输入集合来说执行效率非常低，主要是因为 a g m 在生成候选予图时要判断是否存在相同的七q 子图，当七很大时，这需要花 费很长时间。并且通过每次添加一个顶点来产生候选子图时会产生许多冗余k + l 子图。在剪枝的过程中，也需要很多时间来判断每个k + l 候选子图的所有k 子图是 否都是频繁的。剪枝后的候选子图仍然很多，因此需要大量的重复扫描输入图集 合来计算候选子图的支持度。这就占用了大量的内存空问和c p u 处理时间，很难 发现较大的模式子图，执行效率不高。而a c g m 算法是在a g m 算法的基础上提 出来的。区别在于a e g m 算法旨在发现连通的频繁子图，采用了一些特殊的技巧 以提高性能。它引入了半连通图的概念，图g 是半连通图当且仅当g 是连通图或 g 只由一个连通分支和一个孤立点组成。在a e g m 算法中所使用的规范化标记将 旦基于相似性度量的图模式挖掘研究 顶点的标号也考虑在内，同时还应用了诸如规范化标记发现和k 树等技巧来提高 其性能。k u r a m o c h i m 等人提出的f s g 算法采用完全不同的找寻方法挖掘频繁子 图。在他们的算法中采取每次添加一条边的策略，而不是每次添加一个顶点，并 加强了候选子图的剪枝，在计算候选子图的支持度时采用t i d 列表帮助加速计算， 使得执行效率较a g m 有所提高。 3 4 基于f p g r o w t h 思想的频繁子图挖掘 f p g r o w t h 算法的主要思想是将产生频繁集的数据压缩到一棵频繁模式树 f p t r e e 中，用f p t r e e 存储项的关联信息，然后对模式树产生频繁集。g s p a n 算法 和f f s m 算法是f p g r o w t h 思想在频繁子图挖掘中的典型应用，它们都能在 t r a n s a c t i o n 型的输入图集合中挖掘出所有频繁连通子图。下面将详细介绍这两种 算法。 3 4 1g s p a n 算法 首先介绍几个概念。 m i n i m u md f sc o d e ：首先对图进行深度优先搜索，从而形成一棵d f st r e e ， 然后根据 ，来扫描该图，则扫描的边的顺序就构成了一个序列，称为d f sc o d e 。 对这个图的所有d f sc o d e 按照字典顺序进行排序，找出最小的d f sc o d e 来唯一 标识这个图，这个最小的d f sc o d e 被称为m i n i m u md f sc o d e 。 空问树：将图的m i n i m u md f sc o d e 作为一个空问树的节点，对该节点进行 最右路径扩展，把生成的新子图作为该节点的孩子，同一父节点的不同子节点之 间是按照字典顺序排序的，这样就生成了一棵空间树。如果将该空间树的所有非 频繁子节点剪枝就形成了一棵频繁子图树。 o c c u r r e n c e ：如果子图譬与输入图集合中的图g 具有子图同构关系，则g 被称 为g 的o c c u r r e n c e 。 算法的基本思想为： ( 1 ) 计算输入图中所有边的支持度，将所有非频繁边从输入图集合中删除，并 以频繁边作为初始子图。 ( 2 ) 产生候选子图：对k 频繁子图的m i n i m u md f sc o d e 的d f st r e e 进行最 右路径扩展，每次添加一条边，得到k + 1 候选子图。该方法经证明能够保证挖掘 结果的完整性。 ( 3 ) 剪枝：如果k + 1 候选子图不是m i n i m u md f sc o d e 形式的，则认为该图 第三章图模式挖掘算法 是冗余的，从候选子图中删除。 ( 4 ) 每次在计算k 频繁子图的支持度时，同时记录k 频繁子图的所有 o c c u r r e n c e 。这样，k + 1 候选子图的支持度就可以通过对k 频繁子图的所有 o c c u r r e n c e 进行最右路径扩展获得。 ( 5 ) 缩减图集合：当某条频繁边的所有子节点都生成后，就将该边从输入图集 合中删除，缩减输入图集合。 该算法的核心思想如下： a l g o r i t h ms u b g r a p h m i n i n g ( d ，s ，s ) 1 ：弗d 表示输入图集合 2 ：撑s 是挖掘到的频繁子图 3 ：i fs m i n ( s 1t h e n 4 ： r e t u r n ； 5 ：s s u t s ； 6 ：e n u m e r a t esi ne a c hg r a p hi nda n dc o u n ti t sc h i l d r e n ； 7 ：f o r e a c hc ci ss c h i l d d o 8 ：i f s u p p o r t ( c l m i n s u pt h e n 9 ：s - c ： 1 0 ： s u b g r a p h m i n i n g ( d ，s ，s ) ； 该算法在生成候选子图的时候，由于采用了最右路径扩展以及相应的剪枝措 施，大大减少了冗余候选子图的产生，在计算候选子图支持度的时候采用了对 o c c u r r e n c e 进行扫描，而不是对输入数据库进行扫描，避免了大量重复扫描数据 库的问题。但是，对于大型输入数据库，该算法效率仍然很低。 3 4 2c l o s e g r a p h 算法 基于图的频繁闭子图挖掘算法有许多种，有基于a g m 的，也有基于g s p a n 算 法的。这里简单地介绍一下基于g s p