面向教學(xué)資源查詢的語義相似度和相關(guān)度算法

馮　瑤　馮錫煒

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

?

面向教學(xué)資源查詢的語義相似度和相關(guān)度算法

馮瑤馮錫煒

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

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

語義相似度語義相關(guān)度教學(xué)資源領(lǐng)域本體

0　引　言

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

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

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

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

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

本體從層次結(jié)構(gòu)上可以看作是樹結(jié)構(gòu)。在本體樹中，節(jié)點表示概念，連接節(jié)點的邊表示概念之間的關(guān)系。本體樹中有一個節(jié)點被指定為根節(jié)點。每個節(jié)點都至少有一條通往根節(jié)點的路徑，這條路徑上的節(jié)點都是該節(jié)點的祖先節(jié)點，距離最近的直接祖先節(jié)點叫做雙親節(jié)點。對于本體樹中的兩個節(jié)點來說，它們一定共享著共同的祖先節(jié)點集合。表示最具體概念的節(jié)點一般都與兩個節(jié)點的最近共同祖先節(jié)點相關(guān)。給定兩個概念c1和c2，一個計算相似度的最常見的方法就是根據(jù)它們的本體層次計算節(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的語義相似度。

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

(1)

2　語義相似度算法的改進

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

式(1)只考慮了語義距離，沒有考慮節(jié)點間具體的關(guān)系，還有本體樹中影響相似度的其他因素。影響語義相似度的主要因素有節(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) 邊的類型

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

圖3　節(jié)點關(guān)系

2.2改進后的相似度算法

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

(2)

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

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

(3)

式中，Rel(c1,c2)表示c1、c2的語義相關(guān)度，rel(ei)表示連接兩個節(jié)點的關(guān)系邊ei的權(quán)值。γ是調(diào)節(jié)因子，為了方便計算，γ取1。

最后綜合考慮上下位關(guān)系的語義相似度和非上下位關(guān)系的語義相關(guān)度表示為：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的基于上下位關(guān)系的相似度和基于非上下位關(guān)系的相關(guān)度。

計算語義相似度和相關(guān)度的算法如下：

輸入：知識點a和知識點b；關(guān)系邊的權(quán)重Wt(ei)、rel(ei)；調(diào)節(jié)因子α、β、λ、γ。

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

Step1找到本體樹中a到b的路徑，獲取路徑中的關(guān)系邊的集合，以及最近共同祖先節(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根據(jù)本體樹中節(jié)點a和b之間的蘊含(屬于)關(guān)系邊和同義關(guān)系的權(quán)值計算式(2)。

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

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

2.3進一步改進

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

(5)

3　實驗分析

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

圖4　本體樹片段

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

表1　相似度算法比較

根據(jù)領(lǐng)域?qū)＜业囊庖?，參考不同的關(guān)系強度，經(jīng)過實驗取式(4)不同關(guān)系的權(quán)值如下：同義關(guān)系=0，依賴關(guān)系=1，參考關(guān)系=1.5，兄弟關(guān)系=2，平行關(guān)系=2.5，蘊含關(guān)系=無窮大；式(5)不同關(guān)系的權(quán)值如下：同義關(guān)系=1，依賴關(guān)系=0.9，蘊含關(guān)系=0.8，參考關(guān)系=0.7，兄弟關(guān)系=0.6，平行關(guān)系=0.5。經(jīng)過實驗，式(3)的調(diào)節(jié)因子取α=0.7、β=0.1、λ=0.2時效果較好，式(4)的調(diào)節(jié)因子取α=0.2、β=0.05、γ=0.15Z、λ=0.6時效果較好，式(1)的調(diào)節(jié)因子取α=1。

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

圖5　相似度結(jié)果比較圖

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

表2　查詢結(jié)果比較

4　結(jié)　語

本文綜合考慮節(jié)點密度、節(jié)點深度以及不同關(guān)系類型對語義相似度和語義相關(guān)度的影響，改進了傳統(tǒng)的語義相似度計算公式，提出了一種新的語義相關(guān)度算法；并將其應(yīng)用到教學(xué)資源本體，通過實驗比對原始的相似度算法和改進語義相關(guān)度算法的結(jié)果，驗證了算法的實效性和優(yōu)越性；最后在算法的基礎(chǔ)上比較了基于本文算法的教學(xué)資源領(lǐng)域本體語義查詢和傳統(tǒng)關(guān)鍵字查詢的查全率和查準率。但是本文算法忽略了關(guān)系傳遞和疊加對語義相似度和相關(guān)度的影響，關(guān)系傳遞會降低概念間的相似度和相關(guān)度，關(guān)系疊加會增加概念間的相似度和相關(guān)度，下一步改進方向?qū)倪@兩個方面對知識點概念的相似度和相關(guān)度進行進一步的區(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] 劉宏哲,須德.基于本體的語義相似度和相關(guān)度計算研究綜述[J].計算機科學(xué)，2012,39(2):8-13.

[4] 劉群,李素建.基于《知網(wǎng)》的詞匯語義相似度計算[J].中文計算語言學(xué),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] 崔巍.網(wǎng)絡(luò)學(xué)習(xí)與知識表示[J].現(xiàn)代電子技術(shù),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。遼寧省普通高等學(xué)校本科教育科學(xué)改革研究項目(UPRP20140914);遼寧省教育科學(xué)“十二五”規(guī)劃立項課題(JG13DB077)。馮瑤，碩士生，主研領(lǐng)域：人工智能，語義網(wǎng)。馮錫煒，教授。

TP391

A

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