一種關(guān)于本體復(fù)合映射的挖掘算法

（四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院 成都 610068）

摘 要：為了提高本體映射的精度，往往需要同時(shí)考慮1∶1、1∶n、n∶m等多種不同的情況。而對(duì)于以往的映射算法而言，它們主要考慮了簡單的1∶1的映射，忽略了同樣重要并占據(jù)相當(dāng)比例的復(fù)合映射問題，這樣極大地?fù)p失了本體映射的精度。針對(duì)這個(gè)問題，提出了一個(gè)基于多種關(guān)系的復(fù)合映射發(fā)現(xiàn)算法。實(shí)驗(yàn)證明，該算法在對(duì)本體復(fù)合映射的發(fā)現(xiàn)問題上非常有效，而且極大地提高了映射結(jié)果的精度。

關(guān)鍵詞：本體； 本體映射； 復(fù)合映射

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)05-1723-03

Mining algorithm of complex ontology mapping

LI Ming

(College of Computer Science Sichuan Normal University Chengdu 610068 China)

Abstract:In order to improve the accuracy of ontology mapping it always needed to consider multiple different mapping conditions for example 1∶1，1∶n，n∶m.As for existed ontology mapping methods focused on the simple one to one mapping while the problem of the complex mapping which also took important seats had been neglected. Aiming at solving the loss of mapping precision this paper proposed a new complex mapping method based on multiple relationships. Experiment results show good efficiency of the method.

Key words：ontology； ontology mapping； complex mapping

0 引言

隨著本體研究的不斷發(fā)展，本體數(shù)目日益增長，本體的重用與共享成為了語義網(wǎng)進(jìn)一步發(fā)展的前提，解決重用與共享的關(guān)鍵是本體的映射技術(shù)。目前，國內(nèi)外學(xué)者對(duì)本體映射的研究呈白熱化趨勢(shì)，各種算法和系統(tǒng)層出不窮，為此國際上已有專門的學(xué)術(shù)組織OAEI對(duì)這些系統(tǒng)進(jìn)行比較評(píng)估，并且已有一些映射系統(tǒng)日趨完善。但是值得關(guān)注的是大部分的系統(tǒng)都只考慮了簡單的1∶1映射，并沒有涉及1∶n和n∶m的復(fù)合映射問題。而實(shí)際上本體間的復(fù)合映射比重不小，因此進(jìn)一步提高映射精度的關(guān)鍵在于對(duì)復(fù)合映射的處理問題。本文提出了一個(gè)基于概念間不同關(guān)系的復(fù)合映射發(fā)現(xiàn)方法。

本文分析了國內(nèi)外已有的復(fù)合映射發(fā)現(xiàn)算法及其問題，詳細(xì)介紹了本文所提出的復(fù)合映射發(fā)現(xiàn)算法，對(duì)本文提出的方法進(jìn)行了實(shí)驗(yàn)與結(jié)果分析。

1 相關(guān)工作

目前國內(nèi)外學(xué)者對(duì)本體的復(fù)合映射的研究還比較少，僅有的研究中也主要是針對(duì)模式的復(fù)合映射。涉及復(fù)合映射的方法主要有：

使用參考本體^[1]。此方法始于模式匹配，將待映射模式的概念分別映射到第三方參考本體中，利用參考本體來挖掘彼此之間的關(guān)系。但這種方法極大地受限于參考本體，應(yīng)用范圍小。

其他還有iMAP^[2]方法、Rimom^[3]、DCM^[4]等，但是它們各自都存在問題，查全率和精度還有待提高。

2 復(fù)合映射發(fā)現(xiàn)技術(shù)

復(fù)合映射的概念之間主要存在以下三種關(guān)系，即包含關(guān)系、平級(jí)等價(jià)關(guān)系以及不規(guī)則的特殊關(guān)系。下面本文將從這三個(gè)方面給出不同的映射發(fā)現(xiàn)算法。

2.1 基于包含關(guān)系的發(fā)現(xiàn)算法

有相當(dāng)大一部分存在復(fù)合映射關(guān)系的概念之間是屬于包含關(guān)系的，如name=firstname+lastname。實(shí)際上firstname與lastname都是屬于name概念的，它們之間存在著明顯的包含關(guān)系。另外person=man+woman以及address=city+state+street也都是屬于這種情況。

當(dāng)Ci∈O1和Cj，Ck，Cm∈O2時(shí)，對(duì)存在包含關(guān)系的映射O1.Ci=f(O2.Cj，O2.Ck，O2.Cm)一般滿足以下兩個(gè)條件：

(O1.CiO2.Cj)∩(O1.CiO2.Ck)∩(O1.CiO2.Cm)

(O2.Cj∩O2.Ck)∪(O2.Cj∩O2.Cm)∪(O2.Ck∩O2.Cm)=

在同一本體中各個(gè)概念之間的相互關(guān)系是顯而易見的，然而在不同本體中尋找確定它們之間的關(guān)系則較為復(fù)雜，因?yàn)樗鼈冎g不存在明顯的結(jié)構(gòu)關(guān)系。本文使用以下幾種方法進(jìn)行復(fù)合映射發(fā)現(xiàn)。

2.1.1 利用概念實(shí)例的發(fā)現(xiàn)技術(shù)

實(shí)例是概念在現(xiàn)實(shí)世界的具體表現(xiàn)，從很大程度上反映出概念的特點(diǎn)。假設(shè)概念的實(shí)例足夠多、足夠全面，得出如下規(guī)則1。

規(guī)則1 對(duì)于概念Cj、Ck、Cm來說，如果它們所有的實(shí)例都屬于概念Ci的實(shí)例集，并且它們彼此之間不存在相同的實(shí)例，那么認(rèn)為概念Ci與概念Cj、Ck、Cm之間存在復(fù)合映射關(guān)系，即

Cj，Ck，Cm(ins(Ci)ins(Cj))∩

(ins(Ci)ins(Ck))∩(ins(Ci)ins(Cm))

(ins(Cj)∩ins(Ck))∪(ins(Cj)∩ins(Cm))∪

(ins(Ck)∩ins(Cm))=

利用實(shí)例的發(fā)現(xiàn)技術(shù)要求實(shí)例具有代表性、來源于相同的實(shí)例庫。此方法對(duì)同一領(lǐng)域內(nèi)的異構(gòu)本體尤為有效，但是對(duì)于兩個(gè)本體的實(shí)例集沒有交集時(shí)就無能為力^[5]。

2.1.2 利用屬性的發(fā)現(xiàn)技術(shù)

存在映射關(guān)系的概念所具有的屬性之間必定存在一定的關(guān)聯(lián)。利用屬性關(guān)系的復(fù)合映射發(fā)現(xiàn)方法包括以下兩種：

a)屬性限制。復(fù)合映射person=man+woman，person概念具有屬性sex。顯然對(duì)person而言，sex的取值可為male或female中任意一個(gè)；而對(duì)于概念man與woman則不然，它們?cè)趕ex上的取值固定，且它們?nèi)≈档暮先〗Y(jié)果正好與person在sex上的值域重合。

規(guī)則2 對(duì)于概念Cj、Ck、Cm來說，如果它們?cè)趯傩訮上的取值固定不變、互不相交，且它們?cè)趯傩訮上的取值的合取結(jié)果與Ci在屬性P上的值域重合，則認(rèn)為概念Ci與概念Cj、Ck、Cm之間可能存在復(fù)合映射關(guān)系，即

R（p（O1.Ci))=

valueof(restriction(p(O2.Cj)))∪

valueof(restriction(p(O2.Ck)))∪

valueof(restriction(p(O2.Cm)))

valueof(restriction(p(O2.Cj)))∩

valueof(restriction(p(O2.Ck)))=

valueof(restriction(p(O2.Cj)))∩

valueof(restriction(p(O2.Cm)))=

valueof(restriction(p(O2.Ck)))∩

valueof(restriction(p(O2.Cm)))=

b)屬性相似或關(guān)系相似。可以形成復(fù)合概念的各個(gè)概念的屬性之間必然存在一些相似之處，例如從復(fù)合映射address=city+state+street中可以發(fā)現(xiàn)概念address與概念city、state、 street它們都為located at 屬性的值域，如圖1所示。

規(guī)則3 概念Cj、Ck、Cm與概念Ci都為屬性P的值域（定義域），且屬性P在本體O1、O2中的定義域（值域）的類型相同，則認(rèn)為概念Ci與概念Cj、Ck、Cm之間可能存在復(fù)合映射關(guān)系。

當(dāng)概念為屬性的值域時(shí)，R(O1.P)O1.Ci，R(O2.P)(O2.Cj∪O2.Ck∪O2.Cm)并且typeof(D(O1.P))≡typeof(D(O2.P))。

當(dāng)各概念均為屬性的定義域時(shí)必然滿足以下幾個(gè)條件：D(O1.P)O1.Ci，D(O2.P)(O2.Cj∪O2.Ck∪O2.Cm)并且typeof(R(O1.P))≡typeof(R(O2.P))。

2.1.3 利用概念注釋的發(fā)現(xiàn)技術(shù)

毫無疑問，能夠構(gòu)成具有包含關(guān)系的復(fù)合映射的各個(gè)概念之間必然存在一定的相似性，它們屬于相同的領(lǐng)域、描述相似的內(nèi)容，因此它們?cè)谧⑨屔弦矐?yīng)該具有相似性。如下例：

telephone_number=mobile_number+home_number+office_number

telephone 〈comments:an instrument which one can use to communicate with others. 〉

mobile 〈comments:telephone which is capable of moving form place to place.〉

home_number 〈comments: constant telephone number at home.〉

office_number〈comments: constant telephone number at office.〉

從以上的注釋可以得出概念telephone_number與home_number office_number以及mobile_number之間的關(guān)系。據(jù)此本文提出規(guī)則4如下：

規(guī)則4 如果概念Cj、Ck、Cm的注釋都與概念Ci的注釋相似，在語義上存在包含關(guān)系，并且概念Cj、Ck、Cm之間也存在互補(bǔ)關(guān)系，則認(rèn)為概念Ci與概念Cj、Ck、Cm之間可能存在復(fù)合映射關(guān)系，即

(similarity(comments(Ci)，comments(Cj))≥σ)∩

(similarity(comments(Ci)，comments(Ck))≥σ)∩

(similarity(comments(Ci)，comments(Cm))≥σ)

并且

sem(focus(Ci))(sem(focus(Cj))∪

sem(focus(Ck))∪(sem(focus(Cm)))

利用注釋發(fā)現(xiàn)復(fù)合映射技術(shù)的關(guān)鍵在于對(duì)相似度的計(jì)算，使用不同的相似度計(jì)算方法得出的結(jié)果可能差別較大。一般而言，大部分相似度計(jì)算方法都只是考慮概念之間的相同點(diǎn)，然而事實(shí)上概念之間的不同點(diǎn)也充當(dāng)著重要的角色。

Intuition 1 概念A與B的相似度與它們之間的相同點(diǎn)有關(guān)，相同點(diǎn)越多，它們?cè)较嗨啤＊?/p>

Intuition 2 概念A與B的相似度與它們的不同點(diǎn)有關(guān)，不同點(diǎn)越多，它們?cè)讲幌嗨啤＊?/p>

Intuition 3 當(dāng)概念A、B完全相同時(shí)，相似度最大。

基于以上的intuitions^[6]，要獲得相對(duì)準(zhǔn)確的結(jié)果，本文需要同時(shí)考慮概念的注釋之間的共同點(diǎn)和不同點(diǎn)。以往僅僅考慮概念之間的共同點(diǎn)而忽視其不同點(diǎn)，可能過分放大相同點(diǎn)而出現(xiàn)概念與其相反的概念相似的結(jié)果。因此本文采用的相似度計(jì)算方法是通過詞法句法分析截取注釋的中心詞，并同時(shí)考慮兩概念共同點(diǎn)與不同點(diǎn)。

sim(com)=core(A，B)+common(A，B)-difference(A，B)(1)

若sim(com)≥α則認(rèn)為概念A(yù)、B相似。

若概念A、B無相同點(diǎn)，可考慮其與對(duì)方的相關(guān)節(jié)點(diǎn)的相似之處。本文主要考慮概念的直接繼承相關(guān)節(jié)點(diǎn)即概念的直接父子節(jié)點(diǎn)集。

sim′(com)=core(A，fset(B))+common(A，fset(B))-

difference(A，fset(B))(2)

sim′(com)=core(A，sset(B))+common(A，sset(B))-

difference(A，sset(B))(3)

sim′(com)=core(B，fset(A))+common(B，fset(A))-

difference(B，fset(A))(4)

sim′(com)=core(B，sset(A))+common(B，sset(A))-

difference(B，sset(A))(5)

若sim′(com)≥β且β＞α，則認(rèn)為概念A(yù)、B相似。

2.1.4 使用特殊參考本體的發(fā)現(xiàn)技術(shù)

對(duì)于存在比較權(quán)威的全局參考本體的復(fù)合映射，可將概念分別映射到參考本體中去，然后在同一個(gè)本體中查找它們之間的關(guān)系。在同一個(gè)本體中，通過本體結(jié)構(gòu)很容易確定彼此之間的關(guān)系。最典型的全局參考本體是時(shí)間本體，如date=year+month+day，可將其映射到已有的參考本體中（圖2），再查找確定它們之間是否存在復(fù)合映射關(guān)系。

規(guī)則5 如果概念Ci與概念Cj、Ck、Cm可以映射到同一個(gè)參考本體中去，且在參考本體中，C′i分別與C′j、C′k、C′m在結(jié)構(gòu)上為父子關(guān)系，在語義上為isa、has part等明顯的上下位或整體部分（包含）關(guān)系，則認(rèn)為概念Ci與概念Cj、Ck、Cm之間可能存在復(fù)合映射關(guān)系，即

R(stru(C′i，C′j))=R(stru(C′i，C′k))=

R(stru(C′i，C′m))R(stru(fatherson))

R(sem(C′i，C′j))=R(sem(C′i，C′k))=

R(sem(C′i，C′m)){isa，has part}

概念Ci′、Cj′、Ck′、Cm′分別為概念Ci、Cj、Ck、Cm在參考本體中對(duì)應(yīng)的概念。

2.1.5 算法

算法1 基于包含關(guān)系的算法

輸入：待映射本體O1，O2；

輸出：O1.Ci=f(O2.Cj，O2.Ck，O2.Cm)。

a)確定概念Ci與概念Cj、Ck、Cm之間是否存在包含關(guān)系，不存在則終止；

b)將概念映射到已有參考本體并符合規(guī)則5則輸出；

c)分別使用屬性策略、實(shí)例策略與注釋策略將查找出的映射分別放入候選隊(duì)列1、2、3中。

d)對(duì)候選隊(duì)列1、2、3分別采用實(shí)例加注釋技術(shù)、注釋技術(shù)以及實(shí)例技術(shù)進(jìn)行篩選，修正映射關(guān)系、刪除錯(cuò)誤映射并輸出結(jié)果。

2.2 基于平級(jí)等價(jià)關(guān)系的發(fā)現(xiàn)算法

雖然大部分復(fù)合映射的概念之間為包含關(guān)系，但是如weight_kg=2.2×net_weight_pounds，kg與pounds之間并不存在包含關(guān)系；在同一個(gè)本體中間它們應(yīng)該屬于平級(jí)的兄弟關(guān)系，都為計(jì)重單位的子概念，并且相互之間存在著一定的等價(jià)關(guān)系。這就是本文要考慮的另一種復(fù)合映射關(guān)系——平級(jí)等價(jià)關(guān)系。這種關(guān)系常見于重量、長度、體積、金錢等單位代換領(lǐng)域。

規(guī)則6 對(duì)于概念Ci和Cj來說，如果它們描述的是單位代換領(lǐng)域的概念且它們的超類相似，而它們的實(shí)例在數(shù)值上又存在一一對(duì)應(yīng)的固定比例關(guān)系，則認(rèn)為它們存在復(fù)合映射關(guān)系，即

domain(O1.Ci，O2，Cj)unit

superclassof(O1.Ci)=superclassof(O2.Cj)

valueof(ins(O1.Ci))/valueof(ins(O2.Cj))=ω

2.3 基于不規(guī)則特殊關(guān)系的發(fā)現(xiàn)算法

諸如interest_earned=balance×inter_est_rate list_price=price×(1+fee_rate)sports_car=car+constrains(speed>250 km/s) candidate = citizen + constrains ( age>18) 等不規(guī)則的復(fù)合映射關(guān)系，本文選擇重用過去已有的復(fù)合映射匹配

（pastcomplex mapping matches）或者在制定的形式模板(expression template)中搜索。

前者主要是在該領(lǐng)域已有的復(fù)合映射關(guān)系對(duì)的數(shù)據(jù)庫中搜索匹配，后者如sports_car=car+constrains(speed > 250 km/s) candidate = citizen + constrains(age>18)設(shè)計(jì)模板為Ci =Cj+constraints(x)進(jìn)行挖掘。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)

為了評(píng)估本文提出的方法的有效性，本文分別在university數(shù)據(jù)集和company數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。前者包含兩個(gè)實(shí)驗(yàn)本體分別是 SWRC（U1）本體與LUBM（U2）本體，描述的是大學(xué)本體；company數(shù)據(jù)集包含的實(shí)驗(yàn)本體描述的是某公司的信息，分別簡寫為C1與C2。

本文使用查全率和查準(zhǔn)率對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估。筆者手工建立了university數(shù)據(jù)集與company數(shù)據(jù)集的復(fù)合映射關(guān)系，用它們作為測(cè)評(píng)標(biāo)準(zhǔn)。

3.2 實(shí)驗(yàn)設(shè)計(jì)與分析

實(shí)驗(yàn)主要測(cè)試本文所提出的方法對(duì)基于包含關(guān)系的復(fù)合映射的有效性。因?yàn)閷?duì)基于平級(jí)等價(jià)關(guān)系的復(fù)合映射而言，主要出現(xiàn)在單位代換領(lǐng)域，在普通本體中一般比重不大。而對(duì)于不規(guī)則特殊關(guān)系在一般本體中比較罕見，它的挖掘也比較困難，往往受限于已有的匹配模板，因此在此也不多作分析。

對(duì)數(shù)據(jù)集university與company使用算法1所得的查全率和查準(zhǔn)率的實(shí)驗(yàn)結(jié)果如圖3所示。

3.3 實(shí)驗(yàn)結(jié)果分析

從實(shí)驗(yàn)結(jié)果可以看出，本文提出的方法在對(duì)復(fù)合映射進(jìn)行查找確定方面是十分有效的，實(shí)驗(yàn)所得的查全、查準(zhǔn)率都比較高。實(shí)驗(yàn)中出現(xiàn)的錯(cuò)誤匹配主要是遺漏了構(gòu)成復(fù)合概念的個(gè)別概念，而產(chǎn)生遺漏的主要原因在于輔助信息的缺失，主要是實(shí)例信息和注釋信息的缺乏。一旦補(bǔ)全恰當(dāng)?shù)淖⑨屝畔⑦@些映射都可以被挖掘出來。

4 結(jié)束語

本體映射技術(shù)是促進(jìn)本體共享與重用的關(guān)鍵技術(shù)，至今為止絕大部分本體映射的研究還停留在1∶1的簡單映射上，然而在現(xiàn)實(shí)中，復(fù)合映射是相當(dāng)廣泛的。本文提出了一種全新的復(fù)合映射發(fā)現(xiàn)方法，并通過實(shí)驗(yàn)證明了其有效性與精確性。

未來主要從以下幾方面進(jìn)行改進(jìn)：a)考慮n∶m映射。本文僅考慮1∶n的復(fù)合映射未涉及m∶n映射問題。b)提高映射發(fā)現(xiàn)的自動(dòng)化程度。

參考文獻(xiàn)：

［1］DRAGUT E LAWRENCE R. Composing mappings between schemas using a reference ontology[C]//Proc of International Conference on Ontologies Databases and Applications of Semantics. 2004:783-800.

[2]DHAMANKAR R LEE Y DOAN A H et al. iMAP:discovering complex semantic matches between database schemas[C]//Proc of the 23th ACM SIGMOD International Conference on Management of Data. New York:ACM Press 2004:383-394.

[3]TANG Jie LIANG Bangyong LI Juanzi，et al. Risk minimization based ontology mapping[C]//Proc ofAdvanced Workshop on Content Computing.Berlin: Springer 2004:469-480.

[4]HE Bin KEVIN C C C. Automatic complex schema matching across Web query interfaces: a correlation mining approach[J]. ACM Trans on Database Systems 2006，31(1):1-45.

[5]曹澤文 錢杰，張維明，等. 一種綜合的概念相似度計(jì)算方法[J]. 計(jì)算機(jī)科學(xué) 2007，34(3):174-176.

[6]LIN Dekang. An informationtheoretic definition of similarity[C]//Proc of the 15th International Conference on Machine Learning. San Framcisco:Morgan Kaufmann Publishers 1998:296-304.