滕 玲 ，朱俊武 ，李 斌，2 ，楊 洲，朱澤宇

1(揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225009)2(南京大學(xué) 軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京 210093)3(揚(yáng)州大學(xué) 廣陵學(xué)院，江蘇 揚(yáng)州 225000)

1 引 言

隨著web技術(shù)的不斷發(fā)展，語義web為網(wǎng)頁擴(kuò)展了計(jì)算機(jī)可理解的、可處理的語義信息，從而解決了因信息形式異構(gòu)、語義多重性帶來的機(jī)器之間無法理解和交互的問題[1].知識(shí)圖譜是大數(shù)據(jù)的結(jié)構(gòu)化表示，作為互聯(lián)網(wǎng)資源組織的基礎(chǔ)，能夠促進(jìn)語義web的發(fā)展.本體是對(duì)特定領(lǐng)域中概念及概念之間關(guān)系的形式化表達(dá)，可以作為知識(shí)圖譜表示的概念模型和邏輯基礎(chǔ).因此在語義 web中，本體可以為web上的信息提供語義解釋，有利于人機(jī)交互[2].然而隨著特定領(lǐng)域的擴(kuò)大和本體數(shù)量的劇增，不同用戶或agent根據(jù)不同需求、應(yīng)用來構(gòu)建本體，他們往往采用不同的建模方式或本體描述語言，但這些本體所描述的內(nèi)容在語義上有時(shí)會(huì)有重疊或者關(guān)聯(lián)，這就造成了本體的異構(gòu).由于分布式本體異構(gòu)的特性阻礙了web服務(wù)的互操作性，使之成為了語義web中亟待解決的問題之一[3].本體映射(Ontology mapping)和本體合并(Ontology merging)都能有效的解決上述問題.本體映射是將源本體通過映射規(guī)則轉(zhuǎn)換成目標(biāo)本體的過程，它側(cè)重于發(fā)現(xiàn)兩個(gè)本體中術(shù)語或概念之間的語義關(guān)聯(lián)，本體映射不會(huì)改變?cè)幢倔w的結(jié)構(gòu)；而本體合并是指在給定一組源本體的基礎(chǔ)上，通過預(yù)先定義好的合并規(guī)則生成一個(gè)新的共享本體，新本體能夠?yàn)榫唧w語義提供一個(gè)共享的詞匯表，但這個(gè)新本體相對(duì)于源本體結(jié)構(gòu)上發(fā)生了改變[4].

具體來說，本體合并是將特定領(lǐng)域中n(n≥2)個(gè)異構(gòu)的局部本體(Individual local ontology)合并成一個(gè)新的共享決策本體(Shared collective ontology)的過程，因此我們可以將此過程看成是社會(huì)選擇理論(Social Choice Theory，SCT)中的一種應(yīng)用.社會(huì)選擇是經(jīng)濟(jì)學(xué)的一個(gè)重要分支，主要研究和分析個(gè)體偏好和社會(huì)決策之間的關(guān)系，并為聚集個(gè)人偏好提供了多種聚集規(guī)則和評(píng)判準(zhǔn)則.近年來，眾多學(xué)者將SCT與計(jì)算科學(xué)領(lǐng)域相結(jié)合，從而形成一門新的交叉學(xué)科“計(jì)算社會(huì)選擇”，在涉及聚集個(gè)體偏好的領(lǐng)域有著廣泛應(yīng)用[5].例如，社會(huì)選擇函數(shù)在多智能體系統(tǒng)(Multi-agent system)和推薦系統(tǒng)(Recommender system)等方面有著舉足輕重的意義.投票理論(Voting theory)和判斷聚集(Judgement aggregation)作為社會(huì)選擇的經(jīng)典應(yīng)用為本體合并奠定了理論基礎(chǔ)，其中常見的聚集方式以及一般性質(zhì)，例如一致性、單調(diào)性、中立性等都為本體合并機(jī)制的設(shè)計(jì)提供了方法論.

基于以上，本文從SCT的角度出發(fā)，綜合考慮本體構(gòu)建者的可信度和本體間的相似度，針對(duì)異構(gòu)源本體的合并問題做出研究.文章的主要架構(gòu)如下：第二部分介紹國(guó)內(nèi)外學(xué)者對(duì)本體合并的研究現(xiàn)狀以及存在的不足之處；第三部分構(gòu)建了以社會(huì)選擇和描述邏輯為基礎(chǔ)的本體合并框架，并給出了相關(guān)的定義和公式；第四部分具體闡述了本體合并機(jī)制中的兩個(gè)關(guān)鍵技術(shù)，本體聚類和本體聚集(包括積分規(guī)則和階梯規(guī)則)的具體算法及其相關(guān)性質(zhì)；第五部分采用應(yīng)用案例和對(duì)比實(shí)驗(yàn)驗(yàn)證了本文所提出的合并機(jī)制的有效性；第六部分針對(duì)目前工作存在的問題作出總結(jié)并對(duì)規(guī)劃了未來的工作方向.

2 相關(guān)工作

為了促進(jìn)語義web的發(fā)展，國(guó)內(nèi)外學(xué)者對(duì)本體映射、本體集成等相關(guān)問題做出了大量研究并取得了較為滿意的成果.其中，比較成熟的本體合并系統(tǒng)有PROMPT[6]，F(xiàn)CA-Merge[7]，Chimaera[8]和SMART[9]等.PROMPT是一種用于提供本體半自動(dòng)化映射與合并的算法，能夠?qū)Ρ倔w的類、屬性及其關(guān)系進(jìn)行合并；FCA-Merge是一種自底向上的合并方式，運(yùn)用自然語言處理和形式化概念分析，在人工交互的基礎(chǔ)上完成本體合并；Chimaera是支持本體合并和不一致性診斷的系統(tǒng)，它能識(shí)別不同源本體中具有相同語義的概念和概念之間的關(guān)系.SMART是一種不受平臺(tái)限制的基于通用知識(shí)模型的合并系統(tǒng)，在合并的基礎(chǔ)上增加了對(duì)本體不一致性的檢測(cè)，并給出了修復(fù)這些不一致本體的方法.然而這些系統(tǒng)都需要人工參與才能完成，費(fèi)時(shí)又費(fèi)力，尤其是當(dāng)源本體數(shù)量過大時(shí)，系統(tǒng)可能無法精確的對(duì)其進(jìn)行合并.Wang[10]對(duì)現(xiàn)有的本體映射方法進(jìn)行了分類與總結(jié)，認(rèn)為基于機(jī)器學(xué)習(xí)的本體映射技術(shù)能較好的解決由于本體規(guī)模不斷激增給本體映射帶來的問題.在文獻(xiàn)[11]中，作者將概念代數(shù)相關(guān)理論應(yīng)用于本體合并當(dāng)中，并提出了FCA-OntMerg方法.這種方法首先將本體規(guī)范化成統(tǒng)一的概念代數(shù)表示形式，再根據(jù)嚴(yán)格的概念格準(zhǔn)則進(jìn)行合并以生成一個(gè)新本體，實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法在解決本體異構(gòu)問題上的有效性.唐杰等人[12]將映射問題轉(zhuǎn)化為風(fēng)險(xiǎn)決策問題，以貝葉斯決策為理論設(shè)計(jì)了風(fēng)險(xiǎn)最小化的本體自動(dòng)映射模型，實(shí)驗(yàn)證明了該方法具有更高的查準(zhǔn)率和查全率.

在社會(huì)選擇理論方面，投票理論的發(fā)展和判斷聚集的進(jìn)步都為本體合并奠定了基礎(chǔ)[13，14].投票理論是將投票者的個(gè)體偏好聚集為集體偏好的過程，在投票過程中要平等對(duì)待每個(gè)候選者，做到“公平公正公開”，常見的投票聚集方式包括Borda規(guī)則、k-贊成投票規(guī)則、單記移讓式投票等[15，16].Borda計(jì)數(shù)法和贊成投票制都是較為簡(jiǎn)單的聚集方法，每個(gè)候選項(xiàng)根據(jù)選票的數(shù)量來確定最終的贏者.單記移讓式投票較為復(fù)雜，每一輪中都會(huì)淘汰得票數(shù)最少的候選者，最后未被淘汰的候選者即為贏者，在此過程中所有的選票在每一輪的計(jì)票中都會(huì)被計(jì)算到.文獻(xiàn)[17]借助工具OntoCmaps提出了以圖論為基礎(chǔ)的投票機(jī)制，探討了在本體學(xué)習(xí)中概念檢測(cè)的問題.Dietrich F[18]和Pigozzi G[19]致力于研究如何將一群個(gè)體對(duì)命題的判斷聚集為一個(gè)集體決策，即判斷聚集.在判斷聚集中既要保持聚集過程中的公平性，又要關(guān)注聚集結(jié)果的正確性，并由此提出了多種聚集方式，如基于前提/結(jié)論的方法、基于距離的聚集過程等.然而這些聚集方式均要兼顧公平、公正的性質(zhì)，需要平等的對(duì)待每個(gè)候選者并假設(shè)所有投票者擁有的背景知識(shí)相同，這點(diǎn)在本體合并中并不適用，因?yàn)槊總€(gè)本體構(gòu)建者對(duì)領(lǐng)域知識(shí)的認(rèn)知程度并不相同.

3 本體合并框架

本節(jié)主要闡述基于社會(huì)選擇的本體合并框架，首先在3.1節(jié)介紹描述邏輯及問題模型所需的定義和概念，在3.2節(jié)中描述合并框架的組成部分和具體流程.

3.1 問題描述與基本定義

現(xiàn)給定一組有限的候選公式集合Φ和專家(本體構(gòu)建者)集合AgentN={1，2…n}，其中每個(gè)agenti∈N都可以根據(jù)自身的知識(shí)或經(jīng)驗(yàn)構(gòu)建一個(gè)具有一致性的本體，記為Oi?Φ.用CO表示所有具有一致性的本體集合，此集合中不僅包含了O1,O2…On，還包含了其他未被agent所構(gòu)建但具有一致性的本體.本文將O=(O1,O2,…On)∈CON稱為一個(gè)本體組合.由于每個(gè)構(gòu)建者的背景知識(shí)和對(duì)領(lǐng)域認(rèn)知程度不同，本文創(chuàng)新性地為每個(gè)構(gòu)建者都設(shè)置了可信度屬性，可信度用符號(hào)ri∈[0,1]表示，由agenti所構(gòu)建的本體Oi也具有相同的可信度，則R=(r1,r2，…，rn)表示本體組合的可信度向量.基于上述形式化表示，本文分別定義本體聚類和本體聚集兩個(gè)概念：

定義 1. 本體聚類本體聚類是指根據(jù)本體的相似度將可信度相近的本體劃分到一起.已知類別集合C和本體組合O，分類規(guī)則G：O→C能使任意Oi∈O經(jīng)過映射后被劃分到一個(gè)類Cj∈C中.

定義 2. 本體聚集定義本體聚集規(guī)則為將源本體組合O映射到一個(gè)共享的決策本體的過程，即F：CON→2Φ，經(jīng)過聚集規(guī)則生成的決策本體F(O)未必具有一致性.

本文的主要研究思路是通過本體聚類算法舍去可信度較低的本體，從而降低其對(duì)合并精度的影響；再利用聚集規(guī)則對(duì)可信度高的源本體進(jìn)行合并以生成一個(gè)共享的決策本體.精準(zhǔn)的聚類算法能為本體聚集奠定良好基礎(chǔ)，而對(duì)于本體聚集規(guī)則來說，本文希望能夠得到一個(gè)具有一致性的共享本體.

3.2 本體合并流程

從社會(huì)選擇的角度出發(fā)，考慮每個(gè)本體構(gòu)建者的可信度和本體間的相似度，本文構(gòu)建了如圖1所示的面向可信度的異構(gòu)本體合并框架，主要由三個(gè)部分組成，分別是本體聚類器和本體聚集器和決勝規(guī)則.本體聚類器是本體聚集的前提，舍棄低可信度本體從而為合并本體的精度提供了保障，它可以根據(jù)每個(gè)本體的可信度和本體間的相似度對(duì)其進(jìn)行聚類；而本體聚集器則是通過某種聚集規(guī)則對(duì)源本體進(jìn)行合并以期形成一個(gè)共享的決策本體；若經(jīng)過聚集后有多個(gè)符合要求的本體則需要借助決勝規(guī)則來確定唯一F(O)，本文不詳細(xì)介紹此規(guī)則.

圖1 基于社會(huì)選擇的本體合并框架Fig.1 Framework for ontology merging based on social choice

根據(jù)圖1所示的本體合并框架，本文所提出的本體合并機(jī)制具體的工作流程有如下幾個(gè)步驟：

1)每位agent根據(jù)自己的經(jīng)驗(yàn)和知識(shí)背景構(gòu)建出特定領(lǐng)域的本體；

2)基于描述邏輯，將本體規(guī)范成統(tǒng)一的形式O=以便于后續(xù)工作的開展；

3)本體分類器依據(jù)設(shè)定好的聚類算法和本體的可信度向量R對(duì)本體組合O中的源本體進(jìn)行聚類，形成k個(gè)集合.為了便于計(jì)算，本文令k=2，設(shè)定了2個(gè)可信度集合，分別為高可信度集合OH和低可信度集合OL；

4)刪除可信度低的本體集合OL，保留高可信度本體，令本體組合O=OH；

5)最后對(duì)高可信度本體組合O使用本體聚集器和決勝規(guī)則以生成唯一的共享決策本體F(O).

4 本體合并過程

對(duì)本體進(jìn)行聚類有助于獲得更準(zhǔn)確的本體聚集結(jié)果，本小節(jié)將詳細(xì)介紹本體合并框架中兩個(gè)重要的組成部分，本體聚類器和本體聚集器.

4.1 本體聚類器

本體聚類器一方面要根據(jù)每個(gè)本體的可信度對(duì)其進(jìn)行分類，目標(biāo)是形成兩類本體集合OH和OL，分別表示高可信度本體集合和低可信度本體集合；另一方面也要考慮本體之間的相似度，目標(biāo)是將相似度高的本體劃分為一類.為了衡量?jī)蓚€(gè)本體之間的相似度，現(xiàn)定義距離函數(shù)d：2Φ×2Φ→+∪{0}表示兩個(gè)本體之間的距離，距離越小則表示兩個(gè)本體越相似.常用的距離函數(shù)有海明距離、歐式距離和曼哈頓距離[21，22]，他們都滿足

1)非負(fù)性：d(Oi,Oj)≥0；

2)同一性：d(Oi,Oj)=0若Oi=Oj；

3)對(duì)稱性：d(Oi,Oj)=d(Oj,Oi)

本文采用海明距離，即將本體Oi轉(zhuǎn)化成Oj需要改變最少的公式個(gè)數(shù).理想情況下，我們希望集合OH中的本體盡可能的相似，而異類本體盡可能不同.兼顧本體可信度和本體相似度，本文設(shè)計(jì)了異構(gòu)本體聚類器，聚類算法具體流程如Algorithm 1所示.

算法1.Distance-based Ontology Clustering for Reliability

Input：O,R

Output：OH，OL

1OrderontologyprofileOintheascendingorderaccordingtoreliabilityvectorR

3λH=OλL

4repeat

5OH={ontologyOhwithhighestreliability}

6OL={ontologyOhwithhighestreliability}

7fori:1→ndo

8 compute the distance betweenOlandOidli;

9 compute the distance betweenOhandOidhi;

10if(dli≥dhi)then

11OH←OH∪{Oi}

12elseOL←OL∪{Oi}

13endif

14endfor

16Oh←Oh-1withthesecondhighestreliability

17endif

其中第1行是對(duì)本體集合進(jìn)行初始化，將本體按照可信度進(jìn)行升序排序.第2-3行根據(jù)可信度高低程度粗略的將本體分為兩類，顯然這樣的分類是不夠精確的因?yàn)闆]有考慮本體間的相似度.在第7-14行計(jì)算每個(gè)本體Oi與最高可信度本體Oh和最低可信度本體Ol的距離，并根據(jù)距離遠(yuǎn)近確定其所在的類.第15-17行表示，若存在大量可信度低的本體與Oh相似，則說明Oh可能不準(zhǔn)確，因此選取可信度次高的本體作為類中心并進(jìn)行迭代更新，直到OH中包含的本體可信度較高同時(shí)類內(nèi)本體較為相似時(shí)則停止更新(第18行).

定理1.異構(gòu)本體聚類算法的時(shí)間復(fù)雜度為O(n*log2n+nt)，其中t是循環(huán)次數(shù).

證明：根據(jù)本體可信度向量R，我們采用堆排序?qū)Ρ倔w集合中的n個(gè)源本體進(jìn)行升序排序，時(shí)間復(fù)雜度為O(n*log2n).內(nèi)循環(huán)(第7-14行)中分別計(jì)算本體Oi與類中心Oh和Ol的距離并確定其所在類別，共執(zhí)行了3n次；在外層循環(huán)中，由于設(shè)置迭代次數(shù)為t，那么執(zhí)行的頻率為t*(3+3n)；綜上所述，算法的時(shí)間復(fù)雜度T(n)=O(n*log2n)+t(3+3n)=O(n*log2n)+O(nt)=O(n*log2n+nt).

面向可信度的本體聚類算法簡(jiǎn)單、直觀，綜合考慮了異構(gòu)本體的可信度以及本體間的相似程度，減少了類中心本體選擇不當(dāng)對(duì)聚類結(jié)果造成的不利影響；但對(duì)于本體規(guī)模較大的情況，其時(shí)間和空間復(fù)雜度較高，還需要在后續(xù)工作中進(jìn)一步優(yōu)化.

4.2 本體聚集

借鑒社會(huì)選擇理論中的聚集規(guī)則，本文對(duì)其進(jìn)行總結(jié)與分類，并在原有的聚集規(guī)則之上兼顧本體可信度和本體相似度，形成了積分聚集規(guī)則和階段性淘汰規(guī)則兩種方式.

4.2.1 積分聚集規(guī)則

積分聚集規(guī)則通過函數(shù)score:CO→，將具有一致性的本體集合映射到一個(gè)實(shí)數(shù)集.每個(gè)一致性本體根據(jù)積分函數(shù)都可以獲得某個(gè)得分，積分聚集規(guī)則的最終目標(biāo)是將得分最高的本體作為共享本體，即

F(O)=agrmaxco∈COscore(CO)

在積分聚集規(guī)則中，最終生成的共享決策本F(O)體必然具有一致性.本文介紹兩種積分聚集規(guī)則，分別是基于距離的得分規(guī)則和基于可信度的得分規(guī)則.

1)基于距離的得分規(guī)則

基于距離的得分規(guī)則將每個(gè)本體的得分定義為與本體集合O距離的相反數(shù)，即

score(CO)=-d(CO,O)=-∑i∈Nd(CO,Oi)

由上述公式可知，若score(CO)越大，則它與本體集合O的距離越小.換言之，CO與其他本體相似越高，更容易得到agent的認(rèn)可；反之CO得分越低，與其他本體相似程度越低.

2)基于可信度的得分規(guī)則

最簡(jiǎn)單的基于可信度的得分規(guī)則定義每個(gè)本體的得分即為自身的可信度，將可信度最高的本體作為共享本體.顯然這種得分規(guī)則過于簡(jiǎn)單且沒有考慮CO中的其他本體.因?yàn)榭尚哦雀叩谋倔w構(gòu)建者對(duì)領(lǐng)域認(rèn)知也可能會(huì)出錯(cuò)，而可信度低的構(gòu)建者也有可能構(gòu)建出比較完備的一致性本體.為了解決上述問題，首先定義標(biāo)志

用于判斷本體Oi中是否包含公式φ；那么每個(gè)公式的可信度記為r(φ)=∑i∈Nri·xOi(φ).因此，基于可信度的得分規(guī)則將本體的得分定義為它所包含的所有公式可信度之和，即

score(CO)=∑φ∈COr(φ)

若CO的得分越高則表明該本體包含的公式可信度越高，這在一定程度上克服了直接選擇可信度最高本體作為共享本體的弊端.

定理 2.當(dāng)同等對(duì)待所有本體構(gòu)建者，即ri=1對(duì)任意i∈N成立時(shí)，基于海明距離的得分規(guī)則就是基于可信度的得分規(guī)則.

證明：一方面，海明距離d(Oi,Oj)=|Oi|-|Oi∩Oj|定義為兩個(gè)本體間相異公式的個(gè)數(shù).那么，基于距離的得分規(guī)則可以表示為

Fdis(O)=argmaxco∈co(-∑i∈Nd(CO,Oi))

=argminco∈co∑i∈Nd(CO，Oi)

=argminco∈co∑i∈N(|CO|-|Oi∩CO|)

根據(jù)定義，基于距離的得分規(guī)則的最終目標(biāo)是尋找能使∑i∈Nd(CO,Oi)最小的一致性本體，經(jīng)過公式推理可以將原目標(biāo)轉(zhuǎn)換為求使得∑i∈N|Oi∩CO|最大的一致性本體.另一方面，當(dāng)ri=1對(duì)任意i∈N成立時(shí)有

Frel(O)=argmaxCO∈CO(∑φ∈COr(φ)

=argmaxCO∈CO(∑φ∈CO∑φ∈NxOi(φ)

因此基于可信度的得分聚集規(guī)則目標(biāo)是獲得能使∑φ∈CO∑i∈NxOi(φ)最大的一致性本體.又因?yàn)閨Oi∩CO|=∑φ∈COxOi(φ)，所以命題得證.

例1.現(xiàn)有3個(gè)agent構(gòu)成的本體組合O={O1,O2,O3}，并且他們都共同認(rèn)可Tbox中的公式：C3=C1∩C2.由于agent的背景知識(shí)和經(jīng)驗(yàn)不同，對(duì)于Abox中的對(duì)象a也有不同的觀點(diǎn)，如表1所示.根據(jù)Tbox中的約束條件，則一致性本體集合CO={CO1,CO2,CO3,CO4}.

表1 本體及其得分Table 1 Formulas in ontologies and their scores

其中，CO1={Tbox∪{C1(a),C2(a),C3(a)}}

CO2={Tbox∪{C1(a),┐C2(a),┐C3(a)}}

CO3={Tbox∪{┐C1(a),C2(a),┐C3(a)}}

CO4={Tbox∪{┐C1(a),┐C2(a),┐C3(a)}}

首先根據(jù)xOi(φ)，若本體中包含φ則記為1分，否則記0分.每個(gè)公式的可信度得分為r(φ)=∑i∈NxOi(φ)，例如r(C1(a))=0+0+1.每個(gè)一致性本體的得分score(CO)=∑φ∈COr(φ)，例如score(CO1)=1+1+0.可以發(fā)現(xiàn)，|Oi∩CO|=∑φ∈OxOi(φ)，例如|O1∩CO1|=0+0+0=∑φ∈CO1xO1(φ).因此，F(xiàn)dis(O)=Frel(O)={CO4}.

4.2.2 階梯性淘汰規(guī)則

階梯過程是一種經(jīng)過多輪次篩選從而產(chǎn)生共享本體的聚集方式.由這種方式生成的共享本體未必具有一致性，需要通過某種約束來達(dá)到具有一致性的目的.為了使最終本體具有一致性，在每一輪中都保留具有可滿足性的概念或斷言；刪除或修改不可滿足的概念.

1)基于優(yōu)先規(guī)則的多階段淘汰制

基于支持度的優(yōu)先規(guī)則：φψ?

基于可信度的優(yōu)先規(guī)則：φψ?r(φ)≥r(ψ).

這種聚集方式首先根據(jù)上述定義的優(yōu)先規(guī)則對(duì)Φ中的公式進(jìn)行排序，接著在以后的每個(gè)階段中都只考慮一個(gè)公式.首輪中考慮優(yōu)先級(jí)最高的公式并將其加入共享決策本體F(O)中；然后再根據(jù)優(yōu)先級(jí)依次考慮剩余公式，若添加當(dāng)前公式至F(O)會(huì)導(dǎo)致已形成的決策本體不一致，那么刪除或修改此公式，繼續(xù)考慮下一個(gè)公式，直到遍歷完所有的公式為止.我們可以將此過程用形式化語言表示，即F(O)是一個(gè)公式集合Δ?Φ滿足以下條件：

1)Δ={φ|φ∈O1∪O2…∪On}；

2){φ∈Δ|φψ}∪{ψ}是具有一致性的.

定理 3.基于優(yōu)先規(guī)則的階段淘汰制具有一致贊同性.

2)基于推理的兩階段法

本文將判斷聚集中的基于前提(或結(jié)論)的聚集過程應(yīng)用在本體當(dāng)中，得到基于Tbox(orAbox)的本體聚集規(guī)則.這兩種方式的主要步驟相似，這里只介紹一種基于Abox推理的本體聚集規(guī)則.在這之前先介紹兩種較為簡(jiǎn)單、常見的聚集函數(shù)，分別是絕對(duì)多數(shù)規(guī)則和基于距離的聚集規(guī)則.絕對(duì)多數(shù)規(guī)則是指當(dāng)接受一個(gè)公式φ∈Φ的agent個(gè)數(shù)超過半數(shù)時(shí)，φ會(huì)被最終結(jié)果接受，即

基于距離的聚集規(guī)則在3.2.1節(jié)中以介紹，這里不再贅述.那么，基于Abox推理的本體聚集規(guī)則具體的過程可用如下算法表示：

算法2.Abox-based Approach for Ontology Aggregation

Input：O1,O2，…，On

Output：O

1Abox←?

2fori:1→ndo

4i←i+1

5endfor

7forj:1→ndo

9repairontologyOjforconsistency

10endfor

11F(O)=argminCO∈CO∑i∈Nd(Oi,O)

第2-6行首先用絕對(duì)多數(shù)規(guī)則對(duì)本體組合中的Abox進(jìn)行聚集，得出結(jié)果為FA(O)；第7-10行中每個(gè)agent將源本體中的Abox改變?yōu)镕(O)，并根據(jù)本體一致性進(jìn)行修正；最后對(duì)這些修正后的本體組合使用“基于距離的距離規(guī)則”以形成最終的共享本體(第11行).在本體不一致修正時(shí)分為兩個(gè)步驟，首先找出最小不一致集合Δ={φ|φ∈Tbox}，即Δ∪FA(O)具有不一致性；然后刪除或修改集合Δ.當(dāng)采用基于Abox的兩階段方法時(shí)，Abox和Tbox相互獨(dú)立，對(duì)Abox中的公式運(yùn)用絕對(duì)多數(shù)規(guī)則得到FA(O)，而Tbox中的公式取決于FA(O).因此，一致贊同性對(duì)于Abox中的公式仍然成立，但Tbox中的公式未必滿足.若希望獲得具有一致贊同性的聚集規(guī)則，需要對(duì)其中的公式加以約束.

定理 4.令Tbox=T1∪{p}={a1,…,al}∪{p}且β∈Abox，當(dāng)基于Abox的兩階段法滿足約束xO(α1)∧…∧xO(αl)∧xO(p)?xO(β)時(shí)具有一致贊同性.

①當(dāng)β∈FA(O)時(shí)，根據(jù)算法2中第7-11行，得到β∈F(O)，也就是xF(O)(β)=1，又因?yàn)閤F(O)(α1)∧…∧xF(O)(αl)∧xF(O)(p)?xF(O)(β)，所以xF(O)(p)=1，命題得證.

∑i∈Nd(Oi,F(O))=

考慮這樣一個(gè)本體F(O)′使得p∈F(O),xF(O)′(φ)=xF(O)(φ)對(duì)任意φ∈φ/{p}成立.那么

∑i∈Nd(Oi,F(O)′)=

這與∑i∈Nd(Oi,F(O))最小矛盾，因此假設(shè)不成立，原命題成立.

5 應(yīng)用案例與分析

為了驗(yàn)證本文提出的本體合并機(jī)制的有效性，現(xiàn)假設(shè)所有agents都共同認(rèn)可Tbox中的公式：C4=(C1∪C2)∩C3,C5?┐C4，C1,C2,C3,C4,C5分別表示5個(gè)原子概念.若存在論域中的一個(gè)對(duì)象a，那么Abox中的公式可被構(gòu)建為C1(a),C2(a),C3(a),C4(a),C5(a).表1根據(jù)定義

將6個(gè)agents構(gòu)建的Abox表示為0-1向量.

表2 6個(gè)構(gòu)建者提供的本體斷言集及可信度Table 2 Aboxes and reliabilities of 6 agents

圖2 本體聚類器的分類結(jié)果Fig.2 Results of ontology clustering

將本文異構(gòu)本體聚類算法和k-means聚類算法[23]進(jìn)行比較.k-means算法隨機(jī)選擇k個(gè)樣本作為初始點(diǎn)，以最小化平方誤差為目的將每個(gè)點(diǎn)劃入最近的簇，然后重新計(jì)算每個(gè)簇的均值直到簇不發(fā)生改變?yōu)橹?令聚類簇?cái)?shù)k=2，圖3是僅針對(duì)本體間相似度進(jìn)行分類的聚類結(jié)果，而圖4是只考慮本體的可信度的聚類結(jié)果.

通過計(jì)算DBI(Davies-Bouldin Index)可以評(píng)判分類性能的好壞，DB指數(shù)越小，分類性能越好.我們從“本體可信度”和“本體相似度”兩個(gè)屬性來對(duì)上述3種分類結(jié)果進(jìn)行比較，對(duì)比結(jié)果如圖5所示.

圖3 k-means聚類結(jié)果(本體相似度)Fig.3 Results of k-means for similarity圖4 k-means的聚類結(jié)果(可信度)Fig.4 Results of k-means for reliability

圖5 分類算法性能對(duì)比結(jié)果Fig.5 Performance comparison of classification algorithm

方法1為僅考慮本體相似度的k-means聚類算法，方法2是僅考慮本體可信度的k-means聚類算法，而方法3是本文提出的兼顧可信度和相似度的本體聚類算法.通過對(duì)比可以發(fā)現(xiàn)，盡管本方法在可信度分類方面的性能不及方法2，但總體來說分類性能介于三者之間，能夠很好的兼顧相似度和可靠性兩個(gè)屬性.

在本體聚類的基礎(chǔ)上將置信度低的本體舍去，那么在本體聚集時(shí)O={O4,O1,O3}.根據(jù)Tbox中的約束條件，具有一致性的本體集合CO如表3所示.

表3 一致性的本體集合中的斷言集Table 3 Aboxes of ontologies in CO

分別用積分規(guī)則和階梯性淘汰規(guī)則對(duì)異構(gòu)源本體進(jìn)行聚集. 基于海明距離的積分規(guī)則得到的結(jié)果為F(O)={CO4}={O1}，因?yàn)?/p>

score(O1)=-2=argmaxco∈CO(∑i∈Nd(CO,Oi))

基于置信度的積分規(guī)則得F(O)={O1}，因?yàn)?/p>

score(O1)=7.05=argmaxco∈CO(∑φ∈COr(φ))

多階段淘汰規(guī)則得到的結(jié)果為F(O)=CO4=O1，因?yàn)椴徽摳鶕?jù)支持度或是可靠性都有C4(α)C5(α)，所以優(yōu)先考慮將C4(α)加入F(O)中，得F(O)={O1}.基于Abox的兩階段聚集法得到F(O)?{O1,O4}，首先根據(jù)絕對(duì)多數(shù)原則得到FA(O)={C2(α),C3(α)}，繼而得到

∑i∈Nd(Oi,O1)=∑i∈Nd(Oi,O4)=1

=argminCO∈CO∑i∈Nd(CO,Oi)

若我們最終只想獲得唯一的決策本體，那么需要在原有的聚集規(guī)則中結(jié)合決勝規(guī)則，這將是未來的研究方向之一.

6 總 結(jié)

本體合并是促進(jìn)語義web發(fā)展的關(guān)鍵技術(shù)之一，為了解決目前存在的語義異構(gòu)問題，以社會(huì)選擇為理論依據(jù)，將不同agent構(gòu)建的異構(gòu)本體(個(gè)體偏好)通過本體合并機(jī)制生成一個(gè)頂層本體(集體決策)以期形成一個(gè)更大的語義共享空間.由于不同agent的背景知識(shí)不同，所構(gòu)建的本體也具有不同的可靠性.因此，本文針對(duì)異構(gòu)本體的可信度，設(shè)計(jì)了本體聚類器和本體聚集器，本體聚類器為本體聚集器縮減了本體聚集規(guī)模，從而提高了本體合并精度.然而還存在著一些不足之處使得這種合并機(jī)制無法在真實(shí)場(chǎng)景中應(yīng)用.一方面，這種基于距離的本體分類器的時(shí)間和空間復(fù)雜度都會(huì)隨著本體數(shù)量的擴(kuò)大而劇增；另一方面，本體聚集器的設(shè)計(jì)中還未考慮社會(huì)選擇中的其他重要性質(zhì)，例如中立性、單調(diào)性和獨(dú)立性等.未來的主要工作將致力于設(shè)計(jì)一種決勝規(guī)則和完善這兩方面的不足以不斷提升本體合并機(jī)制，并將此機(jī)制用于描述語義web服務(wù)，使具有計(jì)算機(jī)可理解的語義.