張滬寅，溫春艷，劉道波，葉 剛

（武漢大學 計算機學院，湖北 武漢430072）

0 引 言

詞語相似度計算在信息檢索、數(shù)據(jù)挖掘、機器翻譯、個性化推薦等領域有廣泛的應用，因此提高相似度計算結果的準確性顯得尤為重要。隨著領域本體的不斷普及，以及本體樹對概念節(jié)點之間關系的準確描述，本體已經(jīng)成為語義相似度研究的基礎。當前基于本體的語義相似度的研究主要有：提高相似度計算結果準確性、解決本體樹中節(jié)點的多繼承問題、解決節(jié)點對之間的不對稱性問題等。本文算法通過改進相似度計算模型，在提高相似度準確度的同時解決各類多繼承問題。

1 研究現(xiàn)狀

當前基于本體的相似度計算主要分為基于語義距離、基于信息內(nèi)容、基于屬性、混合式相似度計算［1］。基于語義距離的方法［2］是最早采用的本體相似度計算方法，Shortest Path法［3］是該類的典型算法，通過概念詞在本體樹中的路徑長度來量化概念節(jié)點之間的語義距離。Weighted Links法［4］對Shortest Path法進行了改進，對概念節(jié)點的邊進行了權值分配?；谡Z義距離的方法隨著不斷改進，已發(fā)展為基于本體結構的相似度算法［5］。基于信息內(nèi)容的方法［1］是用概念共同父節(jié)點的信息量來衡量二者的相似度，節(jié)點的信息量用節(jié)點包含內(nèi)容在本體中出現(xiàn)的頻率p來衡量。Resnik［6］對基于信息量算法進行改進，采用最小p衡量節(jié)點信息量。用父節(jié)點包含的信息量來衡量兩個節(jié)點的相似度，但并未考慮節(jié)點本身所包含的信息量?；趯傩缘南嗨贫扔嬎悖?］是用兩個節(jié)點的公共屬性個數(shù)來衡量節(jié)點相似度?；旌鲜较嗨贫扔嬎悖?－10］是目前比較常用的相似度算法，綜合考慮語義距離、信息量和概念屬性計算相似度。

文獻 ［11］同時考慮加權語義距離和概念的屬性，文獻 ［12］在文獻 ［11］的基礎上考慮了語義相關度，同時語義距離加入了反向因子。文獻 ［13］提出了基于共享路徑的方法，同時考慮了LCA 節(jié)點深度，一定程度上解決了多繼承的問題，算法并未考慮節(jié)點本身的信息，使得計算結果的準確性有待提高。

2 改進的相似度計算

本文的PRSSC算法是在基于信息內(nèi)容的相似度計算方法的基礎上，綜合考慮概念節(jié)點的密度、自身深度，LCA節(jié)點深度以及概念的屬性。PRSSC 算法描述如下：①采用概念間共享路徑重合度的方法計算相似度，并對其進行改進，在考慮節(jié)點多繼承共同父節(jié)點的同時，引入共同子節(jié)點因素；②考慮概念節(jié)點的密度，用節(jié)點寬度與本體樹的最大出度的比值計算相似度；③考慮概念節(jié)點本身在本體樹中的深度，并對其進行改進，加入LCA 節(jié)點深度因素；④考慮概念屬性的影響，用節(jié)點屬性的相似度衡量節(jié)點間的相似度；⑤通過參考其它已有研究進行權值分配，綜合加權上述4個因素的算法公式，得到本文的PRSSC算法。

2.1 基本定義

本體 （ontology）是由概念組成的高級描述，是表述特殊知識領域的形式化語言。一個本體由有限個數(shù)的概念以及概念之間的關系組成。本文中本體用有向無環(huán)圖表示，記為G＝ （V，E），圖中節(jié)點表示本體的概念，節(jié)點間的有向邊表示概念間的關系。

詞語之間的關系分為語義相關度和語義相似度。語義相似度是指兩個詞語之間在語義上的相似程度，如紅酒和白酒。語義相關度是指詞語之間的關聯(lián)程度，如Microsoft和Internet。由于語義的相關度沒有普遍性，我們通常研究概念的語義相似度。概念M1，M2的語義相似度定義為Sim（M1，M2），對Sim（M1，M2）的值做如下定義：

（1）是 ［0，1］之間的一個實數(shù)；

（2）當且僅當M1和M2為同一節(jié)點時，值為1；

（3）當M1和M2不在同一個本體樹時，值為0。

如圖1wordnet所示是本體的一個典型實例。圖中節(jié)點間都只有一個LCA 節(jié)點，不存在多繼承問題，如若在圖1中添加虛線部分，則motor vehicle和wheeled vehicle有兩個LCA 節(jié)點，從而二者相似度增大，產(chǎn)生多繼承問題。

2.2 基于信息內(nèi)容計算相似度

基于信息內(nèi)容的計算相似度方法主要是通過衡量概念所包含的信息量來計算相似度。概念是對其祖先節(jié)點的繼承，是祖先節(jié)點的又一次細化，所以可以通過祖先節(jié)點包含的信息量來衡量兩個概念的共享信息［14］。當然，祖先節(jié)點包含的信息量僅僅只能表示概念包含的相同信息，概念間的不同信息要通過計算概念本身所包含的信息量來衡量。本文采用基于共享信息重合度來計算相似度。

圖1 wordnet片段

2.2.1 共享路徑重合度

甘明鑫等［13］提出了基于共享路徑重合度的方法計算相似度。兩個概念之間共享的信息越多，則二者之間的相似度越高。反之，則二者的相似的越低。這是共享信息內(nèi)容的相似度計算方法的基本原理。概念的子圖是指概念節(jié)點與其祖先節(jié)點構成的本體部分圖。定義概念M1，M2之間的基于共享路徑重合度的相似度計算公式為

式中：re——概念節(jié)點和有向邊權重的比值，即相對權重。VM1∩M2——概念M1，M2的子圖交集所包含節(jié)點個數(shù)加權，EM1∩M2——概念M1，M2的子圖交集包含有向邊個數(shù)的加權和，VM1∪M2——概念M1，M2的子圖并集所包含節(jié)點個數(shù)加權，EM1∪M2——概念M1，M2的子圖并集包含有向邊個數(shù)的加權和。

基于共享路徑重合度計算相似度能在有效地計算相似度的前提下，解決概念多繼承的問題。當兩個概念具有相同的子節(jié)點時，二者之間的相似度應該更大，上述算法不能很好地解決這一點，針對這一問題，本文對式 （1）進行改進，將共享子節(jié)點信息也加入到共享信息中

式中：｜Vcom｜——概念M1，M2共同直接子節(jié)點的個數(shù)。

2.2.2 概念節(jié)點的密度

概念節(jié)點的密度的定義請參見文獻 ［4］。概念節(jié)點的密度越大，則其直接子節(jié)點的數(shù)目越大，節(jié)點細化的越具體，各直接子節(jié)點之間的相似性就越大，所以可以通過概念節(jié)點的LCA 節(jié)點的密度來衡量概念節(jié)點之間的相似度?；诟拍罟?jié)點密度的相似度計算算法［4］

式中：CountLca（M1，M2）——概念節(jié)點LCA 節(jié)點的直接子節(jié)點個數(shù)；Degree（Tree）——概念M1，M2的所在本體樹中各節(jié)點出度的最大值。

2.2.3 概念節(jié)點的深度

概念節(jié)點的深度是指概念在所處的本體樹中的層次深度［15］。在本體樹中，每個概念節(jié)點 （除了根節(jié)點）都是對其上一層節(jié)點的一次細化。因此概念節(jié)點處于本體樹的層次越深，則其表示的內(nèi)容就越具體，概念間的相似度越大。反之概念間的相似度越小。此處定義根節(jié)點的深度為1，概念節(jié)點M 的深度為Dep（M），Dep（M）＝Dep（parent（M））＋1，其中parent（M）為節(jié)點M 的父節(jié)點。Dep（Tree）表示本體樹的深度。胡哲等［12］的基于概念節(jié)點深度的相似度計算公式為

LCA 節(jié)點的深度越深，代表概念的分類越具體，則概念節(jié)點之間的相似度越大。反之，概念節(jié)點之間的相似度越小。對式 （4）進行改進，得到新的基于概念節(jié)點深度的相似度計算式 （5）

2.2.4 概念屬性

2.3 PRSSC算法

本文在基于共享信息相似度計算算法的基礎上進行改進，加入節(jié)點密度、深度、屬性，由式 （2）、式 （3）、式（5）、式 （6），得到PRSSC算法公式

式中：α1＋β1 ＋χ1 ＋λ1＝1。

依據(jù)文獻 ［1，12］中的權值分配情況，以及分析各影響因素對相似度的影響程度來分配權值，式 （7）中α1、β1、χ1 、λ1的取值分別為0.75、0.01、0.20、0.04。

3 實驗與分析

選用圖2所示的打印機本體實例［11］中的概念節(jié)點作為相似度計算實例。

由于數(shù)據(jù)屬性相對復雜，為了本體圖看起來簡單直觀，給出LaserJetPrinter、PresonalPrinter、HPPrinter的數(shù)據(jù)類型屬性，如下表示：

根據(jù)圖1和上述數(shù)據(jù)屬性類型屬性值，按照式 （7）計算概念間相似度，將計算結果與文獻 ［13］、文獻 ［11］和Resnik算法［6］的計算結果進行對比，見表1。

分析圖2可得， （LaserJetPrinter，HPPrinter）相較于（PresonalPrinter，HPPrinter）有相同的子節(jié)點，且有更多相似的數(shù)據(jù)類型屬性，所以二者的相似度要大于 （Presonal－Printer，HPPrinter）的相似度。PRSSC 算法得到的結果是0.4940＞0.4425，顯然PRSSC 的結果更為準確。文獻［13］算法和Resnik算法算得的二者的相似度相等，是由于二者均未考慮屬性和共同子節(jié)點的問題。

（LaserJetPrinter，PresonalPrinter）與 （PresonalPrinter，HPPrinter）共享父節(jié)點路徑相同，說明兩對節(jié)點的共有信息量相同，而HPPrinter是多繼承節(jié)點，且其HPProducts父節(jié)點到根節(jié)點這條路徑不在 （PresonalPrinter，HPPrinter）的共享父節(jié)點路徑中，因此 （LaserJetPrinter，HPPrinter）的共有信息量不變，但是私有信息量增加，顯然 （Laser－JetPrinter，PresonalPrinter）的相似度應該大于 （Presonal－Printer，HPPrinter）的相似度。文獻 ［13］算法和Resnik算法計算結果顯然不太準確。

給圖1添加LaserJetPrinter到HPProducts的虛線，使（LaserJetPrinter，HPPrinter）有兩個LCA 節(jié)點：Printer和HPProducts。PRSSC算法計算 （LaserJetPrinter，HPPrinter）的相似度結果為0.5764＞0.4940。這是由于LaserJetPrinter和HPPrinter節(jié)點多繼承，二者有兩個LCA 節(jié)點，從而導致二者共享路徑重合度增大，二者相似度增大。

根據(jù)上述三組數(shù)據(jù)對比，可以看出PRSSC 算法相較于其它幾種算法，考慮更加全面，在解決各類的多繼承問題的同時，計算結果更為準確。

圖2 打印機本體片段

表1 打印機本體實驗結果

4 結束語

本文在基于共享信息的基礎上進行改進，提出了一種新的算法模型——PRSSC算法。算法對基于共享路徑重合度進行了改進，加入了共同子節(jié)點因素影響，并引入概念節(jié)點的密度、深度和概念屬性作綜合加權計算。其中概念節(jié)點的深度不僅考慮節(jié)點自身的深度，還考慮了概念的LCA 節(jié)點的深度。實驗結果表明，PRSSC 算法計算結果相較于其它算法更加準確，而且能夠解決各類多繼承問題。本文的算法未解決概念對相似度的不對稱性，這一問題還需進一步研究。

［1］SUN Haixia，QIAN Qing，CHENG Ying.Review of ontolo－gy－based semantic similarity measuring ［J］.New Technology of Library and Information Service，2010，26 （1）：51－56 （in Chinese）.［孫海霞，錢慶，成穎.基于本體的語義相似度計算方法研究綜述 ［J］.現(xiàn)代圖書情報技術，2010，26 （1）：51－56.］

［2］YANG Fangying，JIANG Zhengxiang，ZHANG Shanshan.Semantic similarity measurement based on ontology ［J］.Computer Technology and Development，2013，23 （7）：52－56 （in Chinese）.［楊方穎，蔣正翔，張姍姍.基于本體結構的語義相似度計算［J］.計算機技術與發(fā)展，2013，23 （7）：52－56.］

［3］ZHAO Yongjin，ZHENG Hongyuan，DING Qiulin.Study on semantic similarity algorithm based on ontology ［J］.Journal of Computer Applications，2009，29 （11）：3074－3076 （in Chinese）.［趙永金，鄭洪源，丁秋林.一種基于本體的語義相似度算法研究 ［J］.計算機應用，2009，29 （11）：3074－3076.］

［4］LI Wenjie，ZHAO Yan.Semantic similarity between concepts algorithm based on ontology structure ［J］.Computer Engineering，2010，36 （23）：4－6 （in Chinese）.［李文杰，趙巖.基于本體結構的概念間語義相似度算法 ［J］.計算機工程，2010，36 （23）：4－6.］

［5］HE Yuanxiang，SHI Baoming，ZHANG Yong.Research on ontology－based semantic similarity algorithm ［J］.Computer Applications and Software，2013，30 （11）：312－315 （in Chinese）.［賀元香，史寶明，張永.基于本體的語義相似度算法研究 ［J］計算機應用與軟件，2013，30 （11）：312－315.］

［6］Resnik P.Using information content to evaluate semantic similarity in a taxonomy ［C］／／Proceedings of the 14th International Joint Conference on Artificial Intelligence，1995.

［7］LIU Hongzhe，XU De.Ontology based semilarity and relatedness measures review ［J］.Computer Science，2012，39 （2）：8－13（in Chinese）.［劉宏哲，須德.基于本體的語義相似度和相關度計算研究綜述［J］.計算機科學，2012，39 （2）：8－13.］

［8］CUI Qiwen，XIE Fu.An improved computational method for conceptual semantic similarity in domain ontology ［J］.Computer Applications and Software，2012，29 （2）：173－174 （in Chinese）.［崔其文，解福.改進的領域本體概念語義相似度計算方法［J］. 計算機應用與軟件，2012，29 （2）：173－174.］

［9］LI Wenqing，SUN Xin，ZHANG Changyou，et al.A semantic similarity measure between ontological concepts［J］.ACTA Automatica Sinica，2012，38 （2）：229－235 （in Chinese）.［李文清，孫新，張常有，等.一種本體概念的語義相似度計算方法 ［J］.自動化學報，2012，38 （2）：229－235.］

［10］DING Zhengjian，ZHANG Lu.Improved approach for ontology similarity computation ［J］.Computer Engineering，2010，36 （24）：39－41 （in Chinese）.［丁政建，張路.一種改進的本體相似度計算方法 ［J］.計算機工程，2010，36（24）：39－41.］

［11］XU Guichen，YE Feng.An improved algorithm for semantic similarity based on weighted semantic distance［J］.Journal of Intelligence，2012，31 （2）：119－123 （in Chinese）. ［徐桂臣，葉楓.基于語義加權距離的語義相似度改進算法 ［J］.情報雜志，2012，31 （2）：119－123.］

［12］HU Zhe，ZHENG Cheng.Improved concept similarity computation ［J］.Computer Engineering and Design，2010，31（5）：1121－1124 （in Chinese）.［胡哲，鄭誠.改進的概念語義相似度計算 ［J］.計算機工程與設計，2010，31 （5）：1121－1124.］

［13］GAN Mingxin，DOU Xue，WANG Daoping，et al.Comprehensive weighting method for calculation of ontologybased semantic similarity ［J］.Computer Engineering and Applications，2012，48 （17）：148－153 （in Chinese）.［甘明鑫，竇雪，王道平，等.一種綜合加權的本體概念語義相似度計算方法 ［J］.Computer Engineering and Applications，2012，48（17）：148－153.］

［14］JIANG Hua.Research on concept semantic sim ilarity computation based on ontology ［J］.Computer Applications and Software，2009，26 （7）：143－145 （in Chinese）.［姜華.一種基于本體的概念語義相似度計算研究 ［J］.計算機應用與軟件，2009，26 （7）：143－145.］

［15］ZHANG Zhongping，ZHAO Hailiang，ZHANG Zhihui.Concept similarity computation based on ontology ［J］.Computer Engineering，2009，35 （7）：17－19 （in Chinese）. ［張忠平，趙海亮，張志惠.基于本體的概念相似度計算 ［J］.計算機工程，2009，35 （7）：17－19.］