沈亦軍 呂剛

(合肥學(xué)院，合肥230601)

基于實例相似度的本體映射方法研究

沈亦軍 呂剛

(合肥學(xué)院，合肥230601)

提出利用貝葉斯理論計算實例相似度，定義集合相似度和概率相似度兩個概念，推導(dǎo)出計算模型，得到一個完整的解決實例映射方案。用實例相似來優(yōu)化映射，該方案的查全率和查準率比傳統(tǒng)方法有所提高。

本體映射；實例相似度；貝葉斯概率

本體映射是信息集成、語義Web和知識管理等領(lǐng)域的一個關(guān)鍵問題［1］。在實現(xiàn)本體映射的各類方法中，基于相似度計算的本體映射是最常用的一種方法。在某些場合必須用實例映射才能得到正確的本體映射對，因為實例才真正反映了概念節(jié)點的語義含義，于是可以用實例相似來優(yōu)化映射效果［2］。

檢索是語義WEB的中心環(huán)節(jié)，而相似度計算是實現(xiàn)語義檢索的核心技術(shù)，其計算方法的好壞直接決定了實例檢索的質(zhì)量和可靠性。因此，在構(gòu)建和管理基于實例推理系統(tǒng)時，相似度計算起到了非常關(guān)鍵的作用［3］。許多實例相似度計算根據(jù)實例的屬性特征，采用相似度函數(shù)來計算實例之間的相似度，有的是利用計算兩個概念所對應(yīng)實例集的公共部分所占總實例的比例來衡量［4］。文獻［5］提出了豐富度和平衡度的概念，實現(xiàn)實例相似度的計算。本文基于貝葉斯方法，給出了一個比較有效的計算本體實例相似度的方法。

1 改進的實例相似度計算方法

實例實際上是一個概念的文本集合，兩個實例集的公共元素在一定程度上反映了這兩個集合的相似性。同時，很多時候一個元素是由多個詞組合構(gòu)成的，必須先對其進行預(yù)處理。貝葉斯決策就是在不完全情報下，對部分未知的狀態(tài)用主觀概率估計，然后用貝葉斯公式對發(fā)生概率進行修正，最后再利用期望值和修正概率做出最優(yōu)決策，從而提高查準率和查全率。

1.1 實例預(yù)處理

貝葉斯理論的基礎(chǔ)公式是P(A|B)=P(B|A)P(A) /P(B)，借用概率這個概念來表示相似度，即A與B的相似度就是A與B相似的概率。

定義1實例文本集：某概念所對應(yīng)的若干實例組成的集合，記為Ic。

一個本體中的每個概念都有自己的實例文本集，而給本體構(gòu)造實例文本集也是實例預(yù)處理的首要步驟。首先為本體樹中每個概念節(jié)點在各實例中對應(yīng)的元素值分別構(gòu)造文本集，得到本體的實例文本集；然后，對集合中的多詞進行分詞，得到新的由多詞集合構(gòu)成的實例文本集。

計算實例相似度的基礎(chǔ)原理，這里計算實例相似度主要基于兩個假設(shè)：

（1）兩個概念所包含的公共實例越多，實例集越相似。

（2）某個實例集中元素在另一實例集中出現(xiàn)的頻率越高，實例集越相似。

對于假設(shè)（1），可以將兩個實例文本集看成是兩個簡單的集合，然后計算它們之間交集和并集的比，作為相似度；對于假設(shè)（2），基于貝葉斯決策來計算某個實例文本集中元素在另一個實例文本集中出現(xiàn)的頻率，來求基于貝葉斯理論的相似度，最后將這兩個計算結(jié)果相結(jié)合。

1.2 集合相似度

定義2集合相似度：兩個實例集的集合相似度，將這兩個實例集看成集合后，計算出交集與并集的比值。這個比值越大，則表示兩個實例文本集的公共部分所占比重越大，即兩個實例文本集越相似，反之亦反。然而在分詞過后的實例文本集中，一個多詞分成了多個詞元，于是就有兩種方法可以計算集合相似度：

（1）將所有詞元看成是一個集合。

（2）將每個多詞表示成由詞元組成的集合，而實例文本集便是由這些集合組成的集合。

對于第一種設(shè)計，會把每個多詞拆開，于是詞元充分獨立，這樣處理就忽略了多詞本身的含義，結(jié)果比較片面，不夠準確，所以本文中選用第二種方案。于是，兩個實例文本集就轉(zhuǎn)換成集合的集合，在尋找公共元素時，只要某對多詞集合含有一個公共詞元，則這對多詞集合就是兩個實例文本集中的一個公共元素。

假設(shè)這兩個實例文本集分別是si和sj，其中：si= {g1，g2，g3，…，gm}，sj={g1，g2，g3，…，gn}。而gi={w1，w2，w3，…，wp}，這里gi為多詞集合，而wi（1≤i≤p）為詞元。對于本身就是一個詞元的元素，則gi即是它自身構(gòu)成的長度為1的集合。

接著我們定義si*sj和si∪sj：gk∈si*sj，當(dāng)且僅當(dāng)gk∈si∧{wp∈gk∧（gt∈sj→wp∈gt）}或gk∈sj∧{wp∈gk∧（gt∈si→wp∈gt）}，即si*sj是由si和sj中含有公共詞元的多詞集合構(gòu)成的集合。

最后，實例文本集的集合相似度pl(si,sj)=|si*sj|/| si∪sj|。

1.3 概率相似度

假設(shè)兩個實例文本集si和sj，其中si={g1，g2，g3，…，gm}，sj={g1，g2，g3，…，gn}，gi={w1，w2，w3，…，wp}，這里gi為多詞集合，wi（1≤i≤p）為詞元。si中的詞元在si中出現(xiàn)的頻率和sj中的詞元在sj中出現(xiàn)的頻率都在一定程度上反映了兩個實例文本集的相似性，于是可以利用這兩個頻率來計算相似度。論文引出如下兩個概念來表示上述的兩種頻率：

定義3權(quán)重：某一多詞集合的權(quán)重是指在包含它的實例文本集中與該多詞集合相交的多詞集合所占的比重。

定義4外部權(quán)重：在實例文本集中與該集合內(nèi)或該集合外的某一多詞集合有交集的多詞集合所占的比重，即表示這個多詞集合在該實例文本集中的權(quán)重。

權(quán)重反映了多詞集合在包含它的實例文本集中的重要性，外部權(quán)重是指任一多詞集合在某一實例文本集中的重要性，往往這個多詞集合來源于其他的實例文本集，在計算實例相似度時，這個多詞集合就來源于映射的另一個實例文本集中。

對于兩個實例文本集si和sj，其實si映射到sj的相似程度和sj映射到si的相似程度往往是不一樣的，即這種相似度具有非對稱性。論文提出了“單向概率相似度”的概念描述某一實例文本集映射到另一實例文本集的相似程度，它是有方向的。例如si到sj的單向概率相似度可以記為p(si|sj)，它是由si中每個多詞集合在sj中的外部權(quán)重和這個多詞集合在sk中的權(quán)重決定的。由貝葉斯基本公式可得：

而si和sj的概率相似度是由si到sj的單向概率相似度和sj到si的單向概率相似度組成的，即

基于以上理論，可以用集合相似度和概率相似度來表示兩個實例文本集的相似度：

2 實驗與分析

本文設(shè)計進行了實驗，證明論文所提出的優(yōu)化策略對一般的基礎(chǔ)策略效果的改進。本文選用的實驗數(shù)據(jù)來源于基于KAON2的開源資源Frame work for Ontology Alignment and Mapping（http://www. aifb.uni-karlsruhe.de/WBS/meh/foam/）中所提供的TestOntologies and Alignments。這里提供14個可用本體以及各本體映射的結(jié)果，本文的實驗從中選用russia1.owl和russia2.owl作為數(shù)據(jù)源。整個實驗過程用到的工具主要有Jena，VC++6.0和protégé3.1。

russia1和russia2中自帶了部分實例，而剩余實例便在protégé中手動創(chuàng)建。在本實驗中，每一個類均創(chuàng)建了30至40個實例，整個實例規(guī)模達到3 600左右。經(jīng)過計算，可以得到每對節(jié)點的集合相似度、單向概率相似度以及概率相似度，最終得到實例相似度。如表1是部分結(jié)果，概率相似度是由兩個單向概率相似度的平均值得到的，表中“概率相似度”一列中所填的數(shù)據(jù)同時列出了單向概率相似度。例如第一行0.69(0.71,0.67)表示s1到s2的單向概率相似度是0.71，s2到s1的單向概率相似度是0.67，而s1和s2的概率相似度為0.69。

表1 實例相似度計算結(jié)果

由于本文的映射算法可以應(yīng)用到多策略映射系統(tǒng)中，所以暫稱為MP_Bayes。表2中,測試集1-3表示標(biāo)準測試數(shù)據(jù)集中的本體編號。測試結(jié)果分別與文獻［1］中提出的SNAX_Map方法以及Rimon系統(tǒng)測試結(jié)果進行比較。關(guān)于查全率和查準率，本文采用如下定義：

查全率：映射結(jié)果中正確的映射對數(shù)目與標(biāo)準映射對數(shù)目的比值。

查準率：映射結(jié)果中正確的映射對數(shù)目與映射結(jié)果以及標(biāo)準結(jié)果的并集中映射對數(shù)目的比值。

表2 MP_Bayes與其他系統(tǒng)綜合數(shù)據(jù)比較

從實驗結(jié)果來看,MP_Bayes系統(tǒng)和SNAX_Map系統(tǒng)唯一區(qū)別就是采用了不同的實例映射方法，MP_Bayes系統(tǒng)采用了本文提出的改進的實例映射方法。表2中數(shù)據(jù)顯示實驗MP_Bayes系統(tǒng)的查全率和查準率最高。也就是說，應(yīng)用改進的實例映射算法的多策略結(jié)合方法在保證了查全率的同時，較為明顯的提高了查準率，也就提高了最終映射結(jié)果的質(zhì)量。同時，對各組不同的測試數(shù)據(jù)MP_Bayes的性能比較穩(wěn)定。

3 結(jié)語

概念相似度計算是本體映射、服務(wù)發(fā)現(xiàn)、語義檢索等技術(shù)的關(guān)鍵基礎(chǔ)。本文在分析現(xiàn)有本體實例映射作用的基礎(chǔ)上，提出了改進的本體實例映射方法，很好地利用了貝葉斯理論，彌補了實例映射策略所固有的缺陷，使得某些信息的缺乏或重復(fù)不會對整個映射系統(tǒng)產(chǎn)生大的影響。實驗表明，采用新算法的系統(tǒng)性能比傳統(tǒng)的多策略結(jié)合方法得到了改進。

[1]夏紅科，鄭雪峰，胡祥.一種新的本體映射發(fā)現(xiàn)方法SME [J].計算機科學(xué)，2010，37（6）：233-236.

[2]Ehrig M,Sur Y.Ontology Mapping：An Integrated Approach[D].Germany：University of Karlsruhe，2004.

[3]李軍均，戚進，胡潔，等.一種基于隸屬函數(shù)的相似度計算方法及其應(yīng)用[J].計算機應(yīng)用研究，2010，27（3）:891-894.

[4]唐杰，梁邦勇，李涓子，等.語義Web中的本體自動映射[J].計算機學(xué)報，2006，11（29）：1956-1976.

[5]黎民.語義多策略結(jié)合匹配算法[J]．計算機應(yīng)用，2008，28 (7):1639-1641.

Research on Ontology M apping Based on Instance Sim ilarity

SHEN Yijun LüGang
(HefeiUniversity,Hefei230601)

This paper proposes the sim ilarity calculation based on Bayesian theory，two concepts of the set sim ilarity and the probability sim ilarity,derives the calculationmodel and gets a complete solution to an instance ofmapping programs.Experiments show that the proposed program recall and precision is better than traditional methodshave improved.

ontologymapping；instance sim ilarity；Bayesian probability

TP311

A

1673-1980（2012）03-0170-03

2011-12-16

安徽省教育廳自然科學(xué)基金項目(KJ2011Z321)；安徽省高校省級優(yōu)秀青年人才基金項目（2011SQRL134）；合肥學(xué)院點科研項目（01KY03ZD）

沈亦軍（1966-），男，福建人，實驗師，研究方向為計算機網(wǎng)絡(luò)。