圖解析方式的復合本體映射策略研究

凌仕勇，龔錦紅

（華東交通大學1.軟件學院；2.電子與電氣工程學院，江西南昌 330013）

本體映射在許多應用領域都起到重要的作用，如模式集成、語義WEB、數(shù)據(jù)倉庫、電子商務、智能體通信、WEB服務組合、目錄映射等。很多前期研究往往側重于本體的概念、屬性、實例等特定模式，而忽視本體上下文結構的分析。近來，出現(xiàn)了大量基于英文語料庫Wordnet和中文語料庫Hownet的詞匯相似研究，這些研究語料的詞匯相似度計算是構成本體概念相似度計算的基礎。但是，對于本體本身的研究主要集中于單純的概念、屬性以及實例，如QOM［1］，ASMOM［2］，RiMOM［3］。COMA是由德國萊比錫大學開發(fā)的一套集本體解析，匹配，測試和評估的開源映射系統(tǒng)（http：//sourceforge.net/projects/coma-ce/），COMA解析各種格式輸入文件（XML，RDF，OWL）成一種內部結構，通過這種結構與匹配算法，輸入輸出，數(shù)據(jù)庫（默認mysql，可以自定義算法接入系統(tǒng)接口）進行交互。提供一套工作流用于定義輸入文本的格式，匹配算法，相似度計算的算法（外部接口庫align-4.2-ontowrap.jar），輸出文件的格式（xm l，htm l）。新版COMA++［4］支持不同的輸入如XMLSchema，RDF，OWL，引入了概念間的關系，但本身沒有引入基于語料庫的詞匯計算，不支持本體結構的相似度傳播，并且在映射時為了顧及一般化的多對多映射而采用單向或雙向完全遍歷的方法，使得復雜度大為增加。S-Match［5］是由意大利特倫托大學Fausto Giunchiglia教授主持開發(fā)的一套開源語義映射算法（http：//sourceforge.net/apps/trac/s-match/wiki/），S-Match將待映射的兩個文件解析成樹形結構，然后計算兩個樹節(jié)點之間的語義關系，進而找出映射關系。其語義計算分2個步驟：首先解析兩樹的標簽屬性，類似于本體的概念名稱，通過元素級別的匹配庫計算標簽概念的語義關系；其次解析兩樹的節(jié)點，類似于本體的概念屬性，通過節(jié)點級別的匹配庫計算節(jié)點間的語義關系。其詞匯計算的核心是通過WordNet詞匯庫進行語義相似度的計算。S-Match充分考慮了語義庫的支持和計算方法，但對應本體結構和映射策略并沒有給予過多的支持。

對于輸入模式的解析上，除了需要考慮本體的概念，屬性外，還需要考慮本體之間的上下文結構關系，本體所擁有的實例。本文將本體或其它的輸入模式解析成一種圖描述的結構，這種結構不依賴于任何特定的語義，可以接受其它類型的輸入模式如XML，文本結構，數(shù)據(jù)庫模式等等。并從3個層次上對輸入進行描述：節(jié)點層次上的圖定位，用于解析圖的頂點描述；概念關系層次上的結構圖分析，用于解析圖的邊描述；語義上的結構圖比較，用于節(jié)點的概念相似度計算。

對于本體結構的分析，本文從概念結構和概念所擁有的實例兩個級別引入了相似度傳播，將相似度通過結構算法傳遞到鄰近節(jié)點，提高了系統(tǒng)識別的準確度。并通過引入HopcroftKarp算法對二分圖進行快速匹配達到本體快速映射的目的。最后結合輸入模式的多層解析，設計重用基礎上的復合映射策略，構建迭代本體映射系統(tǒng)，用于快速準確的對本體進行映射。

對于映射系統(tǒng)，一般從效率和效能上進行分析。從效率上，主要考慮時空復雜度，從效能上，則是考慮系統(tǒng)對本體映射的評估效果。本文通過引入快速匹配算法，降低了映射的算法復雜度；通過多層關系結構的復合映射，提高了映射的評估效果。最后通過算法復雜度的分析和一些對比測試證明了這一點。

1 基于解析圖的復合本體映射

首先將輸入模式從3個層次角度解析成圖描述結構：節(jié)點層次上的圖定位，概念關系層次上的結構圖分析，語義層次上的結構圖比較。從概念結構和實例兩個級別引入了相似度傳播，將相似度通過結構算法傳遞到鄰近節(jié)點。引入HopcroftKarp算法對二分圖進行快速匹配達到本體快速映射。最后，設計復合映射策略，在兼顧系統(tǒng)性能基礎上對本體進行高質量映射。

1.1 本體圖解析

在考慮節(jié)點的基本概念特征基礎上，將本體中的概念表示成圖的節(jié)點，概念間的關系表示成圖的邊。并對本體解析圖的圖概念進行拓展，將節(jié)點對象屬性，節(jié)點數(shù)據(jù)屬性、節(jié)點的實例特征以及它們之間的結構關系嵌入到圖中的頂點和邊。這樣拓展后的本體解析圖中的節(jié)點分為兩個部分，第一部分為節(jié)點元素的內容特征，包括元素的名稱，數(shù)據(jù)類型，注釋，實例特征等。第二部分為節(jié)點元素的結構特征，包括節(jié)點的鄰居節(jié)點如子孫節(jié)點、葉子節(jié)點、雙親節(jié)點、兄弟節(jié)點、后代節(jié)點、前輩節(jié)點等等。前一部分關注節(jié)點的靜態(tài)信息，用于節(jié)點信息的匹配；后一部分關注節(jié)點的動態(tài)信息，用于上下文結構關系的分析。例如，針對圖1中的節(jié)點2，得到如表1所示的結果集合。

圖1 本體概念圖Fig.1 Ontology conceptgraph

表1 本體圖解析結構Tab.1 Parsing structureofontology graph

1.2 相似度傳播

相似度傳播的核心思想是，基于概念特征的父類或子類的相似度會傳播到概念本身，進而在一定程度影響概念本身的相似程度。文獻［6］提出了Simialrity Flooding算法，對概念的鄰居節(jié)點進行傳播，給出一個固定比例的相似度傳播值。GMO［7］則考慮全局的相似度傳播。兩者都沒有考慮概念間傳播度的差異性，如圖1中的節(jié)點1和節(jié)點5，節(jié)點1的概念空間比節(jié)點5大，所以對于節(jié)點1的子類相似的可能性要遠小于節(jié)點5的子類相似的可能性，所以不同概念的相似度傳播是有差異的。本文采用文獻［8］提出的語義傳播因子SF的方法，由定義1的語義傳播因子SF所示，C(c)為節(jié)點c的子節(jié)點集合，P(c)為節(jié)點c的父節(jié)點集合。當節(jié)點對的父節(jié)點對的信息量越大，節(jié)點對匹配的可能性越大，其相似度傳播因子也越大；當節(jié)點對的子節(jié)點對的信息量越小，節(jié)點對匹配的可能性越大，其相似度傳播因子也越大。

定義1 語義傳播因子SF

另外，考慮到概念圖中的節(jié)點，一般來說，概念的實例主要集中在葉子節(jié)點，非葉節(jié)點很少擁有大量的實例，所以在擁有大量實例的本體中，可以通過對概念實例的評估來增強概念相似度匹配的準確性。應用到相似度傳播中，采用“向上傳播”的方法［4］，將概念實例相似度從葉子節(jié)點傳播到父節(jié)點。如定義2所示，利用e1所有實例的相似度最大值和e2所有實例的相似度最大值來計算實例相似度傳播值，其中n和m分別為e1和e2實例的個數(shù)。

定義2 實例相似度傳播

1.3 快速穩(wěn)定匹配

在COMA［9］中，采用Selection算子對模式S1和S2匹配的結果集進行單向LargeSmall（|S1|＞|S2|），單向SmallLarge（|S1|≤|S2|）或雙向選擇（Both）。對于Selection算子的選擇策略，提供了選擇最大N個記錄的MaxN操作，選擇最大幾率的MaxDelta操作和閥值Threshold的操作。這些策略都需要對模式S1和S2進行遍歷，其算法復雜度為ri（單向），或2ri（雙向）。

本體1：1映射實際上可以看作是對二分圖的最大匹配［10-11］，二分圖指的是這樣一種圖：其所有的頂點分成兩個集合M和N，其中M或N中任意兩個在同一集合中的點都不相連。二分圖匹配是指求出一組邊，其中的頂點分別在兩個集合中，并且任意兩條邊都沒有相同的頂點，這組邊叫做二分圖的匹配，而所能得到的最大的邊的個數(shù)，叫做最大匹配。為了解決二分圖的最大匹配，采用HopcroftKarp［12］算法。在增加匹配集合M時，每次尋找多條增廣路，這樣迭代次數(shù)最多為2V0.5，所以，時間復雜度就降到了O(V0.5×E)，V為解析圖頂點數(shù)；E為解析圖邊數(shù)。

二分圖匹配本質上一種穩(wěn)定匹配，在后面的迭代映射算法中的收斂條件中，采用穩(wěn)定匹配均值作為迭代收斂條件。例如，有概念Old1，Old2，New1，New2，sim（Old1，New1）=0.9，sim（Old1，New2）=0.8，sim（Old2，New1）=0.6，sim（Old2，New2）=0.2，按穩(wěn)定匹配算法，有匹配［Old1，New1］，［Old2，New2］，其匹配值為0.9+0.2=1.1，而非穩(wěn)定匹配［Old1，New2］，［Old2，New1］的匹配值0.8+0.6=1.4。盡管后者匹配值大，但前者是穩(wěn)定匹配。

1.4 復合映射策略

1.4.1 復合映射路徑

基于前述的本體圖解析，從3個層次和兩個特征對異構本體進行映射分析。對于給定的本體，首先根據(jù)本體各節(jié)點元素及其上下文結構關系構建頂點和邊，進而構建本體解析圖；根據(jù)一定的策略注入本體的節(jié)點元素，對各節(jié)點元素進行遍歷，得到節(jié)點的上下文關系，即圖的結構特征；然后依據(jù)節(jié)點內容特征和相似度傳播特征對各節(jié)點元素進行相似度的計算；最后是建立基于重用思想上的迭代映射。

1.4.2 復合映射框架

如圖2所示，Matcher是最底層的匹配，采用基于詞匯路徑距離和基于wordnet的語義相似度的疊加值，完成節(jié)點內容特征層次上的相似度計算。MultiMatcher是多個Matcher的聚合，MultiMatcher基于某個節(jié)點進行遍歷，針對遍歷后的節(jié)點內容特征進行相似度計算，完成結構層次上的概念計算。Strategy是多個MultiMatcher的聚合，對解析圖節(jié)點進行樹遍歷，基于多個MultiMatcher完成某個策略的映射。最終，多個MultiMatcher和多個Matcher共同完成本體解析圖的結構特征和內容特征的多級映射策略，IterStrategy基于集合的交，并，差重用思想，對多個策略進行穩(wěn)定匹配迭代映射。

圖2 復合映射策略Fig.2 Com positemapping strategy

1.4.3 結果重用

在策略迭代IterStrategy中，我們引入了重用算子∩一∪，分別代表集合的交，差，并操作，用于迭代映射的結果集重用。∩操作intersect返回兩個不同結果集的共同映射對。一操作Diff返回映射對出現(xiàn)在一個結果集而沒有出現(xiàn)在另外一個結果集中。∪操作Union則合并兩個結果集的映射對。

1.4.4 收斂條件

對于每一種復合策略的映射，都可以得到一個映射結果集合?？紤]到映射算法本身屬于二分圖匹配的穩(wěn)定算法，故將兩次映射結果集合中的相似度均值誤差作為迭代收斂條件。

2 復雜度分析

整個映射系統(tǒng)包括本體解析圖構建，多個Strategy，每個Strategy包括多個MultiMatcher，以及每個Mulit?Matcher包括多個Matcher。在此定義：整個映射系統(tǒng)復雜度cis，本體解析圖構建復雜度cg；Strategy復雜度cs，MultiMatcher復雜度cmm，Matcher復雜度cm，以及結果集的合并操作復雜度cc，相似度計算復雜度cs和結果集匹配復雜度ch。

其中：nm，nmm，ns分別表示為每個MultiMatcher包括的Matcher個數(shù)，每個Strategy包括的MultiMatcher個數(shù)，整個系統(tǒng)包括的Strategy個數(shù)。故有：cis=cg+ns×{nmm×[(nm×(cc+cs)+cc)]}+cc+ch。

對于本體圖的解析，采用對圖進行樹遍歷的方法，故本體圖解析的復雜度為樹的遍歷復雜度O(nlog(n))。基于字符串距離的依賴于字符串的長度l，為O(l)。而基于wordnet的語義距離則是基于語義詞典，其計算復雜度為O(1)。在計算相似度傳播時，考慮到傳播的深度帶來的復雜性，一般只考慮節(jié)點的直接父節(jié)點，直接子節(jié)點和直接兄弟節(jié)點。故復雜度為這些節(jié)點集合的計算復雜度，設節(jié)點集合大小為s，結構相似度的計算復雜度為O(s2)。Hopcroft Karp快速匹配算法的復雜度為O(V^0.5 E),合并操作實際是集合的操作，故為O(s2)。

綜合以上，系統(tǒng)復雜度

考慮到一般結構集大小s一般遠小于節(jié)點數(shù)，故系統(tǒng)復雜度為O(nlog(n))+O(V0.5×E)。相對于一般系統(tǒng)如GLUE系統(tǒng)的復雜度O(n2)，系統(tǒng)運行復雜度大大降低，其主要原因在于首先采用了基于樹的解析圖結構，而不是對本體概念的遍歷（其復雜度為O(n2)；其次采用了快速匹配算法HopcroftKarp，將算法復雜度將為O(V0.5×E)；最后，盡管經(jīng)過了多次迭代和多種策略，但正是由于應用了多種策略，使得迭代相當少就可以達到很好的精度。

3 測試分析

本系統(tǒng)分為系統(tǒng)性能對比測試和實驗評估。系統(tǒng)性能考慮對兩個本體映射的解析特征結構，映射對個數(shù)以及映射時間進行比較，并在同一型號PC機和主流系統(tǒng)進行對比。實驗評估考慮的是對本體映射的質量進行比較。

3.1 系統(tǒng)性能測試

系統(tǒng)性能測試將采用OAEI2010［13］作為測試集，其中101#為基準集，分別選用103#，203#，224#，233#，246#，265#，301#為測試集。表2給出了一部分測試結果，包括本體的類，對象屬性，數(shù)據(jù)屬性以及實例個數(shù)、構建解析圖后的頂點和邊的個數(shù)、以及測試集相對于基準集的映射時間。相對來說，由概念及概念間關系解析出的頂點和邊數(shù)越少，解析時間越少，相應映射時間也少。233#解析后的邊數(shù)為0說明概念間沒有任何相對關系如繼承關系，ISA關系，屬性關系等等，概念為孤立的節(jié)點。

另外，本系統(tǒng)和另外兩個映射系統(tǒng)COMA［9］，S-Match［5］進行映射時間對比，從對比可以看出，本系統(tǒng)在性能上得到一定的提升。

表2 本體圖解析和映射性能Tab.2 Ontology graph parsing andmapping performance

3.2 實驗評估測試

實驗評估采用OAEI2010作為測試集，從編號101到304共50個數(shù)據(jù)集。F-Measure=(b2+1)PR/(b2P+R)［14］，設當b=1 時，F(xiàn)-Measure=2PR/(P+R)作為評估指標。其中：P為查準率Precision=發(fā)現(xiàn)的正確映射數(shù)/發(fā)現(xiàn)映射數(shù)；R為查全率或稱召回率Recall=發(fā)現(xiàn)的正確映射數(shù)/實際存在的映射數(shù)［15］；F-Measure指標綜合了信息檢索中的準確率和召回率。圖3比較了F-Measure在本文的測試系統(tǒng)IOMBF（iterative ontologymapping based figure），COMA++以及S-Match的曲線圖，可以看出，本文的測試效果優(yōu)于COMA++，與S-Match不相上下。

圖3 F-Measure實驗比較Fig.3 F-measure experiment com parison

4 結束語

本文通過對本體映射的分析，構建了一種基于多層解析的圖描述結構，并在此基礎上通過分析本體上下文結構，引入結構和實例相似度傳播和快速匹配算法，設計一種復合匹配策略，用于本體映射。算法分析和實驗證明，本系統(tǒng)能在保證性能基礎上提高一定映射的質量。本文側重于充分挖掘本體本身的內在結構，進而提出了相應的策略，對于不同的復合策略，將影響迭代算法的收斂次數(shù)，進而影響映射性能映射效果，因此，對于復合策略的研究有待于做進一步的工作。

［1］EHRIGM，STAABS.Quick ontologymapping［C］//Rome Proc of the ISWC‘04，Italy：Proc of VLDB’01，2004：683-697.

［2］YVESR，MANSUR R.ASMOV results for OAEI 2007［C］//Bexco Proc of the ISWC'07，Korea：Morgan Kaufmann Publishers，2007：141-151.

［3］唐杰，梁邦勇，李涓子，等.語義Web中的本體自動映射［J］.計算機學報，2006，29（11）：1956-1976.

［4］ DENGLLLAN N，SMASSMAN N.Instancematching w ith COMA++［J］.Model Managementand Metadaten-Verwaltung，2007，35（7）：56-63.

［5］ GIUNCHIGLIA F，SHVAIKO P，YATSKEVICH M.S-match：an algorithm and an implementation of semanticmatching［J］.Proceeding of ESWS，2004，23（5）：61-75.

［6］ DONG X，HALEVY A，MADHAVAN J.Reference reconciliation in complex information spaces［C］//Tomah in Proc of the 2005ACM SIGMOD IntConference on Managementof Data，New York ：ACM Press，2005：85-96.

［7］Muhlenbein H，Mahnig T.Convergence theory and application of the factorized distribution algorithm［J］.Journalof Computing and Information Technology，1999，7（1）：19-32.

［8］李熙，徐德智，王建新.本體映射中結構策略改進算法［J］.計算機工程與應用，2010，46（8）：24-28.

［9］ HH DO，RAHM E.COMA-a system for flexible combination of schemamatching approaches［J］.in Proceedingsof VLDB，2001，62（2）：610-621.

［10］ GUSFIELD D，IRVING RW.The stablemarriage problem：structure and algorithms［J］.M IT Press Cambridge，1989，10（3）：23-35.

［11］LOVASZ L.Matching theory［D］.New York：Elsevier Science Ltd，1996：233-235.

［12］ Blum N.A simplified realization of the hopocroftkarp approach tomaximum matching in genenalgraphs［J］.Inst fur Infromatik on Computing，1999，2（4）：225-231.

［13］宋嵐，雷莉霞，王洪.基于本體的智能化語義信息處理系統(tǒng)研究［J］.華東交通大學學報，2009，10（5）：31-34.

［14］ CJVAN RIJSBERGEN.Information retrieval［D］.2nd edition.Glasgow：Dept.of Computer Science University of Glasgow，1999：98-105.

［15］ HDOSM，E.Comparison of schemamatching evaluations［J］.workshop onWeb Databases，2002，6（1）：12-18.