ABox推理計算實體相似度

薛詠,馮博琴,武艷芳

?

ABox推理計算實體相似度

薛詠1,2,馮博琴1,武艷芳2

針對主題圖本體映射中主題上下文語義不易確定,缺少分類信息,但有明確的結構語義特征的特點,提出了A-Sim主題圖本體映射算法。首先對主題圖中的主題進行分類,利用描述邏輯語言ALCIR+的表達能力,根據主題屬性及關聯關系建立各種能表達上下文語義信息的概念術語集,將主題圖本體轉換為斷言集合;其次在斷言集合上進行多項式復雜度實例檢測,記錄模型構造過程中的個體,獲得主題的上下文語義;最后將上下文語義結合元素級概念相似度算法計算實體綜合相似度,獲得異構主題圖實體間的實體映射關系。通過對主題圖進行相似度計算實驗,結果證明新算法對主題圖實體相似度計算綜合性能至少提升了14%。

本體映射;相似度計算;描述邏輯;實例檢測

實體相似度計算是本體映射的基礎,用以解決異構本體語義一致性與本體復用問題,在知識地圖中,需要不斷更新融合新數據,這些數據中存在術語異構等問題。主題圖是一種應用廣泛的知識地圖結構,主題、關聯(association)、資源出處(occurrences)組成的集合體(TAO)[1]通過主題自身特征及與其他概念的關聯關系確定概念語義。

主題圖本體的融合算法,主要有文獻[2]提出的SIM算法,屬于元素級算法;文獻[3]提出的TM-MAP算法,計算主題圖中主題和主題間關系,將關系的計算結果以權重的形式綜合到計算公式來判決概念的融合,考慮了數種固定的屬性關系;文獻[4]提出的TOM算法,與SIM算法類似,基于字符串統計,涉及到主題圖三要素中的主題、關系、資源實體;文獻[5]利用關鍵詞聚類圖與文本聚類圖方法確定主題關系;文獻[6]提出的擴展主題圖融合ETMSC算法,該算法對詞典未收錄詞匯的相似度來自于兩個方面,一是進行切詞然后進行基于字符串的統計,二是來自于與之有直接關系的概念相似度;文獻[7]對專用領域概念利用語料庫技術形成專業領域詞典,提高對領域本體元素級相似度計算性能;文獻[8]提出的一種將語義進行命題邏輯描述的方法,對一般概念相似度計算,語義引入合取、析取與否定構子,表達能力差,利用WordNet詞典進行概念可滿足性判斷。

針對主題圖中數據量大、結構化良好的特點,本文提出一種混合式相似度A-Sim算法,利用ALCIR+描述邏輯語言實現對概念上下文語義的靈活描述。根據主題圖元素之間的關系定義概念術語集(TBox),將主題的結構語義描述為多種邏輯概念,將待匹配數據轉化為斷言集(ABox),設計了一種多項式復雜度的概念實例檢測推理算法,每一種可滿足的概念都是一個主題的結構語義,將結構語義與元素級語義相似度相結合,進行綜合實體相似度計算。

1 背景知識與問題描述

標準主題為主題、資源兩層結構,擴展主題圖在標準知識地圖-主題圖上增加知識元層,對主題知識結構進行細化,增加知識地圖導航能力,是一系列E-Learning知識獲取服務國家級項目的知識組織結構,主題、知識元、資源的教育類資源知識組織方式已有很多實際應用[6]。圖1是兩個異構擴展主題圖片段,圖中節點為主題圖實體,邊標注為關系類型,從圖中可以看出主題圖間“數據通信”與“服務”、“面向無連接”與“無連接服務”、“IP地址”與“網絡協議地址”都屬于異構術語,是相似主題。此外,有同形異意異構等,相似度計算的目的即對不同本體內實體進行相似度計算,同義術語賦予高相似度。

圖1 異構的擴展主題圖

本文中實體相似度指主題圖中主題的相似度,可以定義為一個4元組,e1、e2分別為第一、第二映射元素實體,k為兩元素關系之間的相似度,一般取值范圍為[0,1],r為兩元素之間的關系,包括對稱、相交、包含、不相交等。

2 主題圖的描述邏輯表示方法

2.1ALCIR+描述邏輯

描述邏輯是語義網OWL語言的理論基礎,描述邏輯語言建立的本體知識庫可表示為KB=,TBox是有關概念和角色的蘊含公理集合,聲明概念或角色間的包含關系。ABox是有關個體的實例斷言集合,斷言包括聲明個體是某概念的實例,以及個體之間的二元關系。描述邏輯語言包含邏輯構子越多表達能力越強,推理復雜度越高,在基本的AL語言上加入概念析取、完全存在量詞、概念否定后為ALC語言,加入逆角色、允許角色傳遞后構成ALCIR+邏輯描述語言。根據擴展主題圖實體關系特點,以ALCIR+作為TBox描述語言。

2.2 構建TBox

擴展主題圖的基本概念有主題、知識元包含的子類以及資源包含的子類,其中主題間關系有前續和后繼、整體和部分、同義、類似、對比、不相關等,根據需要還可以定義并列、用途和環境、因果等任意關系。主題與知識元、資源的結合中,不同的結構有明確的自然語義信息,比如主題是知識點,在學習過程中有先后順序,不考慮知識結構文件來源,與知識元關系構成學習單元,這些學習單元的結構是相對穩定的,因此以知識類別、知識單元進行結構語義匹配,比一般模式匹配更加準確,利用描述邏輯進行精確形式化結構描述是非常有意義的[8-9]。

主題為基本概念,前驅主題類為原子定義概念,?后繼.主題為復雜定義概念。①～⑥為對主題結構概念的定義,同理可定義出整體概念類與部分概念類公理,區別知識等;⑧～⑨為知識元與資源出處概念,其中⑦為角色公理,表示兩角色為互逆角色,定義NR+={有后繼,有前驅,整體,部分}。實體基本類概念、知識元結構概念以及角色關系與性質用類似方法定義。通過定義的TBox可以看出,圖1中的“IP協議”屬于前驅主題類、后繼主題類、屬性類的交集,而“IP地址”屬于知識單元。利用公用推理機可驗證構建的TBox是非循環一致的ALCIR+描述公理集合。

2.3 構建斷言

Abox包含兩類斷言,C(a)形式的概念斷言,以及R(a,b)形式的角色斷言,擴展主題圖格式文件XTM(基于XML語法的TM文件)以標準主題圖語法為基礎,從數據庫中抽取個體聲明,個體之間的關系聲明,形成XTM文件。根據XTM文件建立ABox的過程,即為抽取TBox定義的相關概念實例與角色實例的過程,利用XStream技術實現XTM與Java對象之間的轉換,去除與結構信息無關的范圍約束等元素。將XTM的個體與角色信息讀入定義的數據結構中,形成需要的ABox,因為大規模主題圖本體標注困難,只能給出個體的基本概念類斷言。

3 結構語義信息計算

3.1 可滿足性推理

ABox的推理都可以轉換為一致性推理,目前有兩種方法,一種將ABox展開為預完整形式[10],將ABox中的斷言根據TBox不斷擴充,得到一系列等價的ABox集合,如果沒有出現空概念或者沖突,表明ABox一致,算法復雜度為4倍指數級。另一種將ABox推理規約到TBox推理中[11]。

定義1 一個ABox相對于TBox是可滿足的,是指存在一個模型I={ΔI,·I}滿足TBox,并且對于ABox有:如果C(a)∈ABox,那么aI∈CI;如果(a,b)∈ABox,那么(aI,bI)∈RI;如果a=b∈ABox,那么aI=CI;如果a≠b∈ABox,那么aI≠bI。

3.2 結構語義計算

定義2 同知識單元個體集合。假設個體a屬于知識單元C,以a為根節點,構造概念C完備語義樹過程中經過個體的集合。

對于個體主題a,同知識單元個體集合就包含了a關于C的結構語義信息,而所有知識單元概念都是定義概念,所以結構信息計算中只對定義概念進行實例檢測。為了記錄同知識單元集合,設計一個儲存結構語義的數據結構

其中Ci{b1,b2,…,bmi}表示個體a所屬概念Ci中包含的所有個體。每個個體a都有一個對應的Msem集合,記錄ABox中實例所屬概念語義信息。

設計實例檢測函數instanceDetection返回實例檢測a:Cn關于TopicMap=的結果,同時生成一個以L為對象的列表,存儲Ci{b1,b2,…,bmi},記錄實例模型構建過程中經過的節點,當實例檢測結果為真時,將該列表與其對應的概念加入Msem集合。

本文中的TBox是一個可展開的ALCIR+邏輯系統,因此首先需要將知識庫TopicMap中的TBox展開并保持語義不變,展開后的術語集右邊只包含基礎概念,左邊為定義概念,這樣定義概念可以內化為一個標準形式

C=D C ?U．C

(1)

式中:D指基本概念的合取與吸取;U為所有角色的超角色,這樣所有的實例檢測都可以表示為對迭代表達式的概念可滿足性檢測。經典的概念可滿足性檢測采用對個體斷言集合加入否定概念斷言,再利用Tableaux算法不斷對個體斷言集進行擴展,如果擴展樹出現矛盾,則表明概念是可滿足的?；谡Z義的實例檢測與經典的方法有如下兩點不同。

(1)經典的實例算法通過加入否定概念,運用tableaux算法檢測ABox關于TBox是否一致,會因為存在量詞和數量限定而產生新節點,隨著ABox擴展可能會在新節點中發現沖突,從而判斷不一致性。比如對于ABox={a:主題,a:?R.C},一致性檢測會產生一個R后繼節點x={C},若有a的鄰居再次擴展x節點,沖突是有可能的,當沒有其他節點對a節點進行擴展時它是一致的,但是增加節點會改變主題圖原有結構,而在主題圖中這樣的語義結構是不存在的。

(2)現有的實例檢測算法,只給出是否滿足的結果,而不能記錄同知識單元個體集合。

Output:L

begin

1.初始化L包含Cn的全局變量

2.for all subconceptCiinCn

3. ifa:Ci

4.L.add (a); return ture;

5. else

6. switch(Ci)

8. return true;

9. else return false;

11. return true;

12. else return false;

13. case ?R.Dif exist R-successorbi

14. if iD(bi:D);

15. return true

16. else return false;

17. case ?R.Dfor all R-successor ofbi

18. if al l iD(bi:D)

19. return true;

20. else return false;

21. case ?R+.Dfor all R-successor ofbi

22. if all iD(bi:D)

23. ifbihas R-successorci

24. if all iD(ci:D)

25. return true;

26. else return false;

27. else return true;

28. else return false;

29. default return false;

30.end for

end

如果instanceDetection返回為false值,將L中的Ci刪除,這樣L只包含a可滿足概念。算法補充說明:①對于所有的涉及R-角色,如果存在R-.D則將R-看作一般角色展開,否則檢測是否有R角色的前驅節點b存在,則對b:D進行實例檢測,關于前驅、后繼、鄰居的概念可參考文獻[10];②?R+可能引起循環檢測,所以需要對其經過的個體節點進行記錄并檢測,進行阻塞,使算法能夠中止,也就是進入第一次迭代后,以下所有迭代都不能再對根節點進行實例檢測,這說明存在一個傳遞關系組成的環路徑;③所有需要對鄰居進行實例檢測時,如果不存在滿足要求的鄰居節點,都返回false值;④因為析取與存在規則,個體對概念的可滿足模型可能有多個,所以需要通過加標記的方法,對所有分支都進行檢測。

因為本算法并不產生新的斷言節點,而且除過逆角色外所有以個體為根節點向后繼角色單向擴展的,只有傳遞性角色可能產生循環檢測,通過阻塞后,算法中的5條規則必然會在最多遍歷整個主題圖節點后中止。

證明完畢。

3.3 相似度計算

設待匹配擴展主題圖中的主題集合分別為E1={e1,e2,…,en}、E2={e1,e2,…,em},任意兩個主題之間的相似度計算由語法相似度SG、語義相似度SS及結構相似度ST三部分組成,通過實例檢測得到個體的Msem集合包含完整的上下文結構信息。

對于語法、語義相似度的計算方法參見文獻[7],其中語義相似度使用WordNet詞典、HowNet詞典、同義詞詞林進行相似度計算,針對字典中沒有的專業領域主題相似度計算采用了基于語料庫的方法,獲得了較好的實驗結果,因此本文只闡述ST的計算算法。設兩個待比較主題對為(ei,ej),對應的題可滿足的概念集合分別為:Msemi={C1,C2,…Ci,…,Cn},Msemj={C1,C2,…Cj,…,Cm},其中Ci、Cj為概念包含個體的集合,設Msemi與Msemj中概念名的交集為G,并集為E,對所有概念名相同的集合做Jarcard相似度計算,得到|G|個集合相似度

(2)

式(2)中以詞法語法相似度作為集合交并集運算的基礎。設置閾值t1,若Csim>t1的概念名個數為p,則主題間的相似度可表示為ST(ei,ej)=(|G|-p)/|E|,在相似性判斷中通過實驗設置閾值t2,如果ST>t2,則認為兩主題相似。

3.4 算法復雜度分析

設TBox左側概念數為n,根據展開后的TBox計算LHS概念間包含關系,共需要進行n2次計算,本部分復雜度為平方復雜度。

設ABox中包含的個體數為n,需要檢測的概念數為m,每個概念的子概念數最多為p,因為算法?R+.D規則復雜度最高,傳遞性檢測最多可以設計n-1個節點,假設子概念約束都是全稱量詞,角色深度為q,則每個子概念需要檢測的次數為(n-1)q,則算法復雜度為O(mpnq+1)。

4 實驗與結果分析

相似性度量算法的評價,使用信息檢索領域通用的查準率(Precise)、查全率(Recall)和F值(F-measure) 3個評價標準。

擴展主題圖TBox共15個基本概念,18個定義概念,23個角色,其中傳遞角色4個,逆角色2個。ABox測試數據來源于“863課題”的計算機領域擴展主題圖。將3組不同標注來源的《計算機網絡》擴展主題圖分別進行相似度計算,其中節點最大連通圖分別為756、452、563,融合時刪除了所有孤立節點。應用開源推理工具pellet調試一致并分類后,解析成專用TBox數據結構。實驗平臺Inter i5 4 200MB CPU,內存4 GB,Java虛擬機內存1 GB,3組比較最大用時82 s。

閾值t1、t2使用實驗的方法確定,以計算結果的綜合性能為依據,假定兩閾值對結果的影響是相互獨立的,采用經驗給定t1值后,取使得F值最高的t2為最終閾值,再對t1進行調整。圖2為t1=0.4時不同t2值對各項性能指標的影響,在進行集合相似度計算時,僅使用了字符串比對的方法來提高算法時間性能。準確性由計算結果與人工標注結果進行對比得出,除去完全相同的主題,人工標注給出了50對相似度最高的主題,根據實驗結果取t1=0.4、t2=0.6作為最終閾值。

圖2 不同閾值t2與算法性能關系

在閾值確定過程中,為了提高速度與結果檢查效率,未計入語義相似度SS。以獲得性能最好時的閾值為目的,圖3給出了結構語義相似度對匹配結果的影響,在語法相似度計算的基礎上,加入ST的計算結果,查全率有11%的提高,同時對異構術語相似度的準確性也得到了提高,F值提高了6%。

圖3 語法相似度與總相似度的比較

經過語法相似度篩選以后,共得到117 936個比對結果,其中90%以上的值為0,其他值主要分布在0.3～0.7之間,實驗結果顯示查全率隨著閾值t2的升高下降很快。這是由于一些關系復雜的相似主題,在另一個主題圖中卻關系簡單,導致相似度下降,主要中心節點比如“協議”、“網絡協議”關聯的實體可能很多。一些相似度很高的主題,可能完全不相似,比如“子網掩碼”與“網絡網關”都是“TCP/IP”參數的后繼,但是又都沒有其他個體關系。這種情況比較多,所以設置策略將大于閾值,但只有一個鄰居的個體對相似度設為0。計算機網絡主題圖中的主題以基本概念為主,產生異構的來源主要是人工標注過程中的隨意性,另外一部分來自網絡抽取的數據,但是這些基本概念一般比較固定,一個異構實體的關聯實體都異構的情況很少,而且主題關系的關聯以前后序、整體部分關系較多,很適合本文算法的特點,但是同樣存在一些不能識別的實體,比如“網關”與“協議轉換器”,一個關聯著“網絡層設備”,一個關聯著“網絡層”,這類異構主題降低了相似度算法的性能,需要依賴更好的領域知識詞典配合。

將A-Sim算法與SIM、TM-MAP、ETMSC算法進行了比較,結果如表1所示,因為SIM算法的語法相似度計算來自于通用本體詞典,因此性能較差。TM-MAP、ETMSC的相似度計算包括了主題上下文語義,因此對查全率有較大的提升作用,但是以相鄰實體作為上下文語義不夠精確。本文算法在各方面都體現出較好的性能結果,綜合相似最少提高了14%。

表1 當前主題體相似度算法性能的比較

表2為不同算法對部分異構主題相似度判斷結果的描述,括號內為1表示認為相似,0表示認為不相似。因為本文算法的概念是以相對固定的知識結構定義的,因此對于關聯節點不但涉及到相鄰實體,還涉及到多級相連實體,尤其對前后續、整體部分中的異構術語能計算出較準確的相似度。例如圖1中的“網際協議地址”與“IP地址”的結構相似度可以追溯到“傳輸層”主題,向下可以達到資源層,對于主題對“數據通信”和“服務”,因為A-Sim可以將兩個part-of關系主體合并為一個“部分概念”,從而減小了主題關系數量不同產生的干擾。在最壞情況下,算法將退化為一般結構相似度算法,比如ETMSC的關聯結構算法,即主題不屬于TBox中定義的復雜結構概念類。

表2 部分異構相似主題的匹配

注:√表示正確

實驗表明，A-Sim算法對本體中主題上下文環境的確定更加全面、準確,提升了實體相似度計算的查全率與查準率。實驗同時顯示,進一步研究實體結構語義與語法語義相似度有效結合的方法,比如自適應的參數調整,有利于提高對同形異意異構實體的相似度計算性能。

[1] GARRIDO A, ILARRI S. TMR: a semantic recommender system using topic maps on the items’ descriptions [C]∥The Semantic Web: ESWC 2014 Satellite Events. Berlin, Germany: Springer, 2014: 213-217.

[2] MALCHER L, WITSCHEL H F. Merging of distributed topic maps based on the subject identity measure (SIM) approach [M]. Leipzig, Germany: LIT, 2004: 1-11.

[3] KIM J M, SHIN H, KIM H J. Schema and constraints-based matching and merging of topic maps [J]. Information Processing and Management, 2007, 43(4): 930-945.

[4] 吳笑凡, 周良, 張磊, 等. 分布式主題地圖合并中的TOM算法 [J]. 武漢大學學報: 工學版, 2006, 39(5): 131-136. WU Xiaofan, ZHOU Liang, ZHANG Lei, et al. TOM algorithm in distributed topic maps merging [J]. Journal of Wuhan University: Engineering Edition, 2006, 39(5): 131-136.

[5] DING Y, FU X. The research of text mining based on self-organizing maps [J]. Procedia Engineering, 2012, 29(4): 537-541.

[6] 魯慧民, 馮博琴, 李旭. 面向多源知識融合的擴展主題圖相似性算法 [J]. 西安交通大學學報, 2010, 44(2): 20-25. LU Huimin, FENG Boqin, LI Xu. Novel similarity algorithm of extended topic maps for multi-resource knowledge fusion [J]. Journal of Xi’an Jiaotong University, 2010, 44(2): 20-25.

[7] 薛詠, 馮博琴, 劉偉濤. 擴展主題圖本體融合策略與算法 [J]. 西安交通大學學報, 2011, 45(10): 13-18. XUE Yong, FENG Boqin, LIU Weitao. Strategy and algorithm for merging ontologies of extend topic maps [J]. Journal of Xi’an Jiaotong University, 2011, 45(10): 13-18.

[8] GIUNCHIGLIA F, SHVAIKO P, YATSKEVICH M. S-Match: an algorithm and an implementation of semantic matching [C]∥ESWS. Berlin, Germany: Springer, 2004: 61-75.

[9] CHIU D Y, PAN Y C. Topic knowledge map and knowledge structure constructions with genetic algorithm, information retrieval and multi-dimension scaling method [J]. Knowledge-Based Systems, 2014, 67(9): 412-428.

[10]FOKOUE A, KERSHENBAUM A, MA L, et al. The summary abox: cutting ontologies down to size [M]. Berlin, germany: Springer, 2006: 343-356.

[11]HAARSLEV V, M?LLER R. Expressive Abox reasoning with number restrictions, role hierarchies, and transitively closed roles [C]∥International Conference on Principles of Knowledge Representation and Reasoning. Hamburg, Germany: Universit?t Hamburg, 2000: 273-284.

(編輯 趙煒)

(1.西安交通大學電子與信息工程學院,710049,西安;2.西南科技大學信息工程學院,621010,四川綿陽)

Measuring Similarity of Entities Based on ABox Reasoning

XUE Yong1,2,FENG Boqin1,WU Yanfang2

(1. School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China; 2. School of Information Engineering College, Southwest University of Science and Technology, Mianyang, Sichuan 621010, China)

Aiming at the problems that the context semantics of concepts are hard to make sure in the ontology mapping of topic map, and that the topics are lack of classification information but have well-defined constructive semantic characters, an A-Sim algorithm for ontology mapping of topic maps is presented in this paper. At first, the topics in topic maps are classified using expression ability of description logic language ALCIR+; then the concept terminology box expressing various context semantics of concepts is built according to the attributes and associations of topics, and the topic map ontologies are transformed into an assertions box. Second, a polynomial complexity algorithm for instance detection is presented and implemented on the assertions box, to obtain the context semantics of concepts by storing individuals in the process of constructing models. At last, the semantic similarity which combines the syntax-based and semantic similarity measurements is measured to calculate the synthetic similarity of entities, and then the mapping relationship between entities of heterogeneous topic maps is obtained. The experiments of similarity measurement of topic maps demonstrated that the novel method has achieved better performance and improved the comprehensive performance value at least 14% than other methods.

ontology mapping; similarity measurement; description logic; instance detection

2015-01-13。 作者簡介:薛詠(1978—),男,博士生;馮博琴(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61202181);教育部博士學科點專項科研基金資助項目(20130201130002)。

10.7652/xjtuxb201509013

TP391

A

0253-987X(2015)09-0070-07