大規模本體分塊與映射中一種新的塊映射策略

摘 要：現有的大規模本體分塊與映射系統中大多采用基于參考點的塊映射策略，映射策略比較單一，塊映射質量不高。因此，提出一種新的基于本體塊結構的塊映射策略，通過重建本體塊結構圖來獲取塊與塊之間在結構上的相似度，并將其和基于參考點的策略相結合，通過加權求和得到總的相似度。理論分析和實驗結果表明，本文的方法塊映射準確率高。

關鍵詞：大規模本體；塊映射；參考點；本體塊結構圖

中圖分類號： TP391 文獻標識碼：A

1 引 言

在大規模本體分塊與映射問題中，除了要保證分塊質量之外，塊映射質量也是一個不容忽視的重要問題。因為，如果分塊質量很好，但是塊映射質量不好，即產生錯誤的塊映射，這會導致存在映射的兩個實體對得不到匹配，造成最終大規模本體映射的整體質量不高，或者說對查全率和查準率都有影響，因此，在對大規模本體進行分塊之后，如何找到一種最佳的塊映射策略，也是需要研究的一個重要問題。

2 相關工作

目前，國內外學者在大規模本體分塊與映射方面研究不是很多，而且大多數專注于對大規模本體的分塊［1-3］，在塊映射方面，文獻［2］提出了基于參考點的方法。參考點被定義為具有很高相似度的實體對，是在進行塊映射之前預先找好的，一般能夠通過比較簡單的映射策略找到，比如字符串匹配，近義詞關系，在WordNet詞典中具有近義詞或者相等關系，另外還可以利用本體可視化工具，如protégé［4］，通過人工識別來獲取，不過由于這種方法不利于映射系統的自動化程度，一般不會采用，只在前面幾種方法找到的參考點比較少的情況下才采取這種方法。該方法的主要是通過考察參考點在各個塊中的分布來來計算塊塊之間的計算各個塊之間的相似度。其主要思想是兩個塊之間的參考點個數越多，則這兩個塊之間的相似度越高，反之，如果兩個塊之間的參考點越少，他們的相似度越低。因此，對于那些在名稱上異構的本體對，找到的參考點就會很少，使得塊映射質量不高。

3 基于本體塊結構的塊映射策略

3.1 問題描述

目前解決大規模本體映射問題的最主要的方法采用分治法的思想，先對大規模本體進行分塊，然后在塊與塊之間進行映射發現，從而將大規模本體映射問題轉化成普通本體映射問題。因此，對大規模本體進行分塊之后，最重要的一個問題就是找到互相匹配的塊。由于一個塊中往往包含很多個實體元素，如概念，屬性，實例等，要直接計算兩個塊之間的相似度，就要計算塊與塊之間各個元素之間的相似度，這樣的話不僅違背了分治法思想的初衷，也是一件時間復雜度非常高的事情。

因此，大部分的大規模本體映射系統都采用啟發式的方法來尋找塊映射，如本文在第二章相關工作中介紹的基于參考點的方法，該方法并沒有精確的計算出各個塊之間的相似度，且塊映射的準確度完全依賴參考點的數量，參考點的數量越多，塊映射的準確度越高，反之，參考點數量越少，塊映射的準確度越低。

本體映射問題主要是為了解決不同本體之間的異構，由于本體異構有不同的表現形式，如名稱異構、結構異構、實例異構等等。因此，對于不同的本體映射任務，僅僅采用基于參考點的塊映射策略未必有效，因為有的本體之間在名稱上異構很嚴重，會導致找到的參考點非常少，這對發現塊映射是很不利的，因此，除了采用基于參考點的策略之外，尋找更多塊映射策略，提高塊映射的準確度。

本體中包含豐富的語義信息，而基于參考點的策略僅僅只利用了本體語言學方面的信息。由于本體具有高度結構化的特征，本體中的實體在結構上都是緊密相連的，這主要通過本體各種關系來體現，其中最重要的就是本體中的is-a關系，通過is-a關系，本體可以組織成一個樹狀結構，被is-a關系相連接的兩個實體具有繼承關系。因此，本文考慮利用本體結構上的信息來發現幫助發現塊映射。

計算技術與自動化2011年9月

第30卷第3期徐德智等:大規模本體分塊與映射中一種新的塊映射策略

在普通本體映射策略中［5］，有一種基于結構的策略，其基本的思想是利用本體中結構上的信息來計算實體之間的相似度，即在本體樹中，如果兩個實體結點的父節點相似，那么這兩個節點有可能相似；如果兩個實體結點的子節點相似，那么這兩個實體結點有可能相似；如果兩個結點的兄弟節點相似，那個這兩個結點有可能相似；如果兩個實體結點具有相同的實例，那么這兩個結點相似；如果兩個實體具有相同的屬性，那么這個實體結點可能相似。如果兩個屬性具有相同的rang和domain，那么它們也可能相似。因此本文考慮利用本體結構上的信息來幫助發現塊映射。

3.2 構建本體塊結構圖

在大規模本體匹配任務中，對大規模本體進行分塊后，待映射的兩個本體被分割成兩個本體塊集合，但是本體塊之間仍然存在結構上的聯系，因此，本文考慮利用這些結構上的聯系來還原本體層次結構圖，然后再采用普通本體映射中計算結構相似度的方法來計算本體塊之間的相似度。本文的基本思想是，在對大規模本體進行分塊的時候，不管采用的什么樣的分塊策略，一個本體的各個子塊之間多多少少存在語義聯系，在這里，僅僅只考慮實體之間的is-a關系，即一個子塊中存在一個或多個實體與其他子塊中的實體具有直接的is-a關系，這些is-a關系在分塊的時候被切斷，因此，本文考慮利用這些is-a關系構建一個本體塊圖，圖中的每個結點代表一個子塊，然后各個子塊通過這些is-a關系與其他本體塊相連，即圖中的每條邊代表一個is-a關系，然后從根節點所在塊開始，從上到下，構建本體塊結構圖。其具體步驟如算法1所示。

算法1：構建本體塊結構圖

輸入：待映射大規模本體的子塊集合以及實體之間的is-a關系

輸出：本體塊結構圖

Step1：找到Thing結點所在的塊，將其作為本體塊結構圖的根結點，圖G的深度d記為1；

Step2：分析本體結構圖中當前深度結點所代表的本體塊，獲取該塊中實體被切斷的is-a關系；

Step3：在本體子塊集合中尋找與該塊中實體存在is-a關系的塊，將其加入到圖G中，并用邊將它們連接起來，依次循環，直到所有與該本體塊具有is-a關系的所有塊都被加入到圖中；

Step4：若當前深度還存在其他塊節點未處理，轉到Step2，否則轉到Step4；

Step5：圖的深度d加1，轉至Step2，直到所有的塊都被加入到本體塊圖中；

Step6：算法結束。

對算法1的補充說明，在Step2中，對當前深度的塊結點的處理是按照從左到右的順序。通過算法，構建了一個本體塊結構圖，與原來的本體樹結構圖不同的是，圖中的節點數目將大大減少，圖中的每一個節點就是一個本體塊，這樣大大方便了結構相似度的計算。

圖1為一個本體的樹狀結構圖（部分），假設圖中的虛線為本體塊的分割線，則該本體被分為三個子塊，因此，對其應用算法1，構建的本體塊結構圖如圖2所示，可以看出，圖2中僅僅包含三個結點，遠遠少于圖1中的結點個數。

3.3 基于結構的塊相似度計算

由于前面提到了普通本體基于結構的映射策略所采用的思想，在計算本體塊結構相似度的時候可以借鑒其中的部分思想，因為畢竟本體塊圖中結點和實體節點存在著差異，即如果本體塊結點的父結點相似，那么這兩個結點可能相似；如果本體塊結點的兄弟結點相似，那么這兩個結點可能相似；如果本體塊結點的子結點相似，那么這兩個結點可能相似。目前在普通本體映射方面相似度計算策略已非常成熟，因此，本文采用文獻［6］中的結構相似度計算方法，得到本體塊基于結構的相似度，記為Simstr(bi，b′j)。

4 塊相似度計算

4.1 基于參考點的策略