第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=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所示 吃早饭可以忽略 Location1 2)中午至多只能有做饭、吃饭、洗碗、看电视、 40min以上的午休时间，那么可以用看电视代替（午 Location2 休和看电视有且只有一个)· 饭、洗碗这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加入了周期性 和时变性的思想，对具有周期性的不同时间片内的 上下文信息分别处理，避免了不同时间片间的相互
·526 智能系统学报 第4卷 干扰，提高了预测的精度 K步相关联，因此抗随机扰动的能力较强，因此预测 1.0-PTYMM-ActiveLeZi LZ7B 精度的方差较小.相反地，PTVMM本质上为1阶的 0.8 马尔可夫预测器，这就造成了PTVMM在预测时将 0.6 受到更大的随机噪声扰动的干扰，表现为预测精度 04 方差较大 0.2 10 0 尽晨 巾午 晚L全天平均 8 时问段 6 图8预测精度比较(PTVMM.8=1,a=0.2) 4 Fig.8 Comparison of prediction accuracy (PTVMM=1, 2 a=0.2) 0 Lz78 ActiveLeZi PTVMM 1.0PTVMM m ActiveLeZi LZ7B 08 图11预测精度方差比较(PTVMM.8=1,a=0.2) 0.6 Fig.11 Comparison of variance of prediction accuracy 0.4 (PTVMM6=1,a=0.2) 0.2 4结束语 0 早晨 巾午 晚上 全天平均 时间段 通过在仿真环境(virtual smart home)中的仿真 图9预测精度比较(PTVMM8=2,a=0.2) 研究显示，和以数据无损压缩算法为基础的Z78 Fig.9 Comparison of prediction accuracy (PTVMM 8 =2, 和ALZ模型相比，由于加入了时间维度上的周期性 a=0.2) 和时变性的特点，使得PTVMM具有较小的时间复 3)3种模型的长期预测精度趋势比较 杂度、较高的预测精度以及较快的预测精度收敛性， 图10显示了模型训练数据量从0~100天时3 能够比较好地在智能数字家庭环境中进行实时的、 种预测模型的平均预测精度变化趋势.从图中可以 高精度的居住者位置预测，为智能家庭的环境自动 看出3种预测模型都具有较好的精度收敛性，基本 调整行为提供决策依据.但是，仿真研究中依然暴露 在10天左右的训练数据量时就可以收敛到最大预 出了PTVMM的一些缺点，比如受随机噪声扰动干 测精度附近.总体上看，在训练样本足够大时(10 扰过大造成长期预测精度方差过大的问题，所以如 天)，LZ78的预测精度最低，在54%附近；ALZ精度 何改进PTVMM的预测精度偏差，是下一阶段的研 较高，在65%左右；PTVMM比ALZ稍高，在67%上 究方向工作， 下 参考文献： 0.9 0.8 型 0.7 锐特气A喻A。 [1]GOPALRATNAM K,COOK D J.Online sequential predic- 0.6 帆e,ahr 0.5 薹 0-LZ78 tion via incremental parsing:the active LeZi algorithm[J]. 0.4 。ALZ IEEE Intelligent Systems,2007,22(1):52-58. 0.3 0.2 PTVMM [2]ROY A,DAS S K,BASU K.A predictive framework for lo- 0 cation-aware resource management in smart homes J]. 20 406080100120 训练天数天 IEEE Transaction on Mobile Computing,2007,6(11): 1270-1283. 图10长期预测趋势比较(PTVMM8=1,a=0.2) [3]INTILLE S S.Designing a home of the future J].IEEE Fig.10 Comparison of long-term forecast trend (PTVMM Pervasive Computing,2002,1(2):80-86. 6=1,=0.2） [4]MOZER M.The neural network house:an environment that 4)3种模型的长期预测精度方差比较 adapts to its inhabitants[C]//Proc AAAI Spring Symp on 图11显示了3种模型在预测精度方差方面的 Intelligent Environments.Palo Alto,USA,1998:110-114. 表现.ALZ表现最好，方差只有1.36；LZ78表现次 [5]HELAL S,MANN W,EI-ZZABADANI H.The gator tech 之，方差为2.12；PTVMM在方差的表现上差强人 smart house:a programmable pervasive space[J].IEEE 意，为8.69.这是因为，在本质上说，LZ78和ALZ属 Computer,2005,38(3):50-60 于K阶马尔可夫预测器]，由于每一次预测都与前 [6]ZIV J,LEMPEL A.Compression of individual sequences via
第6期 王志良，等：一种周期时变马尔可夫室内位置预测模型 ·527… variable-rate coding[J].IEEE Transaction on Information 作者简介： Theory,1978,24(5):530-536. 王志良，男，1956年生，教授，博士 [7]CHING W K,FUNG E S,NG M K.A higher-order Markov 生导师，北京科技大学信息工程学院电 model for the Newsboy's problem[J].Joumal of the Opera- 子信息系主任，中国人工智能学会理 tional Research Society,2003,54(2):291-298. 事.主要研究方向为人工心理与情感计 [8]CAWOOD S,MCGEE P.Microsoft XNA game studio crea- 算、智能机器人、和谐人机交互，发表学 tor's guide[M ]New York,USA:MeGraw-Hill Inc, 术论文60余篇，其中被SCI、EI、ISTP检 2007:51-109. 索30余篇，出版学术专著2部，合著2部. [9]黄海平，王汝传，孙力娟，蒋颢.基于Agent和无线传感 杨溢，男，1984年生，博士研究 器网络的普适计算情景感知模型[J].南京邮电大学学 生，主要研究方向为数字家庭、人工智 报：自然科学版，2008,28(2)，74-79. 能与计算机网络。 HUANG Haiping,WANG Ruchuan,SUN Lijuan,JIANG Hao.Pervasive computing scene apperceive model based on Agent wireless sensor networks[J].Joumal of Nanjing U- niversity of Posts and Telecommunications:Natrual Science, 2008,28(2),74-79. 杨扬，男，1980年生，博士研究 [10]FEDER M,MERHAV N,GUTMAN M.Universal predic- 生，主要研究方向为人机交互技术，数 tion of individual sequences[J].IEEE Transaction on In- 字家庭， formation Theory,1992,38(4):1265-1270. 2010生命系统建模与仿真国际会议和2010可持续 能源与环境中的智能计算国际会议 2010 International Conference on Life System Modeling and Simulation 2010 International Conference on Intelligent Computing for Sustainable Energy and Environment 背景介绍： 2010生命系统建模与仿真国际会议(LSMS2010)和2010可持续能源与环境中的智能计算国际会议(ICSEE 2010)将于2010年9月17~20日在中国无锡举行.LSMS-ICSEE2010是面向全世界生命系统建模与仿真、可持续 能源与环境智能计算理论、方法和应用等相关研究领域科技人员和学者的国际学术会议.会议将以大会主题发 言、分组讨论、专题研讨以及展板等多种形式来促进研究团体和学者之间的学术交流.会议论文将在Springer的 Lecture Notes in Computer Science和Lecture Notes in Bioinformatics上出版(EI和ISTP收录)，同时，部分高质量论 文将被推荐到SCI期刊发表。 大会议题： A.生命系统建模与仿真中的计算方法和人工智能； B.智能计算及其应用（包括可持续能源与环境）· 会议网站：htp:/www.LSMS-ICSEE-2010.org