代码相似度分析（共5篇）
代码相似度分析 篇1
1研究背景和意义
在现代的计算机专业的教学中, 实践占据着越来越重要的作用。编码题目在计算机专业日常作业和考试中占据着越来越多的比重, 但是这也加重了老师的负担。而代码相似度分析会对老师在判题的过程中提供一个重要的参考。本课题研究主要通过对代码的处理以及一些算法, 来实现一个完整的代码相似度分析的一种方法。
1990年, Komondoor和Horwitz提出的使用程序切片技术进行检测。通过构造出程序依赖图PDG (Program Dependence Graph) , 然后是用文本比较方法, 找到相似重复的子句。1992年, B.S.Baker通过将源代码的函数名称、变量、常量、类型等各种标识符 (identifier) 转换为参数化特征 (Parameterized Symbols) 而提出了基于Parameterized Matching的重复代码检测工具DUP, 用于实现同一文件的比较。1994年, Alex Aiken在Berkeley开发了MOSS (Measure of Software Similarity) , 用来识别C, C++, Java, Pascal, Ada, ML, Lisp或Scheme等编制的源程序的相似度。1998年, D.Baxer等提出了基于抽象语法数 (Abstract Syntax Tree) 的重复代码检测技术。这种检测技术针对C语言程序进行语法解析, 建立起完整的语法树, 随后应用三种算法进行重复代码检测。
2过程与方法
2.1预处理
由于源程序中有很多会影响结果的字符串, 比如输入输出函数, printf (“abcd”) ;和printf (“njdms”) ;对源程序来说是变动性很大的因素, 注释, 空格等添加修改对源程序的逻辑没有任何影响, 为了排除这些冗余的字符串, 所以在匹配之前要去除这些字符串, 预处理的程度对结果的影响是重要因素之一。
预处理的步骤如下:
(1) 对输入的源程序进行冗余预处理, 即为了保证检测准确度, 去除代码中的注释、输入输出语句如scanf等。
(2) 对代码进行分词处理, 主要的处理就是将i+1类似形式的单词串用空格分隔为i+1, 以减小误匹配。
(3) 将字符串转换为单词串, 由于要考虑到程序的结构问题, 单独的对字符串进行相似性的匹配, 由于缺少程序结构, 所以效果差强人意。如果可以对有语。言意义的单词进行语句式匹配, 则可以增加其准确度。
2.2相似性检测
2.2.1最长公共子序列 (Longest Common Subsequence, LCS)
LCS算法是将两个给定字符串分别删去零个或者多个字符, 但不改变剩余字符的顺序后得到的长度最长的相同字符序列。采用自上而下的地推法来计算公共子串的长度, 算法的运行步骤如下:
矩阵matrix中的最大值就是最长公共子串的长度, 用LCS来表示。
2.2.2贪婪串匹配算法 (Greedy String Tiling, GST)
(1) GST算法是一种贪婪的算法, 最早被澳大利亚悉尼大学的Michael Wise设计。在给出GST伪代码之前需要先明确两个基本的概念。
(2) 最大匹配 (Maximal-Match) 是指在匹配过程中, 模式串中从i处开始的子串Pi与文本串中从j处开始的子串Ti的最长可能匹配。
最小匹配长度 (Minimun-Match-Length, MML) 用来设定匹配所允许的最小长度, 所有小于该长度的匹配将被忽略, 其值可以为1, 但是一般取大于1的整数。
(3) 字符串T与P的相似度使用式 (2) 计算。
(4) GST最坏情况下的时间复杂度是O (n3) , 最好情况下的时间复杂度是O (n2) , 能够解决两个字符串中改变序列的查找。目前应用较广, 但因该算法采用了两个字符串逐字符比较的方法, 所以算法的时间复杂度较大。
(5) 我们同样使用了LCS算法处理代码的方式, 将字符串分为带有语言意义的单个词组, 对词组进行相似性的匹配, 这样可以较多的将代码结构计算在内, 实现较准确的匹配。
3结论
本文主要使用了LCS和GST这两种对字符串匹配的常用算法, 研究了代码结构化编程的特点, 在源程序代码物理属性特征和结构属性特征的基础上, 研究了加权的相似代码属性识别方法, 通过总结这些方法, 我们总结出了通过类似于词法匹配的方法, 把源代码转换为一个单词序列, 然后对单词序列进行匹配, 这样充分考虑到编程语言的结构化的特性。通过结合对代码的预处理以及LCS和GST两种算法, 使得逐字拷贝、更改注释语句、更改空白区域、重新命名变量名、改变代码块的顺序、简单数据类型更改等更改方式几乎不会对结果造成影响, 大大提高了分析结果的准确性。
参考文献
[1]M H Halstead.Elements of software science[J].ELSEVIER SCIENCE, 1977.
[2]于海英.程序代码相似度度量的研究与实现[J].计算机工程, 2010, 36 (4) :45-46.DOI:10.3969/j.issn.1000-3428.2010.04.016.
代码相似度分析 篇2
恶意程序代码相似度度量是通过一定的程序检测方法度量恶意程序代码的相似度程序,它主要用在核查软件剽窃[1]、知识产权保护[2]等方面。恶意程序代码相似度度量的难点在于恶意程序代码的灵活性,但是恶意程序代码无论如何改变,其代码间内涵的属性及结构没有发生本质变化。现有的恶意程序代码相似度度量主要有属性计算和结构度量两类[3],其中属性计算主要是从通过提取恶意程序代码的软件度量特征,计算每个程序的软件度量指标,以其构造成空间向量,最后利用空间向量的夹角余弦公式来计算恶意程序代码的相似度。结构度量主要是利用对程序内部的结构进行对比分析来判断恶意程序代码的相似性。结构度量通常包括点阵图[4]等。从现有的恶意程序代码检测系统来看,恶意程序代码相似度度量的方法各有优缺点。属性计算对恶意程序代码的结构信息保留较少,其计算性能较低;而结构度量采取了字符串匹配来计算恶意程序代码标准化后产生的Token序列的相似度,其时间的复杂度较高。文献[5]提出了Token序列字串的指纹集合提取方法。若某字串的散列值与固定尺寸模板的模为0,则将其选择为一个指纹,并提出了其基于指纹的恶意程序代码相似度度量计算公式。文献[6]提出了属性计算和结构度量相结合的恶意程序代码相似度度量算法,但是其属性计算以向量点积的方式进行计算,损失了较多的结构信息;而且其未对属性计算和结构计算的相似度进行加权对比。基于此,本文提出了基于作用域的改进指纹和LSC加权恶意程序代码相似度估计算法,通过对作用域范围内的标准化Token序列进行指纹提取,改进其恶意程序代码的相似度计算方法,并结合恶意程序代码的结构度量,对其恶意程序代码的相似度进行加权,实验仿真证明该算法具有较好的相似度精度和执行效率。
1恶意程序代码预处理
在对恶意程序代码进行预处理时,以C语言程序为例。考虑到C语言的程序结构自身特征,将标识符进行重新定义、更改代码程序块执行次序和改变代码程序块中语句的执行顺序等控制手段来对原有程序结构进行改变;并利用以下步骤进行基于C语言结构的恶意程序代码相似度度量。这种度量方法可使程序相似度在度量过程中有较高的精度,同时执行效率较高。
1.1函数作用域划分
函数作用域划分主要是为了细化恶意程序代码的粒度,为恶意程序代码间的相似度计算提供可靠的支持。对于一个特定的C语言程序,其边界以大括号为作用域标识,因此在对其程序进行结构划分时,主要是分为定义变量和初始化变量过程,控制语句过程,程序执行结果三个部分。依据C语言程序结构的特点,对恶意程序代码进行作用域划分时,从外层嵌套的边界开始,以数据栈为存储结构,利用其先进后出的特征,对边界函数的作用域进行划分。
1.2恶意程序代码标准化处理
为了对更改过的恶意程序代码进行检测,并求得在相同函数作用域范围内的标记串(Token)[7]的散列值,其作用去除划分作用域后的代码中在进行恶意程序代码相似度计算时的无效片段,进一步提高恶意程序代码相似度度量的精度和执行效率。
恶意程序代码标准化处理有三大原则,即首先删除恶意程序代码中的关键字、标识符及库函数等。如删除关键字void、库函数名min等。其次要将恶意程序代码中所有不是关键字、标识符及库函数操作符的恶意程序代码用#替换。最后删除程序中的注释语句和空格。
例如有程序1:
int min (float x ,float y)
{ int z;
z=x>y?x:y
return (z);
}
对其恶意程序代码进行标准化,首先删除库函数min、关键字int及空格和注释语句等,然后利用#替换生成Token序列:
(#,#){#;#=#>#?#:#;(#);}
取K值为6时,对其生成Token子串:(#,#){,#,#){#,,#}{#;,…,#;(#);,;(#);}
将通过该方法获得的字串长度成为Token的串长度-(K-1)。其中K是噪声阈值,是算法不能检测出长度小于K的串匹配。因此在恶意程序代码检测时,可设置一个阈值T,当长度不小于T的公共字串时,才能称为是一个串匹配,即将T作为用户检测恶意程序代码相似度的粒度阈值。
1.3字串散列
在函数作用域范围内,通过作用域划分和恶意程序代码的标准化处理,可将恶意程序代码的Token序列映射到比其更短的Hash值,且Hash映射函数必须尽可能地保证不同的字符串能够产生相同的指纹,其目的是为提取指纹集合提供更好的相似度支持,提高其程序相似度度量的度量效果。参考文献[8]中算法的思想,Hash函数如下:
其中asc[ci]是字符ci的ASCII编码,q是一个满足计算的足够大的素数。
通过该式可利用第i个字串的散列值Hash快速地计算出第i+1个字串的Hash值:
2改进指纹和LSC加权的恶意代码相似度估计
在进行恶意程序代码相似度度量时,首先将在一个函数作用域内的恶意程序代码进行标准化处理;然后生成Token序列,并将其子序列集合当作整个串的特征值,称为指纹。指纹的提取算法参考文献[9],则恶意程序代码(A,B)的相似度度量为:
其中(|A|,|B|)为恶意程序代码(A,B)的指纹数,|A∩B|是其代码(A,B)中共有的指纹数。
由文献[10]的研究可知,设恶意程序代码A可划分L个函数作用域,恶意程序代码B可划分F个作用域,则A={A1,A2,...,AL},B={B1,B2,...,BF}。设恶意程序代码A为源恶意程序代码,恶意程序代码B是对比恶意程序代码,则其相似度度量如下:
其中Ai是恶意程序代码A的第i个函数作用域的指纹数,Bj是恶意程序代码B的第j个函数作用域的指纹数,
由于在对源恶意程序代码A进行恶意程序代码B更改时,是基于C语言结构特征的随机序列更改,不能保证函数作用域都被更改。若将字符串看作是若干个字串的组成,则(A,B)中始终会存在k个最长公共字串,且其k的取值与用户检测恶意程序代码相似度的粒度阈值T相关。
在对恶意程序代码(A,B)的相似度利用最长公共字串在整个串中的比重进行度量时,采取文献[11]的算法,来对基于C语言结构预处理的恶意程序代码(A,B)寻找其最大的公共字串,则其相似度sim(A,B)'为:
其中MatchLen=∑match(i,j,length)∈Tileslength;match (i,j,length)为在恶意程序代码A中起始位为i,在恶意程序代码B中起始位为j,长度序列为length的公共字串;Tiles为公共字串集合。该算法基于C语言结构特点进行恶意程序代码预处理,然后循环遍历标记串中未被匹配的所有字串长度大于指定最小匹配长度的最大公共字串,因此其效率要优于LSC算法[12]。
故,若∃A,∀B,(A,B)为恶意程序代码,B为对源程序A经过C语言结构特征更改的恶意程序代码,且恶意程序代码(A,B)中仍存在最大的公共字串,则恶意程序代码(A,B)的相似度为:
其中α是调节因子,是对两种相似度计算方法的加权。
相似度Sim(A,B)的大小反映了恶意程序代码(A,B)相似程序的多少,其阈值是对程序的相似性进行识别的定量分析。对于较大的阈值,其相似性的程序较少;若阈值设置偏小,则会有更多的程序与之相似。因此,恶意程序代码的相似度阈值必须选择得当。
3实验仿真
实验测试时,以折半查找算法prog.c为源程序,并依据文献[13]的提出的修改源恶意程序代码的方法对prog.c源恶意程序代码进行多次修改,从而得到不同更改程度的测试样本集合。设K是生成Token字串序列的最小颗粒度,w为文献[9]算法的指纹提取窗口尺度,令K=5、w=4时,经测试,实验的度量效果最好。
在进行实验时,选取文献[12]的LSC算法和文献[14]来进行对比验证本文算法的度量效果及执行效率。样本分组时将不同更改程度的源程序作为一组,通过5次更改,形成5组样本,并对每一种样本与源程序prog.c进行相似度计算,求其平均值,计算出三种方法度量恶意程序代码相似度平均值的差,具体如图1所示:
通过实验可以看出,文献[14]对经过文献[13]中提到的恶意程序代码修改方案中的{4,5,6,7,10}这5组样本的相似度计算相对于文献[12]而言效果较好,而本文算法对其中的{4,5,6,7,9,10}这6组样本的相似度计算相对于文献[12]效果较好。这主要是由于本文对恶意程序代码相似度度量采取基于指纹数和最大公共字串方法的相似度加权,更易检测出相似程序。
对本文算法与文献[12]和文献[14]的算法在恶意程序代码相似度度量的时间开销上进行对比,统计其与执行源代码程序prog.c的执行时间相对比的平均值,文献[12]的平均执行时间为253ms,文献[14]的执行时间为81ms,本文算法的执行时间为92ms。可以看出,本文算法的执行时间介于文献[12]和文献[14]的算法执行时间之间,尽管其执行时间并不是最优的,这是由于其在进行相似度计算时,采取指纹总数和最大公共字串匹配相结合的相似度度量方法,其计算的恶意程序代码相似度精度要高。因此,从恶意程序代码相似度精度和执行效率两个角度来看,本文的算法具有较好的执行效果。
4结语
通过对恶意程序代码相似度度量方法进行研究,提出了基于C语言结构特征的恶意程序代码相似度度量方法,以指纹提取和最大公共字串的匹配为思路,对恶意程序代码的相似度进行加权求和,使得恶意程序代码相似度的计算更加精确。下一步的研究重点是对于提取Token自序列时阈值的设置和恶意程序代码相似度加权因子的实验统计,并尽可能地优化C语言程序,使得算法的执行效率更优。
摘要：恶意程序代码的相似度估计是恶意程序代码分析和检测的重要研究内容。现有的方法主要是对恶意程序代码进行属性计算或结构度量,但由于恶意程序代码结构的灵活性和恶意程序代码的伪装、恶意程序代码的相似度较难度量。提出了改进指纹和LSC加权的恶意程序代码相似度估计算法。该算法首先对恶意程序代码进行函数作用域划分和标准化预处理,然后对其进行字串序列化,利用改进的指纹相似度来对恶意程序代码的相似度进行度量;同时结合最大公共字串匹配算法进行结构度量,并对其相似度计算结果进行加权,对恶意程序代码结构的相似度进行综合估计。实验以C语言结构的程序代码为例,利用折半查找算法生成恶意程序代码测试数据集进行算法有效性验证。仿真证明该算法具有较好的恶意程序代码相似度估算精度。
判断相似度快速分析油井示功图 篇3
本文是通过对各种异常情况的示功图来对比得到现在机采井的工作情况。先收集各种异常情况的示功图并将示功图数字化, 把将要判断的示功图数字化后与已知的示功图做对比, 取得相似度最高的图, 得出现在示功图抽油泵的工作情况。
1 各种异常情况的示功图
以下是各类情况的抽油泵工作的示功图。
图1是最理想的地面示功图 (无气, 多水, 供液充足的正常示功图) 充满系数100%, 特征为平行。
图2为油井供液不足时的地面示功图。特征为上、下平行, 左右平行, 图右下下角缺失, 增载正常, 卸载慢。
图3为油稠时的地面示功图。特征为上、下行曲线成凸状。由于上、下冲程的形成中间速度较快, 阻力增大所致。
图4是油井出砂的地面示功图柱塞受油井出砂影响, 容易卡泵时的示功图。特征为上、下曲线没有明显的阻尼状, 而是呈小牙齿的不规则, 不重复的示功图。
图5油井气体影响的地面示功图。是高油气比井特征, 油气比越高, 圆弧的曲率半径越大, 图右侧呈圆弧状。
图6是油井气锁的地面示功图。属于气体影响的特殊现象, 图形成扁长状, 上、下从图中间平行, 左右不规则, 且左侧向下。
图7是固定阀漏失的地面示功图, 其特征是示功图左下方呈圆形缺失 (无气体影响时右下角也呈圆形) 类似一个碗状。
图8是游动阀漏失的地面示功图, 特征为曲线左上部分有圆形缺失, 有时右上角也呈圆形缺失。若是游动阀或阀座被严重刺坏, 上部曲线则呈圆形形状。
图9是双阀漏失的地面示功图, 特征为上行曲线呈凸状, 下行曲线呈凹状, 油井不出油, 需要检泵。
2 感知哈希算法和余弦定理
2.1 原理
感知哈希算法, 它的作用是对每张图片生成一个“指纹”字符串, 然后比较不同图片的指纹。结果越接近, 就说明图片越相似。
感知哈希算法算法的简单实现:
第一步, 缩小尺寸。将图片缩小到8×8的尺寸, 总共64个像素。这一步的作用是去除图片的细节, 只保留结构、明暗等基本信息, 摒弃不同尺寸、比例带来的图片差异。
第二步, 简化色彩。将缩小后的图片, 转为64级灰度。也就是说, 所有像素点总共只有64种颜色。
第三步, 计算平均值。计算所有64个像素的灰度平均值。
第四步, 比较像素的灰度。将每个像素的灰度, 与平均值进行比较。大于或等于平均值, 记为1;小于平均值, 记为0。
第五步, 计算哈希值。将上一步的比较结果, 组合在一起, 就构成了一个64位的整数, 这就是这张图片的指纹。组合的次序并不重要, 只要保证所有图片都采用同样次序就行了。
余弦定理描述了三角形中任何一个夹角和三个边的关系, 换句话说, 给定三角形的三条边, 我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为a, b和c, 对应的三个角为A, B和C, 那么角A的余弦
如果我们将三角形的两边b和c看成是两个向量, 那么上述公式等价于
其中分母表示两个向量b和c的长度, 分子表示两个向量的内积。
2.2 利用余弦定理判断相似度
余弦定理判断图片的相似度, 似乎没有什么联系, 但是在向量代数里, 向量实际上是多维空间中有方向的线段。如果两个向量的方向一致, 即夹角接近零, 那么这两个向量就相近。而要确定两个向量方向是否一致, 这就要用到余弦定理计算向量的夹角了。以此来判断两个向量是否相近。
但是图片怎么进行向量化, 进行类似于感知哈希算法的压缩, 为了提高图片相似度的度量大小, 将感知哈希算法中压缩8*8的图片, 压缩成32*32的图片, 通过感知哈希算法得到一个1024位的二进制值, 我们将其存成一个数组, 这就是我们每一个示功图的指纹。
假设图片X和图片Y, 所对应的向量分别为:
那么他们的夹角余弦
当夹角的余弦接近于一时, 两个图片越相似;夹角的余弦越小, 两个图片越不相似。
所以可以得出图片的相似度公式
3 判断相似度分析示功图
首先先将需要判定的示功图通过感知哈希算法数字化, 假设需要判定的示功图为Q, 通过感知哈希算法得到1024位的二进制数值存成一个数组, 这个数值就是示功图Q的指纹。
通过和已知的示功图的值做对比, 得到示功图Q与所有图片的相似度nx大小如列举出的17种情况n1 n2…n17, 将这17种情况得到的数值通过冒泡排序从大到小排列, 排名第一的就是和示功图Q最接近的, 将此示功图预先存在数据库中的状况, 反应到用户终端, 以此自动的判断出, 该抽油泵的工作状况。
4 并入物联网智能化构想
数字化油田, 最终要实现智能化, 节约人力资源成本, 在油田数字化后, 并入物联网后可以将油井上的示功仪的图像实时传回数据中心, 并直接通过相似度对比实时判断油井情况。
参考文献
[1]吴军.数学之美[M].人民邮电出版社, 2012, 5
代码相似度分析 篇4
而物流网中普遍存在物流效率低、成本高、大量的异构系统不能顺畅交换数据等问题。在物流网中,如何准确获取物品信息、如何在异构系统中交换物品信息,已经成为近几年物流网络研究的热点。本文提出一种基于相似度的社区挖掘算法,将物流网的各个节点看作是社交网络(Social Networks)的社区,社区结构可能各不相同,物品是隶属于不同社区的成员(意味着,不同物流节点的信息组成是异构的)。通过社区挖掘寻找各个异构的物流网络中固有的社区结构,从而发现物流网中隐藏的规律并进行路径优化等网络行为。
1 相关工作
对物流中所涉及到的数据,建立一个适用于物流的地理社会网络,通过分析和处理,优化物流流程,提高物流效率。物流的产生和发展的原因在于没有将时间、空间以及人这三者关系结合起来,地理社会网络可以实现时间、地点与人三者关系的叠加处理[8]。因此,将地理社会网络与物流信息平台相结合,关注用户与系统、用户与用户间关系,让用户作为系统的一个节点,有效地参与并发布数据;结合地理社会网络,消除信息之间的孤立等研究具有一定的研究价值和实际意义。
1.1 物流网关系模型
物流关系:一个物流网络可以用一张图来表示,如图1 所示。供应商、客户、物流企业对应图中的节点,每个节点拥有自己的属性,包括身份,公司,车队等;边代表节点之间的关系,包括买卖关系,合作关系等。用一个无向图来表示这样的网络,Nsocial=(P,C,T),P是代表一组供应商用户的节点集合;C代表一组客户用户的节点集合;T代表物流企业,T包含于P×C的笛卡尔乘积中,是无向图中的边的集合。一条边(p1,c2)属于T,表示p1,c2这两个的关系。
对物流网络进一步抽象,用连通的无向图G=(V,E)来表示,节点集V表示物流网络中个体(既可以是供应商也可以是消费者客户)的集合,V={v_1,v_2,…,v_n},边集合E表示网络中供应商或者消费者之间的关系,E={e_1,e_2,…,e_m}。
这样,物流中的每类关系都可以对应出一个子图Gj=(Vj,Ej),j=l,2,…,k,k≥2,Vj表示该子图中供应商的集合;Ej表示子图中供应商之间关系的集合。在图G中,边E上是有标有权重的,供应商之间关系的紧密程度是通过权重来体现的,权值的计算是根据计算供应商之间的标记数目得到的。所以,在构建子图Gj=(Vj,Ej)所对应的关系矩阵Rj时,需要计算边上的权值,同样,通过计算物流网络中供应商之间的标记数,得到个体边上的权重,用如下公式进行计算:
其中{x,y}∈ Vj,表示在物流子图Gj中存在的两个供应商x,y,假设x和y具有3 个相同的标记,则Rjxy为3,是通过这种方式进行计算物流网络中所有边上的权值的。对于关系矩阵Rj,j=1,2,…,k,k≥2,通过除以物流网络中边上的最大权值作归一化处理,使得所有的边上的权重值在范围[0,1]内。因为Rj是一个对称矩阵,所以可以采用一个向量表示它。
1.2 物流网络中的社区
一个社区可以简单地定义成享有一些共同属性的一群对象的集合,这个共同属性就是对象之间的关系。例如,给出一个用户的一组选择P ={p1,p2,⋯,pk} ,构建出相应的关系矩阵RP,关系矩阵RP是一个对称矩阵;然后,找出最能匹配选择关系向量的已有关系的线性组合,根据得到的关系组合,来挖掘符合用户需求的社区。
这些关系矩阵具有如下的属性:
频率:f (xj) = xj/n ,表示社会网络中供应商xj在关系Rj中所对应的标记占关系Rj中的有对象对应的标记的百分比,其中xj表示对象xj在关系Rj中所对应的标记数;n为关系Rj中所有对象对应的标记总和。若xj在关系Rj所对应标记中出现的次数越多,则f (xj) 值越大,表示xj在关系Rj中与其他个体之间的联系越紧密。
重要性:I(xj) = N/xj,表示供应商xj在整个网络中的一个重要参数,式中的N表示整个物流网络中所有物流个体对应的标记总数目,xj表示对象xj在整个网络中对应的标记总数。若xj对应标记在整个网络中出现的次数越多,则I(xj) 的值就越小。
次序值:RV(xj) = f (xj) /I(xj) ,由频率与重要性的定义可知,若对象xj所对应标记总数在社会网络中出现的次数越多,并且在某一关系中出现次数越多,则对象xj的次序值就越大。若以这样的xj作为一组选择实例,则在网络中,次序值越大的关系就更可能符合用户的需求。
综合次序值:整个网络中某关系中的次序值。表示用户选择P={p1,p2,⋯,pk},在整个网络某关系中的次序值。
1.3 基于相似度的社区挖掘算法
进行用户推荐,需要了解客户的购买行为。可以通过大量的订单的信息来了解,因为订单信息一般包含客户的编号、物品名称、数量、时间等信息;然后根据不同用户提取相关数据并调用推荐算法,最后找出1~3 个供应商作为结果展现给用户。
对于两位用户,当他们在物流信息平台上购买物品,选取的物流公司相同,则认为两位用户有一定的相似性;假如两位用户同时都在物流服务平台上购买相同的物品并且选取的物流公司也相同,可以认为这两位用户在选取物流公司的相似度较高;假如两位用户同时都在物流服务平台上购买相同的物品并且选取的物流公司也相同,而且两位用户在同一个区域,认为这两位用户在选取物流公司的相似度更高。
在物流社交网络中,用户每一次下单行为可以称作一个购买兴趣点(Purchase of interest,PI)。PI库中都会记录每一个PI的供应商、物品名称、发货地、送货地、送货方式(物流公司名称),即PI=(P,N,O,D,T)。在物流过程中,经常会涉及到订单,需要对订单进行定义。这样,每一个订单都会有供应商、物品名称、发货地、送货地、物流公司名称,即Order=(Provider Name,Goods⁃Name,Origin,Destination,Logistics Company Name)。n个订单可以看成n × 5 的矩阵:
首先,给出一个连通的无向图G(V,E),|V|=M,代表物流网络中的有M个物流个体,确切地说是M个供应商;E代表个体之间的关系。并对其对应的关系向量R1,R2,⋯,Rn作标准化处理。
其次,物流社会网络中物流个体间存在着各种关系,每种关系都可以映射为一个关系图,因此一个社会网络映射出多个关系图,G1,G2,⋯,Gn,并根据用户的选择信息,由次序值公式:RV(xj) = f (xj)/ I(xj) 计算综合次序值,然后重新排序关系,其中N表示关系的种类数目。
最后,选择次序值高于一定阈值t的关系,在此关系基础上,调用基于回归的多关系抽取算法,求出组合系数:= a1R1′ + a2R2′ + ⋯ + anRn′ ,其中a1,a2,⋯,an为对应关系的组合系数,得到一组关系组合R1′,R2′⋯,Rn′ ,调用K⁃means算法,得到K个聚类,即挖掘出k个社区。
该算法伪代码如下所示:
2 实验及分析
本实验使用4 000 个订单数据集进行实验,把这个数据集看作一个物流网络,供应商视为网络中的对象,供应商使用不同的物流公司配送物品视作一种关系,因为10 个物流公司,则至多有10 种不同关系,那么这个数据集就是一个多关系社会网络。本实验就是在其上研究供应商的内在的关系,对供应商社区进行挖掘。
首先构建关系图,把供应商视为节点,标记数初始值为0,如果有两个供应商使用同一个物流公司配送物品,则他们的标记数加l,否则不变;然后生成关系图,每一个物流公司生成一个关系图,对每个物流公司,将数据相加获得该物流公司的供应商关系图。这种关系图反映了供应商在配送某一类物品时的相似度,相似度越高,说明他们之间的具有共同喜好的可能性越大。一般来说,如果两个供应商在某一图中边的权值较大,就说明他们有着相似或者相同的物品或物流公司,也说明他们的相似度更高。最后,对于每一个关系图,需要进行归一化权值,可以采用他们的权值除以整个网络关系图中的最大权值的方式来处理,权值结果都在区间[0,l]内。本实验选取了配送物品较多的物流公司构建了关系图。所有供应商的综合次序值的计算结果如表1所示。
当选择淘宝、京东、天猫,阈值t为10 时,综合次序值对应的是表1 中的第4,9,10 次序;抽取的关系组合系数分别为:
由上式可以看出,当选择淘宝、京东和天猫这几个供应商和物流公司R1′(顺丰)的关系最密切,换言之,淘宝、京东和天猫与顺丰的业务合作比较多。最终,通过聚类,得到一个社区,该社区如图2 所示。
从图2 中可以看出,这个社区中的供应商有一个共同的特点,那就是他们的客户主要是个人,而不是企业。他们使用的物流公司大都是一些快递公司。因为这些快递公司的费用较低,速度快等特点,淘宝是最典型的例子。进而得到一个供应商和客户的关系,该社区的供应商大多数业务是面向个人用户的。
同样的,当用户选择当当、TCL、索尼,阈值t为10时,综合次序值对应的是表1 中的第1,2,3 次序;抽取的关系组合系数分别为:
由上式可以看出,当选择当当、TCL和索尼这几个供应商和物流公司R1′(顺丰)R2′(中国外运(集团)总公司)R3′ (EMS)R4′ (中远国际货运有限公司)R5′(德邦物流)的关系比较密切;最终,通过聚类,得到2 个社区,如图3 所示。从图3 中可以看出,社区1 中的供应商的共同特点是他们的客户主要是个人。他们使用的物流公司大都是一些快递公司,使用最多的是顺丰快递和EMS。此社区中的供应商大多数业务是面向个人用户的。社区2 中的供应商的共同特点是他们的客户主要是企业。他们使用的物流公司大都是一些货运代理公司,如中国外运(集团)总公司、中远国际货运有限公司、德邦物流等。此社区中的供应商大多数业务是面向企业用户的。
3 结语
传统K均值数据挖掘算法的好处是不需要进行关系选择和抽取,但是其结果会随着选取实例比率的不同在一个而上下浮动。针对实验中的4 000 个订单数据,分别使用K均值算法[9]、回归算法[10]和相似度挖掘算法在选择实例的比例为5%,10%,15%和20%下得出的挖掘正确率如表2 所示。
经过实验验证,在关系数恒定的情况下,相似度算法的正确率会随着用户选定实例比率的提高而提高,且明显要好于传统K均值挖掘算法,略微高于基于线性回归的多关系抽取算法。
参考文献
[1]SHANKAR L B,BASAVARAJAPPA S,CHEN J C H,et al.Location and allocation decisions for multi-echelon supply chain network:a multi-objective evolutionary approach[J].Expert systems with applications,2013,40:551-562.
[2]WANG Y,MA X L,WANG Y H,et al.Location optimization of multiple distribution centers under fuzzy environment[J].Journal of Zhejiang University(Science A),2012,13(10):782-798.
[3]MIRANDA P A,GARRIDO R A,CERONI J A.E-work based collaborative optimization approach for strategic network design problem[J].Computer&industrial engineering,2009,57(1):3-13.
[4]IYOOB I M,KUTANOGLU E.Inventory sharing in integrated network design and inventory optimization with low-demand parts[J].European journal of operational research,2013,224:497-506.
[5]CHOPRA S,MEINDL P.Supply Chain management:strategy,planning and operation[M].3rd ed.[S.l.]:Pearson Prentice Hall,2007.
[6]KO H J,EVANS G W.A genetic algorithm-based heuristic for the dynamic integrated forward/reverse logistics network for3PLs[J].Computers&operations research,2007,34:346-366.
[7]KANNAN G,SASIKUMAR P,DEVIKA K.A genetic algorithm approach for solving a closed loop supply chain model:A case of battery recycling[J].Applied mathematical modelling,2010,34:655-670.
[8]肖智清.基于SOA的物流信息系统集成平台LESB的研究与实现[D].吉林:吉林大学,2012.
[9]GAZI V P,KAYIS E.Comparing clustering techniques for real microarray data[C]//2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.[S.l.]:IEEE,2012:788-791.
代码相似度分析 篇5
近年来随着因特网技术的发展与普及, 网络上的信息量越来越大, 如何高效地从网络上获得有用的资源变得至关重要。主题爬行器是解决这一问题的技术之一, 它是在预定主题的指引下, 在网络上选择与主题相关的网页进行爬取, 并避免了非相关的网页[1]。传统的爬行策略大多都是通过与关键词机械的匹配, Ehrig等人把本体引入到主题爬行中[2], 利用本体代替了关键词, 利用本体中的词汇层次关系计算出网页的主题相关度, 但本体的描述方法过于复杂, 直接影响了使用效率。在计算网页相关性上, 传统主题爬行策略主要有两类:基于网页内容的搜索策略、基于Web链接评价的搜索策略。基于网页内容的搜索策略是对文本中的相似度进行计算, 根据相似度确定URL优先级;基于Web链接评价的搜索策略是根据Web页面之间的相互引用关系来确定网页的相似度, 从而确定URL优先级队列。基于网页内容的搜索策略虽然简单但忽略了链接结构信息, 所以不能很好的预测链接价值;而基于Web链接评价的搜索策略只考虑了网页之间的相互引用, 但忽略了页面与主题的相关性, 容易出现“出题漂移”的问题[3], 因此不适合挖掘主题资源。本文在综合考虑以上问题的基础上, 设计了一种新的主题爬行策略, 首先通过维基百科对主题进行描述;对下载的网页进行处理后, 综合基于网页内容和Web链接分析来确定URL的优先级。
1 主题爬行策略设计
本文综合维基百科、网页内容和Web链接的方法来设计主题爬行策略, 新策略的处理流程图如图1所示。
1.1 基于维基百科的主题描述
在主题爬虫中如果对主题描述太为广泛就会导致搜索的网页量大而相关性就小;如果太具体就会限制爬行范围, 虽然搜索的网页相关度高, 但是会减少数量[4]。而维基百科[5]是一个动态的、可自由访问和编辑的全球最大的Web知识库。维基百科对其中的每个概念都给出了对应的描述文档, 并以分类树[6]的形式组织在一起。分类树中上层为较泛化的概念, 下层为较细化的概念。
本文通过维基百科的主题向量来描述主题, 约束爬取范围, 具体方法为:
(1) 完善分类树。维基百科中对属于某概念的部分下层概念并不收录进分类树中, 而出现在描述文档中, 这样就导致了分类树不完整, 从而影响相关度计算。本文将这些概念提取出来, 并加入到分类树中。例如, 将出现在“转基因”描述文档中的“遗传工程”加入到“转基因”的分类树中。
(2) 从分类树中提取概念p向上一层的概念集合Cup和向下N层概念的集合Cdown, 组成p的相关概念集合 (Relevant Concept Mass, RCM) , 即RCMp=Cup⋃Cdown⋃ {p}。
(3) 对概念p的相关概念集合中的每个概念RCMp={c1, c2, ⋯, ci, ⋯, cm} (m>0) 计算权重 (0<i<m) , 权重wi由ci与主题概念p的距离d (ci) 决定, W (ci) =μd (ci) 。其中, d (p) =0, 0≤d≤N;0<μ<1, μ根据实验获得;W为递减函数, 即距离主题概念p越近, 权值W越大, 反之, 越小。计算出p的概念集合RCMp后就确定了主题概念的向量空间VSp。
(4) 将主题描述文档经过分词和去除排除词汇后映射到VSp上, 即将词语映射到RCMp中存在并且在分类树中距离主题概念p最近的概念上, 然后统计VSp中每个概念在主题描述文档中出现的频率 (f) , 最终计算主题向量T:
式中:fi等于属于ci的词的频率之和。
1.2 网页主题相关性计算
主题相关性的计算准确与否直接影响了主题爬行器的性能。本文将下载的网页进行分块后, 利用改进的Shark[7]启发式搜索算法, 根据爬行过的网页内容和Web链接信息来计算待爬行网页队列中的URL优先级。
1.2.1 网页内容评价
本文设计两个队列来存放待爬行的URL, 分别为相关度高的优先队列PQ (Prior Queue) 和相关度低的普通队列NQ (Normal Queue) ;设计三类阈值来决定待爬行URL属于哪个队列, 分别为页面内容阈值上限page MaxLimit、页面阈值下限page Min Limit, 节点阈值上限nodeMax Limit、节点阈值下限node Min Limit, 锚文本的相关度阈值anchor Limit。其中, 节点阈值上限即是PQ的最低相关度值, 节点阈值下限即是NQ的最低相关度值。而网页和关键词的相似度计算仍采用向量空间模型, 计算公式如下:
根据相关度可以将待爬URL放入相应的队列中, 若一个页面的主题相关度大于page Max Limit, 则将该页面的子页面放入PQ队列中;若一个页面的主题相关度值介于page Max Limit和page Min Limit之间, 则根据该页面的子页面的锚文字或URL字符串是否包含关键词向量中的关键词来决定是否将其加入到PQ中, 如果满足任何一个条件, 则将其加入到PQ中;否则由子节点的相关度值来决定加入队列的类型。
1.2.2 Web链接评价
本文采用Hits[8]算法思想来进行Web链接评价。Hits算法由Kleinberg首先提出, 用来判断网页重要性, 目前主要用于搜索结果排序。该算法思想是如果一个网页被其他多个网页链接, 则比其他链接少的页面重要。因此引入权威 (Authority) 页面和中心 (Hub) 页面的概念。即好的Hub页面总是指向许多好的Authority页面;反之, 好的Authotirty页面总是被许多好的Hub页面所链接。因此, 这种相互加强的关系可以用于发现Authority页面。算法首先利用爬虫从Web上获取与用户查询相关的部分网页构成网络子图G (V, E) (V为网络子图的节点集, E为网络子图的边集) , 然后通过迭代计算出每个网页的权威值和中心值, 迭代步骤如下:
(1) 确定与主题最相关的K (200) 个页面, 称为root集。
(2) 对于root集中的任一网页p, 将p中所包含的链接加入到root集中, 最多不超过d (50) 个, 扩展后称为base集。
1.2.3 改进的优先级计算
由于基于内容评价的策略忽略了链接结构信息, 在预测链接价值方面存在不足;而Hits算法只考虑了Web页面之间的引用关系, 忽略了页面的主题相关性, 容易造成主题漂移现象。为了克服二者的不足, 本文设计了基于主题敏感的链接分析方法, 称为主题Hits。对于中心Hub页面只有当所指网页为主题相关时才能获得相应值, 该值由所指页面的Authority值和其主题相关度决定;而Hub值由其链接到的页面的主题相关度决定。因此迭代公式如下:
式中:ti指网页i的主题相关度;thr为相似度阈值;Pi指网页i的链接个数;o (i-1) k指网页i-1的第k个链接所指的网页编号。
2 实验与分析
系统选用Java语言在Eclipse平台下开发。实验环境为微机1台, CPU为Intel Core 2, 内存1 GB。软件环境为Windows XP和JDK1.6, 选IIS 6.0为Internet为信息服务, 数据库选用My SQL。系统选用转基因生物为主题, 运行时初始种子网页包括乌有之乡, 天涯网:天涯杂谈、经济论坛, 凤凰网:辩论会、铿锵杂谈, 新华网:发展论坛, 人民网:强国论坛, 百度贴吧, 中华网论坛, 腾讯论坛, 网易论坛, 新浪论坛, 搜狐论坛;主要门户网站新闻及相关转载情况, 主要门户网站:雅虎、搜狐、新浪、网易、腾讯等。关注人物包括:金薇 (国际先驱报) 、张宏良、蒋高明、顾秀林、郎咸平。根据上述内容, 设计了一个主题爬虫, 将三种爬行策略进行对比, 图2是对比结果, 其中, 查准率=主题相关的网页数/总网页数。
上面的分析可知, 新的爬行策略在查询特定主题信息方面比传统的爬行技术有着明显的优势, 随着网页数量的增大, 新的策略在总体上也存在优势。算法中各种参数的设置和阈值的选择对爬行结果有重要的影响, 因此如何确定最有利的参数和阈值有待于进一步研究。
3 结语
本文研究了主题爬虫中爬虫策略的选取, 主要包括对关键字向量的描述、网页优先级计算, 设计并实现了一个通用的主题爬虫爬行策略, 实验表明本文的方法取得了良好的效果, 具有较大的应用价值。
摘要：针对当前常用爬虫爬行策略的不足, 提出结合维基百科和网页相似度分析的主题爬行策略。利用维基百科分类树的结构对主题进行描述;下载网页后对网页进行相应处理, 结合文本相关性和Web链接分析来计算候选链接的优先级。实验表明, 该爬虫搜索结果与主题相关度明显高于传统爬虫, 爬虫爬全率有一定提高。该主题爬虫主题描述方法和爬行策略有一定的推广价值, 尤其在转基因生物领域中, 该爬虫中有一定的创新性。
关键词：维基百科,文本相关性,链接分析,相似度计算
参考文献
[1]蔡号, 贾于波, 黄成伟, 等.Web日志挖掘中的会话识别算法[J].计算机工程与设计, 2009, 30 (6) :1321-1324.
[2]戴智利, 王鑫昱.一种基于动态时间阈值的会话识别方法[J].计算机应用与软件, 2010, 27 (2) :244-246.
[3]AGGARWAL C C, AL-GARAWI, YU P S.Intelligentcrawling on the world wide Web with arbitrary predicates[C]//Proceedings of the 10th International Conference on WorldWide Web.New York:ACM, 2001:89-113.
[4]史天艺, 李明禄.基于维基百科的自动词义消歧方法[J].计算机工程, 2009, 35 (18) :62-65.
[5]Anon.Wikipedia[EB/OL].[2011-02-16].http://wikipedia.jaylee.cn.
[6]赵飞, 周涛, 张良, 等.维基百科研究综述[J].电子科技大学学报, 2010, 39 (3) :321-334.
[7]陈竹敏.面向垂直搜索引擎的主题爬行技术研究[D].济南:山东大学, 2008.