吳 奎,周獻(xiàn)中,王建宇,趙佳寶

(1.南京理工大學(xué) 自動化學(xué)院,江蘇 南京210094;2.南京大學(xué) 工程管理學(xué)院,江蘇 南京210093)

1 引言

領(lǐng)域本體可以有效地組織、共享、重用領(lǐng)域中的知識,在軟件工程、人工智能、信息檢索、Web服務(wù)發(fā)現(xiàn)等領(lǐng)域扮演著越來越重要的角色。概念語義相似度計(jì)算是領(lǐng)域本體應(yīng)用中的基礎(chǔ)問題,用于表示本體中兩個(gè)概念之間的語義接近程度,以便提高知識檢索、服務(wù)匹配、本體映射等過程的性能[1]。已有的各種概念語義相似度計(jì)算模型,都是為了刻畫兩個(gè)概念之間的語義相近程度,其數(shù)值大小應(yīng)盡可能地接近主觀意識和客觀因素。主觀上,由于人們對事物認(rèn)識的差異,并不能給出兩個(gè)概念的相似度具體數(shù)值,但在父子概念層次結(jié)構(gòu)中,某個(gè)概念與它的子概念之間的相似度必然大于其父概念與其子概念的相似度。如“哺乳動物”和“男人”之間的語義相似度應(yīng)大于“動物”和“男人”之間的相似度,小于“哺乳動物”和“人”之間的相似度。客觀上,任何一個(gè)概念都是對其祖先概念信息的細(xì)化。因此從信息論角度,兩個(gè)概念之間的相似度與二者共享的信息有關(guān),它們從相同祖先概念中共享的信息量越多,則二者越相似。

計(jì)算兩個(gè)概念之間的語義相似度,目前有很多種方法,Budanitsky[1]對基于WordNet的幾種方法進(jìn)行了比較。李峰[2]認(rèn)為這些方法可以分為兩大類：一種是基于兩個(gè)節(jié)點(diǎn)之間的路徑長度,即語義距離;另一種是基于兩個(gè)節(jié)點(diǎn)所含的共有信息大小。綜合來看,基于語義距離算法簡單,但它依賴于主觀建立好的概念層次網(wǎng)絡(luò)和各個(gè)邊的權(quán)值,因而不能保證相似度的客觀性;基于信息量的相似度計(jì)算在理論上更具有說服力,它根據(jù)信息論的方法,通過概念A(yù)、B之間的共享信息量和獨(dú)立信息量計(jì)算獲得,然而這種方法需要足夠多的領(lǐng)域資料。針對這些方法的不足,江敏等[3]以加權(quán)和的方式綜合不同方法的結(jié)果,然而這種方式的合理性值得懷疑;Anna Formica[4]提出了一種基于形式概念分析的相似度算法,基于概念的上下文計(jì)算二者的相似度。本文以Lin[5]的概念相似度算法為基礎(chǔ),提出一種基于貝葉斯估計(jì)的相似度計(jì)算方法(Bayesian Estimation Similarity,BES),通過綜合考慮主觀先驗(yàn)因素和客觀統(tǒng)計(jì)樣本,以求能更好地體現(xiàn)領(lǐng)域本體中兩個(gè)概念之間的語義接近程度。

貝葉斯統(tǒng)計(jì)推斷[6]是當(dāng)今統(tǒng)計(jì)學(xué)發(fā)展最快的分支之一,已成為當(dāng)今統(tǒng)計(jì)學(xué)的重要組成部分。雖然這種方法曾經(jīng)有很多爭論,比如指定一種先驗(yàn)分布不免帶有人為性,未必有助于問題的合理解決,但近年來這些爭論已不是主流,大多數(shù)研究人員都承認(rèn)貝葉斯方法可較好的應(yīng)用于統(tǒng)計(jì)學(xué)的幾乎所有分支。本文不考慮貝葉斯方法在哲學(xué)方面的問題,而是根據(jù)貝葉斯估計(jì)計(jì)算概念出現(xiàn)概率。該方法主要思路為：考慮到Beta分布可以通過選擇合理參數(shù)適應(yīng)多種分布形狀,且容易獲得計(jì)算結(jié)果,本文假設(shè)概念出現(xiàn)概率也服從Beta分布,隨后基于語義距離的算法構(gòu)造其先驗(yàn)參數(shù),并利用貝葉斯估計(jì)計(jì)算該先驗(yàn)分布和統(tǒng)計(jì)樣本下的后驗(yàn)概率,最后根據(jù)基于信息量的公式獲得主觀經(jīng)驗(yàn)與客觀事實(shí)相結(jié)合的概念語義相似度。

本文后續(xù)內(nèi)容安排如下：第2節(jié)給出語義相似度計(jì)算的基本思想,第3節(jié)介紹本文提出的算法,第4節(jié)將本文提出的算法與現(xiàn)有的6種方法進(jìn)行比較,最后在第5節(jié)總結(jié)全文。

2 基本思想

2.1 基本定義

本體的概念起源于哲學(xué)領(lǐng)域,是關(guān)于存在的學(xué)說。1993年美國斯坦福大學(xué)的G ruber給出了第一個(gè)在信息科學(xué)領(lǐng)域中的本體的正式定義[7]：本體是一個(gè)明確的概念化共享規(guī)范。目前關(guān)于本體的形式化定義很多,這里采用W 3C給出的定義[8]。

定義1：概念,也稱為類,是指具有相似特性的實(shí)體集合的名稱;某個(gè)概念所限定的具體事物對象,稱為個(gè)體;個(gè)體之間的相互聯(lián)系稱為關(guān)系。如：“小張”是概念“學(xué)生”的個(gè)體,他與《本體論》這本“書”之間存在“借閱”關(guān)系。

定義2：本體是一種領(lǐng)域知識表示手段,可以被表示為O=(C,R,I,A),其中C表示概念集合,R表示關(guān)系集合,I表示個(gè)體集合,A表示相關(guān)公理集合。

定義3：如果概念 A具有概念B的特性,稱概念A(yù)是概念B的子概念,記為A?B。如果A?B且A、B之間不存在滿足繼承關(guān)系的其他概念,則稱概念A(yù)是概念B的直接子概念,記為A=B?;。概念B的子概念集合記為ch(B),概念B的直接子概念數(shù)稱為該概念的出度deg?(B)。相應(yīng)地,也有直接父概念B,父概念集合an(B)。

定義4：領(lǐng)域本體中的概念集在繼承關(guān)系上構(gòu)成了概念格。格的頂節(jié)點(diǎn)稱為頂概念T,概念C與頂概念之間最短路徑上的邊數(shù)稱為該概念的深度dep(C)。

定義5：在領(lǐng)域本體中,概念的出現(xiàn)概率記為P(C)=P(c∈C),它表示從所有個(gè)體中隨機(jī)抽取某個(gè)個(gè)體是概念C個(gè)體的可能性。統(tǒng)計(jì)上,該數(shù)值可以用相對頻率P(C)=f req(C)/N,其中 f req(C)=∑c∈C count(c)表示概念C的所有個(gè)體數(shù),N為領(lǐng)域本體中全部個(gè)體數(shù)。

定義6：在領(lǐng)域本體中,概念C1和C2之間的相似度定義為[5]

其中LCS(C1,C2)表示概念C1和C2的最小公共父概念。

2.2 相似度基本假定

從公式(1)我們可以看出概念出現(xiàn)概率是計(jì)算兩個(gè)概念語義相似度的關(guān)鍵,而它需要在大樣本空間中統(tǒng)計(jì)基礎(chǔ)上獲得,本文提出了一種基于貝葉斯估計(jì)的算法以減小這種依賴。在下文展開之前,首先給出如下兩個(gè)基本假設(shè)：

1)領(lǐng)域知識庫中,“個(gè)體a是概念C中的個(gè)體”這一命題的取值只有True和False兩種可能,即隨機(jī)變量 x：=a∈C服從0～1分布;

2)若個(gè)體a是概念C中的個(gè)體,則它必然是C的父概念的個(gè)體,因此某概念的出現(xiàn)概率必然大于其子概念的出現(xiàn)概率,小于其父概念的出現(xiàn)概率。

顯然,這兩個(gè)基本假定是可以接受的,概念語義相似度具有如下性質(zhì)[5,9]：

1)當(dāng)兩個(gè)概念相同時(shí),相似度最大,規(guī)定為1;當(dāng)兩個(gè)概念沒有共性時(shí)相似度最小,規(guī)定為0,即0≤Sim(C1,C2)≤1,且Sim(C,C)=1。

2)概念間相似度與二者所處層次有關(guān),概念層次越深,對事物刻畫越細(xì),父子概念之間的差異越小,語義越接近。即Sim(C,C)≤Sim(C,C)。

3)某個(gè)概念的直接子概念越多,則分類越細(xì),某個(gè)子概念對父概念的修飾越少,父子概念之間相似度越大。

3 基于貝葉斯估計(jì)的概念相似度算法原理

3.1 概念出現(xiàn)概率先驗(yàn)分布構(gòu)造

根據(jù)基本假設(shè),從領(lǐng)域本體中任意選取某個(gè)體ai,事件 xi：=ai∈C是獨(dú)立同分布的,且服從概率為P的0～1分布。我們利用基于語義距離的算法構(gòu)造概率P的先驗(yàn)分布。概念之間的語義距離是指概念層次結(jié)構(gòu)中節(jié)點(diǎn)之間最短路徑的加權(quán)和,路徑的權(quán)值可按公式(2)計(jì)算：

其中經(jīng)驗(yàn)參數(shù)ρ>1反映了概念層次結(jié)構(gòu)中語義距離隨著深度變化的減小程度。兩個(gè)概念之間的語義距離為：

其中min{C1;C2}是概念C1和C2之間的最短路徑,因此C1和C2的語義相似度為：

經(jīng)驗(yàn)參數(shù)μ為調(diào)節(jié)參數(shù)。根據(jù)公式(4)容易驗(yàn)證對于任意概念C均有

3.3 Beta分布形狀參數(shù)計(jì)算

考慮到標(biāo)準(zhǔn)Beta分布變量范圍在[0,1]之間,做線性變換將上述Beta分布化為標(biāo)準(zhǔn)形式[10]：

根據(jù)Beta分布形狀參數(shù)計(jì)算公式[10]有：

其中,期望E=(?PM+4?P+?PN)/6,方差D=(?PN-?PM)2/36。

3.4 后驗(yàn)出現(xiàn)概率

根據(jù)統(tǒng)計(jì)樣本在n個(gè)個(gè)體中有k個(gè)個(gè)體屬于概念C,下面根據(jù)最小貝葉斯風(fēng)險(xiǎn)估計(jì)計(jì)算θ的估計(jì)值。

設(shè)損失函數(shù)為 L(θ,δ),則統(tǒng)計(jì)判決 δ(X)的貝葉斯風(fēng)險(xiǎn)函數(shù)為

其中 f(X,θ)為 X在θ估計(jì)下的聯(lián)合分布,根據(jù)貝葉斯定理,可得：

其中c(X)是歸一化常數(shù)保證該分布是一個(gè)概率分布,將公式(10)代入公式(9)并交換積分次序后可得：

把損失函數(shù) L(θ,δ(X))關(guān)于后驗(yàn)分布 π(θ|x)的加權(quán)平均稱為后驗(yàn)風(fēng)險(xiǎn),即

可以看出若某個(gè) δ(X)使得后驗(yàn)風(fēng)險(xiǎn) Rπ(δ|x)達(dá)到最小,則它也使貝葉斯風(fēng)險(xiǎn) Rπ(δ)達(dá)到最小。取損失函數(shù) L(θ,δ(X))=(δ(X)-θ)2代入公式(11)后得

其中：

因此當(dāng)δ=-b/2a時(shí),Rπ(δ|x)取得最小值。根據(jù)公式(10),有：

可以看出 π(θ|x)也服從 Beta分布,其超參數(shù)為k+α和n-k+β,即

因此使得Rπ(δ|x)取得最小值的δ為：

最后根據(jù)線性變換公式(6),有

這樣,我們便通過貝葉斯估計(jì)計(jì)算出概念出現(xiàn)概率P的后驗(yàn)估計(jì)值。從公式(16)看出P為概念出現(xiàn)概率的主觀經(jīng)驗(yàn)值根據(jù)統(tǒng)計(jì)特性的修正,當(dāng)有大樣本時(shí)δ趨向于k/n體現(xiàn)了統(tǒng)計(jì)特性。當(dāng)樣本很少,特別是k=0時(shí)并不能說某概念不可能出現(xiàn),仍然具有一定的出現(xiàn)可能,可通過主觀經(jīng)驗(yàn)算法計(jì)算獲得。

4 算法實(shí)現(xiàn)及結(jié)果分析

4.1 算法實(shí)現(xiàn)過程

基于上面介紹的概念相似度BES算法原理,我們實(shí)現(xiàn)了本算法,并與其他幾種方法比較。在算法實(shí)驗(yàn)中以WordNet[11]作為數(shù)據(jù)源,首先利用JAWS開發(fā)包,以entity為根節(jié)點(diǎn),通過函數(shù)getSynsets獲得單詞的義元,通過函數(shù)getTagCount獲得該義元的出現(xiàn)次數(shù),通過函數(shù)getHyponyms獲得該義元的子概念。采用寬度優(yōu)先的方式逐層訪問各個(gè)概念節(jié)點(diǎn)信息,獲得其出現(xiàn)次數(shù)統(tǒng)計(jì)值,并保存到自定義的數(shù)據(jù)庫中。隨后根據(jù)提取出的概念層次結(jié)構(gòu),遍歷各個(gè)節(jié)點(diǎn),依次計(jì)算各自的出現(xiàn)概率先驗(yàn)分布參數(shù)和后驗(yàn)估計(jì)值,由于這些數(shù)據(jù)的計(jì)算為實(shí)數(shù)運(yùn)算,故算法復(fù)雜度取決于所采用的遍歷策略,可以證明為O(n)[12]。概念出現(xiàn)概率的貝葉斯估計(jì)算法過程如下：

算法CalcValues(C)過程如下：

4.2 算法實(shí)驗(yàn)結(jié)果分析

由于不同的算法原理不同,計(jì)算結(jié)果也有較大差異,我們參考文獻(xiàn)[1]的做法：以M iller和Charles統(tǒng)計(jì)的30對概念間的主觀相似度數(shù)值作為參考標(biāo)準(zhǔn),并與 Ted Pedersen 實(shí)現(xiàn)的 Wordnet：：Similarity[13]中其他相似度算法結(jié)果對比。實(shí)驗(yàn)中取ρ=1.1,μ=0.5(x)=x,實(shí)驗(yàn)結(jié)果見表1,表中BES為本算法結(jié)果,HSO 、LCH、WUP、RES、JCN 、LIN分別表示 Hirst&St-Onge方法,Leacock&Chodorow方法,Wu&Palmer方法,Resnik方法,Jiang&Conrath方法和Lin方法。

為了比較不同相似度算法的差異,我們參考文獻(xiàn)[1],計(jì)算各組數(shù)據(jù)與Human結(jié)果的相關(guān)系數(shù),以此作為衡量各種算法優(yōu)劣的指標(biāo),結(jié)果如表2所示,可以看出本文算法的相關(guān)系數(shù)稍高于其他算法。

表1 相似度數(shù)值對比計(jì)算結(jié)果

表2 相似度相關(guān)系數(shù)對比

4.3 參數(shù)對比實(shí)驗(yàn)

為了分析統(tǒng)計(jì)數(shù)據(jù)和算法參數(shù)對相似度計(jì)算結(jié)果的影響,采用同樣的測試集做了對比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表3所示。

表3 參數(shù)調(diào)整對比計(jì)算結(jié)果

續(xù)表

實(shí)驗(yàn)中,前三組為帶有統(tǒng)計(jì)數(shù)據(jù)的結(jié)果,其中第1組ρ=1.1,μ=0.5;第2 組 ρ=1.2,μ=0.3;第3組ρ=1.4,μ=0.2。后三組為概念出現(xiàn)次數(shù)均為0時(shí)的結(jié)果,其中第4組ρ=1.1,μ=0.5;第5組ρ=1.2,μ=0.3;第 6組ρ=1.4,μ=0.2。計(jì)算各組數(shù)據(jù)與H um an結(jié)果的相關(guān)系數(shù),結(jié)果如表4所示。

表4 參數(shù)調(diào)整對比實(shí)驗(yàn)相關(guān)系數(shù)

從實(shí)驗(yàn)結(jié)果看出,盡管隨著統(tǒng)計(jì)數(shù)據(jù)和參數(shù)的變化,相似度結(jié)果也有所不同,但與主管經(jīng)驗(yàn)的相關(guān)系數(shù)變化很小,因此本算法對數(shù)據(jù)和參數(shù)的變動不敏感。

5 結(jié)束語

概念相似度計(jì)算是本體映射、服務(wù)發(fā)現(xiàn)、語義檢索等技術(shù)的關(guān)鍵基礎(chǔ)。本文的主要貢獻(xiàn)如下：提出了一種基于貝葉斯估計(jì)的概念出現(xiàn)概率算法;在此基礎(chǔ)上概念相似度計(jì)算綜合考慮了人為主觀經(jīng)驗(yàn)和客觀統(tǒng)計(jì)樣本,改進(jìn)了傳統(tǒng)方法的不足,具有較好的實(shí)用性。結(jié)合WordNet的算法實(shí)驗(yàn)表明,本算法與人為主觀經(jīng)驗(yàn)之間具有最大的相關(guān)系數(shù)。

由于本算法需要首先根據(jù)當(dāng)前概念層次結(jié)構(gòu)和出現(xiàn)次數(shù)計(jì)算各個(gè)概念的出現(xiàn)概率,當(dāng)概念數(shù)較多,網(wǎng)絡(luò)復(fù)雜時(shí),如使用WordNet時(shí),它必須構(gòu)造新的數(shù)據(jù)庫以便存放每個(gè)概念的出現(xiàn)概率,需要占用額外的資源。另外,由于概念相似度大小并沒有客觀標(biāo)準(zhǔn),僅依賴少量測試數(shù)據(jù)并不能充分說明各種方法之間的性能差異,且主觀經(jīng)驗(yàn)值是否合理也有待商榷,因此如何評價(jià)各種算法的優(yōu)劣性還值得進(jìn)一步研究。

[1] A lexander Budanitsky,Graeme H irst.Evaluating Word-Net-based Measures of Lexical Semantic Relatedness[J].Computational Linguistics,2006,1(32)：13-49.

[2] 李峰,李芳.中文詞語語義相似度計(jì)算——基于《知網(wǎng)》2000[J].中文信息學(xué)報(bào),2007,21(3)：99-105.

[3] 江敏,肖詩斌,王弘蔚,等.一種改進(jìn)的基于《知網(wǎng)》的詞語語義相似度計(jì)算[J].中文信息學(xué)報(bào),2008,22(5)：84-89.

[4] Anna Form ica.Ontology-based concept similarity in Formal Concep t Analysis[J].Information Sciences,2006,176(18)：2624-2641.

[5] Dekang Lin.An in formation-theoretic definition o f similarity[C]//Proceedings of the 15thInternational Conference on M achine Learning,San Francisco：M organ Kaufmann.1998：296-304.

[6] 陳希孺.數(shù)理統(tǒng)計(jì)引論[M].北京：科學(xué)出版社,1999：131-159.

[7] Thomas R.G ruber.A translation approach to portable ontology specification[J].Know ledge Acquisition,1993,5(2)：1992-2201.

[8] W 3C.OW LW eb Ontology Language Reference[EB/OL][2009-7-8].http：//www.w3.org/TR/ow l-ref.

[9] 劉群,李素建.基于《知網(wǎng)》的詞匯語義相似度計(jì)算[C]//臺北：第三屆漢語詞匯語義學(xué)研討會論文集.2002：59-76.

[10] 方開泰,許建倫.統(tǒng)計(jì)分布[M].北京：科學(xué)出版社.,1987：246-258.

[11] Princeton University Cognitive Science Laboratory.W ordNet-a lexical database for the English language[EB/OL][2009-7-9].http：//wordnet.p rinceton.edu.

[12] Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Introduc tion to A lgorithms[M],M IT Press,2001：224-227.

[13] Ted Pedersen.W ordnet：：Sim ilarity[EB/OL][2009-7-9],http：//w nsim ilarity.sourceforge.net.