面向情景感知计算的轨迹大数据挖掘技术

魏军林 韩楠 乔少杰 甘戈 温敏

摘要：以Internet应用、GIS、静态感知基础设施、移动及可穿戴设备感知的轨迹大数据挖掘问题为背景，将移动数据库作为研究对象，以大数据处理、情景感知计算、轨迹数据挖掘为主要研究手段，从模型通用性入手，利用情景获取技术提取复杂时空交互语义，建立情景表达和情景与时空数据关联模型，从主客观角度阐明时间、用户和社会情景因素对轨迹大数据挖掘准确性的影响，提出融合复杂情景信息的轨迹大数据挖掘新概念、特色理论及模型，为智慧交通、城市计算、大数据分析研究奠定理论基础。

关键词：轨迹数据库;时空计算;轨迹预测;GIS;大数据;情景感知计算

中图法分类号：TP311文献标识码：A文章编号：1672-9129（2018）06-0004-03

Techniques of Trajectory Big Data Mining over Context-aware Computing

WEI Jun-Lin¹， HAN Nan²， QIAO Shao-Jie³， GAN Ge⁴， WEN Min¹

（1.Sichuan JKC Geographical Information Technologies Co.， Ltd.， Chengdu， 610043）

（2.School of Cybersecurity， Chengdu University of Information Technology， Chengdu， 610225）

（3.School of Management， Chengdu University of Information Technology， Chengdu， 610103）

（4.Chengdu Municipal Public Security Bureau， Chengdu， 610017）

Abstract：This study focuses on the research of trajectory big data mining， where the data are obtained from the Internet applications， GIS， static sensing infrastructure and mobile and wearable devices. Aiming to analyze the mobile databases， we apply the big data processing， context-aware computing and trajectory data mining techniques. By taking into full consideration the generalization of models， we use the context acquisition approach to retrieve the complex spatio-temporal interaction semantic， create the context expression and context and spatio-temporal association model， clarify the effect of time， individuals and social contexts on the accuracy of trajectory big data mining from the subjective and objective aspect， and propose new concepts， specific theories and models by integrating complex context information to trajectory big data mining in order to set up the methodology on intelligent traffics， urban computing and big data analysis.

Key words：trajectory databases; spatio-temporal computing; trajectory prediction; GIS; big data; context-aware computing

1  引言

隨着互联网、传感网、物联网、云计算、移动计算技术的实现及应用，以及智能手机、车载移动终端等移动设备的普及，可以被人们访问和利用的数据呈爆炸式增长，包括：从Internet和Web的网页、图像及多媒体信息，到车联网、移动社交网络、微博等新兴互联网应用数据;从静态感知基础设施（如：移动网络、基站），到移动及可穿戴设备。最重要的是典型应用产生的大数据具有情景信息与轨迹时空数据契合的特点。情景感知应用产生和积累了海量、动态、异构、无规律、分布在系统各处的情景信息。而轨迹数据研究的最终目的是回答：“在何时（When）、何地（Where）、时空对象（Who或What）发生了什么样的变化（What）以及如何变化的（How）”，这与情景感知计算研究中的4W （Who、When、Where和What）非常契合。因此从时空特性角度，通过借鉴轨迹数据挖掘已有成果，研究情景感知应用中的海量数据具有重要的科学意义。

通过分析和挖掘情景感知设备，如：车载GPS、手机、公共交通卡等多源移动终端提供的轨迹行为信息，可以对个体行为模式（如：基于位置的服务、出租车异常轨迹检测、个性化旅游路线推荐）;群体及社会行为（如：智慧交通，城市计算）进行预测和模拟。针对轨迹大数据的管理和挖掘，已经成为当前学术界的一个研究热点。

情景感知计算（context-aware computing）^[1]源于普适计算，由Schilit提出，“指根据情景信息自动地为用户提供适合当前情景的信息或服务”，情景感知被认为是下一个智能科技新趋势 ，可以通过位置感知设备获得关于用户所处环境的信息，结合当时的时间、用户兴趣偏好和用户与系统的交互历史等信息，了解用户行为、发现用户真实意图，进而提供智能服务。情景感知计算被定义为一种新的计算形态，具有适应性、反应性、响应性、就位性、情景敏感性和环境导向性等特性^[2]，作为Context-Rich Systems中的核心技术被美国著名市场研究公司Gartner评选为2015年最具战略意义的十大技术，具有广阔的应用前景。

将情景感知计算技术应用于挖掘具有时间和空间特性的轨迹大数据是一个新的研究领域，具有很高的创新意义和研究价值，本文前期调研发现目前国内外鲜有相关技术成果报道。值得注意的是“2015年国家重点基础研究发展计划（973）和重大科学研究计划”将情感的计算与交互，面向信息空间、物理世界和人类社会三元空间的协同感知理论的基础研究作为重要支持方向。本文研究的关键技术：结合轨迹数据时空特性，设计融合情景信息的时空轨迹聚集模式发现及复杂环境下移动对象轨迹预测与国家重点基础研究发展计划指南中给出的研究内容“研究情感的计算与交互，空间信息数据、社会网络数据等的协同挖掘”高度吻合，说明本文研究具有重要科学意义。

2  相关工作

近年来，移动数据管理和挖掘技术成为国内外学术界与工业界共同关注的研究热点。2014年出版的《移动对象管理：模型、技术与应用》一书综述了移动对象管理和预测的最新研究进展，分析了现有轨迹预测研究工作仍然偏向预测简单的运动模式。由于多模式轨迹预测问题较复杂，现有的模型非常少，融合情景信息对位置精准预测未获得充分重视。下面分别从情景感知技术、移动行为模式发现、城市计算、轨迹数据挖掘、轨迹预测等方面介绍相关研究成果。

2.1  情景感知计算

情景感知是指系统能够根据用户的情景信息，向用户提供与其任务相关的信息和/或服务，重点是提升用户体验^[2]。情景感知计算是情景感知研究的主要工作，与普适计算、移动计算和智能计算密切相关，且这些前沿研究方向都与情景感知计算交叉，使情景感知计算具有广阔的研究前景与应用领域。谷歌Project Tango让移动设备通过先进的感应器来“理解”空间和运动，从而实现了3D扫描和室内导航等个性化体验。国内学者顾君忠最先开始“情景感知计算”的研究，在情景建模方法及情景感知系统框架方面进行深入的研究^[3]。近年来情景感知计算得到国内外学者的广泛关注。Perera等人^[4]对2001-2011年间50项代表性情景感知计算课题进行详细阐述，系统给出情景感知计算在物联网上应用的技术、方法、模型及系统。Khalid等人^[5]针对交通，会场距离，天气情况等情景因素建模并进行情景分析，利用社会关系过滤技术查找关键和权威人物。Fraile等人^[6]基于情景获取技术设计了一种能够根据患者生活的真实环境规划安全运动路线的多代理系统。国内学者的代表性工作包括：陈鹏^[7]对基于情景感知计算的时空数据管理、查询、分析算法展开深入研究，详细阐述情景感知计算关键技术。曹怀虎等人^[8]将用户的位置信息、环境特征、运动轨迹等情景引入到聚合算法中，智能地发现潜在的社交网络。近期，林一等人^[9]提出了增强现实浏览器系統中情景感知四层服务框架，并给出了其在寻路导航系统中的应用。

上述工作对情景感知数据建模，识别个体所处的真实环境信息，进而提供最优的服务或者进行智能决策，但是大多数工作主要针对小规模数据或者开发实验原型系统，当情景信息复杂、多变、大体量时，算法的性能无法得到保障。

2.2  移动行为模式发现

这一领域研究主要集中于在原始感知数据基础上识别个体行为，分析其行为特性和规律。美国东北大学发表在Nature上的工作^[10]，通过分析手机移动网络数据，发现人的运动轨迹具有高度的时空规律性，从整体上看用户的位移分布接近于幂律模型。MIT的Reality Mining项目^[11]通过分析不同国家、不同地域手机用户位置数据，理解不同文化背景人群的社会经济状态、生活节奏、移动性、对社会突发事件的反应。Lazer等人^[12]在Science上撰文分析大规模现实生活数据理解个体、组织和社会。Song等人^[13]在Science上发表了一篇介绍如何预测人类移动性的文章，通过测量个体轨迹的信息熵定量地给出了人类动态运动行为具有93%的可预测性。於志文等人^[14]指出：现有研究主要集中于识别个体简单的活动，对复杂行为模式的研究不够。此外，社会性方面的语义较少，如交互空间语义、细粒度关系等，这些因素都可以归结为情景感知范畴。此外，在个体行为识别上一般是采用有监督的学习，现有的方法通常需要样本训练，计算开销较大，不适合轨迹大数据中运动行为模式发现。

2.3  轨迹预测

轨迹预测作为移动数据管理中的关键问题一直得到国内外学者的广泛关注^[15]。Meng等人^[16]在《移动数据管理—建模，技术及应用》对移动对象建模、位置预测、索引查询、聚类和隐私保护等问题进行了详实的介绍。Ding等人^[17]提出了一种路网匹配的基于轨迹数据库的交通流分析方法，用于预测移动对象位置信息。

Qiao等人^[18]对移动对象轨迹数据进行分段处理，提出基于隐马尔科夫模型的轨迹预测算法及参数自适应调整策略。Qiao等人^[19]提出了一种基于频繁轨迹模式的轨迹预测算法，构建轨迹频繁模式树挖掘频繁轨迹模式。为了解决大规模轨迹数据处理和预测时间效率低下的问题，在文献[18]工作基础上对海量轨迹利用基于密度的聚类方法进行位置密度分区和高效分段处理，减少HMM的状态数量^[20]。为了解决分布式传感器网络中异构轨迹数据挖掘问题，Qiao等人^[21]组织一期SCI专刊介绍了当前分布式传感器网络数据中轨迹数据挖掘热点问题。近期，文献[22， 23]针对移动对象复杂多模式运动行为，利用高斯混合回归方法建模，计算不同运动模式的概率分布，利用高斯过程回归预测运动轨迹。

通过上述工作分析可知，现有研究工作中存在的突出问题是：并未深入考虑复杂情景下多模式轨迹预测所衍生的深刻挑战，而是分别针对简单模式开展研究工作，无法有效应对诸如轨迹预测算法的实时性、准确性、稳定性和可伸缩性的要求。而这些技术指标正是研究中所要考虑的核心问题。

3  轨迹大数据挖掘体系架构

轨迹数据挖掘是数据挖掘的一个新兴分支，近年来得到大型科研机构的广泛关注。2014年大数据应用案例TOP 100中浪潮帮助济南公安局搭建大数据平台，开展轨迹行为分析等多种大数据研判手段研究。微软亚洲研究院以郑宇为代表的课题组分析大规模车流轨迹数据在不同区域之间行驶特征，发掘现有城市道路网的不足;利用装有GPS 传感器的出租车感知交通流量，为普通用户设计最快驾车线路。上述案例进一步证明轨迹大数据挖掘的研究成果可以一方面解决具有挑战性的科学问题，另一方面可应用于真实移动行为分析案例中。本文立足于大数据处理层和数据挖掘层，通过抽取逻辑规则对不同的特征或情境信息进行集成，设计新型轨迹数据挖掘方法，获得智能决策信息，服务于应用层。

本文旨在从时空特性角度研究情景感知应用中的海量轨迹数据，利用轨迹大数据预处理技术提取情景感知数据特征并对轨迹大数据进行降维分析;利用情景感知计算技术获取复杂情景信息并构建语义网络，设计新型时空索引结构，提升轨迹大数据管理性能;设计基于相似性的层级聚类算法发现时空轨迹聚集模式，进而挖掘轨迹时空交互规律;结合情景信息与时空数据的关联，利用高斯混合模型、卡尔曼滤波等机器学习方法预测最可能运动行为。提出新的有特色的轨迹大数据挖掘方法。本文将面向情景感知计算的轨迹大数据挖掘体系定义为四个层次，如图1所示。

4  轨迹大数据的处理方法

轨迹大数据预处理主要包括三个关键步骤：

（1）情景感知数据特征提取。标准GPS数据包含时间、位置、状态和信号质量四类数据，可以从中获得包括用户情景和时间情景在内的初级情景信息，对于位置点之间的关系、用户当前活动、交通拥挤情况等高级社会情景，本文采用SVM和关联规则分析等技术进行深层次抽取，构建轨迹时空语义交互网络。

（2）轨迹大数据降维分析。对轨迹数据实现空间维度和时间维度的降维分析，空间维度通过分析路网中节点的介数（betweenness），减少路网中的区域或减少边，抽取关键节点和路径。此外，采用主成分分析技术将关键分量的分析获得全局特征，实现进一步空间降维。对于时间尺度的降维分析，设计找寻和量化移动对象的整体移动模式在各自时间片下显著差异的算法，进而实现精确的时间片划分，降低各时间段间的相似性。

（3）混合时空索引结构。本文采用如图2所示的混合索引结构，索引移动对象历史、当前和未来轨迹信息，实现轨迹及位置点的高效查询。图1所示的索引结构是一种基于历史树和基于双层索引结构的DISC-tree，历史树采用四叉树索引移动对象历史轨迹点，DISC-tree^[24]索引移动对象现在和最近将来的位置信息。同时，随着时间的推移，将DISC-tree的内容过渡到历史树中。此外，为移动对象的各段轨迹建立双向链表，当要查找某一移动对象的完整或者部分轨迹时，只要找到一段，就可以依據前向后向指针找到轨迹所有各段。这样既保证了历史轨迹的空间性，又实现了轨迹的连续性。

5  融合情景信息的轨迹聚集模式发现方法

将轨迹大数据处理后抽取的初级和高级情景感知数据作恰当的转换，转换成与模型相符的形态，通过情景过滤技术把影响应用的情景信息筛选出来，构建数学模型对不同情境特征融合，量化表达它们间的关联。利用兴趣点识别技术挖掘轨迹时空交互行为模式，构建用户&位置关联矩阵。

设计一种基于个体时空相似性度量方法对具有相似行为特征的轨迹聚类识别。算法利用用户&位置关联矩阵，基于个体位置、时间、环境特征、移动轨迹相似性的层次型聚类算法自下而上地把较小的cluster合并聚集。聚类过程分为两个阶段，1） 局部匹配，将轨迹划分成不同基本单元，给定一个距离阈值θ，如果两个基本单元之间的距离小于θ，则认为基本单元匹配;2） 全局匹配，计算任意两条轨迹的基本单元集合中局部匹配轨迹点的数量，如果大于给定的数量阈值ξ，则认为两条轨迹全局匹配。基于平移的最小Hausdorff距离的思想，不仅比较两个基本单元的形状及其蕴含的运动规律，而且能够消除一定范围内基本比较单元的公共偏差，提高聚类准确性。

6  复杂情景下时空轨迹预测模型

复杂情景下时空轨迹预测模型主要包括情景感知信息建模、轨迹热点区域挖掘和模型训练和学习预测过程，其技术路线如图3所示^[22]。下面将对轨迹预测的关键步骤给出详细的说明。

1）情景感知信息建模。利用关键值偶模型（key&value pair models）对时间和位置情景等简单情景信息建模;利用面向对象模型（object oriented models）对用户情景和社会情景等复杂情景信息建模，模型将每一种可能出现的情景因素组合映射为一种关于移动对象行为模式的状态，每一种状态信息能够充分反映动态情景的变化，与轨迹上不同位置点相对应，将移动对象的一条完整轨迹表示为一条包含复杂情景信息的状态链^[25]。

2）轨迹热点区域挖掘。提出基于频繁轨迹模式的热点区域挖掘算法，算法的主要步骤包括：a） 通过挖掘轨迹数据计算各轨迹片段的访问频率，获取频繁轨迹模式进而构建轨迹热点区域;b） 对轨迹进行划分，计算落在热点区域内的片段构造的完整轨迹。通过轨迹热点区域挖掘出包含单一和多种运动特征的轨迹模式。

3）模型训练和学习预测^[22]。结合情景感知信息，将单一运动模式利用高斯过程GP表示，而复杂场景中多种运动模式利用高斯混合模型GMM建模。a） 针对稀疏离散的轨迹大数据，利用高斯混合模型对轨迹数据利用概率密度函数建模，通过GMM对训练轨迹数据进行聚类分析;然后，利用EM算法估计相应参数，依据符合正态分布数据的条件分布得到多个高斯分量的回归函数;最后，将回归函数加权混合完成轨迹回归预测。b） 对于密集复杂的轨迹大数据，利用卡尔曼滤波算法计算的高效性，通过系统的状态空间模型以及观测模型，同时以最小均方差为准则，利用前一时刻的估计值和现时刻的观测值来更新对状态变量的估计，进而对下一时刻的轨迹预测^[26]。在卡尔曼滤波周期过程中存在两个不同更新过程，分别是时间更新和观测更新过程，时间更新过程根据前一时刻的最优状态估计预测出当前时刻下的状态，同时更新当前预测状态的协方差。预测出轨迹点之后，需要用观测值来进行线性拟合出最优估计轨迹点信息。

7  结论

本文针对轨迹大数据挖掘提出新的研究问题：1） 结合情景信息（时间情景、物理情景、用户情景、社会情景）挖掘轨迹数据中人类活动模式和预测空间移动行为;2） 基于个体行为相似性的轨迹时空聚集模式发现算法。利用情景感知计算技术结合轨迹大数据的时空特性、用户兴趣偏好、用户与系统的交互历史信息，来了解用户行为、发现用户真实意图、挖掘用户行为模式可以推动数据库及相关领域，如大数据管理、数据挖掘、GIS等多学科多领域交叉研究的发展。本文提出的方法在适当变通后，可应用于广泛的领域，如：环境监控，公共安全等民生应用。此外，可以将其扩展到现实世界挖掘、城市计算等实际若干类似的研究领域。

参考文献

[1]      Schilit B， Adams N， Want R. Context-aware Computing Applications. In： Proceedings of WMCSA94， Santa Cruz， CA， USA， 1994： 89-101.

[2]      Dey A K. Providing Architectural Support for Building Context-aware Applications[Ph.D. Thesis]. Atlanta： Georgia Institute of Technology， 2000.

[3]      顾君忠. 情景感知计算. 华东师范大学学报（自然科学版）， 2009， （5）： 1-20.

[4]      Perera C， Zaslavsky A， Christen P， Georgakopoulos D. Context Aware Computing for the Internet of Things： A Survey. IEEE Communications Surveys & Tutorials， 2014， 16（1）： 414-454.

[5]      Khalid O， Khan M U S， Khan S U， et al. OmniSuggest： A Ubiquitous Cloud-Based Context-Aware Recommendation System for Mobile Social Networks. IEEE Transactions on Services Computing， 2014， 7（3）： 401-414.

[6]      Fraile J A， Paz Y D， Bajo J， et al. Context-aware Multiagent System： Planning Home Care Tasks. Knowledge and Information Systems， 2014， 40（1）： 171-203.

[7]      陳鹏. 面向情景感知计算的时空数据管理、查询、分析与相关算法研究[博士学位论文]. 上海： 华东师范大学， 2013.

[8]      曹怀虎， 朱建明， 潘耘， 李海峰. 情景感知的P2P移动社交网络构造及发现算法. 计算机学报， 2012， 35（6）： 1223-1234.

[9]      林一， 刘越， 王涌天， 贺长宇. 一种增强现实分场景推送情景感知服务的方法. 软件学报， 2016， 27（8）： 2115-2134.

[10]    González M， Hidalgo C， Barabási A -L.Understanding Individual Human Mobility Patterns. Nature， 2008， 453（5）： 779-782.

[11]    Pentland A. Societys Nervous System： Building Effective Government， Energy， and Public Health Systems. IEEE Computer， 2012， 45（1）： 31-38.

[12]    Lazer D， Pentland A， et al. Life in the Network： the Coming Age of Computational Social Science. Science， 2009， 323（5915）： 721-723.

[13]    Song C， Qu Z， Blumm N， Barabási A -L. Limits of Predictability in Human Mobility. Science， 2010， 327（5968）： 1018-1021.

[14]    於志文， 於志勇， 周兴社. 社会感知计算：概念、问题及其研究进展. 计算机学报， 2012， 35（1）： 16-26.

[15]    Shaojie Qiao， Nan Han， Junfeng Wang， Rong-Hua Li， Louis Alberto Gutierrez， Xindong Wu. Predicting Long-term Trajectories of Connected Vehicles via Prefix-Projection Technique. IEEE Transactions on Intelligent Transportation Systems， 2017， 19（7）： 2305-2315.

[16]    Meng X， Ding， Z， Xu J. Moving Objects Management： Models， Techniques and Applications. Springer Press， 2014.

[17]    Ding Z， Yang B， Guting R H， et al. Network-Matched Trajectory-Based Moving-Object Database： Models and Applications. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（4）： 1-11.

[18]    Qiao S， Shen D， Wang X， Han N， Zhu W. A Self-Adaptive Parameter Selection Trajectory Prediction Approach via Hidden Markov Models. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（1）： 284-296.

[19]    Qiao S， Han N， Zhu W， Gutierrez L. TraPlan： An Effective Three-in-One Trajectory-Prediction Model in Transportation Networks. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（3）： 1188-1198.

[20]    乔少杰， 李天瑞， 韩楠， 高云君， 元昌安， 王晓腾， 唐常杰. 大数据环境下移动对象自适应轨迹预测模型. 软件学报， 2015， 26（11）： 2869-2883.

[21]    Qiao S， Jin H， Gao Y， Xing H. Trajectory Data Mining in Distributed Sensor Networks. International Journal of Distributed Sensor Networks， 2015（3， article 1）： 1-3.

[22]    乔少杰， 金琨， 韩楠， 唐常杰， 格桑多吉， Gutierrez Louis Alberto. 一種基于高斯混合模型的轨迹预测算法， 软件学报， 2015， 26（5）： 1048-106.

[23]    乔少杰， 韩楠， 丁治明， 金澈清， 孙未未， 舒红平. 多模式移动对象不确定性轨迹预测模型. 自动化学报， 2018， 44（4）： 608-618.

[24]    乔少杰， 韩楠， 王超， 祝峰， 唐常杰. 基于路网的移动对象动态双层索引结构. 计算机学报， 2014， 37（9）： 1947-1958.

[25]    乔少杰， 韩楠， 李天瑞， 熊熙， 元昌安， 黄江涛， 王晓腾. 一种基于空间编码技术的轨迹特征提取方法. 中国科学： 信息科学， 2017， 47（11）： 1523-1537

[26]    乔少杰， 韩楠， 朱新文， 舒红平， 郑皎凌， 元昌安. 基于卡尔曼滤波的动态轨迹预测算法. 电子学报， 2018， 46（2）： 418-423.