基于领域本体的概念格语义匹配

陈红红, 李 辉, 李新春

(1.西华大学数学与计算机学院 四川成都610039;2.西华大学档案馆 四川成都610039)

基于领域本体的概念格语义匹配

陈红红1, 李 辉2, 李新春1

(1.西华大学数学与计算机学院 四川成都610039;2.西华大学档案馆 四川成都610039)

本体作为语义网的重要工具,是对共享概念模型的形式化规范说明.领域本体更是说明了一个领域特定的概念定义和概念之间的关系,提供该领域中发生的活动以及该领域的主要理论和基本原理等.提出了一种基于领域本体的概念格语义匹配方法,以提高匹配的精确度.

形式概念分析;概念格;语义匹配;领域本体;相似度

0 引言

传统的信息检索系统是基于向量空间模型的,它最早是由Salton等人提出的[1],是建立在词与词相互独立基础上的,因此无法解决多义词和同义词的影响.虽然基于SVD的LSI技术解决了上述问题,但是仍然不太适合于大规模动态变化的数据集.

基于格的信息检索模型从1958年由Mooners[2]提出就获得了广泛关注.德国的Wille将格的思想上升到理论的角度,提出了形式概念分析(FCA)[3].基于格的信息检索能在一定程度上改善检索的现状,特别是对自然语言的处理方面,概念格能抽象文档的概念.但是现有的基于格的信息检索系统大都是基于格的推荐系统,利用哈斯图进行导航,这样的系统存在一些缺点[4]:1)把文档集作为对象,把文档中的关键词作为属性,对于人脑表达、感知、交流概念来说不现实;2)用一个大的概念格来表达整个文档集的计算复杂度高,并且不利于小的文档集的应用;3)过去的模型只是停留在浏览上;4)建格的算法复杂,随着格中节点的增加时间复杂度成指数增长;5)格一旦建立就固定了,不能再改变.

本文分析了基于概念格的信息检索模型,提出了基于领域本体的概念格的语义匹配策略.

1 FCA(formal concept analysis)

形式概念分析(FCA)是信息科学中用来进行数据分析、知识表示、信息处理、信息检索等重要的数学手段.它是由W ille于1982年首次提出[3],用于概念的发现、排序和显示,所有的概念连同它们之间泛化/例化关系构成了一个概念格.

定义1[3]一个形式背景是一个三元组T=(G,M,R),其中,G,M是非空有穷集合,R⊆G×M是它们之间的二元关系,G是研究的对象集合,M是描述G的属性集合,(g,m)∈R表达了g具有属性m.

为了表达该形式背景中的一个形式概念(X,Y),Wille定义了两个集合函数↑和↓:

定义2[3]形式背景T=(G,M,R)的一个形式概念是一个对象与属性对(X,Y)∈P(G)×P(M),使得X↑=Y和Y↓=X.集合X称为概念的外延,集合Y称为概念的内涵.

P(G)×P(M)的子集合L(G,M,R)形成了形式背景的所有形式概念,形式概念(A,B)≤(C,D),当且仅当C⊆A(或者说D⊇B).这种“≤”构成了L(G,M,R)的一个偏序关系,偏序关系也就形成了格的层次, (L(G,M,R),≤)和LUB、GLB构成了形式背景(G,M,R)的形式概念格,并且它是一个完备格.LUB和GLB分别为:

举例如下:形式背景T=(G,M,R),其中,G={1,2,3,4},M={a,b,c,d},二元关系见表1,其形成的概念格的Hasse图见图1.从形式背景生成概念格的过程实质上是一个概念聚类的过程.一个形式背景对应唯一的一个概念格,一个概念格对应一个形式背景,研究概念格的过程实质也就是在研究概念格所对应的形式背景.

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

图1 形式背景所对应的概念格Fig.1 The concept lattice corresponding to the fo rmal context

2 词语相似度

语言学研究认为词语距离与词语相似度之间有着密切的关系[5]:两个词语的距离越大,其相似度越低;反之,两个词语的距离越小,其相似度越大.二者之间可以建立一种简单的对应关系,这种对应关系需要满足3个条件:1)两个词语距离为0时,其相似度为1;2)两个词语距离为无穷大时,其相似度为0;3)两个词语的距离越大,其相似度越小(单调下降).对于两个词语W1和W2,记其相似度为Sim(W1,W2),其词语距离为Dis(W 1,W2),那么可以定义一个满足这3个条件的简单转换关系

其中,α是一个可调节的参数,代表当相似度为0.5时的词语距离值.

计算词语距离有两种常见的计算方法,一种是根据某种世界知识(ontology)来计算,一种为利用大规模的语料库进行统计.根据世界知识(ontology)计算词语语义距离的方法,一般是利用一部同义词词典(Thesaurus).与叙词表相比,领域本体既是概念集,也是一个知识库.叙词表中只包含“用、代、属、分、参、族”这样的简单语义关系,而领域本体则可描述更细致、全面的概念间关系,但这并不影响采用语言学中的语义距离思想来计算领域本体中的概念语义相似度.设C1,C2是领域本体中的两个概念,Sim(C1,C2)表示这两个概念之间的相似程度,则有其中,n是概念C1与C2在领域本体中所具有的最大深度;θi是权重(可简单地取θi=1/n);δi(C1,C2)取值定义为

根据实际需要,可对式中的θi进行调整.

有了词语间的相似关系,就可以采用文献[6]的相似图定义来构造相似图.

3 概念格的语义匹配

信息检索从一定意义上来讲是对自然语言的处理,而现在对自然语言语句的匹配一般是将两个句子表示成词的向量,然后计算两个向量的夹角余弦来作为两个句子之间的相似程度,目前信息检索所流行的基于向量空间模型也是采用这个方法来解决文档的匹配问题.概念是人类进行思维最基本的单位,是用来组织成为诸如判断、结论等更为复杂思想的基础,是人类进行知识表述的一种有效手段.FCA可以从文档数据库中抽取出其对应的形式背景知识,然后进行概念聚类,也就是抽取文档中心思想的一个过程,把相关概念聚类更能反映文档的主题.用概念格进行信息检索一般要经过文档内容抽取与预处理、构造形式背景、建立概念格、匹配以及结果排序处理等几个重要过程,这里重点研究概念格之间的匹配问题.

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

传统的基于概念格的信息检索系统是基于概念格的导航系统,把文档集作为对象,把文档中的关键词作为属性,然后建立一个概念格.用户提供检索词从一个结点开始,通过概念格的偏序关系来寻找自己所需要的文档集.

然而这样做会引起前面所述的一些缺点,文献[4]中提出:把每一个文档构造成一个文档格;同时用户查询的自然语言也构成一个概念格,叫做查询格.因为概念格和形式背景是一一对应的,所以查询格和文档格之间的匹配就是检索对用户查询有用的文档,然后根据格之间的语义相似度进行排序.匹配模型如图2所示.

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

3.2 概念格的语义匹配策略

文献[4]中的Partial matching和Keyword matching缺乏对概念语义的描述,本文提出了一种语义匹配算法,在不降低查全率的同时,提高了查找的准确率.算法的提出是基于如下的考虑:人脑对信息筛选的时候,一般先看文档中是否有我们需要的对象,如果没有就可以跳过该文档继续查找,否则再看文档中对该对象的描述是否满足我们的条件,根据对该对象描述的详细程度进行评分.当然对该对象描述得越详细,就越满足我们的需求,得分也就越高.格的匹配并不是其外形结构上的匹配,同构的两个格表达的思想可能相差很大,格的匹配从根本上说是对格中节点所蕴含内容的匹配,因此我们通过计算格中节点的相似度来衡量格的相似度.

3.2.1 概念格节点间的相似度[6]相同或不同形式背景下的两个概念(E1,I1)和(E2,I2)之间的相似度计算公式为

其中,r是E1,E2势的较大值,m是I1,I2势的较大值,w是权重因子且是 I1×I2候选对集合中最大的相似度之和.

3.2.2 节点与概念格间的相似度 有了相似度计算公式(5),就可以计算一个格Q上的概念Ci与另一个格D各层上节点概念的相似度,选取最大的作为候选概念,通过概念格的偏序特性,就可以依次计算候选概念的子概念,这样层层递归,就可以得到D上对Ci描述的一条或多条路径,大部分情况下是一条路径,用Ri表示,那么定义节点Ci与概念格D的相似度为

其中n是路径上节点概念的个数.

3.2.3 概念格间的相似度 把概念格Q中所有节点与概念格D的相似度之和定义为概念格Q与D的相似度

其中n是格Q中节点的个数.

用我们的方法重新计算文献[3]中格匹配的例子,实验证明我们的方法能取得一样的效果.

4 结论

针对传统的向量空间模型对现有搜索引擎发展的制约,明确了基于概念格的搜索引擎匹配模型的设计.概念格的匹配问题在目前的研究中还处于起始阶段,为解决查询格和文档格之间语义匹配的问题,我们采用了领域本体中相似度的思想,提出了语义概念格的匹配算法,在不降低查全率的同时,提高了查询的准确率.文献[7]指出,在知识处理的过程中FCA和本体可以有效地相互补充:一方面,FCA可以很好地辅助本体工程;另一方面,本体工程也改善了基于FCA的应用,帮助FCA处理大数据库的问题等等.

将来的工作主要是:1)现有的概念格是基于二值背景的,但文档中出现术语的频数经常不是一次,所以需要拓展二值背景到多值背景中构造概念格.2)生成的概念格比较复杂,有些属性对于匹配没有起到作用,降低了效率,所以,要对概念格的属性进行约减.3)我们构造的是基于某个领域的知识本体,所以文档受到领域范围的限制,而从文档形式背景中去挖掘本体就没有领域的束缚.

[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] 刘群,李素建.基于《知网》的词汇语义相似度计算[J].中文计算语言学,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与本体结合研究的综述[J].计算机科学,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

西华大学重点实验室项目,编号XZD0818-09.

陈红红(1971-),女,讲师,硕士研究生,主要从事计算机及其应用研究,E-mail:hhchen94@sina.com.