相似度估计（通用7篇）
相似度估计 篇1
恶意程序代码相似度度量是通过一定的程序检测方法度量恶意程序代码的相似度程序,它主要用在核查软件剽窃[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语言结构的程序代码为例,利用折半查找算法生成恶意程序代码测试数据集进行算法有效性验证。仿真证明该算法具有较好的恶意程序代码相似度估算精度。
关键词：恶意程序代码,相似度估计,LSC算法,串匹配
疾病相似度方法研究 篇2
近年来, 相似度的研究在生物医学领域正受到各方的高度关注, 如:基因序列相似度[1]、生物本体术语的相似度[2]、药物相似度[3]等。而相似度就是指定量估算事物的相似性, 事物间的相似性则主要由事物之间的共同属性进行决定并确定。一个具体的事物, 总是有许许多多的性质与关系, 在此即将一个事物的性质与关系都称做该事物的属性。事物的形状、颜色、气味、美丑、善恶、优劣、用途等都是事物的性质;而包含、被包含、整体、部分、大于、小于、压迫、反抗、朋友、热爱、同盟、矛盾等, 则都是事物的关系。并且任何属性都是属于某种对象的。比较事物的相似度就是定量评估事物间的共同属性。
疾病相似度则是对疾病与疾病之间相似性的量化过程。疾病相似性是疾病与疾病之间的共同属性。疾病的属性包括:疾病与疾病之间的共同关系、疾病与疾病之间共同的关联因素。疾病与疾病之间的共同关系又包括:疾病与疾病之间的包含关系, 如:‘乳腺癌’包含‘男性乳腺癌’和‘女性乳腺癌’。‘乳腺癌’与‘男性乳腺癌’及‘女性乳腺癌’的关系是包含与被包含的关系。‘男性乳腺癌’与‘女性乳腺癌’即通过‘乳腺癌’得到了关联。疾病与疾病之间共同的关联因素包括:共同的致病基因、共同的治疗药物、共同的代谢产物等。例如, 基因‘NOS3’和‘AGTR2’是疾病‘乳腺癌’和‘糖尿病’的共同的致病基因;药物‘caffeine’和‘cisplatin’都是疾病‘乳腺癌’和‘卵巢癌’的治疗药物;代谢产物‘D-Glucose’和‘3-Methylhistidine’都是疾病‘类型2糖尿病’和‘阿尔茨海默氏病’共同相关的代谢产物。
1 疾病相似度发展现状
如图1所示, 计算疾病相似度的方法通常可以从两个角度考虑:基于语义关联计算疾病相似度、基于疾病相关的基因计算疾病相似度。生物医学领域经常利用本体计算术语的语义相似度, 如:基因本体[4]、人类表型本体[5]等。尽管如此, 这些方法中却只有很少一部分已用于计算疾病相似度。Resnik设计的方法即是其中最为常见的方法[6], 该方法更多是应用于基因本体计算基因功能、细胞构成、生物学过程术语的相似度, 而且若与其它多种方法 (union-intersection、longest shared path、JC) [7]相比, 则具有明显的优势[8]。Resnik的方法是利用本体中的‘is_a’关系计算术语相似度, 该方法计算疾病对之间的相似度主要依赖于疾病对信息量最大的共同祖先节点。而Lin的方法[9]则改进了Resnik的方法中对信息熵的比较方法, 从理论角度对Resnik的方法进行了一定的完善。Resnik和Lin的方法最近已由研究人员写入R包[10], 以方便计算疾病的相似度。Wang等人提出的方法对Resnik的方法进行了更深层的优化[11]。该方法在计算疾病对相似度时, 不仅考虑了疾病对的信息量最大的共同祖先节点, 还考虑了疾病对其它的共同祖先节点。该方法的优越性在基因本体中得到了更好的体现, 并且已用于计算医学主题词中的疾病术语语义相似度。
疾病的关联不仅体现在疾病相关的本体上, 而且体现在共同的致病基因上。因此, 研究人员同样关注如何基于疾病的致病基因计算疾病的相似度。目前存在两种基于基因计算疾病相似度的方法。第一种是基于共同的疾病基因 (based on overlapping gene set-BOG) 的方法[12]。该方法比较疾病之间共同相关的基因数目, 由此而获取疾病相似度。若与基于语义的角度计算相似度相比, 该法则从一个全新的角度发现相似的疾病对。因此, 该方法能发现新的未知疾病关联。尽管如此, 在计算疾病相似度时, 该方法却未考虑疾病基因之间的功能关联, 而显然可见的是这种关联对疾病相似度却有着一定影响。第二种方法即基于过程相似性 (process similarity based-PSB) 计算疾病相似度[13], 其中, 过程指的是致病基因相关的基因本体的生物学过程术语。该方法考虑了疾病基因的功能关联, 因此对BOG方法有了很大的提高。PSB与Resnik、Lin、LC和JC的方法相比, 也呈现了良好的性能。基因间的功能关联包含很多方面, 如:基因共表达、蛋白质相互作用、基因本体术语等。另外, 为了提高疾病相似度方法的性能, Fun Sim方法利用综合加权的人类基因关联网络[14]计算疾病相似度。
2 集成的疾病相似度算法
本文集成了疾病之间的基因关联和语义关联, 提出了集成的疾病相似度算法Fun Sim Wang, 计算公式如下:
其中, d1和d2是一对疾病, G1和G2分别是d1和d2相关的基因集, |G1|和|G2|则分别是G1和G2包含的基因数;GA1表示G1和G2信息量最小的共同祖先节点, GAi表示GA1的第i个祖先节点, Fun Sim (d1, d2) 表示了d1和d2之间的功能相似度, 而α表示的是‘is_a’关系表达的语义关联参数。基于Wang等人的研究, α=0.8。
3 验证过程
在图2中, 圆圈表示疾病本体[15]中的疾病术语, 圆圈之间的联系表示疾病术语之间的‘is_a’关系, 其中箭头指向为父节点, 另外一个则是子节点。相似的疾病基准集包括两个疾病集, 并分别来自于两篇文献。具体地, 一个疾病集来自于Suthram等人的研究[16]。该研究利用表达谱数据设计算法寻找到相似的疾病对, 再利用药物进行验证。另外一个疾病集则来自于Pakhomov等人的研究[15], 该数据集通过两个医学专家的联合验证而最终得到[17]。在此将这两部分疾病集合并为基准集, 共有47个疾病, 70个疾病对。以基准集作为正例, 同时从疾病本体中随机地抽取700个疾病对作为反例。更利用五种相似度算法计算相似度, 比较得到的相似度接受者操作特性曲线 (receiver operating characteristic curve–ROC curve) [18]。该验证方法共产生了100个随机的疾病对, 分别实验了100次, 以提高实验的真实可靠性。
4 实验结果与分析
图3 (a) 给出了通过每种方法得到的ROC曲线, 图的横坐标表示特异性, 图的纵坐标表示敏感性。由图可知, 通过每种方法得到的ROC曲线下方的面积分别为:Resnik (63.14%) 、Lin (66.17%) 、Wang (68.04%) 、BOG (78.10%) 、PSB (89.52%) 、Fun Sim (94.37) 、Fun Sim Wang (95.36%) 。对于每种方法而言, ROC曲线下方的面积 (AUC) 越大, 表明方法性能越好。而由图3中ROC曲线下方的面积清楚显示了Wang的方法比Resnik的方法有了一点提高, 且Wang的方法和Resnik方法得到的面积非常接近。显而易见, 在基于基因的方法中, BOG方法的性能是最差的。尽管通过PSB方法得到了很高的性能, Fun Sim仍然将PSB方法的性能提高了5%左右。在融合了基因功能和语义关联后, Fun Sim Wang方法已将性能提高到接近100%。
为了避免实现结果由于偶然的因素造成, 研究随机生成了100份疾病对集合, 并进行了100次实验。实验结果如图3 (b) 所示。图中横坐标是疾病相似度方法, 纵坐标是平均的AUC值。由该图可知, 平均的AUC值分别为:Resnik (63.45%) 、Wang (67.84%) 、BOG (76.57%) 、PSB (89.84%) 、Fun Sim (94.15%) 、Fun Sim Wang (95.56%) 。所得结果与图3 (a) 的结论亦保持了一致。
在七种疾病相似度方法中, Resnik的方法利用最大信息量共同祖先的信息熵识别疾病间的语义关联。在基准集中, 有一些疾病对仅存一个共同的祖先节点 (根节点) 。因此, 根据Resnik方法, 这些疾病对的疾病相似度即为0。例如:疾病对‘diabetes mellitus (DOID:9351) ’和‘Alzheimer’s disease (DOID:10652) ’的相似度为0, 因为在疾病本体中, 该疾病对的最大信息量共同祖先是根节点, 而根节点的信息量为0。为了避免错误地理解相似的疾病对, Sem Sim中就没有使用信息量。如此一来, 发生以上的情况时, 疾病相关的基因功能关联就能发挥应有作用。图3中的ROC曲线表明SemFun Sim方法取得了最高的AUC值, 这即充分验证了被集成进来的语义关联对识别真阳性率和减少假阴性率已获明显提高。
5 结束语
本文提出了一种新的疾病相似度算法。该算法融合了语义关联与基因功能关联。语义关联是指疾病与疾病之间通过疾病本体的‘is_a’关系建立的关联。基因功能关联指的是疾病相关的基因之间存在的功能关联, 包括:基因本体术语关联、蛋白质相互作用关联、共表达关联等。本文利用基准集 (70个相似的疾病对) 及100个来自疾病本体的随机集 (700个疾病对) , 对Fun Sim Wang方法进行了性能评估。而且, 在ROC曲线之下的面积已经达到了95.56%, 该结果表明Fun Sim Wang获得了一个非常高的真阳性率和非常低的假阴性率。
摘要：本文研究了集成语义与基因功能关联的疾病相似度方法。综合的加权的人类基因关联网络可用于衡量疾病相关的基因集之间的关联分值;疾病术语对以及其在疾病本体中的共同祖先相关的基因数可用于计算疾病术语的语义关联分值。这两类关联被用于计算集成的疾病相似度。通过从文献中搜集相似的疾病对作为基准集, 对疾病相似度算法的性能进行了有效的评价, 证实了集成的疾病相似度方法优于已有的其他方法。
相似度估计 篇3
1)答疑是学生进行系统学习的有益补充,同时也是学生巩固知识的重要途径,无论学习的形式如何变化,答疑对于学习活动来说是必要且不可或缺的,在网络坏境下,及时、有效地获得解答是学生远程学习的基本需求。
2)通过对学生所提问题的记录分析,可以统计出学生普遍存在的知识薄弱环节,为教师进一步改进教学方法提供参考,成为辅助教学的有效工具。
3)在网络环境下的智能答疑系统采用了友好自然的自然语言接口,学生可以轻松自如地提问,及时解决学习过程中遇到的难题,使远程教学真正起到用户良师的作用,对于远程教学方式在我国的进一步普及,具有不可估量的重大意义。
4)将功能良好的智能答疑系统应用于国家大力发展的远程教学支撑平台中,具有很大的社会价值。
5)为自然语言理解以及信息检索技术的应用发展提供了一个方向,可以推动该技术领域的发展。
如何让计算机理解用户提出的自然语言描述的问题,检索到目标问题,并自动的返回答案,这是智能答疑系统的关键。本文讨论怎样根据用户问题去匹配目标问题的思想及其算法,这也是智能答疑系统的最终目的。
1 问题关键词匹配度计算
一个问题中含有一个或多个关键词,但是每个关键词在句子中的地位是不一样的,有的起决定性的作用。该类关键词就是要重点考虑的关键词,它与问题的匹配度为1。如:“编译原理是什么?”,含有关键词“编译原理”、“编译”,在这个问题中学生要问的是“编译原理是什么”,因而“编译原理”是要重点考虑的关键词。但是“编译”也属于《编译原理》这门课程的专业词,匹配时也可以考虑,因为这将有利于问题答案的检索。如果学生问的“编译是什么?”,若FAQ中没有该匹配对,不能检索到相同的问题则检索近似的问题。
例如:编译原理是什么?
起决定性作用的关键词,它与该问题的匹配度为1,不起决定性的关键词与问题的匹配度为0.5。
采用这种策略,可以实现简单的语义分析。
例如:“编译原理是什么?”与“什么是编译原理?”是同一个问题。如果用户输入的是这两个问题,则检索到的都是同一个问题。
如果问的是“编译是什么?”(假设FAQ中没有该问题与“编译”的匹配度为1的匹配对),则检索到近似的“编译原理是什么?”,然后返回其答案。这样系统用一个近似的问题及其答案来回答学生所问问题,从所返回的答案中学生能有所启发。
2 基于问题关键词匹配度的相似度计算
系统根据用户所问问题去检索相应的问题及其答案,即根据用户问题去匹配目标问题。匹配到的目标问题是否与用户问题对应,相似程度有多大?这将涉及到相似度问题。
句子相似度计算在自然语言处理中有着广泛的应用,例如,在基于实例的机器翻译中的源语言检索,面向常问问题集的自动问答系统中的问句检索等领域。在不同的具体应用中,相似度的含义也有所不同。例如,在基于实例的机器翻译中,相似度主要用于衡量文本中词语的可以相互替换使用而不改变文本的句法语义结构的程度;在信息检索中,相似度更多的是反映文本与用户查询在意义上的符合程度。
目前常见的两种句子相似度的计算方法:(1)基于词向量空间模型的TF-IDF相似度计算方法;(2)基于语义词典的相似度计算方法。
本文在这两种相似度计算方法的基础上提出了一种新的相似度计算——基于问题关键词匹配度的相似度计算:
当用户问题中的关键词与目标问题的匹配度为1且句子类别一致时,则认为目标问题与用户问题完全相似,相似度为1。
当用户问题中的关键词与目标问题的匹配度为0.5且句子类别一致时,则认为目标问题与用户问题近似相似,相似度为0.5。
当用户问题中的关键词与目标问题的匹配度为1或0.5但句子类别不一致时,则认为目标问题与用户问题低相似,相似度为0.25。
利用这种相似度计算方法,相似度在系统实现中不用单独计算,它的计算隐含在问题匹配中。
在实际的系统实现中,一般只要考虑前两种。这种方法是一种非常有效的相似度计算方法,在实际的系统中能大大提高系统的效率,减少了传统的相似度计算的复杂统计及计算。
3 问题匹配算法
利用本文中提出的相似度计算来完成问题的匹配——用户问题与目标问题的匹配。
利用FAQ库进行用户问题解答的基本计算流程如下图所示:
3.1算法程序代码
while(rsl1.next())//判断CutWord表是否为空即是否切到了关键词;AND判断是否遍历完;(技巧:只要能进入循环就不是空即切到了关键词;于是随即就可以进行遍历)
4 结束语
本文阐述了智能答疑系统的作用,介绍了一种基于问题关键词匹配度的相似度计算,然后利用该思想来完成问题匹配,并给出了问题匹配算法的流程图以及程序代码。
摘要：答疑是教学中不可或缺的环节,传统面对面的答疑浪费时间和精力,因而开发高效、准确、智能化的自动答疑系统是必要的。系统返回答案的准确性在一定程度取决于问题匹配的相似度。该文介绍了智能答疑系统中传统的相似度计算,然后在传统的相似度计算的基础上提出了一种新的相似度计算方法——基于问题关键词匹配度的相似度计算,同时给出了该思想在系统中的实现算法。
关键词：智能答疑系统,相似度,匹配度
参考文献
[1]侯丽敏.基于网络的智能答疑系统的研究与实现[D].河南:河南大学,2005.
本体相似度计算方法研究 篇4
本体映射算法以两个本体作为输入, 然后为这两个本体的各个元素 (概念、属性或者关系) 建立相应的语义关系。相似性提取是本体映射的一个重要步骤, 它主要是进行概念相似度的计算, 提高语义相似度计算精度成为提高语义信息检索质量的关键之一。语义相似度一般是指计算本体概念间的相似度, 多数方法所考虑的概念是基于一个本体的, 跨本体概念间的方法比较少。MD3模型是一种典型的计算跨本体概念间相似度的方法。
1 MD3模型
Triple Matching-Distance Model (MD3) 模型是一种跨本体概念间相似度计算框架。计算实体类a和b之间的相似度通过计算同义词集、特征属性和语义邻居之间的加权和, 公式如下:
其中w, u, v表示了各组成部分的重要性。特征属性细化为组成部分、功能以及其他属性。概念a和b的语义邻居及其特征属性 (即概念的部分、功能及其他属性) 也通过同义词集合描述, 每一个相似度的计算都通过Tversky公式:
其中A, B分别表示概念a和b的描述集合, A-B表示属于A但不属于B的术语集 (B-A相反) 。参数 (a, b) 由概念a和b和在各自层次结构中的深度确定。
2 EMD3模型
MD3模型的不足在于没有考虑对象实例对概念的影响, 同时其语义邻居只考虑语义关系中层次之间的相似度, 没有考虑非层次之间的相似度。本文在MD3模型的基础上, 参考了其概念名称相似度、特征属性, 对本体的结构以及概念描述两方面做了扩充, 重点讨论了跨本体概念间非层次关系的相似度的比较和实例对概念相似度的影响, 把MD3模型扩展到Extension of Triple Mapping Distance model (EMD3) 模型。
2.1 概念属性的相似度
属性有属性名称、属性数据类型、属性实例数据等要素, 因此判断两个属性是否相似主要从这三个要素来考虑。属性名称、属性类型本身是文本类型, 是字符串, 因此可以采用字符串相似度计算方法进行判定。例如用Humming distance来比较两字符串。设两字符串s和t, 则它们之间的相似度可由下式给出:
其中:若s[i]=t[i], 则f (i) =0;否则f (i) =1。由于每个概念的实例对该概念的每个属性都分配了一个相应的值, 对于其他类型的数据, 可以采用下面介绍的方法进行计算。
设概念A的属性为ai, 概念B的属性为bj, 两个属性之间的相似度的计算公式为:
其中wi是权重, 代表属性名称、数据类型、属性实例数据对属性相似度计算的重要程度, 且和为1。设概念A, B之间总共计算出m个sim (ai, bj) , 并设置相应的权值kl, 则概念之间基于属性的相似度为:
2.2 概念名称相似度
知网中概念的语义用义原来描述, 义原是描述概念语义的最小单位, 一共有1500多个义原。由于所有义原根据上下位关系构成了一个树状的层次体系, 所有可以用语义距离计算相似度。假设两个义原在该层次体系中的路径为d, 可以得到两个义原之间的语义相似度如下:式中a是一个可以调节大小的因子。在知网中一个概念由多个义原描述, 所以我们只要计算每个义原的相似度来考虑其重要性, 就可以得到概念之间的名称相似度。计算方法如下:, 其中m, n为概念c1, c2的义原数, wi为第i个义原所占的权重。
2.3 语义关系的相似度
语义关系包括层次语义关系和非层次语义关系, 层次语义关系具有有向传递性, 非层次关系不具有传递性 (如关联关系) 。
(1) 层次语义关系的计算
本文借鉴参考文献[1]中的方法来计算层次语义关系, 利用语义邻居的概念, 以实体为中心向周围辐射, 设定一个语义半径, 半径取值的大小反映与实体之间的亲疏关系。划定语义邻居的范围集合进行匹配, 取集合中的最大值作为语义邻居之间的相似度。语义邻居计算公式如下:
层次语义关系相似度计算:其中A, B分别代表实体a, b的语义邻居集合。
(2) 非层次语义关系的计算
上位词:定义概念的上位词为概念所有父类的集合, 公式如下:UC (Ci, H) ={CjC|H (Ci, Cj) }
基于概念上位词的定义, 定义概念的匹配公式:
与概念相关的非层次关系:如果关系的定义域或值域是概念c, 则称这些关系为与概念c相关的非层次关系, 公式如下:
还可以进一步把非层次关系细化为概念的In关系和Out关系 (可以认为非层次关系的方向是从定义域到值域, 凭此来定义In和Out的关系) , In关系指概念c是非层次关系的值域, 公式如下:。而Out关系指的是概念c是非层次关系的定义域, 公式如下:
比较概念的非层次关系, 首先应该找出两个本体中与这两个概念相关的同类非层次关系 (无需考虑不同类的非层次关系) , 进而比较这些同类非层次关系的另外一项之间的相似度 (如果要比较的概念是非层次关系的定义域, 分别找出这个关系的值域, 通过概念匹配公式对其进行比较, 反之亦然) 。
下面以In关系为例描述比较的过程:其中RaP-I表示本体p中与概念a相关的In关系, 而Rqb-I表示本体q中与概念b相关的In关系, 所以其交集RI表示本体p, q中与概念a, b相关的公共In关系集合。如果概念a, b没有公共的In关系, 则RI为空, 无需下面的计算。对于公共In关系集合, 公式如下:对In关系和Out关系进行加权综合, 得到非层次关系相似度的公式如下:
其中i, o为权值, 反映的是非层次关系的值域与定义域对概念相似度的影响程度。对层次关系和非层次关系计算结果进行综合, 得到概念语义环境的相似度计算公式如下:
其中t, u分别是层次关系和非层次关系的权重, 因为在本体中层次关系要比非层次关系的重要性高, 所以在计算中应该赋以较大的值, 即t>0.5>u, 且t+u=1。
2.4 概念实例特征的相似度
基于实例特征计算相似度的理论依据是, 如果概念所具有的实例全部都相同, 那么这两个概念是相同的;如果两个概念具有相同实例的比重是相同的, 那么这两个概念是相似的。对于概念A, B的具体实例, 可以用Jaccard系数来计算相似度:
其中P (A, B) 表示一个实例既属于概念A又属于概念B的概率, 表示一个实例属于概念A但不属于B的概率。
2.5 结论
由上面的分析, 综合了各个部分相似度的值, 得到跨本体概念间相似度的综合公式如下:
其中m, n, r, t为各个部分所占的权重, 根据各个部分重要性的不同m, n, r, t分别被赋以不同的值, 并且m+n+r+t=1。
3 结语
本文扩展的模型充分继承了MD3模型的优点, 并对MD3模型进行了优化。在选择了适当权重的前提下, EMD3模型能够确保语义相似度的计算更准确, 更全面。但是在语义相似度计算过程中存在着大量权重的设定问题, 对模型的性能有一定的影响。如何准确高效地设定权重是未来值得深入研究的问题。
摘要：MD3模型是一种系统的跨本体概念间相似度的计算方法, 这种方法无需建立一个集成的共享本体。本文在MD3模型的基础上, 充分利用本体对概念的描述信息, 重点讨论了跨本体概念间非层次关系相似度的计算, 把MD3模型扩展到EMD3模型, 使得概念间相似度的计算理论上更全面、更精确。
关键词：本体,元数据模型,语义相似度,MD3模型
参考文献
[1]Rodriguez M A, Egenhofer M J.Determining Semantic SimilarityAmong Entity Classes from Different Ontologies.IEEE Trans.onKnowledge and Data Engineering.2003.
[2]徐德智, 肖文芳, 王怀民.本体映射过程中的概念相似度计算[J].计算机工程与应用.2007.
[3]陈杰, 蒋祖华.领域本体的概念相似度计算[J].计算机工程与应用.2006.
[4]李鹏, 陶兰, 王弼佐.一种改进的本体语义相似度计算及其应用[J].计算机工程与设计.2007.
[5]Alexander Budanitsky, Graeme Hirst.Evaluating WordNet-basedMeasures of Lexical Semantic Relatedness[J].Computational Linguis2tics.2006.
一种综合概念相似度计算方法 篇5
关键词：异构,本体,映射,概念相似度
在当代知识集成的研究中, 无论是应用在普通知识系统中的本体, 还是应用于语义Web中的本体, 由于其表示形式和内在逻辑结构的多样性, 本体的数量也越来越多, 并且单个本体不能充分完成目标任务。因此, 必须联合多个本体来完成任务。由于本体的构造一直没有一个统一的规范和标准, 所以, 在同一个领域内会存在多个本体。这些本体的概念分类可能不同, 概念间的关系也可能不同, 并且相同的概念可能用不同的术语来表示。也就是说, 这些本体之间存在冲突, 它们是不匹配的, 是异构的。异构的本体之间不能进行互操作。要想达到信息交流的目的就必须在本体之间架起语义映射的桥梁。因此, 解决本体异构最有效的方法就是本体间进行映射。
本体映射的目的就是找到本体中概念之间的对应关系, 并制定出相应的映射规则。最初, 这些映射过程都是由人手工完成的。但随着语义Web的发展, 在Web上用本体表示的信息越来越多, 仅仅由人来完成这些工作已经力不从心, 因而迫切需要发展一些方法, 来自动地或半自动地完成这种映射过程, 以节省大量的人力劳动。当前有不少研究者致力于本体概念相似度的研究, 取得了一些成果, 但是还存在不少问题, 概括起来主要有如下两个: (1) 概念相似度的计算量大; (2) 概念相似度计算的片面性和计算方法的不完善。单纯从某一方面来计算概念相似度是片面的和不完善的, 概念相似度的计算应该充分考虑本体和概念的特点, 综合各个方面来进行计算。针对概念相似度计算中存在的问题, 提出了一种改进的计算方法, 先分别计算基于实例的概念相似度、基于概念名的相似度和基于属性的相似度, 然后进行加权合并形成新的综合相似度计算方法, 最后进行简单验证进而根据本体和本体中概念的特点, 设计了一种改进的相似度的计算方法。
1 本体映射及其过程
本体映射通过定义条件规则、函数、逻辑以及表与关系的集合来实现不同本体间的映射, 是完成本体集成的重要一步工作, 或者说, 本体映射是不同的本体在概念层语义相关联。源本体的实例根据语义关联的关系转换为目的本体。Ehrig给出了一个形式化的本体映射函数:
map:O1→O2;
如果sim (e1, e2) >s, map (e1) →e2, 其中e1和e2分别是两个本体中的实体, sim (e1, e2) 是这个实体的相似度, s是相似度阀值。
本体映射是指在两个本体中存在语义级的概念关联, 通过语义的联系, 实现将源本体的实体 (概念、实例、属性等) 映射到目标本体实体上的过程。本体的映射类型有概念-概念、属性-概念、属性-属性、情境和约束等。本体映射就是指给定两个本体A和B, 对于A 上的每一个实体, 设法在B上找到与其有相同或相近语义的实体, 这些实体包括本体中的类、属性以及类的实例。一个完整的映射框架应该包括整个映射过程:映射的发现、表达和执行。一个本体映射的过程, 如图1所示。
2 相似度及相似度计算
本体一般可理解为概念、属性和关系的集合。属性即概念的属性, 关系即概念间的关系, 因此, 本体映射主要是集中在概念间的相似度计算及相应的映射。在映射过程中, 本体映射的核心内容是计算两个概念间的相似度, 并求出本体中概念的相似矩阵。当其相似度大于某个阈值时就认为这两个概念间存在一定的映射关系 (这里只着重考虑1∶1的映射关系) 。
先定义相似度:Sim:w1×w2×O1×O2→[0, 1], 相似值在0和1之间。Sim (A, B) 表示A和B之间的相似度。w1和w2是两个本体所基于的术语集, O1和O2是需要映射的两个本体。
Sim (e, f) =1表示e和f是两个完全相同的概念;
Sim (e, f) =0表示e和f是两个完全不同的概念。相似度综合公式:
undefined, 其中undefined
wk为每种度量方法的权植。
3 改进的综合概念相似度计算方法
把概念相似度分成基于实例的概念相似度、基于概念名的概念相似度和基于属性的概念相似度。先分别计算相似度, 然后把基于实例的概念相似度、概念名的相似度和属性的相似度进行合并生成最终的综合概念相似度。
(1) 首先设实例相似度为Sims (a, b) , 利用概念具体实例对概念相似度进行计算。
一个概念的实例也是它祖先概念的实例。对于一个实例, 利用Jaccard系数来计算相似度。该系数的计算公式为:
undefined
根据本体中概念a和概念b的具体实例来计算undefined和undefined。其中P (a, b) 表示一个实例在某本体中即属于概念a, 又属于概念b的可能性。undefined表示一个实例在某本体中属于概念a, 但不属于概念b的可能性。undefined表示一个实例在某本体中不属于概念a但属于概念b的可能性。
undefined
其中H指实例个数, U指实例集合, H (Uundefined) 表示在U1中即属于a又属于b的实例个数。以P (a, b) 为例, 先对本体a中概念A的实例进行样本训练, U1是本体a的实例集合, 根据概念A把U1分成实例集Uundefined和实例集undefined, 由实例数据可计算可得undefined, 同理本体b中概念B的实例进行样本训练, U2是本体b的实例集合, 根据概念B把U2分成实例集Uundefined和实例集undefined, 由数据可以得到, undefined。然后把本体a和本体b位置调换。先对本体b中概念B的实例进行样本训练, 同样可以得到, undefined, 等值, 最后可以利用公式3-5算出以上的公式。
(2) 基于概念名计算概念相似度:
本体中的概念是分层的。本体也可以看成一棵概念树, 树中每个结点代表一个概念。所以, 概念间的关系也具有树的一些性质。树中有子结点、父结点和兄弟结点等一些特有概念, 所以, 概念树中也存在子概念、父概念和兄弟概念。这里按照 [Tversky1977]和集合论给出语义相似值的一般性计算公式作为两个本体间概念相似度计算的方法, 令计算所得的相似度记为Simr (a, b) :
undefined
这里的A、B分别是概念节点a, b描述元素的集合, 对于不同的匹配标准, a, b的描述元素是不同的;|A∩B|是共有描述元素的个数, 或者称共有描述元素集合的势;|A/B|也同集合论中的意义;depth () 函数计算概念节点在概念树中的深度。α (a, b) 系数是反映两个概念在各自本体层次中的位置, 以及本体描述的详细程度不同对语义上相似性评价产生的不对称的影响。这个公式符合上述的语义相似Simtree (a, b) 所具有的性质, 而且与信息论中的相似性定义相一致。
(3) 计算基于属性的概念相似度:
在本体中, 每个属性也是一个概念, 两个属性间的相似度记为Sima (a, b) , 属性的语义评价是对两个概念的属性集合进行评价, 因为属性表达为<属性名, 属性值的约束>这样一个二元组, 令a的属性集合的势为m, b的为n, 因此有公式 (5, 7) 的变形。
undefined
其中undefined, 即近似计算a, b 集合中相同语义属性的个数, 为了防止出现a, b的属性集合的势减去ao1∩bo2的差为负数, 有:
f (m, |ao1∩bo2|) =m-|ao1∩bo2|, m>|ao1∩bo2| (9)
(4) 最后综合概念相似度的计算:
Sim (a, b) =
wsSims (a, b) +wrSimr (a, b) +waSima (a, b) (10)
其中ws+wr+wa=1。
4 总结与展望
本体映射是本体融合领域的核心, 是一个非常复杂的过程, 在这个过程中, 包括本体与数据库, 本体与XML文档, 本体与网页上数据等的映射关系。在这里只列出来两个本体间的映射作为研究方法的探讨, 并详细阐述了异构本体映射的过程, 文中使用的是将多种相似度进行综合以体现实体在各个层次上的相似度的方法实现了本体的映射, 对于各种特征权值的确定可由本体专家根据各种特征在本体中出现的频率定义。提出的相似度计算方法有两个优点:一是根据本体语义树的特点和相似度计算的启发规则以及数据挖掘的思想, 合理设置侯选映射集, 降低了计算量;二是根据本体和概念的特点, 对概念相似度计算方法的改进。
参考文献
[1]Guus Schreiber, 史忠植.知识工程和知识管理[M].机械工业出版社, 2003.
[2]王志军, 郭学俊.基于本体的XML语义集成研究[J].计算机技术与发展, 2006 (8) .
[3]李玉华, 刘涛.基于混合本体方法的集成算法研究[J].计算机工程与科学, 2007, (07) 8 (9) :687-693.
[4]H Mihabi, Ana Simonet.Towards a Declarative Approachfor Reusing Domain Ontologies[J].Information Systems, 1998, 23 (6) :365-381.
[5]聂朝晖, 王英林.相似本体间属性映射方法的研究[J].计算机仿真, 2006 (9) .
[6]曹泽文, 钱杰, 张维明, 等.一种改进的本体映射方法[J].科学技术与工程, 2006 (19) .
[7]郑丽萍, 李光耀, 梁永全, 等.本体中概念相似度的计算[J].计算机工程与应用, 2006 (30) .
旅游本体的概念相似度算法改进 篇6
语义相似度是用来衡量文档或术语的语义内容或涵义间的相似程度的概念[1]，目前相似度计算已广泛应用于本体学习与合并、语义标注、知识管理中的信息抽取及自然语言理解等相关领域。与依赖关键词的检索相比，基于语义的检索能大幅度提高信息检索的查准率和查全率[2]。而概念的相似度计算决定了语义匹配的精确度，是语义检索的基础，因此提高概念相似度计算的精确度成为本体应用的关键。
目前，国内外学者已经对概念相似度计算进行了广泛的探索和研究，提出了很多计算相似度的方法。根据所使用的数据源及数据源的使用方式，相似度算法大致可分为基于路径的方法、基于特征的方法、基于信息内容IC(Information Content)的方法。基于路径的方法把概念相似性度量建立在本体中分割两个概念的语义连接数目上[3,4]。基于特征的方法根据本体概念描述模型中相同和不同的概念属性来估计概念间的相似度[6]。基于信息内容的相似性度量方法把概念信息量与本体知识相结合[7,8,9]。传统的信息内容求解方法是基于统计方法，统计给定语料库中的概念出现的次数，求得其出现的概率，从而得到信息内容值。但是基于统计的方法会受语料库内容的影响，工作量较大。
本文结合Word Net词典本身结构，综合考虑概念在分类树中的子节点信息、深度信息、公共父节点信息，提出了一个新的基于信息内容的概念语义相似度算法，这种基于Word Net本身结构的求解方法不需要其他语料库的参与，简单易行。同时本文利用Word Net词典，构建了旅游领域本体，通过实例证明该算法有效地提高了概念间语义相似度计算的准确度。
1 信息内容
1.1 信息内容算法概述
用数学语言去描述Word Net中的概念的信息内容参数，P(c)表示遇到概念c的实例的概率。根据信息理论中的定义，信息内容表示为-log P(c)，即IC(c)=-log P(c)，含义是一个概念的出现的概率越大，则该概念的自信息量就越小。其中，c是指某一具体概念，IC(c)指概念c的信息内容值。在Resnik的实验中，求解P(c)的方法是统计布朗语料库中名词出现的频率，计算方法可以形式化表示为:
其中，count(w)表示单词w在语料库中的个数，N表示语料库中的名词个数。
由式(1)可以看出，对于不同的语料库，则有可能得到不同的IC(c)。这是因为语料库中的概念是有限的。不同的语料库概念的数量也不同，出现的频率也不一定相同。由此可见，基于语料库进行词频统计有着不足之处。
Seco的IC计算模型是基于Word Net自身分类树结构来求解[10]。Seco发现子节点越多的概念所包含的信息量越少，而那些叶子节点的信息量最大。Seco的计算模型形式化表示为:
其中，hypo(c)返回值为概念的所有子节点数，max_node是一个常量，表示存在于分类树的所有概念的数目。
然而，该模型只考虑了概念的子节点数。如果在本体树中两个概念的子节点个数相同，则IC值相同。为此，Zhou在此算法基础上加入了概念深度因素[11]:
其中，depth(c)是概念深度，max_depth是本体树的最大深度。虽然上述算法较之Seco算法有所改进，但该模型仍无法区分概念子节点数相同、深度相同时的IC值。
1.2 信息内容算法改进
通常我们用Sim(A,B)来表示概念A和B间的相似度。概念信息内容的精确与否直接影响到概念间相似度的比较。经过分析，本文认为影响概念信息内容及概念间相似度的因素有:
(1)被比较概念在本体树中的深度。根据Resnik[7]和Seco[10]理论，概念深度越小，说明出现频率越高，则该概念越抽象，所涵盖的信息内容也就越少。反之，底层概念更为具体，所继承的信息内容也越多，概念间所共享的上层信息概率越大，因此底层概念间的语义相似度一般大于高层概念间的相似度。如IC(水果)
(2)被比较概念在本体树中所在簇的密度(簇:在语义树中，从根节点分出的树枝[12])。簇中概念节点越多，密度越大，说明对该簇根节点概念的细化程度越大，所对应的子节点所代表的概念也就更为具体，信息内容也就越大，所共享信息的概率也就越大，因此相似度越高。如第2节的图1中Activity簇的细化程度比Accommodation簇高，IC(Relaxation)>IC(Hotel)。
(3)被比较概念在本体树中相隔的路径长度。在密度及路径类型相同的情况下，概念间路径长度越长，相似度越小。如图1中Sim(Luxury Hotel,Hotel)>Sim(Luxury Hotel,Accommodation)。
(4)被比较概念最近祖先节点LCS(Least Common Subsumer)的信息内容。在密度、深度及路径长度相同的情况下，被比较概念最近祖先节点的信息内容越大，概念的信息内容也就越大。如第2节的图1中，IC(Sports)>IC(Rural Area)，则IC(Climbing)>IC(Countryside)。
基于以上分析，提出了基于信息内容特征参数求解的新模型，如式(4)所示:
其中，Cnode_max是概念C所在簇的概念节点总个数，Tnode_max是本体树所有概念节点的个数，AIC是概念C最近公共祖先节点的IC值，Hnode是概念C最近祖先节点拥有的与C深度相同的子节点个数，hypo(c)是概念C的所有子节点，depth(c)是概念C的深度，Tdepth_max是本体树的最大深度。
上述算式中的分母把信息内容值约束在[0,1]之间，本体树中顶层概念节点信息内容值为0，底层概念节点信息内容值为1，如此规律递增。概念节点越向上，说明概念出现的频率越高，所包含的信息内容越少，反之亦然。同样，概念节点所包含的子节点越多，则出现的频率越高，涵盖的信息内容也少。在深度、密度、子节点数都相同的情况下，如果父节点的信息内容值越大，则子节点的信息内容值也越大。
2 实例与仿真
2.1 实例
在研究与旅游有关的知识体系时，我们利用Word Net把有关的本体分成了Activity、Way、Accommodation和Destination四大类。图1为利用Protégé4.1创建的本体库片段。
2.2 实验仿真
为了验证旅游本体库的合理性，以及检验本文算法的实用性和有效性，我们使用MyEclipse 6.5、JDK 1.6.0等开发工具实现了本文中的算法。同时用基于路径的方法(Wu&Palmer[1])、基于特征的方法(David&Montserrat[6])、基于信息内容的方法(Resnik[7]、Jiang&Conrath[9]、Lin[8])对图1中部分本体概念进行了相似度求解并与人工打分进行了比较，结果见表1、表2。其中，基于信息内容的方法分别使用了Seco[10]、Zhou[11]及本文模型进行了结果对比。
本文采用皮尔森相关系数作为评价本文相似度计算公式的标准，如式(5)所示:
其中，xi表示相似度计算公式计算出来第i对概念的相似度值;yi表示由专家判定的第i对概念的相似度值;分别表示它们的平均值;σx和σy分别表示它们的方差。
不同相似度算法和不同信息内容算法对相同概念进行相似度求解的结果。其中，方法1为基于路径算法，方法2为基于特征算法，方法3-方法5为信息内容算法。所对应的具体算法名称详见表3。
从表2中的数据可以看出:本文的算法计算结果比较精确，更为接近人类专家的判断结果。
同时，为了更进一步验证本文算法的本体适用性，将该算法应用于文献[12]的基因本体中，对基因本体的部分概念节点进行了相似度求解，并把该结果与文献[13]中的算法结果进行对比，结果如表4所示。
3 结语
本文给出了概念的信息内容参数模型，该参数可以广泛应用到基于信息内容相似度算法当中。相对比其他模型，该模型不仅考虑了概念的子节点的个数，而且将概念所处于树中最近公共祖先节点、簇中同深度的节点数等纳入模型当中，使得概念的IC值更为精确。通过与其他相似度算法进行比较，结果表明本文算法求得与人工判别得到的相似度值的相关系数更高，同时把该算法用于基因本体，更进一步证明本文中新的IC模型的本体适用性。
摘要：传统的基于信息内容的概念相似度算法在计算信息内容值时过于依赖语料库,给出一个新的只通过WordNet结构计算概念语义相似度的信息内容模型。该模型以WordNet的is-a关系为基础,不仅考虑了概念所包含的子节点个数和所处深度,而且将该概念所处的簇及父节点的信息内容值引入到模型中,使得概念的信息内容值更为精确。实验结果显示将该模型应用到领域本体的概念相似度计算中,可以明显提高现有相似度算法的性能。
程序相似度判定算法研究与实现 篇7
当前的大学教育中学生作业抄袭现象比较普遍,尤其是程序设计类课程,作业是以电子文档方式存储的,学生可以直接将互联网上或其他同学的作业拷贝过来,作一些简单修改就直接交给老师,抄袭容易[1,2,3]。国外很多教育机构针对程序设计课程的源代码抄袭现象进行的调查显示,高达85.4% 的学生承认抄袭过别人的编程作业[4,5]。教师在大量的程序作业中人工判别抄袭将是一项繁重的工作,也无法确保考核的正确性和客观性。因此,检测程序代码的相似度具有重要的现实意义,可以帮助教师检查学生中的抄袭现象,还可以辅助实现作业批改或者试卷评阅的自动化[6,7]。
程序代码相似度检测早在20世纪70年代初就有学者对此进行了研究。1976年,Purdue大学的Ottenstein[8]首次提出了基于属性计数法度量相似度算法———An Algorithmic Approach to the Detection and Prevention of Plagiarism。Ottenstein首次使用Halstead程序度量方法进行程序相似度识 别,其开发的 某系统可 直接统计M.Halstead[9]提出的衡量程序 长度的4个基本软 件科学参数:n1,n2,N1,N2。Ottenstein认为两个程序具有相同的4个属性值的可能性是非常小的。这4个程序的参数,构成一个向量vi,设另一程序4个参数构成向量vj,则可通过计算这两个向量的夹角余弦作为其相似度。1992年,Komondoor和Horwitz提出使用 切片技术 进行检测[10],把语句完全相同的代码中间夹杂的不相关语句放到该部分代码的前面或后面,如此就会使两段相似的代码连成一体,形成一个更大规模的相似代码,进而能够识别出程序中的非连续完全相似代码。1996年,Verco和Wise[11]指出,对于仅仅使用属性计数法的检测算法,增加向量位数并不能改善错误率。改进属性计数法的措施就是加入程序的结构信息,结合结构 度量(structure metrics)来检测相似度。
本文在已有研究的基础上,基于属性度量与最长公共子序列算法,将属性度量的结构无关性与最长公共子序列算法的结构依赖性有机结合,巧妙避开了两个算法原有的缺点,取长补短,从而得到源代码较为可信的综合相似值。
1相似度判定算法分析
1.1最长公共子序列算法
最长公共子序列[12](Longest Common Subsequence,LCS)算法用于计算两个给定字符串分别删除零个或多个字符后得到的长度最长的相同字符序列。该算法的核心思想为动态规划[13],以LCS(A,B)表示A,B的最长公共子序列,其动态转移方程如下:
设LCS(Ai,Bj)表示长度为i、j的两字符串的最长公共子序列长度,ai、bj表示字符串中下标为i与j的字符,将动态转移方程改写成易于编程的数学表达式描述如下:
1.2相似代码分类
2001年,Edward L.Jones对程序相似代 码之间的 更改手段重新总结,在不影响程序结果的前提下,将相似代码分为10类情况[14],如表1所示。
这10种情况相对简单的解决策略如下:
(1)对于逐字拷贝产生的代码,由于源代码未作改动,或只有细微改动,对两部分代码使用最长公共子序列算法(以下简称LCS算法),将可以准确得出两代码的相似程度。
(2)对于更改注释语句后形成的代码,由于注释语句与程序功能无任何关联,只具有说明功能,去掉注释对程序的实际运行无任何影响。因此,将需要比对的两段程序去掉注释,即可得到类似于逐字拷贝产生的相似代码,对其使用LCS算法即可得出相似程度。
(3)更改空白区域与更改注释信息的行为类似,只需对源代码进行空格缩进处理,进而使用LCS算法得出相似程度。
(4)重新命名标识符后的源程序,经过编译后与修改之前的源程序产生同 样的可执 行程序,只对可读 性有影响,因此可以对用户自定义变量进行统一替换后使用LCS算法。
(5)通常数据类 型的修改 都会影响 到程序的 执行结果,但也有部分数据类型之间存在隐式转换,绝大多数情况下对此类数据类型的修改将不影响运行结果。因此,将所有可以隐式转换的数据类型统一替换成指定的数据类型后使用LCS算法。
(6)对于更改各类语句、语句块顺序的做法,可以通过Halstead属性统计的方法来计算相似程序,该方法只统计属性的数目而不讨论其出现的位置,因而得出的结果也不受语句顺序的影响。
(7)若用户增加无用语句与变量,则需使用程序切片技术处理,在此不作深入研究。
(8)若用户使用等价语句重新书写源程序,则单从对字符数据处理已无法解决,需对程序进行语法分析处理。若用户对整个源程序 重写,即使通过 语法分析 得出其相似,也很难将其归为抄袭,因为即使正常的代码书写,若逻辑过程一致,则其最终代码与等价重写代码也相似。
学生作业中最常见的相似代码类型为表1中的前8种,本文所研究算法将对后两种情况不予考虑,认可其中的改动部分为不相似。
由前面所述应对策略可以看出,Halstead程序度量法可有效识别出代码语句块顺序错乱的相似代码。而LCS算法则可有效识别出对于代码语句块顺序未发生改变的相似代码,若将两者优点结合,则可较为准确地识别出上述几类相似情况。
1.3解决相似的办法
目前,相似代码的检测所针对的对象主要分为两种:一种是源代码文件,另一种是将源代码进行某种形式的转换,将其转换成 某种内部 信息形式,例如:目标文件 (.obj),然后运用检测方法分别进行比较。已有的识别方法主要分为以下3类:基于String、基于Token和基于ParseTree[15]。
(1)String:源程序以字符串为单位划分,最典型的就是按照行来划分,将这些String相互比较来发现重复的字符串序列。
(2)Token:由词法分析程序将源文件转换成Token,查找相似的Token流。
(3)Parse-Tree:基于源程序文件或者目标文件,建立完整的语法树,搜索树中相似的子树。
三类识别方法特性如表2所示。
本文将Halstead与LCS结合,且算法实现用于编程教学,代码量不会过大,在教学过程中,偶尔也会穿插其它编程语言。因此,使用基于String的处理方式更加合理、更易于实施。
2算法改进
基于对代码相似判定算法进行的一系列研究,以及对各种编程风格进行分析,得出下列要素:
(1)不以行为单位对源码进行分解。在用户编码风格出现差异时,若行内语句过多,行内语句间并无任何内部关联。此种情况下,以行为单 位将可能 导致某种 极端情况,即所有语句都写在同一行上,此时,算法将退化为对整个程序进行相似分 析操作,达不到预 期的分块 目的。因而,本文算法采取以语句为单位对源码进行处理,各编程语言普遍以“;”为语句结束标志,算法将以分号对源码进行分割处理,此举有效避免了上述的极端情况。
(2)只度量属性个数。Halstead程序度量计算法在统计整个源程序文件时,获得的度量属性频度较高,而在采取基于字符串的子句分割处理条件下,度量属性的频度取值往往较低,通常为1。为简化子句的相似度计算,提高程序运行效率,算法将只对度量属性的种类进行考量。对于频度不为1的度量属性,在本算法的处理方法下亦可得到体现。
(3)对单条语 句使用LCS算法度量 其结构相 似度。Halstead程序度量法无法识别程序结构,但可以识别语句顺序发生改动的源码,LCS对程序相似长度进行统计,达到对结构的度量,但对于语句顺序发生变化的源码,LCS计算的相似长度将大为降低。
(4)抄袭程度计 算。由于在预 处理过程 中去掉了 注释、头文件信息,对用户变量进行统一替换,使得源程序丢失过多信息,导致判定算法对修改了此类信息的源码与未修改此类信息的源码进行同等处理。然而,对代码未作修改与稍作修改,这两种做法代表的抄袭心态有巨大差别。虽然都为抄袭,前者的行为更为恶劣。
综合以上结论,改进的算 法实现具 有以下特 性与功能:1对输入源码进行空格紧缩处理;2将源码中的头文件信息、注释信息按照指定格式及顺序移动到冗余信息链表上,供后续处理;3将获取的用户自定义变量及数据类型进行记录后再对其统一替换;4采用基于字符串的子句分割处理,以分号作为分割条件;5对度量属性种类进行权值计算,以方便比较;6各语句片段权值逐一比较,找出最匹配的相似语句;7对权值相似语句排序,计算排序后的最长公共子序列长度,得出单句语句的相似程度;8对所有相似语句进行数据统计,得出最终代码相似度;9对于相似度过高的代码,将继续对其冗余信息采用类似手段考核。
改进的算法能够综合解决相似种类及解释:1逐字拷贝:由于此类程序不论在整体上、局部上以及待度量属性上都未作修改,算法能够有效识别出,而最终得出的相似度必然接近100%;2更改注释语句:由于算法将注释信息添加到冗余队列,在对程序考核之后,若程序主体相似过高,则对注释信息亦会考量,进而得出代码注释部分的相似程度,其结果与程序相似结果独立;3更改空白区域:对于空白区域,算法不对其个数进行统计从而加以区分,多个连续空格将视为一个。因而,用户对空白区域的添加或删除将不对相似程度产生影响;4重新命名标识符:程序主体相似过高时,对标识符列表进行考量,结果与程序相似独立;5更改数据类型:若程序主体相似过高,将对数据类型列表进行考量,结果与程序相似独立;6更改代码块顺序:由于算法采用局部逐一比对,更改代码块顺序将对结果无影响;7改变表达式中的操作符和操作数顺序:Halstead属性只对表达式中的操作符种类统计数量,改变操作符顺序对此无影响;8改变代码块中语句的顺序:原理同6;9增加语句和变量:算法未进行相关的程序切片处理,该做法将降低程序的相似程度;10用等价语句替换原有语句:算法未涉及源程序的语法分析,该做法将降低程序的相似程度。
3改进后的算法流程
在对源码进行比较前,源程序将经过预处理,剔除源码中无用信息并将此信息附加到冗余信息列表中,将源码分解成符合处理要求的形式。
单条语句的权值由操作符与关键字构成,每个操作符与关键字都具有唯一权值,所有操作符与关键字进行逻辑或操作即可得出该条语句的最终权值。
预处理流程中使用的操作符权值计算索引如表3所示。
预处理流程如图1所示。
语句以分号或大括号作为分割符,分割后的语句块作为本算法的基本处理单元。关键字被记录在指定数组中,计算模块获得待计算字符串后,设置初始权值为1,将待计算字符串逐一与数组中关键字比较,同时权值进行左移1位运算,即等效的权值乘以2,找到匹配字符后返回权值,若无匹配,返回 -1表示该字符串非关键字。待判定源码与目标源码预处理结束后,程序将对两份源码的每条语句操作符权值与关键字权值逐一比较,计算出待判定源码与目标源码的关键字权值与操作符权值的最佳匹配。对于匹配值较高的源码,将语句中包含的自定义变量进行统一替换,对替换后的语句执行最长公共子序列算法,计算出公共子序列长度,然后将其值与待定源码和目标源码中长度较长的语句长度计算比值,最终获得待定源码与目标源码间的每条相似语句,程序根据代码量计算相似度,并根据用户需要,将详细结果以指定形式反馈给用户进行人工分析。流程如图2所示。
4算法实现
4.1程序相似度判定实现
4.1.1操作符权值计算
程序依据各类一元操作符的权值,与最终权值进行逻辑与,以获得单条语句的整体权值,代码如下:
4.1.2关键字权值计算
根据单词在关键字表中的位置,得出其相应的二进制位值,与最终结果进行或操作进行置位。
4.1.3权值比较
对权值采取二进制位个数统计,得出相同部分二进制位为1的个数,另取出两个权值中二进制数中1的个数较多的权值,将两数相除后作为权值的相似程度。关键字相似采用与此相同的方法,结果与操作数独立,参考优先级大于操作符相似。
4.1.4最长公共子序列长度计算
对权值相似度达到阈值的语句排序后,采用下列最长公共子序列长度算法计算两语句间的相似程度。
4.2程序相似度判定结果
算法首先以分号或大括号作为分隔符,将语句分割为基本处理单元,然后以多种方式对待测源码与目标源码进行相似度考量,如:目标原始代码考量,剔除无用信息后的考量,统一替换变量后的考量,统一替换可以隐式转换的数据类型等,最终得出 各类相似 值的集合。若用户有 需求,则将详细列表予以展示供人工检阅。在待测代码中,系统逐一对相似代码语句予以不同的颜色显示,并标明其具体的语句相似值,相似值极高的代码采用红色字体显示(如图3中编号为0、1、2、3、4、7的待测代码),相似值极低的代码采用绿色显示(如图3中编号为6的待测代码),对于中等相似予以黄色字体显示(如图3中编号为5的待测代码),其中的“NO”为待测代码的语句编号,“DesNO”为目标代码的语句编号,总体相似程度为各语句相似度的平均值。待测代码与目标代码的相似判定结果值如图3所示。
5结语
算法基于已有的属性度量与最长公共子序列算法,将属性度量的结构无关性与最长公共子序列算法的结构依赖性有机结合,得到程序源代码较为可信的综合相似值。实验结果表明,改进后的算法可以有效降低程序源代码的评测难度,提高评测结果的准确性,得到较为科学的总体相似度值,从而增强评测人员对抄袭现象的监测力度,据此对抄袭者给予警告。
摘要：有效检测程序设计类课程作业抄袭现象具有重要的现实意义。传统的代码相似度检测方法主要利用代码属性或结构信息判定代码之间的相似性。基于已有的属性度量与最长公共子序列算法,提出一种代码相似度检测算法,算法将属性度量的结构无关性与最长公共子序列算法的结构依赖性有机结合。实验结果表明,该算法可以有效降低程序源代码的评测难度,得到较为可信的综合相似度值,增强了评测人员对抄袭现象的监测力度。