移动行为感知计算技术研究综述

邓舟彦 韩楠 乔少杰 徐小玲 黄萍 熊熙

摘要：随着智能计算、无线通信、传感器等技术的快速发展，具有GPS定位功能的移动便携设备日益普及和流行，这些设备会产生能够反映设备的移动行为运动规律的大规模轨迹数据，可以为出行规划、城市道路规划、共享单车站点分布、出租车调度等提供有力支撑。本文从轨迹数据的采集、提取和移动行为感知分析等方面进行阐述，讨论当前主流技术基本思想及工作原理，最后对未来的研究工作进行展望。

关键字：移动行为感知；GPS；轨迹数据；行为分析

中图分类号：TP393.03 文献标识码：B 文章编号：1672-9129（2019）04-0001-06

Abstract：With the rapid development of the intelligent computing， wireless communication and sensors， mobile portable devices with GPS positioning function are becoming more and more popular. These devices will generate large-scale trajectory data which can reflect the movement behavior of devices， which can be used for trip planning， urban road planning， station planning of sharing bicycles and taxi dispatch. This study reviews the techniques of trajectory data collection， extraction and mobile behavior perception analysis， discusses the basic ideas and working principles of the state-of-the-art techniques， and finally presents the future research work.

Keywords：mobile behavior perception； GPS； trajectory data； behavior analysis

引言

近年來，随着具有GPS定位功能的设备的普及，手机、平板、车载导航、共享单车等移动设备进入我们的生活并变得日益普及。据工业和信息化部统计，截至2018年5月，三家基础电信公司的手机用户总数接近15亿。大城市的手机普及率接近100%。手机自带的位置定位功能在服务于用户定位时，通信运营商也积累了大量的位置轨迹数据。同时，手机导航作为汽车导航的普遍率很高。艾媒咨询发布了“2017-2018中国移动地图市场研究报告”。根据该机构的数据，截至2017年第四季度，中国的移动地图用户数量已达到7.07亿。

比起基于移动通信数据等方法对用户行为的预测，基于GPS和移动数据的定位轨迹因为其具有海量的规模、不易受天气影响和能精准及时地反馈记录的坐标等特点而具有较大的研究价值和应用前景。这些数据大大降低了数据采集成本，为行驶路径规划、交通流量预测、城市道路规划、共享类交通工具调度等提供有效数据支撑。

1 问题描述

近年来，使用移动轨迹数据做数据挖掘和机器学习来感知移动行为得到许多研究人员的关注。运动物体轨迹预测方法主要分为基于道路网络限制的轨迹预测和基于欧式空间的轨迹预测[1]。通过频繁模式挖掘到的轨迹模式来对轨迹进行预测和根据当前移动对象前一段时间片的位置和速度预测当前时刻的轨迹位置都是基于欧式空间轨迹预测。但基于移动设备的轨迹数据往往只是单一地在道路网上运动，其位置和速度都会受到限制，而无法有效的通过基于欧式空间的方法进行预测。

大部分的研究都集中在具体分析运动物体的历史轨迹，从而得到有价值的信息，针对基于历史数据的位置预测的研究相对较少。运动物体的连续位置预测主要包括过去轨迹的重建以及当前和未来轨迹的预测。研究重点是挖掘轨迹频繁模式找出典型运动路径[2]。目前，移动行为感知研究主要关注两个问题：一、提高交通设施运行效率的提高智能交通系统（ ITS），二、通过电信移动运营商的无线电通讯网络（例如，GSM网络，CDMA网络或外部定位方法（例如GPS）获得移动终端用户的位置信息服务。

2 国内外研究现状

越来越多的研究人员利用机器学习技术和数据挖掘来对移动对象行为感知研究。由此，产生了大量关于移动行为感知的研究成果。文献[3]介绍了移动轨迹可视化技术对于智能交通、人员流动性评估和路径规划三个方面的作用。通过对轨迹空间和时间等属性的可视化分析，在一个显示图上展现这些属性之间的关系。可以为研究人员寻找数据之间的联系和规律提供铺垫。刘震等人[4]指出，基于移动通信技术对用户轨迹预测，通过记录手机通话时基站位置来确定用户位置是不准确的，因信号、基站容量等客观因素的影响，手机通信时选择的并不一定是最近的基站，可以用过设定地区转换的上限的方法来判断用户是否移动。Wiest等人0提出建立概率模型，对物体运动前一段时间运动的参数进行收集作为运动模型的联合概率分布，通过对分布的计算来推断未来运动轨迹。这种方法的优点在于不仅是对运动轨迹的预测，而且能反映对未来轨迹的整体分布，通过对统计的属性评估可以对特定的目标进行预测。该预测结果还可以用方差来评估预测的准确性。

彭曲[5]等人基于马尔科夫链进行轨迹预测，运用转移概率矩阵评估状态评估直接转换的可能性，对处于交叉路口的轨道的选择进行预测，但因为实际交通状况具有不确定性，在交叉路口的选择需遵守一定的规则等因素，故预测结果准确率存在瓶颈。Song等人[6]做了对人类移动轨迹预测的研究，利用DBSCAN算法在人群中找到的聚类来构建轨迹，基于Lempel-Ziv压缩算法算出移动序列的熵值，定量地给出了人类动态运动轨迹具有70%-93%的可预测性，文中结论指出人类的运动规律独立于轨迹路径。Qiao等人[7]基于隐马尔科夫模型，设计实现了自适应调整轨迹预测算法，可以根据轨迹数据预测算出最佳路线，但随着数据量的增加，该算法会出现运行时间成本过高的问题。乔少杰等人[8]提出基于隐马尔科夫模型的自适应轨迹预测模型，对移动对象轨迹数据基于密度聚类分区和高效分段处理，根据轨迹数据选择参数组合，解决了隐马尔科夫模型中状态间断、中断等问题。Shi等人[9]基于马尔科夫模型，根据移动轨迹所在的路段预测其在短期内将到达的路段。

3 轨迹特征提取

随着智能设备与车载雷达的普及，GPS数据库与显示结合，让我们能享受更加便利的生活，在这当中轨迹数据发挥了重要的作用。但是，随着数据量的爆发式增长，现有存储和计算能力的限制和冗余数据的存在，在海量数据中提取能够精确反映轨迹信息的点就显得尤为重要，而轨迹特征就是具有独特价值的点。以下是对于轨迹特征提取的具体因素。

（1）对轨迹点数据的获取进程，因GPS数据采集设施的定位精度等限制，导航中会出现轨迹偏差，故需要提取轨迹特征，来提高在轨迹模型系统匹配的准确率[10]。

（2）采集到的数据具有许多不确定性，如数据来源存在的不确定性、位置的不确定性、运动行为的不确定性等诸多不确定性因素[11]，使得原始轨迹数据中将存在一定的噪声点，导致大轨迹数据查询、挖掘、预测不精确。因此，在大数据挖掘之前从原始轨迹中提取特征是非常重要的。

（3）可以通过移动轨迹数据来体现交通状态信息，并且可基于轨迹特征提取来评估交通流量。另外，我们可以通过对轨迹数据进行聚类分析从而找到功能区域的缺陷，重新规划城市社区周边配套设施布局提升的设施资源利用率。

3.1 数据预处理

轨迹原始数据往往包含误差，所以需要对数据进行特征提取，可以通过数据去噪、分段、压缩、地图匹配等一系列的操作来对数据特征进行采集[12]。乔少杰等人[13]提出了一种基于GeoHash空间编码[14]的轨迹特征提取方法，对轨迹数据进行GeoHash编码，生成GeoHashTree，将拐角大于阈值的拐点作为特征点。

3.1.1 数据去噪

去噪是通过对轨迹数据进行预处理，通过如获取聚类处理结果等方法对轨迹数据中的异常轨迹数据和冗余数据进行过滤，从而排除本身数据问题所带来的干扰。一般来说，去噪一般可以通过基于中值或均值滤波、Kalman 滤波和基于粒子滤波[15]。

3.1.2 数据分段

分段是指对轨迹进行分段的操作，对原有轨迹进行分段，可以极大提高挖掘效率。轨迹分段可以分为三种分类型：

（1）利用时间间隔分段，表示对长时段轨迹进行合理划分和标注。

（2）基于軌迹形状分段，历史轨迹在变化时与上一轨迹点方向角度的变化大小决定了是否要分段，一旦角度超过了某一零界点，则分段。

（3）基于轨迹实际意义分段，轨迹如果是存在实际停留点，则可作为分段结点。轨迹如果基于出行模式，若轨迹来源用户交通工具发生改变，则分段。因此，应该考虑轨迹所存在的具体物理意义。

3.1.3 数据压缩

对于基于时间的轨迹记录可以采用以秒为计时单元，但由于计算能力、存储容量等因素的限制，导致轨迹数据挖掘一般无法采用太过精细的位置数据，需要轨迹压缩来处理数据[16]。轨迹压缩可以分为离线压缩方法和在线压缩方法。对于离线压缩的方法以轨迹起始点和终点进行连线，如下图1（a）的P1和P2点连线，找到剩余点到连线的垂直欧氏距离最长的点作为图1（a）中的P5点，选择P5作为压缩点，P1与P5、P10与P5分别连线，在P1-P10之间的点分别寻找所在范围的欧氏距离最大的点，如果寻找到的点欧式距离达到阈值或以下则停止寻找。

在线压缩的的方法可以用下图2表示，P1，P10分别作为轨迹的起终点，从P3开始计算与P1垂直的欧几里得距离，然后以此计算P4、P5、P6，如果计算P6的距离时发现大于阈值，就将P6，P10作为新的起终点，从P8开始依次计算欧几里得距离，依次进行下去，直至计算到P10的值也没有大于阈值时停止压缩。

J Hershberger等人[17]利用著名的离线压缩算法Douglas-Peucker算法实现轨迹点批处理模式，但在实际的应用环境时，却很难批处理轨迹数据的压缩，当数据量过大时，容易造成失真。在理想环境下的路径而言，Douglas-Peucker算法是实用的，但因偏差是以垂直欧式距离为准的，当数据轨迹中存在折返路径，会造成拐角处很容易被压缩掉，使得压缩后的轨迹无法正确的反映出轨迹的方向。

3.1.4 地图匹配

轨迹地图匹配时结合数据轨迹与数字地图，将单纯的GPS点的原始轨迹数据匹配在地图数据上能够更加直观的反映数据轨迹。轨迹数据因为存在噪声、信号丢失和数据精度不高等不足，通过将轨迹数据航迹与数字地图上矢量路径匹配，找到当前所行驶的路径，将每一个轨迹数据点映射在地图上的空间位置，可一定程度上弥补误差[18]。

4 移动行为感知

4.1 用户行为挖掘与分析

随着手机等具有GPS功能的智能设备的普及，从收集的用户轨迹数据中可以提取到用户的相关信息，包括用户个人活动规律喜好等。位置服务可以给用户提供更加个性化、更便捷的生活方式，提高生活水平。

袁书寒等人错误！未找到引用源。通过对用户轨迹进行分析，可以得到用户在物理坐标位置下的行为方式，基于分析在各种领域范围内用户地理坐标的聚类，计算用户行为轨迹上的相似性。Jure等人[19]利用MSN用户的信息验证了数学领域的“六度空间猜想”，该猜想表明了两个陌生人间可以通过不超过6个人组成的关系网连接在一起。说明各个体之间的关系网络看似毫无联系，实际上可以通过几个中间网络关系连接在一起。

Song等人[20]对人类轨迹做了预测的研究，研究表明人类行为具有70%-90%的可预测性。对于人类行为的预测对城市交通管理和对用户的个人服务推荐具有重要作用。郑宇等人[21]通过对轨迹数据建模，将相似的位置点聚类形成层次树，计算各个地区之间的兴趣度。可以通过轨迹位置算出的兴趣度较大的地区推荐给用户，从而提高用户体验。

4.2 行为预测

用户使用基于定位服务的软件或者应用时，网络中会留下用户浏览痕迹，用户下次使用软件时，可以基于用户当前位置和历史浏览数据为用户推荐相关信息，给用户提供更加个性化的推荐。Pentland等人[22]指出人的行为可以被精准得描述为一组由马尔科夫链排列在一起的动态模型（如：Kalman lters）。高卫华等人[23]以马尔科夫模型和有向图为基础，采用MD（Al1.KthMarkov—and-Digraph）模型进行预测，准确度和马尔科夫模型持平，但是其复杂度低于马尔科夫模型，并且提出了一种算法—NDLACO算法，该算法是对蚁群算法的改进，根据算法在轨迹寻找过程中释放的”信息素”等信息，能够利用蚂蚁算法正反馈快速发现较优解、并发性强等特点，并且可以避免算法容易出现停滞、收敛速度慢的特点。

Tseng等人[24]提出了一种型的数据挖掘方法，即SMAP-Mine，该算法能够发现移动用户和请求服务相关的顺序移动模式。在对用户行为预测中，Tseng等人使用了基于N-gram模型的SMAR-N-gram算法实现预测功能。George等人[25]使用运动循环、运动轨迹模型以及马尔科夫链模型的预测移动和轨迹的方案，提出了MC/MT模型用于规律性的运动， MC/MT模型预测算法避免了在随机模型中的复杂计算，降低了处理预测算法所需的计算能力，同时使用马尔科夫模型处理随机运动。并且George等人提出对MC/MT模型和马尔科夫模型进行比较，希望寻找其与随机因子的作用”交叉”点来研究两种模型各自的特点。

4.3 智能交通技术

智能交通研究的一个重要的话题是对行驶过程中的车辆进行路径诱导，为驾驶员提供最优路径。Balan等人[26]通过对出租车轨迹的分析，可以提前预测两地之间所需要花费的时间。但由于交通环境存在诸多不确定性，所以最短路径花费的时间不一定最短。贪心算法可尋找道路两点之间最短路线[27]，但往往在实际条件下，因为道路交通状况、驾驶成本、道路等级等原因，贪心算法得到的路径对于驾驶者来说并不是最优路径。

Gonzalez等人[28]提出了基于道路信息寻找最优路径的方法，道路因为等级差异，道路等级越高，可达到的速度越快，不同等级的道路之间又可以划分为各自的封闭环路。此外，由于路线中有些道路虽然等级较高，但通行的车辆却不多，因此，Gonzalez对道路等级评定制定了一些相关标准，即道路等级同时取决于道路静态等级和道路动态特征。

文献[29]中的算法在路段较长的环境中能够较好地发挥作用，但对路段较短、起始段和终点端处于同一个道路封闭区域时，跳转至更高一级路网会浪费更多的时间。郑宇等人[28]基于出租车驾驶员的经验的记录数据，郑宇等人认为在同一城市内，出租车驾驶员经验普遍较高，所以可以通过采集出租车轨迹数据作为两点之间最优路径。

5 结语

基于移动用户行为轨迹的收集，产生了海量的数据可供研究分析。但随着对着世界各地区对自身隐私关注度的不断提高，避免隐私泄露成为了研究者获取数据来源的阻力[29]。研究人员如Ratti等人[30]运用收集手机时空行为数据产生的数据群来研究城市结构的变化规律，避免了与个人信息的关联。对于科学研究与个人隐私冲突问题具有指导价值[31]。

目前，智能交通的运用主要研究方向在驾驶路径诱导、交通状况判断等传统问题上。随着物联网技术的兴起和基于社交网络服务的发展，研究的内容将更有实用性，特别是基于商业活动的个性化推荐和基于共享设备管理等问题的出现给相关研究注入了新的活力。

参考文献：

[1] 彭曲， 丁治明， 郭黎敏. 基于马尔可夫链的轨迹预测[J]. 计算机科学， 2010， 37（8）： 189-193.

[2] 乔少杰， 韩楠， 李天瑞， 等. 基于前缀投影技术的大规模轨迹预测模型[J]. 软件学报， 2017， 28（11）： 3043- 3057.

[3] 蒲剑苏， 屈华民， 倪明选. 移动轨迹数据的可视化[J]. 计算机辅助设计与图形学学报， 2012， 24（10）：1273- 1282.

[4] 刘震， 付俊辉， 赵楠. 基于移动通信数据的用户移动轨迹预测方法[J]. 计算机应用与软件， 2013， 30（2）：10-13.

[5] Wiest J， H?ffken M， Kre?el U， et al. Probabilistic trajectory prediction with gaussian mixture models[C]//Proceedings of Intelligent Vehicles Symposium （IV）， 2012 IEEE. IEEE， 2012： 141-146.

[6] Song C， Qu Z， Blumm N， et al. Limits of Predictability in Human Mobility[C]//Proceedings of American Association for the Advancement of Science， 2010： 1018-1021.

[7] Qiao SJ， Shen D， Wang X， et al. A Self-Adaptive Parameter Selection Trajectory Prediction Approach via Hidden Markov Models[J]. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（1）： 284-296.

[8] 乔少杰， 李天瑞， 韩楠， 等. 大数据环境下移动对象自适应轨迹预测模型[J]. 软件学报， 2015， 26（11）： 2869-2883.

[9] Shi C， Yan Z， Wang Y， et al. A Genetic Algorithm for Detecting Communities in Large-scale Complex Networks[J]. Advances in Complex Systems， 2010， 13（01）： 3-17.

[10] Xiang L， Jiangshui Z， Jian M， et al. Feature Extraction Algorithm in Consideration of the Trend Changing of Track[J]. Journal of Computer-Aided Design & Computer Graphics， 2016， 28（8）： 1341-1349.