基于Rough逻辑粒的不确定上下文推理
2011-07-24吕方苏饶文碧徐铁城
吕方苏,饶文碧,徐铁城
(武汉理工大学计算机科学与技术学院,湖北武汉430070)
上下文感知计算[1]是普适计算[2]的核心技术。其上层应用和服务需要利用各传感器所得数据融合出来的高层上下文信息。然而受传感器物理特性限制及环境动态性变化的影响,底层上下文信息常常是不精确、不完备的,从而给上下文的推理带来很大困难。目前对于这类问题的推理方法主要有多值逻辑、概率逻辑、模糊逻辑和贝叶斯网络等。李蕊[3]等利用上下文之间的层次关系提出了一种基于贝叶斯网络的上下文关系的学习算法;GU[4]等利用贝叶斯网络对不确定性进行了推理;马守明[5]等提出了一种基于集对分析的不确定上下文推理方法;易建康[6]对觉察上下文计算的软件支撑环境进行了全面分析和研究。以上各种方法都有其特定的优势,也都存在局限性,比如贝叶斯方法不善于处理模糊信息,集对分析对不完备上下文信息无法处理。因此,需要对不确定上下文的推理进行更加深入的研究。粒计算[7]是研究基于多层次粒结构的思维方式、问题求解方法、信息处理模式及其相关理论、技术和工具的学科。笔者采用 Rough逻辑(rough logic,RL)诱导的粒对不确定上下文信息进行推理,其基本思想是通过对RL公式进行4个层次的粒划分,将每个公式的取值映射到[0,1]区间,完成对不确定上下文信息的推理。
1 Rough逻辑
1.1 RL公式的定义
RL是在信息系统IS=(U,A)上的逻辑。其中原子公式是形如a=v或缩写成av的式子,它被解释为a(x)=v,a∈A为IS上的属性,x∈U为对象,v为属性值。这样可定义RL中的合成公式。
定义1[8]满足以下条件的公式为RL中的合成公式:(1)RL中的一切原子公式都是RL中的公式;(2)设 φ、φ是 RL中的公式,则¬φ,φ∨φ,φ∧φ,φ→φ,φ↔φ 都是 RL中的公式。
(3)凡是有限次重复引用(1)、(2)得到的公式都是RL中的公式。
从该定义可以看出IS中的属性相当于RL公式中的谓词。
1.2 RL公式的真值
信息系统IS=(U,A)上的RL公式F(·)为U上的子集,,其中 ≈IS表示可满足。
定义2[9]设TIu为对公式的赋值符号,则:集合·的基数;为
2 上下文信息系统中的RL粒
2.1 CISR 系统
将上下文信息系统分成3个层次的属性:底层上下文属性、高层上下文属性和服务属性。其中底层上下文属性是指所有传感器属性构成,如存在温度传感器,则“温度”可以作为一个底层上下文属性;高层上下文属性是指通过底层上下文推理得出的上下文信息所构成的属性,如由灯光亮度、人员数量和噪声强度可得知当前空间状态处于“开会”状态,则空间状态可以作为一个高层上下文属性;服务属性的值是系统执行的动作或者服务,如由灯光、时间、门的状态得知当前空间处于“深夜休息状态”,则可以执行关掉空调的动作,这时可以将“空调服务”作为一个服务属性,其取值包括“打开”和“关闭”。每个属性都有其相关的取值范围。
由此可以得出基于RL表示的上下文信息系统的模型CISR(context information system based on rough logic)。
设U为对象集,Al为底层上下文属性集,Au为高层上下文属性集,As为服务属性集,R为RL公式集合,则基于RL表示的上下文信息系统的模型可用如下5元组表示:
2.2 CISR上的RL粒
CISR上的RL粒包含两个部分,一个是粒的
根据上下文信息系统的特性,CISR上推理的主要问题是:U的获取、逻辑粒的生成。
2.3 U 的获取
U所包含的全部对象的个数为K(A1)×K(Ai)×…×K(An),在上下文信息系统中获取U的所有对象是不必要的,也是不切实际的,因此需要选取U的一个样本。笔者采用一种称为虚实体的方案。
由于上下文信息系统中有用信息常常是最近一段时间的上下文信息,因此可以选取与当前时间t最为接近的m个虚实体构成U的子样本Ut,m可以是常量,也可以是与t相关的变量。
2.4 RL粒的生成
为了简化上下文信息系统中RL的论述,需要对CISR中的R做些限制。
在CISR中,若F∈R,则F满足以下条件:
(1)F可表示成式(2)的形式:
式中,LFij和LEi为原子公式。
(2)原子公式av中v可以是变量。为了表示v可以是变量这个特性,引入“(a,b]”、“[a,b]”、“(a,b)”、“[a,b)”和“=”5 个符号,它们的意义与通常的意义相同,v的取值范围就用这些符号来表示,例如 av(3,5)表示3 <v<5。
每个粒的内涵在含有m个虚实体的Ut上讨论。为此,先定义λ-包含运算。
定义3[10]设 F1,F2为给定信息系统上的RL公式,m(F1)至少以λ程度包含于m(F2),其运算∝λ为:
式中:K(·)为集合的元素个数。
设lc为底层上下文属性信息,称lc满足原子公式av,当且仅当lc的置信度为p的区间[lc-Δlc,lc+Δlc],λ -包含于原子公式 av。
一般p>0.9,λ 不小于0.5。如果t时刻某底层上下文属性信息缺失,则将该时刻的上下文属性信息取值记为∞,表示不满足任何原子公式。
设 GF、GCE、GLFi、GLFij、GCEi分别为式(2)中 F、CE、LFi、LFij、CEi对应的粒,则每个粒在 t时刻Ut上的内涵由如下算法确定:
(1)所有粒内涵赋值初始化为零;
(2)如果Utλ-包含于某个底层上下文属性的原子公式,则将该公式对应的粒GLFij的内涵更新为λ;
(3)每个GLFi的内涵更新为其包含的粒的内涵的最大值;
(4)每个GCF的内涵更新为其包含的粒的内涵的最小值;
(5)每个GF的内涵更新为GCF的内涵;
(6)如果GCE的内涵小于GF的内涵,则将GCE的内涵更新为GF的内涵;
(7)如果GCEi的内涵小于GCE的内涵,则将GCEi的内涵更新为GCE的内涵;
(8)重复(3)~(7),直到不再有原子粒内涵发生变化,或者循环次数大于q(q为指定常数)。
2.5 基于RL粒的高层上下文更新和服务调用
假设系统设定r(0≤r<1)为RL公式得以满足的最小阈值,则t时刻虚实体vet上的高层上下文或服务属性值更新为其上内涵最大且大于r的原子粒对应的原子公式的论域,调用相应的服务属性对应的服务,即完成t时刻的高层上下文更新和服务调用。
3 实例验证
3.1 实例
在一个智能实验室中,假设有如下属性:
温度T:范围为-10到50,连续,置信区间为[T.value-1,T.value+1];
人数n:0到20人,离散值;
光亮l:将其映射到0到10,连续,置信区间为[l.value-0.5,l.value+0.5];
门d:0为关状态,1为开状态;
空调ac:0为关状态,1为开状态;
空间状态sp:0为开会状态,1为无人状态,2为工作状态;
门服务ds:0为关门服务,1为开门服务;
空调服务as:0为关闭空调服务,1为打开空调服务;
其中:温度、人数、光亮、门和空调为底层上下文属性;空间状态为高层上下文属性;门服务和空调服务为服务属性。
仅选取以下4条RL公式做实例验证:
假设系统每隔1 min从底层传感器得到一次数据,Ut的基数选择为10,r设为0.7,在时刻 t时,将不精确的数值对应到相应的区间后得到的10个虚实体(属性排列顺序为温度、人数、光亮、门、空调、空间状态、门服务、空调服务,∞为信息缺失)如下:
3.2 验证
按照粒的赋值算法,t时刻每个粒的内涵更新过程如下:
(1)将所有粒的内涵初始化为零;
(2)计算得到 Gd[1]=0.7,Gn[0]=0.7,Gl[0,1]=0.7,Gac[1]=0.8。Gav为 av对应的原子粒,其他原子粒的内涵为零;
(3)完成相应步骤,经计算得到 Gsp[1]=0.7;
(4)因原子公式 sp[1]对应的粒的内涵发生了变化,故从步骤(3)~步骤(7)循环一次得到Gds[0]=0.7,Gas[0]=0.7,再次循环,直至没有粒的内涵发生变化,结束。
更新虚实体后可得:vt10=([24,26],0,[0,1],1,1,1,0,0)。此时系统会调用关门服务和关闭空调服务。
由上述分析可知,基于RL逻辑粒的上下文推理,可以处理一定的模糊不完备上下文信息。如果有新的逻辑规则加入或需要删除、禁用某规则,只需要处理与该规则相应的粒即可,因而具有良好的可扩展性和可维护性。
4 结论
笔者将RL逻辑粒应用到不确定的上下文推理中,提出了一种针对模糊不完备上下文信息的推理算法。实例证明了该方法的可行性。
[1]ANIND K D.Understanding and using context[J].Personal and Ubiquitous Computing Journal,2001,5(1):4-7.
[2]WEISER M.The computer for the twenty-first century[J].Scientific American,1991,265(3):94 -104.
[3]李蕊,李仕伦.面向上下文感知计算的贝叶斯网络结构自学习算法的研究[J].计算机应用研究,2010,27(1):107 -110.
[4]GU T,PUNG H K,ZHANG D Q.A bayesian approach for dealing with uncertain contexts[C]//International Conference on Pervasive Computing.Austria:[s.n.],2004:1-7.
[5]马守明,王汝传,叶宁.基于集对分析的上下文感知不确定性的推理方法[J].南京邮电大学学报:自然科学版,2009,29(1):64 -67.
[6]易建康.觉察上下文计算软件支撑环境研究[D].武汉:武汉理工大学图书馆,2006.
[7]ZADEH L A.Fuzzy logic computing with words[J].IEEE Trans on Fuzzy System,1996,4(1):103 -111.
[8]刘清,刘少辉,郑非.Rough逻辑及其在数据约简中的应用[J].软件学报,2001,12(3):415-419.
[9]刘清.算子Rough逻辑及其归结原理[J].计算机学报,1998,21(5):476 -480.
[10]LIU Q,WANG JY.Semantic analysis of rough logical formulas based on granular computing[C]//The 2006 IEEE International Conference on Granular Computing.Beijing:[s.n.],2006:393 -396.