廖建新，劉秀磊，朱曉民，孫海峰，王敬宇

(1.北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100876； 2. 東信北郵信息技術(shù)有限公司，北京 100191)

1 引言

隨著本體的廣泛應(yīng)用，表示相似領(lǐng)域共享概念模型的大部分本體往往是由不同背景知識(shí)的工程師使用各種術(shù)語(yǔ)構(gòu)造和維護(hù)。這些表示相似領(lǐng)域的不同本體之間的異構(gòu)性阻礙了應(yīng)用系統(tǒng)對(duì)知識(shí)的共享、重用和互操作。本體匹配則是解決本體異構(gòu)問(wèn)題的方法之一。本體匹配在本體工程、生物醫(yī)學(xué)、P2P信息共享、Web服務(wù)組合以及語(yǔ)義物聯(lián)網(wǎng)等領(lǐng)域有著廣泛的應(yīng)用。

OWL（ontology Web language）是目前較為流行的本體描述語(yǔ)言。使用OWL表示的本體由各種構(gòu)造器和公理構(gòu)成。文獻(xiàn)[1～3]中一些方法通過(guò)使用詞法（lexical）分析和語(yǔ)義（semantic）分析的方法匹配本體。在語(yǔ)義分析階段，它們通常將詞法分析階段的結(jié)論輸入推理機(jī)（reasoners）直接產(chǎn)生實(shí)體間的匹配[4,5]，或基于推理機(jī)的推論計(jì)算實(shí)體間的相似性[6～8]。因此，目前基于語(yǔ)義分析的本體匹配方法多是通過(guò)推理機(jī)利用本體中的語(yǔ)義信息。然而，它們并沒(méi)有充分探索本體中的構(gòu)造器和公理（比如?、∩、∪、?等）所蘊(yùn)含的語(yǔ)義信息。例如有如下2組公理：

如果直接應(yīng)用推理機(jī)，這2組公理可得到相同的推論，即Book ? Publication，然而這些公理并不表示相同的語(yǔ)義信息。因此，基于推理機(jī)的語(yǔ)義分析方法并不能夠完全反映本體中的語(yǔ)義，它僅反映了這些語(yǔ)義的推論。

基于以上考慮，本文擴(kuò)展了結(jié)構(gòu)包含推理算法以分析本體的語(yǔ)義信息。該方法首先剖析組成本體的各種構(gòu)造器和公理（比如?、∩、∪、?等），基于描述邏輯和代數(shù)集合中的定理構(gòu)建實(shí)體的范式（normal forms），這使得本體里蘊(yùn)含的語(yǔ)義信息和詞法信息能夠容易讀出；然后通過(guò)調(diào)節(jié)實(shí)體間被允許的差異程度比較2個(gè)實(shí)體范式之間的句法結(jié)構(gòu)以產(chǎn)生實(shí)體間匹配。

2 相關(guān)工作

隨著語(yǔ)義Web和大量基于本體應(yīng)用的發(fā)展，本體匹配已經(jīng)成為目前的研究熱點(diǎn)之一。文獻(xiàn)[1～3]調(diào)查了各種本體匹配方法，從不同方面對(duì)它們進(jìn)行歸類，并提出在本體匹配中可利用的信息。它們包括：詞法信息、結(jié)構(gòu)信息、語(yǔ)義信息、外部數(shù)據(jù)信息和個(gè)體信息。通常不同的本體匹配方法通過(guò)各種信息技術(shù)使用上述中的一種或多種信息進(jìn)行匹配。

這些信息技術(shù)包括系數(shù)的計(jì)算（coefficient computation）[9]、機(jī)器學(xué)習(xí)（machine learning）[10,11]、合成理論（hybrid methods）[12]、圖匹配（graph matching）[13]、馬爾科夫網(wǎng)（Markov network）[14]、向量空間模型（vector space models）[15]、優(yōu)化技術(shù)（optimization techniques）[16,17]、貝葉斯決策理論（Bayesian decision theory）[18]以及各種推理機(jī)制（reasoning mechanisms）[6,7,9,19]等。

本體中公理和構(gòu)造器不僅含有本體的結(jié)構(gòu)（structural）信息，也蘊(yùn)含了本體的語(yǔ)義信息。本文僅關(guān)注于本體匹配系統(tǒng)對(duì)語(yǔ)義信息的使用方法。根據(jù)歸約（deductions）規(guī)則，本體匹配中的語(yǔ)義分析方法主要分為2類：可滿足性問(wèn)題（propositional satisfiability problem）和描述邏輯推理（description logics reasoning）。

可滿足性問(wèn)題的決策器（deciders）通常輸入交范式（conjunctive normal forms），然后判定輸入范式之間的語(yǔ)義關(guān)系，但交范式并不能很好地處理一些OWL本體中的構(gòu)造器和公理，比如并（disjunction）、完全否（full negation）和完全存在限制（full existential restriction）等，這導(dǎo)致了基于交范式的本體匹配方法（比如 S-Match[4]）可被用在簡(jiǎn)單的本體語(yǔ)言表示的本體匹配中，但并不被用于OWL表示的本體匹配中。

通常，描述邏輯推理方法采用能夠解釋并、完全否和完全存在限制等的表演算法（tableau algorithms），所以使用推理機(jī)推論的方法（比如ILIADS[6]（integrated learning in alignment of data and schema）和ALOWS[7]）能處理在OWL本體中的各種句法元素。

ILIADS通過(guò)啟發(fā)式算法抽取了有限的本體公理，并基于這些公理使用推理機(jī)進(jìn)行推理，因此它并沒(méi)有使用來(lái)自本體的所有公理進(jìn)行推理，這有可能導(dǎo)致某些語(yǔ)義的丟失，甚至導(dǎo)致不正確的推論。ALOWS通過(guò)在所有的公理上直接使用推理機(jī)來(lái)解決該問(wèn)題。CtxMatch[19]將表達(dá)式提交到基于表演算法的推理機(jī)，并直接將推理機(jī)的推論作為實(shí)體間的關(guān)系。S-Match不僅使用推理機(jī)制，而且提供了 2種不同的概念表示：標(biāo)簽概念和實(shí)體概念。標(biāo)簽概念僅關(guān)于實(shí)體標(biāo)簽里上下文無(wú)關(guān)的單詞詞義，它簡(jiǎn)單地表示了標(biāo)簽的詞法信息。實(shí)體概念與上下文相關(guān)，它表達(dá)了一定的邏輯關(guān)系。S-Match通過(guò)使用從根實(shí)體到需要計(jì)算實(shí)體之間所有實(shí)體標(biāo)簽的交計(jì)算實(shí)體概念。

ASMOV[9]（automated semantic matching ontologies with verification）首先獲得本體之間的匹配，然后檢驗(yàn)這些匹配以確保它們不包含任何不一致的語(yǔ)義。ASMOV中的語(yǔ)義匹配是基于結(jié)構(gòu)信息的翻譯，實(shí)際上它依然采用相似性方法計(jì)算來(lái)自不同本體的實(shí)體間的匹配，僅使用語(yǔ)義的方法檢驗(yàn)獲得的本體匹配，以提高系統(tǒng)的精度。

綜上所述，目前大部分使用語(yǔ)義信息的本體匹配方法并沒(méi)有分析公理和構(gòu)造器中的語(yǔ)義，而僅是使用推理機(jī)的推論。本文提出的擴(kuò)展結(jié)構(gòu)包含推理算法的方法（DLOM）分析了公理和構(gòu)造器中的各種元素使得本體的語(yǔ)義顯示地表現(xiàn)出來(lái)，比較了表現(xiàn)語(yǔ)義的實(shí)體范式以推理來(lái)自不同本體的實(shí)體間的匹配。

3 背景知識(shí)和系統(tǒng)架構(gòu)

3.1 背景知識(shí)

隨著語(yǔ)義Web的發(fā)展，OWL成為目前較為流行的本體描述語(yǔ)言，依據(jù)表達(dá)能力，它被劃分為 3個(gè)表達(dá)層次：OWL-Lite、OWL-DL和OWL-Full。OWL-Lite對(duì)應(yīng)于描述邏輯SHIF(D)，具有概念分層和簡(jiǎn)單限制，雖然推理服務(wù)相對(duì)有效，但表達(dá)能力較弱。OWL-DL對(duì)應(yīng)于描述邏輯SHOIN (D)，其表達(dá)能力強(qiáng)，推理服務(wù)相對(duì)有效。OWL-Full的表達(dá)能力最強(qiáng)，但它的語(yǔ)義具有邏輯不可判定性。因此，相對(duì)于 OWL-Lite和 OWL-Full，OWL-DL應(yīng)用更為廣泛。本文只關(guān)注于以 OWL-DL表示的本體之間的匹配。

OWL-DL的語(yǔ)義可翻譯（interpretation）成知識(shí)庫(kù)（knowledge base），因此當(dāng)匹配本體時(shí)為了使用蘊(yùn)含的語(yǔ)義信息，僅需分析其對(duì)應(yīng)的知識(shí)庫(kù)。知識(shí)庫(kù)通常包含3部分：TBox、PBox和ABox。其中TBox是概念公理的集合；PBox是屬性公理的集合；ABox是個(gè)體公理的集合[20]。本文不關(guān)注個(gè)體信息，因此僅分析知識(shí)庫(kù)中的TBox和PBox，同時(shí)也假設(shè)在本體里沒(méi)有對(duì)實(shí)體進(jìn)行圈定義（cyclical definition），比如 Human≡People ∩ ?hasParent. Human。

在本體匹配過(guò)程中，有必要匹配來(lái)自不同本體的數(shù)據(jù)屬性（datatype property）和對(duì)象屬性（object property）。因此本文不區(qū)分本體里的數(shù)據(jù)屬性和對(duì)象屬性，統(tǒng)稱它們?yōu)閷傩裕ɑ蚪巧??；谝陨峡紤]，需將 OWL-DL表示的本體中的數(shù)據(jù)屬性轉(zhuǎn)化為對(duì)象屬性，轉(zhuǎn)化過(guò)程如下。

1) 轉(zhuǎn)換數(shù)據(jù)類型屬性的范圍（range），即數(shù)據(jù)類型（datatype），為概念（concepts）。

2) 轉(zhuǎn)換數(shù)據(jù)類型的值（value of datatypes）為相應(yīng)概念的個(gè)體（individuals）。

3) 轉(zhuǎn)換數(shù)據(jù)類型屬性（datatype properties）為對(duì)象類型（object properties）。

由于OWL-DL所對(duì)應(yīng)的SHOIN (D)使用數(shù)據(jù)值、數(shù)據(jù)類型和數(shù)據(jù)屬性擴(kuò)展SHOIN而得到。因此，轉(zhuǎn)換后的本體句法與SHOIN句法相同。本文以下內(nèi)容均指轉(zhuǎn)換后的本體。

3.2 系統(tǒng)架構(gòu)

本節(jié)簡(jiǎn)述了原型系統(tǒng)DLOM（如圖1所示）。DLOM系統(tǒng)主要分為2個(gè)階段：候選計(jì)算階段（圖1中豎虛線左側(cè)所示）和匹配推理階段（圖1中豎虛線右側(cè)所示）。它輸入2個(gè)OWL-DL表示的本體，輸出一組來(lái)自不同本體的實(shí)體間的匹配。本文使用2個(gè)樣例本體解釋各種示例，它們分別來(lái)自于OAEI(ontology alignment evaluation initiative) 2009標(biāo)準(zhǔn)測(cè)試集的101文件夾和302文件夾。為了表示樣例本體中的實(shí)體，采用＜101 (或302)：實(shí)體標(biāo)簽＞的方式。

候選計(jì)算階段與文獻(xiàn)[7]中的詞法分析階段相同。詞法分析器的主要目的是分析本體中實(shí)體的標(biāo)簽和評(píng)論，自動(dòng)地獲得它們中每個(gè)單詞在WordNet本體中的合適詞義[21]，并擴(kuò)展這些詞義。實(shí)體標(biāo)記表示器基于單詞的詞義及其擴(kuò)展定義實(shí)體標(biāo)記以表示本體中實(shí)體的詞法信息，簡(jiǎn)記為C(E)，其中 E表示本體中的實(shí)體。匹配候選生成器基于實(shí)體標(biāo)記生成一組匹配候選供匹配推理階段使用。匹配候選過(guò)濾器將刪除冗余的候選，過(guò)濾后的匹配候選集合，簡(jiǎn)記為MCF。基于過(guò)濾的匹配候選集合，匹配推理階段擴(kuò)展結(jié)構(gòu)包含推理算法以推理來(lái)自不同本體的實(shí)體間的匹配（第 4節(jié)描述了該階段）。

圖1 系統(tǒng)架構(gòu)

4 擴(kuò)展結(jié)構(gòu)包含推理算法的本體匹配

匹配推理階段擴(kuò)展結(jié)構(gòu)包含推理算法以推理出實(shí)體間的匹配。該階段首先基于候選計(jì)算階段定義的 C(E)通過(guò)重定向?qū)嶓w到范式的方式分析了本體中的構(gòu)造器和公理，然后基于候選計(jì)算階段的MCF通過(guò)比較來(lái)自不同本體的范式之間的句法結(jié)構(gòu)產(chǎn)生匹配。

4.1 定義范式

將本體里實(shí)體（包括概念和屬性）重定向?yàn)榉妒剑òǜ拍罘妒胶蛯傩苑妒剑┑哪康氖鞘贡惶N(yùn)含的語(yǔ)義信息能夠明顯地表示出來(lái)。本節(jié)形式化地定義了范式。該定義不僅明顯地表示了本體的語(yǔ)義信息，也表示了本體的詞法信息。

概念范式的形式化定義如下。

1) 集合prim(Ci)表示在Ci的頂層中所有的原子概念和它們的補(bǔ)概念（negated）以及相應(yīng)實(shí)體標(biāo)記的表示。

2) NR是在Ci頂層中可用角色（或?qū)傩裕┑募稀?/p>

3) existR(Ci)是一個(gè)概念描述集合。這個(gè)集合里的任何元素C在Ci頂層中存在?R.C。

4) forallR(Ci)是通過(guò)在Ci頂層中合并角色R的所有值限制（C1∩…∩Cn）形成若干個(gè)概念描述的交（?R.C1∩…∩?R.Cn）。

5）minR(Ci)表示在Ci頂層中角色R的至少限制（at-least restrictions）的最大勢(shì)（cardinality），maxR(Ci)表示該角色R的至大限制（at-most restrictions）的最小勢(shì)（cardinality）。如果存在角色R的相等限制（at-equivalence restrictions），則minR(Ci)和maxR(Ci)與相等限制中的勢(shì)相同。如果僅minR(Ci)存在，maxR(Ci)是+∞。如果僅 maxR(Ci)存在，minR(Ci)是0。如果相應(yīng)的?R存在，minR(Ci)大于0。

6）對(duì)于任意的 i，forallR(Ci)和 C'都在范式形式。如果 Ci≡⊥（通過(guò)推理機(jī)進(jìn)行判斷），則在公式中將它刪除。

從范式的定義中可以看到，集合補(bǔ)（negation）總是直接出現(xiàn)在原子概念前面，?R在Ci頂層中出現(xiàn)多次。屬性范式的形式化定義與上述概念范式的形式定義類似，此處不再贅述。

4.2 重定向?qū)嶓w到范式

在概念到范式的重定向組件中，主要有以下幾個(gè)步驟。

首先，基于下面的規(guī)則將本體知識(shí)庫(kù) TBox中的包含公理和不相交公理轉(zhuǎn)換為定義公理，轉(zhuǎn)換后的TBox記作TBox。轉(zhuǎn)換公理的規(guī)則和順序如下：

1）如果A是命名的概念，A⊥B?A??B；

2）A?B；A?C；A?D?A≡B∩C∩D；

正如規(guī)則4)所述，通過(guò)引入實(shí)體標(biāo)記，將包含公理轉(zhuǎn)換為定義公理。這里實(shí)體標(biāo)記代表了概念A(yù)與它的父概念的不同，并沒(méi)有改變?cè)邪淼恼Z(yǔ)義。這些規(guī)則保證了 TBox是定義的（關(guān)于定義的TBox，參考文獻(xiàn)[22]）。規(guī)則4)也保證了在TBox里概念僅被定義一次，也就是說(shuō)，至多有一個(gè)左面是A的公理存在于TBox中。規(guī)則3)和規(guī)則4)引入的實(shí)體標(biāo)記保證了實(shí)體間潛在的關(guān)系。

轉(zhuǎn)換概念到范式組件的第2步利用一個(gè)迭代的過(guò)程將TBox中的定義公理擴(kuò)展。它使用相應(yīng)概念的定義替換每個(gè)定義公理中右面的概念。因?yàn)樵谳斎氡倔w里沒(méi)有圈定義，所以該過(guò)程最后將終結(jié)。

轉(zhuǎn)換概念到范式組件的第3步通過(guò)描述邏輯和代數(shù)集合的定律（比如結(jié)合律、吸收律、摩根律、分配律、同一律等[17,18]）將上一步得到的定義公理的擴(kuò)展化簡(jiǎn)到4.1節(jié)所述的范式形式。屬性到范式的重定向方法與概念到范式的重定向方法類似，此處不再贅述。

假設(shè)有簡(jiǎn)單本體O，由如下公理構(gòu)成：通過(guò)上述步驟以及4.1節(jié)范式的定義，可將本體O轉(zhuǎn)化到范式形式，如下所示：

從條款⑥可以看到概念“Grandmother”在本體O中的形式化語(yǔ)義由原子實(shí)體Person，F(xiàn)emale，hasChild所構(gòu)成；C(A)表示了概念A(yù)與其父概念的不同，也表示了在WordNet中的詞義（即人們對(duì)概念 A的詞法信息在現(xiàn)實(shí)世界中的認(rèn)識(shí)），這種方法沒(méi)有改變?cè)泄淼恼Z(yǔ)義。重定向?qū)嶓w到范式方法將實(shí)體在本體中語(yǔ)義信息和詞法信息都顯示地表示出來(lái)，為推理匹配奠定了基礎(chǔ)。

4.3 推理實(shí)體間匹配

當(dāng)分別定義不同本體里相似的概念時(shí)，知識(shí)工程師們有時(shí)會(huì)忽略一些元素或者使用不同的范圍限制它們。即便是工程師們?yōu)椴煌谋倔w構(gòu)建2個(gè)相同的概念時(shí)，這些概念之間通常也存在著差異。因此本節(jié)引入閾值α、β和γ以便調(diào)節(jié)來(lái)自不同本體的實(shí)體間被允許的差異程度。

在概念范式比較組件里假如有來(lái)自不同本體的2個(gè)概念C和D，它們不是⊥也不是T。它們的概念范式如下（分別簡(jiǎn)記為NormalC和NormalD）。

如果下列條件成立則稱之為C?D：

對(duì)于所有的i，1≤i≤n，存在j，1≤j≤m使得 Ci?Dj。

如果下列條件成立（0≤α≤1，0≤β≤1，γ≤ 1），則稱之為 Ci?Dj：

在條件 1)中，當(dāng)判定prim(Ci)中的元素是否是prim(Dj)中元素的子概念時(shí)（即 A?B），使用相應(yīng)的實(shí)體標(biāo)記替代這些原子概念，然后基于 MCF推理它們之間的關(guān)系。例如，┐C(A)和C(B)之間的關(guān)系替代原子概念┐A和B之間的關(guān)系。條件①中屬性關(guān)系的判定，由屬性范式比較組件完成。

引入閾值α、β和γ是為了調(diào)節(jié)不同本體中實(shí)體間被允許的差異程度。閾值α在[0，1]區(qū)間變化時(shí)，它反映了在prim(Ci)和prim(Dj)中忽略元素的個(gè)數(shù)。α越大，在prim(Ci)和prim(Dj)中忽略的元素越多。如果 α=0，說(shuō)明系統(tǒng)并不考慮來(lái)自 prim(Ci)和prim(Dj)元素之間的任何關(guān)系。如果α=1，說(shuō)明系統(tǒng)考慮來(lái)自prim(Ci)和prim(Dj)任何元素之間的關(guān)系。閾值β與α類似，它反映的是屬性之間的關(guān)系。閾值γ反映的是at-least限制和at-most限制中范圍被允許的差異。它越小，范圍之間被允許的差異越大。當(dāng)閾值γ=0，意味著at-least和at-most限制中不被允許任何差異。

根據(jù)上述方法，可以推理出實(shí)體間的包含關(guān)系，基于此，使用下列定律也可以推理實(shí)體間的相等（equivalence）和不相交（disjoint）關(guān)系[18]。

在直覺(jué)上該方法能夠保證推理的有力性（sound），但不能保證其完整性（complete），這與結(jié)構(gòu)包含算法的特殊性有關(guān)。正如條件③和條件④所示，該方法包含一個(gè)遞歸的過(guò)程。屬性范式比較方法與概念范式比較方法類似，此處不再贅述。通過(guò)比較范式的句法結(jié)構(gòu)，將產(chǎn)生一組來(lái)自不同本體概念間的匹配，每個(gè)匹配包含一個(gè)源實(shí)體、一個(gè)目標(biāo)實(shí)體和它們之間的邏輯關(guān)系。在匹配樣例本體的過(guò)程中，此階段產(chǎn)生的匹配情況如圖2所示。圖2中匹配的左側(cè)方框和區(qū)配的右側(cè)方框分別表示實(shí)體來(lái)自樣例本體Ontology101和Ontology302；黑線表示 DLOM 系統(tǒng)發(fā)現(xiàn)的且存在于標(biāo)準(zhǔn)答案中的匹配；黑粗線表示 DLOM 系統(tǒng)未發(fā)現(xiàn)的但存在于標(biāo)準(zhǔn)答案中的匹配；點(diǎn)線表示 DLOM 發(fā)現(xiàn)的但較少出現(xiàn)在其他解決方案中的匹配；虛線表示DLOM發(fā)現(xiàn)的但不存在于標(biāo)準(zhǔn)答案中的匹配。

描述邏輯領(lǐng)域的非標(biāo)準(zhǔn)推理技術(shù)結(jié)構(gòu)包含推理算法的基本思想是比較范式間原子概念以得到概念間的關(guān)系。4.2節(jié)將實(shí)體轉(zhuǎn)換到范式顯示地展現(xiàn)了實(shí)體的語(yǔ)義信息和詞法信息，本節(jié)比較了實(shí)體范式間的句法結(jié)構(gòu)，實(shí)際上是比較展現(xiàn)的語(yǔ)義信息和詞法信息。明顯地，DLOM繼承了結(jié)構(gòu)包含推理算法的基本思想，為適應(yīng)本體匹配它也進(jìn)行了擴(kuò)展。在比較范式句法結(jié)構(gòu)時(shí)，它基于實(shí)體標(biāo)記利用 WordNet[21]作為知識(shí)庫(kù)推理出原子概念之間的關(guān)系，也引入了α、γ和β表示本體匹配時(shí)所容許的差異，這些是原有的結(jié)構(gòu)包含推理算法所沒(méi)有的。

5 算法復(fù)雜度分析

本文包括2個(gè)主要步驟：重定向?qū)嶓w到范式和推理實(shí)體間匹配，本節(jié)分別闡述它們的算法復(fù)雜性。

5.1 重定向?qū)嶓w到范式算法分析

由4.2節(jié)可看到重定向?qū)嶓w到范式是一個(gè)迭代過(guò)程，使用相應(yīng)概念的定義替換定義公理右側(cè)的概念直到公理右側(cè)無(wú)概念可替換。

假設(shè)TBox中有n個(gè)公理且TBox中無(wú)圈定義，An表示最后的原子概念，下面的n個(gè)公理描述了最復(fù)雜的情況：

圖2 匹配樣例本體時(shí)的匹配情況

本文將采用由底向上的迭代過(guò)程，從時(shí)間來(lái)看，其基本操作是公理右側(cè)概念的替代。先分析重寫An-2到范式的情況，需將定義An-1公理的右側(cè)代入定義An-2公理右側(cè)的An-1。當(dāng)重寫實(shí)體Ai到范式時(shí)，需要將其后面的已寫成范式的 n-i個(gè)概念代入其右側(cè)的相應(yīng)概念。則在整個(gè)重寫實(shí)體到范式的過(guò)程中，所需進(jìn)行替代的次數(shù)為1+2+3…+(n-2)= (n-1)×(n-2)/2。上述最簡(jiǎn)單的情況是每個(gè)定義公理右側(cè)都是原子概念，所以替代次數(shù)為0。若TBox中定義公理的復(fù)雜程度是隨機(jī)的，即定義公理右側(cè)出現(xiàn)各種情況的概率相同，則可取上述最大值和最小值的平均值，作為概念替代的次數(shù)，約為(n-1) ×(n-2)/4，因此時(shí)間復(fù)雜度為O(n2)。

根據(jù)由底向上的迭代過(guò)程，從空間來(lái)看，其基本空間單位是原子概念，計(jì)算上述過(guò)程的空間復(fù)雜度，即是計(jì)算增加的使用原子概念的次數(shù)?，F(xiàn)分析重寫An-3到范式的情況，需分別將An-2和An-1右側(cè)的原子概念代入到An-3右側(cè)的相應(yīng)概念，它增加了1次原子概念的使用。若重寫Ai到范式，需要將其后面的已寫成范式的n-i個(gè)概念代入其右側(cè)的相應(yīng)位置，它增加了 f(Ai+1)+f(Ai+2)+…f(An-1)+f(An)次原子概念的使用，其中，f(Aj)表示概念A(yù)j中增加的使用原子概念的次數(shù)，其中，An-3為1。假設(shè)n=8，則有：

所以，在整個(gè)重寫實(shí)體到范式的過(guò)程中，增加地使用原子概念的次數(shù)為 20+21+…+2n-2=2n-1-1。上述最簡(jiǎn)單的情況是每個(gè)定義公理右側(cè)都是原子概念，所以增加地使用原子概念的次數(shù)為0。若TBox中定義公理的復(fù)雜程度是隨機(jī)的，則可取上述最大值和最小值的平均值，作為增加地使用原子概念的次數(shù)，約為(2n-1-1)/2，因此時(shí)間復(fù)雜度為O(2n)。所以DLOM更加適合于小本體的匹配。大規(guī)模本體的匹配將是下一步重要的研究工作。

5.2 推理實(shí)體間匹配算法分析

由4.3節(jié)條件③和條件④可看出，DLOM推理實(shí)體間匹配時(shí)包含一個(gè)遞歸的過(guò)程。假設(shè)有分別來(lái)自 TBox1的概念 A1的范式和 TBox2的概念 B1的范式（為計(jì)算方便省去＜min, max＞R和?R.C），如下所示：

其中，n表示TBox1中命名概念的個(gè)數(shù)，m表示 TBox2中命名概念的個(gè)數(shù)，Ci和 Dj分別表示原子概念。概念A(yù)i和Bj分別表示TBox1和TBox2中概念最為復(fù)雜的情況（見(jiàn)5.1節(jié)）。由5.1節(jié)可以看到，Ai中原子概念的個(gè)數(shù)約為2i，Bj中原子概念個(gè)數(shù)約為2j。

根據(jù)4.3節(jié)算法的過(guò)程來(lái)看，不需要任何輔助存儲(chǔ)空間，因此無(wú)需計(jì)算該算法的空間復(fù)雜度。從時(shí)間來(lái)看，基本操作是來(lái)自不同本體的原子概念間關(guān)系的比較。如果要判斷A1?B1，首先需要將C1到 Cx中任何元素與 D1…Dy依次比較，計(jì)算次數(shù)為 x×y；然后需要依次比較 A2與 B1…Bm中的元素，共比較次數(shù)為20×((2m-1-1)/2)；最后將A2到An中任何元素與B1…Bm依次比較，計(jì)算總次數(shù)為x×y +(2n-1-1)×(2m-1-1)/4。上述最簡(jiǎn)單的情況是A1=C1∩C2∩…∩Cx和 B1=D1∩D2∩…∩Dy，則比較次數(shù)為 x×y。若 TBox中定義公理的復(fù)雜程度是隨機(jī)的，則可取上述最大值和最小值的平均值，作為原子概念間關(guān)系計(jì)算的次數(shù)，約為 x×y+(2n-1-1)×(2m-1-1)/4，因此時(shí)間復(fù)雜度為O(2n+m)。所以，再一次說(shuō)明DLOM更加適合于小本體的匹配。

6 實(shí)驗(yàn)評(píng)估

本節(jié)討論了第2節(jié)中原型系統(tǒng)（DLOM）的評(píng)估。DLOM使用多種開(kāi)源分組來(lái)操作本體、執(zhí)行推理、比較匹配和與WordNet交互，包括JENA、Java WordNet Library API、Pellet API、OWL2.0 API、Prot égé API、SKOS API和 JOWL 等。

圖3 系統(tǒng)評(píng)估結(jié)果：準(zhǔn)確率，覆蓋率和F測(cè)度值

本節(jié)主要使用 3種性能指標(biāo)（準(zhǔn)確率（precision）、覆蓋率（recall）和 F測(cè)度值（F-measure））評(píng)估DLOM系統(tǒng)的性能。其中F測(cè)度值反映了準(zhǔn)確率和覆蓋率的綜合值（關(guān)于它們的計(jì)算，請(qǐng)參閱文獻(xiàn)[9,18]）。

6.1 實(shí)驗(yàn)數(shù)據(jù)

本節(jié)選擇了本體匹配評(píng)估倡議組織（OAEI ,ontology alignment evaluation initiative）標(biāo)準(zhǔn)中4個(gè)工業(yè)本體作為測(cè)試集（可通過(guò)文獻(xiàn)[23]下載）。它們都是書(shū)目領(lǐng)域的本體，分別來(lái)自BibTeX、UMBC、Karlsruhe、INRIA，依次標(biāo)記它們?yōu)镺ntology301、Ontology302、Ontology303、Ontology 304。同時(shí)，OAEI也提供了這些本體匹配任務(wù)的標(biāo)準(zhǔn)匹配，以便計(jì)算方案的性能。通常，這些本體包括大約 37個(gè)概念、72個(gè)屬性和108個(gè)公理。

6.2 參數(shù)優(yōu)化

在DLOM系統(tǒng)中，有3個(gè)參數(shù)表示匹配過(guò)程中被允許的實(shí)體間的差異程度：α、β和γ。本節(jié)通過(guò)匹配書(shū)目領(lǐng)域4個(gè)本體的實(shí)驗(yàn)設(shè)置它們。其中α和β在[0，1]之間變化，變化間隔為0.01；由于在實(shí)驗(yàn)中 γ ≤-10沒(méi)有實(shí)際意義，所以實(shí)驗(yàn)中 γ在[-10，0]之間變化，變化間隔為 0.01。實(shí)驗(yàn)時(shí)，固定2個(gè)參數(shù)不變，僅變動(dòng)一個(gè)參數(shù)，并標(biāo)識(shí)當(dāng)時(shí)的F測(cè)度值。表1顯示了實(shí)驗(yàn)的部分結(jié)果，當(dāng)α=0.5、β=0.44和γ=-2時(shí)F測(cè)度值最大。

表1 DLOM參數(shù)優(yōu)化實(shí)驗(yàn)結(jié)果

6.3 與其他匹配方法的比較

本節(jié)通過(guò)測(cè)試書(shū)目領(lǐng)域的本體比較 DLOM 和其他12個(gè)系統(tǒng)，包括SOBOM、DSSim、amaker、aroma、Lily、ASMOV、RiMOM、GeRoMe、aflood、kosimap、TaxoMap以及一種基本的匹配系統(tǒng)（即edna）。如圖3所示，DLOM顯示出較好的性能。

圖3顯示了13個(gè)系統(tǒng)的準(zhǔn)確率、覆蓋率和F測(cè)度值。從圖3可以看到，DLOM在覆蓋率方面有較好的質(zhì)量，最高提高達(dá)到58%（相對(duì)于TaxoMap），最低也有7%（相對(duì)于RiMOM）。DLOM擴(kuò)展了結(jié)構(gòu)包含推理算法使得被蘊(yùn)含的語(yǔ)義能夠明顯地表示出來(lái)。因此 DLOM 能夠深入地探索本體中的語(yǔ)義信息，并通過(guò)比較范式句法結(jié)構(gòu)的方式對(duì)比相似實(shí)體間的語(yǔ)義信息。該特點(diǎn)使得 DLOM 發(fā)現(xiàn)了較多匹配，同時(shí)也產(chǎn)生了一些并不經(jīng)常出現(xiàn)在其他方法中的匹配（但出現(xiàn)在標(biāo)準(zhǔn)匹配中）。因此，相對(duì)于其他方法，DLOM顯示了較高的覆蓋率。下面列出了匹配樣例本體時(shí)，并不經(jīng)常出現(xiàn)在其他方法中但出現(xiàn)在標(biāo)準(zhǔn)答案中的匹配（如圖2所示）。

圖3也顯示了edna有較高的覆蓋率，但準(zhǔn)確率很低。因?yàn)閑dna發(fā)現(xiàn)了太多的匹配，雖然覆蓋了大部分標(biāo)準(zhǔn)匹配，但也產(chǎn)生了許多不精確的匹配。

從圖3可以看到DLOM的準(zhǔn)確率較低（相對(duì)于DSSim和SOBOM等）。SOBOM和DSSim等方法的基本思想是希望得到的每個(gè)匹配都是正確的，如果產(chǎn)生不確定的匹配，則舍去。因此在測(cè)試時(shí)它們僅產(chǎn)生約50個(gè)匹配，而其他方法通常產(chǎn)生約70個(gè)匹配。這保證了它們較高的準(zhǔn)確率，然而這也導(dǎo)致了它們較低的覆蓋率。同時(shí)，DLOM使用MCF作為推理實(shí)體間匹配時(shí)的知識(shí)庫(kù)（如4.3節(jié)所示）。因此MCF中的異常匹配候選會(huì)導(dǎo)致最后錯(cuò)誤匹配的產(chǎn)生。例如在匹配樣例本體時(shí)，MCF中的C(101:notes)?C (302:school)導(dǎo)致了匹配＜101: notes,302: school, ?＞的產(chǎn)生。因此繼續(xù)提高匹配候選過(guò)濾器的性能是下一步的重要工作。文獻(xiàn)[24]已指出OAEI建議的標(biāo)準(zhǔn)匹配并不包含所有合理的匹配；標(biāo)準(zhǔn)匹配中的匹配也不都合乎邏輯。在DLOM 中產(chǎn)了這樣符合本體語(yǔ)義的匹配，然而它們并沒(méi)有出現(xiàn)在標(biāo)準(zhǔn)匹配中。例如當(dāng)匹配Ontology101和Ontology303時(shí)，DLOM產(chǎn)生了＜101:Deliverable, 303:Report, ?＞和＜101:Report, 303:ProjectReport, ?＞等，這些匹配是合理的且與本體的語(yǔ)義一致，但并沒(méi)有出現(xiàn)在標(biāo)準(zhǔn)匹配中。這也是DLOM方法準(zhǔn)確率較低的原因之一。

盡管 DLOM 的準(zhǔn)確率不是最高的，但從圖 3可以看到，相比其他12個(gè)方法，DLOM在F測(cè)度值方面（反映了準(zhǔn)確率和覆蓋率的綜合性能）有較好的質(zhì)量，最高提高達(dá)到44%（相對(duì)于TaxoMap），最低也有3%（相對(duì)于aflood）。

7 結(jié)束語(yǔ)

擴(kuò)展結(jié)構(gòu)包含推理算法的方法首先將本體中實(shí)體重定向?yàn)榉妒剑沟帽惶N(yùn)含的語(yǔ)義信息形式化顯示出來(lái)，然后比較范式之間的句法結(jié)構(gòu)，推理出不同實(shí)體間的匹配。實(shí)驗(yàn)表明，該方法具有較好的性能。

[1] SHVAIKO P, EUZENAT J. Ten challenges for ontology matching[A].Proceedings of the OTM 2008 Confederated International Conferences[C]. 2008. 300-313.

[2] ZHAO H. Semantic matching across heterogeneous data sources[J].Communication ACM, 2007, 50(1): 45-50.

[3] KALFOGLOU Y, SCHORLEMMER M. Ontology mapping: the state of the art[J]. Knowl Eng Rev, 2003, 18(1): 1-31.

[4] GIUNCHIGLIA F, SHVAIKO P. Semantic matching[J]. Knowl Eng Rev, 2003, 18: 265-280.

[5] REUL Q, PAN J Z. Kosimap: use of description logic reasoning to align heterogeneous ontologies[A]. Proceedings of the 23rd International Workshop on Description Logics, Ser CEUR Workshop Proceedings[C]. Waterloo, Canada, 2010.

[6] UDREA O, GETOOR L, MILLER R J. Leveraging data and structure in ontology integration[A]. SIGMOD 07: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data[C].New York, NY, USA, 2007. 449-460.

[7] LIU X, BARNAGHI P, MOESSNER K. Lexical and Semantic Analysis for Ontology Matching[R]. CCSR, Surrey University, Guildford,Surrey, Tech Rep CCSR-TR-101211, 2011.

[8] KOLLI M, BOUFAIDA Z. A description logics formalization for the ontology matching[J]. Procedia Computer Science, 2011, 3(1): 29-35.

[9] JEAN Y R, SHIRONOSHITA E P, KABUKA M R. Ontology matching with semantic verification[J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2009, 7(3): 235-251.

[10] SPILIOPOULOS V, VOUROS G A, KARKALETSIS V. On the discovery of subsumption relations for the alignment of ontologies[J].Web Semantics:Science, Services and Agents on the World Wide Web,2010, 8(1): 69-88.

[11] ALGERGAWY A, MASSMANN S, RAHM E. A clustering-based approach for large-scale ontology matching[A]. Databases and Information Systems, Ser Lecture Notes in Computer Science[C]. 2011.415-428.

[12] BUCCELLA A, CECHICH A, GENDARMI D, et al. Building a global normalized ontology for integrating geographic data sources[J].Computers & Geosciences, 2011, 37(7): 893-916.

[13] JAMES N, TODOROV K, HUDELOT C. Combining visual and textual modalities for multimedia ontology matching[A]. Semantic Multimedia, Ser Lecture Notes in Computer Science[C]. Springer, 2011. 95-110.

[14] ALBAGLI S, BEN-ELIYAHU-ZOHARY R, SHIMONY S E. Markov network based ontology matching[A]. Proceedings IJCAI'09 Proceed-ings of the 21st International Jont Conference on Artifical Intelligence[C]. San Francisco, CA, USA, 2009.

[15] MOUSELLY-SERGIEH H, UNLAND R. Irom: information retrieval-based ontology matching[A]. Semantic Multimedia, Ser Lecture Notes in Computer Science[C]. 2011.127-142.

[16] BOCK J, HETTENHAUSEN J. Discrete particle swarm optimization for ontology alignment[J]. Information Sciences, 2010, 192: 152-173.

[17] WANG X, XU Q. An improved ant colony optimization for ontology matching[A]. Computer Research and Development (ICCRD), 3rd International Conference on[C]. 2011. 234-238.

[18] TANG J, LI J, LIANG B, HUANG X, et al. Using Bayesian decision for ontology mapping[J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2006, 4(4): 243-262.

[19] BONIFACIO M, DONA A, MOLANI A, et al. Context matching for electronic marketplaces - a case study[A]. Proceedings of the Workshop on Ontologies and Distributed Systems, 18th Int, Joint Conf on Artificial Intelligence[C]. 2003.

[20] GUARINO N, GIARETTA P. Ontologies and knowledge bases: towards a terminological clarification[A]. Towards Very Large Knowledge Bases: Knowledge Building and Knowledge Sharing[C]. 1995.

[21] MILLER G A, BECKWITH R, FELLBAUM C, et al. Introduction to wordnet-an online lexical database[J]. International Journal of Lexicography, 1990, 4(3): 235-244.

[22] BAADER F, CALVANESE D, MCGUINESS D, et al.. The Description Logic Handbook: Theory, Implementation and Applications[M].Cambridge University Press, 2003.

[23] OAEI[EB/OL].http://oaei.ontologymatching.org/2009/benchmarks/,2009.

[24] MEILICKE C. The relevance of reasoning and alignment incoherence in ontology matching[A]. ESWC, Ser Lecture Notes in Computer Science[C]. Springer, 2009. 934-938.