王朕，陸能枝

（上海海事大學信息工程學院，上?！?01306）

基于樹狀結構的語義相似度算法改進

王朕，陸能枝

（上海海事大學信息工程學院，上海201306）

0　引言

概念相似度在信息檢索、信息抽取、機器翻譯、詞義排歧、文本聚類、文本映射等方面都有著廣泛的應用，因其突破了傳統信息檢索思想的束縛，對信息進行語義匹配［1］。在大數據背景下，語義檢索在各類電子商務平臺的應用也愈加廣泛，避免出現“信息孤島”［2］。語義檢索對用戶輸入的信息進行語義分析、推理和擴展，并形成擴展后的語義查詢，最終獲得相應的信息反饋。在上述過程中需要進行語義相似度計算，來提高信息查詢的準確率。本文在分析傳統語義相似度計算方法的基礎上，進行了改進，并驗證了該算法的有效性。

1　基本概念

本體（Ontology）是一個五元組的結構O=｛C，R，Hc，Rel，Ao｝。其中C指概念的集合，R指關系的集合，Hc指概念間的分類關系，Rel指概念間的非分類關系，Ao指本體公理。

如果兩個實體概念所擁有的相同屬性越多，則說明它們的語義相似度越高，同樣對于兩個概念的某一個相同屬性，如果其擁有越多的相同屬性值，其語義相似度也越高。

對于兩個實體元素A，B，用sim（A，B）表示，之間的語義相似度，形式上，語義相似度計算應滿足［7］：

（1）語義相似度的值為［0，1］區(qū)間中的某個實數，即sim（A，B）∈［0，1］；

（2）如果兩個概念是完全相似的，則語義相似度為1，即sim（A，B）=1，當且僅當A=B；

（3）如果兩個概念沒有任何共同特征，那么語義相似度為0，即sim（A，B）=0；

（4）相似關系式對稱的，即sim（A，B）=sim（B，A）。

2　傳統的語義相似度計算模型

概念結點間的距離與語義相似度具有很大的關系，在本體中，兩個概念結點之間的語義距離越大，它們之間的相似度就越低；相反，兩個概念結點之間的語義距離越小，它們之間的相似度就越大。假設兩個概念結點為A，B。sim（A，B）表示兩個概念結點之間的相似度，sim（A，B）為0表示兩個概念結點不相似；為1表示兩個概念結點完全相似，因此，0≤sim（A，B）≤1。dis（A，B）表示兩個概念結點之間的距離。由于兩個結點之間的距離與它們的相似度存在反比關系，所以可得到下列公式。其中，為調節(jié)因子。

概念深度是指概念結點在樹狀結構中所在的層數，即與根節(jié)點最短路徑所包含的邊數。在樹狀結構中，每一層的概念都是上一層的細化，即概念結點所在層數越大，它的概念就越詳細。所以，深度較深處的概念結點之間的相似度比層數較低的結點之間的相似度大。也就是說，兩個概念結點的深度之和與概念之間的相似度成正比。而兩個概念結點之間層數相差越大，它們之間細化程度的差異越大，則概念結點之間的相似度越小。根據上述可得到以下公式［3］。

其中，depth（i）表示結點所在深度。depth（i）=depth （parent（i））+1。假設根節(jié)點的深度為1，且depth（parent （i））是的父節(jié)點的深度。

結點密度是指概念結點所擁有的兄弟結點的個數。某個結點的分類越細，密度越大，該結點分類越具體，它的直接孩子之間的語義距離越小，相似度就越大。所以兩個結點的共同祖先結點的孩子結點越多，它們之間的相似度就越大。因此得到如下公式。

其中wid（B）表示結點i的兄弟結點的個數。LCN表示最小公共結點（Least Common Node）。

（1）語義重合度是指兩個概念結點所具有的相同概念的個數。表示概念在其祖先結點上的相似程度，如果兩個概念結點所具有的相同的信息越多，它們之間的重合度就越大，語義相似度也越大，反之亦然［4］。從而得到如下公式。

由于年輕時對事業(yè)的追求和奮斗，當人們進入中老年時期后，身體各方面機能都在逐漸衰退，骨骼逐漸僵硬、靈活性差。人們可能剛從忙碌、快節(jié)奏的生活中解放出來，此時打亂了身體機能的運行規(guī)律和節(jié)奏，不利于身體健康，進而誘發(fā)中老年人的消極情緒。而舞蹈的出現，則能驅散中老年人的消極、負面情緒，有益身心，通過運動排汗的形式鍛煉身體，提高身體的靈活性，還能消磨中老年人的無聊時光，養(yǎng)成積極、樂觀的心態(tài)。

其中，U（i）表示結點到根節(jié)點所有結點的集合。

（2）還有一種方法是，在實際中兩個結點不同的概念越多說明它們之間的相似度越小，所以兩個結點不同概念與其相似度成反比［5］。所以有如下公式。

3　改進的語義相似度計算算法

公式（3）具有的缺點：在有些極端情況可能出現simdensity（A，B）＞1的情況。不符合上面所提到的語義相似度的條件。

例如，在如圖1中，節(jié)點w12和w13中l(wèi)ogwid （w12）和logwid（w13）都為0，所以，相似度就是無窮大，因此不符合0≤sim（A，B）≤1。

因此，為了避免上述問題，本文將計算方法改為如下公式所示。

其中，wid（T）=max（wid（i）），表示在此樹中寬度最大的結點的寬度，即兄弟節(jié)點個數。利用本文的此方法可得，處于區(qū)間［0，1］，計算結果符合條件。w12和w13的相似度計算結果為simdensity（w12，w13）=0.625。

圖1　一個樹狀圖例

在公式（4）中，缺點是|U（A）∩U（B）|相同的情況下，無論它們屬于哪一層，結果都是一樣的，這是不符合常理的。

（2）在公式（5）中也體現出問題。針對圖1，每個概念結點之間的相似度計算結果如下表格1所示。

然而在這個計算方法中，

這明顯不符合常理，也就是說有比較大的誤差，實際中，應該是：

所以，現本文結合上訴兩種情況的公式得到如下公式。

而新公式得到的結果為如表2所示：

這兩個計算結果都與主觀觀點一致，符合實際。所以，在重合度相似度計算算法中新的公式更適合實際。

表1　根據圖1使用傳統算法得到的每個結點之間的相似度

針對以上四種考慮因素：路徑距離、結點深度、結點密度、語義重合度，綜合計算得到如下公式。

其中，θ+β+γ+λ=1，是四個調節(jié)因子。

4　實驗及分析

選取文獻［8］中使用的例子如圖2，提取其樹狀結構中的一部分進行計算驗證。

選取該樹狀結構中的“4主機”概念結點來計算與該樹狀結構中其他概念結點之間的語義相似度值，假設參數值為α=3，θ=0.25，β=0.25，γ=0.25，λ=0.25，計算得到的部分結果如表3所示，在原計算方法中sim（主機，軟件）=sim（主機，系統軟件），這是不符合常理的，而在本文算法的結果是sim（主機，軟件）≠sim（主機，系統軟件），這是符合常理的，所以本文算法具有優(yōu)越性。

表2　針對圖1使用改進的算法得到的每個結點之間的相似度

5　結語

本文針對樹狀結構的本體領域，利用樹狀結構的各種特點，提出了概念之間的語義相似度計算。其中不僅考慮到路徑距離、結點深度、結點密度、語義重合度等因素，并在其中的密度和語義重合度進行了改進，還添加了一些調節(jié)因子。通過實驗證明，該算法更符合實際且更嚴謹。

表3　概念結點4（主機）與其他結點的語義相似度實驗結果比較

圖2　一個簡單的計算機樹狀結構圖

［1］安建成，武俊麗.基于語義樹的概念語義相似度計算方法研究［J］．微電子學與計算機，2011

［2］劉雙印.電子商務智能推薦系統中基于領域本體的案例檢索算法［J］．計算機應用，2010

［3］周書鋒，陳杰.基于本體的概念語義相似度計算［J］.情報雜志，2011

［4］蔣溢，丁優(yōu)，熊安萍，王化晶.一種基于知網的詞匯語義相似度改進計算方法［J］.重慶郵電大學學報，2009

［5］丁健，范太華.一種綜合的概念語義相似度計算方法［J］.電腦知識與技術，2011

［6］楊春龍，顧春華.基于概念語義相似度計算模型的信息檢索研究［J］.計算機應用與軟件，2013

［7］趙捧未，袁穎.基于領域本體的語義相似度計算方法研究［J］.科技情報開發(fā)與經濟，2010

［8］韓欣，攀永生，馬春森，楊和平.基于樹狀結構的語義相似度計算方法分析［J］.微電子學與計算機，2012

［9］李昊迪.語義相似度的混合計算方法［M］.哈爾濱工業(yè)大學，2012.

［10］張永攀，畢福偉等.電子商務個性化推薦系統的應用［J］.遼寧石油化工大學學報，2013.

Semantic Similarity；Tree Structure；Node Density；Semantic Coincidence Degree

Improvement of Semantic Similarity Algorithm Based on Tree Structure

WANG Zhen，LU Neng-zhi
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

1007-1423（2015）17-0027-04

10.3969/j.issn.1007-1423.2015.17.006

王朕（1991-），男，安徽阜陽人，碩士研究生，研究方向為電子商務與信息系統

2015-04-16

2015-05-25

在計算基于本體領域的樹狀結構的概念語義相似度時，從路徑距離、結點深度、結點密度、語義重合度等角度討論語義相似度計算方法，其中針對結點密度的影響和語義重合度的影響部分進行改進。

語義相似度；樹狀結構；節(jié)點密度；語義重合度

陸能枝（1959-），男，工學博士，研究方向為決策支持及其在港航信息工程中的應用、電子商務、地理信息及物流信息化技術等

Based on tree structure of domain ontology，discusses the traditional semantic similarity calculation method from the path distance，the density of nodes depth，concept overlap degree，and makes improvement including the node density and semantic coincidence degree.