2.东北大学 软件学院, 辽宁 沈阳 110819
2.School of Software, Northeastern University, Shenyang 110819, China
当前,很多应用领域都涉及到时空信息[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=(ΔD,φD),其中:
1) ΔD是模糊时空区域的集合;
2) φD是模糊时空区域之间的二元模糊时空谓词的集合.
下面将对Dfst中所包含的模糊时空区域和二元模糊时空谓词进行详细阐述.
1.1 模糊时空区域
根据文献[1]可知,α-截(α-cut level)区域可以用来近似地估计区域的不确定边界.由于本文需要得到模糊区域间的定量拓扑关系,所以选择α-截区域去估计模糊区域.Aαi是以隶属度等于αi的所有点边界组成的二维区域,即Aαi={(x,y)∈IR2 |μA(x,y)≥αi}.其中,IR2表示平面的二维空间,x和y分别表示模糊区域A的x轴和y轴坐标点的集合,μA(x,y)表示模糊区域A的隶属函数.假设存在隶属度的关系是:1=α1>α2>…>αn>αn+1=0,那么它们所对应的α-截区域的关系是:
在上述模糊区域概念的基础上,本文进一步给出了模糊时空区域的形式化定义.
定义2 假设T是在时间流上的离散时间点或时间区间的集合,A是模糊区域的集合,那么模糊时空区域O可以定义为:O=<ti,ai>,其中,ti∈T,ai∈A,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)表示模糊区域A和B之间的8种拓扑谓词f的模糊度,其值介于0到1之间;δc(Aαi,Bαj)表示A和B的两个α-截集Aαi和Bαj间的基本拓扑谓词c的值,其值只能取0或者1;m和n分别表示A和B所取的α-截区域个数.
2) 模糊时空拓扑谓词.模糊时空谓词是模糊时空区域的一个重要属性.在定义2的基础上,进一步给出了Dfst中模糊时空谓词的定义.
定义3 假设T是拓扑关系的有效时间集合,OA和OB是T时间上的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个云团A和B是模糊时空区域,如图 2所示.假设,2个区域取了5个相同的α-截集区域,其边界隶属度分别为α1=1.0,α2=0.8,α3=0.5,α4=0.2,α5=0.
本文用矩阵的形式表示α-截集Aαi和Bαj间拓扑关系值,如下所示(矩阵中的元素只能取0或1):
利用公式(1)和上述的矩阵数值,A和B之间的拓扑关系Disjoint模糊度的计算结果为
因此,2015年6月1日,大气层中的云团A与B处于相离(Disjoint)关系的程度为0.84.
2 F-ALCT(Dfst)的语法、语义以及知识库表示本节将从语法、语义和知识库三个方面来描述模糊时空描述逻辑F-ALCT(Dfst).
2.1 F-ALCT(Dfst)语法定义4给出了F-ALCT(Dfst)的语法.
定义4 假设NC,NR,NT,NI,NO分别是F-ALCT(Dfst)中不相交概念名、抽象角色名、具体角色名、个体实例名和时空区域的集合;R∈NR叫做抽象角色,T∈NT叫做具体角色,◇*表示未来的某个时间点(sometime in the future),□*表示未来的所有的时间点(always in the future).与Fuzzy-ALC[9]的语法相类似,F-ALCT(Dfst)的概念是由以下语法定义:
其中:⊥和⊥分别是顶概念和底概念;C和D是两个任意概念;A是C中的原子概念;Dfst是模糊时空具体域;p,p1和p2表示模糊时空谓词.
2.2 F-ALCT(Dfst)语义F-ALCT(Dfst)语义包括两个部分,一部分是对模糊时空具体域Dfst的语义解释,另一部分是对定义4中语法的语义解释.这两部分的解释都是建立在Zadeh[10]提出的模糊集的基础上的.首先,给出F-ALCT(Dfst)中Dfst的语义解释.
定义5 假设T是有序的时间点集合.模糊时空具体域Dfst的语义是由模糊解释J给出的.对于任意的时间点t∈T,J将时空拓扑谓词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=(ΔI,ΔD,J,·I)给出.在时间点t的解释 I(t)=(ΔI,ΔD,J,·I(t)).其中:ΔI是由模糊抽象域中个体实例组成的非空集合;ΔD是由模糊时空具体域中模糊时空区域组成的非空集合,并且与ΔI是互不相交的;J是对Dfst中时空谓词的模糊解释;·I(t)是模糊解释函数.对于任意的时间点t,模糊解释函数·I(t)将:
1) 任意的抽象概念C∈NC映射为一个隶属函数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):
F-ALCT(Dfst)知识库Σ是由模糊TBox T和模糊ABox A两个部分组成.下面给出这两个部分的定义.
定义7 模糊TBox T:模糊TBox T是有限个模糊术语公理集,包含公理<C
定义8 模糊ABox A:模糊ABox A是有限的模糊断言集合,以
1) 模糊概念断言<a:C
2) 模糊抽象角色断言<(a,b):R
3) 模糊具体角色断言<(a,o):T
4) 模糊时空谓词断言<(o1,o2,): p
如果一个模糊解释I(t)满足模糊ABox A成立,当且仅当I(t)满足A的所有模糊断言集合.
综上所述,一个模糊解释I(t)满足知识库Σ成立,当且仅当I(t)满足所有的模糊ABox A和模糊TBox T.
一个F-ALCT(Dfst)知识库Σ蕴含模糊断言α(记着Σ|=α)当且仅当Σ的每一个模型也满足α.给定一个知识库Σ和模糊断言α,那么相对于Σ,一个断言α的最大下确界(记为glb(Σ,α))表示为
(2) |
相对于Σ,一个断言的最小上确界(记为lub(Σ,α))表示为
(3) |
本文以某个地区的天气变化为例来说明模糊时空描述逻辑的知识表示能力及其在实例检索方面的应用.
具体描述为:假设2张卫星云图(SatelliteMap)i1和i2,分别是5月1日8:00am(t1)和5月1日9:00am(t2)的快照.在t1和t2时刻,一个雾区(fog)r1和风区(wind)r2处于模糊相离(Disjoint)的时空拓扑关系.随着时间的变化,2个区域的Disjoint关系所具有的隶属度不同.模糊抽象域到模糊时空具体域的映射如图 3所示.
本实例假设2个模糊时空区域r1和r2被划分为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, Ouztü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) |