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

江荔

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

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

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2017）12（b）-0129-02

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

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

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

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

2 基于實(shí)例的NSGA-II算法

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

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

2.2 NSGA-II算法

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

2.3 有效的提升策略

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

2.4 實(shí)驗(yàn)的結(jié)果與分析

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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