馮　瑤　馮錫煒

(遼寧石油化工大學計算機與通信工程學院　遼寧 撫順 113001)

?

面向教學資源查詢的語義相似度和相關度算法

馮瑤馮錫煒

(遼寧石油化工大學計算機與通信工程學院遼寧 撫順 113001)

在基于距離的語義相似度計算方法的基礎上，綜合多種因素對相似度的影響，提出一種新的相似度和相關度計算方法。將其應用到教學資源領域本體，計算本體概念間的相似度和相關度。實驗結果顯示該算法可以提高傳統(tǒng)基于距離的相似度算法的性能。最后比較了利用該算法的語義查詢與傳統(tǒng)關鍵字查詢的結果。

語義相似度語義相關度教學資源領域本體

0　引　言

近年來E-Learning正被廣泛關注，E-Learning的基礎和核心是建立專業(yè)教學資源庫。但當前Web上的各種教學資源缺乏一致的標準，無法通用和共享，同時資源的知識組織缺乏語義關聯(lián)，無法進行智能檢索等服務。本體是實現(xiàn)語義Web的重要基礎和技術，廣泛應用于知識表示、知識共享與重用、邏輯推理等領域。本體是使用特定詞匯來描述具有明確觀點的實體、類、屬性和相關函數(shù)的形式化概念模型。本體可以通過推理從已知有限的語義關系中推理出更豐富更深層的語義關系，從而增強了本體的表達性。近十年來，很多機構和組織都致力于對本體的研究并把其應用到各種實際領域中來。將本體應用到教學資源領域，構建層次劃分清晰、語義關系豐富的教學資源本體庫可以優(yōu)化知識表示，同時為教學資源的語義查詢和個性化自主學習做好準備。

語義相似度在信息檢索、數(shù)據挖掘、自然語言處理等諸多領域有著非常廣泛的應用。常用的語義相似度計算方法有基于信息內容的相似度算法、基于屬性的相似度算法和基于語義距離的相似度算法:基于信息內容的方法定義兩個術語間的語義相似度基于它們最近共同祖先節(jié)點的信息內容，信息內容基于統(tǒng)計的方法，統(tǒng)計給定語料庫中的概念出現(xiàn)的次數(shù)，求得其出現(xiàn)的概率；基于屬性的相似度算法是計算本體類的屬性的重合度，本體中的兩個概念具有的相同的屬性越多，它們的相似度就越大；基于語義距離的相似度算法把本體層次按照樹來處理，計算本體的術語(類)在一個本體層次中的對應節(jié)點的距離[1]。經典的基于距離的語義相似度算法有Path法、Leacock and Chodorow法、Wu and Palmer法：Path法基于連接兩個is-a(上下位)本體樹中概念節(jié)點的最短路徑計算相似度；Leacock and Chodorow法在Path法的基礎上還考慮了本體樹的最大深度對相似度的影響；Wu and Palmer法基于兩個概念節(jié)點與其最近共同祖先節(jié)點的位置關系計算相似度[2,3]。這些方法雖然簡單直觀，但忽略了其他因素對語義相似度的影響。

語義相關度是比相似度更普遍的概念，包含了概念間除了相似之外的更廣范圍的關系[2]。一般情況下，如果相似度計算過程中只考慮了上下位關系，那么就稱該算法為相似度算法；如果計算過程中除上下位關系外，還考慮了其他類型的關系，那么就稱該算法為相關度算法[3]。

本文將語義相似度和相關度計算引入到教學資源領域本體中來，在基于距離的語義相似度的基礎上提出了一種綜合考慮節(jié)點密度、深度及關系強度等因素語義相似度和相關度混合計算方法；同時構建教學資源領域本體，利用實例驗證了算法的有效性，將算法應用到教學資源本體的語義查詢，與傳統(tǒng)的關鍵字相比提高了查全率和查準率。

1　基于距離的語義相似度算法

本體從層次結構上可以看作是樹結構。在本體樹中，節(jié)點表示概念，連接節(jié)點的邊表示概念之間的關系。本體樹中有一個節(jié)點被指定為根節(jié)點。每個節(jié)點都至少有一條通往根節(jié)點的路徑，這條路徑上的節(jié)點都是該節(jié)點的祖先節(jié)點，距離最近的直接祖先節(jié)點叫做雙親節(jié)點。對于本體樹中的兩個節(jié)點來說，它們一定共享著共同的祖先節(jié)點集合。表示最具體概念的節(jié)點一般都與兩個節(jié)點的最近共同祖先節(jié)點相關。給定兩個概念c1和c2，一個計算相似度的最常見的方法就是根據它們的本體層次計算節(jié)點的語義距離：距離越近，相似度越高。在節(jié)點中存在多條路徑的情況下，考慮所有路徑的最短路徑或平均路徑。先給出幾個常用定義：

(1)depth(ci)：從根節(jié)點到ci的路徑長度，depth(root)=1。

(2)deep_max：本體樹的最大深度。

(3)dist(c1,c2)：c1到c2的最短路徑長度。對于本體樹中的兩個概念節(jié)點c1和c2之間的最短路徑可以分三種情況定義：

①c1和c2是相同的概念，那么c1、c2和lso(c1,c2)是相同的節(jié)點，我們定義c1到c2的語義距離是0，即dist(c1,c2)=0。

②c1和c2不是相同的節(jié)點，但是c1是c2的雙親節(jié)點，我們指定c1到c2的語義距離是1，例如dist(c1,c2)=1。

③c1和c2既不是相同的節(jié)點，又不是雙親節(jié)點，我們計算c1到c2的實際邊數(shù)，所以1

(4)lso(c1,c2)：c1和c2的最近共同祖先節(jié)點。

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

根據上述定義，文獻[4]提出的計算語義相似度的公式如下：

(1)

2　語義相似度算法的改進

2.1影響語義相似度的其它因素

式(1)只考慮了語義距離，沒有考慮節(jié)點間具體的關系，還有本體樹中影響相似度的其他因素。影響語義相似度的主要因素有節(jié)點密度、節(jié)點深度和邊的類型等[3]：

(1) 本體樹的密度

密度越高，概念的劃分越細，語義相似度越大[5]。如圖1所示本體樹中，右半部分的節(jié)點間的語義相似度要大于左半部分節(jié)點間的語義相似度。

圖1　本體樹的密度

(2) 節(jié)點的深度

節(jié)點的位置越深，概念劃分得越具體，節(jié)點表示的概念越相似[6]。如圖2所示本體樹中，節(jié)點C3和C4的語義相似度大于節(jié)點C1和節(jié)點C2的語義相似度。

圖2　節(jié)點深度

(3) 邊的類型

最常見的關系就是is-a關系，其他關系例如part-of關系、substance-of等關系，都與邊的權值相關[7]。連接一個結點和它所有孩子結點的邊的權值可能各不相等。在節(jié)點間距離相等的情況下，存在其他關系的節(jié)點間的相似度較大。如圖3所示本體樹中，節(jié)點C2和節(jié)點C3的的距離與節(jié)點C2和C4的距離相等，但C2與C3間存在其他關系，所以C2和C3的語義相似度要大于C2和C4的語義相似度。

圖3　節(jié)點關系

2.2改進后的相似度算法

綜合2.1節(jié)的影響因素，本文改進的相似度公式如下：

(2)

式(2)第一項表示c1到c2的最短路徑中的上下位關系邊的距離，在本體樹中c1和c2間一定存在由上下位關系邊組成的最短路徑，如果c1和c2的最短路徑中存在多條上下位關系邊，通過累加的方式進行傳遞。ei表示連接兩個節(jié)點的第i條關系邊，wt(ei)表示ei的長度，即權值；第二項是節(jié)點密度，lso(c1,c2)表示節(jié)點c1和c2的最近共同祖先節(jié)點，degree(lso(c1,c2))表示lso(c1,c2)的度，degree(Tree)表示本體樹的度；第三項是節(jié)點深度，depth(c1)表示概念c1的深度，depth(c2)表示概念c2的深度。depth(lso(c1,c2))表示c1和c2最近共同祖先節(jié)點的深度。α,β,λ是可調節(jié)參數(shù)，α+β+λ=1，分別調節(jié)距離、節(jié)點密度、節(jié)點深度對相似度的影響度。本文構建的教學資源知識點關系中，本體的上下位關系主要是蘊含關系和其逆關系屬于關系，取wt(ei)=1/2；與式(1)相同，本算法將兩個同義關系的概念節(jié)點當作一個節(jié)點處理，將同義關系的語義距離權值取wt(ei)=0。

式(2)的算法是建立在本體樹的層次和上下位關系上的，而沒有考慮其他關系。對于關系較多的本體，還要考慮到這些關系的強度對本體樹中概念相關性的影響。

(3)

式中，Rel(c1,c2)表示c1、c2的語義相關度，rel(ei)表示連接兩個節(jié)點的關系邊ei的權值。γ是調節(jié)因子，為了方便計算，γ取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)；調節(jié)因子α、β、λ、γ。

輸出：知識點a和b的相似度的值。

Step1找到本體樹中a到b的路徑，獲取路徑中的關系邊的集合，以及最近共同祖先節(jié)點lso(a,b)。計算節(jié)點a和b的深度depth(a)和depth(b)，祖先節(jié)點lso(a,b)的深度depth(lso(a,b))和度degree(lso(a,b))，本體樹的度degree(Tree)。

Step2根據本體樹中節(jié)點a和b之間的蘊含(屬于)關系邊和同義關系的權值計算式(2)。

Step3如果節(jié)點a和b之間除了蘊含(屬于)關系和同義關系之外，還具有其它的關系，根據關系的權重計算式(3)。

Step4將step2和step3的結果用式(4)計算知識點a和b的關聯(lián)度。

2.3進一步改進

式(4)把語義相似度和相關度分開計算，相似度計算同義和上下位關系，相關度計算其它關系；由于相似度也是特殊的相關度，所以把所有關系都按相關度來計算，針對教學資源領域本體，對式(4)進行改進如下：

(5)

3　實驗分析

本文使用protégé4.0構建教學資源領域本體。教學資源知識點語義關系是對知識點概念之間的語義相關性的表征。教學資源知識點之間具有豐富的語義關系，這些語義關系是教學資源語義推理和查詢的基礎。將知識點的語義關系分為上下位關系和相關關系。上下位關系即層次關系，是構建本體概念層次關系的基礎，包括蘊含關系和屬于關系。相關關系是兩個概念之間的非層次關系，包括同義關系、依賴關系、兄弟關系、平行關系和參考關系[8]。

圖4　本體樹片段

選取教學資源領域本體里的概念對式(1)、式(4)和式(5)進行比較，參考如圖4所示本體樹片段，應用三個公式比對了12組經常會被查詢到的知識點，這些知識點間具備不同的關系，比如“棧”和“線性表”之間具備依賴關系，必須先學習“線性表”才能學習“?！?；“?！焙汀瓣犃小笔切值荜P系；“插入排序”和“選擇排序”是平行關系；“希爾排序”和“直接插入排序”是參考關系。相似度算法比較結果如表1所示。

表1　相似度算法比較

根據領域專家的意見，參考不同的關系強度，經過實驗取式(4)不同關系的權值如下：同義關系=0，依賴關系=1，參考關系=1.5，兄弟關系=2，平行關系=2.5，蘊含關系=無窮大；式(5)不同關系的權值如下：同義關系=1，依賴關系=0.9，蘊含關系=0.8，參考關系=0.7，兄弟關系=0.6，平行關系=0.5。經過實驗，式(3)的調節(jié)因子取α=0.7、β=0.1、λ=0.2時效果較好，式(4)的調節(jié)因子取α=0.2、β=0.05、γ=0.15Z、λ=0.6時效果較好，式(1)的調節(jié)因子取α=1。

從表1可以看出，式(1)的算法只是單純地根據概念節(jié)點在本體樹中的位置計算的相似度，對具體的知識點概念沒有明顯的區(qū)分。式(3)和式(4)的算法都極大地改進了原算法，都可以對不同知識點進行區(qū)分。圖5直觀地顯示了式(3)算法和式(4)算法的結果與專家經驗的比較。式(4)是式(3)的改進和簡化，式(4)算法的結果與專家經驗更加符合，并且計算復雜性更低，盡管式(4)對于同義詞的相似度計算結果有些偏差，但對查詢結果的影響可以忽略，所以本文采用式(4)進行知識點的語義相似度計算。

圖5　相似度結果比較圖

為驗證算法的實效性，用本文介紹的查詢方法與傳統(tǒng)的關鍵字查詢對200個文本、動畫、試卷、課件和視頻等教學資源從查全率和查準率兩個方面做了比較，根據四個常用知識點進行查詢，得到的查詢結果對比如表2所示，相似度計算的閾值分別取0.55、0.6和0.65。

表2　查詢結果比較

4　結　語

本文綜合考慮節(jié)點密度、節(jié)點深度以及不同關系類型對語義相似度和語義相關度的影響，改進了傳統(tǒng)的語義相似度計算公式，提出了一種新的語義相關度算法；并將其應用到教學資源本體，通過實驗比對原始的相似度算法和改進語義相關度算法的結果，驗證了算法的實效性和優(yōu)越性；最后在算法的基礎上比較了基于本文算法的教學資源領域本體語義查詢和傳統(tǒng)關鍵字查詢的查全率和查準率。但是本文算法忽略了關系傳遞和疊加對語義相似度和相關度的影響，關系傳遞會降低概念間的相似度和相關度，關系疊加會增加概念間的相似度和相關度，下一步改進方向將從這兩個方面對知識點概念的相似度和相關度進行進一步的區(qū)分。

[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].現(xiàn)代電子技術,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);遼寧省教育科學“十二五”規(guī)劃立項課題(JG13DB077)。馮瑤，碩士生，主研領域：人工智能，語義網。馮錫煒，教授。

TP391

A

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