相似度度量

相似度度量（精选4篇）

相似度度量 篇1

0 引言

随着社会经济以及科学技术的迅速发展, 为了扩大社会效益、提高人才培养率, 科技与教育的结合程度越来越高。近年来, 在高等院校教育机制日臻完善的前提下, 社会对学校创新人才的培养越来越重视, 对学校教师的课程设计以及学生程序设计实践课的要求也越来越高。要实现知识结构多元化, 就要对相关设施进行剽窃检测, 从而保证高质量教育人才培养与时代发展接轨。程序代码相似度的识别是近年来维护知识产权、尊重原创、倡导自主创新社会价值引导的重要环节。对程序代码形似度度量进行分析研究, 符合教育现代化的要求。

1 程序代码相似度度量

程序代码具备特有的运作规范, 对程序代码的修改若不能按照程序运行的规范模式进行, 就会影响甚至终止程序运行。代码相似度是指两个程序彼此之间重合率的高低, 百分之百的重合率即代表着完全抄袭, 两个程序代码形似度的高低就可以反映出抄袭情况。

程序代码相似度度量有属性检测和结构检测两种。早在20世纪70年代初, 就有学者研究阻止大规模拷贝程序的技术和软件, 出现了一批比较典型的程序源代码剽窃检测系统[1]。这些检测系统就是早期程序代码相似度度量的雏形。随着科学技术的进步以及信息技术等发展, 程序代码相似度度量由原始简单检测向着用更精准的字符串规范表示程序结构, 选择高效迅速的字符串重合匹配算法的方向发展, 程序代码相似度度量算法研究不断健全和完善。这些研究与实践应用在减少相似度度量的时间长度, 提高相似度度量的精准性方面取得了很大的成效。

属性检测在对每个程序进行检测时, 分别设计4个统计值:X1=单一操作符的数量, X2=单一操作数的数量, Y1=所有操作符的总量, Y2=所有操作数的总量。根据这4个基本赋值统计结果, 定义X=X1+X2作为词汇量, Y=Y1+Y2作为执行长度, 再根据以上数据计算出程序的容量V=Ylog2 (X) , 然后将这些数据结果进行整合生成一个特征向量M (X, Y, V) 。为每个待检测其重复率的程序都建立一个特征向量之后, 再计算每两个向量之间的距离。若检测的两个程序的特征向量之间的距离很小, 就可以认为这两个程序重复率很高, 进而检查对这两个程序之间是否存在抄袭。

结构检测是根据程序的结构来度量两个程序之间的相似度, 这就要求对被检测程序的内部构成进行分析。在这种检测方法中, 要明确程序语言规范, 将程序语言按照某种标准转化成单一字符串, 然后通过某种算法对这些字符串进行比较, 从而判断两个程序之间的重复率。

2 算法

由于属性检测技术存在着遗漏和忽略程序结构信息的弊端, 在检测过程中的错误率较高, 因此在近来开发的检测系统中多使用结构检测方法。算法就是结构检测系统的核心环节。

算法是将程序代码的字符串中的每个字符逐一进行对比, 通过对比检测出程序代码中相同字符的数量, 从而判断程序代码的抄袭率。由于字符串中字符量大, 在程序代码相似度度量过程中, 检测难度和复杂度大, 时间长, 效率低。如果把字符串划分为N个不同的小字符串, 对每个小字符串重新赋值, 那么重合的字符串就可以被同一简单值表示, 这样便减小了检测单位, 降低了检测的复杂程度, 必然可以提高检测效率。

在实际重复率检测过程中, 对检测的程序一般不进行精准匹配检测, 所以, 算法在程序代码相似度度量中的应用率越来越高, 对其进行研究可以提高程序代码相似度度量的质量和效率。

3 算法在程序代码相似度度量中的应用

3.1 代码分割

将被检测的程序代码进行有效分割, 把长字符串划分成多个可以赋值的子串, 具有精准重合和模糊重合的程序代码就会被同一值表示。将两个待检测程序的代码按统一标准分割, 在检测时就可以很快的将具有相同赋值的字符串查找出来, 对具有相同赋值的字符串所表示的程序结构和程序步骤进行抄袭度对比, 便可以得到相关数据。代码分割可以有效地缩减检测程序的单位, 从而减少检测时间提高检测效率。

3.2 特征向量相似度的获取

代码分割后, 将程序按结构划分为不同的信息序列。提取出来的程序结构信息和基本结构元素相结合, 就可以形成一个特征向量, 这个向量就是待检测程序所对应的特征向量。以此类推, 每个待检测程序都可以通过这种方法来生成特征向量。特征向量降低了检测的复杂度和检测单位, 对于快速准确的检测程序的重合程度和重复率帮助很大。

3.3 程序结构相似度的获取

经过属性度量的方法可以获取程序对的标准规范赋值标识符序列, 应用动态规划算法的思想中最长公共子序列算法计算出最优值, 进而得到最长公共标识符子序列, 其他个别情况下可以用自底向上建立地推关系地计算方法计算最优值来提高算法的效率。

由算法LCTS_LENGTH计算得到的数组可用于表示建立的快速构造表的最长公共标识符子序列。在特殊情况下, 可以用递归算法来设计程序的运行构造表。

对于改变关键字的拷贝问题、更改引用文章、调换文章段落、更换新的赋值表示、改变程序代码的顺序、改变程序代码字符串组合的程序语言的顺序、对表达式中的操作符和操作数的顺序进行调换和改变、数据类型转换等更改方式的一种或几种共用进行修改后, 得到的程序对在属性相似度检测中能够检测出较高的重合率, 即相似度较高。但某些情况下, 两个程序的相似度偏高却与其属性检测相关度低, 就必须结合结构相似度来对两个程序的相似度进行考察。

程序结构相似度的获取能够为高效查重和反抄袭提供技术支持, 程序结构相似度的获取有效的弥补了属性检测存在的不能识别结构重合的弊端, 是整体相似度检测的关键环节。

4 结论

程序代码相似度度量技术在检测抄袭率方面发挥着重要的作用, 将算法应用于程序代码相似度度量中, 能够实现对待检测程序的自动化精准复制检测, 从而提高创新水平和社会效益。

参考文献

[1]于海英.程序代码相似度度量的研究与实现[J].计算机工程, 2010 (2) :45-47.

[2]邓爱萍.程序代码相似度度量算法研究[J].计算机工程与设计, 2008 (9) :4636-4639.

[3]全上克, 杨新锋.程序代码相似度检测方法的设计与实现[J].研究与设计, 2013 (10) :38-41.

相似度度量 篇2

云模型是李德毅院士在模糊数学和概率统计的基础之上,通过特定的结构算法所形成的定性概念与其定量表示之间的转换模型。云模型将自然语言中定性概念的模糊性和随机性有机地结合在一起,实现了定性语言值与定量数值之间的自然转换[1,2]。正态云模型通过三个数字特征(期望、熵、超熵)描述信息的模糊性和随机性,这三个数字特征值把模糊性(边界的亦此亦彼性)和随机性(发生的概率)完全集成到一起,构成定性和定量相互间的映射,作为知识表示的基础,有效的反映了模糊性和随机性之间的关联性。

付斌等[3,4]归纳了正态云模型应用活跃的几个领域(数据挖掘、算法改进、网络安全等),分析它在这些应用中的方法和优势,其中数据挖掘是一个重要的应用方向。数据挖掘中的定量数据可以通过正态云模型来实现定性概念转换,同时建立在定性概念基础之上的数据挖掘任务需要进行相似度计算,例如不确定性分类、聚类、相似性搜索等。特别的,在股票时间序列数据挖掘中,云模型可以对时间序列数据进行分段概念表示,需要利用云模型相似性计算方法来度量概念之间的距离,以便在挖掘过程中发现潜在的序列模式和其它信息。因此,在云数据挖掘应用领域中,正态云模型相似度计算方法的优劣直接影响到数据挖掘算法的效率[5]。张勇等[6]提出了一种通过随机取若干个云滴,计算云滴平均距离值来表示正态云模型的相似度,但选取云滴、对云滴的排序以及云滴的组合将不利于大规模数据;张光卫等[7]将正态云模型的数字特征当作向量,利用夹角余弦来计算相似度,这种方法容易忽视熵和超熵的作用。李海林等[5]提出通过求解两个正态云模型期望曲线和最大边界曲线相交重叠部分面积来表示云模型的相似度,这两种方法前者忽视了超熵的作用后者扩大了超熵的作用,而且仅考虑重叠面积衡量云模型相似度仍然不够,尤其对于两个云模型具有包含关系的情形。本文依据云模型的统计特征重新定义了正态云期望曲线,将修正的正态云期望曲线看作正态模糊数,考虑内积和外积即考虑重叠面积与非重叠面积之比的方法,提出基于组合模糊贴近度的云模型相似度计算方法。实例表明,该方法在一定程度上能够克服现有方法的不足。

2 云模型概念及数字特征

云模型是用语言值表示的某个定性概念与其定量表示之间的不确定性转换模型,它把模糊性与随机性这二者完全集成在一起构成定性和定量相互间的映射[1]。

定义1设U是一个普通集合,U={x},称为论域。C是论域U上的概念。论域U中的元素x对C的隶属函数μC(x)∈[0,1]是一有稳定倾向的随机数。概念C的云模型是从论域U到区间[0,1]的映射,有

从云的基本定义出发,论域U中某一个元素与它对概念C的隶属度之间的映射是一对多的转换,而不是传统的模糊隶属函数中的一对一的关系。

定义2设U为论域,C是论域U上的定性概念,若定量值x∈U,且x是定性概念C的一次随机实现,若满足:x～N(Ex,En'2),其中,En'～N(En,He2),且对C的确定度满足:

则称在论域U上的分布成为正态云模型。

正态云期望曲线是研究正态云重要几何特征的重要方法,刘常昱等[8]证明了由正态云发生器算法生成的正态云模型(1)产生的云滴是一个期望为Ex,方差为En2+He2的随机变量,因此,文献[5]定义的期望曲线方差忽视了超熵的作用,具有一定的缺陷,为此定义如下改进的正态云期望曲线。

定义3若随机变量x满足:x～N(Ex,Wn'2),其中En'～N(En,He2),且En≠0),则

称为正态云的修正期望曲线。

正态云模型是基本的云模型,正态分布具有普适性,大量社会和自然科学中定性知识的云的期望曲线都近似服从正态或半正态分布[9]。正态云的数字特征反映了定性概念和定量特性,用期望Ex(Expected Value)、熵En(Entropy)、超熵He(Hyper Entropy)三个数值来表征,如图1所示。

3 基于组合模糊贴近度的正态云相似度计算

模糊贴近度概念是我国学者汪培庄教授[10]于1982年提出的,它不同于一般数学意义下的“相似度”,它是用来描述两个模糊数之间的贴近程度,对贴近度的公理化定义是由刘学成[11]完成的。

定义4设Ψ(U)为论域U的模糊幂集,若映射C:Ψ(U)×Ψ(U)→[0,1],满足

则称为模糊数的贴近度。

设论域U为实数域R,则依据定义4和内积和外积的性质,定义下列模糊贴近度

其中,表示两个模糊数重叠面积与非重叠面积之比,表示两个模糊数重叠面积与总面积之比。

假定正态云修正期望曲线是一个正态模糊数,则正态云模型相似度计算就可以理解为计算两个正态模糊数的贴近度问题。设两个正态模糊数为

若a1<x*<a2,则两个模糊数的交点横坐标为

则由式(3)和式(4),相应的

为了计算方便，令类似的令，有

将上式代入式(6)和式(7),得

对于上述,记,

则有

若a2<x*<a1时,类似的也可以得到上述结果。对于上述两个模糊贴近度,定义下列算术平均组合模糊贴近度

因此,对于两个正态云模型N1(Ex1,En1,He1)和N2(Ex2,En2,He2),则基于组合模糊贴近度(Combined Fuzzy Similarity Measure,CFSM)的云模型相似度为

4 实例分析

为了更好的说明云模型相似度计算方法的有效性,分别利用文献[6]和文献[7]中示例数据进行数据实验,并且与现有方法进行比较,分析它们的实验结果。

实例1文献[6]给出3个正态云模型N1=(3,3.1 23,2.05),N2=(2,3,1),N3=(1.585,3.556,1.358),如图2所示,这3个正态云模型具有熵和超熵比较大的特征,也即模糊性和随机性都比较大,因此在计算它们的相似度时,不但要考虑熵的因素也必须要考虑超熵的作用。

利用Matlab软件以及正态云发生器,由组合模糊贴近度公式(11)对3个正态云模型的相似度进行计算,实例结果如表1所示。

由表1可知,N2和N3的相似度最大((0.9035),N1和N2的相似度次之(0.7790),N1和N3的相似度最小(0.7223),这个结果与图2的直观印象一致。由表2容易发现,SCM、ECM和CFSM方法的结果一致,但是CFSM方法效果更好,这是因为SCM算法通过取随机云滴的平均值,并计算平均值的距离度量云模型的相似度,这种方法容易引起结果的不稳定;EC M方法没有考虑超熵的作用,计算结果要大于CFSM方法;MCM方法虽然考虑了超熵的影响,但是采用最大边界曲线方法扩大了超熵的作用,导致了与其他三种方法不同的结果。

实例2文献[7]给出了4个正态云模型N1=(1.5,0.62666,0.3390),N2=(4.6,0.60159,0.30862),N3=(4.4,0.75199,0).27676),N4=(1.6,0.60159,0.30862),如图3所示,这4个正态云模型的熵和超熵虽然都不是很大,而且相互之间相差不大,在计算它们的相似度时,也必须要考虑超熵的作用。

利用Matlab软件以及正态云发生器,由组合模糊贴近度公式(11)对4个正态云模型的相似度进行计算,实例结果如表3所示。由表3可知,N1和N4的相似度最大(0.88),N2和N3的相似度次之(0.79),N1、N4和N2、N3的相似度最小(0.00、0.01),这个结果与图3的直观印象一致。由表4容易发现,LICM、ECM、MCM和CFSM方法的结果一致。但是,CFSM方法能够更好的鉴别云模型的相似度,LICM方法认为(N1,N4)和(N2,N3)的相似度一致(均为0.99),ECM方法认为(N1,N4)和(N2,N3)的相似度相差0.08,MCM方法认为(N1,N4)和(N2,N3)的相似度相差0.01,而CFSM方法认为(N1,N4)和(N2,N3)的相似度相差0.09。

5 结论

本文在现有云模型相似度计算方法的基础上,提出了一种新的基于组合模糊贴近度的正态云模型相似度度量方法。CFSM方法改进了现有的云模型期望曲线,修正期望曲线综合利用了云的三个数字特征,能更好地描述正态云的“骨架”,从模糊数学的角度利用组合模糊贴近度对正态云相似度算法进行了分析和描述。实例验证表明,该方法在计算正态云模型相似度方面是有效和可行的,在一定程度上能够克服现有方法的不足。云模型是一种具有定性表示数据能力的模型,如何运用云模型相似度计算方法定性分析数据之间的关系仍然是今后不确定数据挖掘研究的一个方向。

摘要：提出一种新的计算正态云模型相似度方法——基于组合模糊贴近度的正态云相似度方法,该方法利用两种模糊贴近度,并通过计算修正的正态云期望曲线的模糊贴近度度量云模型的相似度。实例表明,与现有方法相比本文方法计算简单,能够更有效的对正态云模型相似度进行度量。

关键词：正态云模型,相似性度量,期望曲线,模糊贴近度

参考文献

[1]李德毅等.不确定性人工智能[M].北京:国防工业出版社,2005.

[2]李德毅等.隶属云和隶属云发生器[J].计算机研究与发展,1995,32(6):15~20.

[3]付斌等.云模型研究的回顾与展望[J].计算机应用研究,2011,28(2):420~426.

[4]叶琼等.云模型及应用综述[J].计算机工程与设计,2011,32(12):4198~4201.

[5]李海林等.正态云模型相似度计算方法[J].电子学报,2011,39(11):2561~2567.

[6]张勇等.相似云及其度量分析方法[J].信息与控制,2004,33(2):129~132.

[7]张光卫等.基于云模型协同过滤推荐算法[J].软件学报,2007,18(10):2403~2411.

[8]刘常昱等.正态云模型的统计分析[J].信息与控制,2005,34(2):236~248.

[9]李德毅等.论正态云模型的普适性[J].中国工程科学,2004,6(8):28~34.

[10]汪培庄.模糊集理论及其应用[M].上海:上海科技出版社,1982.

模块化软件的软件凝聚度度量 篇3

1 软件系统的网络观

从结构上看，任何网络都可以概括成结点和边的集合，不管是构造出的规则网络，随机网络，还是复杂网络。因此，软件系统可以表示为一个二元组G(类/函数集，关系集)，模型所反映的层次结构可以用有向非循环的关系依赖图表示。图中每个结点代表一个元素，每条有向弧表示元素间的层次关系，如is-a,has a,part a关系等。当元素和关系数量不断增加时，软件系统则呈现出复杂的网络结构，即扩张性及不断演化的特性。

在工程领域中，软件系统往往表现出无标度网络的特性。如软件内聚程度过高时，若某一个类内部出现异常，在最坏的情况下，会影响到很多与之相关的其它类。这恰恰与无标度网络特有的无标度性和脆弱性所对应;“在当前版本中出错的模块在下一版本中仍可能存在其它错误”[1]这一经验说明易出故障的模块在系统中的比重虽然很小，但是它可能蕴含很多关联错误.这正是对幂律度分布特性——“大量结点有少数连线，少数结点有大量连线”的例证。近年来，已经有人经实验仿真验证软件系统是一个具有幂律分布的无标度网络[2]。

2 模块化软件系统凝聚度

模块化软件系统与汇编语言软件系统相比较而言，有很好可读性和结构性。依据复杂网络理论将模块化软件系统软件系统抽象为一个二元组G(类/函数集，关系集)，其中关系集是类/函数集之间的依赖关系。具体地说，包含以下依赖关系：

2.1 类/函数调用中的参数传递依赖

类/函数参数传递依赖在本质上是由调用类/函数(过程)和被调用类/函数(过程)在调用发生时进行通信而引起的。基本的参数传递依赖有两种：值传递依赖和引用传递依赖。在引用传递过程中，被调类/函数对形参的任何操作都被处理成间接寻址，即通过堆栈中存放的地址访问主调类/函数中的实参变量。所以，被调类/函数对形参做的任何操作都影响了主调类/函数中的实参变量，主调类/函数与被调类/函数之间的依赖关系是双向的。另外对于调用关系的依赖又有三种特殊情况：1)被调用类/函数并没有实际使用传入的参数;2)被调类/函数的返回值没有得到调用者的使用;3)指针类型的参数并没有起到双向传递数据的作用，被调用类/函数中虽然包括对指针的定义性操作，但操作的结果并没有返回调用者。

2.2 各类/函数通过共享全局变量形成的全局数据依赖

使用全局变量的优点是：可以减少变量的个数，减少由于实际参数和形式参数的数据传递带来的时间消耗。但是，使用全局变量也有众多缺点，最重要的是全局变量破坏了类/函数的封装性能。类/函数中若使用了全局变量，那么类/函数体内的语句就可以绕过类/函数参数和返回值进行存取，这种情况破坏了类/函数的独立性，使类/函数对全局变量产生严重的依赖关系。同时，也降低了该类/函数的可移植性。而且，全局变量使类/函数的代码可读性降低。因为多个类/函数都可能使用全局变量，类/函数执行时全局变量的值可能随时发生变化，对于程序的查错和调试都极其不利。从复杂网络的角度来说，全局变量是个具有很大度的关键结点，关联结点很多，这种结点一旦被破坏，整个网络的抗毁性则遭受到严重打击。

根据这些特点，本文建立模块化软件系统模型：

定义模块化软件系统的关系依赖图：一个模块化软件系统的关系依赖图G定义为G(V,W)。其中，V是结点集，W是带权的有向边集。

结点集：结点集V={V1,V2,V3，…，Vi，…，Vn}，其中0

带权有向边集：带权有向边集W={W11,W12,W13，…，Wij，…，Wnn}，其中0

调用关系：在关系依赖图G中，满足以下条件之一者，称为存在调用关系：

1)标注为结点Vi的类/函数与标注为结点Vj的被调用类/函数之间存在参数传递且被调用类/函数实际使用了传入的参数。特殊地，标注为结点Vi的类/函数与标注为结点Vj的被调用类/函数之间存在引用传递依赖且引用传递的值在标注为结点Vj的被调用类/函数中得到改变，则称存在调用关系。

2)标注为结点Vi的类/函数修改全局变量，且被标注为结点Vj的类/函数读取了同一全局变量。

软件凝聚度：

为模块化软件系统G的凝聚度。其中，n代表软件系统G的结点个数，且n≥1;l代表软件系统G中，每两结点之间的平均路径长度;dij代表结点i和结点j之间的最短距离。当结点i和结点j之间没有路径可达时，dij=∞。当n=1时，软件凝聚度为0，即只有一个结点时，不存在与其它结点的交互。

具体算法如下：

1)找到结点Vi的调用关系。若Vj第一次被调用，则为Vj建立一个新结点。并在Vi结点与Vj结点之间连一条有向边，且设Wij=1;若Vj不是第一次被调用，则在Vj与Vi的连线上赋新权Wij=Wij+1。

2)重复步骤1，直到包含所有模块或函数。

3)将步骤1和2所处理的图记作关系依赖图G(V,W)。

4)对关系依赖图G(V,W)分别求取每个结点到其它结点的最短路径。

5)根据公式计算软件凝聚度。

3 实例分析

本文对程序设计语言JAVA的类库进行分析。其中，JAVA选用的是SUN公司的JDK。对应用程序员来说，最常用的是开发桌面应用程序。因此，本文以JAVA中对话框框架的源码作为研究对象，分别建立各自的结点集V和边权集W。其中，V代表框架中出现的类，W说明框架中存在调用关系，调用关系分以下三种，如表1。

我们用复杂网络分析软件Netdraw画出的网络图如图1所示。

在软件凝聚度度量的各种参数中，使用最广泛是MOOD度量的耦合因子CF(Coupling Factor)。所以我们选取耦合因子CF，并与软件凝聚度比较。比较结果如表2所示。

表2通过对耦合因子CF和软件凝聚度比较，我们发现凝聚度高的软件其耦合度低。所以，我们建议使用JDK开发软件。从理论的角度讲JAVA是基于面向对象的语言，模块在抽象性和封装性上都强于传统的面向过程语言。从业界的角度进行统计也是如此，JDK开发的软件无论在开发还是维护阶段，都比传统的面向过程语言开发和维护要容易。这与我们计算所得到的结论是相似的，凝聚度高的软件其耦合度低。

4 结束语

研究软件凝聚度的度量方法，对“计算型”软件工程有重要意义。借鉴复杂网络思想的软件模型更容易考察软件系统的整体性质，且能动态的反映出这些性质，这为我们掌握软件系统的规律提供无可比拟的优势。但是目前基于复杂网络研究在建模、分析、验证，以及探索合理的内外属性度量对应关系等方面才刚开始，我们软件凝聚度的研究工作也处于探索阶段，软件凝聚度能不能找到一个阈值去度量大多数软件质量，有待于大家的继续研究与探讨。

参考文献

[1]Musa J D.Software Reliability Engineering[M].北京:机械工业出版社,2003:60-151,355-434.

[2]Albert R,Jeong H,Bambasi A L.Error and attack tolerance of complex net-works[J].Nature406,2000:378-382.

[3]韩明畅,李德毅,刘常昱,等.软件中的网络化特征及其对软件质量的贡献[J].计算机工程与应用,2006(20):9.

相似度度量 篇4

最大最小关联度图聚类方法将最大最小距离聚类方法的基本思想与连接度矩阵相结合, 给出了图中结点连接度和图的连接度矩阵的定义及计算方法。这种度量标准对大多数图都有良好的适应性, 但是, 存在这样的少数情况, 如果图中两个邻接结点的度都非常大, 而它们连接相同结点的数目极少, 按照邻接结点的相似性定义, 这两个结点的关联度很大, 但实际上这两个结点的相似性并不高, 应归为不同的类。为此, 本文采用相异度矩阵来描述图的特性, 解决此类问题。

1 相异度定义

两个对象之间的相异度是这两个对象差异程度的数值度量。对象越相似, 它们的相异度就越低。通常, 术语距离用作相异度的同义词, 常常用来表示特定类型的相异度[1]。

定义图G的邻接矩阵为A (G) , 简记为A, n=|V|表示图中结点的总数。图中相邻结点间相似性与结点周围的结点有关, 也就是说两个结点连接相同结点的数目越多, 关联度就越高, 那么这两个结点就越相似;反之, 这两个结点的相异度就大。因此可以用相异度矩阵来描述图的特性[1]。

如果将图中每个结点用其邻接矩阵中对应的行 (或者列) 向量来表示, 即:

vi= (ai1, ai2, …, ain) i=1, 2, …, n (1)

那么每个结点就是一个n维的数据对象, 因此可以采用著名的曼哈坦距离作为结点的相异度测量, 则有:

s (vi, vj) =|ai1-aj1|+|ai2-aj2|+…+|ain-ajn| (2)

满足如下性质[2]:

(1) 非负性

(a) 对于所有的i和j, s (vi, vj) ≥0;

(b) 仅当i=j时, s (vi, vj) =0。

(2) 对称性

对于所有i和j, s (vi, vj) =s (vj, vi) 。

(3) 三角不等式

对于所有i, j和k, s (vi, vk) ≤s (vi, vj) +s (vj, vk) 。

在层次聚类方法中要做边的移除或添加, 因此只需计算相邻结点的相异度, 非相邻结点的相异度可以置为无穷大。根据图的邻接矩阵, 通过式 (2) , 可以构造图G= (V, E) 的相异度矩阵S|V|×|V|。由于s (vi, vj) =s (vj, vi) , 因此S是一个对称阵。如上所述, 鉴于s (vi, vi) =0 (i=1, 2, …, |V}) 是无定义的, 为节省存储空间, 置矩阵S主对角线上元素的值为相应结点的度, 因而有:

该相异度矩阵是本文图聚类算法的数据基础[3]。

2 聚类算法描述

本文采用凝聚聚类思想进行聚类, 要做聚类的合并, 因此给出类间距离的定义。

类间距离定义可以有多种方法, 本算法将两个聚类之间的距离定义为两个类之间所有的结点对间距离的最小值, 表示为:

d (ωi, ωj) =min{s (vl, vk) |vl∈ωi, vk∈ωj} (4)

假定图G= (V, E) 的相异度矩阵S由式 (3) 求得。算法分为两部分:第一部分是聚类初始化过程, 即初始时, 将每个结点定义为一类, 对于n个结点的图, 共有n个初始聚类;第二部分是多次凝聚过程, 每次在当前聚类层次下, 将具有最小距离的类合并, 重复执行此步, 直到所有的结点都聚成一类[3]。则算法的执行步骤如下:

步骤1 聚类初始化过程

初始化图为n个聚类, 即每一个结点就是一个独立聚类。初始聚类为:

ω={ω1, ω2, …, ωn}

其中, $\omega {}_i=\{v{}_i|i=1,2,\cdots ,n$且vi∈V (G) }。

步骤2 凝聚聚类过程

(1) 在同一层次上, 根据式 (4) 计算d (ωi, ωj) =min{s (vl, vk) |vl∈ωi, vk∈ωj}, 求出距离最小的两个类进行合并, 若min{d (ωi, ωj) }=d (ωg, ωt) , 则合并ωg和ωt, 产生新层次上的聚类ωgt=ωg∪ωt;

(2) 重复执行步骤2, 直到所有的类都合并为一个类。

3 算法例证

给定无向非加权图G= (V, E) , 其中V={v1, v2, v3, …, v7}, 即图G由7个结点, 8条边构成[3]。如图1所示。

首先计算各结点的度, 得:deg (v1) =3, deg (v2) =4, deg (v3) =1, deg (v4) =2, deg (v5) =2, deg (v6) =2, deg (v7) =2。再求图G= (V, E) 的邻接矩阵A, 最后根据式 (3) 求得相异度矩阵S。由于A, S是对称阵, 故本文只列出上三角和主对角线上的元素。

$A=\left(\begin{array}{ccccccc}0& 1& 0& 0& 0& 1& 1\\ & 0& 1& 1& 1& 0& 0\\ & & 0& 0& 0& 0& 0\\ & & & 0& 1& 0& 0\\ & & & & 0& 0& 0\\ & & & & & 0& 1\\ & & & & & & 0\end{array}\right)$

$S=\left(\begin{array}{ccccccc}3& 7& \infty & \infty & \infty & 3& 3\\ & 4& 5& 4& 4& \infty & \infty \\ & & 1& \infty & \infty & \infty & \infty \\ & & & 2& 2& \infty & \infty \\ & & & & 2& \infty & \infty \\ & & & & & 2& 2\\ & & & & & & 2\end{array}\right)$

基于该S矩阵, 应用上述聚类算法, 首先可求得初始聚类ω1={v1}, ω2={v2}, ω3={v3}, ω4={v4}, ω5={v5}, ω6={v6}, ω7={v7};在此基础上, 进行多遍凝聚聚类, 直到所有的类都合并为一类, 采用树状图表示聚类过程及聚类结果, 如图2所示。

4 分析比较

针对本文中给出的图, 如果聚类数为k=2, 按照相似度度量及其算法, 得到的聚类结果为:ω1={v2, v1, v3, v4, v5}, ω2={v6, v7};按照本文的聚类算法, 则所有的结点分为两个簇, 即ω1={v2, v3, v4, v5}, ω2={v6, v7, v1}, 结点v1划分到不同的类中。直观地看, 第二种结果更合理一些。因此, 图的结构也是影响聚类效果的一个重要因素, 需要针对不同类图的特点, 找到相应的快速而且可靠的分析算法。

5 聚类结果评测

采用Newman等人提出的衡量网络划分质量的标准——模块性 (Modularity) 来评测聚类结果。它是基于同类匹配 (Associative Mixing) 来定义的。考虑某种划分形式, 它将图划分为k个子图。定义一个k×k 维的对称矩阵[4]:

e= (eij) (5)

其中元素eij表示图中连接两个不同子图的结点的边在所有边中所占的比例;这两个结点分别位于第i个子图和第j个子图。注意, 在这里所说的所有的边是在原始图中的, 因此, 该模块性的衡量标准是利用完整的图来计算的。

设矩阵中对角线上各元素之和为${\rm T}re={\displaystyle \sum _{i}e}{}_{ii}$。它给出了图中连接某一个子图内部各结点的边在所有边的数目中所占比例。定义每行 (或者列) 中各元素之和为:

ai=∑eij (6)

它表示与第i个子图中的结点相连的边在所有边中所占的比例。在此基础上, 用下式来定义模块性的衡量标准[4]:

$Q={\displaystyle \sum _i(}e{}_{ii}-a{}_i{}^2)={\rm T}re-\parallel e{}^2\parallel$ (7)

其中‖x‖表示矩阵x中所有的元素之和。上式的物理意义是:图中连接两个属同一聚类的结点的边 (即子图内部边) 的比例减去在同样的社团结构下任意连接这两个节点的边的比例的期望值。如果子图内部边的比例不大于任意连接时的期望值, 则有Q=0。Q的上限为Q=1, 而Q越接近这个值, 就说明子图结构越明显。该值通常位于0.3～0.7之间。

下面结合树状图来介绍模块性标准的典型应用 (见图3) 。当沿着树状图逐步下移时, 每移一步, 就对该截取位置对应的子图结构计算其Q值, 并找到它的局部峰值。该峰值即对应着比较好的截取位置。通常, 这样的局部峰值仅有一到两个。对一些社团结构已知的网络用该标准进行分析, Newman等人发现这些峰值的位置与所期望的划分位置密切相关, 而峰值的高度即可作为该社团划分方法的强度判断标准。

采用凝聚的层次聚类方法, 聚类过程及聚类结果用树状图表示, 如图3所示。

根据式 (5) 和式 (7) 计算出:

当k=2时, , 则Q=0.295;

当k=3时, , 则Q=0.317;

当k=4时, , 则Q=0.181。

可见, 当k=3时Q值最大, 聚类效果是满意的、有效的。

6 结论与展望

图聚类问题已经成为当今一个非常具有挑战性和前景性的研究领域。本文主要从时间复杂度和相似性度量方面作了一些改进, 提出了基于相异度度量的凝聚聚类方法, 采用曼哈坦距离作为结点相似性度量, 其计算量极小, 实验表明这两种聚类方法都能达到令人满意的效果。

时间复杂度和结果有效性仍然是大规模图聚类分析算法面临的两个主要问题。目前, 在事先不知道子图数目的情况下, 最快的算法时间复杂度大约为O (nlog2n) 。该算法可以帮助分析大型网络的社团结构, 但是却无法保证得到正确合理的社团结构。而其它可能可以得到更好结果的算法的时间复杂度都比较大, 难以应用于超大规模图的分析。因此, 如何针对不同类图的特点, 找到快速而且可靠的子图结构的分析算法, 仍然是今后需要解决的主要问题。

参考文献

[1]Inderjit S Dhillon, Yuqiang Guan, Brian Kulis.Kernel k-means, Spec-tral Clustering and Normalized Cuts[C]//KDD’04, August 22-25, 2004, Seattle, Washinton, USA.

[2]解, 汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学, 2005, 2 (3) .

[3]Xiaodi Huang, Peter Eades, Wei lai.A framework of Filtering, Clus-tering and Dynamic Layout Graphs for visualization[C]//AustralianComputer Society, 28thAustralian Computer Science Conference, 2005.