本體領(lǐng)域綜合概念相似度計算中的權(quán)重確定方法

成錦暉, 鄭山紅, 李萬龍, 岳紹敏

(長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院, 長春 130012)

本體領(lǐng)域綜合概念相似度計算中的權(quán)重確定方法

成錦暉, 鄭山紅, 李萬龍, 岳紹敏

(長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院, 長春 130012)

利用粗糙集及條件信息熵的相關(guān)理論, 針對基于相似度計算的本體映射方法在相似度融合時權(quán)重過分依賴專家參與等問題, 給出一種自動確定權(quán)重的策略, 并通過實例驗證了該方法的可行性.該方法充分考慮在信息量不確定情況下, 用各屬性對系統(tǒng)信息熵的影響程度確定各屬性在當(dāng)前信息系統(tǒng)中所占的權(quán)重, 從而使本體的自動化映射和語義網(wǎng)的實時服務(wù)成為可能.

本體； 相似度； 概念相似度； 粗糙集； 信息熵； 權(quán)重

本體作為語義網(wǎng)的重要支撐, 近年得到快速發(fā)展.但由于知識領(lǐng)域的分布性和自治性及本體開發(fā)者的認(rèn)知水平不同, 導(dǎo)致了本體異構(gòu)性的產(chǎn)生, 因此本體映射與集成已成為當(dāng)前本體研究領(lǐng)域的熱點問題之一.本體映射過程分為3個步驟： 本體特征項的提取、概念相似度的計算和映射后處理.綜合相似度計算是本體映射的關(guān)鍵, 由于目前在進(jìn)行相似度合并時主要采用領(lǐng)域?qū)＜胰斯ご_定的方法設(shè)定各部分權(quán)重, 因此使映射效率受到較大影響且不適應(yīng)實時網(wǎng)絡(luò)服務(wù).基于此, 本文提出一種基于粗糙集條件信息熵的綜合相似度計算中權(quán)重的自動確定方法, 并以國際組織OAEI給出的測試數(shù)據(jù)benchmarks 2007為數(shù)據(jù)源進(jìn)行了算法驗證, 證明了該方法的有效性.

1 基本概念

1.1本體

本體是共享概念模型明確的形式化規(guī)范說明, 包含概念化、明確化、形式化和共享性4層含義.本文采用Gruber[1]提出的本體定義, 將本體表示為五元組：O=〈C,I,R,F,A〉, 其中:C表示概念集;I表示實例集合;R表示定義在概念集上的關(guān)系集;F表示函數(shù)集合;A表示公理集合.

1.2本體映射

本體映射是指兩個本體存在語義上的概念關(guān)聯(lián), 通過語義關(guān)聯(lián), 將源本體的元素映射到目標(biāo)本體的過程.Shvaiko等[2]給出了映射定義：f=〈id,e,e′,n,R〉, 其中:R表示實體e和e′的關(guān)系;n表示映射的置信度, 可通過相似度計算等方法獲取.

2 綜合概念相似度計算方法

目前, 研究人員普遍采用綜合相似度計算方法[3], 即綜合考慮待映射本體概念間的名稱、屬性、結(jié)構(gòu)和實例的相似程度, 運(yùn)用適當(dāng)?shù)臋?quán)重予以集成.

2.1相似度計算方法

2.1.1 概念名稱相似度計算 本文采用Wu-Palmer基于WordNet的相似度算法[4-5].WordNet是一部樹狀英語語義詞典, 其根據(jù)詞義組織詞匯信息, 用同義詞集合表示詞義, 同義詞集之間以語義相關(guān)聯(lián).對于本體O1中的概念A(yù)和本體O2中的概念B, 概念名稱相似度計算方法為

其中: depth(x)表示該概念在WordNet樹中所處的深度; lso(A,B)表示兩個概念的最近公共祖先.

2.1.2 概念屬性相似度計算 概念屬性包括數(shù)據(jù)類型屬性和對象類型屬性, 本文采用文獻(xiàn)[6]中的概念屬性相似度計算方法.

對于數(shù)據(jù)類型, 將兩個概念的數(shù)據(jù)類型屬性按數(shù)據(jù)類型分類, 成為若干個屬性集合； 對每種數(shù)據(jù)類型對概念A(yù)和B構(gòu)造屬性相似矩陣； 求出所有數(shù)據(jù)類型語義相似度的平均值, 記為S1(A,B).

對于對象類型, 設(shè)概念A(yù)和B的對象類型屬性集合分別為attrA={a1,a2,…,am}和attrB={b1,b2,…,bn}, 且概念A(yù)和B的對象類型屬性ai和bj所關(guān)聯(lián)的概念分別是Ai和Bj.求出Ai和Bj的語義相似度作為概念屬性ai和bj的相似度, 建立相似矩陣, 取出相似矩陣的最大項序列{t1,t2,…,tk}.該序列的算術(shù)平均數(shù)即為對象類型屬性的語義相似度, 記為S2(A,B).基于數(shù)據(jù)類型屬性和數(shù)據(jù)對象屬性相似度, 概念屬性相似度計算方法為

其中:α=數(shù)據(jù)類型屬性數(shù)量/總屬性數(shù)量;β=對象類型屬性數(shù)量/總屬性數(shù)量.

2.1.3 概念實例相似度計算 概念實例相似度計算[7]的原理為: 當(dāng)本體中的概念具有相同的實例時, 概念可能是相似的.基于該思想的概念實例相似度計算方法為

其中CN表示屬于概念N的實例集.

2.1.4 結(jié)構(gòu)相似度計算 概念的結(jié)構(gòu)包含豐富的語義, 兩個概念的父概念和子概念的相似度會影響兩個概念的相似性.因此可通過獲取結(jié)構(gòu)相似度度量概念間的相似度[8], 計算方法為

其中sim1和sim2分別是兩個概念的父概念集和子概念集的相似度.

2.2相似度的合并

基于式(1)～(4), 概念A(yù)和B的綜合相似度即為上述相似度值的加權(quán)平均, 計算方法為

其中ωi表示各部分相似度所占權(quán)重.在綜合相似度計算中, 權(quán)重的確定關(guān)系到綜合相似度計算結(jié)果的準(zhǔn)確性和效率, 通常通過專家意見指定ωi, 這種人工參與方法直接影響了相似度計算的效率.近年來, 一些研究人員提出了運(yùn)用Sigmoid函數(shù)自動生成各部分的權(quán)重, 但仍存在計算量大、區(qū)分度不高等問題.

3 基于粗糙集條件信息熵的權(quán)重確定

根據(jù)粗糙集理論, 設(shè)全域U表示參加相似度計算的概念對集合, 屬性集合A={C,D}, 令條件屬性集C={simname,simattr,simcase,simstruc}, 決策屬性集D=j5i0abt0b(d的取值為1或0, 表示兩概念相似與否), 屬性的值域集合為V,f：U×A表示信息函數(shù), 為U中的每對概念指定A中各屬性的屬性值.于是有決策表S=(U,C,D,V,f).

決策屬性D(U/D={d1,d2})對各相似度屬性C(U/C={c1,c2,c3,c4})的條件信息熵定義[9]為

相似屬性ci的重要度定義[9]為

則各相似屬性的權(quán)重為

通過上述方法計算各屬性的權(quán)重, 并將其應(yīng)用到映射過程中.基于粗糙集條件信息熵的權(quán)重確定方法即為在信息不完整的情形下, 利用各部分相似度的信息熵及對整個系統(tǒng)影響的程度, 對其重要性給予評定, 最后確定各部分的權(quán)重值.整個過程可由程序自動進(jìn)行, 避免了因為領(lǐng)域?qū)＜业倪^多參與而對系統(tǒng)性能產(chǎn)生影響, 為語義網(wǎng)的實時服務(wù)提供可能.

4 算法設(shè)計與實驗驗證

4.1算法設(shè)計

對于給定的兩個本體O1和O2, 綜合相似度計算中權(quán)重確定的算法如下.

輸入： 待映射本體O1和O2;

輸出： 概念對映射結(jié)果集;

1) 根據(jù)上述4種相似度計算方法分別計算O1和O2中各概念間的相似度simname,simattr,simcase和simstru, 記入數(shù)據(jù)集S1;

2) 隨機(jī)選取O1中的一個概念A(yù), 遍歷源數(shù)據(jù)集S1, 選取數(shù)據(jù)構(gòu)成歷史數(shù)據(jù)集, 離散化處理后建立決策表;

3) 根據(jù)式(6)計算條件屬性信息熵I(D/C),I(D/C1)和I(D/(C-{ci}));

4) 根據(jù)式(7)計算條件屬性ci∈C的重要度;

5) 計算條件屬性的權(quán)重ω(ci);

6) 處理當(dāng)前映射中的每條記錄, 運(yùn)用權(quán)重ω進(jìn)行加權(quán)平均, 得到概念間的最終相似度值, 獲得最佳映射;

7) 循環(huán); 處理源本體的剩余概念;

8) 結(jié)束.

4.2實驗驗證與分析

為了驗證本文方法的有效性, 采用國際組織OAEI給出的測試數(shù)據(jù)benchmarks 2007中的標(biāo)準(zhǔn)本體test#101和同義詞本體test#205進(jìn)行實驗.實驗結(jié)果表明, 若兩個概念存在相似的可能, 則兩概念間的4種相似度值之和普遍大于某一閾值； 反之則小于(閾值的選取最好采用圖像分割或Otsu自適應(yīng)方法給定)該閾值.因此, 隨機(jī)選取源本體中的一個概念(本文實驗選取Organization, 簡稱Org), 在結(jié)果集中各隨機(jī)選取6～8項記錄, 以確保最少有兩項其4種相似度之和不小于1.5, 并把其決策屬性分別記為0和1(遍歷后符合條件的詞有Movie,Entry,Person等, 并將每條記錄表示成Org-Movie的形式表示進(jìn)行相似度計算的兩個概念).這8組數(shù)據(jù)項作為相似度評價的歷史記錄, 將數(shù)據(jù)離散化后構(gòu)成決策表, 結(jié)果分別列于表1和表2.

表1 概念對相似度Table 1 Similarity of concept pairs

表2 決策表Table 2 Decision table

用式(6)～(8)計算各屬性的權(quán)重:

同理可得

最終每個屬性的權(quán)重為

W(c1)=0.162,W(c2)=0.162,W(c3)=0.334,W(c4)=0.342.

由結(jié)果可見, 本文中所占權(quán)重最大的是概念結(jié)構(gòu)的相似度, 而名稱相似度權(quán)重最小.分析源計算結(jié)果集、源概念Organization和目標(biāo)概念集間的simname值(即概念間名稱相似度)相差較大, 對兩個概念是否相似有很強(qiáng)的區(qū)分度, 應(yīng)給予小的權(quán)重值； 概念間結(jié)構(gòu)的相似度值在本文實驗中相差不大, 但較大的結(jié)構(gòu)差異將對最終結(jié)果產(chǎn)生決定性影響, 與本文方法所得結(jié)果相符.

由于本體開發(fā)者的習(xí)慣和同一領(lǐng)域內(nèi)資源分布呈現(xiàn)一定規(guī)律等特點, 本體中的不同概念在結(jié)構(gòu)和實例分布等方面所占的比重并沒有太大差異.因此, 在本文方法中, 通過利用部分?jǐn)?shù)據(jù)所得的權(quán)重值, 完全可運(yùn)用到當(dāng)前概念的整個映射過程中, 而避免了過多的重復(fù)計算.運(yùn)用本文所得權(quán)重計算test#101和test#205間概念的相似度, 得到相似度最大的概念對集合, 與OAEI組織提供的結(jié)果集相比, 正確率基本達(dá)到要求.

將本文方法所得權(quán)重與其他采用Sigmoid函數(shù)方法所得的權(quán)重進(jìn)行對比分析, 結(jié)果列于表3(用SigmoidX表示運(yùn)用Sigmoid計算事件Xi中各屬性權(quán)重的方法).

表3 本文方法與Sigmoid函數(shù)所得權(quán)重對比分析Table 3 Contrastive analysis between weight by this paper method and that by Sigmoid function

由表3可見, Sigmoid函數(shù)對每對概念都要進(jìn)行一次運(yùn)算, 計算量大, 且所得各權(quán)重值趨于平滑, 區(qū)分度不明顯.而本文方法利用一部分?jǐn)?shù)據(jù), 經(jīng)過分析計算最終得到的權(quán)重值在當(dāng)前候選概念集映射過程中均適用, 避免了重復(fù)計算, 特別是在本體規(guī)模較大的情況下, 計算次數(shù)極大減少, 且計算結(jié)果更接近于實際權(quán)重.在本體領(lǐng)域的綜合相似度計算中, 比Sigmoid函數(shù)更高效.

綜上可見, 本文提出的方法改進(jìn)了現(xiàn)有的綜合概念相似度計算方法, 實驗證明本文方法達(dá)到需求的同時避免了領(lǐng)域?qū)＜疫^多的參與, 從而達(dá)到綜合概念相似度計算自動進(jìn)行的目的.

[1]Gruber T R.A Translation Approach to Portable Ontology Specifications [J].Knowledge Acquisition, 1993, 5(2): 199-220.

[2]Shvaiko P, Jérme E.A Survey of Schema Based Matching Approaches [J].Journal on Data Semantics Ⅳ, 2005, 3730: 146-171.

[3]王穎, 劉群, 張冰.基于Top-k映射的本體匹配方法 [J].計算機(jī)工程, 2008, 34(15): 57-59.(WANG Ying, LIU Qun, ZHANG Bing.Ontology Matching Method Based on Top-kMapping [J].Computer Engineering, 2008, 34(15): 57-59.)

[4]Chantal Reynaud, Brigitte Safar.Exploiting WordNet as Background Knowledge [C]//International ISWC’07 Ontology Matching (OM-07) Workshop.Busan: [s.n.], 2007: 271-275.

[5]WU Zhibiao, Palmer M.Verb Semantics and Lexical Selection [C]//Proc of the 32nd Annual Meeting of the Association for Computational Linguistics.New York: ACM, 1994: 133-138.

[6]聶規(guī)劃, 左秀然, 陳東林.本體映射中一種改進(jìn)的概念相似度計算方法 [J].計算機(jī)應(yīng)用, 2008, 28(6): 1563-1565.(NIE Guihua, ZUO Xiuran, CHEN Donglin.Improved Concept Similarity Computing Approach in Ontology Mapping [J].Computer Applications, 2008, 28(6): 1563-1565.)

[7]Doan A, Madhavan J, Dhamankar R, et al.Learning to Match Ontologies on the Semantic Web [J].VLDB Journal, 2003, 12(4): 303-319.

[8]徐德智, 肖文芳, 王懷民.本體映射過程中的概念相似度計算 [J].計算機(jī)工程與應(yīng)用, 2007, 43(9): 167-169.(XU Dezhi, XIAO Wenfang, WANG Huaimin.Concept Similarity Calculating during the Process of Ontology Mapping [J].Computer Engineering and Applications, 2007, 43(9): 167-169.)

[9]鮑新中, 張建斌, 劉澄.基于粗糙集條件信息熵的權(quán)重確定方法 [J].中國管理科學(xué), 2009, 17(3): 131-135.(BAO Xinzhong, ZHANG Jianbin, LIU Cheng.A New Method of Ascertaining Attribute Weight Based on Rough Sets Conditional Information Entropy [J].Chinese Journal of Management Science, 2009, 17(3): 131-135.)

WeightDetermineMethodforComprehensiveSimilarityCalculationaboutConceptofOntology

CHENG Jinhui, ZHENG Shanhong, LI Wanlong, YUE Shaomin
(SchoolofComputerScience&Engineering,ChangchunUniversityofTechnology,Changchun130012,China)

Using the theory of rough set and conditional information entropy, we presented a strategy to automatically determine the weight in connection with determining weight in integrated similarity calculation relying too heavily on domain experts in the ontology mapping method based on similarity calculation.In full consideration of uncertain information using the influence degree of each attribute on the system information entropy to determine each attribute’s weight in the current information system made the automatic mapping of ontology and semantic network real-time services possible.At last, the feasibility of this method was verified by examples.

ontology; similarity; concept similarity; rough set; information entropy; weight

2013-12-09.

成錦暉(1989—), 男, 漢族, 碩士研究生, 從事智能計算的研究, E-mail: cjh985034577@126.com.通信作者： 鄭山紅(1970—), 女, 漢族, 博士, 副教授, 從事智能計算的研究, E-mail: bioszsh2007@aliyun.com; 李萬龍(1963—), 男, 漢族, 博士, 教授, 從事智能計算的研究, E-mail: lwl@mail.ccut.edu.cn.

吉林省自然科學(xué)基金(批準(zhǔn)號: 20130101060JC)和吉林省教育廳“十二五”科學(xué)技術(shù)研究項目(批準(zhǔn)號: 2014131; 2014125).

TP391

A

1671-5489(2014)06-1272-05

10.13413/j.cnki.jdxblxb.2014.06.31

韓 嘯)