梁少星

（武漢大學信息管理學院，湖北武漢430072）

基于語義關聯的實例相似度計算方法及應用研究

梁少星

（武漢大學信息管理學院，湖北武漢430072）

〔摘 要〕相似度計算方法的優(yōu)劣直接影響到信息檢索與推薦的效果。本文根據本體圖模型中屬性序列的特點，綜合考慮層次關系和屬性關系，在分析路徑關聯相似度、層次相交關聯相似度及屬性相交關聯相似度的影響因素的基礎上給出了實例之間綜合語義相似度的計算方法。文章最后討論了該相似度計算方法在解決基于內容的推薦中的過于專門化問題、協(xié)同過濾推薦中的稀疏性問題以及檢索中查全率和查準率問題中的應用。

〔關鍵詞〕語義關聯；相似度計算；本體；屬性序列

相似度計算是知識檢索和知識推薦的基礎及關鍵技術，其計算方法與資源和用戶的建模及表示方式有關。本體建模由于其良好的概念層次結構、對邏輯推理的支持以及對知識的共享和復用，已成為主流的方法。

當前基于本體的相似度計算存在兩大問題：

（1）為簡化本體構建和相似度計算，較多考慮本體中的層次關系，忽略屬性關系，影響了相似度計算的準確性。文獻［1］計算相似度只考慮層次關系，忽略了屬性關系，丟失了很多語義描述。文獻［2-4］引入屬性關系計算綜合語義相似度，但考慮的屬性關系過于簡單，不具有普適性。

（2）側重概念相似度計算的研究，較少有實例相似度計算的研究。計算概念相似度的目的在于可以將信息資源（如文本、網頁等）特征表示為概念的集合，然后借助概念相似度計算信息資源的相似度。但在實例作為信息資源特征表示對象的應用中，需要計算實例相似度。文獻［5］分析了實例相似度的影響因素，但受應用的限制，對實例相似度影響因素的分析不夠全面。

本文分析了實例之間的層次關系和屬性關系對相似度計算的影響，討論了實例之間基于語義關聯的相似度計算方法，并介紹了該計算方法在信息推薦和信息檢索中的應用，期望改善內容推薦中的專門化問題、協(xié)同過濾推薦中的稀疏性問題以及檢索中查全率和查準率不高的問題。

1　研究背景

1.1本體模型的構建

本體是共享概念模型的明確的形式化規(guī)范說明［6］，可以理解和表達為一組概念的定義及其相互關系?？梢詫⒈倔w形式化表示為：O＝｛C，I，RH，RP，A｝，其中C指概念，也稱為類；I指實例，即類的具體實體；RH指概念或實例之間的層次關系（Hierarchy Relationship），包括概念之間的SubclassOf關系和概念與實例之間的InstanceOf關系；RP指概念之間或實例之間的屬性關系（Property Relationship），是由用戶自定義的對象屬性，加強了人類的認知；A指公理。

本體模型構建一般考慮的是層次關系，表現為本體的樹形結構。如若同時考慮層次關系和屬性關系，則表現為更為復雜的圖形結構。為簡單說明，使用斯坦福大學開發(fā)的protégé4.3構建Movie本體。protégé4.3中的OntoGraf插件可以將Movie本體中的類、實例及關系以圖形的形式更清楚地呈現出來。在OntoGraf中，本體表示為由節(jié)點和邊組成的有向圖，節(jié)點表示概念或實例，邊表示屬性。僅考慮層次屬性RH時，本體表現為樹形結構（圖1），綜合考慮層次屬性RH和對象屬性RP時，本體表現為圖形結構（圖2）。

圖1　僅考慮層次屬性的Movie本體

圖2　綜合考慮層次屬性和對象屬性的Movie本體

1.2屬性序列

文獻［7］首次提出屬性序列的概念，但在屬性序列的定義中僅考慮屬性關系RP。本文根據實例相似度計算的需要，綜合考慮層次屬性RH和對象屬性RP，重新對屬性序列進行定義。

定義1在有向本體圖模型中，如果存在n個屬性p1，p2，……，pn將n+1個節(jié)點a1，a2，……，an+1連接起來（如圖3所示），其中pi（1≤i≤n）∈RH∪RP，ai（1≤i≤n+1）∈C∪I，則稱該有限屬性集合為屬性序列（Property Sequences，PS），形式化表示為：ps＝｛p1，p2，……，pn｝。屬性序列的長度（length）即ps中屬性的個數。

圖3　屬性序列示例圖

定義2函數NodesOfPS（）返回屬性序列中屬性所連接的所有節(jié)點，即NodesOfPS（ps）＝｛a1，a2，……，an+1｝。節(jié)點a1稱為屬性序列的起點（origin），節(jié)點an+1稱為屬性序列的終點（terminus）。

定義3如果屬性序列ps1和ps2滿足NodesOfPS（ps1）∩NodesOfPS（ps2）≠?，則稱兩個屬性序列相交（Joined Property Sequence），ai∈（NodesOfPS（ps1）∩NodesOfPS（ps2））稱為相交節(jié)點（join node）。

1.3語義關聯

本體圖模型中，如果兩個實例間存在連通路徑，則稱兩個實例存在語義關聯（Semantic Association，記為SA）。文獻［7-9］將節(jié)點之間的語義關聯分為路徑關聯和相交關聯，但因其對屬性序列定義的局限性，沒有考慮層次屬性RH對語義關聯的影響，在應用上有局限性。

本文在定義1基礎上，分析了實例間連通路徑所包含的屬性序列的特點，將實例之間的語義關聯分為路徑關聯、層次相交關聯、屬性相交關聯3類，其定義分別如下：

定義4存在一條屬性序列ps，如果實例x和y分別是ps的起點和終點，且該屬性序列中所有屬性pi∈Rp，則稱x、y之間存在路徑關聯（Path Association，記為PA）。

圖4　路徑關聯

如果x和y之間存在路徑關聯，則x和y之間路徑關聯的長度等于屬性序列的長度，即length（PA（x，y））＝length（ps）。

定義5存在兩條屬性序列ps1和ps2相交，如果實例x和y同為ps1和ps2的起點或同為終點，且ps1和ps2中的所有屬性pi∈RH，即實例x和y屬于同一個類或相似類，則稱x、y之間存在層次相交關聯（Hierarchy Join Association，記為HJA）。

根據層次相交關聯中實例x和y所屬的類Cx和Cy是否相同，將層次相交關聯分為兩種情況：

（1）若Cx和Cy相同，即實例x和y為同一個類的實例，則ps1和ps2的相交節(jié)點為C（C＝Cx＝Cy），如圖5（a）所示；

（2）若Cx和Cy不同，即實例x和y為相似類的實例，則ps1和ps2的相交節(jié)點為C（C≠Cx≠Cy），如圖5（b）所示。

圖5　層次相交關聯

如果x和y之間存在層次相交關聯，則層次相交關聯的長度等于它所包含的2個屬性序列的長度之和，即length（HJA（x，y））＝length（ps1）+length（ps2）。

定義6存在兩條屬性序列ps1和ps2相交，如果x和y同為ps1和ps2的起點或同為終點，且ps1和ps2中屬性p1∈RP，pi∈RH∪RP（2≤i≤n），即實例x和y具有共同或相似的屬性，則稱x、y之間存在屬性相交關聯（Property Join Association，記為PJA）。

根據屬性相交關聯中屬性序列特點及相交節(jié)點的類型，將屬性相交關聯分為3種情況：

（1）實例x和y通過一個屬性相交于實例I（Join Instance），此時實例x和y有共同屬性，如圖6（a）所示；

（2）實例x和y通過多個屬性相交于實例I（Join Instance），此時實例x和y有相似屬性a1和a2，如圖6（b）所示；

（3）實例x和y通過多個屬性相交于類C（Join Class），與第二種情況類似，此時實例x和y的屬性實例a1和a2仍為相似屬性，如圖6（c）所示。

圖6　屬性相交關聯

如果x和y之間存在屬性相交關聯，則屬性相交關聯的長度等于所包含的2個屬性序列的長度之和，即length

（PJA（x，y））＝length（ps1）+length（ps2）。

2　基于語義關聯的實例相似度計算方法

本體優(yōu)勢在于其圖形結構，圖模型中節(jié)點之間的連通路徑體現了節(jié)點之間的相似性。文獻［10-11］將基于本體的語義相似度計算方法分為4類：基于距離的方法、基于內容的方法、基于屬性的方法以及混合式方法，其中混合式語義相似度計算方法是對前面3種方法的綜合考慮。本文采用混合式計算方法，綜合考慮本體中的層次關系和屬性關系，從語義關聯的角度，分析實例之間的路徑關聯相似度、層次相交關聯相似度和屬性相交關聯相似度的影響因素及算法，并對其進行綜合。

2.1路徑關聯相似度的影響因素及算法

實例x和y之間可能存在多條路徑關聯，假設存在n條路徑關聯（如圖7所示），第i條（1≤i≤n）路徑關聯的長度為length（PAi（x，y））。通過對圖7進行分析，可知x和y之間路徑關聯相似度與以下因素有關：

圖7　實例x和y之間的路徑關聯

（1）最短路徑關聯的長度min（length（PAi（x，y）））。實例x和y之間的最短路徑關聯越短，它們之間的中間結點越少，相似度也越大。

因此，實例x和y之間的路徑關聯相似度可以表示為：

公式（1）中a為可調節(jié)參數。

2.2層次相交關聯相似度的影響因素及算法

層次相交關聯是兩個實例因存在共同祖先而產生的關聯，層次相交關聯側重層次關系，體現實例之間的層次相似性。

一個實例可能屬于多個類，即實例存在多重繼承關系，實例多重繼承導致實例x和y之間可能存在多條層次相交關聯。假設存在n條層次相交關聯且相交類為實例x和y的最近共同祖先（Lowest Common Ancestor，LCA）（如圖8所示），depth（x）和depth（y）分別表示實例x和y的深度，實例深度等于實例所屬類在本體樹中的深度，depth（LCAi）為第i條層次相交關聯中相交節(jié)點的深度，其中depth（LCA）＝depth（LCA1）＝depth（LCA2）＝……＝depth（LCAn）。通過對圖8進行分析，可知x和y之間的層次相交關聯相似度與以下因素有關：

（1）相交節(jié)點即最近共同祖先的深度depth（LCA）。最近共同祖先越深，實例x和y越具體，層次相交關聯相似度越大。

（2）層次相交關聯所在分支的最大深度max（depth（x），depth（y））。分支的最大深度越深，節(jié)點離共同祖先距離越遠，節(jié)點之間的層次相交關聯相似度越小。

因此，實例x和y之間的層次相交關聯相似度可以表示為：

如果LCA為根節(jié)點，則層次相交關聯相似度為0。

如果實例x和y屬于同一個類（如圖5（a）所示），則層次相交關聯相似度為1，因為depth（LCAi）＝depth（x）＝depth（y）。

圖8　實例x和y之間的層次相交關聯

2.3屬性相交關聯相似度的影響因素及算法

屬性相交關聯是兩個實例因存在共同屬性或相似屬性而產生的關聯，屬性關聯側重用戶自定義對象屬性關系，體現實例之間的屬性相似性，如兩部電影有同樣的演員或相似的主題。

假設實例x和y之間存在n條屬性相交關聯（如圖9所示），第i條路徑相交關聯的長度為length（PJAi），實例x和y的屬性個數為m。通過對圖9進行分析，可知x和y之間屬性相交關聯相似度與以下因素有關：

圖9　實例x和y之間的屬性相交關聯

（1）屬性相交關聯條數n。屬性相交關聯越多，說明兩個實例相同或相似的屬性值越多，兩個實例越相似。

（2）語義關聯長度length（PJAi）。語義關聯長度越長，說明兩個實例相隔的路徑越長，相似度越小。

因此，實例x和y之間的屬性相交關聯相似度可以表示為：

公式（3）中b為可調節(jié)參數。

2.4基于語義關聯的綜合語義相似度算法

兩個實例之間可能存在多種語義關聯，設路徑關聯相似度的權重為α（0≤α≤1），層次相交關聯相似度的權重為β（0≤β≤1），屬性相交關聯相似度的權重為γ（0≤γ≤1），且α+β+γ＝1，則本體中任意兩個實例x和y的綜合語義相似度為：

3　基于語義關聯的相似度計算方法的應用

3.1在推薦領域的應用

常用的推薦方法有兩種，分別是基于內容的推薦和協(xié)同過濾推薦。下面介紹語義關聯在內容推薦和協(xié)同過濾推薦中的應用，并分析基于語義關聯的實例相似度算法如何改善內容推薦的過于專門化問題和協(xié)同過濾推薦的稀疏性問題。

3.1.1在基于內容的推薦中的應用

基于內容的推薦策略的本質是計算項目與用戶模型的相似度，向用戶推薦與用戶歷史偏好語義相似度大的項目。

傳統(tǒng)基于內容的推薦方法最大缺點在于過于專門化（Overspecialization）。受余弦相似度算法的限制，只有與用戶偏好有相同屬性的內容才會被加入最終推薦集呈現給用戶，導致推薦結果過于專門化。

基于語義關聯的方法可以提高推薦結果的多樣性，改善過于專門化問題?；谡Z義關聯的方法對過于專門化的改善體現在兩個層面：

（1）用戶偏好擴散。根據本體圖模型中的連通路徑，可以找到與用戶模型中偏好實例存在語義關聯的實例，這些實例組成一張網狀圖，從而實現了用戶偏好的擴散。文獻［5］利用擴散算法實現初始節(jié)點的繼承關聯擴散和路徑關聯擴散，發(fā)現存在內在聯系的結點，但沒有考慮實例之間的屬性相交關聯。文獻［12-13］使用擴散激活技術（Spreading Activation Technique）根據路徑關聯和相交關聯來發(fā)現與用戶偏好有隱藏聯系的結點，從而豐富最終的推薦結果集，但沒有考慮實例之間的層次相交關聯。在推薦應用中，可以根據定義4、定義5和定義6對初始節(jié)點進行全面的擴散，以發(fā)現更多與用戶偏好存在語義關聯的節(jié)點。

（2）相似度計算。根據偏好擴散后網狀圖中實例與用戶模型的語義相似度來預測用戶對該實例的興趣度，并將相似度大于閾值的實例推薦給用戶。

需要注意的是，用戶對網狀圖中某實例的興趣度不僅與該實例與用戶模型的相似度有關，而且與用戶模型中實例的興趣度有關。用戶模型中實例的興趣度越大，與該實例語義相似度大的實例的興趣度也越大。

設用戶偏好擴散后的網狀圖中某實例為x，目標用戶的用戶模型Pu＝｛（I1，D1），（I2，D2），…，（In，Dn）｝，其中Di為用戶對第i個實例（1≤i≤n）Ii的興趣度，則用戶對實例x的預測興趣度為：

通過公式（5）可知，在興趣度預測時可以綜合考慮實例之間的路徑關聯相似度、層次相交關聯相似度和屬性相交關聯相似度，不僅向用戶推薦與用戶偏好有相同屬性的項目，而且推薦與用戶偏好語義關聯的項目，最終提高推薦結果的多樣性，改善過于專門化問題。

3.1.2在協(xié)同過濾推薦中的應用

協(xié)同推薦的本質是發(fā)現與目標用戶偏好相同的鄰居用戶，將鄰居用戶喜歡的節(jié)目推薦給目標用戶，因此鄰居用戶的發(fā)現是核心。鄰居用戶的發(fā)現需要借助用戶偏好之間的相似性來計算。

傳統(tǒng)協(xié)同過濾方法的最大缺點是稀疏性問題。受到用戶相似度算法的限制，只有當用戶喜歡更多相同的項目時才表明用戶相似大，因此導致發(fā)現的鄰居用戶較少，產生了稀疏性問題，影響了推薦的質量和效率。

基于語義關聯的方法可以將項目語義相似度加入用戶相似度算法中，通過對用戶相似度算法加以修正來優(yōu)化最近鄰的形成，最終改善稀疏性問題［3］。

假設目標用戶（Target User）的用戶模型Pu＝｛（I1，DTU1），（I2，DTU2），…，（In，DTUn）｝，其中Di為用戶對實例Ii（1≤i≤n）的興趣度。目標用戶TU的用戶偏好向量可以表示為→VTU＝（DTU1，DTU2，…，DTUn），候選鄰居CN（Candidate Neighborhood）的用戶偏好向量可以表示為→VCN＝（DCN1，DCN2，…，DCNn）。

傳統(tǒng)方法通過計算目標用戶TU和候選鄰居CN之間的余弦相似性選擇最近鄰，然后將最近鄰喜歡的項目推薦給目標用戶，余弦相似度算法可以表示為：SimCos（TU，CN）

基于語義關聯的方法通過加入項目的語義相似度對用戶向量的點積加以修正，優(yōu)化最近鄰的形成，修正后的公

通過對比分析得出，基于語義關聯的相似度可以通過項目的語義相似度改善用戶相似度度量，找出更多的最近鄰，改善稀疏性問題。

3.2在檢索領域的應用

傳統(tǒng)的搜索引擎存在兩大問題：一是大都采用基于關鍵字的相似度匹配方法，由于系統(tǒng)不能理解用戶輸入的查詢信息，導致查全率和查準率不高；二是沒有對個性化的查詢需求給予重視，不同興趣的用戶使用相同的關鍵字，查詢結果完全相同。

針對問題一，基于本體的方法可以將用戶輸入關鍵詞映射為本體概念或實例，進行基于概念或實例的語義檢索，從而幫助系統(tǒng)理解用戶意圖，提高檢索質量。針對問題二，可以借助語義關聯對用戶本體模型進行語義擴展，滿足用戶的個性化需求，提高查準率。

下面從查詢詞的映射和用戶模型的語義關聯擴展兩個方面，分析語義關聯相似度如何通過提高查詢詞映射的準確率及對用戶模型進行語義擴展來提高查詢的查準率和查全率。

3.2.1在查詢詞映射中的應用

基于本體的檢索需要將用戶輸入的關鍵詞映射為本體概念或實例，進行基于概念或實例的語義檢索，但在映射過程中，由于不能確定用戶意圖，可能產生錯誤的映射。

一般來說，用戶在一次查詢中輸入多個關鍵詞代表用戶查詢意圖，因此這些關鍵詞之間存在較強的關聯。將n個查詢關鍵詞映射為本體庫中的n個實例集后，選擇語義相關度高的實例進行組合，該組合代表用戶正確查詢意圖的可能性也較大［14］。文獻［5］在選擇映射實例時，僅考慮了路徑相似度，用實例之間的最短屬性序列長度代表語義相似度，忽略了層次相交相似度和屬性相交相似度（即在公式（4）中只取α＝1，而β＝0，γ＝0），影響了查全率和查準率。在具體應用中，可以根據應用的需要，對公式4中的各個權重參數加以調整，利用語義關聯相似度提高實例映射的準確率，優(yōu)化用戶輸入，幫助搜索引擎有效推測用戶意圖，最終提高檢索的查準率。

3.2.2在用戶模型語義擴展中的應用

語義關聯可以對用戶模型進行語義擴展，從而為不同興趣的用戶提供滿足其個性化需求的搜索服務。對于用戶模型的表示，可以使用瀏覽歷史中包含的實例來表示用戶模型，如文獻［5］將用戶對網頁的偏好轉化為對本體實例的偏好，形成用戶偏好模型。

根據實例之間的語義關聯實現用戶偏好擴散，可以發(fā)現隱含的用戶偏好，并利用實例之間的語義相似度更新實例的興趣度。與基于語義關聯的內容推薦相似，假設用戶偏好擴散后的網狀圖中某實例為x，可以根據公式（5）更新實例x的興趣度，最后對檢索結果重新排序。因此，與用戶模型相結合，可以滿足用戶的個性化需求并提高查準率，利用公式（4）的語義關聯相似度對用戶模型進行語義擴展，可以提高查全率。

4　結 語

本文從屬性序列的角度分析了實例之間的路徑關聯、層次相交關聯、屬性相交關聯對語義相似度的影響，并得出了綜合語義相似度的算法。將該相似度算法應用于推薦和檢索中，可以對基于內容的推薦中的過于專門化問題、協(xié)同過濾推薦中的稀疏性問題以及檢索中查全率和查準率不高的問題加以改善。

后續(xù)工作將建立領域本體并設計對比實驗驗證所提出相似度算法的有效性，并使用定量分析驗證該算法在推薦和檢索質量改善方面的效果。

參考文獻

［1］陳沈焰，吳軍華.基于本體的概念語義相似度計算及其應用［J］.微電子學與計算機，2009，25（12）：96-99.

［2］Fernández Y B，Pazos Arias J J，Nores M L，et al.AVATAR：an improved solution for personalized TV based on semantic inference［J］. Consumer Electronics，IEEE Transactions on，2006，52（1）：223-231.

［3］Martín-Vicente M I，Gil-Solla A，ramos-Cabrer M，et al.A semantic approach to improve neighborhood formation in collaborative recommender systems［J］.Expert Systems with Applications，2014，41（17）：7776-7788.

［4］楊美榮，邵洪雨，史建鋒，等.改進的領域本體概念相似度計算模型研究［J］.情報科學，2014，32（5）：72-77.

［5］梅翔，孟祥武，陳俊亮，等.一種基于用戶偏好分析的查詢優(yōu)化方法［J］.電子與信息學報，2008，30（1）：33-37.

［6］Studer R，Benjamins V R，Fensel D.Knowledge Engineering，Principles and Methods［J］.Data and Knowledge Engineering，1998，25（1）：161-197.

［7］Anyanwu K，Sheth A.Theρoperator：discovering and ranking associations on the semantic web［J］.ACM SIGMOD Record，2002，31（4）：42-47.

［8］Anyanwu K，Sheth A.ρ-Queries：enabling querying for semantic associations on the semantic web［C］∥Proceedings of the 12th international conference on World Wide Web.ACM，2003：690-699.

［9］Blanco-Fernández Y，Pazos-Arias J J，Gil-Solla A，et al.A flexible semantic inference methodology to reason about user preferences in knowledge-based recommender systems［J］.Knowledge-Based Systems，2008，21（4）：305-320.

［10］劉宏哲，須德.基于本體的語義相似度和相關度計算研究綜述［J］.計算機科學，2012，39（2）：8-13.

［11］孫海霞，錢慶，成穎.基于本體的語義相似度計算方法研究綜述［J］.現代圖書情報技術，2010，26（1）：51-56.

［12］Blanco-Fernández Y，López-Nores M，Gil-Solla A，et al.Exploring synergies between content-based filtering and Spreading Activation techniques in knowledge-based recommender systems［J］.Information Sciences，2011，181（21）：4823-4846.

［13］徐守坤，孫德超，石林，等.基于語義推理的學習資源推薦［J］.計算機工程與設計，2014，35（4）：1496-1501.

［14］張克狀，劉友華，黃芳，等.一種面向用戶興趣的個性化語義查詢擴展方法［J］.現代圖書情報技術，2008，24（8）：48 -52.

（本文責任編輯：郭沫含）

·研究生園地·

Research on Computation Method of Instance Similarity based on Semantic Association and its Application

Liang Shaoxing
（School of Information Management，Wuhan University，Wuhan 430072，China）

〔Abstract〕The effect of information retrieval and recommendation is relative to the similarity computation method.Taking hierarchy relationships and property relationships into account，this paper analyzed the influencing factors of path association similarity，hierarchy join association similarity and property join association similarity according to the characteristics of property sequence in ontology diagram model，and then proposed a similarity computation method between instances.Finally，this paper discussed the applications of this similarity computation method in solving overspecialization problem of content-based recommendation，sparsity problem of collaborative filtering recommendation and recall ratio and precision ratio problems of information retrieval.

〔Key words〕semantic association；similarity computation；ontology；property sequence

作者簡介：梁少星（1990-），女，碩士研究生，研究方向；個性化推薦。

收稿日期：2015-05-14

〔中圖分類號〕G252.2

〔文獻標識碼〕A

〔文章編號〕1008-0821（2015）08-0151-06

DOI：10.3969／j.issn.1008-0821.2015.08.030