基于樹(shù)狀結(jié)構(gòu)的語(yǔ)義相似度算法改進(jìn)

王朕，陸能枝

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

基于樹(shù)狀結(jié)構(gòu)的語(yǔ)義相似度算法改進(jìn)

王朕，陸能枝

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0　引言

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

1　基本概念

本體（Ontology）是一個(gè)五元組的結(jié)構(gòu)O=｛C，R，Hc，Rel，Ao｝。其中C指概念的集合，R指關(guān)系的集合，Hc指概念間的分類關(guān)系，Rel指概念間的非分類關(guān)系，Ao指本體公理。

如果兩個(gè)實(shí)體概念所擁有的相同屬性越多，則說(shuō)明它們的語(yǔ)義相似度越高，同樣對(duì)于兩個(gè)概念的某一個(gè)相同屬性，如果其擁有越多的相同屬性值，其語(yǔ)義相似度也越高。

對(duì)于兩個(gè)實(shí)體元素A，B，用sim（A，B）表示，之間的語(yǔ)義相似度，形式上，語(yǔ)義相似度計(jì)算應(yīng)滿足［7］：

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

（2）如果兩個(gè)概念是完全相似的，則語(yǔ)義相似度為1，即sim（A，B）=1，當(dāng)且僅當(dāng)A=B；

（3）如果兩個(gè)概念沒(méi)有任何共同特征，那么語(yǔ)義相似度為0，即sim（A，B）=0；

（4）相似關(guān)系式對(duì)稱的，即sim（A，B）=sim（B，A）。

2　傳統(tǒng)的語(yǔ)義相似度計(jì)算模型

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

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

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

結(jié)點(diǎn)密度是指概念結(jié)點(diǎn)所擁有的兄弟結(jié)點(diǎn)的個(gè)數(shù)。某個(gè)結(jié)點(diǎn)的分類越細(xì)，密度越大，該結(jié)點(diǎn)分類越具體，它的直接孩子之間的語(yǔ)義距離越小，相似度就越大。所以兩個(gè)結(jié)點(diǎn)的共同祖先結(jié)點(diǎn)的孩子結(jié)點(diǎn)越多，它們之間的相似度就越大。因此得到如下公式。

其中wid（B）表示結(jié)點(diǎn)i的兄弟結(jié)點(diǎn)的個(gè)數(shù)。LCN表示最小公共結(jié)點(diǎn)（Least Common Node）。

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

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

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

（2）還有一種方法是，在實(shí)際中兩個(gè)結(jié)點(diǎn)不同的概念越多說(shuō)明它們之間的相似度越小，所以兩個(gè)結(jié)點(diǎn)不同概念與其相似度成反比［5］。所以有如下公式。

3　改進(jìn)的語(yǔ)義相似度計(jì)算算法

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

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

因此，為了避免上述問(wèn)題，本文將計(jì)算方法改為如下公式所示。

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

圖1　一個(gè)樹(shù)狀圖例

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

（2）在公式（5）中也體現(xiàn)出問(wèn)題。針對(duì)圖1，每個(gè)概念結(jié)點(diǎn)之間的相似度計(jì)算結(jié)果如下表格1所示。

然而在這個(gè)計(jì)算方法中，

這明顯不符合常理，也就是說(shuō)有比較大的誤差，實(shí)際中，應(yīng)該是：

所以，現(xiàn)本文結(jié)合上訴兩種情況的公式得到如下公式。

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

這兩個(gè)計(jì)算結(jié)果都與主觀觀點(diǎn)一致，符合實(shí)際。所以，在重合度相似度計(jì)算算法中新的公式更適合實(shí)際。

表1　根據(jù)圖1使用傳統(tǒng)算法得到的每個(gè)結(jié)點(diǎn)之間的相似度

針對(duì)以上四種考慮因素：路徑距離、結(jié)點(diǎn)深度、結(jié)點(diǎn)密度、語(yǔ)義重合度，綜合計(jì)算得到如下公式。

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

4　實(shí)驗(yàn)及分析

選取文獻(xiàn)［8］中使用的例子如圖2，提取其樹(shù)狀結(jié)構(gòu)中的一部分進(jìn)行計(jì)算驗(yàn)證。

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

表2　針對(duì)圖1使用改進(jìn)的算法得到的每個(gè)結(jié)點(diǎn)之間的相似度

5　結(jié)語(yǔ)

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

表3　概念結(jié)點(diǎn)4（主機(jī)）與其他結(jié)點(diǎn)的語(yǔ)義相似度實(shí)驗(yàn)結(jié)果比較

圖2　一個(gè)簡(jiǎn)單的計(jì)算機(jī)樹(shù)狀結(jié)構(gòu)圖

［1］安建成，武俊麗.基于語(yǔ)義樹(shù)的概念語(yǔ)義相似度計(jì)算方法研究［J］．微電子學(xué)與計(jì)算機(jī)，2011

［2］劉雙印.電子商務(wù)智能推薦系統(tǒng)中基于領(lǐng)域本體的案例檢索算法［J］．計(jì)算機(jī)應(yīng)用，2010

［3］周書(shū)鋒，陳杰.基于本體的概念語(yǔ)義相似度計(jì)算［J］.情報(bào)雜志，2011

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

［5］丁健，范太華.一種綜合的概念語(yǔ)義相似度計(jì)算方法［J］.電腦知識(shí)與技術(shù)，2011

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

［7］趙捧未，袁穎.基于領(lǐng)域本體的語(yǔ)義相似度計(jì)算方法研究［J］.科技情報(bào)開(kāi)發(fā)與經(jīng)濟(jì)，2010

［8］韓欣，攀永生，馬春森，楊和平.基于樹(shù)狀結(jié)構(gòu)的語(yǔ)義相似度計(jì)算方法分析［J］.微電子學(xué)與計(jì)算機(jī)，2012

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

［10］張永攀，畢福偉等.電子商務(wù)個(gè)性化推薦系統(tǒng)的應(yīng)用［J］.遼寧石油化工大學(xué)學(xué)報(bào)，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-），男，安徽阜陽(yáng)人，碩士研究生，研究方向?yàn)殡娮由虅?wù)與信息系統(tǒng)

2015-04-16

2015-05-25

在計(jì)算基于本體領(lǐng)域的樹(shù)狀結(jié)構(gòu)的概念語(yǔ)義相似度時(shí)，從路徑距離、結(jié)點(diǎn)深度、結(jié)點(diǎn)密度、語(yǔ)義重合度等角度討論語(yǔ)義相似度計(jì)算方法，其中針對(duì)結(jié)點(diǎn)密度的影響和語(yǔ)義重合度的影響部分進(jìn)行改進(jìn)。

語(yǔ)義相似度；樹(shù)狀結(jié)構(gòu)；節(jié)點(diǎn)密度；語(yǔ)義重合度

陸能枝（1959-），男，工學(xué)博士，研究方向?yàn)闆Q策支持及其在港航信息工程中的應(yīng)用、電子商務(wù)、地理信息及物流信息化技術(shù)等

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.