徐英卓, 賈 歡

?

基于樹結(jié)構(gòu)的本體概念相似度計(jì)算方法①

徐英卓, 賈 歡

(西安石油大學(xué)計(jì)算機(jī)學(xué)院, 西安 790065)

隨著本體在數(shù)據(jù)集成方面的廣泛應(yīng)用, 面向本體的概念相似度計(jì)算成為人們關(guān)注的熱點(diǎn)問題. 針對(duì)當(dāng)前領(lǐng)域本體概念相似度的計(jì)算過程都比較復(fù)雜的問題, 提出一種基于樹結(jié)構(gòu)的本體概念相似度的計(jì)算方法. 該方法通過添加和重組虛擬節(jié)點(diǎn)重構(gòu)本體樹, 再通過屬性比較映射對(duì)象, 最后通過計(jì)算, 得到本體概念的語義相似度結(jié)果. 實(shí)驗(yàn)結(jié)果表明, 該方法有效利用了本體概念的語義信息, 得到了合理的計(jì)算結(jié)果, 并簡化了計(jì)算過程.

本體; 概念相似度; 樹結(jié)構(gòu)

數(shù)據(jù)集成的一個(gè)難點(diǎn)是分布式語義信息集成, 在語義集成方面, 可以將數(shù)據(jù)集成看作是一個(gè)知識(shí)表示問題. 然而, 相同的知識(shí)經(jīng)常使用不同的本體來表達(dá), 不同的應(yīng)用之間對(duì)相同知識(shí)的表達(dá)也不相同[1], 結(jié)果就會(huì)產(chǎn)生誤解和沖突. 因此, 建立本體映射來加強(qiáng)可理解性, 從而有效地解決這種沖突是非常必要的[2]. 語義集成的關(guān)鍵是本體映射, 而本體映射的關(guān)鍵是概念相似度計(jì)算. 當(dāng)前概念相似度計(jì)算方法大致可分為兩類: 一類利用大規(guī)模語料庫進(jìn)行統(tǒng)計(jì), 依據(jù)詞匯上下文信息的概率分布進(jìn)行計(jì)算, 這種方法比較精準(zhǔn), 但是需要依賴于訓(xùn)練所用的語料庫, 計(jì)算量大且易受訓(xùn)練數(shù)據(jù)噪聲影響; 另一類基于某種世界知識(shí)來計(jì)算, 主要是基于某個(gè)知識(shí)完備的語義詞典中的層次結(jié)構(gòu)關(guān)系進(jìn)行計(jì)算, 這種方法比較直觀, 易受人們的主觀意識(shí)影響[3,4]. 中科院劉群的基于《知網(wǎng)》的詞語相似度計(jì)算是當(dāng)前比較有代表性的計(jì)算概念相似度的方法之一.

很多學(xué)者考慮到其他因素對(duì)概念相似度的影響, 如黃果等人[3]提出的以基于距離的計(jì)算模型為基礎(chǔ), 把概念的信息內(nèi)容和概念的屬性作為兩個(gè)決策因子來計(jì)算相似度的方法, 能較準(zhǔn)確地反映概念之間的語義關(guān)系, 但是計(jì)算過程復(fù)雜; 劉紫玉等人[5]在本體模型的基礎(chǔ)上提出領(lǐng)域本體模型的八元組表示方法和領(lǐng)域

表示方法, 給出領(lǐng)域本體模型的有向循環(huán)圖, 通過綜合計(jì)算, 得到領(lǐng)域本體中概念的實(shí)際相似度, 能夠比較準(zhǔn)確地反映概念之間的語義關(guān)系, 但是計(jì)算量比較大; 姜華[6]提出的改進(jìn)的本體語義相似度計(jì)算方法, 該方法考慮了本體結(jié)構(gòu)中概念的共同分離祖先和幾種語義距離影響因子, 將信息量融合到語義距離的計(jì)算中, 得到了較合理的實(shí)驗(yàn)結(jié)果, 但是計(jì)算范圍較小. 本文提出一種基于樹結(jié)構(gòu)的概念語義相似度計(jì)算方法, 該方法根據(jù)本體概念的特點(diǎn)及概念間的關(guān)系, 利用樹結(jié)構(gòu)的層次特點(diǎn)計(jì)算基于實(shí)例的概念相似度, 能發(fā)掘更多的潛在信息, 提高計(jì)算的準(zhǔn)確性, 簡化計(jì)算過程, 并通過實(shí)驗(yàn)對(duì)所提方法進(jìn)行了實(shí)驗(yàn)驗(yàn)證.

1　基于樹結(jié)構(gòu)的本體概念相似度算法

概念相似度是指兩個(gè)概念之間的相似程度, 通常指兩個(gè)概念間具有某些共同特性[7]. 本文用樹形結(jié)構(gòu)模擬本體, 并用樹結(jié)構(gòu)表示所有的節(jié)點(diǎn)關(guān)系, 每個(gè)節(jié)點(diǎn)代表一個(gè)概念[8]. 本節(jié)將詳細(xì)闡述一種重組方法, 利用中間本體樹和源本體樹通過增加和組合虛擬節(jié)點(diǎn)來規(guī)范所有的樹結(jié)構(gòu), 并利用本體映射關(guān)系進(jìn)行概念相似度的計(jì)算.

假設(shè)所有的本體信息使用XML和XML DTD表示, 本文提出的本體概念相似度算法包括本體模型的構(gòu)建和本體概念相似度計(jì)算兩部分.

1.1 本體模型的構(gòu)建

1.1.1將XML轉(zhuǎn)換為樹結(jié)構(gòu)

假設(shè)有本體O, 其根節(jié)點(diǎn)為A, I(A, B)表示B繼承于A, I’(A, B)表示A和B是兄弟節(jié)點(diǎn). 那么, 創(chuàng)建本體樹的關(guān)聯(lián)規(guī)則如下[9]:

I(C, B)^ I(B, A)àI(C, A)

I(A, B)^ I(B, C)à I(A, C)

I(A, B)^ I(C, A)à I(C, B)

I(A, B)^ I(A, C)à I(B, C), I’(B, C)

分類元素并建立本體樹: 當(dāng)元素不在DTD文件的末端時(shí), 如果一個(gè)元素X有子元素, 那么將X作為子元素的一個(gè)父元素記錄下來, 否則, 將X作為根節(jié)點(diǎn); 如果元素X有一個(gè)父元素Y, 那么將X作為Y下面的節(jié)點(diǎn), 否則, 將X作為Y的一個(gè)屬性值. 再到下一個(gè)元素, 如此循環(huán).

1.1.2重構(gòu)本體樹

本體樹由不同的DTD表達(dá)模式轉(zhuǎn)換而來, 其多樣性使得它很難進(jìn)行本體映射[10], 因此可以借助于中間本體樹完成映射過程. 重構(gòu)本體樹的過程包括三個(gè)步驟: 特征提取、匹配識(shí)別和結(jié)構(gòu)比較.

1) 特征提取

從待映射的本體中獲取特征值, 包括本體中的概念集合、屬性集合等, 通過比較屬性集合進(jìn)行本體匹配映射. 若兩個(gè)屬性集包含的屬性數(shù)目相同, 屬性名稱相似, 且數(shù)據(jù)類型相同, 則它們是等價(jià)屬性集; 若兩個(gè)屬性集的數(shù)量相同且屬性內(nèi)容相似, 則它們是等效屬性集; 若兩個(gè)對(duì)象是兄弟節(jié)點(diǎn), 且有一個(gè)等效屬性集, 則可從中提取這些等價(jià)屬性組合成的新屬性設(shè)置為其共同的父對(duì)象.

2) 匹配識(shí)別

根據(jù)提取的屬性特征, 對(duì)待映射的本體進(jìn)行匹配. 若兩個(gè)對(duì)象都是葉子節(jié)點(diǎn), 且擁有相同的屬性集, 則它們是精確匹配的; 若只有部分屬性匹配, 則它們是部分匹配的. 對(duì)于非葉子節(jié)點(diǎn), 可以用它們的子節(jié)點(diǎn)進(jìn)行匹配. 若所有的屬性和子節(jié)點(diǎn)都是精確匹配, 則這兩個(gè)非葉子節(jié)點(diǎn)也是精確匹配. 若它們的屬性是部分匹配, 并且部分匹配的子節(jié)點(diǎn)數(shù)目相同, 則它們也是部分匹配的.

3) 結(jié)構(gòu)比較

通過創(chuàng)建虛擬節(jié)點(diǎn)重構(gòu)中間本體樹和源本體樹. 此過程以已經(jīng)確定的精確匹配或部分匹配的節(jié)點(diǎn)開始. 例如下圖中所示, 圖1給出了鉆井作業(yè)中間本體樹, 圖2給出了鉆井作業(yè)源本體樹.

圖1 鉆井作業(yè)中間本體樹(部分)

圖1 鉆井作業(yè)源本體樹(部分)

假設(shè)可以找到以下精確/部分匹配對(duì):

① 井號(hào)(A)à井號(hào)(B)

② 開鉆時(shí)間(A)à開鉆日期(B)

③ 完鉆時(shí)間(A)à完鉆日期(B)

④ 進(jìn)尺(A)à鉆進(jìn)(B)

對(duì)每一個(gè)匹配對(duì)進(jìn)行絕對(duì)位置計(jì)算, 絕對(duì)位置是節(jié)點(diǎn)與根節(jié)點(diǎn)之間的距離[11]. 如果將根節(jié)點(diǎn)定義為0級(jí)(level 0), 那么節(jié)點(diǎn)的絕對(duì)位置就等于節(jié)點(diǎn)的級(jí)別.

① 井號(hào)(A) level 2à井號(hào)(B) level 2

② 開鉆時(shí)間(A) level 2à開鉆日期(B) level 3

③ 完鉆時(shí)間(A) level 2à完鉆日期(B) level 3

④ 進(jìn)尺(A) level 2à鉆進(jìn)(B) level 3

定義1. 設(shè)X、Y是本體樹中的任意兩個(gè)節(jié)點(diǎn), Level(X)表示節(jié)點(diǎn)X所處的層級(jí), Level(Y)表示節(jié)點(diǎn)Y所處的層級(jí), |Level(X)- Level(Y)|表示節(jié)點(diǎn)X和節(jié)點(diǎn)Y的層級(jí)差.

后面三個(gè)匹配對(duì)在不同的層級(jí), 結(jié)果表明中間本體樹與源本體樹之間的結(jié)構(gòu)是不同的, 應(yīng)該向具有較低絕對(duì)位置的樹添加虛擬節(jié)點(diǎn). |Level(X)- Level(Y)|的值表示需要添加的虛擬節(jié)點(diǎn)數(shù). 如果具有較低絕對(duì)位置的節(jié)點(diǎn)N處在1級(jí), 那么應(yīng)該為這個(gè)絕對(duì)位置N添加虛擬父節(jié)點(diǎn), 否則, 進(jìn)一步執(zhí)行比較程序?yàn)樘摂M節(jié)點(diǎn)找到合適的位置. 虛擬節(jié)點(diǎn)插入程序應(yīng)該被執(zhí)行|Level(X)- Level(Y)|次, 計(jì)算節(jié)點(diǎn)X和節(jié)點(diǎn)Y的部分匹配子節(jié)點(diǎn)數(shù)目. 如果節(jié)點(diǎn)X是部分匹配節(jié)點(diǎn), 而它的子節(jié)點(diǎn)數(shù)目和其他任何部分匹配節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目都不相同時(shí), 那么添加的虛擬節(jié)點(diǎn)和X的子節(jié)點(diǎn)在同一層級(jí), 新增加的節(jié)點(diǎn)以節(jié)點(diǎn)X和其兄弟節(jié)點(diǎn)的名字命名, 其名稱表明了它們的功能.

1.2 本體概念相似度計(jì)算

1.2.1基本定義

定義2. “本體概念相似度”是描述兩個(gè)詞語在文章上下文結(jié)構(gòu)中可以相互替換使用而不改變文本的句法、語義結(jié)構(gòu)的程度. 其應(yīng)用也十分廣泛, 從心理學(xué)、語言學(xué)、認(rèn)知科學(xué)到人工智能都有涉及[12].

概念相似度是一個(gè)數(shù)值, 取值范圍為[0, 1], 一個(gè)詞語和它本身的相似度是1(相同) , 如果兩個(gè)詞語在任何上下文中都不可替換, 則它們的相似度為零[13].

定義3. “邊權(quán)值”表示連接兩個(gè)節(jié)點(diǎn)的路徑上的值, 也可以理解為結(jié)點(diǎn)間的距離.

假設(shè)各條邊的邊權(quán)值相等, 則在語義距離相等的情況下, 距離根節(jié)點(diǎn)遠(yuǎn)的概念間的相似度要比距離根節(jié)點(diǎn)近的概念間的相似度高. 因此, 邊權(quán)值的大小應(yīng)該隨其在本體樹中所處的深度不同而變化. 我們?cè)O(shè)定深度越深, 邊權(quán)值越小, 每個(gè)節(jié)點(diǎn)的邊權(quán)值為該節(jié)點(diǎn)流出的邊權(quán)值和流入的邊權(quán)值之和, 根節(jié)點(diǎn)的邊權(quán)值為1.

定義 4. 如果領(lǐng)域本體中概念S和S成同義關(guān)系, 即可以相互替換而不影響文字所表達(dá)的意思, 那么概念S和 S的相似度為1, 可以用公式表示為.

根據(jù)“知網(wǎng)”[15], “概念”是對(duì)詞匯語義的一種描述. 每一個(gè)詞可以表達(dá)為幾個(gè)概念. “概念”是用一種“知識(shí)表示語言”來描述的, 這種“知識(shí)表示語言”所用的“詞匯”叫做“義原”. “義原”是用于描述一個(gè)“概念”的最小意義單位.

1.2.2算法描述

目前, 計(jì)算概念相似度的方法多數(shù)是基于文獻(xiàn)[14]提出的方法, 在計(jì)算兩個(gè)概念的相似度時(shí), 通過計(jì)算其所在層次樹上的最短路徑距離Sim來確定其相似度, 如公式(1)所示:

從公式(1)可以看出,的值越小, 兩個(gè)概念之間距離越近,值越大, 其相似度也越大. 由此可知, 一個(gè)概念的兄弟節(jié)點(diǎn)就是與其相似度最高的概念節(jié)點(diǎn).

該方法只考慮了路徑距離, 沒有考慮其他因素, 得出的結(jié)果在一定程度上與人的正常邏輯思維不符合[14], 例如, “汽車”和“自行車”兩個(gè)詞語, 在語義方面都是表示一種交通工具, 從主觀上來看相似度很高, 但是利用文獻(xiàn)[14]的方法計(jì)算的到的相似度并不是很高. 因此本文提出一種新的方法, 考慮不同概念在本體樹中所占的比重不同, 給其加上合理的邊權(quán)值, 在一定程度上削弱距離對(duì)相似度值的影響, 使得計(jì)算結(jié)果更符合人們的主觀認(rèn)識(shí).

由此, 根據(jù)以上映射規(guī)則, 在領(lǐng)域本體中, 對(duì)于兩個(gè)概念S和S, 提出相似度計(jì)算公式為:

1.2.3整體計(jì)算步驟

根據(jù)上面1.1節(jié)形成的映射關(guān)系, 對(duì)本體概念相似度計(jì)算可分為兩個(gè)步驟進(jìn)行: 1)比較本體概念所處的層級(jí), 重構(gòu)本體樹; 2)概念相似度值的具體計(jì)算.

具體計(jì)算流程如圖3所示.

圖3 計(jì)算流程圖

整體計(jì)算步驟如下:

步驟1: 構(gòu)建本體樹, 找到所有的概念匹配對(duì).

步驟2: 比較兩個(gè)概念所處的層級(jí)是否相同, 如果二者在處于同一層級(jí), 那么可以直接進(jìn)行概念相似度計(jì)算, 否則執(zhí)行下一步操作.

步驟3: 為具有較低絕對(duì)位置的節(jié)點(diǎn)添加虛擬節(jié)點(diǎn), 然后進(jìn)行概念相似度計(jì)算.

步驟4: 利用公式(2)進(jìn)行相似度的計(jì)算, 通過相似度的值判斷兩個(gè)概念的相似程度.

2　實(shí)例驗(yàn)證

本實(shí)驗(yàn)構(gòu)建了鉆井作業(yè)本體樹如圖4, 以圖1和圖2所示鉆井本體片段為例, 選擇具有代表性的概念進(jìn)行相似度計(jì)算, 圖中的概念用Si表示. 根據(jù)以上方法, 本文實(shí)現(xiàn)了一個(gè)基于樹結(jié)構(gòu)的語義相似度計(jì)算模型.

圖4 鉆井作業(yè)本體樹

例如: 計(jì)算“進(jìn)尺”和“鉆進(jìn)”這兩個(gè)概念的相似度值時(shí), 由于節(jié)點(diǎn)“鉆進(jìn)”處于較低絕對(duì)位置, 所以需要為其在本體樹中添加虛擬節(jié)點(diǎn), 虛擬節(jié)點(diǎn)線框及連接線用虛擬線條表示, 得到新的結(jié)果本體樹O, 如圖5所示, 圖中帶箭頭的虛線表示匹配關(guān)系.

圖5 結(jié)果本體樹(部分)

計(jì)算“鉆進(jìn)&進(jìn)尺”匹配對(duì)的相似度值, 根據(jù)計(jì)算公式,=0.1,1, 當(dāng)=0.02,Sim(鉆進(jìn), 進(jìn)尺)= 0.882.

對(duì)于本體概念相似度計(jì)算的結(jié)果評(píng)價(jià), 本文采用了人工判別的方法. 為了驗(yàn)證方法的有效性, 使用兩種方法實(shí)現(xiàn)概念的相似度計(jì)算, 并對(duì)它們的計(jì)算結(jié)果進(jìn)行比較. 方法1采用基于《知網(wǎng)》的語義相似度計(jì)算方法[16], 方法2采用本文提出的語義相似度計(jì)算方法.

表1 鉆井作業(yè)本體實(shí)驗(yàn)結(jié)果

表1為方法1和方法2計(jì)算得到的概念相似度, 其中, M1、M2分別為方法1和方法2計(jì)算所得的相似度值. 結(jié)果表明, 基于樹結(jié)構(gòu)的本體概念相似度計(jì)算模型能夠方便地用來計(jì)算領(lǐng)域本體概念間的相似度, 并能較好地反應(yīng)本體映射關(guān)系, 在滿足映射質(zhì)量的前提下, 極大地簡化了計(jì)算過程. 如對(duì)于“進(jìn)尺&鉆進(jìn)”匹配對(duì), 在鉆井領(lǐng)域, 二者所表達(dá)的內(nèi)容是相同的, 因此, 主觀判斷其相似度應(yīng)該更高, 本文所用方法的計(jì)算結(jié)果更符合人們的直觀判斷.

3　結(jié)語

本文以本體樹結(jié)構(gòu)為基礎(chǔ), 提出了一種合理的概念相似度計(jì)算方法, 該方法依賴于重構(gòu)本體樹進(jìn)行本體映射過程, 確定了將XML DTD模式的節(jié)點(diǎn)基于節(jié)點(diǎn)間關(guān)系轉(zhuǎn)換為樹結(jié)構(gòu)的方法, 并著重于尋找對(duì)象之間的等價(jià)性, 通過比較屬性, 建立對(duì)象之間的匹配, 這比在信息共享中尋找屬性之間的匹配更為有效, 并簡化了計(jì)算過程, 有效確保了計(jì)算的全面性、準(zhǔn)確性. 不足之處在于憑經(jīng)驗(yàn)設(shè)定的各個(gè)權(quán)值對(duì)結(jié)果造成了一定的誤差. 在以后的工作中, 需要進(jìn)一步完善概念語義相似度的計(jì)算方法, 比如本體樹中如何更好的確定邊權(quán)值等.

1 甘健侯,姜躍,夏幼明.本體方法及其應(yīng)用.北京:科學(xué)出版社,2011.

2 程勇,黃河,邱莉,等.一個(gè)基于相似度計(jì)算的動(dòng)態(tài)多維概念映射算法.小型微型計(jì)算機(jī)系統(tǒng),2006,27(6):975–979.

3 黃果,周竹榮,周亭.基于領(lǐng)域本體的語義相似度計(jì)算研究. 計(jì)算機(jī)工程與科學(xué),2007,29(5):112–117.

4 范弘屹,張仰森.一種基于HowNet的詞語語義相似度計(jì)算方法.北京信息科技大學(xué)學(xué)報(bào),2014,29(4):42–45.

5 劉紫玉,黃磊.基于領(lǐng)域本體模型的概念語義相似度計(jì)算研究.鐵道學(xué)報(bào),2011,33(1):52–57.

6 姜華.改進(jìn)的本體語義相似度計(jì)算方法.計(jì)算機(jī)工程與應(yīng)用, 2008,44(36):143–145.

7 劉宏哲,須德.基于本體的語義相似度和相關(guān)度計(jì)算研究綜述.計(jì)算機(jī)科學(xué),2012,39(2):8–13.

8 魯?shù)潞?郟東耀.一種改進(jìn)的概念相似度計(jì)算方法.鄭州大學(xué)學(xué)報(bào)(理學(xué)版),2010,42(1):9–12.

9 Ehrig M, Sure Y. Ontology mapping-an integrated approach. Lecture Notes in Computer Science, 2004, 3053: 76–91.

10 嚴(yán)麗,馬宗民,劉健,于戈.模糊XML DTD到UML數(shù)據(jù)模型的轉(zhuǎn)換.小型微型計(jì)算機(jī)系統(tǒng),2009,30(4):586–592.

11 Chiabrando E, Likavec S, Lombardi I, et al. Semantic similarity in heterogeneous ontologies. Ht’11, Proc. of the, ACM Conference on Hypertext and Hypermedia, Eindhoven. the Netherlands. June, 2011. 153–160.

12 游彬,嚴(yán)岳松,孫英閣,等.基于HowNet 的信息量計(jì)算語義相似度算法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2013,22(1):129–133.

13 許云,樊孝忠,張鋒.基于HowNet 的語義相關(guān)度計(jì)算.北京理工大學(xué)學(xué)報(bào),2005,20(5):411–414.

14 Wen, Yu, Gao, et al. Research on concept semantic similarity computation based on ontology. IEEE, International Conference on Computing, Control and Industrial Engineering. IEEE. 2011. 284–287.

15 劉群,李素建.基于《HowNet》的詞語語義相似度計(jì)算.計(jì)算語言學(xué)及中文信息處理,2007,(7):59–76.

16 董振東,董強(qiáng).HowNet knowledge database.http://www. Keenage.com/. [2014-05-05].

Ontology Concept Similarity Calculation Based on Tree Structure

XU Ying-Zhuo, JIA Huan

(Institute of Computer, Xi’an Shiyou University, Xi’an 710065, China)

With the wide application of ontology in data integration, the concept of ontology-oriented similarity calculation became a hot issue of concern. In view of the problems that current domain ontology concept similarity calculation processes are complex, this paper proposes a concept of ontology similarity calculation method based on tree structure. The thought of this method is that through adding virtual nodes and restructuring, refactoring ontology tree, and then comparing and mapping object properties, at last, the computation of the concept of ontology semantic similarity results are obtained. The experimental results show that the method is effective to use the concept of ontology semantic information, reasonable calculation results are obtained, it can also simplify the calculation process.

ontology; concept similarity; tree structure

國家自然科學(xué)基金(51574194);陜西省科技工業(yè)攻關(guān)項(xiàng)目(2014K05-02,2016GY-144);陜西省教育廳專項(xiàng)科研計(jì)劃項(xiàng)目(15JK1567)

2016-06-29;

2016-08-08

[10.15888/j.cnki.csa.005667]