（计算机应用技术专业论文）基于路径模式挖掘的个人连续路径预测.pdf

浙江大学硕士学位论文摘要 摘要 随着定位技术的发展以及移动计算的普及，与物体移动路径和位置相关的服 务和产品成为了业界关注的焦点。如新兴的现代智能交通系统( i n t e l l i g e n t t r a n s p o r ts y s t e m ，i t s ) ，利用安装在车辆上的感知器返回车辆的各种信息以帮助交 通调度；又如各种基于位置的服务( l o c a t i o n - b a s e ds e r v i c e s l b s ) ，通过车辆上的 移动设备返回信息，判断车辆的运动状况，实时为车辆的驾驶者提供相关的信息 等服务。这些富于潜力的应用领域激发了学术界对移动对象轨迹的相关研究。 目前与物体移动位置相关的研究工作主要关注于车辆而不是个人。然而在日 常生活中，将个人作为运动单位有着更广阔的应用空间。本文提出了一整套关于 个人连续轨迹挖掘和预测的系统。该系统综合考虑了以下问题：个人运动状态的 多样性，地理定位系统的准确性，个人手持移动设备有限的运算能力，个人移动 路径的私密性，系统的可重用性等。 针对这些问题，本文提出了以下解决方案。首先，移动电话和便携式g p s 接 收器被用作数据采集和处理。运行在移动电话的上的数据采集程序可以依据用户 的运动状况自动调整数据采集的频率。多个数据过滤算法被用来去除原始数据中 的噪声，以得到合理的个人路径信息。其次，本文提出了连续路径模式挖掘算法 ( c r p m ) 。该算法可以容忍各种实际干扰在原始路径中造成的差异，以挖掘出更长 的路径模式。第三，本文提出了一种新颖的c s ( 客户端h i 务器端) 体系构架。 该构架在保证用户路径信息不被泄露的情况下，使得服务器端承受大部分运算压 力，有效地减轻了对个人手持设备的运算压力。第四，本文提出一种基于预测树 的路径预测算法。该算法不仅有效地减轻了实时路径预测的运算量，而且提高了 路径预测的准确度。通过对1 7 名用户提供的真实路径的实验表明，连续路径模 式挖掘算法可以挖掘出比传统序列挖掘算法更长的路径模式，连续路径预测算法 为个人路径的实时预测提供了有效而可靠的解决方案。 关键词g p s ，路径模式，数据挖掘，个人隐私 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t r e c e n t l y , w i t ht h ed e v e l o p m e n to fp o s i t i o n i n ga n dp o p u l a r i t yo fp e r v a s i v ec o m p u t i n g ， t h et r a j e c t o r i e sa n dp o s i t i o n sr e l a t e ds e r v i c e sa n dp r o d u c t sb e c a m et h ef o c u so f i n d u s t r y f o re x a m p l e ，t h em o d e mi n t e l l i g e n tt r a n s p o r ts y s t e m ( i t s ) u t i l i z e dt h e s e n s o rw h i c he q u i p p e do nv e h i c l e st og e ti n f o r m a t i o nf o rt r a n s p o r ts c h e d u l i n g i m p r o v e m e n t a n o t h e re x a m p l ei st h el o c a t i o n b a s e ds e r v i c e s ( l b s ) w h i c hg e td a t a o fv e h i c l e sf r o mp o r t a b l ed e v i c ea n dm a k eu s eo fi tt op r o v i d er e a l - t i m es e r v i c e sf o r t h ed r i v e r s i nt h e s ef i e l d s ，r o u t ep a t t e r n sm i n i n ga n dp r e d i c t i n gf o rm o v i n go b j e c t si s t h ef o u n d a t i o n u n t i ln o w , t h em a j o ro b j e c ti nt h er o u t ea n dp o s i t i o nr e l a t e dr e s e a r c hi st h ev e h i c l e ， n o tt h ep e r s o n h o w e v e r , i nd a i l yl i f e ，c o n s i d e rap e r s o na sam o v i n gu n i ti sm o r e p e r v a s i v et h a nc o n s i d e rav e h i c l ea sam o v i n gu n i t i nt h i sp a p e r , w ep r o p o s e da ne n t i r e s y s t e mf o rp e r s o n a lc o n t i n u o u sr o u t e sm i n i n ga n dp r e d i c t i n g t h es y s t e mt a k e si n t o c o n s i d e r a t i o nt h ef o l l o w i n gi s s u e s ：t h ed i v e r s i t yo fp e r s o n a lm o v i n gs t a t u s ，t h e p r e c i s i o no ft h ep o s i t i o n i n gs y s t e m , t h el i m i t e dc o m p u t i n ga b i l i t yo fp e r s o n a lp o r t a b l e d e v i c e ，t h ep r i v a c yo fp e r s o n a lr o u t e sa n dt h er e u s a b i l i t yo ft h em o d u l e si nt h es y s t e m t oh a n d l et h e s ei s s u e s ，w ep r o p o s e ds e v e r a ln o v e ls o l u t i o n s f i r s t ，m o b i l ep h o n e a n dm i n ig p ss e n s o rw e r eu s e df o rd a t ac o l l e c t i o na n dp r o c e s s i n g ap r o g r a mw h i c h r a no nm o b i l ep h o n ec a nr e c o r dt h eu s e r sm o v i n gs t a t u sa d a p t i v e l y s e v e r a ld a t a f i l t e r sa r eu s e df o rc l e a n i n gd a t aa n dr e m o v et h en o i s e s e c o n d ，w ep r o p o s e dt h e c o n t i n u o u sr o u t ep a t t e r n sm i n i n g ( c r p m ) w h i c hc a nt o l e r a t et h ep r a c t i c a l d i s t u r b a n c ei nr e a lr o u t ed a t aa n de x t r a c tl o n gr o u t ep a t t e r n s t h i r d ，w ed e s i g n e dan e w c l i e n t s e r v e ra r c h i t e c t u r e t l l i sa r c h i t e c t u r ec a nm a k et h es e r v e rc o n d u c t sm o s to f c o m p u t a t i o nw i t h o u tg e ta w a r e n e s s o fu s e r s r e a lr o u t e s ，w h i c hw i l lg r e a t l yr e d u c et h e c o m p u t a t i o n a ll o a d o nt h ep e r s o n a l p o r t a b l ed e v i c e s f o u r t h , w ep r o p o s e d a d e c i s i o n - t r e eb a s e dr o u t e p r e d i c t i n ga l g o r i t h m ，w h i c hc a nn o to n l y r e d u c et h e c o m p u t a t i o n , b u ta l s op r o v i d eh i g l lp r e d i c t i n gp r e c i s i o n a ne v a l u a t i o no v e r17u s e r s s h o wt h a t , c r p mc a ne x t r a c tm u c hl o n g e rr o u t ep a t t e r n st h a nt h et r a d i t i o n a ls e q u e n t i a l 浙江大学硕士学位论文 a b s t r a c t m i n i n ga l g o r i t h m s ，a n do u rp r e d i c t i n ga l g o r i t h mc a np r o v i d er e a lt i m ea n de f f e c t i v e s o l u t i o nf o rp e r s o n a lr o u t ep r e d i c t i o n k e y w o r d s g p s ，r o u t ep a t t e r n s ，d a t am i n i n g ，p e r s o n a lp r i v a c y 浙江大学硕士学位论文 图目录 图目录 图1 1 美国“国家智能交通系统项目规划”整体框架一2 图2 1 个人连续路径预测系统框架1 5 图3 1 描述数据采集系统的有限自动机1 9 图3 2 数据采集系统采集到的真实路径数据样本2 0 图3 3 图3 2 中原始路径经过数据过滤后的结果2 0 图3 4 位移总量过滤器( 左) 和角度过滤器( 右) 的效果2 2 图3 5 每个参与者过滤后的数据点总数占原始数据点总数的百分比2 5 图3 6 每个参与者所记录的路径总数2 6 图3 7 每个参与者的平均路径长度( 位置点数) 2 6 图4 1 原始路径数据点( 左) 和插值补充后的路径数据点( 右) 3 0 图4 21 号参与者和1 7 号参与者的活跃网格区域。3 0 图4 3 当最大区域边长为网格边长两倍时，l 号参与者与1 7 号参与者的活跃 i 噩域31 图4 4 利用活跃区域时间序列抽象真实路径3 2 图4 5 一个参与者的路径样例3 3 图4 6 连续路径模式挖掘算法挖掘出的路径模式3 5 图4 7k m a xr e g _ s i z e 与活跃区域数目的关系3 7 图4 8k i 舶增长时路径模式数量的变化3 8 图4 9k i 眦不同时各个参与者的最长路径模式3 9 图4 1 0k i 呲不同时各个参与者的平均路径模式长度4 0 图4 1 1h 硫不同时1 号参与者路径模式长度分布4 1 图4 1 2h i l i l c 不同时6 号参与者路径模式长度分布。4 1 图4 1 3h 眦不同时9 号参与者路径模式长度分布4 2 图4 1 4k i 眦不同时1 5 号参与者路径模式长度分布4 2 i i i 浙江大学硕士学位论文 图目录 图4 1 5 人工评判第二题结果的统计数据4 3 图4 1 6 人工评判第三题结果的统计数据4 3 图5 1 一个用户活跃区域的样例4 7 图5 2 路径模式p l = 2 ，3 ，4 ) ，p 2 = 1 ，3 ，6 ，7 ) ，p 3 = 1 ，3 ，5 ，8 ，9 ) 所生成的预测树 z 1 8 图5 3 当k 。眦佗擎不同值时连续路径预测系统的单步预测精度5 3 图5 4 基于马尔科夫模型的预测方法、基本连续路径预测算法、5 4 图5 5 输入区域序列长度不同给单步预测带来的影响5 4 图5 6 连续路径预测算法的平均预测长度5 5 图5 7 不同预测方法产生的多步预测结果5 6 图6 1 系统原型客户端实验设备5 7 图6 2 原型系统结构层次图5 8 图6 3 系统原型客户端截图6 0 i v 浙江大学硕士学位论文 表目录 表目录 表3 1 数据过滤器算法结构2 3 表3 2 实验参与者路径信息统计数据2 4 表4 1 个人路径模式挖掘算法结构2 8 表4 2c r p m 中拓展映射算法3 4 表5 1 启发式连续路径预测算法结构51 表6 1 真实路径采集程序主要实现的类5 8 表6 2 个人路径模式挖掘及预测系统主要实现的类5 9 v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得迸江盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 叶泳 签字日期：y 内旷年月归日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝江盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 叶敝聊签名：恬蚤何 签字日期：v 哟艿年6 月i e l签字日期：枷s 年石, e li o 日 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 课题背景 随着地理定位技术的发展和成熟，以及移动计算的兴起，基于路径和地理位 置的应用成为了学术界和工业界，甚至是政府的共同焦点。路径信息和地理信息 作为移动对象的重要属性，可以为很多服务和应用系统的改进提供重要的支持。 将移动对象的路径和位置信息作为系统输入，催生了众多新兴的应用领域。智能 交通系统( i n t e l l i g e n tt r a n s p o r ts y s t e m , i t s ) 和基于位置的服务( l o c a t i o n b a s e d s e r v i c e s l b s ) 是其中最为著名的两个应用领域。 1 1 1 智能交通系统( i t s ) 智能交通系统( i t s ) 作为一种实时、高效、准确的新型交通运输系统目前已 经在欧美等发达国家得到广泛的应用。根据相关报道，应用了智能交通系统后， 可有效提高交通运输效率，使得交通拥挤降低2 0 ，延误损失减少10 2 5 ，车 祸概率降低5 0 8 0 ，油料消耗减少3 0 。 1 9 9 5 年3 月，美国交通部出台了“国家智能交通系统项目规划”【2 7 1 ，明确规定 了智能交通系统的7 大领域和2 9 个用户服务功能，并确定了到2 0 0 5 年的年度开 发计划。图1 1 显示了这个计划的整体框架，其中7 大领域包括出行和交通管理 系统、出行需求管理系统、公共交通运营系统、商用车辆运营系统、电子收费系 统、应急管理系统、先进的车辆控制和安全系统。美国联邦政府1 9 9 0 1 9 9 7 年 用于i t s 研究开发的年度预算总计为1 2 9 3 5 亿美元，2 0 年发展规划投资预算约 为4 0 0 亿美元。美国政府要求将i t s 的发展与建设纳入各级政府的基本投资计划 之中。目前i t s 在美国的应用已经达到8 0 以上，而且相关设备也较为先进。 日本早在1 9 7 3 年就开始了对智能交通的研究【2 7 】。日本i t s 规划体系包括先 进的导航系统、安全辅助系统、交通管理最优化系统、道路交通管理高效化系统、 浙江大学硕士学位论文第l 章绪论 公交支援系统、车辆运营管理系统、行人诱导系统和紧急车辆支援系统。日本政 府1 9 9 6 - - - 1 9 9 7 年用于i t s 研究开发的预算为1 6 1 亿日元，用于i t s 实用化和基 础设施建设的预算为1 2 8 5 亿日元。1 9 9 6 年，“推进i t s 总体构想”推出了一个投 资预算7 8 兆日元的2 0 年规划。日本走政府与民间企业相互合作的道路，如车辆 信息通讯系统( v i c s ) 的运作方式极大地调动了企业的积极性，加速了日本i t s 的开发与应用。在欧洲，t e l e m a t i e 系统正在全面开发阶段。该系统计划在全欧洲 建立专门的交通( 以道路交通为主) 无线数据通信网，正在开发先进的出行信息 服务系统( a t i s ) ，先进的车辆控制系统( a 、，c s ) ，先进的商业车辆运行系统 ( a c v o ) ，先进的电子收费系统等。欧盟从1 9 8 4 年到1 9 9 8 年仅用于i t s 共同研 究开发项目的预算就达2 8 0 亿欧元。 图1 1 美国“国家智能交通系统项目规划”整体框架 2 浙江大学硕士学位论文第l 章绪论 1 1 2 基于位置的服务( l b s ) 基于位置的服务( l b s ，又称“移动定位服务”) 【2 8 】是利用路径和地理位置信 息的另一个新兴领域。它根据移动物体的当前位置，提供相关的服务。如为游客 提供离他们最近的旅馆或者是a t m 机的信息：向司机提供导航信息，加油站的 信息，以及前方交通堵塞信息等。在欧美等发达国家，基于位置的服务已经进入 了千家万户。近年来，随着移动通信网络从2 5 g 向3 g 的发展，我国的移动定位 业务在行业用户市场加快渗透的同时，正逐步向大众用户市场拓展。中国移动和 中国联通都推出了相关的l b s 服务，主要包括提供最近的商场宾馆餐厅等查询、 导航、物流、报警、车辆跟踪指挥调度、老人孩子位置查询等。基于位置的服 务被认为是最具发展潜力的移动增值业务之一。2 0 0 5 年，中国国内移动定位市场 规模达到2 2 1 亿元，比2 0 0 4 年增长8 0 。在2 0 0 6 到2 0 0 8 年的三年内，该市场 的增长率保持在1 5 0 以上。2 0 0 8 年国内移动定位服务市场规模将达到5 2 5 亿元， 而全球移动定位服务市场规模将达到1 2 0 亿美元。 基于路径和位置的服务之所以能够得到快速的发展，一个很重要的原因是地 理定位技术的发展和成熟。目前流行的地理定位系统包括g p s 系统、g s m 系统、 车辆探测系统( p r o b e c a i s y a e m ) 、车辆分享系统( c a r - s h a r i n gs y s t e m ) 等。 1 1 3 全球定位系统( g p s ) g p s 是目前全球精度最高的定位系统。美国从上世纪7 0 年代开始研制全球定 位系统( g l o b a lp o s i t i o n i n gs y s t e m ，g p s ) ，历时2 0 年，于19 9 4 年全面建成，是具 有在海、陆、空进行全方位实时三维导航与定位能力的新一代卫星导航与定位系 统 2 9 1 。g p s 系统包括三大部分：空间部分( g p s ) i - j 星、地面部分( 地面监控系统) 、 用户设备部分( g p s 信号接收机) 。 g p s 的空间部分是由2 4 颗工作卫星组成，它位于距地表2 0 2 0 0 k m 的上空， 均匀分布在6 个轨道面上( 每个轨道面4 颗) ，轨道倾角为5 5 0 。此外，还有4 颗有 源备份卫星在轨运行。卫星的分布使得在全球任何地方、任何时间都可观测到4 浙江大学硕士学位论文第l 章绪论 颗以上的卫星，并能保持良好定位解算精度的几何图像。这就提供了在时间上连 续的全球导航能力。g p s 卫星产生两组电码，一组称为c a 码( c o a r s e a c q u i s i t i o n c o d e l l 0 2 3 m i - i z ) ；一组称为p 码( p r e c i s ec o d e1 0 1 2 3 m h z ) ，p 码因频率较高，不 易受干扰，定位精度高，因此受美国军方管制，并设有密码，一般民间无法解读， 主要为美国军方服务。c a 码人为采取措施而刻意降低精度后，主要开放给民间 使用。目前，民用的g p s 信号定位误差大约在5 1 0 米的范围内。 g p s 的地面控制部分由一个主控站，5 个全球监测站和3 个地面控制站组成。 监测站均配装有精密的铯钟和能够连续测量到所有可见卫星的接受机。监测站将 取得的卫星观测数据，包括电离层和气象数据，经过初步处理后，传送到主控站。 主控站从各监测站收集跟踪数据，计算出卫星的轨道和时钟参数，然后将结果送 到3 个地面控制站。地面控制站在每颗卫星运行至上空时，把这些导航数据及主 控站指令注入到卫星。这种注入对每颗g p s 卫星每天一次，并在卫星离开注入站 作用范围之前进行最后的注入。如果某地面站发生故障，那么在卫星中预存的导 航信息还可用一段时间，但导航精度会逐渐降低。 用户设备部分即g p s 信号接收机。其主要功能是能够捕获到按一定卫星截止 角所选择的待测卫星，并跟踪这些卫星的运行。当接收机捕获到跟踪的卫星信号 后，即可测量出接收天线至卫星的伪距离和距离的变化率，解调出卫星轨道参数 等数据。根据这些数据，接收机中的微处理计算机就可按定位解算方法进行定位 计算，计算出用户所在地理位置的经纬度、高度、速度、时间等信息。接收机硬 件和机内软件以及g p s 数据的后处理软件包构成完整的g p s 用户设备。g p s 接 收机的结构分为天线单元和接收单元两部分。接收机一般采用机内和机外两种直 流电源。设置机内电源的目的在于更换外电源时不中断连续观测。在用机外电源 时机内电池自动充电。关机后，机内电池为r a m 存储器供电，以防止数据丢失。 目前各种类型的接受机体积越来越小，重量越来越轻，便于野外观测使用。 1 1 4 全球移动通信系统( g s m ) 另一种流行的定位系统是g s m 定位系统，其利用目前用户最多覆盖范围最广 4 浙江大学硕士学位论文第l 章绪论 的公众通信系统。g s m 全名为：g l o b a ls y s t e mf o rm o b i l ec o m m u n i c a t i o n s ，中文 为全球移动通讯系统，俗称“全球通”，是一种起源于欧洲的移动通信技术标准， 是第二代移动通信技术，其开发目的是让全球各地可以共同使用一个移动电话网 络标准，让用户使用一部手机就能行遍全球。我国于2 0 世纪9 0 年代初引进采用 此项技术标准，此前一直是采用蜂窝模拟移动技术，即第一代g s m 技术( 2 0 0 1 年1 2 月3 1 日我国关闭了模拟移动网络) 。目前，中国移动、中国联通各拥有一 个g s m 网，为世界最大的移动通信网络。 利用g s m 网络的定位系统主要有三种系统物理结构：第一种是基于移动台的 定位。移动台利用来自基站的信号计算出它自己的位置的情况被称为基于移动台 的定位。这是自定位系统的一种。有许多方法可以用来进行位置计算，但t d o a 是最基本的一种方法。对于利用t d o a 的基于移动台的定位系统，需要对g s m 设备进行两个基本的改进。首先要改进移动台，使其可以进行高精度的t d o a 的 测量。并且这种测量需要多径抑制算法。相应的在移动台里要有一个称为定位函 数的特殊函数，函数可以精确的确定t d o a 及其它一些可能的信号参数。这可以 通过对突发传输进行处理进而确定训练序列的开始时刻来得到。第二个改进是由 于网络同步的需要。这里有两种选择，第一种是对网络进行严格的同步。这可以 通过很多方法实现，其中包括在每个基站使用g p s 时间发逍接收机。另一种选 择是给移动台提供有关网络同步的信息。这可以使用一个特殊的监测接收机来实 现，该接收机可以测量不同基站间的时间差，并通过g s m 的短信息业务( s m s ) 或寻呼业务( p s ) 把这些时间数据传送给移动台。上面只是描述了使用t d o a 的系 统的基本的操作。为了实现具有高精度和覆盖范围的蜂窝定位系统，集成许多其 它来源的信息是必要的。完成这种集成的一种关键部分是一个可将不同来源的信 息进行混合的复杂的软件，它被称为混合函数。这些信息中的一个重要的信息就 是基站的位置，这在进行时间测量时是必须的。其它一些可以用来提高精度及解 决二义性的可能的信息来源包括信号强度及扇区信息等。在基于移动台的定位的 实际实现中，系统对每个基站的数据库进行维护，并且把诸如基站位置及相邻频 率的分配表等信息传送给移动台是必要的。在很多时候，其它地方可能需要由移 浙江大学硕士学位论文第l 章绪论 动台计算出的定位信息。这时定位信息可通过s m s 由移动台传到其它地方。这 将构成一个间接远程定位系统，但网络不必知道定位信息正在如此使用。 第二种系统结构是基于网络的定位。利用移动台传来的信号计算出移动台的 位置的定位称为基于网络的定位，并且这构成一种远程定位系统。g s m 的基于网 络的定位的最简单的实现也是基于t d o a 方法的。在这种情况下，需要几个分布 在移动台周围的定位接收机来监测由移动台传来的信号，并对这些信号进行精确 的t o a 的测量。在每个定位接收机中需要一个定位函数。该函数将对上行链路 中来自通话中的移动台的突发流进行处理。定位服务中心将从不同的t o a 测量 中得出t d o a ，进而得出定位估计。因此，混合函数将在定位服务中心使用。定 位服务中心可被看作事务处理器。它来自不同计算机的对位置测量的请求，选择 适当的定位接收机对指定的移动台进行所需的定位区测量，收集来自定位接收机 的定位区测量，将所有信息进行综合来得到定位测量，并把该定位测量传送给发 出请求的计算机。定位服务中心与g s m 的移动业务交换中心是处于同一分层的。 与基于移动台的定位相同，在这里同步同样是一个问题。如果是同步网络，则在 每个基站应该有一个可唯一标定给定频道中给定的t c h 突发信号的t o a 的时钟。 在非同步网络中，则需要有一种机制用来使在每个定位接收机中的时钟同步。采 用基于网络的定位系统结构有许多好处。首先它提供了一种无需对移动台进行改 进的定位方法。另外，如果采用适当的方法与安全措施，定位网络还可提供许多 基于地点的服务，如对交通堵塞的监测，为移动用户提供诸如路途向导之类的服 务等等。当网络测出移动台的位置后，它可通过s m s 将此信息回传给移动台， 这样就构成一个间接自定位系统。 第三种混合定位的系统结构是将自定位系统与远程定位系统的不同方面相结 合而构成的。一个可行的混合定位系统结构是使定位函数位于在移动台中而混合 函数则处于l s c 之中。当l s c 向某一移动台发出请求时，该移动台将对来自不 同基站的突发传输进行t o a 的测量。之后这些测量值将传输给l s c ，在那里进 行t d o a 的测量并计算出此移动台的位置估计值。如同基于移动台的定位，这里 同样需要某种方式的同步。适用于基于移动台定位的同步方法对于混合定位结构 6 浙江大学硕士学位论文第l 章绪论 同样适用。混合定位系统结构的一个变形是数字光标系统。该系统通过传输信号 的拷贝，并使用不同拷贝的互相关进行t d o a 的计算来替代了定位区信息的传输。 此系统的静态与动态试验已达到了l o o m 以下的定位精度。 1 2 研究现状及存在问题 目前，关于移动对象运动预测的研究工作主要集中于对车辆运动状况分析在 智能交通系统( i t s ) 和基于位置的服务( l b s ) 中的应用。在这些研究工作中，研 究人员利用不同信息获取渠道以及定位系统，采用不同的解决问题的思路。但是， 这些预测系统基本由三大部分组成。 首先，研究人员利用不同方法对真实的路径数据进行抽象化处理。这种处理 的方法包括：利用地图信息将真实路径信息映射到地图上的真实街道，利用规则 图形( 如，矩形) 代替包含在其内部的路径等。抽象化处理的主要目的是提取道 路之间的相似特性，并简化后续工作计算量，减轻计算压力。第二部分，研究人 员从抽象化的真实路径中抽取运动模式( 模型) 。其方法包括序列挖掘算法，经 典熟悉模型( 如，隐性马尔科夫模型) 和相似序列合并算法等。抽取模式和模型的 目的是为进一步的预测工作提供依据。第三部分，即道路预测部分，该部分的主 要工作是根据物体运动的路径模式( 模型) ，结合一定的实时运动信息，当前交 通状况等，来预测物体运动终点、运动时间、运动路径等运动状况。以下提到的 各项研究工作，是这些移动对象状态预测系统中比较典型的几个。 文献 2 1 q b 的工作重点关注了频繁时空序列挖掘的问题。在这项工作中，研究 人员利用线型简化化i n es i m p l i f i c a t i o n ) 技术来抽象化原始的移动物体轨迹。定义 块( s e g m e n t ) s i j 为连续时空序列s 中的一个连续的子序列，并h a s i j 开始于 ( x i ，y i ，t i ) ，结束于( x i j y j ，t j ) 。给定s i j ，定义它所表示的线型块l 。i 开始于 ( x i ，y i ) ，结束f ( x j ，y j ) 。阈值被用来判断s i j 是否服从于( c o n l p l y 谢m ) l 。i 。其依据是， s i i 中每一点( x k j y k ) 到1 i 的距离均小于e 。如果s i 胡艮从于l 。i ，在后续的运算中，1 ；代 替s i i 进行计算。【2 】还定义了两个线型块的相似( s i m i l a r ) 关系和相近( c l o s e ) 关系，用 于合并相似的较短轨迹。相似关系的定义为，给定两个线型块l 。：和l g 二，当满足下 7 浙江大学硕士学位论文 第l 章绪论 列条件时，认为两个线型块是相似的： ( 1 ) 阶a n g l e l g h a n g l e l 0 ( 2 ) l e n l g h 1 e n l f xm a xo i j 1 e n ，l g h 1 e n ) 其中9 是用来限制两个线型块角度差异的阈值，f 是一个可调整的比例，用来限制 两个线型块的长度差异。相近关系的定义如下：线型块i 与线型块石相近，当 v ( x i ，y i ) 一i l l , d i s t ( ( x i ，y i ) ，西。这样，抽象化工作的目标被定义为找到能够最 好表示原有时空序列s 的线型块序列。将合并后的线型块所代表的区域进行编号， 并用区域的中心线( c e n t r a ll i n e ) 来描述这个区域。则原始移动轨迹被抽象为字符串 序列r l r 2 r 3 r q ，( 1 q m ) 抽象所得的序列经过将进行两种级别的挖掘。层级 另l j ( 1 e v e l w i s e ) 的挖掘主要用于合并较短区域序列，子字符串树( s u b s t r i n gt r e e ) 挖掘 采用树状数据结构挖掘区域序列。 2 】中的路径抽象化方法能够较好地描述路径的 特点，克服了利用网格描述路径时，单个格内运动状况无法表达的缺陷。但是这 种抽象和挖掘方法带来较大的运算压力，不适合使用在个人手持设备上。 文献【4 】中建立了一个基于g p s 数据的车辆路径预测系统。研究人员将g p s 接收设备安装在2 5 2 个参与者的车辆上。设备的能源是车内的电力系统，这种设 计使得g p s 设备可以在车辆启动时自动开启，并记录位置信息。在车辆熄火时， g p s 设备能自动关闭。研究人员利用时间阈值将所记录的位置信息进行分割。并 利用数据过滤算法对数据进行过滤，以除去其中的噪声。该工作中所使用的数据 过滤算法根据移动对象的特点考虑了车辆移动的速度、加速度、移动方向、移动 距离等因素。 4 1 利用了一种应用在计算机视觉中的h a u s d o r f f 距离【8 】来判断两条 路径的相似程度。其方法是，给定真实路径t r i pa 和t r i pb ，对于t r i pa 中的每 个点( x i ，y j ) ，计算该点到t r i pb 的距离，求距离的最大值。因为真实路径是由许 多点组成的线段，( x i ，y j ) 至ut r i pb 的距离被定义为该点到t r i pb 中所有线段的最 短值。当t r i pa 到t r i pb 的距离小于某个给定的阈值时，认为两条路径是相似， 即可以在后续的计算中将它们合并。利用h a u s d o r f f 距离进行道路合并的过程即 为原始道路抽象化和道路模式挖掘的过程。车辆路径的预测也基于h a u s d o r f f 距 浙江大学硕士学位论文第l 章绪论 离的计算。文献【4 】中的道路预测系统提供了实时的道路预测方案，它可以依据车 辆当前行驶的道路预测车辆未来的道路。该系统实现了两种道路预测的准则，一 是“最佳匹配预测”，该准则保证总是返回与当前经过的路径最佳匹配的道路模式。 第二是“基于阈值的匹配”，该准则将返回一组道路模式和它们的可信度，并按照 置信度量对它们排序。文中的实验显示，当车辆行驶了约5 0 的路程后，预测系 统预测的准确性可以达到9 0 以上。该文采用的h a u s d o r f f 方法能够较好地保留 路径的完整性和特征，但是计算量较大，该算法也不适合运行在个人手持设备上。 文献【5 】提出了挖掘时间标注序列( t e m p o r a l l ya n n o t a t e ds e q u e n c e s ，t a s ) 的概 念，使得时空序列中的时间信息不仅仅用于对空间位置或状态的排序，而是参与 了模式的挖掘。时间标注序列的定义如下： 定义1 1 ( 时间标注序列) 一个长度为n o 的时空序列，被成为时间标注序 列，是一个二元组t = ( - ，- ) ，其中季= ( s o ，s n ) ，v o s i s n s i 是某一状态，而 瓦= ( a 1 一，a n ) ，v 1 s i s n a i 从s i - i 转换到s i 所经过的时间间隔。 时空标注序列也可以用下列方式表示：t = ( 季，瓦) = s o i z ls 1 一c t 2 g ns n 研究人员进一步定义了两个时间标注序列的包含关系( c o n t a i n m e n t ) ，其定义如下： 定义1 2 ( 时间标注序列包含关系) 给定一个时间阈值百，一个长度为n 的时 间标注序列t l 和一个长度为m 的时间标注序列t 2 ，其中n m 。t l 被t 2 包含( 被 表示为t 1 。t 2 ) ，当且仅当存在一个整数序列0 i o i n m 满足： 1 v o s k s n s t ，k s z ，i k 2 v 1 s k 鲫i s t ，k s 。，k i 百 其中v 1 s k 鲫伍。，k = i k l 歹i k 【5 】中挖掘算法的目标是挖掘时间标注序列 集合中的序列模式。根据其定义，这种定义方法不仅可以用于时空序列的模式挖 掘，也可以用于时间序列相关的其他应用，如挖掘用户在线浏览网页的模式等。 研究人员提出了一种思想类似于f r e e s p a n 7 的挖掘算法：m i s t a 。其核心思想是 9 浙江大学硕士学位论文第l 章绪论 将与状态序列相关的时间序列表示为高维空间中的多维块。在挖掘时间标注序列 的模式时，按照前缀( p r e f l x ) 的思想，长度为n 的时间标注序列模式必定是从长度 为n - 1 的时间标注序列中获得。m i s t a 利用扩大( e n l a r g e m e n t ) 和扩展( e x t e n s i o n ) 算法迭代地获得更长的模式。【5 】提出的挖掘算法新颖地将时间序列引入了模式挖 掘过程，但由于算法自身设计的问题，当序列模式变得较长时，即挖掘空间维度 变高时，算法的复杂度会非常高。 文献【6 】中的研究工作将m i s t a 时间标注序列挖掘方法应用于物体移动轨迹 的挖掘中。该研究工作通过以下方法将车辆的时空信息转化成时间标注序列。定 义时空序列的包含关系( c o n t a i n m e n t ) 如下： 定义1 - 3 ( 时空序列包含关系，n ) 给定一个时空序列t ，时间阈值t ，以及 用于计算邻近关系( n e i g h b o r h o o d ) 的函数n ：r 2 一p ( r 2 ) 和时间标注模式 ( s ，a ) = ( x 。，y 。) 墨( x 1 ，y 1 ) 兰一a k ( x k y k ) ，( s ，a ) 被t 包含当且仅当，t 存在一个子 序列t ，t = ( ( x ：，y o ，t o ) ，( x i ( ，y i ( ，t ，k ) ) ，它满足： 1 s nt 2 v 1 k s n i a j 一嵋l t ，其中a ；= t ；一t ；一1 为了抽象化车辆移动路径，研究人员利用网格作为定义区域的最小单位。将 车辆有活动的区域均匀划分成网格，然后根据路径的历史记录来区分网格被访问 的频繁程度。由于记录的路径历史信息是离散的，为了保证路径连续，研究人员 利用线性插值的方法补充相邻两个记录点之间的位置信息。邻近的，具有相近访 问频率的网格被合并成“活跃区域”( r e g i o no f i n t e r e s t , r o i ) 。而在挖掘过程中“活跃 区域”就是【5 】中的状态。状态间转换所需的时间，被定义为车辆从进入第n 个区 域开始到进入第n + 1 个区域所消耗的时间。基于不同的区域划分方法，文献 6 】 提出了两种挖掘策略：第一，静态地确定“活跃区域”，即，采用人为定义或者仅 仅通过对历史数据的分析来确定“活跃区域”。这种方法有效地减少了“活跃区域” 检测工作的复杂度。第二种挖掘策略是，在路径的挖掘过程中不断优化“活跃区域” 1 0 浙江大学硕士学位论文第l 章绪论 检测和界定。然而，第二种挖掘策略的算法复杂度非常高，无法应用于移动设备。 实验结果表明m i s t a 在挖掘时空数据中的应用仅适用于较大区域间移动的模式 挖掘，而不适合用于路径模式的挖掘。 n e c 的研究人员利用从车载感知系统( p r o b e c a rs y s t e m ) 所记录的交通信息数 据，建立了一个车辆行程时间( t r a v e lt i m e l 的预测系统f 1 2 】。该预测系统基于统计信 息分析，采用了带周期性调整的a r 模型和最小描述长度准则( m i n i m u m d e s c r i p t i o nl e n g t h ，m d l ) 。周期性调整指的是将一天中的绝对时间信息加入挖掘 的模型中。该系统中所使用的行程信息包括如下内容： 伍zi g , 彻= ( d a yo f aw e e k , t i m ei n d e x , m e a nt r a v e lt i m e , v a r i a n c e , # t r i p s ) 其中t i m ei n d e x 是一个范围在0 到9 5 之间的整数，期间每个整数对应于一天中的 一个1 5 分钟的时段，依次递增。o 代表时段0 ：0 0 0 ：1 5 。该系统利用状态空间模型 ( s t a t es p a c em o d e l ) 处理时间序列和时段的关系，并利用最小描