陳紅紅, 李 輝, 李新春

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

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

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

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

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

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

0 引言

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

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

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

1 FCA(formal concept analysis)

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

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

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

定義2[3]形式背景T=(G,M,R)的一個形式概念是一個對象與屬性對(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),當且僅當C?A(或者說D?B).這種“≤”構(gòu)成了L(G,M,R)的一個偏序關(guān)系,偏序關(guān)系也就形成了格的層次, (L(G,M,R),≤)和LUB、GLB構(gòu)成了形式背景(G,M,R)的形式概念格,并且它是一個完備格.LUB和GLB分別為:

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

表1 一個形式背景Tab.1 A formal context

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

2 詞語相似度

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

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

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

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

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

3 概念格的語義匹配

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

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

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

然而這樣做會引起前面所述的一些缺點,文獻[4]中提出:把每一個文檔構(gòu)造成一個文檔格;同時用戶查詢的自然語言也構(gòu)成一個概念格,叫做查詢格.因為概念格和形式背景是一一對應(yīng)的,所以查詢格和文檔格之間的匹配就是檢索對用戶查詢有用的文檔,然后根據(jù)格之間的語義相似度進行排序.匹配模型如圖2所示.

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

3.2 概念格的語義匹配策略

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

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

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

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

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

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

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

用我們的方法重新計算文獻[3]中格匹配的例子,實驗證明我們的方法能取得一樣的效果.

4 結(jié)論

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

將來的工作主要是:1)現(xiàn)有的概念格是基于二值背景的,但文檔中出現(xiàn)術(shù)語的頻數(shù)經(jīng)常不是一次,所以需要拓展二值背景到多值背景中構(gòu)造概念格.2)生成的概念格比較復(fù)雜,有些屬性對于匹配沒有起到作用,降低了效率,所以,要對概念格的屬性進行約減.3)我們構(gòu)造的是基于某個領(lǐng)域的知識本體,所以文檔受到領(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].中文計算語言學(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].計算機科學(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é)重點實驗室項目,編號XZD0818-09.

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