图的结构及应用

图的结构及应用

数据收集从大量、不完整、噪声、模糊和随机数据中提取，并嵌入其中。人们事先不知道的，但潜在有用的信息和知识流程。这些数据可以是结构化的,如关系数据库中的数据,也可以是半结构化的,如文本、图形、图像数据,甚至是分布在网络上的异构型数据。针对半结构化数据的研究已经成为近年来国内外数据挖掘领域的研究热点,而目前国内的研究热点主要集中在文本数据挖掘等领域,针对图的数据挖掘研究才刚刚开始。与一般的数据比较,图能够表达更加丰富的语义,在科学研究和许多商业领域有着更为广泛的应用。同时,这种丰富的语义也增加了数据结构的复杂性和挖掘令人感兴趣的图的子结构的难度。因此,需要综合应用图论知识与数据挖掘的各种技术。本文主要对经典的Apriori算法进行改进,引入图论知识,使之能够对由无向图组成的数据库进行频繁子图的挖掘。1频繁子图挖掘算法框架图的数据挖掘主要是从图的数据库中找到大于最小支持度的频繁子图。Apriori算法是从购物篮分析中引出的经典数据挖掘算法,可以有效地从事务数据库中挖掘出频繁项集,但是由于图是一种复杂的数据结构,原始的Apriori算法不能用于图的数据挖掘。因此,有必要对Apriori进行数据结构和算法的改进,使得改进后的算法适合于频繁子图的挖掘。频繁子图挖掘必须解决子图同构问题。直观地说,子图同构即是确定图G’是否为图G的子图。子图同构已经被证明是一个NP完全问题,所以必须附加限制条件来减少搜索空间,降低算法的时间复杂度。1.1理论的子图挖掘子图同构:图G’子图同构于图G,当且仅当图G中存在子图G’’,使得G’’同构于G’。导出子图:记V(G),E(G)分别为图G的顶点集和边集,则G’是G的导出子图当且仅当V(G’)⊆V(G),E(G’)⊆E(G)且对∀u,v∈V(G’),{u,v}∈E(G)⇔{u,v}∈E(G’)。直观地说,G的导出子图G’的顶点集是G的顶点集的子集,而G’的边集由原图决定,即:G’中任意两顶点之间是否有边与G中相应的两顶点之间是否有边一一对应。本文中所提到的子图挖掘均针对导出子图。其中图1(b)是(a)的导出子图并且图1(b)子图同构于(a),图1(c)是(a)的一般子图。在引入这两个概念之后,还要对图的所有顶点和边注明标记,以区分不同的顶点和边,同时允许同一个图中出现相同的顶点标记和边标记。如在化学有机物分子结构图中经常出现相同的碳原子C或氢原子H标记。这样,有了顶点标记和边标记之后,就可以大大减少子图匹配时的搜索空间,从而在一定程度上回避了关于子图同构的NP完全问题所带来的困难。给定图的数据库D={G0,G1,…,Gn},导出子图G的支持度定义如下:而所谓频繁导出子图就是支持度大于指定的最小支持度min＿sup的导出子图。另外,记size(G)表示图G中顶点的个数,这在后面的算法描述中将被用到。1.2基于规范矩阵的编码无向图的数据结构定义采用邻接矩阵表示法,为了提高算法的效率,根据对称性,只保留邻接矩阵的下三角阵。这样无向图G的邻接矩阵元素xij定义如下:即对角线元素为顶点标记,下三角阵其余元素为边标记或0(当边不存在时)。同时规定,顶点标记按词典有序。这样,图1(a)的邻接矩阵表示就如图2所示(本文提到的邻接矩阵的组成元素均为字符)。可见,即使规定顶点标记按词典有序,由于允许出现相同的标记,因此不能保证邻接矩阵的唯一性。为此,本文引入规范矩阵的概念,使得该矩阵能够与图形成一一对应关系。首先,对符合以上定义的邻接矩阵X进行如下方式的编码:则规范矩阵定义为:当图G只有一个邻接矩阵描述时,该邻接矩阵就是图G的规范矩阵;当图G存在多个邻接矩阵描述时,取Code值最大的邻接矩阵作为图G的规范矩阵。Code值的大小比较遵循词典有序规则,其中a>b>…>z>0。如图2的两个邻接矩阵记为M1和M2,则它们的Code值分别为:因为Code(M1)>Code(M2),所以取M1作为图1(a)的规范矩阵。1.3u3000jb3-3-k-项频繁导数子图Apriori算法利用候选集寻找频繁项集。候选集的产生采用自底向上的思想,由频繁k-项集产生候选k+1-项集,主要由两步组成:连接步和剪枝步。其中,利用了Apriori性质来压缩搜索空间。所谓Apriori性质,即频繁项集的所有非空子集都必须也是频繁的。扩展到图的数据库中,即频繁导出子图的所有非空导出子图都必须也是频繁的。以下具体说明改进后的连接步和剪枝步以及计算候选子图支持度的方法。(1)连接步:设矩阵Xk和Yk分别是含k个顶点的频繁导出子图对应的规范矩阵,其中,则可以连接它们产生k+1个顶点的候选导出子图所对应的矩阵Zk+1,其中,xT和yT是(k-1)维行向量。zk+1,k的值由顶点标记xkk和ykk之间是否存在边来确定,这有两种可能。有关文献的方法是:将这两种可能都直接加以肯定。而本文对此作了进一步的改进。本文确定zk+1,k的值的方法如下:如果顶点标记xkk和ykk之间不存在边,则zk+1,k取0,连接结果只有一个;如果存在边,则zk+1,k就等于该边的边标记,同时也保留zk+1,k=0的情况,即连接结果有2个。另外,如果Zk+1对应的子图是频繁的,则由Apriori性质,它所有的导出子图也必须是频繁的,所以如果xkk和ykk之间存在边,则该边一定是频繁的,从而其必被包含在2-项频繁导出子图集合之中。由此,边标记的具体值可以通过扫描2-项频繁导出子图集来得到。图3是一个具体的连接实例。其中图3(c)中bc之间是否存在边由频繁2-项集决定。通过连接操作得到的矩阵Zk+1可能不再是规范矩阵,因此要将其调整为规范矩阵。(2)剪枝步:剪枝主要是为了减少候选空间,即考察Zk+1是否应该作为频繁导出子图候选。同样要用到Apriori性质,考察Zk+1的所有k-项子集Zk(Zk需要被调整为规范矩阵),当且仅当所有这样的Zk都属于k-项频繁导出子图集合时,就把Zk+1添加到k+1-项频繁导出子图候选集合中。(3)计算Zk+1支持度:在k+1-项频繁导出子图候选集合产生后,就要通过扫描数据库,计算其中每一个候选Zk+1的支持度,来决定它是否是频繁导出子图。当Zk+1与数据库中某一事务G的子图G’的顶点标记和边标记一一对应时,就将该候选的计数值增加1。在全部扫描完成后,将候选计数值除以数据库事务总个数就得到该候选的支持度,如果该支持度大于指定的最小支持度,则将Zk+1添加到k+1-项频繁导出子图集合中。在算法的实际实现中,是首先将最小支持度与事务总个数相乘得到一个最小计数值,而每一个Zk+1的计数值只需和这个最小计数值相比较即可。2chl1lk-12输入:以规范矩阵形式描述的图的数据库D={M1,M2,…,Mn}和最小支持度min＿sup。输出:频繁导出子图集合L。主算法基本和Apriori算法相同,参见文献,需要改变的是第一步扫描数据库时不仅要产生频繁1-项集L1,而且要产生频繁2-项集L2,而循环则从寻找频繁3-项集开始。以下给出关键子程序算法的完整描述。(1)产生k-项频繁导出子图候选集Ck的子程序:1)foreachl1∈Lk-12)foreachl2∈Lk-1//频繁k-1项集Lk-1中任意不同的//两项仅连接1次,以避免重复连接3){5){6)扫描频繁2-项集L2,确定顶点标记为l1[k-1][k-1]和l2[k-1][k-1]的两顶点之间是否存在边标记。若不存在,连接l1和l2,得到候选c1,其中c1[k][k-1]=0,其它元素由l1和l2确定;若存在边标记p,连接l1和l2,得到候选c1和c2,其中c1[k][k-1]=0,c2[k][k-1]=p,c1,c2的其它元素由l1和l2确定;7)调整步骤6)所产生的c1或者c1和c2为规范矩阵;8)对每一个c1或c2(当c2存在时)的k-1项子集s//剪枝过程9){10)调整s为规范矩阵;11)if(s不属于Lk-1)12)删除c1或c2,goto2;13)}14)添加c1或c2到Ck中;15)}//endif16)}(2)判断矩阵c是否被t所包含(子图同构)的子程序:1)x=c,n1=size(c),n2=size(t);//n1,n2是顶点个数(即行数或//列数)2)遍历t的对角线元素3)if(存在t[k][k]=x)goto5);4)returnFALSE;//判断顶点标记和边标记是否相同7)returnTRUE;8)elsereturnFALSE;3实验结果及分析本文中,算法性能的验证是通过对一个小型数据库进行仿真实验而得到的。该数据库中的每个图元素均以规范矩阵形式存储,包含300个随机数据,每个数据最大顶点个数为10,最大边个数为20。库中顶点标记和边标记的总个数都为100。实验环境为:奔腾Ⅲ1GHz处理器,128MB内存,Windows2000操作系统。参数设置和实验结果如表1所示。其中,运行时间和内存消耗保留到小数点后1位。从表1中可以看出,当支持度较小的时候,算法的运行时间和内存消耗随着支持度的减小而急剧增加,近似于指数级的变化趋势。4研究局限及建议本文用邻接矩阵表示图,以经典的Apriori算法为基础,并且通过对其关键步骤:连接步和剪枝步的改进,得到频繁导出子图的候选集。同时,提出了一种解决子图同构问题的算法,利用该算法来计算每一个候选的支持度。从而,得到了一种能够有效地进行频繁导出子图挖掘的方法。本研究仍存在需要改进的地方:首先,本文的算法还只能处理无向图,需要继续研究能够处理有向图的方法;其次,大量的候选集的产生是算法执行效率的瓶颈之一,因此应该继续研究减少候选集甚至不产生候选集的适应于图的数据挖掘的方法;最后,从算法的性能分析可以看出:当最小支持度较小时,算法的效率剧降,并挖掘出了一个很大的频繁导出子图集,然而有些频繁导出子图的实际意义不大,例如单个顶点标记。所以在以后的