基于樹結構的本體概念相似度計算方法①

徐英卓, 賈 歡

?

基于樹結構的本體概念相似度計算方法①

徐英卓, 賈 歡

(西安石油大學計算機學院, 西安 790065)

隨著本體在數據集成方面的廣泛應用, 面向本體的概念相似度計算成為人們關注的熱點問題. 針對當前領域本體概念相似度的計算過程都比較復雜的問題, 提出一種基于樹結構的本體概念相似度的計算方法. 該方法通過添加和重組虛擬節點重構本體樹, 再通過屬性比較映射對象, 最后通過計算, 得到本體概念的語義相似度結果. 實驗結果表明, 該方法有效利用了本體概念的語義信息, 得到了合理的計算結果, 并簡化了計算過程.

本體; 概念相似度; 樹結構

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

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

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

1　基于樹結構的本體概念相似度算法

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

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

1.1 本體模型的構建

1.1.1將XML轉換為樹結構

假設有本體O, 其根節點為A, I(A, B)表示B繼承于A, I’(A, B)表示A和B是兄弟節點. 那么, 創建本體樹的關聯規則如下[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)

分類元素并建立本體樹: 當元素不在DTD文件的末端時, 如果一個元素X有子元素, 那么將X作為子元素的一個父元素記錄下來, 否則, 將X作為根節點; 如果元素X有一個父元素Y, 那么將X作為Y下面的節點, 否則, 將X作為Y的一個屬性值. 再到下一個元素, 如此循環.

1.1.2重構本體樹

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

1) 特征提取

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

2) 匹配識別

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

3) 結構比較

通過創建虛擬節點重構中間本體樹和源本體樹. 此過程以已經確定的精確匹配或部分匹配的節點開始. 例如下圖中所示, 圖1給出了鉆井作業中間本體樹, 圖2給出了鉆井作業源本體樹.

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

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

假設可以找到以下精確/部分匹配對:

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

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

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

④ 進尺(A)à鉆進(B)

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

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

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

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

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

定義1. 設X、Y是本體樹中的任意兩個節點, Level(X)表示節點X所處的層級, Level(Y)表示節點Y所處的層級, |Level(X)- Level(Y)|表示節點X和節點Y的層級差.

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

1.2 本體概念相似度計算

1.2.1基本定義

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

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

定義3. “邊權值”表示連接兩個節點的路徑上的值, 也可以理解為結點間的距離.

假設各條邊的邊權值相等, 則在語義距離相等的情況下, 距離根節點遠的概念間的相似度要比距離根節點近的概念間的相似度高. 因此, 邊權值的大小應該隨其在本體樹中所處的深度不同而變化. 我們設定深度越深, 邊權值越小, 每個節點的邊權值為該節點流出的邊權值和流入的邊權值之和, 根節點的邊權值為1.

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

根據“知網”[15], “概念”是對詞匯語義的一種描述. 每一個詞可以表達為幾個概念. “概念”是用一種“知識表示語言”來描述的, 這種“知識表示語言”所用的“詞匯”叫做“義原”. “義原”是用于描述一個“概念”的最小意義單位.

1.2.2算法描述

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

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

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

由此, 根據以上映射規則, 在領域本體中, 對于兩個概念S和S, 提出相似度計算公式為:

1.2.3整體計算步驟

根據上面1.1節形成的映射關系, 對本體概念相似度計算可分為兩個步驟進行: 1)比較本體概念所處的層級, 重構本體樹; 2)概念相似度值的具體計算.

具體計算流程如圖3所示.

圖3 計算流程圖

整體計算步驟如下:

步驟1: 構建本體樹, 找到所有的概念匹配對.

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

步驟3: 為具有較低絕對位置的節點添加虛擬節點, 然后進行概念相似度計算.

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

2　實例驗證

本實驗構建了鉆井作業本體樹如圖4, 以圖1和圖2所示鉆井本體片段為例, 選擇具有代表性的概念進行相似度計算, 圖中的概念用Si表示. 根據以上方法, 本文實現了一個基于樹結構的語義相似度計算模型.

圖4 鉆井作業本體樹

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

圖5 結果本體樹(部分)

計算“鉆進&進尺”匹配對的相似度值, 根據計算公式,=0.1,1, 當=0.02,Sim(鉆進, 進尺)= 0.882.

對于本體概念相似度計算的結果評價, 本文采用了人工判別的方法. 為了驗證方法的有效性, 使用兩種方法實現概念的相似度計算, 并對它們的計算結果進行比較. 方法1采用基于《知網》的語義相似度計算方法[16], 方法2采用本文提出的語義相似度計算方法.

表1 鉆井作業本體實驗結果

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

3　結語

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

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

2 程勇,黃河,邱莉,等.一個基于相似度計算的動態多維概念映射算法.小型微型計算機系統,2006,27(6):975–979.

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

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

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

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

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

8 魯德浩,郟東耀.一種改進的概念相似度計算方法.鄭州大學學報(理學版),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 嚴麗,馬宗民,劉健,于戈.模糊XML DTD到UML數據模型的轉換.小型微型計算機系統,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 游彬,嚴岳松,孫英閣,等.基于HowNet 的信息量計算語義相似度算法.計算機系統應用,2013,22(1):129–133.

13 許云,樊孝忠,張鋒.基于HowNet 的語義相關度計算.北京理工大學學報,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》的詞語語義相似度計算.計算語言學及中文信息處理,2007,(7):59–76.

16 董振東,董強.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

國家自然科學基金(51574194);陜西省科技工業攻關項目(2014K05-02,2016GY-144);陜西省教育廳專項科研計劃項目(15JK1567)

2016-06-29;

2016-08-08

[10.15888/j.cnki.csa.005667]