一種基于NSGA—II算法的本體匹配技術(shù)

江荔

摘 要：本體可以用于克服語義異質(zhì)問題，但是直接使用不同的本體會將語義異質(zhì)問題提升到更高的級別。本體匹配過程是通過確定兩個本體中的實體之間的關(guān)系，從而解決兩個本體間的異質(zhì)問題。目前提出的各種本體匹配方法中，基于進化算法的本體匹配技術(shù)應(yīng)用比較廣泛，但是基于進化算法的本體匹配技術(shù)的效率和最后獲取的本體匹配結(jié)果的質(zhì)量都差強人意。為了解決這一問題，本文在提出了一種新的基于NSGA-II的本體匹配技術(shù)。在本文的工作中，提出了一種新的基于信息論的相似度度量技術(shù)，為本體匹配問題構(gòu)建了一個多目標的優(yōu)化模型，針對性地設(shè)計了一種NSGA-II算法以求解該問題。實驗結(jié)果表明我們的方案是有效的。

關(guān)鍵詞：本體匹配技術(shù) NSGA-II 進化算法 相似度度量技術(shù)

中圖分類號：TP311 文獻標識碼：A 文章編號：1674-098X（2017）12（b）-0129-02

本體被認為是一種實現(xiàn)異質(zhì)語義數(shù)據(jù)源交互的方案。然而由于人的主觀性，同一個實體（如類、屬性或個體）在不同的本體中可能用不同的名稱或方式來定義。因此，直接使用不同的本體會將語義異質(zhì)問題提升到更高的級別。本體匹配過程是通過確定兩個本體中的實體之間的關(guān)系，從而解決兩個本體間的異質(zhì)問題。當本體規(guī)模龐大的時候，手動匹配本體是不可能的，因此人們近年來提出了各種本體匹配技術(shù)。通過各種能夠提供本體元素之間相似度數(shù)值的相似度度量技術(shù)，本體匹配技術(shù)能夠識別本體中的元素是否相同?？傮w上來說，相似度度量技術(shù)可以分3種：一種是基于字面的，一種是基于語言學(xué)的，還有一種是基于分類結(jié)構(gòu)的?；谧置娴南嗨贫榷攘考夹g(shù)計算本體實體名稱的字符串編輯距離?；谡Z言學(xué)的相似度度量技術(shù)通過電子詞典來（如WordNet）來確定本體實體名稱之間的同義關(guān)系?；诜诸惤Y(jié)構(gòu)的相似度度量技術(shù)通過測試本體周邊實體的相似度來估算該實體的相似度值。然而，上述任何一種相似度度量技術(shù)的性能都無法做到在所有的應(yīng)用場合中都能比其他技術(shù)好，嚴重影響了本體匹配結(jié)果的質(zhì)量。因此，如何設(shè)計一種高語義識別能力的相似度度量技術(shù)是本體匹配技術(shù)的關(guān)鍵。

1 相似度度量技術(shù)

除此之外，當兩個待匹配本體中擁有的實體規(guī)模十分龐大的時候，從某種程度上來說，進化算法通常會被用于計算本體匹配結(jié)果。最著名的基于遺傳算法的本體匹配技術(shù)是GOAL，它的本體匹配結(jié)果是通過遺傳算法來確定最優(yōu)的相似度度量技術(shù)的集成權(quán)重，參考的方案詳見參考文獻。但是這些方法只用了一種本體匹配結(jié)果的質(zhì)量度量指標來評價本體匹配方案，可能導(dǎo)致本體匹配結(jié)果在進化過程中有偏好地改進，降低了最終的本體匹配的水平，同時對已有的基于進化算法的本體匹配技術(shù)時間消耗很大。因此，如何設(shè)計一種高效的基于進化算法的本體匹配技術(shù)是本體匹配領(lǐng)域的另一個挑戰(zhàn)。

相似度度量技術(shù)是本體匹配技術(shù)的基礎(chǔ)。本文引入了香農(nóng)的信息理論，提出一種新的語義相似度度量技術(shù)。該技術(shù)能夠組合基于字面的、語言學(xué)的和分類結(jié)構(gòu)的相似度度量技術(shù)的特點以計算實體的相似度值。具體來說，本文的方法是通過實體提供的信息量來計算它們之間的相似度值。為了準確估計實體的信息量，本文提出通過本體的分類結(jié)構(gòu)來獲取實體內(nèi)部的和其所有子類的信息以構(gòu)建實體的信息檔案，然后對于本體中的兩個實體，通過以下的非對稱度量的方式來計算二者的相似度值。當獲取某個本體匹配結(jié)果之后，相應(yīng)的相似度矩陣可以按照如下方法生成：矩陣的行列分別代表兩個本體中的實體，矩陣中的元素代表相應(yīng)實體的相似度值，過濾掉相似度矩陣中可信度不高的匹配結(jié)果。

2 基于實例的NSGA-II算法

2.1 基于實例的本體匹配多目標優(yōu)化模型

這里我們預(yù)先定義好兩個匹配本體OA和OZ，本體匹配問題的多目標優(yōu)化模型如下：假設(shè)n是本體OA中的實例個數(shù)，m是本體OZ中的實例個數(shù)。群體中的每個個體是一個長度為n+1的一維數(shù)組，將當前代總?cè)汉透复N群放在一起，取出冗余的個體之后，依據(jù)NSGA-II的非支配排序和擁擠度計算方案來選出下一代種群。

2.2 NSGA-II算法

NSGA-II算法有3個算子，即選擇算子、交叉算子和變異算子。本文采用賭輪盤選擇算子，該算子為每一個個體賦予一個正比于它們的適應(yīng)度值的選擇概率，這就使得適應(yīng)度值最高的個體擁有最高概率產(chǎn)生下一代個體，而適應(yīng)度值不是那么高的個體也有機會產(chǎn)生下一代個體。選擇算子依據(jù)變異概率判斷某個基因位上的元素是否需要產(chǎn)生變異。若變異發(fā)生在某個基因位上的話，將該基因位上的值由1變?yōu)?，或者由0變?yōu)?。

2.3 有效的提升策略

由于在適應(yīng)度計算過程中需要讀取不同的本體匹配結(jié)果，集成并評價，用時很大。且每次將要集成的本體匹配結(jié)果讀入內(nèi)存，內(nèi)存消耗也很大。因此本文在運行算法之前，將所有的相似度度量技術(shù)對應(yīng)的相似度矩陣一次讀入內(nèi)存以提高算法運行的效率。精英策略是指每一代擁有最高適應(yīng)度值的個體都可以嘗試成為精英個體，精英個體另外保存并在算法終止后返回給用戶。

2.4 實驗的結(jié)果與分析

實驗采用本體匹配領(lǐng)域公認的2012年本體匹配評價競賽（ontology alignment evaluation initiative，OAEI）的測試數(shù)據(jù)集，其中的數(shù)據(jù)是Benchmark中所有測試數(shù)據(jù)的結(jié)果的均值。同時為了區(qū)分已有的本體匹配系統(tǒng)，本文采用傳統(tǒng)的recall、precision和f-measure重新度量，從而獲取本體匹配結(jié)果。通過對給出的基于實例的NSGA-II方法的運行結(jié)果是30次獨立運行后得出的平均結(jié)果，與通過隨機方法和概念聚類算法構(gòu)建的局部標準匹配比較的結(jié)果運行時間進行比較，實驗結(jié)果表明，在測試數(shù)據(jù)集Benchmark中，基于實例的NSGA-II方法的解的f-measure排在第1位，precision排在第2位。在測試數(shù)據(jù)集Anatomy中，基于實例的NSGA-II方法的解的f-measure排在第2位，而precision排在第1位。在測試數(shù)據(jù)集Library中，基于實例的NSGA-II方法的解優(yōu)于所有其他的本體匹配系統(tǒng)。3種測試數(shù)據(jù)集的結(jié)果表明，基于實例的NSGA-II算法是可行并且有效的，通過在本體匹配過程中使用本體中的實例信息可以大大提高本體匹配結(jié)果的準確性，具體體現(xiàn)在實驗結(jié)果中較高的precision值。

3 結(jié)語

本文建立了一個全新的多目標優(yōu)化模型，該模型匹配以查全率和查準率為目標的本體，并提出了新的相似度擴散算法和實例相似度度量技術(shù)，根據(jù)這種算法重新設(shè)計了個體編碼方案，從而提出了一種新的基于實例的NSGA-II本體匹配方法。實驗數(shù)據(jù)采用OAEI 2012的Benchmark、Anatomy和Library測試數(shù)據(jù)集，通過對2組本體30次獨立運行后得出的平均結(jié)果表明，基于實例的NSGA-II本體匹配方法獲取的本體匹配結(jié)果的質(zhì)量在目前流行的本體匹配技術(shù)中排名前列，并且查準率和查全率有了明顯的提高。

參考文獻

[1] 陳亮.一種改進的本體匹配方法研究[D].吉林大學(xué)，2015.

[2] 鄒黎君.基于多策略的本體匹配研究[D].蘇州大學(xué)，2013.

[3] 任建歡.基于多策略的本體匹配系統(tǒng)設(shè)計與實現(xiàn)[D].東南大學(xué)，2015.

[4] 崔金棟，徐寶祥.IOPE視角下網(wǎng)格服務(wù)本體匹配算法研究[J].現(xiàn)代圖書情報技術(shù)，2014（15）：10-17.

[5] 薛醒思.基于NSGA-Ⅱ的大規(guī)模本體映射方法[J].計算機應(yīng)用，2014（6）：1622-1625.

[6] 薛醒思，王金水.采用雙向個體標注的本體匹配技術(shù)[J].福州大學(xué)學(xué)報：自然科學(xué)版，2016（1）：64-70.