基于領(lǐng)域本體的概念格語義匹配

陳紅紅, 李 輝, 李新春

(1.西華大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院 四川成都610039;2.西華大學(xué)檔案館 四川成都610039)

基于領(lǐng)域本體的概念格語義匹配

陳紅紅1, 李 輝2, 李新春1

(1.西華大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院 四川成都610039;2.西華大學(xué)檔案館 四川成都610039)

本體作為語義網(wǎng)的重要工具,是對(duì)共享概念模型的形式化規(guī)范說明.領(lǐng)域本體更是說明了一個(gè)領(lǐng)域特定的概念定義和概念之間的關(guān)系,提供該領(lǐng)域中發(fā)生的活動(dòng)以及該領(lǐng)域的主要理論和基本原理等.提出了一種基于領(lǐng)域本體的概念格語義匹配方法,以提高匹配的精確度.

形式概念分析;概念格;語義匹配;領(lǐng)域本體;相似度

0 引言

傳統(tǒng)的信息檢索系統(tǒng)是基于向量空間模型的,它最早是由Salton等人提出的[1],是建立在詞與詞相互獨(dú)立基礎(chǔ)上的,因此無法解決多義詞和同義詞的影響.雖然基于SVD的LSI技術(shù)解決了上述問題,但是仍然不太適合于大規(guī)模動(dòng)態(tài)變化的數(shù)據(jù)集.

基于格的信息檢索模型從1958年由Mooners[2]提出就獲得了廣泛關(guān)注.德國的Wille將格的思想上升到理論的角度,提出了形式概念分析(FCA)[3].基于格的信息檢索能在一定程度上改善檢索的現(xiàn)狀,特別是對(duì)自然語言的處理方面,概念格能抽象文檔的概念.但是現(xiàn)有的基于格的信息檢索系統(tǒng)大都是基于格的推薦系統(tǒng),利用哈斯圖進(jìn)行導(dǎo)航,這樣的系統(tǒng)存在一些缺點(diǎn)[4]:1)把文檔集作為對(duì)象,把文檔中的關(guān)鍵詞作為屬性,對(duì)于人腦表達(dá)、感知、交流概念來說不現(xiàn)實(shí);2)用一個(gè)大的概念格來表達(dá)整個(gè)文檔集的計(jì)算復(fù)雜度高,并且不利于小的文檔集的應(yīng)用;3)過去的模型只是停留在瀏覽上;4)建格的算法復(fù)雜,隨著格中節(jié)點(diǎn)的增加時(shí)間復(fù)雜度成指數(shù)增長;5)格一旦建立就固定了,不能再改變.

本文分析了基于概念格的信息檢索模型,提出了基于領(lǐng)域本體的概念格的語義匹配策略.

1 FCA(formal concept analysis)

形式概念分析(FCA)是信息科學(xué)中用來進(jìn)行數(shù)據(jù)分析、知識(shí)表示、信息處理、信息檢索等重要的數(shù)學(xué)手段.它是由W ille于1982年首次提出[3],用于概念的發(fā)現(xiàn)、排序和顯示,所有的概念連同它們之間泛化/例化關(guān)系構(gòu)成了一個(gè)概念格.

定義1[3]一個(gè)形式背景是一個(gè)三元組T=(G,M,R),其中,G,M是非空有窮集合,R?G×M是它們之間的二元關(guān)系,G是研究的對(duì)象集合,M是描述G的屬性集合,(g,m)∈R表達(dá)了g具有屬性m.

為了表達(dá)該形式背景中的一個(gè)形式概念(X,Y),Wille定義了兩個(gè)集合函數(shù)↑和↓:

定義2[3]形式背景T=(G,M,R)的一個(gè)形式概念是一個(gè)對(duì)象與屬性對(duì)(X,Y)∈P(G)×P(M),使得X↑=Y和Y↓=X.集合X稱為概念的外延,集合Y稱為概念的內(nèi)涵.

P(G)×P(M)的子集合L(G,M,R)形成了形式背景的所有形式概念,形式概念(A,B)≤(C,D),當(dāng)且僅當(dāng)C?A(或者說D?B).這種“≤”構(gòu)成了L(G,M,R)的一個(gè)偏序關(guān)系,偏序關(guān)系也就形成了格的層次, (L(G,M,R),≤)和LUB、GLB構(gòu)成了形式背景(G,M,R)的形式概念格,并且它是一個(gè)完備格.LUB和GLB分別為:

舉例如下:形式背景T=(G,M,R),其中,G={1,2,3,4},M={a,b,c,d},二元關(guān)系見表1,其形成的概念格的Hasse圖見圖1.從形式背景生成概念格的過程實(shí)質(zhì)上是一個(gè)概念聚類的過程.一個(gè)形式背景對(duì)應(yīng)唯一的一個(gè)概念格,一個(gè)概念格對(duì)應(yīng)一個(gè)形式背景,研究概念格的過程實(shí)質(zhì)也就是在研究概念格所對(duì)應(yīng)的形式背景.

表1 一個(gè)形式背景Tab.1 A formal context

圖1 形式背景所對(duì)應(yīng)的概念格Fig.1 The concept lattice corresponding to the fo rmal context

2 詞語相似度

語言學(xué)研究認(rèn)為詞語距離與詞語相似度之間有著密切的關(guān)系[5]:兩個(gè)詞語的距離越大,其相似度越低;反之,兩個(gè)詞語的距離越小,其相似度越大.二者之間可以建立一種簡單的對(duì)應(yīng)關(guān)系,這種對(duì)應(yīng)關(guān)系需要滿足3個(gè)條件:1)兩個(gè)詞語距離為0時(shí),其相似度為1;2)兩個(gè)詞語距離為無窮大時(shí),其相似度為0;3)兩個(gè)詞語的距離越大,其相似度越小(單調(diào)下降).對(duì)于兩個(gè)詞語W1和W2,記其相似度為Sim(W1,W2),其詞語距離為Dis(W 1,W2),那么可以定義一個(gè)滿足這3個(gè)條件的簡單轉(zhuǎn)換關(guān)系

其中,α是一個(gè)可調(diào)節(jié)的參數(shù),代表當(dāng)相似度為0.5時(shí)的詞語距離值.

計(jì)算詞語距離有兩種常見的計(jì)算方法,一種是根據(jù)某種世界知識(shí)(ontology)來計(jì)算,一種為利用大規(guī)模的語料庫進(jìn)行統(tǒng)計(jì).根據(jù)世界知識(shí)(ontology)計(jì)算詞語語義距離的方法,一般是利用一部同義詞詞典(Thesaurus).與敘詞表相比,領(lǐng)域本體既是概念集,也是一個(gè)知識(shí)庫.敘詞表中只包含“用、代、屬、分、參、族”這樣的簡單語義關(guān)系,而領(lǐng)域本體則可描述更細(xì)致、全面的概念間關(guān)系,但這并不影響采用語言學(xué)中的語義距離思想來計(jì)算領(lǐng)域本體中的概念語義相似度.設(shè)C1,C2是領(lǐng)域本體中的兩個(gè)概念,Sim(C1,C2)表示這兩個(gè)概念之間的相似程度,則有其中,n是概念C1與C2在領(lǐng)域本體中所具有的最大深度;θi是權(quán)重(可簡單地取θi=1/n);δi(C1,C2)取值定義為

根據(jù)實(shí)際需要,可對(duì)式中的θi進(jìn)行調(diào)整.

有了詞語間的相似關(guān)系,就可以采用文獻(xiàn)[6]的相似圖定義來構(gòu)造相似圖.

3 概念格的語義匹配

信息檢索從一定意義上來講是對(duì)自然語言的處理,而現(xiàn)在對(duì)自然語言語句的匹配一般是將兩個(gè)句子表示成詞的向量,然后計(jì)算兩個(gè)向量的夾角余弦來作為兩個(gè)句子之間的相似程度,目前信息檢索所流行的基于向量空間模型也是采用這個(gè)方法來解決文檔的匹配問題.概念是人類進(jìn)行思維最基本的單位,是用來組織成為諸如判斷、結(jié)論等更為復(fù)雜思想的基礎(chǔ),是人類進(jìn)行知識(shí)表述的一種有效手段.FCA可以從文檔數(shù)據(jù)庫中抽取出其對(duì)應(yīng)的形式背景知識(shí),然后進(jìn)行概念聚類,也就是抽取文檔中心思想的一個(gè)過程,把相關(guān)概念聚類更能反映文檔的主題.用概念格進(jìn)行信息檢索一般要經(jīng)過文檔內(nèi)容抽取與預(yù)處理、構(gòu)造形式背景、建立概念格、匹配以及結(jié)果排序處理等幾個(gè)重要過程,這里重點(diǎn)研究概念格之間的匹配問題.

3.1 基于格的信息檢索匹配模型

傳統(tǒng)的基于概念格的信息檢索系統(tǒng)是基于概念格的導(dǎo)航系統(tǒng),把文檔集作為對(duì)象,把文檔中的關(guān)鍵詞作為屬性,然后建立一個(gè)概念格.用戶提供檢索詞從一個(gè)結(jié)點(diǎn)開始,通過概念格的偏序關(guān)系來尋找自己所需要的文檔集.

然而這樣做會(huì)引起前面所述的一些缺點(diǎn),文獻(xiàn)[4]中提出:把每一個(gè)文檔構(gòu)造成一個(gè)文檔格;同時(shí)用戶查詢的自然語言也構(gòu)成一個(gè)概念格,叫做查詢格.因?yàn)楦拍罡窈托问奖尘笆且灰粚?duì)應(yīng)的,所以查詢格和文檔格之間的匹配就是檢索對(duì)用戶查詢有用的文檔,然后根據(jù)格之間的語義相似度進(jìn)行排序.匹配模型如圖2所示.

圖2 基于概念格的匹配模型Fig.2 Thematching model based on the concep t

3.2 概念格的語義匹配策略

文獻(xiàn)[4]中的Partial matching和Keyword matching缺乏對(duì)概念語義的描述,本文提出了一種語義匹配算法,在不降低查全率的同時(shí),提高了查找的準(zhǔn)確率.算法的提出是基于如下的考慮:人腦對(duì)信息篩選的時(shí)候,一般先看文檔中是否有我們需要的對(duì)象,如果沒有就可以跳過該文檔繼續(xù)查找,否則再看文檔中對(duì)該對(duì)象的描述是否滿足我們的條件,根據(jù)對(duì)該對(duì)象描述的詳細(xì)程度進(jìn)行評(píng)分.當(dāng)然對(duì)該對(duì)象描述得越詳細(xì),就越滿足我們的需求,得分也就越高.格的匹配并不是其外形結(jié)構(gòu)上的匹配,同構(gòu)的兩個(gè)格表達(dá)的思想可能相差很大,格的匹配從根本上說是對(duì)格中節(jié)點(diǎn)所蘊(yùn)含內(nèi)容的匹配,因此我們通過計(jì)算格中節(jié)點(diǎn)的相似度來衡量格的相似度.

3.2.1 概念格節(jié)點(diǎn)間的相似度[6]相同或不同形式背景下的兩個(gè)概念(E1,I1)和(E2,I2)之間的相似度計(jì)算公式為

其中,r是E1,E2勢的較大值,m是I1,I2勢的較大值,w是權(quán)重因子且是 I1×I2候選對(duì)集合中最大的相似度之和.

3.2.2 節(jié)點(diǎn)與概念格間的相似度 有了相似度計(jì)算公式(5),就可以計(jì)算一個(gè)格Q上的概念Ci與另一個(gè)格D各層上節(jié)點(diǎn)概念的相似度,選取最大的作為候選概念,通過概念格的偏序特性,就可以依次計(jì)算候選概念的子概念,這樣層層遞歸,就可以得到D上對(duì)Ci描述的一條或多條路徑,大部分情況下是一條路徑,用Ri表示,那么定義節(jié)點(diǎn)Ci與概念格D的相似度為

其中n是路徑上節(jié)點(diǎn)概念的個(gè)數(shù).

3.2.3 概念格間的相似度 把概念格Q中所有節(jié)點(diǎn)與概念格D的相似度之和定義為概念格Q與D的相似度

其中n是格Q中節(jié)點(diǎn)的個(gè)數(shù).

用我們的方法重新計(jì)算文獻(xiàn)[3]中格匹配的例子,實(shí)驗(yàn)證明我們的方法能取得一樣的效果.

4 結(jié)論

針對(duì)傳統(tǒng)的向量空間模型對(duì)現(xiàn)有搜索引擎發(fā)展的制約,明確了基于概念格的搜索引擎匹配模型的設(shè)計(jì).概念格的匹配問題在目前的研究中還處于起始階段,為解決查詢格和文檔格之間語義匹配的問題,我們采用了領(lǐng)域本體中相似度的思想,提出了語義概念格的匹配算法,在不降低查全率的同時(shí),提高了查詢的準(zhǔn)確率.文獻(xiàn)[7]指出,在知識(shí)處理的過程中FCA和本體可以有效地相互補(bǔ)充:一方面,FCA可以很好地輔助本體工程;另一方面,本體工程也改善了基于FCA的應(yīng)用,幫助FCA處理大數(shù)據(jù)庫的問題等等.

將來的工作主要是:1)現(xiàn)有的概念格是基于二值背景的,但文檔中出現(xiàn)術(shù)語的頻數(shù)經(jīng)常不是一次,所以需要拓展二值背景到多值背景中構(gòu)造概念格.2)生成的概念格比較復(fù)雜,有些屬性對(duì)于匹配沒有起到作用,降低了效率,所以,要對(duì)概念格的屬性進(jìn)行約減.3)我們構(gòu)造的是基于某個(gè)領(lǐng)域的知識(shí)本體,所以文檔受到領(lǐng)域范圍的限制,而從文檔形式背景中去挖掘本體就沒有領(lǐng)域的束縛.

[1] Salton G,Wong A,Yang C S.A vector space model for automatic indexing[J].Communication of the ACM 1975,18 (11):613-620.

[2] Mooers C N.A mathematical theo ry of the use of language symbols in retrieval[C]//Proceedings International Conference Scientific Information.Washington D C,1958:1327-1367.

[3] Wille R.Restructuring Lattice Theo ry:an App roach Based on Hierarchieson Concep ts,in Ordered Sets[M].Dordrecht, Reidel,1982:445-470.

[4] Rajapakse R K,Denham M.Text retrievalw ith mo re realistic concep tmatching and reinforcement learning 2006 info rmation science[J].Info rmation Processing and Management,2006,42(5):1260-1275.

[5] 劉群,李素建.基于《知網(wǎng)》的詞匯語義相似度計(jì)算[J].中文計(jì)算語言學(xué),2002,7(2):59-76.

[6] Formica A.Ontology-based concep t similarity in fo rmal concep t analysis[J].Information Science,2006,176(18): 2624-2641.

[7] 周文,劉宗田,陳慧瓊.FCA與本體結(jié)合研究的綜述[J].計(jì)算機(jī)科學(xué),2006,33(2):8-12.

Concept Lattice Semantic Matching Based on Domain Ontology

CHEN Hong-hong1, L IHui2, L IXin-chun1
(1.School of M athem atics and Com puter,X ihua University,Chengdu 610039,China; 2.A rchives,Xihua University,Chengdu 610039,China)

A n ontology,as an impo rtant tool of the semantic Web,is a fo rmal and exp licit specification of shared concep tmodel.And a domain onto logy further specifies the relationship betw een definitions and concep tsof a specific domain,and p rovides the activitiesoccurring,aswell as the main theories,basic p rincip les,etc,in the domain.A concep t lattice semantic matching method based on the domain ontology is p roposed for imp roving the matching accuracy.

formal concep t analysis;concept lattice;semantic matching;domain ontology;similarity

TP 311

A

1671-6841(2010)02-0070-04

2009-12-20

西華大學(xué)重點(diǎn)實(shí)驗(yàn)室項(xiàng)目,編號(hào)XZD0818-09.

陳紅紅(1971-),女,講師,碩士研究生,主要從事計(jì)算機(jī)及其應(yīng)用研究,E-mail:hhchen94@sina.com.