东北大学学报:自然科学版  2016, Vol. 37 Issue (9): 1259-1263  
0

引用本文 [复制中英文]

程海涛, 马宗民, 严丽, 张富. 一种模糊时空描述逻辑F-ALCT(Dfst)[J]. 东北大学学报:自然科学版, 2016, 37(9): 1259-1263.
[复制中文]
CHENG Hai-tao , MA Zong-min , YAN Li , ZHANG Fu . A Fuzzy Spatio-Temporal Description Logic F-ALCT(Dfst)[J]. Journal Of Northeastern University Nature Science, 2016, 37(9): 1259-1263. DOI: 10.3969/j.issn.1005-3026.2016.09.010.
[复制英文]

基金项目

国家自然科学基金资助项目(61370075); 教育部新世纪优秀人才支持计划项目(NCET-05-0288)

作者简介

程海涛(1986-),男,河南光山人,东北大学博士研究生;
马宗民(1965-),男,山东金乡人,东北大学教授,博士生导师。

文章历史

收稿日期: 2015-07-20
一种模糊时空描述逻辑F-ALCT(Dfst)
程海涛1, 马宗民1, 严丽2, 张富1    
1.东北大学 计算机科学与工程学院, 辽宁 沈阳 110819;
2.东北大学 软件学院, 辽宁 沈阳 110819
摘要: 为了实现语义Web中模糊时空知识的表示与推理,提出了一种支持模糊时空具体域的模糊描述逻辑F-ALCT(Dfst).首先,构建了包含模糊时空区域及其时空拓扑谓词的模糊时空具体域Dfst,给出了两个模糊时空区域之间的拓扑关系模糊度的计算方法.然后,将Dfst和时态操作符引入到模糊描述逻辑Fuzzy-ALC中,构建出一种新的模糊描述逻辑F-ALCT(Dfst),并定义了其语法、语义和知识库.最后,给出了一个F-ALCT(Dfst)的知识库实例.F-ALCT(Dfst)有效地实现了语义Web中模糊时空知识的表示.
关键词语义Web    模糊描述逻辑    模糊时空区域    拓扑谓词    具体域    模糊时空描述逻辑    
A Fuzzy Spatio-Temporal Description Logic F-ALCT(Dfst)
CHENG Hai-tao1, MA Zong-min1, YAN Li2, ZHANG Fu1    
1.School of Computer Science & Engineering, Northeastern University, Shenyang 110819, China;
2.School of Software, Northeastern University, Shenyang 110819, China
Corresponding author: CHENG Hai-tao, E-mail:haitaoneu@126.com
Abstract: In order to achieve representation and reasoning of fuzzy spatio-temporal knowledge in semantic Web, a fuzzy description logic F-ALCT(Dfst) supporting fuzzy spatio-temporal concrete domain was proposed. Firstly, a fuzzy spatio-temporal concrete domain Dfst containing fuzzy spatio-temporal regions and their topological predicates was constructed. And the quantitative computation method of fuzzy topological relationships between fuzzy spatio-temporal regions was presented. Then, the concrete domain Dfst and temporal operators were introduced to fuzzy description logic Fuzzy-ALC, and a new fuzzy spatio-temporal description logic, called F-ALCT(Dfst), was proposed. Furthermore, a formal definition of syntax, semantics and knowledge base of the F-ALCT(Dfst) was presented. Finally, an example of F-ALCT(Dfst) knowledge base was given. The F-ALCT(Dfst) effectively realizes the representation of fuzzy spatio-temporal knowledge in semantic Web.
Key Words: semantic Web    fuzzy description logic    fuzzy spatio-temporal regions    topological predicates    concrete domain    fuzzy spatio-temporal description logic    

当前,很多应用领域都涉及到时空信息[1],例如,地理信息系统、时空数据库、动态社交网络以及环境气象监测系统.随着时空应用需求的不断扩大,对时空知识的管理便成为一个很重要的研究方向.由此产生了与时空知识管理技术相关的研究问题,包括时空知识的表示、推理和检索等[2].

然而,在实际应用中存在着大量的不精确和不确定时空知识,一些时态信息、空间对象的位置信息以及空间拓扑关系等都存在模糊性[3].随着模糊时空知识的出现,模糊时空知识的表示已经成为当前机器人视觉、环境监测和地理信息系统等领域的研究热点问题之一[4].

近年来,随着语义Web的发展,大量模糊时空知识及其相关的应用被纳入到语义Web中.而描述逻辑(DL)作为语义Web对知识表示和推理的逻辑基础,在人工智能等领域中已经得到了广泛应用[5].如何扩展描述逻辑以实现模糊时空知识的表示与推理是当前亟需解决的问题.

当前,为了表示和推理语义Web中的空间知识和模糊空间知识,已经有大量的工作致力于经典(模糊)空间描述逻辑的研究.针对语义Web中空间知识的处理,许多研究人员对ALC进行扩展,提出了一系列空间描述逻辑,例如,ALCRP(D)[5],ALCRP3(D)[6]和ALC(Drcc)[7]等.针对语义Web中模糊空间知识表示,Straccia等提出了支持空间具体域的模糊空间描述逻辑Fuzzy-ALC(D)[8].然而,上述的研究只能处理空间和模糊空间知识,不能表示和推理实际应用中的模糊时空知识.

为此,本文提出了一种支持模糊时空知识表示和推理的描述逻辑F-ALCT(Dfst).具体的思路是:首先,定义了由模糊时空区域及其拓扑谓词组成的模糊时空具体域Dfst.然后,将模糊时空具体域Dfst和时态算子◇*(sometime in the future)与□*(always in the future)引入到模糊描述逻辑Fuzzy-ALC[9]中,构建出一种新的模糊描述逻辑F-ALCT(Dfst),并给出其语法、语义以及知识库表示的形式化定义;最后,通过一个知识库实例来展示F-ALCT(Dfst)对模糊时空知识的表示能力以及在语义图像检索方面的应用.

1 模糊时空具体域Dfst

为了构建模糊时空描述逻辑F-ALCT(Dfst),需要定义模糊时空具体域Dfst.基于文献[9]对模糊具体域的描述,本文给出了Dfst的形式化定义.

定义1 模糊时空具体域Dfst是一个二元组Dfst=(ΔDD),其中:

1) ΔD是模糊时空区域的集合;

2) φD是模糊时空区域之间的二元模糊时空谓词的集合.

下面将对Dfst中所包含的模糊时空区域和二元模糊时空谓词进行详细阐述.

1.1 模糊时空区域

根据文献[1]可知,α-截(α-cut level)区域可以用来近似地估计区域的不确定边界.由于本文需要得到模糊区域间的定量拓扑关系,所以选择α-截区域去估计模糊区域.Aαi是以隶属度等于αi的所有点边界组成的二维区域,即Aαi={(x,y)∈IR2 |μA(x,y)≥αi}.其中,IR2表示平面的二维空间,xy分别表示模糊区域Ax轴和y轴坐标点的集合,μA(x,y)表示模糊区域A的隶属函数.假设存在隶属度的关系是:1=α1>α2>…>αn>αn+1=0,那么它们所对应的α-截区域的关系是:.图 1给出了模糊区域的图形化表示.

图 1 模糊区域的图形化表示 Fig.1 Graphical representation of fuzzy region

在上述模糊区域概念的基础上,本文进一步给出了模糊时空区域的形式化定义.

定义2 假设T是在时间流上的离散时间点或时间区间的集合,A是模糊区域的集合,那么模糊时空区域O可以定义为:O=<ti,ai,其中,ti∈T,aiA,i=1,2,…,n.

1.2 模糊时空谓词

1) 模糊空间拓扑谓词.模糊区域的边界存在着不确定性和模糊性,从而导致2个模糊区域之间的拓扑关系也存在着模糊性.下面将描述如何定量地计算拓扑关系模糊度.

依据文献[1]中提到的基本概率赋值函数m(Aαi),将其引入到模糊区域A的每一个α-截区域Aαi中,并给出了m(Aαi)=αi-αi+1的定义(1 ≤i≤n).2个模糊区域间的拓扑关系模糊度计算公式表示如下:

(1)

其中:δf(A,B)表示模糊区域AB之间的8种拓扑谓词f的模糊度,其值介于0到1之间;δc(Aαi,Bαj)表示AB的两个α-截集AαiBαj间的基本拓扑谓词c的值,其值只能取0或者1;mn分别表示AB所取的α-截区域个数.

2) 模糊时空拓扑谓词.模糊时空谓词是模糊时空区域的一个重要属性.在定义2的基础上,进一步给出了Dfst中模糊时空谓词的定义.

定义3 假设T是拓扑关系的有效时间集合,OAOBT时间上的2个模糊区域.模糊时空谓词是形如p(OA,OB,t)的三元组,其中,t∈T,p∈{disjoint,meet,contains,inside,equal,overlap,covers,coverredby}.对于每个时间点t,则有模糊时空谓词p的模糊度:δp(OA,OB,t)=δp(A,B),其中,δp(A,B)∈[0, 1]可由公式(1)计算出.

下面通过1个实例来说明2个模糊时空区域间拓扑关系模糊度的计算.假设2015年6月1日2个云团AB是模糊时空区域,如图 2所示.假设,2个区域取了5个相同的α-截集区域,其边界隶属度分别为α1=1.0,α2=0.8,α3=0.5,α4=0.2,α5=0.

图 2 模糊时空区域AB的拓扑关系图 Fig.2 Topological relationship between fuzzy spatio-temporal regions A and B

本文用矩阵的形式表示α-截集AαiBαj间拓扑关系值,如下所示(矩阵中的元素只能取0或1):

利用公式(1)和上述的矩阵数值,AB之间的拓扑关系Disjoint模糊度的计算结果为

因此,2015年6月1日,大气层中的云团AB处于相离(Disjoint)关系的程度为0.84.

2 F-ALCT(Dfst)的语法、语义以及知识库表示

本节将从语法、语义和知识库三个方面来描述模糊时空描述逻辑F-ALCT(Dfst).

2.1 F-ALCT(Dfst)语法

定义4给出了F-ALCT(Dfst)的语法.

定义4 假设NC,NR,NT,NINO分别是F-ALCT(Dfst)中不相交概念名、抽象角色名、具体角色名、个体实例名和时空区域的集合;RNR叫做抽象角色,T∈NT叫做具体角色,◇*表示未来的某个时间点(sometime in the future),□*表示未来的所有的时间点(always in the future).与Fuzzy-ALC[9]的语法相类似,F-ALCT(Dfst)的概念是由以下语法定义:

其中:⊥和⊥分别是顶概念和底概念;CD是两个任意概念;AC中的原子概念;Dfst是模糊时空具体域;pp1p2表示模糊时空谓词.

2.2 F-ALCT(Dfst)语义

F-ALCT(Dfst)语义包括两个部分,一部分是对模糊时空具体域Dfst的语义解释,另一部分是对定义4中语法的语义解释.这两部分的解释都是建立在Zadeh[10]提出的模糊集的基础上的.首先,给出F-ALCT(Dfst)中Dfst的语义解释.

定义5 假设T是有序的时间点集合.模糊时空具体域Dfst的语义是由模糊解释J给出的.对于任意的时间点t∈TJ将时空拓扑谓词p解释为pJ(AJ,BJ,tJ)→ [0, 1],p∈{disjoint,contains,inside,equal,overlap,covers,meet,coverredby},解释J还被扩展到其他的时空谓词表达式,即

然后,将Dfst的解释引入到Fuzzy-ALC的语义解释中,就得到了F-ALCT(Dfst)语义解释.

定义6 F-ALCT(Dfst)语义是由模糊解释I=(ΔID,J,·I)给出.在时间点t的解释 I(t)=(ΔID,J,·I(t)).其中:ΔI是由模糊抽象域中个体实例组成的非空集合;ΔD是由模糊时空具体域中模糊时空区域组成的非空集合,并且与ΔI是互不相交的;J是对Dfst中时空谓词的模糊解释;·I(t)是模糊解释函数.对于任意的时间点t,模糊解释函数·I(t)将:

1) 任意的抽象概念CNC映射为一个隶属函数CI(t):ΔI →[0, 1];

2) 抽象实例a ∈NI映射为ΔI的一个元素aI(t)ΔI.如果a b,那么aI(t)bI(t)

3) 模糊时空区域o∈NO映射为ΔD的一个元素oI(t)ΔD,满足oI(t)=o

4) 抽象角色R∈NR映射为一个隶属函数RI(t): ΔI×ΔI → [0, 1];

5) 具体角色T∈NT映射为一个隶属函数TI(t) : ΔI ×ΔD→ [0, 1];

6) 具体特征f∈NT映射为一个隶属函数fI(t): ΔI×ΔD →{0,1},对于每个个体实例a∈NI,都有唯一的模糊时空区域o∈NO,使得fI(t)(a,o)被定义.

此外,模糊函数·I(t)还可以扩展到任意的概念,其语义解释如下(假设u,v∈ΔI,r1,r2∈ΔD):

2.3 F-ALCT(Dfst)知识库

F-ALCT(Dfst)知识库Σ是由模糊TBox T和模糊ABox A两个部分组成.下面给出这两个部分的定义.

定义7 模糊TBox T:模糊TBox T是有限个模糊术语公理集,包含公理<CD>和等价公理<C≡D>.从语义的角度来解释,一个模糊解释I(t)满足公理CD成立,当且仅当对于任意的d∈ΔI和任意的时间点t, 有CI(t)(d)DI(t)(d);一个模糊解释I(t)满足公理C≡D成立,当且仅当对于任意的d∈ΔI和任意的时间点t,有CI(t)(d)=DI(t)(d).也就是说,一个模糊解释I(t)满足模糊TBoxT成立,当且仅当I(t)满足所有的概念公理.

定义8 模糊ABox A:模糊ABox A是有限的模糊断言集合,以的形式表示.其中,α是形如<a:C>,<(a,b):R>,<(a,o):T>和<(o1,o2,):p>的模糊断言,∈{≥,>,≤,<},k∈[0, 1],t表示任意的时间点.模糊ABox A包括以下4种模糊断言类型:

1) 模糊概念断言<a:Ck,t>:该断言表示在任意的时间点t,抽象个体实例a是概念C的一个实例,并且具有隶属度为k.一个模糊解释I(t)满足该断言成立,当且仅当CI(t)(d)k.

2) 模糊抽象角色断言<(a,b):Rk,t>:该断言表示在时间点t,两个抽象个体实例ab之间存在抽象角色关系R,且该关系具有隶属度为k.一个模糊解释I(t)满足该断言成立,当且仅当R I(t)(a,b)k.

3) 模糊具体角色断言<(a,o):Tk,t>:该断言表示在时间点t,抽象个体实例a和具体域中模糊时空区域o之间存在具体角色关系T,且具有隶属度为k.一个模糊解释I(t)满足该断言成立,当且仅当TI(t)(a,o)k.

4) 模糊时空谓词断言<(o1,o2,): pk,t>:该断言表示在时间点t,2个模糊时空区域o1o2之间存在模糊时空谓词关系p,且具有隶属度为k.一个模糊解释I(t)满足该断言成立,当且仅当p I(t)( o1,o2) k.

如果一个模糊解释I(t)满足模糊ABox A成立,当且仅当I(t)满足A的所有模糊断言集合.

综上所述,一个模糊解释I(t)满足知识库Σ成立,当且仅当I(t)满足所有的模糊ABox A和模糊TBox T.

一个F-ALCT(Dfst)知识库Σ蕴含模糊断言α(记着Σ|=α)当且仅当Σ的每一个模型也满足α.给定一个知识库Σ和模糊断言α,那么相对于Σ,一个断言α的最大下确界(记为glb(Σ,α))表示为

(2)

相对于Σ,一个断言的最小上确界(记为lub(Σ,α))表示为

(3)
3 知识库实例

本文以某个地区的天气变化为例来说明模糊时空描述逻辑的知识表示能力及其在实例检索方面的应用.

具体描述为:假设2张卫星云图(SatelliteMap)i1i2,分别是5月1日8:00am(t1)和5月1日9:00am(t2)的快照.在t1t2时刻,一个雾区(fog)r1和风区(wind)r2处于模糊相离(Disjoint)的时空拓扑关系.随着时间的变化,2个区域的Disjoint关系所具有的隶属度不同.模糊抽象域到模糊时空具体域的映射如图 3所示.

图 3 从模糊抽象域到模糊时空具体域的映射实例图 Fig.3 Mapping from fuzzy abstract domain to fuzzy spatio-temporal concrete domain

本实例假设2个模糊时空区域r1r2被划分为5个相同的α-截集区域,利用式(1),可以计算出在t1时刻,2个区域的Disjoint关系隶属度为0.92;在t2时刻,其隶属度为0.84.下面给出模糊时空描述逻辑的知识表示以及语义检索应用.

1)知识表示.在t1时刻,模糊时空纯断言知识库Σt1={

t2时刻,模糊时空纯断言知识Σt2={

2)图像检索.本文假设需要检索雾区和风区处于相离关系的图像.通过定义一个查询概念C对知识库Σt1Σt2进行实例查询,其中概念C被定义如下:

利用式(2),可以计算出

因此,在对整个卫星云图图像检索之后,检索结果的排序是:图像i2排在i1的前面.

4 结语

本文提出了一种模糊时空描述逻辑F-ALCT(Dfst),并给出了F-ALCT(Dfst)的语法、语义和知识库表示的形式化定义.最后,通过具体的知识库实例展示了F-ALCT(Dfst)的知识表示能力以及在语义检索方面的应用.后续的研究工作是在F-ALCT(Dfst)的基础上,研究其推理机的实现.

参考文献
[1] Sözer A, Yazlcl A, Ouztüzün H, et al. Modeling and querying fuzzy spatiotemporal databases[J]. Information Sciences , 2008, 178 (19) : 3665–3682. DOI:10.1016/j.ins.2008.05.034 (0)
[2] Pierkot C, Andrés S, Faure J F, et al. Formalizing spatiotemporal knowledge in remote sensing applications to improve image interpretation[J]. Journal of Spatial Information Science , 2013, 7 (1) : 77–98. (0)
[3] Bai L,Yan L,Ma Z M.Modeling topological relations between fuzzy spatiotemporal regions over time[C]//Proceedings of 2012 IEEE International Conference on Fuzzy Systems.Brisbane,2012:1-8. (0)
[4] Ribaric S, Hrkac T. A model of fuzzy spatio-temporal knowledge representation and reasoning based on high-level Petri nets[J]. Information Systems , 2012, 37 (3) : 238–256. DOI:10.1016/j.is.2011.09.010 (0)
[5] Haarslev V, Lutz C, Möller R. A description logic with concrete domains and a role-forming predicate operator[J]. Journal of Logic and Computation , 1999, 9 (3) : 351–384. DOI:10.1093/logcom/9.3.351 (0)
[6] Kaplunova A,HaarslevV,Möller R.Adding ternary complex roles to ALCRP(D)[C]//Proceedings of the International Workshop on Description Logics.Toulouse,2002:45-52. (0)
[7] Weasel M.Some practical issues in building a hybrid deductive geographic information system with a DL-component[C]//Proceedings of the 10th International Workshop on Knowledge Representation Meets Databases.Hamburg,2003. (0)
[8] Straccia U.Towards spatial reasoning in fuzzy description logics[C]//IEEE International Conference on Fuzzy Systems.Jeju Island,2009:512-517. (0)
[9] Straccia U.Description logics with fuzzy concrete domains[C]//Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence.Edinburgh,2005:559-567. (0)
[10] Zadeh L A. Fuzzy sets[J]. Information Control , 1965, 8 (3) : 338–353. DOI:10.1016/S0019-9958(65)90241-X (0)