（计算机应用技术专业论文）图的数据挖掘.pdf

中国科学技术大学硕士学位论文 图的数据挖掘 摘要 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取 隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。这些 数据可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、 图形、图像数据，甚至是分布在网络上的异构型数据。针对半结构化数据的研究 已经成为近年来国内外数据挖掘领域的研究热点日前国内的研究热点主要集中 在文本数据挖掘等领域，针对图的数据挖掘的研究才刚刚开始。 在计算机科学领域，图是最复杂的数据结构之一，与一般的数据比较，图能 够表达更加丰富的语义，同时，这种丰富的语义也增加了数据结构的复杂性和挖 掘令人感兴趣的图的子结构的难度。因此，需要综合应用图论知识与数据挖掘的 各种技术。图具有直观的表达形式，图的数据挖掘无论在研究领域还是在商业领 域都有着广泛的应用。例如：c a d 电路分析、分子模型分析、w e b 浏览中的用户兴 趣点的挖掘、以及数据的压缩等等。因此，如何从大量的图中挖掘出令人感兴趣 的子图模式也应该成为国内的数据挖掘领域研究的热点之。 本文完成的工作主要如下： 1 ) 调研了种图的数据挖掘的方法s u b d u e 系统使用的方法，该方法与 我们的方法的目的都是挖掘子图结构，但是两者的思想是截然不同的。 并且还对相关的数据挖掘知识做了详细的介绍，以作为图的数据挖掘中 的数据挖掘基础。 2 ) 结合图沦知识，对经典的a p r i o r i 算法进行了改进，并提出了一种图的数 据挖掘方法，该方法能够对由无向图组成的数据库有效地进行频繁导出 子图的挖掘。 3 ) 由于2 ) 的方法只能对无向图进行处理，所以本文还研究了处理有向图的 思想。该思想的主要算法和2 ) 的方法中的主要算法基本相同，但是在数 据结构的表示和处理上却是刁i 一样的。这种能够处理有向图的方法去除 了原图中的边标签，并且还能处理顶点带自身环的情况。 4 ) 最后对本文的工作做了一个总结并对未来提出了展望。 关键词：图，a p r i o r i 算法，数据挖掘 i 中国科学技术大学硕士学位论文图的数据挖掘 a b s t r a c t d a t am i n i n gi sap r o c e s so fm i n i n gu s e f u li n f o r m a t i o na n dk n o w l e d g e ，w h i c ha r e h i d d e ni ng r e a tv o l u m e so fd a t a ，s o m e t i m e si n c o m p l e t e ，f u z z y , w i t hn o i s e ，e v e n r a n d o m t h ed a t am i g h tb es t r u c t u r e d ，e g ，d a t ai nar e l a t i o n a ld a t a b a s e ，a n dt h ed a t a m i g h tb es e m i s t r u c t u r e d a sw e l l ，e g ，t e x t ，g r a p h i c s ，i m a g ea n dd a t aw i t hd i f f e r e n t s t r u c t u r e s ，d i s t r i b u t e di n an e t w o r kr e s e a r c ho nm i n i n gs e m i s t r u c t u r e dd a t ah a s b e c o m eam a j o rc o n c e r ni nt h ef i e l do f d a t am i n i n g i nc h i n a ，ag r e a td e a lo f w o r kh a s b e e nd o n eo nm i n i n gt e x td a t a ，w h i l ef o rg r a p h b a s e dd a t am i n i n g ，i ti sj u s ta b e g i n n i n g i nc o m p u t e rs c i e n c e ，t h eg r a p hi soneo f t h em o s tc o m p l i c a t e dd a t as t r u c t u r e s i t s s e m a n t i cr i c h n e s sp l a c e sm o r ec o m p l e x i t yi ni t sd a t as t r u c t u r ea n dm o r ed i f f i c u l t yi n m i n i n gi t si n t e r e s t i n gs u b s t r u c t u r et h eg r a p ht h e o r yi s o f t e nu s e dt o g e t h e rw i t h v a r i o u st e c h n o l o g i e si nd a t am i n i n gg r a p hc a nb ei n t u i t i v e l yp r e s e n t e da n dh a sa w i d ev a r i e t yo fa p p l i c a t i o n sb o t hi nr e s e a r c ha n di nb u s i n e s s ，e gc a dc i r c u i t a n a l y s i s ，m o l e c u l a rm o d e la n a l y s i s ，f i n d i n gu s e r si n t e r e s ti nw e bb r o w s i n ga n dd a t a c o m p r e s s i o na c c o r d i n g l y , h o wt od e r i v et h ei n t e r e s t i n gs u b g r a p hp a t t e r n sf r o mt h e g r e a tv o l u m eo f g r a p h s t r u c t u r e dd a t as h o u l db e c o m eoneo f t h eh o t t e s ti s s u e si nd a t a m i n i n gf i e l d t h ed i s s e r t a t i o ni so r g a n i z e da sf o l l o w s ： na ni n v e s t i g a t i o nt oam e t h o do fm i n i n gg r a p h - b a s e dd a t a s u b d u es y s t e m , w h i c hs h a r e st h es a m ep u r p o s eo fm i n i n gs u b g r a p hs t r u c t u r ea so u rm e t h o d ，b u ti na q u i t ed i f f e r e n tw a y t o g e t h e rw i t had e t a i l e di n t r o d u c t i o nt od a t am i n i n g ，w h i c hi s t h eb a s i sf o rg r a p h b a s e dd a t am i n i n g 2 ) i m p r o v et h ec l a s s i ca p r i o r ia l g o r i t h m ，w i t ht h eh e l po ft h eg r a p ht h e o r y , a n d p r e s e n to u rm e t h o dt om i n eg r a p h b a s e dd a t a ，w h i c hi sc a p a b l eo fm i n i n gf r e q u e n t i n d u c e ds u b g r a p hi nad a t a b a s ew i t hu n d i r e c t e dg r a p hd a t a 3 ) s i n c eo u rm e t h o da p p l i e so n l yt ou n d i r e c t e dg r a p h ，w ed i df u r t h e rr e s e a r c h i n t on e wi d e a so fh a n d l i n gt h ec a s eo fd i r e c t e dg r a p h t h en e wi d e ab a s i c a l l yh a st h e s a m ea l g o r i t h ma s2 ) ，b u ti sd i f f e r e n ti nr e p r e s e n t a t i o na n dh a n d l i n go ft h ed a t a s t r u c t u r e i tr e m o v e st h el i n kl a b e l sa n di sc a p a b l eo fd e a l i n gw i t ht h ec a s eo f s e l f - l o o p sv e r t i c e s i v 中国科学技术大学硕士学位论文图的数据挖掘 4 ) c o n c l u s i o na n df u t u r ew o r k k e y w o r d s ：g r a p h ，a p r i o r ia l g o r i t h m ，d a t am i n i n g v 中国科学技术大学硕士学位论文圈的数据挖掘 第一章绪论 1 1 图的数据挖掘技术的产生背景 这些年来，数据挖掘已引起了信息产业界的极大关注其主要原因在于存在 大量的数据可以被广泛地使用，并且迫切需要将这些数据转换成有用的信息和知 识。获取的信息和知i ： 可以广泛用于各种应用。针对半结构化数据【l 】的研究 已经成为近年来国内外数据挖掘领域的研究热点，而目前国内的研究热点主要集 中在文本数据挖掘等领域，针对图的数据挖掘的研究才刚刚开始。就目前来说， 图的数据挖掘的主要目的是提供新的原则和有效的算法以挖掘嵌入在图中的拓 扑结构。在计算机科学领域，图是最复杂的数据结构之一，与一般的数据比较， 图能够表达更加丰富的语义，同时，这种丰富的语义i 虹增加了数据结构的复杂性 和挖掘令人感兴趣的图的子结构的难度。因此，需要综合应用图论知识与数据挖 掘的各种技术。图具有直观的表达形式，图的数据挖掘无论在研究领域还是在商 业领域都有着广泛的应用。例如：c a d 电路分析、分子模型分析、w e b 浏览中的用 户兴趣点的挖掘、以及数据的压缩等等。因此，我们有必要研究图的数据挖掘技 术。 1 2 目前图的数据挖掘技术方法的分类 1 2 1 基于贪心搜索的方法 s u b d u e 系统【2 】和g b i 【3 】使用的是贪心搜索方法并且在图的匹配问题上 使用的是不精确的图的匹配算法以避免图的同构问题的高度复杂性。它们都从图 中抽取出了公共予结构，但它们进行的是不完全搜索，这就有可能导致丢失最佳 的子结构。 s u b d u e 系统处理的是连通图【4 】，并且这个连通图的顶点和边都要加上标 签。s u b d u e 系统寻找的子图结构足能够最大压缩输入图g 的子图结构，压缩的 方法使用了m d l ，原则。可以把被找到的子图结构看作一个概念。s u b d u e 系统使 用的算法是柱型搜索算法。算法开始的时候，有待扩展的子图结构仅仅只是输入 图中的一个顶点，然后这个顶点随着算法不断扩展。在每一步扩展中，对每一个 子图结构都会计算1 ( s ) + l ( g i s ) 【5 l ，在这个公式中，s 是被发现的子图结构，g 是输入的图，l ( s 1 是必须用于编码被发现的子图结构的b i t s 的数量，在用子图 结构s 对原图g 进行压缩以后，用，( g 心) 表示必须用于编码被压缩后的图g 的 b i t s 的数量。如果哪个子图结构的，( s ) + z ( g i s ) 最小，那么这个子图结构就作为 中国科学技术大学硕士学位论文 圈的数据挖掘 最优子结构被保存起来。这个算法是完全贪心的，是没有回溯的。因为柱型搜索 的最大柱宽已经预定好了，所以有可能丢失最佳的子结构。s u b d u e 的一个特征 是：它的子图匹配算法是不精确匹配算法，所以它允许在子图匹配中出现轻微的 图的扭曲。 1 2 2 归约数据库方法 m o l f e a 系统使用的是归约数据库方法，m o l f e a 系统使用的是l e v e l w i s e 版本空问算法【6 】。该方法虽然对原图执行了完全的路径搜索，但是它所挖掘的 子结构被限制在图中的连续子结构的范围里。 1 2 3 归约逻辑编程( i l p ) 方法 w a p 。m r 【7 】和f a i 姒r 【8 】使用的是i l p 方法。虽然它们进行也是完全搜索 并能够发现公共子图结构，但是它所挖掘的子图结构的类别被限制在了连通子图 结构的范围里面。 1 2 4 数学图论方法 数学图论方法【9 】能够从图中抽取出频繁出现的公共子结构，并且能够执 行完全搜索。因为数学图论方法要处理图的同构问题，解决图的同构问题的算法 是多种多样的。而精确的图的匹配( 同构) 的难度相当于n p 完全问题( n p 完全问 题是这样的问题：用确定性的算法在多项式时间内无法解决的问题。) 的难度， 这时就要加上一定的限制条件以减少搜索空间，以便于在一定程度上回避n p 完 全问题的难度，从而达到降低时间复杂度的目的。 1 3 图的数据挖掘技术的应用 1 3 1 w e b 浏览中的用户兴趣点的挖掘 今天的数据量以及数据的复杂性正在不断地提高，例如w w w 服务器日志文 件。在w w w 服务器曰志文件巾记录了用户浏览w e b 的历史。u r l 表示该网站上的 不同的信息位置。每一次访问可以用一个图来表示，图的顶点代表不同的u r l ， 图的有向边代表访问过程。整个访问日志就可以抽象为图的集合。所以通过对这 个图的集合进行数据挖掘操作并提取频繁出现的子图结构，不但可以压缩服务器 日志文件，而且可以看出人们的访问习惯，以便找出用户的兴趣点，从而有助于 网站设计者在超链接上的设计。例如：通过对网站访问者访问刚站的习惯的分析 可以发现，网站访问者从u r la 经过许多其他的u r l 访问到u r le 的频率非常高， 中国科学技术大学硕士学位论文 图的数据挖掘 这就说明网站访问者喜欢由u r la 直接访问到u r le ，但是在网站的超链接设计 上却没有设计出从u r la 直接到u r le 的超链接，所以这时网站设计者就有必要 考虑是否应该在u r la 与u 刚，e 之问加k j x 接的超链接以便于网站防问者能够更 加方便的访问该| 叫站： 1 3 2 分子模型分析 分子的模型可以抽象为一个图的集合，在化学试验中经常需要找出特定的分 子结构以确定某种物质的属性，例如经常需要在一个化学混合物的分子模型中找 出具有致癌属性的分子结构的分子数量。这时我们就可以用图的数据挖掘技术对 这个代表化学混合物的分子结构的恻的集合进行处理，以找出我们所需要的子图 结构及其实例。 1 3 3 c a d 线路分析 c a d 电路图也是可以抽象为一个图的集合的。根据领域专家对子图结构实例 的频繁性要求的设定，再通过图的数据挖掘技术在c a d 电路图上的应用，就可以 计算出电路予结构出现的频繁性，从而让用户知道哪种子电路图的应用是频繁 的，最终让用户对那些频繁出现的子电路图的实用性加以肯定。 1 3 4 数据的压缩 在一个可以抽象为元素是图的结构的数据库中，可以通过应用图的数据挖掘 技术来找出频繁出现的某种子图结构的实例，然后用一个指向该实例的指针来代 替该实例，通过这种代替可以大大的压缩数据库的大小。 1 4 图的数据挖掘技术的研究历史 在过去的一些年里，数据挖掘已经作为一个新的研究领域出现了，数据挖掘 的研究对很多令人感兴趣的话题做了讨论，并且将研究结果应用到了现实生活当 中去。在一开始的时候，数据挖掘的研究对象局限在关系表和事务集之中，关系 表中的每一行代表每一个实例，或者用一个集合表示一个事务。但是后来数据挖 掘的研究对象扩展到了半结构化数据，例如：h t m l 文本和x m l 文本、符号序列、 有序树以及用先进逻辑表示的关系。在一些主要的国际杂志和会议上，提出了许 多关于针对半结构化数据的数据挖掘的文章【1 0 l 。在过去的些年里，针对符 号序列的数据挖掘和机器学习的研究也变得积极起来了。在i l p ，a l t 和d s 会议 【1 l 】上就出现了很多这方面的文章。而且，在过去的一些年里，很多研究者都 开始了挖掘有序树结构【i 2 】的工作。与结构化数据有关的一个研究话题是多元 中囡科学技术大学硕士学位论文躅的数据挖掘 关系数据挖掘，这种研究的主要作用范围足从来自于复杂的多元关系和结构化数 据的表达力丰寓的逻辑关系语言中找到模式【l 3 】。挖掘半结构化数据、符号序 列以及有序树的主要目的足从结构化数捌巾抽取模式。基于这个框架，通过对挖 掘出来的频繁性和信息熵值的测量，模式挖掘被描述了特征。 最近，根据对数据结构中拓扑结构的研究，一个新型的数据挖掘领域出现了。 在数学中，最复杂的拓扑结构之一是图。用文本标签、符号序列以及有序树或者 无序树表示的半结构化数据都属于普通图的子类。在9 0 年代中期，由c o o k 和 h o l d e r 提出的s u b d u e 系统和m o t o d a 提出的g b i 系统【1 4 】是从图的数据库中 发现子图模式的最早的研究。他们使用了贪心搜索的方法，以避免图的同构问题 的高度复杂性，但是得到的结果只是不完全的子图结构的集合。在1 9 9 8 年， i ) e h a s p e 和t o i y o r l e l 提出了一个基于i l p 的方法w a r m r ，这个方法可以对图 的数据库进行频繁子图的完全挖掘。后来，n i j s s e n 和k o k 提出了一个更快的算 法f a r m e r 。在2 0 0 0 年，i n o k u c me ta l 提出了一种数学图论的方法。在2 0 0 1 年，d er a e d t 和k r a m e r 提出了一个基于版本空问的m o l f e a 系统以从图中发现 特征路径。此后，关于图的数据挖掘的研究仍在继续的进行。 1 5 目前图的数据挖掘技术中的难点 对于现在提出的多种图的数据挖掘算法来讲，它们是各有各的优点与缺点。 例如s u b d u e 系统，他用的是贪心搜索算法和不精确的图的匹配算法，这样做的 优点是在一定程度上回避了图的同构问题所带来的巨大复杂性，缺点是：它进行 的是不完全搜索，容易丢失最佳子图结构。数学图论方法进行的是完全搜索并且 用的图匹配算法是精确的图的匹配算法，不会丢失解，但是却要面对n p c 难度的 图的同构问题，所以就必须给算法加上很多限制条件以降低时间复杂度，这样就 使算法的功能受到了限制。所以对于图的数据挖掘技术来说，目前的难点就是很 难找出一种方法，这种方法具有目前所有方法的绝大部分优点，其缺点的危害性 小到不足以让人考虑。所以我们应该对目前的方法仔细研究，取长补短，争取能 够找出一种最理想的方法。 本文的组织结构是这样安排的：第一章是绪论；第二章对s u b d u e 系统使用 的图的数据挖掘方法做了调研，s u b d u e 系统使用的方法和我们的方法的目的都 是挖掘子图结构，但是思想是截然不同的；第三章对我们的图的数据挖掘算法所 需要用的理论基础( 数据挖掘知识) 作了详细的介绍；第四章对我们的图的数据挖 掘算法做了详细的介绍；由f 我们的方法只能处理有向图所以在第五章我们还研 究了处理有向图的思想；第六章埘全文进行了总结，并对未来提出了展望。 4 中国科学技术大学硕士学位论文 图的数据挖掘 今天，随着数据量的大量增加以及复杂度的极大提高，人们迫切地需要提高 对大型数据库进行数据挖掘的能力。而且这些数据中的大部分在本质上是结构 化的，或者组成这些数据的每一部分之间都是有联系的。因此，我们需要开发一 定的工具以在结构化的数据库中分析和发现概念。 本章的目的是介绍一个能够在元素为图的结构的数据库中进行数据挖掘的 系统s u b d u e 系统。 2 1 介绍 在数据大量被收集的今天，研究者们正在努力地试图解释这些数据并从中找 到令人感兴趣的模式。为了能够达到这个目的，许多研究者已经开发了在数据库 中发现概念的技巧【3 2 ，3 3 ，3 4 】。尽管在这些大量的数据中有着显示的或者隐式 的结构化成分，但是却很少有方法可以用】j 处理这种问题【3 5 】。 在结构化的数据当中发现知识的一种方法是从元素为图的结构的数据库中 挖掘公共子图结构。之所以这么做的目的，不仅是为了能够通过抽取出公共子图 结构以用于压缩数据，而且也是为了能够更加有力的在概念上提高数据的解释。 子图结构的挖掘过程就是从图结构的数据当中识别出令人感兴趣的或者重复的 子图结构的过程。一旦这个子图结构被挖掘，那么就可以通过用指向这个子图结 构概念的指针来代替这个子图结构实例以达到压缩数据的目的。 本章描述了s u b d u e 系统如何在图结构的数据库中挖掘令人感兴趣的子图结 构。s u b d u e 系统挖掘的子图结构可以用于压缩原始数据库，并且这个子图结构 也代表了令人感兴趣的结构概念。通过利用被挖掘出来的子图结构来压缩数据 库，s u b d u e 系统逐渐地在数据库中产生了一个分层的子图结构规律性的描述。 2 2 使用s u b d u e 系统进行子图结构的挖掘 s u b d u e 系统可以在数据库中挖掘可以用于压缩原始数据并且可以表示结构 化概念的子图结构。这个子图结构挖掘系统把结构化数据表示为一个加以标签的 图。在s u b d u e 系统的方法中，o b j e c t s 是指图中的顶点或者子图。o b j e c t s 间的 r e l a t i o n s h i p s 是指图中的有向边或者无向边。在图的表示中，子图结构是指连 通子图。在一个输入图中，一个子图结构的实例是顶点和边的集合，并且这些顶 点和边的集合可以构成一个图的表示，也就是说它们组成了连通子图。在s u b d u e 中国科学技术大学硕士学位论文图的数据挖掘 这个子图结构挖掘系统中，输入是：图的表示。图2 一l 是一个数据库中的个几 何图形的例子。图2 1 展示了被发现的子图结构的图的表示，并且强调了多个子 图结构的实例之一。 i n p u tg r a p h f 。- r l 一一 s u b s t r u c t u r e 图2 1 图结构实例 s u b d u e 系统使用的子图结构挖掘算法是柱型搜索。s u b d u e 系统的挖掘算法 被展示在了下一页。算法的第一。一步是初始化p a r e n t l i s t ( p a r e n t l i s t 中包含了即 将被扩展的子图结构) ，c h jl d l i s t ( c h i l d l i s t 中包含了已经被扩展的子图结 构) ，并且初始化b e s t l i s t ( b e s t l i s t 中包含了s u b d u e 系统至今为止已经发现的 被赋予了最高启发值的子图结构) 为空，并且还设置了p r o c e s s e d s u b s ( 至今为止 己经被扩展的子图结构的数量) 为0 。上面四个表中的每一个表都是关于子图结 构的链表，按照子图结构被赋予的启发值的非增顺序来排序。对于每一个唯一的 顶点标记来说，一个子图结构的定义就是带有那个顶点标记的顶点，并且这个子 图结构的实例就是图g 中带有那个顶点标记的所有顶点。将所有的单个顶点的不 同的子图结构插在p a r e n t l i s t 中。 内部的w h i l e 循环是算法的核心。p a r e n t l i s t 中的每一个子图结构轮流地 从p a r e n t l i s t 头部去除，并且被去除的子图结构的每一个实例都用尽一切可以 用的方法进行扩展。扩展的方法是：通过给这个子图结构的实例增加图g 中的 条新边和一个新顶点，如果某两个顶点本身就在这个子图结构实例中，那么这种 情况的扩展就是直接在这两个顶点问加上一条新边。对于一个新c h i i d 来讲，每 一个唯一的扩展的第一个实例就变为了一个新c h i l d 子图结构的定义( 概念) ，并 且所有的用以上相同方法进行扩展的c h i l d 实例就变为了c h i l d 子图结构的实 例。另外，用不同扩展方式产生的，并且匹配c h i i d 子图结构定义的且在匹配闽 值( m a t c h c o s tt h r e s h 0 1 d ) 内的c h i l d 实例也变为了c h i l d 子图结构的实例，总 之，就是通过上面介绍的扩展方法( 扩展的方法是：通过给这个子图结构的实例 增加图g 中的一条新边和一个新顶点，如果某两个顶点本身就在这个子图结构实 6 中国科学技术大学硕士学位论文圈的数据挖掘 例中，那么这种情况的扩展就是直接在这两个顶点间加上一条新边。) ，不仅可以 可以产生新的c h ii d 子图结构的定义，而且还可以产生很多在此定义下的新的 c h i i d 实例。 s v a d u 辩( g r a p h ，b e a m w i d t h ? m a x b c s t ，m a x s u b s i 涨。l h n i t ) p a r e n t , l i s t 一 c h i m l i s t 一 b c 搿t ；i s t 一 l r 壮c 彀娜l s u b 8 - o c r e a t e 鑫s u b s l ：r u e t n r 啦f r o me a t i ：hu u i q u e 蝌t e xl a b e la n di 鼯s i n g l c - v e z t , e x h m t a n c e 蜷；i l l s e nt l 地l 秣轴l t i n g 葬t l l 礴t r u e t t 埘# 臻i np a r e n t l i s t w h i l ep m 懒x t s u t m m a x b e s tt h e n d 鹅t n wt h es l 】t 缚“瞄“i 艇a t t h ee n dt 汀l 融t l i s t s w i t c hp a e n t l i s ta n dc h i k l l i s t r e t u r nb e s t l i s t s u b d u e 系统的算法 用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 ) 为每一个c h i l d 赋予一个启发值 ( h e u r i s t i c ) ，并且这些被赋予了启发值的c h i l d 都按照以启发值为序的原则安 插到了c h i l d l i s t 中。在s u b d u e 方法中，通过控制c h i l d l i s t 的长度来达到控 制柱型搜索的柱宽的目的。具体做法是这样的：在插入一个新c h i i d 到c h i l d l i s c 中国科学技术大学硕士学位论文图的数据挖掘 中之后，如果c h i l d l i s t 的长度超过了柱宽，那么删除c h i i d l i s t 末尾的子图结 构。然后把c h i l d l i s t 的头部元素插在b e s t l i s t 中，并用相同的方法把b e s t l i s t 的长度限制在不超过m a x b e s t 的范围内。当p a r e n t l i s t 为空时，就将p a r e n t l i s t 和c h i i d l i s t 作一个转换，其目的是：让p a r e n t l i s t 拥有下一代即将被扩展的 子图结构。s u b d u e 的运行时间南一个多项式决定，这个多项式的参数可以由以 下内容的一个或者几个组成：柱宽、用户定义的可以处理的予图结构的数量限制、 还包括在不精确的图的匹配算法中的计算上的限制，以及一些用户设置的其他限 制等等。 在s u b d u e 系统中，用户可以指定的参数之是一通过决定是否要抛弃一个其 启发值比其在c h i l d l i s t 链表中的父亲节点的启发值还要小的c h i l d 的方式来控 制子图结构挖掘搜索空问是否需要被修剪。在挖掘过程的早期，一个给定的子图 结构的实例数量非常大，并且这个实例数量控制着启发值，因为实例的数量可以 是启发值的参数之一。随着子图结构的增加，因为子图结构变得更加的具体更加 的复杂，所以这些新的子图结构的实例就急剧减少，这就意味着启发值往往也随 之减少。如果启发值减少得足够小，那么所有的c h i l d 子图结构就会被抛弃( 因 为它们的启发值没有达到用户规定的启发值闽值) ，所以等待扩张的子图结构的 链表就会变为空，这时算法结束。还有一种方法可以使算法结束：如果用户指定 了子图结构大小( 子图中顶点的个数) 的最大值m a x s u b s i z e ，如果某个c h i l d 子 图结构的大小比m a x s u b s i z e 大，那么这个c h i i d 就不会被插迸c h i l d l i s t 中， 这就会导致p a r e n t l i s t 和c h i l d l i s t 最后为空，这时算法结束。 一旦发现了一个子图结构那么就可以通过用一个指向子图结构的指针来代 替子图结构的实例，以达到压缩数据的目的。s u b d u e 系统允许从原始数据库中 的复杂结构中挖掘予图结构。就己发现的子图结构而论，重复的子图结构的发现 和压缩数据过程给予了结构化数据一个分层的描述。这个分层的描述给予数据以 各种各样的解释。 2 3 基于如l 原则的启发值 在s u b d u e 系统中，赋予子图结构的启发值的确定是建立在m d l 原则的基础 上的，m d l 原则即：m i n i m u md e s c r j p t i o nl e n g t hp r i n c i p l e 。m d l 原则可以很 好的描述数据集，它最小化了整个数据集的描述长度【3 6 1 。本地计算机( 编码器) 进行描述长度的计算，并且发送一个概念的描述给远程计算机( 解码器) 。本地计 算机( 编码器) 必须把概念编制为一串可以送往远程计算机( 解码器) 的b i t s ，远 程计算机( 解码器) 必须对这串b i t s 进行解码以恢复出原始的概念。m d l 原则已 中国科学技术大学硕士学位论文 图的数据挖掘 经被刚j - 决策树归纳【3 7 1 、基凶序列叫 的模式发现【3 8 1 、陶像处理【3 9 ，4 0 ，4 l 】、 对关系数据的概念学习 4 2 l 、以及非同类工程领域的学习模型 4 3 】。 在这一小节里，我们说明如何用本节介绍的图的编码方式来计算 i ( s ) 4 - 1 ( o l s ) ，因为i ( s ) + 1 ( o l s ) 的大小直接影响着启发值的设定，s u b d u e 系统 认为最好的子图结构是能够最小化，( s ) + 1 ( c f s ) 的子图结构。我们定义幅图的 最小描述长度为：为了完整描述幅图所必须要的b i t s 数量。 在s u b d u e 系统中，最好的予图结构是能够最小化，( s ) + i ( g i s ) 的子图结构。 在这个公式中s 是被发现的子图结构，g 足输入的图，1 0 ) 是必须用于编码被 发现的子图结构的b i t s 的数量，在用子图结构s 对原图g 进行压缩以后，用 1 ( o l s ) 表示必须用于编码被压缩后的图g 的b i t s 的数量【2 】。 在本节中用邻接矩阵来表示图的连通性，考虑一个具有n 个顶点的图，这 些顶点被标号为0 ，1 n - 1 。一个n $ n 的邻接矩阵a 中的每项用a i ，j 来表示， a i ，j 等于0 或1 。当a i ，j = o 表示从顶点i 到顶点j 没有边，当a i ，j = l 表示从顶点i 到顶点j 至少有一条边。图的邻接矩阵表示形式如下所示： 州，洲窿7 w 如 图的编码由以下步骤组成。我们瑕设解码器有唯一的对于原始图g 的标签表， 其大小为l u 。 1 确定需要用于编码阁的顶点标签的b i t 位的数量v b i t s 。首先我们需要l g v 个b i t s 位来编码图中顶点的数量v 。然后，为了编码所有v 个顶点的标签需要 v ( 1 9 l u ) 个b i t s 位。我们假设按照顶点在邻接矩阵中出现的顺序来指定顶点。所 以编码顶点标签的b i t s 位的总数v b i t s = 1 9 v + v ( 1 9 l u ) 。例如在图2 2 中，v = 6 ， 并且我们假设解码器有唯一的对于原始图g 的标签表，其人小为l u = 8 ，所以编 码顶点标签的b i t s 位的总数为：1 9 6 + 6 1 9 8 = 2 0 5 8 b i t s 。 2 确定需要用于编码邻接矩阵a 的行的b il s 位的数量r b i t s 。典型地，在 大图中，一个顶点仅仅只和图中的其它小部分顶点有边相连，因此在邻接矩阵的 行中，i s ( 标记为i 的项) 的是很少的，比起图中顶点的总数v 来是要少得多的。 假设第i 行中包含k i 个l s ，那么就有( n - k i ) 个o s ，b = m a x ( k i ) ，那么邻接矩阵 0 0 b 0 l o 0毋l爵o 9 o o l 0 、。0 l 0 娃稃o o l静舔o 0 拈 o o 狰o o 好 茹如静w r i f 够 绷 洳 删 中国科学技术大学硕士学位论文 的第i 行可以编码如下： ( a ) 编码k i 的值需要l g ( b + 1 ) 位b i t s 图2 2m d 。图的实例 图的数据挖掘 最后，我们需要额外的l g ( v + 1 ) 位b i t s 来编码用于指定k i 值的b i t s 所占 用的编码位数，以便让解码器知道整个b i t s 流中有多少位是用于编码k i 的。邻 接矩阵总的编码长度是： r 3 叭= 竺l g ( b 喜+ l ( ) 1 麓x l g 铲 ) = ( v + 1 ) + l ：i 7 ，9 3 ，+ - g ( ： + - g ( ： + - g ： + ，g ： + g ( ? + b i t s 的数量是 = 2 1 4 9 b i t s 。 ；的边的b i t s位的数量 e b i t s 。需要用于编码项a i ，j = 1 的b i t s 的数量是1 9 m + e ( i ，j ) 1 + l g ( 1 u ) ，其 中e ( i ，j ) 表示图中顶点i 和j 之间边的实际的数量，m = o ( i ，j ) ，l g m 用于编码i 和j 之间边的数量， 1 + l g ( 1 u ) 用于编码边的标签和边的有向或者无向，除了编 码边之外，我们还需要编码用于指l g m 的b i t s 所占用的编码位数，以便让解码 器知道整个b i t s 流中有多少位是用于编码l g m 的。所以边的总的编码量为： e b i t s 2 l g m + ( m j l g m + e ( i ，j ) 1 + l g l u ) 1 0 能丫l，呵u 雌g褫射 矾谯不= 苫 的的行况，隋第的在置现位出现h 咀v 行度在 ， s 酏马 薰嘛个要卜需k 以啪所饴种 对叶 有共 。 性 位 中国科学技术大学硕士学位论文图的数据挖掘 = l g m + e ( 1 + l g 。) + 舷卅i g m i = ij = 1 = e ( 1 + l g f ) + ( k + i ) l g m 公式中，e 是图中边的数量，k 是邻接矩阵 中i s 的数量。例如在图2 2 中， e = 5 ，k = 5 ，m = l ，l u = 8 ，所以边的总的编码量为5 ( 1 + 1 9 8 ) + 6 1 9 1 = 2 0 。 所以图的编码总量为v b i t s + r b i t s + e b i t s ，例如在图2 2 中，编码总量为： 6 2 0 7 位b i t s 。 不管是输入图还是挖掘。t “来的子图结构都能够用以上方式对其进行编码。当 发现了一个子图结构后，输入幽当中的每一个子图结构的实例都会被一个单独的 顶点所代替。用i ( s ) 位b i t s 来编码被挖掘出来的予图结构，并且被用子图结构 代替方法处理过的原图则用i ( g l s ) 位b n s 来编码。对s u b d u e 系统来说，最好 的子图结构应该满足条件：最小化i ( s ) + i ( g 心) 。所以可以根据i ( s ) + i ( g i s ) 的 值来设定启发值的大小。 2 4 不精确的图的匹配算法 虽然用精确的图的匹配算法能够找到很多令人感兴趣的子图结构，但是在整 个数据库中有许多令人感兴趣的子图结构却是以轻微的差异的方式展现出来。这 些轻微的差异也许归咎于噪音或者扭曲，也许这些轻微的差异仅仅是说明了同一 类子图结构的实例之间的少许差异。考虑图2 3 。铅笔和立方体在这副图像中可 以成为具有代表性的子图结构，但是一个精确的图的匹配算法并不会认为铅笔和 立方体是具有代表性的子图结构，因为图像中的众多铅笔之问和立方体之间都存 在着少许差异。 给定一个输入图和一个集合的子图结构，s u b d u e 的不精确的图的匹配算法 试图从输入图中找出那些与给定的予图结构最接近的子图结构实例。并且，我们 要测量出给定的子图结构和与该子图结构匹配的子图结构实例之间的差异程度。 我们采用的方法是b u n k e a 1 1 e r m a n n 提出的不精确的图的匹配算法【4 4 1 。 在不精确的图的匹配算法中，对一幅图的每一个扭曲都要赋予其一个代价。 扭曲是一种变形的情况，例如：删除、插入、以及顶点和边的替换。扭曲的代价 值是由用户决定的，以便反映用户对不同类型的扭曲的不同的在意程度。 对于不精确的图的匹配算法来说，将9 1 与9 2 匹配时，我们可以将9 2 解释 为g l 的一个扭曲的版本。一般来说，一个不精确的图的匹配是一个映射 f ：n 1 寸，y 缸 ，。和，分别是g l 和9 2 的顶点集合。如果顶点v n 1 ，有条 中国科学技术大学硕士学位论文 图的数据挖掘 因 图2 - ：3 情景分析实例 图：2 - 4 两个相似的图g i 和9 2 囡 件，0 ) = a 成立，那么v 就被删除。也就是说v n ，在9 2 中找不到对应的顶点。 就像上面已经讨论过的，给定一个集合的特定的扭曲代价值，我们定义一个不精 三一。w弯 蟛 一 。二b。| 卜 中国科学技术大学硕士学位论文 圈的数据挖掘 确的图的匹配的映射f 的扭曲代价为c o s t ( f ) ，这个代价c o s t ( f ) 是在一次映射 中所产生的全部扭曲的代价的总和，并且我们定义m a t c h c o s t ( g l ，9 2 ) 为g l 匹配 到9 2 时的最小代价值。 给定g i 和9 2 以及扭曲代价的设定，那么我们可以通过一个树的搜索过程来 计算实际的m a t c h c o s t ( g l ，9 2 ) 。搜索树的每一个状态刘应一个部分的匹配状态： 9 1 顶点集的子集匹配到了9 2 顶点集的子集。最初，我们从搜索树的树根开始， 在树根状态，匹配结果为空。出现一个新的状态相当于在搜索树中增加一个新的 节点，该节点是一个顶点对，该顶点对由g l 的一个顶点和9 2 的一个顶点组成。 搜索树的最后一个状态是；gl 的所有顶点都与9 2 中的顶点或者五匹配了。图2 - 4 的搜索树展现在图2 5 中。对于这个例