一種基于社會選擇的本體聚類與合并機制

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

1(揚州大學 信息工程學院，江蘇 揚州 225009)2(南京大學 軟件新技術(shù)國家重點實驗室，南京 210093)3(揚州大學 廣陵學院，江蘇 揚州 225000)

1 引 言

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

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

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

2 相關(guān)工作

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

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

3 本體合并框架

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

3.1 問題描述與基本定義

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

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

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

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

3.2 本體合并流程

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

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

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

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

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

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

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

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

4 本體合并過程

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

4.1 本體聚類器

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

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

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

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

本文采用海明距離，即將本體Oi轉(zhuǎn)化成Oj需要改變最少的公式個數(shù).理想情況下，我們希望集合OH中的本體盡可能的相似，而異類本體盡可能不同.兼顧本體可信度和本體相似度，本文設(shè)計了異構(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行是對本體集合進行初始化，將本體按照可信度進行升序排序.第2-3行根據(jù)可信度高低程度粗略的將本體分為兩類，顯然這樣的分類是不夠精確的因為沒有考慮本體間的相似度.在第7-14行計算每個本體Oi與最高可信度本體Oh和最低可信度本體Ol的距離，并根據(jù)距離遠近確定其所在的類.第15-17行表示，若存在大量可信度低的本體與Oh相似，則說明Oh可能不準確，因此選取可信度次高的本體作為類中心并進行迭代更新，直到OH中包含的本體可信度較高同時類內(nèi)本體較為相似時則停止更新(第18行).

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

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

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

4.2 本體聚集

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

4.2.1 積分聚集規(guī)則

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

F(O)=agrmaxco∈COscore(CO)

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

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

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

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

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

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

最簡單的基于可信度的得分規(guī)則定義每個本體的得分即為自身的可信度，將可信度最高的本體作為共享本體.顯然這種得分規(guī)則過于簡單且沒有考慮CO中的其他本體.因為可信度高的本體構(gòu)建者對領(lǐng)域認知也可能會出錯，而可信度低的構(gòu)建者也有可能構(gòu)建出比較完備的一致性本體.為了解決上述問題，首先定義標志

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

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

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

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

證明：一方面，海明距離d(Oi,Oj)=|Oi|-|Oi∩Oj|定義為兩個本體間相異公式的個數(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ī)則的最終目標是尋找能使∑i∈Nd(CO,Oi)最小的一致性本體，經(jīng)過公式推理可以將原目標轉(zhuǎn)換為求使得∑i∈N|Oi∩CO|最大的一致性本體.另一方面，當ri=1對任意i∈N成立時有

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

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

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

例1.現(xiàn)有3個agent構(gòu)成的本體組合O={O1,O2,O3}，并且他們都共同認可Tbox中的公式：C3=C1∩C2.由于agent的背景知識和經(jīng)驗不同，對于Abox中的對象a也有不同的觀點，如表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分.每個公式的可信度得分為r(φ)=∑i∈NxOi(φ)，例如r(C1(a))=0+0+1.每個一致性本體的得分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)生共享本體的聚集方式.由這種方式生成的共享本體未必具有一致性，需要通過某種約束來達到具有一致性的目的.為了使最終本體具有一致性，在每一輪中都保留具有可滿足性的概念或斷言；刪除或修改不可滿足的概念.

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

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

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

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

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

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

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

2)基于推理的兩階段法

本文將判斷聚集中的基于前提(或結(jié)論)的聚集過程應(yīng)用在本體當中，得到基于Tbox(orAbox)的本體聚集規(guī)則.這兩種方式的主要步驟相似，這里只介紹一種基于Abox推理的本體聚集規(guī)則.在這之前先介紹兩種較為簡單、常見的聚集函數(shù)，分別是絕對多數(shù)規(guī)則和基于距離的聚集規(guī)則.絕對多數(shù)規(guī)則是指當接受一個公式φ∈Φ的agent個數(shù)超過半數(shù)時，φ會被最終結(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行首先用絕對多數(shù)規(guī)則對本體組合中的Abox進行聚集，得出結(jié)果為FA(O)；第7-10行中每個agent將源本體中的Abox改變?yōu)镕(O)，并根據(jù)本體一致性進行修正；最后對這些修正后的本體組合使用“基于距離的距離規(guī)則”以形成最終的共享本體(第11行).在本體不一致修正時分為兩個步驟，首先找出最小不一致集合Δ={φ|φ∈Tbox}，即Δ∪FA(O)具有不一致性；然后刪除或修改集合Δ.當采用基于Abox的兩階段方法時，Abox和Tbox相互獨立，對Abox中的公式運用絕對多數(shù)規(guī)則得到FA(O)，而Tbox中的公式取決于FA(O).因此，一致贊同性對于Abox中的公式仍然成立，但Tbox中的公式未必滿足.若希望獲得具有一致贊同性的聚集規(guī)則，需要對其中的公式加以約束.

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

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

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

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

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

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

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

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

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

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

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

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

通過計算DBI(Davies-Bouldin Index)可以評判分類性能的好壞，DB指數(shù)越小，分類性能越好.我們從“本體可信度”和“本體相似度”兩個屬性來對上述3種分類結(jié)果進行比較，對比結(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 分類算法性能對比結(jié)果Fig.5 Performance comparison of classification algorithm

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

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

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

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

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

基于置信度的積分規(guī)則得F(O)={O1}，因為

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

多階段淘汰規(guī)則得到的結(jié)果為F(O)=CO4=O1，因為不論根據(jù)支持度或是可靠性都有C4(α)C5(α)，所以優(yōu)先考慮將C4(α)加入F(O)中，得F(O)={O1}.基于Abox的兩階段聚集法得到F(O)?{O1,O4}，首先根據(jù)絕對多數(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é)

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