一種基于人工免疫的本體匹配算法*

董濟(jì)德，謝強(qiáng)，丁秋林

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

摘要：針對(duì)目前本體匹配算法存在運(yùn)行效率低和匹配準(zhǔn)確度不高等問題，提出一種基于人工免疫的動(dòng)態(tài)本體匹配算法，用來快速地從現(xiàn)有本體中篩選出用戶所需的子本體。該算法根據(jù)用戶行為信息構(gòu)建抗原本體模型，利用情景匹配確定其領(lǐng)域上下文環(huán)境，然后通過結(jié)構(gòu)匹配獲得匹配度最高的本體，最后對(duì)本體執(zhí)行語義匹配得到最終需要的子本體。實(shí)驗(yàn)表明，該算法提高了本體匹配的準(zhǔn)確度和效率。

關(guān)鍵詞：本體匹配；抗原本體；情景匹配；結(jié)構(gòu)匹配；語義匹配

通信地址：210016 江蘇省南京市秦淮區(qū)御道街29號(hào)南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

Address:College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,29 Yudao Rd,Qinhuai District,Nanjing 210016,Jiangsu,P.R.China

An ontology matching algorithm based on artificial immunity

DONG Ji-de，XIE Qiang，DING Qiu-lin

(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

Abstract:Because of the low efficiency and low accuracy existing in the traditional ontology matching algorithms, we introduce an automatic ontology matching algorithm based on artificial immunity to rapidly get the required sub-ontology from the existing ontology pool. The algorithm constructs an antigen ontology model according to the information of users’ behaviors, determines its domain context by matching the context, obtains the ontology with the highest matching degree via structure matching, and finally gets the right ontology through semantic matching. The experimental results show that the algorithm can improve the precision and the efficiency of ontology matching.

Key words:ontology matching;antigen ontology;context matching;structure matching;semantic matching

1引言

本體作為一種語義和知識(shí)層面上的概念共享模型[1]，可作為用戶和計(jì)算機(jī)以及計(jì)算機(jī)與計(jì)算機(jī)之間的知識(shí)載體，從而實(shí)現(xiàn)語義網(wǎng)中知識(shí)的統(tǒng)一化表示。從知識(shí)工程領(lǐng)域上解釋，本體是一種表述語義知識(shí)的方法[2]，并包含了對(duì)術(shù)語以及關(guān)鍵詞語的語義解釋。本體定義了一個(gè)統(tǒng)一化表述語義的數(shù)據(jù)視圖,并且可以用來對(duì)同一框架內(nèi)的異構(gòu)數(shù)據(jù)源進(jìn)行建模。另外，本體可為不同數(shù)據(jù)源模型之間提供相互溝通交流的能力，并對(duì)模型內(nèi)蘊(yùn)含的信息進(jìn)行集成。

雖然本體在語義和知識(shí)層次上得到了廣泛的應(yīng)用，但基于本體的知識(shí)表示方法在一定程度上并沒有充分解決本體的互操作以及相互通信的問題。相同或者相似領(lǐng)域間的本體亟需一種方法建立聯(lián)系，因此，本體匹配被人們提出，用來解決本體之間的協(xié)調(diào)與通信問題。本體匹配作為一種打破本體與本體之間的獨(dú)立性的方法，是一種用來查找本體之間或本體內(nèi)部元素之間相似程度的關(guān)鍵技術(shù)，能夠解決不同領(lǐng)域內(nèi)或者相同領(lǐng)域內(nèi)本體異構(gòu)的問題，被一致認(rèn)為是解決人機(jī)交互、機(jī)機(jī)交互時(shí)語義異構(gòu)問題的有效方法。而且，本體匹配對(duì)于本體映射與集成、本體的檢索以及本體重用、本體知識(shí)集成、語義Web服務(wù)的匹配，以及基于本體的軟件需求工程等是不可缺少的重要環(huán)節(jié)[3]。

本體匹配目前是一個(gè)活躍的研究領(lǐng)域，研究人員對(duì)此提出了眾多解決方案。在生物醫(yī)學(xué)和生物信息學(xué)的知識(shí)領(lǐng)域，本體匹配發(fā)展得益于對(duì)詞匯和本體的主動(dòng)研究和應(yīng)用。統(tǒng)一醫(yī)學(xué)語言系統(tǒng)UMLS(Unified Medical Language System)正是一個(gè)由國(guó)家醫(yī)學(xué)圖書館事業(yè)創(chuàng)建的規(guī)模浩大的醫(yī)學(xué)和生物術(shù)語單一存儲(chǔ)庫[2]。目前，對(duì)本體匹配的研究主要圍繞語義或者結(jié)構(gòu)方法展開。黃濤等人[1]提出的基于虛擬路徑的本體匹配算法OMA-VP(Ontology Matching Approach based on Virtual Path)對(duì)本體結(jié)構(gòu)匹配進(jìn)行改進(jìn)，提出了虛擬路徑的概念，一定程度上提高了本體匹配的準(zhǔn)確度。但是，該算法僅是對(duì)本體匹配局部性的改進(jìn)，并沒有在全局上降低本體匹配效率，而且匹配準(zhǔn)確度不確定。OLA(OWL-Lite Alignment)[2]采用加權(quán)平均值沿多個(gè)本體特征之間的匹配，并引入了一種基于數(shù)值分析的實(shí)體集的相似性計(jì)算機(jī)制，使得本體匹配準(zhǔn)確度有所提高，但算法的匹配效率較低。ASMOV算法[2]對(duì)OLA進(jìn)行了一系列的改進(jìn)，以圖形化本體的表示方法描述本體之間的關(guān)聯(lián)，根據(jù)術(shù)語關(guān)鍵詞、結(jié)構(gòu)以及實(shí)體三個(gè)層次分別計(jì)算出術(shù)語相似性、結(jié)構(gòu)相似性和實(shí)體相似性的大??；然后對(duì)計(jì)算結(jié)果進(jìn)行參數(shù)校準(zhǔn)，從而得到最終本體匹配值。但是，該算法沒有考慮用戶的上下文語境，因此本體匹配的準(zhǔn)確度并不理想。Falcon-AO(Finding，aligning and learning ontologies,ultimately for capturing knowledge via ontology-driven approaches)是由東南大學(xué)瞿裕忠教授和胡偉博士等人[1]開發(fā)的本體對(duì)齊工具，它利用一個(gè)語言匹配器并結(jié)合了一種以二部圖結(jié)構(gòu)表示的待匹配本體結(jié)構(gòu)的方法，通過計(jì)算概念之間語義相似系數(shù)進(jìn)行了相似性分析，但大量的冗余計(jì)算降低了算法的執(zhí)行效率。H-Match是由意大利米蘭大學(xué)Castano S等人提出的面向分布式的本體的動(dòng)態(tài)匹配方法，通過輸入兩個(gè)待比較本體得到兩個(gè)本體中具有語義相似性的元素對(duì)[1]，來確定兩個(gè)本體之間的相似度。但是，該算法沒有充分解決因本體異構(gòu)而引發(fā)的匹配問題，同時(shí)該算法也沒有解決本體情景不匹配的情況下出現(xiàn)的匹配問題。蓋克[3]提出了一種基于概念上下文的本體匹配算法CBOMA(Context-Based Ontology-Matching Algorithm)，通過構(gòu)建概念結(jié)構(gòu)層次樹來實(shí)現(xiàn)對(duì)本體自上而下的匹配，提高了本體匹配的準(zhǔn)確度，但無法解決不同領(lǐng)域內(nèi)本體匹配相似度高的問題。王曉云等人[4]將改進(jìn)的蟻群算法應(yīng)用到本體匹配算法中，通過構(gòu)建距離矩陣、能量損耗矩陣和信息素矩陣來對(duì)本體匹配算法流程的進(jìn)行優(yōu)化，其匹配精確度雖然得到提高，但大量的冗余計(jì)算降低了算法執(zhí)行效率。針對(duì)目前本體匹配算法中存在的問題，本文提出了一種基于人工免疫的動(dòng)態(tài)本體匹配算法AOMA-AI(Automated Ontology Matching Algorithm based on AI)。人工免疫算法既能夠提供噪聲忍耐、無監(jiān)督學(xué)習(xí)、自組織以及記憶等學(xué)習(xí)機(jī)理，又結(jié)合了神經(jīng)網(wǎng)絡(luò)和機(jī)器推理等系統(tǒng)的一些優(yōu)點(diǎn)，因此能夠提供解決新問題方法的潛力[5,6]。AOMA-AI算法核心思想是根據(jù)用戶行為信息構(gòu)建抗原本體模型，利用情景匹配確定其領(lǐng)域上下文環(huán)境，然后通過結(jié)構(gòu)匹配獲得匹配度最高的本體，最后對(duì)本體執(zhí)行語義匹配得到最終需要的子本體。AOMA-AI基于人工免疫算法，對(duì)待匹配的本體賦予一定的生存期限，在匹配過程時(shí)不斷更新本體集合，這是其他本體匹配算法中所不具有的。所以，利用人工免疫算法的收斂快、耗時(shí)低等優(yōu)點(diǎn)，AOMA-AI算法在進(jìn)行本體匹配時(shí)可進(jìn)一步提高本體匹配準(zhǔn)確度和效率。

2AOMA-AI算法框架

本體匹配的過程是對(duì)抗原本體的系統(tǒng)解讀，即將外界的本體通過匹配算法與系統(tǒng)中既定義的流程本體對(duì)應(yīng)。所謂抗原本體，是對(duì)用戶行為信息進(jìn)行本體化描述而得到計(jì)算機(jī)可識(shí)別的本體。本體匹配圖如圖1所示。

Figure1　Ontology matching process 圖1　本體匹配過程圖

圖2給出了AOMA-AI算法的組成框架，其大致可以分為四步：(1)根據(jù)用戶行為信息構(gòu)建抗原本體模型；(2)利用情景匹配確定其領(lǐng)域上下文環(huán)境；(3)通過結(jié)構(gòu)匹配獲得匹配度最高的子本體；(4)對(duì)本體執(zhí)行語義匹配，得到最終的子本體并輸出。

Figure 2　Structure of AOMA-AI 圖2　AOMA-AI算法框架圖

3基于人工免疫的本體匹配算法

3.1本體相關(guān)定義

傳統(tǒng)本體按照分類法來組織，包含了四個(gè)基本的建模語言，即概念類(Concept)、實(shí)體類(Instances)、屬性(Property)和公理(Axioms)[3，7]。概念采用框架結(jié)構(gòu)，包括概念的名稱以及用自然語言對(duì)概念的描述[7]；實(shí)體類是指屬于某概念的基本元素，即該概念類對(duì)應(yīng)的具體實(shí)體；公理主要是用來描述屬性與屬性之間的包含關(guān)系以及類與類之間的從屬關(guān)系，同時(shí)公理也用來表示取值限制。

定義1本體可以用一個(gè)五元組表示：O={C,R,Hc,A,I},其中，C稱為本體中的概念集；R代表了領(lǐng)域中概念之間的相互關(guān)系，形式上定義為n維的笛卡爾積的子集，其基本關(guān)系可表示為part-of、kind-of、instant-of和attribute-of四種；Hc是本體概念的層次關(guān)系，其中Hc?C×C,Hc(C1,C2)表示C1是C2的子類；A為公理集合，是定義在概念和屬性上的限定和規(guī)則；I為C概念類對(duì)應(yīng)的實(shí)例[7]。

關(guān)鍵詞定義2抗原本體，也稱為任務(wù)本體，是從用戶輸入信息中獲取來實(shí)現(xiàn)對(duì)信息的標(biāo)準(zhǔn)化、本體化描述而得到的計(jì)算機(jī)可識(shí)別的本體。

定義3記憶本體是這樣一類本體，即經(jīng)過抗原本體的多次刺激后，本體集合中的某一個(gè)或某一些本體多次被選中而轉(zhuǎn)化形成的本體。

本體表示是本體匹配過程中的一個(gè)重要環(huán)節(jié)。文獻(xiàn)[8]中提供了一種本體結(jié)構(gòu)圖OSG(Ontology Structure Graph)的表示方法，該方法能夠形式化表示出本體以及本體內(nèi)實(shí)體的從屬關(guān)系。鑒于本體結(jié)構(gòu)圖能夠充分表示本體結(jié)構(gòu)，以及本體內(nèi)實(shí)體與實(shí)體之間、實(shí)體與屬性之間的從屬關(guān)系，本文也采用本體結(jié)構(gòu)圖表示本體，并且形式化地表示出本體之間匹配的過程。另外，由于本體在加入情景感知的特性后使本體具有了對(duì)象化、情景化的可分辨性的特征[9]，本文進(jìn)行本體匹配時(shí)能夠根據(jù)本體情景減少匹配次數(shù)，從而提高效率。

3.2AOMA-AI算法設(shè)計(jì)

根據(jù)用戶輸入信息，首先利用程序構(gòu)建出抗原本體O；然后構(gòu)建出本體內(nèi)的實(shí)體E；最后在本體內(nèi)插入屬性值。上述過程結(jié)束后，提取用戶輸入信息關(guān)鍵詞W，然后進(jìn)入算法本體匹配過程。

AOMA-AI從本體集群中匹配最優(yōu)本體的計(jì)算方法如公式(1)表示：

(1)

其中，Sim函數(shù)是本體匹配函數(shù)；Si為本體群中第i個(gè)本體子群；S′為待匹配本體；δ為設(shè)定的閾值；O則為本體子群Si中的某一個(gè)本體。

接下來將介紹本體匹配函數(shù)的詳細(xì)過程。

本文本體匹配分為初始匹配、外匹配和內(nèi)匹配三個(gè)過程，分別對(duì)應(yīng)于情景匹配、結(jié)構(gòu)匹配和語義匹配三個(gè)部分，詳細(xì)匹配過程如下：

(1)初始匹配，即為情景匹配。在基于語義Web的知識(shí)查找系統(tǒng)中，領(lǐng)域匹配是本體匹配中很重要的一步。在特定領(lǐng)域確定的情況下，對(duì)后續(xù)的本體進(jìn)行結(jié)構(gòu)和語義匹配能夠提高匹配的查準(zhǔn)率和查全率[1]，此處的領(lǐng)域匹配是對(duì)各領(lǐng)域內(nèi)關(guān)鍵詞的匹配過程。

(2)外匹配，即為結(jié)構(gòu)匹配，對(duì)于兩個(gè)待比較本體，如果其結(jié)構(gòu)上差異程度非常大，那么后續(xù)的語義匹配就顯得沒有意義，所以，對(duì)本體的結(jié)構(gòu)匹配非常重要，能夠在一定程度上減少迭代次數(shù)，降低時(shí)間復(fù)雜度。

(3)內(nèi)匹配，即為語義匹配，是這次匹配過程的主要組成部分，該匹配包含了貪婪實(shí)體匹配和屬性匹配兩個(gè)過程。

設(shè)F={C,H,E}為計(jì)算相似度值的操作集，分別對(duì)應(yīng)于上述的三種匹配過程，C為本體的上下文概念集，H為層次結(jié)構(gòu)，E為本體內(nèi)實(shí)體。對(duì)于目標(biāo)本體O和待匹配本體集S中的任意本體O′，那么，相似度匹配計(jì)算結(jié)果可用公式(2)表示：

(2)

其中α、β、γ分別為控制參數(shù)，而且α、β、γ滿足以下條件：

AOMA-AI算法的流程過程可用以下八個(gè)步驟描述，其中(1)～(3)為情景匹配部分，(4)～(6)為結(jié)構(gòu)匹配部分，(7)為語義匹配部分，(8)為算法流程輸出部分。AOMA-AI算法的具體描述如下：

關(guān)鍵詞(1)獲取抗原本體O的描述W，并確定本體O′集中每個(gè)功能描述關(guān)鍵詞Mi(i=1,2,3,…,n)，即首先考察每個(gè)本體是否存在與抗原本體關(guān)鍵詞W相關(guān)聯(lián)的概念(例如同義概念、父子概念、包含或者被包含概念等)[10]；同時(shí)，設(shè)定一個(gè)匹配閾值θ來保證情景匹配結(jié)果的準(zhǔn)確性，閾值θ初始值為θ0，并隨著匹配迭代過程不斷更新。

(2)通過詞語相似性公式(3)，計(jì)算抗原和本體集內(nèi)各本體的領(lǐng)域相似度[11]：

SimC(O,O′)=Comm(W,Mi)-

Diff(W,Mi)+Winkler(W,Mi)

(3)

關(guān)鍵詞其中，Comm表示兩個(gè)最大匹配字串所占比例，Diff表示未匹配比例，Winkler函數(shù)的返回值表示修正參數(shù)[12]，其相應(yīng)的計(jì)算公式如公式(4)～(6)所示：

(4)

Diff(W,Mi)=

(5)

Winkler(W,Mi)=

WinkerImpro(W,Mi,Comm(W,Mi))

(6)

WinkerImpro(W,Mi,comm)=

CPL*0.1*(1-comm)

關(guān)鍵詞其中，CPL(Common Prefix Length)為待比較W和Mi相同前綴的長(zhǎng)度值；p為調(diào)節(jié)系數(shù)，根據(jù)文獻(xiàn)[3]取p=0.6。

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

doi:10.3969/j.issn.1007-130X.2015.06.014

收稿日期：*2014-06-17;修回日期：2014-09-18

基金項(xiàng)目：江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金資助項(xiàng)目(SBY201320423)

作者簡(jiǎn)介:

(3)利用公式(3)得出領(lǐng)域相似度最大的本體并進(jìn)行判斷。如果SimC(O,O′)≥θ，則可以確定該本體領(lǐng)域即可作為抗原的領(lǐng)域，可直接進(jìn)入本體結(jié)構(gòu)和語義匹配來計(jì)算Sim(O,O′)值的大小。如果比較本體為記憶本體，并且Sim(O,O′) ≥δ，則輸出匹配的記憶本體，否則將遍歷本體集合，查找與之匹配的子本體。

(4)情景匹配結(jié)束后，接下來是結(jié)構(gòu)匹配和語義匹配的過程。首先，利用本體的概念關(guān)系計(jì)算本體結(jié)構(gòu)匹配度大小值SimH(O,O′)；其次，構(gòu)建本體的實(shí)體相似度矩陣，計(jì)算本體語義匹配度的大小SimE(O,O′)。請(qǐng)注意，本文在結(jié)構(gòu)匹配中也需要設(shè)定一個(gè)閾值，只有當(dāng)SimH(O,O′)大于閾值時(shí)才能繼續(xù)執(zhí)行語義匹配過程(為降低算法復(fù)雜性，該閾值暫設(shè)為一定值)。

(5)本體結(jié)構(gòu)匹配主要包括實(shí)體的結(jié)構(gòu)匹配，下面將詳細(xì)介紹匹配過程。首先，實(shí)體結(jié)構(gòu)匹配主要是對(duì)本體內(nèi)實(shí)體與實(shí)體之間關(guān)系的匹配，其中本文對(duì)實(shí)體與實(shí)體的關(guān)系界定是父子、兄弟和不相關(guān)三種。假設(shè)待匹配本體O和O′中的實(shí)體e和e′，且兩實(shí)體對(duì)應(yīng)的父實(shí)體為u和u′，對(duì)應(yīng)的子實(shí)體分別為v和v′，對(duì)應(yīng)的實(shí)體結(jié)構(gòu)圖如圖3所示。

Figure 3　Ontology structure matching 圖3　本體結(jié)構(gòu)匹配圖

(6)本體結(jié)構(gòu)匹配的計(jì)算公式描述如(7)所示:

SimH(O,O′)=WpSimEp(u,u′)+

WeSimEe(e,e′)+WdSimEd(v,v′)

(7)

而且，對(duì)應(yīng)的約束條件為：

Wp+We+Wd=1

其中，shortcut為實(shí)體e和e′之間最短路徑長(zhǎng)度，Path(e,e′)表示實(shí)體e和e′之間最短路徑的方向改變次數(shù)；≡表示對(duì)等關(guān)系，≤表示從屬關(guān)系，∈表示部分整體關(guān)系；Cbase(e,e′)是對(duì)實(shí)體e和e′的邏輯關(guān)系的表示方法；C為對(duì)關(guān)系的單位表示[1];Wp表示前驅(qū)元素及其屬性的語義相似性分配的權(quán)重比例，We表示實(shí)體的獨(dú)立性語義相似性分批的權(quán)重，Wd表示實(shí)體與后驅(qū)元素的相似性比例[1]。

(7)本體實(shí)體的語義相似度計(jì)算過程。

首先，構(gòu)建相似度實(shí)體矩陣S，具體形式如下所示[13]：

其次，定義基于相似度矩陣S的關(guān)聯(lián)集合AS，獲取AS的方法如下公式所示：

此處對(duì)el、et的取值限制如公式(8)所示：

(8)

第三，實(shí)體內(nèi)部的相似度主要是屬性相似度計(jì)算(有關(guān)詞語相似度則是根據(jù)公式(3)進(jìn)行計(jì)算)，其相應(yīng)的計(jì)算公式如(9)所示：

(9)

最后，計(jì)算實(shí)體的相似度，具體的計(jì)算方法如公式(10)所示：

(10)

(8)根據(jù)公式(1)和公式(2)，從本體集合中檢索出與抗原本體匹配度值最高的本體O′并輸出，得到用戶所需的本體。

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

4.1評(píng)估標(biāo)準(zhǔn)

為了測(cè)試本體匹配算法的有效性，本文從質(zhì)量和性能兩個(gè)方面對(duì)AOMA-AI算法進(jìn)行效率評(píng)價(jià)[1]。在質(zhì)量評(píng)價(jià)測(cè)試中，最著名的標(biāo)準(zhǔn)是來源于信息檢索領(lǐng)域的查準(zhǔn)率(Precision)和查全率(Recall)兩個(gè)指標(biāo)[1]。查準(zhǔn)率表示算法匹配過程中匹配正確次數(shù)的數(shù)量占所有匹配次數(shù)的百分比；查全率表示的是運(yùn)用匹配算法得到的正確匹配次數(shù)占所有計(jì)算正確結(jié)果的數(shù)量的比例[1]，在理想情況下，Precision= Recall=1。

但是，在實(shí)際評(píng)價(jià)中，單獨(dú)使用查準(zhǔn)率或查全率都不能準(zhǔn)確地評(píng)價(jià)算法的質(zhì)量。查全率和查準(zhǔn)率結(jié)果之間會(huì)出現(xiàn)很大的誤差，如果僅靠這個(gè)標(biāo)準(zhǔn)并不能完全判定評(píng)價(jià)算法的質(zhì)量[1]。文獻(xiàn)[1]采用了另外兩種評(píng)估變量F-Measure和OverAll來調(diào)整查準(zhǔn)率和查全率的綜合測(cè)量結(jié)果。本文也采用這兩個(gè)評(píng)估指標(biāo)來評(píng)價(jià)算法的效率。

(11)

(12)

4.2算法分析

從算法流程上講，AOMA-AI算法是對(duì)OMA-VP算法[1]和ASMOV算法[2]的改進(jìn)。ASMOV算法的本體匹配過程包含術(shù)語匹配、結(jié)構(gòu)匹配和實(shí)體匹配三個(gè)過程，OMA-VP算法的本體匹配過程包括結(jié)構(gòu)匹配和語義相似匹配，結(jié)合上述兩種匹配算法的優(yōu)點(diǎn)，AOMA-AI的本體匹配過程除了包括結(jié)構(gòu)匹配和語義匹配兩個(gè)過程之外，新增了情景上下文匹配過程用來減少本體匹配的迭代次數(shù)，從而降低匹配時(shí)間，提高本體匹配效率。

設(shè)本體集合S，且|S|=n，平均每個(gè)本體中包含x個(gè)實(shí)體；由于三種算法中本體與本體之間匹配過程包括了結(jié)構(gòu)和實(shí)體匹配過程，不妨設(shè)任意兩個(gè)本體O1與O2之間匹配的平均時(shí)間為T(O1,O2)，結(jié)構(gòu)匹配平均時(shí)間為T(Hc)，實(shí)體匹配平均時(shí)間為T(E)。T(O1,O2)與T(Hc)和T(E)的關(guān)系為T(O1,O2)=T(Hc)+T(E)。

設(shè)記憶本體集合M長(zhǎng)度|M|=l，此處l為常數(shù)值。

本體匹配算法時(shí)間復(fù)雜度分析過程如下：

首先，AOMA-AI算法時(shí)間復(fù)雜度分析。AOMA-AI采用了分治策略，即將本體集合S集合逐次分解子本體集合，然后遞歸調(diào)用。具體過程描述為：首先，通過情景匹配初步分解為m個(gè)子本體Si(1≤i≤m，m≤n)，選擇滿足條件的子本體集；然后，通過情景匹配遞歸調(diào)用子本體集，從中獲取符合條件的子本體Sij(1≤j≤r,r≤m)。因此，AOMA-AI算法的平均時(shí)間復(fù)雜度可表示為O(logn)(T(O1,O2))；AOMA-AI算法的最差時(shí)間復(fù)雜度為O(n)(T(O1,O2))。由于記憶本體集合M的存在，使得AOMA-AI算法時(shí)間復(fù)雜度最優(yōu)可表示為O(1)( T(O1,O2))。

其次 ，OMP-VP、CBOMA和ASMOV算法的時(shí)間復(fù)雜度分析。OMP-VP、CBOMA和ASMOV算法是對(duì)本體集合S中的所有本體遍歷，其時(shí)間復(fù)雜度直接表示為O(n)(T(O1,O2))，并不存在最優(yōu)時(shí)間復(fù)雜度的情況。

因此，通過比較AOMA-AI、OMP-VP、CBOMA和ASMOV算法的時(shí)間復(fù)雜度可以看出，ASMOV算法在進(jìn)行本體匹配過程時(shí)，利用對(duì)本體集合的預(yù)操作減少了本體匹配的迭代次數(shù)，相對(duì)其他本體匹配算法而言，匹配效率有所提高。

本體匹配算法準(zhǔn)確性分析如下：AOMA-AI算法是對(duì)OMA-VP算法的改進(jìn)，新增情景匹配過程用來保證本體O1和O2的結(jié)構(gòu)和語義匹配過程是在領(lǐng)域上下文相似的前提下進(jìn)行的，這樣可以對(duì)相似詞語進(jìn)行過濾，提高本體匹配的準(zhǔn)確度；AOMA-AI算法與ASMOV算法相比，除了情景匹配的優(yōu)點(diǎn)外，還明顯簡(jiǎn)化了本體比較的過程，減少冗余計(jì)算，從而提高了算法效率；AOMA-AI算法和CBOMA算法相比，相同點(diǎn)是對(duì)實(shí)體匹配都是對(duì)術(shù)語和屬性匹配，而AOMA-AI算法通過情景匹配獲取用戶情景上下文來確定本體領(lǐng)域提高匹配準(zhǔn)確度，并且引入了記憶本體集來提高本體匹配效率。

4.3實(shí)驗(yàn)結(jié)果

本次實(shí)驗(yàn)硬件環(huán)境為E7500 2.93 GHz的CPU，2 GB內(nèi)存，軟件環(huán)境為Eclipse-SDK-3.7。根據(jù)第3節(jié)本體匹配過程，設(shè)計(jì)出其中某一本體的實(shí)體結(jié)構(gòu)圖，該圖中沒有標(biāo)記處實(shí)體內(nèi)屬性，匹配過程如圖4所示。

圖4中本體O為根據(jù)用戶信息構(gòu)建出的抗原本體，而本體O′則是本體集合中的本體。圖4表示出本體匹配時(shí)實(shí)體匹配過程假設(shè)抗原本體O和本體O1中均包含四個(gè)實(shí)體，那么本體匹配過程是通過比較時(shí)實(shí)體相似度構(gòu)建出相應(yīng)的本體相似度矩陣。

Figure 4　Internal entity comparison of ontologies 圖4　本體內(nèi)部實(shí)體比較

AOMA-AI算法閾值δ、θ的確定，對(duì)于δ值的選取如圖5所示。

Figure 5　Result of δ 圖5　δ值結(jié)果

選取δ值太大，將會(huì)使得記憶本體集成為虛設(shè)，而δ值過小，則將會(huì)受制于記憶本體集合而對(duì)匹配的準(zhǔn)確性產(chǎn)生影響，因此本文對(duì)δ值設(shè)定了最大可能區(qū)間δ∈[0.5,0.8]。圖5a中顯示了δ值從0.5到0.8的變化結(jié)果，且當(dāng)δ=0.7時(shí)其匹配度能滿足條件，且匹配效率高。

對(duì)于θ的初始化值θ0的選取將影響本體匹配結(jié)果，由于θ的大小是隨迭代過程變化的，所以對(duì)于θ0值初始化值設(shè)定為θ0∈[0.3,0.7]。圖5b顯示了θ0值從0.3到0.7變動(dòng)時(shí)本體匹配的變化結(jié)果(θ0不妨取0.4)。設(shè)θ值變化公式為：θ=θ0+[logmn]*m/n(m

對(duì)于參數(shù)α、β、γ值的選取對(duì)實(shí)驗(yàn)結(jié)果的影響，如圖6所示。

Figure 6　Results of parameter selection 圖6　參數(shù)選擇結(jié)果

當(dāng)α取值太大時(shí)，本體匹配將會(huì)受限于本體上下文領(lǐng)域而忽視了本體結(jié)構(gòu)和語義匹配結(jié)果；當(dāng)α取值太小，則會(huì)對(duì)匹配結(jié)果值造成很大的影響。從圖6顯示結(jié)果可以看出，當(dāng)α∈[0.4,0.5]時(shí)，本體匹配平均值最大，為了使得算法容易控制，本文中將參數(shù)α和β值暫時(shí)定為0.4和0.3。

本文根據(jù)OAEI 2014測(cè)試數(shù)據(jù)集來測(cè)試AOMA-AI算法的運(yùn)行效果。對(duì)于OAEI 2014數(shù)據(jù)集，本文選取#101、#102、#103、#104、#301、#302、#303和#304數(shù)據(jù)作為本文算法的測(cè)試數(shù)據(jù)集。AOMA-AI算法對(duì)傳統(tǒng)本體匹配算法的改進(jìn)主要有兩點(diǎn)：第一，融入人工免疫算法，以提高本體匹配效率；第二，加入情景匹配，以提高本體匹配的準(zhǔn)確度。所以，這次實(shí)驗(yàn)過程主要是結(jié)合以上兩點(diǎn)展開的。

(1)算法效率比較。由于某特定的抗原本體對(duì)數(shù)據(jù)集多次刺激后生成了相應(yīng)的記憶抗體，這時(shí)通過對(duì)傳統(tǒng)本體匹配算法ASMOV[2]、基于人工免疫的本體匹配算法AOMA-AI以及無人工免疫的本體匹配算法AOMA(AOMA算法是AOMA-AI算法的一部分，是在不考慮記憶本體集合時(shí)執(zhí)行全本體匹配的算法，即進(jìn)行本體匹配過程時(shí)跳過記憶本體集合直接執(zhí)行情景匹配、結(jié)構(gòu)匹配和語義匹配的過程)的運(yùn)行時(shí)間進(jìn)行對(duì)比，得到三種算法運(yùn)行時(shí)間，如圖7所示。

Figure 7　Running time of the algorithms 圖7　算法運(yùn)行時(shí)間

從圖7可以看出，當(dāng)同一抗原本體要求多次與測(cè)試數(shù)據(jù)集合進(jìn)行匹配時(shí)，基于人工免疫的本體匹配算法的耗時(shí)明顯地低于原本體匹配算法的耗時(shí)，而且人工免疫算法還對(duì)本體設(shè)置了生存期，對(duì)于超過生存期的本體進(jìn)行隱藏。所以，隨著匹配次數(shù)的增加，基于人工免疫本體匹配算法提高了本體匹配的效率。

(2)算法準(zhǔn)確度比較。對(duì)于本體匹配準(zhǔn)確度的評(píng)估，本文參照文獻(xiàn)[1]的標(biāo)準(zhǔn)，即用F-Measure和OverAll來比較原本體匹配算法和AOMA-AI算法的匹配準(zhǔn)確度的差異。評(píng)價(jià)指標(biāo)F-Measure和OverAll的比較結(jié)果分別如圖8和圖9所示。

Figure 8　Result of F-Measure 圖8　F-Measure結(jié)果

Figure 9　Result of OverAll 圖9　OverAll結(jié)果

從圖8和圖9結(jié)果中可以看出，相對(duì)ASMOV算法而言，AOMA-AI算法確實(shí)提高了本體匹配的準(zhǔn)確度。分析其中原因，可以看出當(dāng)在數(shù)據(jù)集中的本體加入情景屬性時(shí)，抗原本體與數(shù)據(jù)集中的本體要首先進(jìn)行情景匹配，而只有抗原本體和數(shù)據(jù)集本體的語境相似度值大于或等于閾值θ的時(shí)候，才能進(jìn)行后續(xù)的結(jié)構(gòu)和語義匹配過程，這樣既能排除不同領(lǐng)域內(nèi)的本體匹配結(jié)果的干擾，也能減少本體內(nèi)部的冗余計(jì)算量。

5結(jié)束語

本文利用人工免疫算法的收斂快、耗時(shí)低的特性，AOMA-AI算法將人工免疫算法融入到本體匹配算法中，有效地提高了本體匹配度和匹配效率，為后續(xù)中根據(jù)匹配本體為用戶推薦相應(yīng)的知識(shí)提供基礎(chǔ)。然而，當(dāng)用戶情景上下文不明確時(shí)，該算法將進(jìn)行本體模糊匹配，這時(shí)由于對(duì)用戶行為信息不明確，仍會(huì)存在計(jì)算量冗余的問題。后續(xù)將進(jìn)一步研究如何在用戶上下文不明確時(shí)，根據(jù)用戶歷史信息以及其他相同用戶的行為信息，盡最大可能為該用戶提供情景支持。

參考文獻(xiàn):

[1]Huang Tao，Cui Hong-yang，Liu Qing-tang，et al. Ontology matching approach based on virtual path[J].Computer Science,2009,37(11):207-209.(in Chinese)

[2]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-244.

[3]Gai Ke. A Research on context-based ontology-matching algorithm[D]. Harbin:Harbin Institute of Technology,2010.(in Chinese)

[4]Wang Xiao-yun， Xu Qi-yu. An improved ant colony optimization for ontology matching[C]//Proc of International Conference on Computer Research & Development,2011:235-238.

[5]Han Xu-ming,Wang Li-min. Improved artificial immune algorithms and their applications[M].Beijing: Publishing House of Electronics Industry,2013.(in Chinese)

[6]Yang Gu-gang. An improved artificial immune algorithm [C]//Proc of the 6th International Conference on Natural Compuation,2010:2837-2841.

[7]Dai Wei-min. Technology and method of sematic web information organization[M]. Shanghai:Xuelin Press,2009.(in Chinese)

[8]Sun Cheng-zhu, Xu Xiao-fei, Deng Sheng-chun. Ontology representation method for virtual enterprise model[J].Computer Integrated Manufacturing Systems,2009,151(2):277-286.(in Chinese)

[9]Xu Jian-feng,Wang Dong. Object-oriented and ontology context-aware modeling based on XML[C]//Proc of International Conference on Computer Science and Network Technology,2012:1795-1797.

[10]Guan Dong,Cai Zi-xing,Kong Zhi-zhong. Research on grid service matching based on ontology[J].Journal of Chinese Computer Systems,2009,30(8):1640-1641.(in Chinese)

[11]Stoilos G,Stamou G,Kollias S. A string metric for ontology alignment[C]//Proc of the 4th International Semantic Web Conference,2005:625-628.

[12]Freckleton R E. Freckleton scaling ontology alignment[D]. Colorado:University of Colorado,2013.

[13]Hu Wei,Qu Yu-zhong. A practical ontology matching system[J].Web Semantics Services & Agents on the World Wide Web,2008,6(3):237-238.

參考文獻(xiàn):附中文

[1]黃濤，崔弘揚(yáng)，劉清堂，等.一種基于虛擬路徑的本體匹配算法[J]. 計(jì)算機(jī)科學(xué)，2009,37(11):207-209.

[3]蓋克.基于概念上下文的本體匹配算法研究[D] .哈爾濱：哈爾濱工業(yè)大學(xué),2010.

[5]韓旭明,王麗敏. 人工免疫算法改進(jìn)及其應(yīng)用[M]. 北京：電子工業(yè)出版社,2013.

[7]戴維民. 語義網(wǎng)信息組織技術(shù)與方法[M]. 上海：學(xué)林出版社,2009.

[8]孫成柱，徐曉飛，鄧勝春.面向虛擬企業(yè)模型的本體表示方法[J].計(jì)算機(jī)集成制造系統(tǒng),2009，15(2):277-286.

[10]管東，蔡自興，孔志周.網(wǎng)格服務(wù)本體匹配算法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng),2009，30(8):1640-1641.

董濟(jì)德(1986-),男,山東日照人，碩士，研究方向?yàn)樾畔⑼扑秃腿藱C(jī)交互。E-mail:jidedong2008@126.com

DONG Ji-de,born in 1986,MS,his research interests include information pushing,and human-computer interaction.

謝強(qiáng)(1974-),男,四川瀘州人，博士，副教授，研究方向?yàn)樾畔踩腿藱C(jī)交互。E-mail:xieqiang@126.com

XIE Qiang,born in 1974,PhD,associate professor,his research interests include information security,and human-computer interaction.

丁秋林(1935-),男,江西撫州人，博士，教授，研究方向?yàn)槠髽I(yè)信息化和信息系統(tǒng)集成。E-mail:qlding@nuaa.edu.cn

DING Qiu-lin,born in 1935,PhD,professor,his research interests include enterprise informationization, and information system integration.