联通10010

计算机科学2005Vol.
32No.
9基于Ontology的概念联通在查询系统中的应用研究')雷玉馥,曹宝香,王书西2(山东省曲阜师范大学日照校区计算机学院日照276826)1(中国科学院计算技术研究所北京100080)2摘要为了姆高知识查询系统的知识服务质量,本文提出了一种基于Ontology的概念联通模型,该模型在知识获取阶段能够对知识进行修正、精简和整合,在知识服务阶段能对原有知识库中的知识进行广泛而有意义的知识重组.
本文首先讨论知识本体和概念联通模型,然后分析基于Ontology的概念联通方法,最后给出在知识查询系统中的联通算法.
关健词知识本体,概念联通,查询系统,知识服务,联通算法TheApplicationofKnowledge-Ontology-BasedConcept-InterconnectionMethodsinKnowledgeQuerySystemLEIYtrXia'CAOBao-Xiang'WANGSliu-Xi'(DepartmentofComputerScience,QufuTeachersUniversity,Rizhao276826)1(InstituteofComputingTechnology,ChoneseAcademyofSciences,Be巧ing100080)2AbstractToimprovethecapabilityofknowledgeserviceintheknlwledgequerysystem,thispqperhasproposedanontology-basdedconcept-interconnectionmodelwhichcanrefinethephaseofknowledgeacquisition.
nectionintheprimitiveknowledgeMeanwhile,ithasprovedthatandrestructurethenewlycollectedknowledgeduringthissystemmoreneedsbroadlyknlowledgeintercon-base.
Thepaper,firstlydiscussesknowledgeontologyandconceptmodel,andthenanalyzesmethodsofconcept-interconnection,andfinallyprovidesthreekindsofinterconnectionalgorithms.
Knowledgeontology,Concept-interconnection,Knowledgequerysystem,Knowledgeservice,Interconnectionalgorithm1引言在人工智能和知识工程的研究和应用系统的开发中,知识查询系统是一个十分活跃的分支领域,在许多领域中都有成功的应用.
在开发知识查询系统过程中,有三点显得尤为重要:一是作为查询系统的知识来源,首先要建立一个健全、协调和具有良好联通性的领域知识库;二是开发友好而美观的知识界面,这是一个很重要的研究领域[[1,21;三是查询系统应具有较强的知识推理/知识联通能力,以提供给用户高质量的知识服务[[3]知识本体(KnowledgeOntology)已成为人工智能新的研究领域,是知识共享/重用的重要基础[4],目的就是捕获相关领域的知识,提供对该领域知识的共同理解,确定该领域内共同认可的词汇,并从不同层次的形式化模式上给出这些词汇和词汇之间相互关系的明确定义.
目前,已经广泛应用到许多大型知识系统中(例如美国的D.
Lenat教授等研制的大型常识知识库系统Cyc、普林斯顿大学的重要研究成果一Word-Net等).
概念联通在知识获取和知识服务阶段都具有重要作用.
在知识获取阶段,采集到的"新知识"通常存在下面问题:一是知识之间的不一致性;二是知识粒度(Granularity)不同;三是知识的精度不同.
通过概念联通可以对所获取的知识进行修正、精简和整合;在知识服务阶段,针对不同层次用户的不同层次的、复杂的知识查询需求,可以通过对知识库中的原子知识进行广泛而有意义的联通/重组,反馈给用户高质量的知识.
因此,将概念联通方法引人知识查询系统具有广泛的应用前景.
本文第2部分主要讨论两个层次的知识本体模型:一是领域本体模型(SOM),二是概念本体模型(COM);第3部分讨论基于概念本体的关系联通,并给出相应的基本性质;第4部分介绍基于概念联通的知识查询系统结构模型设计,并给出三个具体的联通算法,并对其进行简单的复杂性分析;最后总结全文并提出需要进一步探讨的问题.
2知识本体模型(KnowledgeOntologyModel,KOM)我们把知识本体分为两个层次:一是领域本体;二是概念本.
前者描述某个领域中的概念以及概念结构,后者主要描述概念的内涵以及与其他概念的关联.
在设计中,在考虑有利于知识查询系统的同时兼顾了本体设计的完备性、准确性、可重用性、简洁性和可扩展性等重要原则151.
2.
1领域本体模型(SpecialOntologyModel)定义2-1(领域本体模型)[3〕一个领域本体模型SOM=(C,R,A,T,H,O,F).
其中,C表示领域概念的集合;R表二)本文得到山东省自然科学基金(项目号:Y2003G01)、山东省曲阜师范大学青年科学基金(项目号:U03015)和曲阜师范大学科研启动基金资助.
雷玉扭讲师.
,宝香教授/硕士生导师.
王书西博士.
187·示定义在C上的关系集合;A表示描述概念的属性集合;下表示C中所有概念的上位概念;H=(C,,p(X,)Cp(兀);(2.
8)Y,CYZ=>a(Y,)Cu(YZ);(2.
9)XCa(p(X));(2.
10)YCT(a(X)).
概念本体模型COM=(A(C),I(C),R(C),H)的一般结构描述为:COMRelationSet(与其他概念的关联描述集>Hc1(C)XA(C)设COM=(A(C),I(C),R(C),P(C),H),对3基于COM的概念联通分析在第2部分,主要讨论了COM,现在就讨论概念联通.
本节主要讨论基于关系的联通.
为清晰起见,仅限于对二元关系的讨论.
多元关系可以转化成二元关系处理.
首先给出关系联通定义,然后给出一些基本性质.
定义3.
1(关系联通)给定COM,二(A(C,),I(C),R(C,),H)和COMZ=(A(C),I(C),R(C),H),称概念C,和C之间存在联通,如果满足下面两个条件之一(R表示二元关系):(3.
1){UFLDR(C))n{UFLDR(C2)}:'-45.
其中,FLDR(C)={C13RER(C,),使得CRC,,或者CRC)(称为强关系联通);或者(3.
2)存在从C,到C的路径,称为弱关系联通.
命题3.
1设C,和C2是强关系联通,则C,和C联通关系的关系图主要有如下4种情况(其中C称为C,和C的联通因子):山C今se.
.
下1|Cc广了②③④C,CZC,CZQ个Ct定义2.
5①CZ(I型关系联通)(II型关系联通)(川型关系联通)C,(w型关系联通)命题3.
2设C为C;和C2的联通因子,C为C.
和C3的联通因子,则有如下结论:0.
3)如果C与C2、C2与C3都是工型(II型、111型)关系联通的,则C与C'也是I型(II型、Ul型)关系联通的,并且C是其联通因子;(3.
4)如果C,与C2X2与C3分别是I型和II型关系联通的,则C与C'是工型关系联通的,并且C2是其联通因子;(3.
5)如果C,与C2、C2与C分别是I型和m型关系联188·通的,则C与C,是m型关系联通的,并且Q2是其联通因子.
证明:由命题3.
2的图示容易得证.
命题3.
3概念C,和CZ是弱关系联通的,如果满足下面条件:(3.
6)如果存在CEFLDR(C,),CEFLDR(CZ),使得极大下界glb(C,C)或极小上界lub(C,C)存在;证明:假设存在CEFLDR(C,).
C任FLDR(C2),使得极大下界glb(C,C)存在,则由定义3.
1和((3.
1)可知C,和glb(C,C),C2和glb(C,C)是强关系联通的;故由((3.
2)可知C,和Q是弱关系联通的;同理可证极小上界lub(C,C)存在的情况.
证毕.
定义3.
2(C-联通类)设IC是某个领域本体模型SOM中的概念集合C上的联通关系,对于任一固定的概念CEC,把与C有强联通关系的概念构成的集合称为C-联通类,记为〔司.
.
定义3.
3(联通矩阵)给定[Cl」二和〔Q」二,设v=CC1J1C000JIC=lCl,C2,…,CNf,则称A=(几)NXN为V的联通矩阵.
其中,用户领域专家知识工程师知识查询系统界面知识获取机制推理机领域知识库图I基于概念联通的知识获取与查询系统模型结构1,当Ci-Cj0,否则引理3.
1给定概念Cl和C2,设V=[Cl]ICUCC21JC-(Cl,C2,.
.
.
ICIO,则有结论(其中A为V的联通矩阵):存在Ck,使得Cl~Ck-C2#}Dlk·Dk2=1.
其中,·表示矩阵的乘法.
证明:+=>"如果存在Q,使得Cl-Ck-C,则Dlk=1,场=1,从而Dlk·几2=1t".
"如果存在Ck,使得Dlk·Dk2=1,则Dlk=1,D12=1,又由马*和Dk:的定义可知Cl-'Ck-C2o该引理说明,如果存在概念Ck,使得Cl-Ck-C2成立,则一定有Dlk·Dkz=1;反之如果不存在Ck,使得Cl}CkCz成立,则一定有Dlk=.
或Dkz=.
,从而Dlk·Dkz二.
.
命题3.
4(概念联通存在的判定定理)给定概念C1和Cz,设V=[Cl〕二UCC2]rc={Cl,C2I.
.
.
ICN),则有结论(其中A为V的联通矩阵):(i)Cl和Q之间存在概念联通,如果存在最小自然数M,使得AM的第1行第2列元素不为零,并且该元素就是长度为M的联通总数;(2)若存在联通,则长度不超过N的联通总数就是D=A+矛+…+八N的Dlz护0,证明:(1)若M=1,则有Cl-Cz,根据((3.
1),结论显然成立,其联通长度为1;如果M=2,则有引理3.
1,结论是成立的,其联通长度为2;如果M-3,则A"'=A·AM-l,从而存在ql],使得Dlk[l3(1)·Dk[l]2(M-1)=1,从而有Dlk{l3(l)=1,巩l]2(M-ll=1,再由引理3.
1可知有Cl-Ck[l].
又因为A&1--l=A·AM-z,从而存在Ck[21,使得风11k[2](1)·Dk[2]2(M-2)=1,再由引理3.
1可知有Ck[1]-Ck[2],从而有Cl~Ck[1]Ck[2].
重复上述操作,则可得到联通C,}Ck[,]-rCk[2]}.
.
.
.
c2.
显然其长度恰好为M.
根据矩阵的乘法可知,长度为M的联通总数恰好是该元素.
(2)由(1)可知,长度为M的联通总数恰好是为A"'的第1行第2列,所以当N>M>l时,长度不超过N的联通总数为D=A+A2+---+A'的第1行第2列元素.
4基于知识本体的查询系统结构模型和联通算法设计4.
1基于知识本体的查询系统结构模型设计下面讨论基于概念联通的知识获取与查询系统模型结构设计(见图1).
该模型引人了概念联通机制.
概念联通在知识服务阶段的功能与目的:对于用户的知识需求主要有:一是简单查询知识库中的原子知识,主要包括查询概念的名称、概念的属性及其属性值等;二是查询知识库中所蕴涵的复合知识.
实践证明,要满足不同层次用户的更为高层次的、复杂的知识查询,提高知识查询系统的智能程度,不仅需要有一个具有良好联通性的大型知识库/数据库,更重要的是进行广泛而有意义的知识推理/知识联通.
为此,我们设计了上述查询系统结构模型.
4.
2概念联通算法设计与分析为了尽可能提高知识查询质量,我们介绍三个描述性的概念联通算法.
其中包括:一般的联通算法、基于深度优先的联通算法和长度为M的最强联通算法.
为了叙述方便,我们只以从概念C,到Cz的联通为例.
从概念C2到C,的联通类似.
一般联通算法:输人概念C,和Q,物出C,到Cz的联通.
其流程图见图2,Stepl:在领域本体中找到相应的概念本体O(C,)和O(C).
Step2:求出[C,〕二、[C2I二和V=CC,〕二UCc2)1c={cC2,一,CN}Step3:判断C,和C2是否是I型(II型.
II[型)关系联通.
若是,则输出该联通.
Step4:求出V的联通矩阵A以及A"',其中,N>M>1.
Step5:若存在联通,则求出所有的长度不超过N的联通,并输出联通集合.
由命题3.
4可知,若D12(M)=A0,则一定存在长度为M的联通,并且联通的个数即为D12(M).
因为M是有限的,所以我们可以用深度优先的算法来求出所有的长度为M的联通.
另外,根据需要,在搜索中没有必要产生概念的所有后继,而只需产生有希望在联通上的概念即可.
这就是基于深度优先的联通算法的基本思想.
下面给出基于深度优先的联通算法,其中C(Ktl)[I(ktl)]表示在搜索中产生的第(K+1)层的概念.
I表示由第K层概念产生第(K+1)层的后继概念的变量.
令Io=0,基于深度优先的联通算法:输人概念C1和Cz.
设Open表存放未扩展的概念;Closed表存放已扩展的概念.
(1)初始化Open表、Closed表为:Open表仅含有概念Cl,Closed表为空.
(2)Repeat(直到进行Dl2(M).
次)(I)把第1个概念从Open表中移到Closed表中;(n)若K=1,则输出Closed表的内容,否则继续进行;189·(Hi)扩展概念CK[rk]2(M)7-.
和AM=A·AM.
.
.
.
1扩展概念Ck[rk}的所有使得DK[Ki](K+1)[r(*十1)]D(Rtll[I(k+1)]2(M-1)护0成立的后继概念C(K+1)[1(k+1)]并把它们放人Open表的前头;其中,D、[.
〕2'材-K[rk_2(M-K)妻1(k+1)>l(W)K~K+l基于深度优先的联通算法是求出所有的从概念C,到C2长度为M的关系联通.
一般联通算法的流程图如下:迪克斯特拉(Dijkstra)算法:若ClC2C3.
.
.
CK是从C:到CK的最强联通,则C,QG…价一,是从C,到蛛一,的最强联通.
该算法描述如下:最强联通算法:输人概念C,的和Q,求出从C,到Q的长度为M的最强联通.
Stepl:根据给定概念C,和C2.
由基于深度优先的联通算法求出分支长度都为M的联通图G.
很显然,图G的宽度为D12(M)#0.
另V=(G的结点}.
Step2:初始化P=(C,},T=V-(C,}.
对于每个CET,定义联通强度I(C)为:I(C)W(C,,C),若C,-C;0,若C,和C不联通;0,若C--C,.
了!
破1一-其中,W(CC)表示抽象边C,---C的联通权重.
Step3:找T中的概念X,使得I(X)=MAX(I(C)ICET},则I(X)是从C,到X的最强联通.
Step4:置T<--T-(X),PGPU(X).
Step5:若X:G,则修改I(C)的值.
其方法如下:若有X-C(X在Step3中选出来的),则置I(C)cMAX(I(C),I(C)+W(X,C)};转Step3,Step6:若X=C},则算法结束.
其中,Step5的本质是若由于概念X的引人使得I(C)更大,则修改之.
通过这个算法,我们可以找到长度为M的最强联通.
图2一般联通算法的流程图5总结和进一步讨论的问题自然语言查询系统是一种很重要的知识服务系统.
在这种系统中,除了有一个友好、美观的知识界面外,更重要的是反馈给用户的知识质量.
为了提高知识服务的质量,本文从知识本体和概念图的角度分析了概念联通存在的判定和联通算法等.
概念联通的主要功能是:在知识服务阶段,通过各种知识推理/概念联通可以满足不同层次用户的知识需求.
在第3部分,我们介绍了三个联通算法:一般概念联通算法,基于深度优先的联通算法和最强联通算法.
这些算法的设计和实现都是建立在已经创建的领域知识本体和概念本体上.
实践证明,不完善或不合理的本体会影响概念联通的质量.
目前,概念联通所处理的知识主要是一些事实性知识或结构比较规范的知识.
下一步,我们将把概念联通的思想、用户建模技术和知识推理技术结合起来,以便更好地满足不同层次用户的不同层次的、复杂的知识/概念查询需求.
上面的两个联通算法没有考虑概念之间的联通强度.
而在实际问题中,给定两个概念,就对应两个概念本体.
在概念本体中,两个概念之间可能存在多个直接关系.
所以,有必要考虑概念之间的联通强度.
给定两个概念C,和C2,假定它们之间有N个直接关系,则称从C,到Q的联通强度为N,在联通算法中,把从C,到C2的N个直接关系抽象成一条有向边,并把N作为该边的联通权重.
由上面分析,给定两个概念,它们之间可能存在多个联通算法.
如何找到最强的联通这是一个很有意义的问题.
为此,我们设计了最强联通算法,该算法的思想类似于图论中的参考文献冯东辉,曹存根.
知识界面在NKI中的应用.
计算机工程与应用,2000(17):115-118HefleyWE.
IntelligentUserInterface.
ACM0.
89791-557-7/92/0012/0003,1992雷玉霞,睦跃飞,曹宝香.
基于本体的属性分析以及概念联通.
计算机科学,2004,31(3):102^-105LuRugian,JinZhi.
FormalOntology;FoundationofDomainKnowledgeSharingandResuing.
JcomputSci&Technol,2002,17(5):535-548GuarinoN,CarraraM,Giaretta.
AnOntologyofMeta-levelCate-gories.
PrinciplesofKnowiedgeRepresentationandReason-ing.
In;Proc.
oftheFourthIntl.
Conf.
190