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

成錦暉, 鄭山紅, 李萬(wàn)龍, 岳紹敏

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

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

成錦暉, 鄭山紅, 李萬(wàn)龍, 岳紹敏

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

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

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

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

1 基本概念

1.1本體

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

1.2本體映射

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

2 綜合概念相似度計(jì)算方法

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

2.1相似度計(jì)算方法

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

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

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

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

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

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

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

其中CN表示屬于概念N的實(shí)例集.

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

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

2.2相似度的合并

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

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

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

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

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

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

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

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

4 算法設(shè)計(jì)與實(shí)驗(yàn)驗(yàn)證

4.1算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

8) 結(jié)束.

4.2實(shí)驗(yàn)驗(yàn)證與分析

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

表1 概念對(duì)相似度Table 1 Similarity of concept pairs

表2 決策表Table 2 Decision table

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

同理可得

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

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

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

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

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

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

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

綜上可見(jiàn), 本文提出的方法改進(jìn)了現(xiàn)有的綜合概念相似度計(jì)算方法, 實(shí)驗(yàn)證明本文方法達(dá)到需求的同時(shí)避免了領(lǐng)域?qū)＜疫^(guò)多的參與, 從而達(dá)到綜合概念相似度計(jì)算自動(dòng)進(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ì)算機(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].計(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]徐德智, 肖文芳, 王懷民.本體映射過(guò)程中的概念相似度計(jì)算 [J].計(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].中國(guó)管理科學(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—), 男, 漢族, 碩士研究生, 從事智能計(jì)算的研究, E-mail: cjh985034577@126.com.通信作者： 鄭山紅(1970—), 女, 漢族, 博士, 副教授, 從事智能計(jì)算的研究, E-mail: bioszsh2007@aliyun.com; 李萬(wàn)龍(1963—), 男, 漢族, 博士, 教授, 從事智能計(jì)算的研究, E-mail: lwl@mail.ccut.edu.cn.

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

TP391

A

1671-5489(2014)06-1272-05

10.13413/j.cnki.jdxblxb.2014.06.31

韓 嘯)