人工智能在本體映射中的應用

苗永昌

(92349部隊 淄博 255178)

?

人工智能在本體映射中的應用

苗永昌

(92349部隊 淄博 255178)

本體映射被認為是異構信息集成的關鍵,研究者們提出了很多本體映射的方法,論文主要從三個方面說明人工智能思想在本體映射中的應用。 1) 基于元素文本相似度計算的方法,往往會借助于自然語言處理技術,對文本進行相關處理。 2) 本體映射問題本質上是一個二元分類問題,可以借助于機器學習的方法提高本體映射的質量。 3) 利用聚類算法將本體分塊,從而將大規模本體映射任務劃分成若干個子任務,有效地解決了大規模本體映射的挑戰。

本體映射; 自然語言處理; 機器學習; 聚類

Class Number TP399

1 引言

信息和通信技術的快速發展導致越來越多的異構信息充斥著互聯網,面對信息的海洋,如何組織、管理、維護、共享這些分布異構的信息顯得越來越困難。本體作為一種能在語義和知識層次上描述信息系統的概念模型建模工具[1],已經廣泛應用于語義信息集成、數據交換、Web服務自動組合等領域,被認為是異構信息集成的基礎。然而由于Web本身的分布性和自發性,不同的領域甚至是同一領域的不同組織,必然會定義不同的本體,這時本體自身就是異構的。因此,為了實現語義信息共享,首先必須建立異構本體中元素(概念、關系、實例等)之間的映射關系,這個過程稱之為本體映射[2]。

目前,本體映射已經成為了語義Web中的研究熱點,相關領域研究者進行了大量研究,提出了很多方法,概括起來可以分為:基于相似度的方法[3]、基于機器學習的方法[4]、基于邏輯推理的方法[5]以及基于背景知識的方法[6]。本體映射的綜述請參見文獻[7～8]。

人工智能是研究理解和模擬人類智能、智能行為及其規律的一門學科[9],因此可以利用人類進行本體映射的思想,為自動本體映射服務。本文將從以下三個方面說明人工智能在本體映射中的應用。

1) 基于自然語言處理的本體元素文本預處理;

2) 基于分類的本體映射方法;

3) 基于聚類的大規模本體映射。

2 本體及本體映射

為了便于表述,本節將有關術語定義如下。

1) 本體

本體的形式化定義有很多,但都離不開幾個關鍵的概念,即類、屬性、關系、實例以及公理,可形式化為

O={C,P,R,I,Ao}

其中,C為類集合,P為屬性集合,R為關系集合,I為實例集合,Ao為公理的集合。為便于表述,本文將本體中的類和屬性統稱為元素。

2) 本體映射

給定兩個本體O1和O2,本體映射就是建立這兩個異構本體的元素之間的語義關系,如圖1所示。在這個過程中,還有一些可選的輸入,例如已有的映射結果、外部資源、參數等。

圖1 本體映射過程

本體映射的輸出是一系列匹配元素對的集合,其中每一項為一個四元組:

M=〈e,e′,r,n〉

其中e和e′分別為O1和O2中的元素,r表示e和e′之間的語義關系(等價、包含等),n為e與e′之間關系r的置信度,通常取值為[0,1]。同大多數研究一樣,本文只考慮一對一的等價映射。

3 基于自然語言處理的本體元素文本預處理

在基于相似度的本體映射方法中,最重要的一類就是利用本體元素的文本特征計算相似度,從而得到映射。本體元素的文本特征包括id、label、comment以及其他描述性信息。提取出兩個本體對應元素的文本特征后,如果直接對這些文本進行相似度計算,則可能準確度不高,因此一般會對文本進行一些預處理,包括:

1) 托肯化。利用空格、下劃線、“駝峰式拼寫法”等特征,將字符串劃分成托肯集,例如,對“programCommittee”進行托肯化后得到單詞集{“program”,“Committee”}。

2) 正規化。消除大小寫、拼寫等文本風格上的差異,形成統一規范。

3) 提取詞干。語法上單詞存在各種變形,例如名詞復數、動詞的過去分詞等。可以利用很多方法(例如Porter stemming算法)提取單詞的詞干。例如“matched”和“matching”提取詞干后都為“match”。

4) 去除停用詞。有很多單詞是非常常見的,對于整個文本的含義不起關鍵作用的,可以去除。例如“has”、“the”等。

5) 同義詞擴展。利用WordNet獲取單詞的同義詞,進行補充。例如“contribution”與“paper”。

文獻[10]對本體映射常用的文本預處理策略進行了大量的實驗對比,發現常用的預處理策略并沒有較大程度上提高本體映射的質量。并且不難猜想,預處理策略消耗了更多時間,例如查詢WordNet數據庫會消耗較長時間。因此,這些預處理策略應根據實際應用情況進行合理選取。

4 基于分類的本體映射方法

本體映射的過程,實質上就是遍歷兩個本體的元素,然后判斷兩個元素是否存在語義聯系,即“等價(+1)”或者“不等價(-1)”。因此,本體映射問題可以轉換為一個二元分類問題:

m(e,e′,r)→{+1,-1}

其中,e和e′分別為O1和O2中的元素,r為e和e′之間的語義關系,此處為“等價”。因此,運用機器學習的方法,利用已有的本體映射結果訓練一個本體映射分類器,當面臨新的未知的本體映射任務時,可以很簡單地對本體映射的結果進行分類,如圖2所示。

需要說明的幾點是:

1) 訓練集的獲取。一種是采用專家驗證的方法,此過程需要消耗較長時間,并且準確度達不到100%。另外一種是利用公開的數據集,例如每年的OAEI本體映射競賽都提供了很多公開的、已知結果的本體映射數據集。但是,很多數據集都是關于某一領域的,利用一個領域的數據集訓練的分類器,是否在另外一個領域的本體映射任務上達到很高的分類效果,值得進一步研究。

2) 特征的提取。可以提取很多本體自身的特征,例如托肯比率、是否都為葉子節點等等;也可以直接利用各種相似度計算方法(matcher),例如編輯距離等。有興趣的讀者請參見文獻[11],該研究利用了相似度特征、本體特征、文本特征、結構特征,最后對這些特征進行了對比實驗,并指出相似度值對于分類效果有反作用。

圖2 基于分類的本體映射方法

3) 分類器的選擇。基本上滿足二元分類要求的分類器都可以使用,文獻[12]通過實驗對比了SVM、KNN、DT、AdaBoost等分類器,發現效果相當。

5 基于聚類的大規模本體映射

隨著本體應用的越來越廣泛,本體的規模越來越大,并且往往涉及多個領域,逐漸向通用本體發展。例如AGROVOC本體[13]包含28439個概念,涉及農業、森林、漁業、食品、環境等多個領域。

基于相似度的本體映射方法是目前最普遍的方法,在映射過程中對兩個本體的每一對元素對進行考慮,當面臨大規模的本體映射任務時,不僅會消耗大量的時間,占用大量的內存,并且映射的質量也會有所影響。因此,大規模本體映射是目前本體映射研究的一個挑戰[7]。

基于聚類的大規模本體映射采用了“分治法”的思想,如圖3所示,其基本過程為:首先將本體轉換成有向無環圖,然后給出本體內元素間相似度計算公式,并以此為基礎構造簇內凝聚度和簇間耦合度的計算方法,然后利用層次聚類方法(包括凝聚的層次聚類方法和分裂的層次聚類方法)將本體劃分成若干個大小合適的塊,并利用特定的方法找出兩個本體之間相似的塊,最后對這些塊對進行通用的本體映射。

圖3 基于聚類的大規模本體映射方法

文獻[14]利用了改進的ROCK聚類算法,基于結點的結構相似度將本體的元素分成若干個塊,然而不是直接對相似的塊進行映射,而是利用“RDF語句”重構RDF片段,然后進行映射,有效地解決了“空白結點”的問題。文獻[15]利用了AHSCAN聚類算法,它是一種社會網絡結點聚類算法,主要利用了結點之間的聯系,算法達到了O(n)的時間復雜度。

基于聚類的分塊思想,有效地解決了大規模本體映射的難題,但是劃分使得本體元素間的語義關系被強行地分割開來,映射結果的質量必然會有所影響,如何消除這些影響有待進一步研究。

6 相關研究

本體映射相關綜述參見文獻[7～8]。根據研究策略的不同,可以將本體映射相關研究分為基于相似度計算的方法、基于機器學習的方法、基于背景知識的方法和基于邏輯推理的方法。

6.1 基于相似度計算的本體映射

基于相似度計算的本體映射方法的基本思想是:本體O1和O2之間的映射發現問題可以分解為:對于O1中的每一個元素e,搜索其在O2中最相似的元素e′。根據使用特征的不同,又可以分為基于語言的策略、基于結構的策略、基于實例的策略。

基于語言的策略利用元素(及其鄰近元素)的描述性信息計算兩個對應元素的相似度,例如文獻[16]提出了“虛擬文檔”的概念,實際上就是一系列帶加權的托肯集,然后利用TF/IDF以及向量空間模型計算文檔間相似度。

基于結構的策略利用利用本體內元素之間的聯系,計算兩個對應元素的相似度。例如similarity flooding算法[17]是一種通用的圖匹配算法,通過建立相似度傳播圖,在每次迭代過程中,每對結點的相似度都將一部分傳遞給其鄰近的結點對,當達到穩定的狀態或最大迭代次數后,停止迭代,并獲得相似度。

基于實例的策略的基本思想是,如果兩個對應元素共有的實例越多,則它們越相似。這里共有的實例不一定完全相等,也可以是滿足一定相似度條件下的實例。文獻[18]分析了五種不同的實例相似度計算方法,并做了大量實驗對比,最后發現Jaccard方法效果最好。

6.2 基于機器學習的方法

基于機器學習的本體映射方法將映射問題轉換成分類問題,為某個元素選擇最優映射的問題就轉換成對其進行分類的問題。通常利用已知映射結果的數據集訓練分類器,當面臨新的映射任務時,對每對元素是否匹配進行預測。

GLUE[4]系統通過學習實例的聯合概率分布發現映射關系,文獻[19]利用各種相似度學習映射過程,并建立實例間的映射關系(本體映射的一種),文獻[20]通過機器學習的方法解決了多語言和不同語言間本體映射的問題。文獻[21]還研究了跨領域學習和分類的效果。

6.3 基于背景知識的方法

基于背景知識的方法利用其他的、通用的或領域內的知識,發現映射關系。例如利用上層通用本體,這些本體逐漸成為了領域的標準,比如Gene本體、UMLS本體等。

文獻[6]利用Google搜索引擎模擬元素之間的相似度,并建立映射關系。文獻[22]利用DBpedia發現模式映射。

6.4 基于邏輯推理的方法

基于邏輯推理的方法往往作為一種輔助方法,事先定義好一系列規則,在得到初步映射之后,對映射結果進行邏輯推理,如果發現矛盾,則給出相應的解決方案,從而提高映射結果的質量。

文獻[23]基于描述邏輯公式發現映射中的不一致性,并自動刪除錯誤的映射,并且該文章作者還開發了基于邏輯推理的開源API[24]。文獻[5]不僅能夠發現矛盾,并且能夠驗證正確的映射。

7 結語

在當前信息要求高度共享的條件下,異構信息集成顯得越來越重要,在語義Web環境下,本體映射被認為是解決語義異構問題的關鍵。人工的建立映射耗時而且容易出錯,因此,人工智能思想必然可以為本體映射服務。本文首先介紹了本體及本體映射相關定義,然后從三個方面詳細說明了人工智能思想在本體映射中的應用,同時也給出了下一步研究方向,最后對本體映射相關研究進行了綜述。

[1] 鄧志鴻,唐世渭,張銘,等.Ontology研究綜述[J].北京大學學報(自然科學版),2002,38(5):730-738.

[2] 仲茜,李涓子,唐杰,等.基于數據場的大規模本體映射[J].計算機學報,2010,33(6):955-965.

[3] 蔣湛,姚曉明,林蘭芬.基于特征自適應的本體映射方法[J].浙江大學學報(工學版),2014,48(1):76-84.

[4] Doan A H, Madhavan J, Dhamankar R, et al. Learning to match ontologies on the semantic web[J]. The VLDB Journal—The International Journal on Very Large Data Bases,2003,12(4):303-319.

[5] Jean-Mary 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.

[6] Gligorov R, ten Kate W, Aleksovski Z, et al. Using Google distance to weight approximate ontology matches[C]//Proceedings of the 16th international conference on World Wide Web. ACM,2007:767-776.

[7] Shvaiko P, Euzenat J. Ontology matching: state of the art and future challenges[J]. IEEE Transactions on Knowledge and Data Engineering,2013,25(1):158-176.

[8] Shvaiko P, Euzenat J. A survey of schema-based matching approaches[C]//Journal on Data Semantics IV. Berlin: Springer Heidelberg,2005:146-171.

[9] 賁可榮,張彥鐸.人工智能[M].第2版.北京:清華大學出版社,2013.

[10] Cheatham M, Hitzler P. String similarity metrics for ontology alignment[C]//The Semantic Web-ISWC 2013. Berlin: Springer Heidelberg,2013:294-309.

[11] Eckert K, Meilicke C, Stuckenschmidt H. Improving ontology matching using meta-level learning[M]. Semantic Web: Research and Applications. Heidelbery: Springer,2009:158-172.

[12] Nezhadi A H, Shadgar B, Osareh A. Ontology alignment using machine learning techniques[J]. International Journal of Computer Science & Information Technology,2011,3(2):139-150.

[13] http://www.fao.org/aims/ag_intro.htm[EB/OL].

[14] Hu W, Qu Y, Cheng G. Matching large ontologies: A divide-and-conquer approach[J]. Data & Knowledge Engineering,2008,67(1):140-160.

[15] Algergawy A, Massmann S, Rahm E. A clustering-based approach for large-scale ontology matching[C]//Advances in Databases and Information Systems. Springer Berlin Heidelberg,2011:415-428.

[16] Qu Y, Hu W, Cheng G. Constructing virtual documents for ontology matching[C]//Proceedings of the 15th international conference on World Wide Web. ACM,2006:23-31.

[17] Melnik S, Garcia-Molina H, Rahm E. Similarity flooding: A versatile graph matching algorithm and its application to schema matching[C]//Data Engineering, 2002. Proceedings. 18th International Conference on. IEEE,2002:117-128.

[18] Isaac A, van der Meij L, Schlobach S, et al. An Empirical Study of Instance-Based Ontology Matching[J]. The Semantic Web,2008:253-266.

[19] Rong S, Niu X, Xiang E W, et al. A machine learning approach for instance matching based on similarity metrics[C]//The Semantic Web-ISWC 2012. Springer Berlin Heidelberg,2012:460-475.

[20] Spohr D, Hollink L, Cimiano P. A machine learning approach to multilingual and cross-lingual ontology matching[C]//The Semantic Web-ISWC 2011. Springer Berlin Heidelberg,2011:665-680.

[21] Mao M, Peng Y, Spring M. Ontology mapping: as a binary classification problem[J]. Concurrency and Computation: Practice and Experience,2011,23(9):1010-1025.

[22] Gillani S, Naeem M, Habibullah R, et al. Semantic Schema Matching Using DBpedia[J]. International Journal of Intelligent Systems and Applications(IJISA),2013,5(4):72-80.

[23] Meilicke C, Stuckenschmidt H, Tamilin A. Repairing ontology mappings[C]//Proceedings of the 22nd national conference on Artificial intelligence-Volume 2. AAAI Press,2007:1408-1413.

[24] Meilicke C. Alignment incoherence in ontology matching[D]. Mannbeim: University Mannheim,2011.

Application of Artificial Intelligence in Ontology Matching

MIAO Yongchang

(No. 92349 Troops of PLA, Zibo 255178)

Ontology matching is considered as the key to heterogeneous information integration, and researchers have proposed many approaches of ontology matching. This paper mainly illustrates the application of the artificial intelligence idea in the ontology matching process from three aspects. First, the elements text based similarity computing approach often process of related text with the help of natural language processing technology. Second, the nature of ontology matching problem is one of the binary classification problems, which can use machine learning methods to improve the quality of ontology matching. Third, the ontology partition method based on clustering algorithm, which divides a large-scale ontology matching task into several sub-tasks, effectively solves the problem of large-scale ontology matching challenge.

ontology matching, nature language processing, machine learning, clustering

2015年1月11日,

2015年2月13日 作者簡介:苗永昌,男,工程師,研究方向:信息保障等。

TP399

10.3969/j.issn1672-9730.2015.07.019