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

馮　瑤　馮錫煒

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

?

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

馮瑤馮錫煒

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

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

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

0　引　言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

2　語義相似度算法的改進(jìn)

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

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

(1) 本體樹的密度

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

圖1　本體樹的密度

(2) 節(jié)點(diǎn)的深度

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

圖2　節(jié)點(diǎn)深度

(3) 邊的類型

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

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

2.2改進(jìn)后的相似度算法

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

(2)

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

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

(3)

式中，Rel(c1,c2)表示c1、c2的語義相關(guān)度，rel(ei)表示連接兩個(gè)節(jié)點(diǎn)的關(guān)系邊ei的權(quán)值。γ是調(diào)節(jié)因子，為了方便計(jì)算，γ取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表示知識(shí)點(diǎn)，Sim(c1,c2)和Rel(c1,c2)分別表示知識(shí)點(diǎn)c1和知識(shí)點(diǎn)c2的基于上下位關(guān)系的相似度和基于非上下位關(guān)系的相關(guān)度。

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

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

輸出：知識(shí)點(diǎn)a和b的相似度的值。

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

Step2根據(jù)本體樹中節(jié)點(diǎn)a和b之間的蘊(yùn)含(屬于)關(guān)系邊和同義關(guān)系的權(quán)值計(jì)算式(2)。

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

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

2.3進(jìn)一步改進(jìn)

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

(5)

3　實(shí)驗(yàn)分析

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

圖4　本體樹片段

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

表1　相似度算法比較

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

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

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

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

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

4　結(jié)　語

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

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

TP391

A

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