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

（武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢430072）

0 引 言

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

1 研究現(xiàn)狀

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

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

2 改進(jìn)的相似度計(jì)算

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

2.1 基本定義

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

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

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

（2）當(dāng)且僅當(dāng)M1和M2為同一節(jié)點(diǎn)時(shí)，值為1；

（3）當(dāng)M1和M2不在同一個(gè)本體樹時(shí)，值為0。

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

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

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

圖1 wordnet片段

2.2.1 共享路徑重合度

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

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

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

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

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

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

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

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

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

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

2.2.4 概念屬性

2.3 PRSSC算法

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

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

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

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

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

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

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

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

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

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

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

圖2 打印機(jī)本體片段

表1 打印機(jī)本體實(shí)驗(yàn)結(jié)果

4 結(jié)束語

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

［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ì)算方法研究綜述 ［J］.現(xiàn)代圖書情報(bào)技術(shù)，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）.［楊方穎，蔣正翔，張姍姍.基于本體結(jié)構(gòu)的語義相似度計(jì)算［J］.計(jì)算機(jī)技術(shù)與發(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］.計(jì)算機(jī)應(yīng)用，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）.［李文杰，趙巖.基于本體結(jié)構(gòu)的概念間語義相似度算法 ［J］.計(jì)算機(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］計(jì)算機(jī)應(yīng)用與軟件，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）.［劉宏哲，須德.基于本體的語義相似度和相關(guān)度計(jì)算研究綜述［J］.計(jì)算機(jī)科學(xué)，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ìn)的領(lǐng)域本體概念語義相似度計(jì)算方法［J］. 計(jì)算機(jī)應(yīng)用與軟件，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ì)算方法 ［J］.自動(dòng)化學(xué)報(bào)，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ìn)的本體相似度計(jì)算方法 ［J］.計(jì)算機(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）. ［徐桂臣，葉楓.基于語義加權(quán)距離的語義相似度改進(jìn)算法 ［J］.情報(bào)雜志，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ìn)的概念語義相似度計(jì)算 ［J］.計(jì)算機(jī)工程與設(shè)計(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）.［甘明鑫，竇雪，王道平，等.一種綜合加權(quán)的本體概念語義相似度計(jì)算方法 ［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ì)算研究 ［J］.計(jì)算機(jī)應(yīng)用與軟件，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ì)算 ［J］.計(jì)算機(jī)工程，2009，35 （7）：17－19.］