第4卷第6期 智能系统学报 Vol.4 No.6 2009年12月 CAAI Transactions on Intelligent Systems Dec.2009 doi:10.3969/j.issn.16734785.2009.06.009 一种周期时变马尔可夫室内位置预测模型 王志良，杨溢，杨扬2，张琼 (1.北京科技大学信息工程学院，北京100083：2.北方工业大学信息工程学院，北京100144) 摘要：根据在家庭环境中居住者的行为习惯具有周期性和时变性的特点，设计了一种智能数字家庭环境中的基于 位置信息上下文的周期时变马尔可夫预测模型(PTVMM),用于预测居住者的下一个出现位置（房间）.另外还构建 了一个三维虚拟的智能数字家庭实验仿真环境(virtual smart home)用于模型的仿真对比研究.利用模拟行为数据的 仿真结果表明，和其他的预测模型相比，周期时变马尔可夫位置预测模型具有较小的时间复杂度、较高的预测精度 和较快的预测精度收敛速度，能够在智能数字家庭环境中进行实时、高精度的位置预测。 关键词：马尔可夫模型；位置感知；人工智能；数字家庭 中图分类号：TP31;TP391文献标识码：A文章编号：16734785(2009)06052107 A periodic time-varying Markov model for indoor location prediction WANG Zhi-liang',YANG Yi',YANG Yang'2,ZHANG Qiong' (1.School of Information Engineering,University of Science and Technology Beijing,Beijing 100083,China;2.College of Informa- tion Engineering,North China University of Technology,Beijing 100144,China) Abstract:A location-based time-varying Markov model was designed to predict the next location (or room)of the inhabitants of a smart home environment.The model used periodic characteristics of inhabitant behavior in a three- dimensional simulation environment,or "virtual smart home".This was established in order to simulate and com- pare different predictive models.The simulation results showed the proposed method decreased time complexity,in- creased predictive accuracy and improved convergences rates compared to other models.This method can be used to implement real-time and highly accurate predictions of location in a smart home environment. Keywords:Markov model;location awareness;artificial intelligence;smart homes 在数字家庭环境中，如何能在数字家庭环境中Home12]、MT的Home of Future3)、科罗拉多大学 应用人工智能的方法，让家庭环境能够智能地根据的ACHE[4]、佛罗里达大学移动和普适计算实验室 居住者的生活习惯自动调整到最佳状态，而不需要 的GatorTech Homets)等.但是，由于数字家庭环境本 居住者的主动干预，一直是智能数字家庭领域中的 身的复杂性以及居住者的个体差异性造成了这些原 一个难点、热点问题.目前世界上的很多科研机构都 型系统不可避免地存在对居住者的生活行为认知误 在这个问题上进行了研究，并且富有成果地构建了 差大、计算复杂度高、系统过于庞大、复杂而维护困 实验仿真原型系统.如德州大学惠林顿分校的Ma 难等缺陷.为了解决这些问题，并且从先前的调研工 作得出的假设出发，本文从室内位置感知及预测入 收稿日期：200908-15， 手，提出了一个基于位置信息上下文的周期时变马 基金项目：国家“863”高技术发展计划资助项目(2007AA01ZI60):北京市 重点学科建设资助项目(K100080637). 尔可夫位置预测模型(periodical time-varying Markov 通信作者：杨溢.E-mail:yanyi0(252087@163.com model,PTVMM),并且构建了一个虚拟数字家庭环
·522· 智能系统学报 第4卷 境(virtual smart home)来进行仿真比较研究.经过与 forever MavHome使用的基于LZ78数据无损压缩算法的预 1.2ALZ模型 测模型(LZ78)和基于改进LZ78算法的Active LeZi 虽然LZ78算法能够比较好地用来预测信息， 模型(ALZ)的仿真对比显示，PTVMM具有较小的时 但是却有以下2个缺点： 间复杂度、较高的预测精度和较快的预测精度收敛 1)由于前缀不会一直保持最大长度，因此很可 速度，能够胜任智能数字家庭环境中的实时、高精度 能丢失了字典项边界的信息，而有些边界信息是对 的位置预测。 预测下一个字符很有用的； 2)LZ78算法的最佳预侧精度收敛性比较差 1LZ78模型与ALZ模型 为了改进LZ78算法的以上缺点，Gopalratnam 在家庭环境中，居住者的行为在很大程度上是 和Cook等人提出了基于改进LZ78算法的Active 和所处的位置相关联的.例如，在卧室中只能进行休 LeZi预测算法.其核心思想是使用滑动窗口保留 息等活动而不能洗浴；在书房中只能学习而不能做 LZ78的最大预测长度信息，最大限度地保留字典项 饭等.因此，只要能够准确的预测居住者的下一个出 的边界信息.其计算流程为 现位置（房间），就能在很大程度上知道居住者的下 initial Max LZ len =0 一个行为，从而采取相应的动作.在世界上众多关注 loop wait for next symbol v 位置感知与位置预测的科研项目中，德州大学惠林 f((o.v）in dictionary） 顿分校的MavHome是最具有代表性的一个，其使用 LZ78模型和ALZ模型作为位置预测的基础， 0=0.0 1.1LZ78模型 else MavHome所使用的LZ78模型的基础是数据无 损压缩算法LZ78.LZ78通过对输入缓存的数据进 add(o.v）to dictionary 行预先扫描，并与它维护的字典中的数据进行匹配 update Max_LZ_Len if necessary 来实现这个功能，在找到字典中不能匹配的数据之 w=null 前它扫描进所有的数据，这时它将输出数据在字典 add v to window 中的位置、匹配的长度以及找不到匹配的数据，并且 if(window.Length Max_LZ_Len) 将结果数据添加到字典中6].由于LZ78是基于字 典的数据无损压缩算法，因此可以很方便的用来训 delete window 0 练预测决策树.其计算流程如下山： update frequencies of all possible contexts Loop within window that includes v wait for next symbol v forever if((w.v)in dictionary) 2 PTVMM的提出 2.13点假设 0=0,V 根据前期研究数据的分析结果，提出了以下3 点假设，并将这3点假设作为本文所提出的预测模 else 型的依据： 1)居住者在家庭中的生活行为是按照一定规 add (w.v)to dictionary 律或者习惯进行的： w =null 2)居住者下一时刻出现的位置仅和之前时刻 increment frequency for every possible 出现的位置有关； prefix of phrase 3)居住者的生活规律具有周期性和时变性。 假设1)说明居住者的出现位置长期来看是符
第6期 王志良，等：一种周期时变马尔可夫室内位置预测模型 ·523· 合某种概率分布规律的，这保证了预测是有意义的. 式中：T为时刻选择单位列向量.于是有： 根据假设2)，采用马尔可夫模型作为本文预测模型 P()=PA)IX-1 的基础是合适的.根据假设3)，需要在马尔可夫模 2.4模型参数估计 型的基础上增加周期时变特性 应用上述模型，就需要准确的估计t时刻单步 2.2ALZ存在的缺陷 转移概率P.以下给出了一种估计P的方法.令 由于ALZ预测模型是基于数据无损压缩算法 {X⊙}为t时刻的样本数据集，从该数据集中可以 改进而来，并没有考虑到事件的发生具有时间维度， 算出单步转移数量矩阵 因此如果采用ALZ预测实际数据，根据假设3)就必 TAP f87 然造成不同时间段内的数据规律互相影响和混叠， 思 … 州 这必然会对预测精度造成影响.为了解决这个问题， 提出了基于周期时变马尔可夫过程的室内位置预测 模型(PTVMM). 8 般 f积 2.3周期时变马尔可夫预测模型(PTVMM) 同时可以从F中计算出t时刻单步转移概率矩阵 令S={X1,X2,…,Xn},n∈N*An<o为随机 P的估计 过程o的有限状态空间，并且在t时刻的第n步转 「9 p阳 移概率仅和第n-1步有关，即 9 = 础 9 p0(X/X1,…,X1)=p9(X/X-i), 且 L 8 D( P+D(Xn/X.-1,…,X）= 式中： p(Xn/Xn-1,…,X)= p((X/X-1), ≠0： 则称随机过程ω为1阶周期时变马尔可夫过程，T 为该马尔可夫过程的周期。 0 其他 令在t时刻X-1的状态为j,X到达状态i的 可以证明，P是P的无偏估计 概率（称为t时刻单步转移概率），用P来表示，即 2.5决策规则 P=p(X=i/X.-1=j),如果令i∈[1，n],je 在得到了t时刻第n步状态出现概率向量P [1,n],则P9可以写成矩阵的形式： 后，需要根据一定的规则来决策下一时刻出现的确 「pp8 …p01 切位置.以下给出决策规则： pp …p 令α为显著性水平，而为位置状态置信区间，6为 P a的状态个数，L为判定的下一时刻出现位置，MaxP pS … p 为P中第i大的元素，L(Maxp()为MaP所代表 那么下一状态的出现概率列向量就可以由式(1)表 的位置状态那么判定规则可以表示为 示： P()=p(x-1. (1) 月Maw>=1-a,Zeǜ 式中：X.-,表示在第n-1步系统所在状态的单位列 [L(Max p)L(Maxp()...L(Maxp()] 向量. otherwise fail. 令任意时刻X.1的状态为j,X到达状态i的 概率（称为任意时刻单步转移概率），用P来表 3仿真对比研究 示： 3.1仿真实验环境 PA=[PP…P]. 为了克服建立实际实验环境成本过高并且可控 那么t时刻单步转移概率P,和任意时刻单步转 性较差的问题，同时更专注于预测模型本身，所以采 移概率P存在如下关系： 用了虚拟现实技术，使用微软最新的游戏开发平台 P =PCAUI. XNA Game Studio3.0[8]搭建了一个三维的智能数
·524· 智能系统学报 第4卷 字家庭环境virtual smart home,如图1~2所示 </Location </Locations 图1 Virtual smart home俯视图 图3运动传感器分布图 Fig.1 Virtual smart home vertical view Fig.3 Motion senor map 3.2模拟行为生成 表1是一个上班族一天的作息时间表，根据这 个作息时间表结合生成规则自动生成了若干天（不 包括周末和假期)的数据用于仿真研究。 表1工作日作息时间表 Table 1 Working day schedule 时间 事件 7:00 起床 7:00~7:50 上厕所、洗漱、吃早饭 图2 Virtual smart home内部视图 Fig.2 Virtual smart home inside view 7:50 上班 11:30 下班 Virtual smart home实际上模拟了一个单身汉 11:50~13:00 做饭、吃饭、洗碗 (Agent)在一个智能单身公寓里的生活情形.这个单 身汉可以在这个智能单身公寓里以人工控制或是程 13:00~13:50 午休 序自动行为生成的方式自由地生活].公寓中安装 13:50 上班 在各个房间的虚拟运动传感器（如图3）将感知这个 18:00 下班 单身汉的位置信息，并且记录下来.由于是虚拟传感 18:30-20:00 做饭、吃饭、洗碗 器，因此假定所有的传感器都是理想的，即只能检测 20:00~23:00 洗澡/看电视/学习/上网/阳台乘凉 到自己所属房间的运动信号，而不能和其他房间的 23:00 睡觉 传感器信号相互干扰.由于位置信息产生具有很强 根据之前对都市白领工作日正常生活的调查， 的时序性，而且附加属性也很规范，因此使用XML 参照表1制定了如下模拟行为生成规则： 文档来存储历史位置信息.XML文档的格式为 1)上午至多只有起床、上厕所、洗漱、吃早饭这 Locations 些事件，并且不能交换顺序.如果时间来不及，那么 <Location Start ="timel",End ="time2"> 吃早饭可以忽略 Location1 2)中午至多只能有做饭、吃饭、洗碗、看电视、 </Location 午休这些事件，并且顺序不能交换.如果不能保证有 Location Start="time3",End ="time4"> 40min以上的午休时间，那么可以用看电视代替（午 Location2 休和看电视有且只有一个)· </Location 3)晚上至多只能有做饭、吃饭、洗碗、洗澡、看 … 电视、学习、上网、阳台乘凉、睡觉这些事件.做饭、吃 <Location Start=“time N”,End=“timeN+1”> 饭、洗碗这3个事件必须是前3个必然出现的事件， Location N 其余事件的出现概率满足平均分布.除了洗澡、阳台
第6期 王志良，等：一种周期时变马尔可夫室内位置预测模型 ·525· 乘凉（如果发生）只能发生一次外，其余的事件可以 重复发生。 早上 2222 4)以上所有事件都不能连续发生. 5)所有事件的发生时间起始点和持续时间间 隔样本概率分别满足高斯概率分布（不同事件的“ 晚 和不同) h 3.3模型训练 图6 PTVMM训练生成状态转换图 为了对模型进行横向对比，将使用上述数据分 Fig.6 State transition graph of PTVMM 别训练3个模型，即基于Z78压缩算法的预测模型 3.4仿真对比 (LZ78)、基于改进LZ78算法的Active LeZi预测模 1)3种模型的时间复杂度对比， 型(ALZ)、基于周期时变马尔可夫过程的预测模型 仿真实验环境分别采用了10天(141个事件)、 20天(269个事件)、30天(410个事件)、50天(677 (PTVMM).图4~6显示的是用10天数据训练3种 模型的结果， 个事件)、100天(1346个事件)的模拟数据用于分 别训练3种模型.图7显示了这3种模型分别所需 的计算次数对比、 50 PTVMM 2) s 6 40 之 。LZ7B 8) 30 -ActiveLeZi .150. 20 00R仅a 3 0OO 10 中⊙ 0 0 ⊙ 2 680121416x10 事件数量 3) 图4LZ78模型训练生成决策树 Fig.4 Decision tree of LZ78 based model 图73种模型的时间复杂度分析 Fig.7 Time complexity analysis of the three models 在实际的数字家庭系统中，预测算法应该具有比 ⊙ O8①a ⊙ ▣ 较低的时间复杂度，以满足实时预测的需要.从图7 ⊙中▣⊙。⊙⊙ ⊙中▣包 ⊙中 中可以明显看出，Active LeZi的模型训练时间复杂度 ⊙⊙⊙⊙⊙⊙⊙。⊙⊙⊙ ⊙⊙⊙ 随事件数量的增加呈现指数增长，实时性较差.而 LZ78和PTVMM的模型训练时间复杂度基本和事件 ⊙⊙@ O⊙白⊙ n 数量呈线性关系，增长速度较慢，实时性较好， 白中 ⊙② 中9 2)3种模型的预测精度对比. 8 采用1)中的20天数据来对比3种模型的预测 精度.其中前10天数据用来训练模型，后10天数据 用作预测对比.图8显示的是当8=2，α=0.2时 PTVMM和另外2个模型的预测精度比较.图9显示 的是当6=1，a=0.2时PTVMM和另外2个模型 )万 白⊙ O白⊙⊙ 白⊙ 的预测精度比较.总体上看，PTVMM的预测精度最 n分 高，ALZ次之，LZ78最低.特别是早晨和中午2个时 ⊙白⊙⊙ 白⊙中 白⊙ 段，PTVMM的优势尤为明显.这是因为LZ78和ALZ 6⊙⊙中⊙ ⊙⊙⊙ 模型都是由数据无损压缩算法改进而来，这2种模 白⊙⊙⊙ ó⊙白 b 型把位置数据作为互相连接的字符数据来处理，没 图5ALZ模型训练生成决策树 有时间维度，这就造成了不同时段的预测规律互相 Fig.5 Decision tree of ALZ based model 干扰，导致预测精度降低.而PTVMM加入了周期性 和时变性的思想，对具有周期性的不同时间片内的 上下文信息分别处理，避免了不同时间片间的相互