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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

這些信息技術(shù)包括系數(shù)的計算（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)含了本體的語義信息。本文僅關(guān)注于本體匹配系統(tǒng)對語義信息的使用方法。根據(jù)歸約（deductions）規(guī)則，本體匹配中的語義分析方法主要分為2類：可滿足性問題（propositional satisfiability problem）和描述邏輯推理（description logics reasoning）。

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

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

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

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

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

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

3.1 背景知識

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

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

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

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

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

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

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

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

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

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

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

4.1 定義范式

將本體里實體（包括概念和屬性）重定向為范式（包括概念范式和屬性范式）的目的是使被蘊(yùn)含的語義信息能夠明顯地表示出來。本節(jié)形式化地定義了范式。該定義不僅明顯地表示了本體的語義信息，也表示了本體的詞法信息。

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

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

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

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

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

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

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

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

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

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

首先，基于下面的規(guī)則將本體知識庫 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)所述，通過引入實體標(biāo)記，將包含公理轉(zhuǎn)換為定義公理。這里實體標(biāo)記代表了概念A(yù)與它的父概念的不同，并沒有改變原有包含公理的語義。這些規(guī)則保證了 TBox是定義的（關(guān)于定義的TBox，參考文獻(xiàn)[22]）。規(guī)則4)也保證了在TBox里概念僅被定義一次，也就是說，至多有一個左面是A的公理存在于TBox中。規(guī)則3)和規(guī)則4)引入的實體標(biāo)記保證了實體間潛在的關(guān)系。

轉(zhuǎn)換概念到范式組件的第2步利用一個迭代的過程將TBox中的定義公理擴(kuò)展。它使用相應(yīng)概念的定義替換每個定義公理中右面的概念。因為在輸入本體里沒有圈定義，所以該過程最后將終結(jié)。

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

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

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

4.3 推理實體間匹配

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

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

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

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

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

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

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

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

在直覺上該方法能夠保證推理的有力性（sound），但不能保證其完整性（complete），這與結(jié)構(gòu)包含算法的特殊性有關(guān)。正如條件③和條件④所示，該方法包含一個遞歸的過程。屬性范式比較方法與概念范式比較方法類似，此處不再贅述。通過比較范式的句法結(jié)構(gòu)，將產(chǎn)生一組來自不同本體概念間的匹配，每個匹配包含一個源實體、一個目標(biāo)實體和它們之間的邏輯關(guān)系。在匹配樣例本體的過程中，此階段產(chǎn)生的匹配情況如圖2所示。圖2中匹配的左側(cè)方框和區(qū)配的右側(cè)方框分別表示實體來自樣例本體Ontology101和Ontology302；黑線表示 DLOM 系統(tǒng)發(fā)現(xiàn)的且存在于標(biāo)準(zhǔn)答案中的匹配；黑粗線表示 DLOM 系統(tǒng)未發(fā)現(xiàn)的但存在于標(biāo)準(zhǔ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é)將實體轉(zhuǎn)換到范式顯示地展現(xiàn)了實體的語義信息和詞法信息，本節(jié)比較了實體范式間的句法結(jié)構(gòu)，實際上是比較展現(xiàn)的語義信息和詞法信息。明顯地，DLOM繼承了結(jié)構(gòu)包含推理算法的基本思想，為適應(yīng)本體匹配它也進(jìn)行了擴(kuò)展。在比較范式句法結(jié)構(gòu)時，它基于實體標(biāo)記利用 WordNet[21]作為知識庫推理出原子概念之間的關(guān)系，也引入了α、γ和β表示本體匹配時所容許的差異，這些是原有的結(jié)構(gòu)包含推理算法所沒有的。

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

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

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

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

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

圖2 匹配樣例本體時的匹配情況

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

根據(jù)由底向上的迭代過程，從空間來看，其基本空間單位是原子概念，計算上述過程的空間復(fù)雜度，即是計算增加的使用原子概念的次數(shù)?，F(xiàn)分析重寫An-3到范式的情況，需分別將An-2和An-1右側(cè)的原子概念代入到An-3右側(cè)的相應(yīng)概念，它增加了1次原子概念的使用。若重寫Ai到范式，需要將其后面的已寫成范式的n-i個概念代入其右側(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，則有：

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

5.2 推理實體間匹配算法分析

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

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

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

6 實驗評估

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

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

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

6.1 實驗數(shù)據(jù)

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

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

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

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

6.3 與其他匹配方法的比較

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

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

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

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

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

7 結(jié)束語

擴(kuò)展結(jié)構(gòu)包含推理算法的方法首先將本體中實體重定向為范式，使得被蘊(yùn)含的語義信息形式化顯示出來，然后比較范式之間的句法結(jié)構(gòu)，推理出不同實體間的匹配。實驗表明，該方法具有較好的性能。

[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.