面向教学资源查询的语义相似度和相关度算法

冯　瑶　冯锡炜

(辽宁石油化工大学计算机与通信工程学院　辽宁 抚顺 113001)



面向教学资源查询的语义相似度和相关度算法

冯瑶冯锡炜

(辽宁石油化工大学计算机与通信工程学院辽宁 抚顺 113001)

在基于距离的语义相似度计算方法的基础上，综合多种因素对相似度的影响，提出一种新的相似度和相关度计算方法。将其应用到教学资源领域本体，计算本体概念间的相似度和相关度。实验结果显示该算法可以提高传统基于距离的相似度算法的性能。最后比较了利用该算法的语义查询与传统关键字查询的结果。

语义相似度语义相关度教学资源领域本体

0　引　言

近年来E-Learning正被广泛关注，E-Learning的基础和核心是建立专业教学资源库。但当前Web上的各种教学资源缺乏一致的标准，无法通用和共享，同时资源的知识组织缺乏语义关联，无法进行智能检索等服务。本体是实现语义Web的重要基础和技术，广泛应用于知识表示、知识共享与重用、逻辑推理等领域。本体是使用特定词汇来描述具有明确观点的实体、类、属性和相关函数的形式化概念模型。本体可以通过推理从已知有限的语义关系中推理出更丰富更深层的语义关系，从而增强了本体的表达性。近十年来，很多机构和组织都致力于对本体的研究并把其应用到各种实际领域中来。将本体应用到教学资源领域，构建层次划分清晰、语义关系丰富的教学资源本体库可以优化知识表示，同时为教学资源的语义查询和个性化自主学习做好准备。

语义相似度在信息检索、数据挖掘、自然语言处理等诸多领域有着非常广泛的应用。常用的语义相似度计算方法有基于信息内容的相似度算法、基于属性的相似度算法和基于语义距离的相似度算法:基于信息内容的方法定义两个术语间的语义相似度基于它们最近共同祖先节点的信息内容，信息内容基于统计的方法，统计给定语料库中的概念出现的次数，求得其出现的概率；基于属性的相似度算法是计算本体类的属性的重合度，本体中的两个概念具有的相同的属性越多，它们的相似度就越大；基于语义距离的相似度算法把本体层次按照树来处理，计算本体的术语(类)在一个本体层次中的对应节点的距离[1]。经典的基于距离的语义相似度算法有Path法、Leacock and Chodorow法、Wu and Palmer法：Path法基于连接两个is-a(上下位)本体树中概念节点的最短路径计算相似度；Leacock and Chodorow法在Path法的基础上还考虑了本体树的最大深度对相似度的影响；Wu and Palmer法基于两个概念节点与其最近共同祖先节点的位置关系计算相似度[2,3]。这些方法虽然简单直观，但忽略了其他因素对语义相似度的影响。

语义相关度是比相似度更普遍的概念，包含了概念间除了相似之外的更广范围的关系[2]。一般情况下，如果相似度计算过程中只考虑了上下位关系，那么就称该算法为相似度算法；如果计算过程中除上下位关系外，还考虑了其他类型的关系，那么就称该算法为相关度算法[3]。

本文将语义相似度和相关度计算引入到教学资源领域本体中来，在基于距离的语义相似度的基础上提出了一种综合考虑节点密度、深度及关系强度等因素语义相似度和相关度混合计算方法；同时构建教学资源领域本体，利用实例验证了算法的有效性，将算法应用到教学资源本体的语义查询，与传统的关键字相比提高了查全率和查准率。

1　基于距离的语义相似度算法

本体从层次结构上可以看作是树结构。在本体树中，节点表示概念，连接节点的边表示概念之间的关系。本体树中有一个节点被指定为根节点。每个节点都至少有一条通往根节点的路径，这条路径上的节点都是该节点的祖先节点，距离最近的直接祖先节点叫做双亲节点。对于本体树中的两个节点来说，它们一定共享着共同的祖先节点集合。表示最具体概念的节点一般都与两个节点的最近共同祖先节点相关。给定两个概念c1和c2，一个计算相似度的最常见的方法就是根据它们的本体层次计算节点的语义距离：距离越近，相似度越高。在节点中存在多条路径的情况下，考虑所有路径的最短路径或平均路径。先给出几个常用定义：

(1)depth(ci)：从根节点到ci的路径长度，depth(root)=1。

(2)deep_max：本体树的最大深度。

(3)dist(c1,c2)：c1到c2的最短路径长度。对于本体树中的两个概念节点c1和c2之间的最短路径可以分三种情况定义：

①c1和c2是相同的概念，那么c1、c2和lso(c1,c2)是相同的节点，我们定义c1到c2的语义距离是0，即dist(c1,c2)=0。

②c1和c2不是相同的节点，但是c1是c2的双亲节点，我们指定c1到c2的语义距离是1，例如dist(c1,c2)=1。

③c1和c2既不是相同的节点，又不是双亲节点，我们计算c1到c2的实际边数，所以1

(4)lso(c1,c2)：c1和c2的最近共同祖先节点。

(5)Sim(c1,c2)：概念c1和c2的语义相似度。

根据上述定义，文献[4]提出的计算语义相似度的公式如下：

(1)

2　语义相似度算法的改进

2.1影响语义相似度的其它因素

式(1)只考虑了语义距离，没有考虑节点间具体的关系，还有本体树中影响相似度的其他因素。影响语义相似度的主要因素有节点密度、节点深度和边的类型等[3]：

(1) 本体树的密度

密度越高，概念的划分越细，语义相似度越大[5]。如图1所示本体树中，右半部分的节点间的语义相似度要大于左半部分节点间的语义相似度。

图1　本体树的密度

(2) 节点的深度

节点的位置越深，概念划分得越具体，节点表示的概念越相似[6]。如图2所示本体树中，节点C3和C4的语义相似度大于节点C1和节点C2的语义相似度。

图2　节点深度

(3) 边的类型

最常见的关系就是is-a关系，其他关系例如part-of关系、substance-of等关系，都与边的权值相关[7]。连接一个结点和它所有孩子结点的边的权值可能各不相等。在节点间距离相等的情况下，存在其他关系的节点间的相似度较大。如图3所示本体树中，节点C2和节点C3的的距离与节点C2和C4的距离相等，但C2与C3间存在其他关系，所以C2和C3的语义相似度要大于C2和C4的语义相似度。

图3　节点关系

2.2改进后的相似度算法

综合2.1节的影响因素，本文改进的相似度公式如下：

(2)

式(2)第一项表示c1到c2的最短路径中的上下位关系边的距离，在本体树中c1和c2间一定存在由上下位关系边组成的最短路径，如果c1和c2的最短路径中存在多条上下位关系边，通过累加的方式进行传递。ei表示连接两个节点的第i条关系边，wt(ei)表示ei的长度，即权值；第二项是节点密度，lso(c1,c2)表示节点c1和c2的最近共同祖先节点，degree(lso(c1,c2))表示lso(c1,c2)的度，degree(Tree)表示本体树的度；第三项是节点深度，depth(c1)表示概念c1的深度，depth(c2)表示概念c2的深度。depth(lso(c1,c2))表示c1和c2最近共同祖先节点的深度。α,β,λ是可调节参数，α+β+λ=1，分别调节距离、节点密度、节点深度对相似度的影响度。本文构建的教学资源知识点关系中，本体的上下位关系主要是蕴含关系和其逆关系属于关系，取wt(ei)=1/2；与式(1)相同，本算法将两个同义关系的概念节点当作一个节点处理，将同义关系的语义距离权值取wt(ei)=0。

式(2)的算法是建立在本体树的层次和上下位关系上的，而没有考虑其他关系。对于关系较多的本体，还要考虑到这些关系的强度对本体树中概念相关性的影响。

(3)

式中，Rel(c1,c2)表示c1、c2的语义相关度，rel(ei)表示连接两个节点的关系边ei的权值。γ是调节因子，为了方便计算，γ取1。

最后综合考虑上下位关系的语义相似度和非上下位关系的语义相关度表示为：Col(c1,c2)=Sim(c1,c2)+Rel(c1,c2)-Sim(c1,c2)×Rel(c1,c2)

(4)

式中，c1,c2表示知识点，Sim(c1,c2)和Rel(c1,c2)分别表示知识点c1和知识点c2的基于上下位关系的相似度和基于非上下位关系的相关度。

计算语义相似度和相关度的算法如下：

输入：知识点a和知识点b；关系边的权重Wt(ei)、rel(ei)；调节因子α、β、λ、γ。

输出：知识点a和b的相似度的值。

Step1找到本体树中a到b的路径，获取路径中的关系边的集合，以及最近共同祖先节点lso(a,b)。计算节点a和b的深度depth(a)和depth(b)，祖先节点lso(a,b)的深度depth(lso(a,b))和度degree(lso(a,b))，本体树的度degree(Tree)。

Step2根据本体树中节点a和b之间的蕴含(属于)关系边和同义关系的权值计算式(2)。

Step3如果节点a和b之间除了蕴含(属于)关系和同义关系之外，还具有其它的关系，根据关系的权重计算式(3)。

Step4将step2和step3的结果用式(4)计算知识点a和b的关联度。

2.3进一步改进

式(4)把语义相似度和相关度分开计算，相似度计算同义和上下位关系，相关度计算其它关系；由于相似度也是特殊的相关度，所以把所有关系都按相关度来计算，针对教学资源领域本体，对式(4)进行改进如下：

(5)

3　实验分析

本文使用protégé4.0构建教学资源领域本体。教学资源知识点语义关系是对知识点概念之间的语义相关性的表征。教学资源知识点之间具有丰富的语义关系，这些语义关系是教学资源语义推理和查询的基础。将知识点的语义关系分为上下位关系和相关关系。上下位关系即层次关系，是构建本体概念层次关系的基础，包括蕴含关系和属于关系。相关关系是两个概念之间的非层次关系，包括同义关系、依赖关系、兄弟关系、平行关系和参考关系[8]。

图4　本体树片段

选取教学资源领域本体里的概念对式(1)、式(4)和式(5)进行比较，参考如图4所示本体树片段，应用三个公式比对了12组经常会被查询到的知识点，这些知识点间具备不同的关系，比如“栈”和“线性表”之间具备依赖关系，必须先学习“线性表”才能学习“栈”；“栈”和“队列”是兄弟关系；“插入排序”和“选择排序”是平行关系；“希尔排序”和“直接插入排序”是参考关系。相似度算法比较结果如表1所示。

表1　相似度算法比较

根据领域专家的意见，参考不同的关系强度，经过实验取式(4)不同关系的权值如下：同义关系=0，依赖关系=1，参考关系=1.5，兄弟关系=2，平行关系=2.5，蕴含关系=无穷大；式(5)不同关系的权值如下：同义关系=1，依赖关系=0.9，蕴含关系=0.8，参考关系=0.7，兄弟关系=0.6，平行关系=0.5。经过实验，式(3)的调节因子取α=0.7、β=0.1、λ=0.2时效果较好，式(4)的调节因子取α=0.2、β=0.05、γ=0.15Z、λ=0.6时效果较好，式(1)的调节因子取α=1。

从表1可以看出，式(1)的算法只是单纯地根据概念节点在本体树中的位置计算的相似度，对具体的知识点概念没有明显的区分。式(3)和式(4)的算法都极大地改进了原算法，都可以对不同知识点进行区分。图5直观地显示了式(3)算法和式(4)算法的结果与专家经验的比较。式(4)是式(3)的改进和简化，式(4)算法的结果与专家经验更加符合，并且计算复杂性更低，尽管式(4)对于同义词的相似度计算结果有些偏差，但对查询结果的影响可以忽略，所以本文采用式(4)进行知识点的语义相似度计算。

图5　相似度结果比较图

为验证算法的实效性，用本文介绍的查询方法与传统的关键字查询对200个文本、动画、试卷、课件和视频等教学资源从查全率和查准率两个方面做了比较，根据四个常用知识点进行查询，得到的查询结果对比如表2所示，相似度计算的阈值分别取0.55、0.6和0.65。

表2　查询结果比较

4　结　语

本文综合考虑节点密度、节点深度以及不同关系类型对语义相似度和语义相关度的影响，改进了传统的语义相似度计算公式，提出了一种新的语义相关度算法；并将其应用到教学资源本体，通过实验比对原始的相似度算法和改进语义相关度算法的结果，验证了算法的实效性和优越性；最后在算法的基础上比较了基于本文算法的教学资源领域本体语义查询和传统关键字查询的查全率和查准率。但是本文算法忽略了关系传递和叠加对语义相似度和相关度的影响，关系传递会降低概念间的相似度和相关度，关系叠加会增加概念间的相似度和相关度，下一步改进方向将从这两个方面对知识点概念的相似度和相关度进行进一步的区分。

[1] Mingxin Gan,Xue Dou,Rui Jiang.From Ontology to Semantic Similarity:Calculation of Ontology-Based Semantic Similarity[J].The ScientificWorld Journal,2013(1):1-11.

[2] Wael H,Aly A.A Survey of Text Similarity Approaches[J].International Journal of Computer Applications,2013,68(13):13-18.

[3] 刘宏哲,须德.基于本体的语义相似度和相关度计算研究综述[J].计算机科学，2012,39(2):8-13.

[4] 刘群,李素建.基于《知网》的词汇语义相似度计算[J].中文计算语言学,2002,7(2):59-76.

[5] Kara S，Alan O，Sabuncu O，et al.An Ontology-Based Retrieval System Using Semantic Indexing[J].Information Systems，2011，37(4):294-305.

[6] Cai Songmei,Lu Zhao.An Improved Semantic Similarity Measure for Word Pairs[C].International Conference on e-Education,e-Business,e-Management and e-Learning，2010:212-216.

[7] Eklund P，Ducrou J，Dau F.Concept Similarity and Related Categories in Information Retrieval Using Formal Concept Analysis[J].International Journal of General Systems，2012，41(8):826-846.

[8] 崔巍.网络学习与知识表示[J].现代电子技术,2007(2):107-109.

ALGORITHM OF SEMANTIC SIMILARITY AND CORRELATION FOR TEACHING RESOURCES QUERY

Feng YaoFeng Xiwei

(SchoolofComputerandCommunicationEngineering,LiaoningShihuaUniversity,Fushun113001,Liaoning,China)

A new method of similarity and correlation calculation is put forward over the algorithm of semantic similarity based on distance,integrating various factors which influences the similarity.Then the algorithm is applied to the ontology of teaching resources field to calculate the similarity and correlation between ontology concepts.The experimental results show that the algorithm is capable of improving the performance of traditional similarity algorithm based on distance.By the end,the result of semantic query using the proposed algorithm and the traditional keyword query is compared.

Semantic similaritySemantic correlationTeaching resources fieldOntology

2015-08-01。辽宁省普通高等学校本科教育科学改革研究项目(UPRP20140914);辽宁省教育科学“十二五”规划立项课题(JG13DB077)。冯瑶，硕士生，主研领域：人工智能，语义网。冯锡炜，教授。

TP391

A

10.3969/j.issn.1000-386x.2016.10.061