基于編輯距離和WordNet的本體匹配算法研究與實(shí)現(xiàn)徐全發(fā)指導(dǎo)老師

1、基于編輯距離和WordNet的本體匹配算法研究與實(shí)現(xiàn)徐全發(fā)指導(dǎo)老師 凌興宏摘要：本體匹配旨在解決語(yǔ)義異構(gòu)問題，實(shí)現(xiàn)不同本體的應(yīng)用程序間的互操作性?；诰庉嬀嚯x和WordNet的算法是本體匹配的一種簡(jiǎn)單綜合方法。匹配中分別對(duì)兩種算法給與不同的動(dòng)態(tài)權(quán)值進(jìn)行綜合計(jì)算得出相似度。關(guān)鍵字：本體，本體匹配，編輯距離，WordNetAbstract: The ontology is to solve the matching semantic heterogeneity, realize the different ontology between applications interoperability

2、. Based on the edit distance and WordNet algorithm is a kind of simple ontology matching comprehensive method. Matching of the two algorithms are given different dynamic weights of comprehensive calculated similarity.Key word: ontology, the ontology matching, edit distance, WordNet0. 引言本體(Ontology)源

3、于哲學(xué)概念，從哲學(xué)范疇來(lái)說(shuō)，本體是對(duì)客觀存在的一個(gè)系統(tǒng)的解釋和說(shuō)明，關(guān)心的是客觀現(xiàn)實(shí)的抽象本質(zhì)1。學(xué)術(shù)界認(rèn)可的一種定義是Gruber提出的“本體是概念模型的明確的規(guī)范說(shuō)明”2。本體的目標(biāo)是捕獲相關(guān)領(lǐng)域的知識(shí)，確定該領(lǐng)域內(nèi)共同認(rèn)可的詞匯，通過概念之間的關(guān)系來(lái)描述概念的語(yǔ)義，提供對(duì)該領(lǐng)域知識(shí)的共同理解。目前本體已被成功應(yīng)用到萬(wàn)維網(wǎng)、人工智能等領(lǐng)域，在知識(shí)共享和傳播中擔(dān)當(dāng)了重要角色。本體可以有效克服分布式應(yīng)用間信息交換的語(yǔ)義異構(gòu)問題3。然而本體的創(chuàng)建和使用具有主觀性和自治性，即使在同一領(lǐng)域也存在著大量語(yǔ)義相關(guān)而表示語(yǔ)言和模型不同的本體，這就是本體異構(gòu)現(xiàn)象。解決本體異構(gòu)已成為基于本體的應(yīng)用面臨的關(guān)鍵問

4、題，本體匹配正是解決這一問題的有效途徑。近年來(lái)，本體匹配方法研究已成為語(yǔ)義web領(lǐng)域的熱點(diǎn)，國(guó)內(nèi)外學(xué)者相繼提出了各種匹配方法，包括基于文本、結(jié)構(gòu)、實(shí)例的匹配方法和基于知識(shí)庫(kù)的方法等。其中基于結(jié)構(gòu)特征的本體匹配通過分析實(shí)體在模式中的位置比較周圍節(jié)點(diǎn)的信息來(lái)計(jì)算相似度，該方法在本體缺乏充分的文本信息時(shí)尤為適用。在結(jié)構(gòu)匹配方法中主要用到了圖結(jié)構(gòu)、路徑結(jié)構(gòu)、分類結(jié)構(gòu)的匹配模式，這些方法大部分融入了相似度傳播的思想。此外為克服圖形匹配中過分重視圖結(jié)構(gòu)而忽略語(yǔ)義特征的缺陷，結(jié)構(gòu)方法中還補(bǔ)充了基于推理和定理證明的方法。然而目前的相似度計(jì)算方法大多需要遍歷全圖，計(jì)算所有實(shí)體間的兩兩相似度并選取相似度超過某一閾

5、值的實(shí)體作為匹配對(duì)，這種算法工作量大而且?guī)в忻つ啃裕绕洚?dāng)本體規(guī)模較大時(shí)計(jì)算復(fù)雜度也會(huì)大大增加。此外計(jì)算結(jié)構(gòu)相似度時(shí)往往只考慮鄰居節(jié)點(diǎn)的信息，而沒有充分利用節(jié)點(diǎn)的上下文語(yǔ)義信息，使得相似度的值過分依賴于鄰節(jié)點(diǎn)。1. 本體匹配算法的研究1.1 編輯距離方法通過編輯距離計(jì)算兩個(gè)字符串之間的相似度是一種很常用的本體匹配方法。原字符串(s)編輯距離表示的是兩個(gè)字符串通過插入字符、刪除字符、替換字符而變?yōu)橄嗄繕?biāo)串(t)所需要的操作數(shù)。在本體匹配中，我們首先抽取兩個(gè)待匹配本體中每一個(gè)實(shí)體的直接描述信息，通過計(jì)算這些描述信息之間的編輯距離來(lái)獲得實(shí)體與實(shí)體之間的相似度。將編輯距離運(yùn)用于相似度計(jì)算的公式如下3：

6、其中: SS( s1， s2) 表示兩個(gè)字符串s1 和s2 之間的相似度；ed( s1， s2) 表示字符串s1，和s2 之間的編輯距離; s1.len 和s2.len分別表示字符串s1和s2 的長(zhǎng)度。2.2 WordNetl)Wu和Palmer的方法Wu所提出的概念語(yǔ)義相似度算法4是基于is-a關(guān)系的，考慮了兩個(gè)概念在樹中的最近的公共父節(jié)點(diǎn)的深度以及兩個(gè)概念之間的距離。對(duì)于同一個(gè)父節(jié)點(diǎn)，兩個(gè)概念之間的距離越大，得到的相似度值越小；對(duì)于距離相同的兩個(gè)概念，如果父節(jié)點(diǎn)的深度越大，則語(yǔ)義相似度越大。如下面公式所示：其中l(wèi)so(c1, c2)指概念c1和c2最低的公共父節(jié)點(diǎn)，depth(c)表示概念

7、c在WordNet中的深度，即從根節(jié)點(diǎn)entity到c之間的距離。2)Leacock和Chodorow的方法Leacock和Chodorow提出的語(yǔ)義相似度算法5是一種典型的基于路徑的方法，此方法中，相似度由兩個(gè)概念之間的最短路徑所決定，最后計(jì)算的結(jié)果在0，l范圍內(nèi)，具體如公式所示:其中l(wèi)en(cl，c2)表示概念c1和c2之間的最短路徑，D表示W(wǎng)ordNet中is-a分類樹的最大深度。這兩種算法共同的優(yōu)點(diǎn)是模型簡(jiǎn)單，求解方便，實(shí)際中也得到廣泛的應(yīng)用。但是在計(jì)算距離的時(shí)候，所有相鄰節(jié)點(diǎn)的距離都是等長(zhǎng)的，沒有考慮各邊的權(quán)值，這就制約了模型的性能。2. 本體匹配系統(tǒng)的實(shí)現(xiàn)我們可以把本體匹配看成是圖

8、3.1所示的一個(gè)“黑盒”操作，其中輸入為兩個(gè)本體與已經(jīng)得到的映射單元集合M，通過考慮參數(shù)配置和外部資源，執(zhí)行匹配過程，輸出新的映射單元集合M。目前絕大多數(shù)本體匹配的相關(guān)研究都假設(shè)輸入為兩個(gè)本體，但是也有部分工作考慮多個(gè)本體間的匹配，例如文獻(xiàn)7利用關(guān)聯(lián)挖掘技術(shù)同時(shí)匹配多個(gè)本體。對(duì)于映射函數(shù)，有相當(dāng)一部分工作假設(shè)映射是雙向的，即概念間是一一對(duì)應(yīng)的關(guān)系。而對(duì)于相似度，也有部分工作的值域超出了0，1的范疇，例如文獻(xiàn)8中定義的相似度值域?yàn)?1，1。 matchingMO resourcesparameters圖3.1 匹配過程當(dāng)前的本體匹配過程通常遵循圖3.2中的基本框架流程。假設(shè)給定圖3.1中的輸入，

9、經(jīng)過以下5個(gè)步驟，輸出一組映射單元：1） 本體預(yù)處理：即對(duì)本體進(jìn)行選擇、修改或轉(zhuǎn)換，以避免和消除語(yǔ)言層的異質(zhì)問題。語(yǔ)言層異質(zhì)涉及到使用的不同的表示語(yǔ)言、建模方法與編輯工具，處理難度很大，應(yīng)盡量避免產(chǎn)生語(yǔ)言層異質(zhì)問題。2） 本體解析：目前已經(jīng)存在不少本體解析工具，例如Jena9、OWLAPIM10等。3） 特征選取：針對(duì)不同的匹配算法，選取不同的特征，例如本體的語(yǔ)言學(xué)特征、結(jié)構(gòu)特征等。4） 匹配算法：使用不同的特征，發(fā)現(xiàn)映射單元。這里需要注意的是，一個(gè)匹配算法可能會(huì)用到多個(gè)特征，而一個(gè)特征也可能被多個(gè)匹配算法所使用。另外，整個(gè)匹配過程還可能組合多種匹配算法，并多次迭代。5） 結(jié)果表達(dá)：采用標(biāo)準(zhǔn)化

10、的結(jié)果表達(dá)格式11，用于表達(dá)和輸出映射單元。6） 評(píng)價(jià)(可選步驟)：對(duì)匹配結(jié)果進(jìn)行評(píng)價(jià)，比如采用基于精度(precision)、召回率(recall)的評(píng)價(jià)方式12。特征選取匹配算法特征選取匹配算法本題解析結(jié)果表達(dá)評(píng)價(jià). . . . .迭代、組合圖3.2 本體匹配的基本流程本系統(tǒng)綜合編輯距離和WordNet算法來(lái)實(shí)現(xiàn)的，它將具有本體的查找、匹配和評(píng)價(jià)匹配結(jié)果的功能。匹配步驟如下：1） 輸入兩個(gè)待匹配本體，并解析這兩個(gè)本體。2） 運(yùn)行算法，獲得匹配結(jié)果。3） 輸出匹配結(jié)果。4） 對(duì)匹配結(jié)果評(píng)價(jià)。實(shí)現(xiàn)的主界面：3. 實(shí)驗(yàn)結(jié)果與分析為了更好地觀察匹配方法對(duì)某一類測(cè)試用例的匹配效果，我們將測(cè)試用例集分

11、成4類：分別是101-104、201-210、221-247和301-304。表2為算法對(duì)benchmarks測(cè)試用例集中各類測(cè)試用例的平均匹配結(jié)果。然后將本實(shí)驗(yàn)的結(jié)果和單獨(dú)用Wordnet匹配、Falcon系統(tǒng)的GMO模塊的計(jì)算結(jié)果做比較，如圖2所示。表2 數(shù)據(jù)結(jié)果測(cè)試用例PrecisionRecallF-Measure101-1040.881.000.94201-2100.880.720.71221-2470.811.000.89301-3040.840.700.764. 總結(jié)本體匹配作為一種處理語(yǔ)義異構(gòu)性的關(guān)鍵技術(shù)，在信息集成、分布式查詢處理等數(shù)據(jù)管理應(yīng)用中起到了重要的作用。本文的算法是

12、比較簡(jiǎn)單的，但使我完整的理解了本體匹配的全過程。在后續(xù)研究中，還將對(duì)算法將作如下改進(jìn)與完善：學(xué)習(xí)研究更復(fù)雜的效率更高的算法，通過調(diào)整各自的權(quán)重將它們合理的整合到一起以完善系統(tǒng)。參考文獻(xiàn)：l鄧志鴻，唐世渭，張銘，楊冬青，陳捷.Ontology研究綜述.北京大學(xué)學(xué)報(bào)(自然科學(xué)版)，第38卷，第5期，2002，P730-738.2 Gruber T R.A Translation Approach to portable ontology Specifications. Knowledge Acquisition，1993，P199-220.3 Stoilos G, Stamou G, Kollia

13、s S. A string metric for ontology alignmentC. In Proceedings of ISWC, 2005.4 JARRAR M， MEERSMAN R Ontology engineering the DOGMA approach C /Advances in Web Semantics I: Ontologies， Web Services and Applied Semantic Web， LNCS 4891 Berlin: Springer-Verlag， 2009: 7 -345Wu Z.，PalmerM，Verb Semantics and

14、 Lexical Selection，Proeeedings of the 32nd Annual Meeting of the Association for ComPutational Linguistics，Las Cruces，New Mexico，1994，P133-138.6 Leacock C.，Chodorow M.，Combining local context and WordNet similarity for word sense identification， In Fellbaum，1998，p265-283.7 He BChang KAutomatic Compl

15、ex Schema Matching across Web Query Interfaces：A Correlation Mining Approach川ACM Transactions on Database Systems，2006，31(1)：346-3958 Stoilos G, Sramou G，Kollias SA String Metric for Ontology AlignmentCIn：Proceedings of the 4th International Semantic Web Conference(ISWC)2005LNCS 372962-6379 McBride

16、BJena：Implementing the RDF Model and Syntax Specification CIn：Proceedings of the 2nd International Workshop Oil the Semantic Web200110 Bechhofer S，Lord P, Volz RCooking the Semantic Web with the OWL API CIn：Proceedings of the 2nd International Semantic Web Conference(ISWC)2003LNCS 2870，659-67511 Euzenat JAn API for Ontology Alignment CIn：Proceedings of the 3rd International Semantic Web Conference(ISWC)2004LNCS 3298，698-71212 Baeza-Yates