在移动互联网、卫星定位技术、LBS技术高速发展的背景下, 无时无刻不在产生轨迹数据, 轨迹数据包括交通数据、人类移动数据、动物迁移轨迹数据和自然现象轨迹数据等.海量的轨迹数据具有很大的研究价值, 一般来说, 轨迹数据都具有时空序列性、异频采样性、数据质量较差的特征[1].通过对轨迹数据的分析, 可以挖掘人类活动和迁移规律, 分析车辆、大气环境等的移动特征[2].对于轨迹数据的分析与挖掘, 是研究人员重点研究领域之一.例如, 基于城市交通的轨迹数据处理能够为优化交通路线[3]、个性化推荐路线[4]、路网预测[5]、城市规划[6]等提供很好的解决方案.

另一方面, 海量的轨迹数据潜在性地暴露了个人的行为特征、兴趣爱好和社会关系等隐私信息.例如, 大量基于位置服务的轨迹数据存在着相互关联的轨迹行为, 这些数据的关联性与时空特征使得攻击者更容易挖掘用户的隐私信息[7, 8].连续变化的时空轨迹数据将更容易推断出用户行为模式与习惯, 同时, 攻击者根据用户的历史移动轨迹数据特征, 可以挖掘出其活动范围和活动场景[9].所以, 对于轨迹数据的隐私保护, 也是目前重点的研究内容.

大数据的迅猛发展和海量轨迹数据的出现, 对于计算性能和存储性能都提出了更高的要求.量子系统的独特特征, 使其具有经典计算不具有的量子超并行计算的能力, 同时使其具有强大的信息存储能力.虽然量子计算与量子存储硬件设备研究还处于起步阶段, 但是对于量子计算与量子存储的理论研究已经非常活跃[10].对于轨迹数据的挖掘过程使用的挖掘算法可以用量子算法进行代替, 很好地实现了大数据与量子计算的具体应用场景的结合.基于轨迹数据特征设计或改进量子算法, 有助于促进量子计算领域的发展.

本文关于轨迹数据处理关键技术重点介绍了轨迹数据挖掘、轨迹数据隐私保护、轨迹大数据支撑技术以及轨迹数据挖掘核心算法与量子算法这4个方面的内容, 目前, 许多研究人员针对轨迹数据处理技术进行了相应的总结与综述性阐述.许佳捷[1]等人从企业数据、企业应用和前沿技术这3个角度总结了目前轨迹数据处理的现状, 但是对于基于轨迹生命周期的轨迹数据处理方法相对缺少基本原理和基本概念的描述, 没有涉及到轨迹数据中轨迹隐私保护方面的内容.郑宇[2]系统地阐述了轨迹数据挖掘中的相关问题, 包括预处理、轨迹数据管理、隐私保护、轨迹挖掘、轨迹分类和轨迹异常检测等方面, 帮助研究人员较为全面地了解轨迹数据处理相关领域知识与方法, 但是对于轨迹数据隐私保护方面的介绍偏少, 没有进行相应处理方法的归纳与总结.特别是在大数据时代, 海量的轨迹数据和异构特性, 需要采用新的思路与方法来提高轨迹数据处理能力, 目前针对轨迹数据处理综述, 特别是轨迹挖掘方面的综述侧重于传统轨迹数据方法的介绍, 对轨迹大数据支撑技术没有相应的自底向上的总结.同时, 目前对于轨迹数据处理中某一特定领域研究的综述也很多, 如:Elgendy[11]主要阐述了结合语义特征对轨迹数据进行挖掘的方法; 文献[7, 12]则主要关注轨迹数据隐私保护从基于位置服务的隐私保护和轨迹数据发布两个方面进行归纳与总结, 分析了目前所采取的隐私保护的主要方法.王书浩等人[10]分类总结了大数据与量子计算相关算法研究, 并分析了未来量子计算在加速经典算法效率研究的发展趋势.本文通过整理与归纳目前关于轨迹数据挖掘、轨迹数据隐私保护方面的综述性文章与最近研究文献, 介绍了轨迹大数据处理相关支撑技术, 并且结合目前轨迹数据挖掘核心算法归纳其对应的通用量子算法方案, 为研究人员从轨迹数据挖掘、轨迹数据隐私保护以及轨迹数据挖掘核心算法与量子算法这3个方面的研究提供方法总结和研究思路, 并对这3个方面未来可能的研究方向进行探讨.

本文第1节对轨迹数据进行概要性描述, 概述轨迹数据特征与轨迹数据处理过程.第2节对已有的轨迹数据预处理方法进行总结.第3节针对轨迹数据查询类型和索引结构进行总结与对比.第4节对已有的轨迹数据模式挖掘进行总结.第5节对于轨迹数据隐私保护从基于位置服务的轨迹数据隐私保护和基于轨迹数据发布的隐私保护方法进行总结.第6节针对大数据环境下的轨迹数据处理介绍轨迹大数据存储技术、轨迹大数据处理新技术和可视化技术.第7节对轨迹数据挖掘中采用的经典算法相对应的量子算法进行总结.本文最后总结全文并展望未来轨迹数据处理需要解决的问题和热点研究方向.

轨迹大数据作为大数据的一种, 其丰富的数据来源与多样化结构符合大数据的3V特征, 即量大 (volume)、实时 (velocity)、多样 (variety).轨迹数据作为轨迹大数据处理的对象, 需要在充分了解其来源、特征与处理技术架构的情况下挖掘其中有价值的信息.本节介绍了轨迹数据概念与分类、轨迹数据特征和轨迹数据关键技术架构, 从整体上了解轨迹数据处理的架构与方法.

轨迹数据是具有时空特征的, 通过对一个或多个移动对象运动过程的采样所形成的数据信息, 一般包括采样点位置信息、采样时间信息、速度等.轨迹数据来源多样并且复杂, 可以通过GPS定位器、手机服务、通信基站、信用卡、公交卡等, 也包括射频识别、图像识别技术、卫星遥感和社交媒体数据等不同方式来获取.轨迹数据一般包括人类活动轨迹、交通工具活动轨迹、动物活动轨迹和自然规律活动轨迹[2].

(1) 人类活动轨迹数据包括主动式记录数据和被动式记录.主动式记录数据是人们在基于GPS定位技术的主动分享位置信息, 同时, 通过社交网络的照片分享、邮件来往等一系列活动轨迹也属于轨迹数据的一类; 被动式记录是用户在无意间开启基于基站定位服务而暴露了具有时空特征的轨迹数据, 同样, 用户的信用卡消费行为、公交刷卡记录等也可以汇聚成具有时空特征的轨迹数据;

(2) 交通工具活动轨迹是在城市环境中基于车载GPS技术的移动轨迹数据.例如, 出租车、公交车上的车载GPS记录了在城市的活动范围轨迹;

(3) 动物活动轨迹数据是为了研究动物迁徙特征、行为特征和生活习惯而通过传感器获取动物的活动轨迹数据;

(4) 自然现象活动轨迹数据是很多研究人员关注的研究领域之一, 通过收集的台风活动轨迹、海洋事件等来探索自然现象的活动规律.

轨迹数据符合大数据时代的3V特征, 即量大、实时、多样.轨迹数据采样由于受设备、采样、采样频率、存储方式等因素的影响, 其具有如下特征.

(1) 时空序列性.轨迹数据是具有位置、时间信息的采样序列, 轨迹点蕴含了对象的时空动态性, 时空序列性是轨迹数据最基本的特征;

(2) 异频采样性.由于活动轨迹的随机性、时间差异较大的特征, 轨迹的采样间隔差异显著, 例如导航服务的秒级或者分钟级的采样、社交媒体行为轨迹是以小时或者以天作为间隔的采样.差异性的轨迹增加了轨迹数据分析的难度;

(3) 数据质量差.由于连续性的运动轨迹被离散化表示, 受到采样精度、位置的不确定与预处理方式的影响, 给基于轨迹数据的分析带来一定的困难.

轨迹数据模型中, 各层次之间紧密联系, 原始轨迹数据存在很多数据冗余与噪音, 需要通过数据清理 (data cleaning)、轨迹压缩 (trajectory compression)、轨迹分段 (trajectory segmentation) 等预处理方式转化为校准轨迹.校准轨迹数据需要通过数据库管理技术进行轨迹索引与检索, 能够有效地存取.最后对处理后的轨迹数据进行模式挖掘、隐私保护等操作获取有价值的知识.其采用的关键技术如图 1所示.

轨迹数据作为轨迹大数据处理对象, 其预处理效果将直接影响轨迹数据挖掘的效果.同时, 针对不同的应用场景与挖掘目标, 采用不同的预处理方式具有重要作用.本节介绍了轨迹数据预处理中主要的方法, 包括原始数据的数据清洗、轨迹压缩和针对应用场景与挖掘目标的轨迹分段与路网匹配预处理方法.特别地, 提出停留点检测技术.一般对于轨迹数据的挖掘研究, 很多都是围绕轨迹停留点来展开研究.同时, 轨迹压缩技术在海量数据的分析中消减无用数据、提升数据分析能力具有重要作用.

轨迹数据清洗主要是为了剔除数据中的冗余点和噪音点.移动对象在静止和匀速运行状态下都会产生大量的冗余点, 其中, 移动对象在某一时间段驻留时间较长, 称为停留点 (stay point).人们往往在数据分析时关心的是数据中的停留区域, 而不是整个轨迹数据.例如, 文献[13]中对旅游路线热点区域和路线进行推荐, 挖掘其中热点区域和剔除冗余采样点.在基于速度的行为模式挖掘中, 往往关心的是基于速度划分的行为模式[14], 文献[15]通过基于速度的出行模式划分, 获取了用户行为模式与习惯.

噪音点是指由软/硬件设备异常导致的错误采样, 例如, 移动对象进入室内或其他干扰GPS接收信号而导致定位误差, 噪音点会极大地影响轨迹数据挖掘和分析的结果.本文定义轨迹数据清洗处理方法包括噪音滤波 (noise filtering)、停留点检测 (stay point detection) 等.

受到传感器噪声、物体遮挡等因素的影响而产生的轨迹数据噪音, 如图 2所示, 在轨迹中, p5点相对轨迹距离过大, 如果此类噪音点不进行处理, 将会影响后续的轨迹数据分析.噪音点的过滤一般来说有3种处理方式:基于中值或均值滤波、基于卡尔曼滤波和基于粒子滤波.

●  中值或均值滤波.对于一个测量点zi, 处理单个噪音点真值的估计是zi和其前n-1个轨迹点的均值或中值[2].中值滤波处理过程与均值滤波类似, 但在处理极端错误值时, 中值滤波要比均值滤波具有更强的鲁棒性.在密集轨迹中, 均值滤波或中值滤波能够很好地处理单个噪音点.但在处理多个连续噪音点时, 均值滤波或中值滤波并不能取得很好的效果;

●  卡尔曼滤波.Lee等人在文献[16]中详细介绍了卡尔曼滤波在轨迹数据预处理中的应用, 卡尔曼滤波包含测量模型与动态模型, 卡尔曼滤波相对中值或均值滤波处理连续噪音点具有一定的优势, 对于当前点的估计取决于先前的测量, 它可以包含更多的状态向量, 例如速度.文献[17]中对于GPS的汽车防撞系统, 利用扩展卡尔曼滤波处理不同情况下车辆行驶轨迹估计.但是卡尔曼滤波也存在一定的局限性, 例如, 它的动态模型是线性的, 对于移动对象受限于其预定义的路径, 很难用卡尔曼滤波来处理;

●  粒子滤波.粒子滤波也同样有测量模型和动态模型, 但是粒子滤波不需要卡尔曼滤波那样要求动态模型是线性的, 文献[18]利用粒子滤波处理基于移动终端的位置估计, 但是一般来说, 粒子滤波对于噪声滤波的处理效率不够明显.文献[19]中详细介绍了Rao-Blackwellised粒子滤波器在处理复杂系统中的优势, 通过实验, 其结果表明:Rao-Blackwellised粒子滤波器在轨迹数据处理中的良好适应性, 相对于卡尔曼滤波具有更好的性能优势.

时空轨迹中存在的轨迹点, 其重要性并不相同, 往往轨迹中某些点反映了人们一段时间的行为, 例如购物、观光某个旅游景点等.在轨迹数据中, 在某一时间区域或空间区域内产生某种行为的轨迹数据定义为停留点, 一般将停留点分为轨迹中停留点和环绕轨迹停留点, 如图 3所示的停留点1和停留点2.文献[20, 21]利用停留点检测技术探索城市领域中驾驶员的加油行为, 挖掘兴趣点与加油事件, 减少驾驶员等待时间和优化加油站布局.文献[22]结合停留点检测、频繁模式挖掘估计轨迹路径旅游时间.通过将轨迹数据转化为具有场景的停留点, 更加有助于对轨迹数据的分析.文献[23]结合停留点检测技术, 利用出租车轨迹数据优化乘客等待时间, 根据乘客到达时间和出租车的抵达与离开时间建立模型, 提出了在历史出租车轨迹数据中给定时间和地点预测乘客等待时间的方法.文献[24]结合停留点检测技术, 通过不同的轨迹策略, 提升出租车运行效率, 节约成本.在文献[3]提出的T-Drive系统中, 也很好地应用了停留点检测技术.

对于移动对象, 基于时间戳的轨迹记录可以采用秒级记录, 但是由于存储设备、计算能力等的限制, 轨迹数据挖掘不需要如此精细的位置定位, 通常需要采用轨迹压缩的方法来处理轨迹数据.

●  垂直欧式距离 (perpendicular Euclidean distance).

文献[2, 25]都提出了使用垂直欧式距离进行轨迹压缩, 如图 4所示, 采用垂直欧式距离, 将{p0, p1, …, p16}轨迹压缩成3个轨迹点, 每一个轨迹点pi都有一个时间戳ti.

●  时间同步欧式距离 (time synchronized Euclidian distance).

这是一种从轨迹数据约简算法中产生近似轨迹的新的误差方法, 其基于时间同步的轨迹计算方式来产生近似轨迹.假设一个初始轨迹有n个采样点, 当然可以将其视为有n-1个分段.如图 5所示, A, B和C是3个连续的时空位置点, 根据其前一个位置点A和后一个位置点C来计算B的时间同步欧式距离[26].定义如下:

其中, ${{{x}'}_{B}}={{x}_{A}}+v_{AC}^{x}\times ({{t}_{B}}-{{t}_{A}}), {{{y}'}_{B}}={{y}_{A}}+v_{AC}^{y}\times ({{t}_{B}}-{{t}_{A}}), v_{AC}^{x}$和$v_{AC}^{y}$表示速度向量.其中, $v_{AC}^{x}$和$v_{AC}^{y}.$

对于离线压缩方法, 给定一个轨迹, 轨迹由一个一系列完整的基于时间戳的点, 通过批量压缩算法丢弃一些可以忽略的轨迹点来获得近似轨迹, 著名的算法有Douglas-Peucker算法.文献[27]基于Douglas-Peucker模型建立轨迹点批处理模式, 但在很多真实轨迹数据压缩处理中, 却很难实现批处理模式.

郑宇在文献[2]中提到了在线数据约简 (online data reduction), 这一方法包括基于滑动窗口算法和开放窗口算法, 同时归纳了语义压缩 (compression with semantic meaning) 算法, 语义压缩需要结合具体的应用场景保留关键位置点.例如, 在基于位置的社交网络中, 用户可能在某些位置点拍照、改变轨迹方向等[28].关于语义压缩, 文献[29]也进行了深入研究.

关于轨迹压缩采用的方法有很多[30-32], 根据不同的场景需求与处理目标, 有针对性地建立轨迹压缩方法, 例如Song等人[33]提出的基于路网的轨迹压缩算法.

轨迹分段是对长时段轨迹 (例如以天或月为单位) 的合理切分与标注, 切分后的子轨迹段代表一次出行的记录.轨迹分段不仅降低了计算复杂度, 同时提供了更加丰富的知识.例如, 子轨迹模式挖掘, 轨迹分段的核心是理解时空移动特征, 轨迹分段的主要方式有基于时间阈值、几何拓扑和轨迹语义这3种基本策略[1].文献[13, 34]利用旅游者的经验和地点兴趣度推荐热门旅游景点, 利用历史数据学习获得停留点, 将原始轨迹数据分段, 极大地提高了挖掘效率.文献[35]融入频率权重来优化兴趣点挖掘模型, 结合轨迹分段思想挖掘兴趣点区域.

路网匹配[36]是结合轨迹与数字地图, 将GPS坐标下的采样序列转换成路网坐标序列.经过路网匹配后, 每个轨迹采样点都映射到一个路网位置.路网匹配对于评估交通流量、引导车辆导航、预测车辆行驶路线、从出发地到目的地之间寻找频繁旅游路线等具有重要的作用, 但是路网匹配是较为复杂的问题.路网匹配主要有在线和离线两种方式.

●  在线匹配更强调实时性, 当每一个GPS位置信息被接收时, 算法需要在路网中进行识别匹配, 该方法主要应用于车辆导航、追踪等;

●  而离线匹配主要针对静态历史数据匹配, 其精度要求更高, 只有整个行程数据匹配均已完成才提供匹配结果, 并且尽可能准确地匹配车辆行驶路线.

对于离线路网匹配问题, 文献[37]利用Dijkstra最短路径算法来确定轨迹与地图序列的距离, 从而实现轨迹匹配; 对于在线路网匹配问题, 文献[38]提出了使用坐标系观测用户位置的拓扑分析方法, 该方法假定没有预期行驶路线和任何速度信息.文献[39]提出了基于模糊逻辑理论的路网匹配算法, 针对不同密度和不同复杂程度的路网进行匹配, 其结果表明, 该算法精度较高.关于路网匹配研究, 也是目前研究人员研究的热点[40-43].

轨迹数据索引与检索对于轨迹数据库管理具有重要作用, 不仅对于传统关系型数据库, 包括目前主流的分布式存储系统都需要建立高效的索引结构和查询策略以提升存储和查询效率.同时, 不同模式的查询需要对应的查询算法与相似性轨迹测量技术.本节从轨迹查询类型和轨迹索引两个方面加以阐述, 以表格形式列出目前采取的主要轨迹距离测量方法和轨迹索引构建模型.

对于轨迹数据的分析都依赖于大量的查询操作, 根据用户定义的输出条件, 如轨迹长度、采样频率等, 返回用户所关心的轨迹数据, 典型的轨迹查询请求信息包括轨迹点信息查询 (P-query)、轨迹区域信息查询 (R-query) 和轨迹查询 (T-query)[44].

●  P-Query.轨迹点查询即请求获取满足预期时空关系的轨迹或轨迹段中的兴趣点 (POI) 信息.一般来说, 点查询是获取在轨迹段中每个点的邻近点.如文献[45]利用P-Query获取轨迹段中轨迹点a到轨迹点b的加油站信息.典型的查询算法有NN (nearest neighbor) 查询算法[46], 点查询也可以获取轨迹段中满足预期条件的所有兴趣点信息.此外, 当给出特定轨迹点时, 点查询可以请求获取轨迹中的段信息[47];

●  R-Query.区域查询是属于特定轨迹区域内查询轨迹段, 此类查询在交通分析、LBS服务中应用广泛, 在轨迹聚类中, R-Query也尤为重要[48];

●  T-Query.对于轨迹分类或聚类处理, T-Query可以从轨迹数据中获取相似轨迹.相似轨迹测量基于轨迹点距离, 即轨迹之间的相似性, 通常是通过某种聚集轨迹点之间的距离来衡量的.常用的方法有CPD (closet-pair distance)[49], SPD (sum of pairs distance)[49], DTWD (dynamic time warping distance)[50], LCSS (longest common subsequence)[34], EDR (edit distance on real sequence)[45]和ERP (distance with reak penalty)[51]等, 具体描述见表 1.

在移动数据库中, 海量的数据无法通过遍历数据库查询方式满足性能需求, 轨迹数据的高效检索依赖于数据索引, 索引结构可以提供快速和有选择地存取移动数据库中的对象, 这一功能一般来说, 空间数据库中常用的索引结构有R-tree及其扩展版本[52]、B-tree及其扩展版本[53, 54]、基于K-D树的索引技术[55]、四叉树索引结构[56]等.表 2列举了相关树结构及其介绍.

轨迹数据挖掘作为轨迹数据处理的重要组成部分, 为了分析与获取有价值的信息, 需要通过融合多种方法挖掘经过预处理的数据.本节将从轨迹数据模式挖掘与轨迹数据分类两个方面进行归纳, 其中, 轨迹聚类是众多模式挖掘快速提取有价值信息的基础.轨迹聚类在相似性测量、轨迹压缩等方面起到很大的作用.同时, 往往在数据挖掘中需要多种技术的融合, 例如轨迹聚类与轨迹分类的结合来标签未分类数据.

伴随模式挖掘是在轨迹数据中提取伴随的移动对象, 通过分析移动对象群体的行为特征和规律, 可以实现时空环境中的事故调查、群体跟踪等.代表性的轨迹模式主要有Flock[67], Convoy[68], Swarm[69], Gathering[70]等.

●  Flock.早期研究群体模式中只考虑单一时刻移动对象的行为特征, 要求在某时刻至少有m个移动对象在同一区域内, 并且移动方向是相同的, 但是并不适应实际应用.Gudmundsson等人[67]对于群体模式挖掘提出了新的定义, 即Flock模型, 其中, flock(m, k, r) 表示在一定数量的移动对象在给定半径的圆形区域内持续地移动, m表示群体移动对象的最小数量, k表示移动对象持续运动的最短时间, r表示移动对象所在圆形区域的最大半径.但是, Flock模型预先定义了区域形状和群体大小, 不能很好地适应实际;

●  Convoy.为了解决在伴随模式挖掘中对于移动对象群体大小和形状的限制, Convoy模型定义为获取基于密度聚类的任意形状的轨迹挖掘, 避免预先定义的空间阈值限定.模型要求一定数量的移动对象在k个持续时间内密度相连;

●  Swarm.Flock和Convoy模型在移动对象群体的定义上有很大的限制, 要求移动对象在持续时间内同时移动; 而Swarm是更加通用化的模型, 模型定义, 在一定时间内移动对象在任意形状区域内一起移动而时间不要求连续;

●  Gathering.Gathering模式是指在轨迹中模拟各种群体性事件, 如庆祝活动、游行、抗议等.通过有效的索引结构、基于位向量的快速模式检测算法等来解决群体性模式挖掘;

●  Traveling companion.Flock和Convoy模型需要将整个轨迹数据导入以便进行模式挖掘, 而对于轨迹数据流的分析并不适用.Traveling companion利用traveling buddy[71]数据结构, 只存储移动对象间的关系, 实现了Flock和Convoy模型的在线分析功能, 极大地减少了计算量.

频繁模式挖掘是从大规模轨迹数据中发现频繁时序模式, 例如挖掘公共性规律或公共性频繁路径等.一般来说, 轨迹数据中包含了位置、时间和语义信息, 所以时空轨迹频繁模式挖掘与传统的频繁序列挖掘有一定的区别.频繁模式挖掘在旅游推荐[72]、生活模式挖掘[73]、地点预测[74]、用户相似性估计[75, 76]等方面有很多应用.一般来说, 对于轨迹数据频繁模式挖掘可以分为如下几种方式.

●  基于简单分段轨迹挖掘方式.这种模式贴近于对于个体移动对象行为的分析, 文献[77]利用Douglas-Peucker算法处理轨迹数据, 通过简单线性方式分割轨迹, 利用最小支持度挖掘频繁模式轨迹.但是一般来说, 轨迹数据的处理往往关心的是轨迹中的兴趣区域, 而不是具体的轨迹采样点信息;

●  基于聚类的兴趣区域挖掘方式.该方式在旅游推荐等方面应用广泛[78], 首先通过不同轨迹聚类, 从中挖掘兴趣区域.文献[72]在数据预处理阶段将轨迹的采样点序列转化为兴趣区域序列, 预设兴趣区域的分类, 并且提出了3种不同模式的频繁模式挖掘, 通过实验表明, 可以更精确地识别轨迹模式;

●  基于路网匹配的频繁模式挖掘.这种模式更加贴近于在城市交通中的应用.首先, 通过路网匹配算法将轨迹数据转化为具有道路网络信息的语义轨迹, 结合路网轨迹进行频繁模式挖掘[22, 33].

对于频繁模式挖掘算法主要分为两种挖掘模式:一种是基于Apriori的频繁模式挖掘, 另一种是基于树结构的频繁模式挖掘.

●  基于Apriori的频繁模式挖掘.主要针对经典的Apriori算法进行改进, 加入时序特征, 并且根据不同应用场景进行相应的优化, 例如GSP[79], PrefixSpan[80]等;

●  基于树结构的频繁模式挖掘.此类算法主要包括基于Suffix Tree[22, 33], SubString Tree[77]的结构树模式挖掘。

移动对象经常有一些周期性的活动行为, 例如购物行为、动物的定期迁移行为等, 通过挖掘此类轨迹, 可以预测移动对象未来的行为.一般将周期模式挖掘分为完全周期模式、部分周期模式、同步周期模式、异步周期模式等.

●  完全周期模式.周期模式更加强调全局性, 强调整个行为过程中呈现周期性, 周期内每个时间点都影响整个周期[81];

●  部分周期模式.周期模式相对于完全周期模式更加关注局部周期特征[82], 在时间序列中, 部分轨迹点表现出某种行为或特征.但是对于部分周期模式挖掘, 经常受到冗余模式和计算效率问题的制约而影响挖掘效果.文献[83]提出了并行性部分周期模式挖掘算法, 有效地避免了冗余周期模式的产生, 同时也解决了海量数据计算问题, 提升了处理速度;

●  同步周期模式.周期模式按照周期间隔发生或者是在周期间隔的整数倍处发生[82];

●  异步周期模式.受到噪音数据的影响, 使得周期模式发生变化, 称为异步周期模式.文献[84]提出了异步周期模式的概念, 有效地解决了由于噪音数据影响对周期同步性带来的破坏.但是该算法不能挖掘多事件时间序列周期模式, 即, 一个时间点上不能同时发生多事件行为, 而且算法只能挖掘最长子序列.文献[85]提出了更加广义的异步周期模式挖掘算法, 实现了多事件的时间序列的周期模式挖掘;

●  其他.文献[86]提出了惊异周期模式 (surprising periodic patterns), 其主要基于信息增益理论的带有概率的周期模式, 时空序列中所有事件的每次发生具有不同的权重信息.文献[87]提出了广义信息增益方法和空位惩罚方法来处理部分周期模式挖掘, 在时间序列和空位惩罚方面, 这个新的指标可以无缝地适应不同频率的事件发生, 三角不等式保留的广义信息增益能够设计一种线性算法来挖掘任何一个重要的模式序列组合.由于周期性行为的复杂性, 存在时空噪声和离群点等.Li等人[88]提出了两阶段检测方法:首先, 通过聚类算法检测少量频繁访问点, 移动对象轨迹被转换成二进制时间序列, 通过利用傅里叶变换和自相关方法处理每一个时间序列, 每一个周期性点的值可以计算得出; 其接下来证明了可以通过从历史数据中使用分层聚类算法来分析周期性行为.

为了通过不同的移动对象获得代表性路径或公共倾向行为, 需要将相似轨迹聚合作为集群, 一般的聚类方法是利用一个特征向量代表一条轨迹, 通过它们之间的特征向量距离来确定其相似性.

Yuan等人[3]研发了T-Drive系统, 通过从轨迹数据中学习出租车的运行规律和经验, 为普通用户推荐更为便捷的路径与出发时间规划.

轨迹数据聚类的关键在于:根据时空数据特征, 设计与定义不同轨迹数据之间的相似性度量.关于轨迹数据距离测量在第3.1节已经列表给出.轨迹聚类在整个轨迹数据处理中具有很大的作用, 例如在预处理中进行轨迹压缩.根据轨迹数据时间维度要求的严格程度和轨迹相似性测量, 将轨迹聚类处理模式分为:

●  基于时间维度的相似轨迹聚类.挖掘整体轨迹相似性, 同时需要满足在轨迹点的时间维度必须一一对应相似.主要处理方法有基于欧式距离的轨迹聚类和基于最小边界矩形 (minmum boundary rectangle) 的轨迹聚类.1993年, Agrawal等人[49]提出了基于欧式距离的轨迹相似性测量, 文献[89, 90]通过采取离散傅里叶变换、离散小波变换预处理基于欧式距离的轨迹相似性测量.文献[91]改进了MBR表示, 提出了MBB (minmum boundary box) 平滑轨迹, 以更好地处理噪声影响;

●  基于轨迹相似性的聚类.侧重于整个轨迹特征的相似性挖掘, 降低了时间维度要求, 只要求轨迹记录点的时间顺序.一般利用DTWD[50]方式处理此类聚类;

●  局部多子轨迹聚类.侧重于整条轨迹中寻找多条子轨迹的相似性聚类, 而不是整条轨迹的相似性聚类.一般处理此类模式聚类采用基于LCSS, EDR, ERP的测量方法;

●  局部单子轨迹聚类.侧重于处理轨迹中的最大相似子轨迹, 降低了时间维度限制.Lee等人[48]提出了先划分后聚合的框架, 按照最小描述长度原则划分子轨迹, 利用基于密度的聚类方法处理.除此之外, 此类模式处理还有基于密度的聚类方法 (OPTICS) 和DBSCAN等[92];

●  轨迹点聚类.侧重于轨迹点的相似性处理, 进一步地, 不依赖于时间变化的轨迹, 即, 用一个时间点代表整个轨迹时间.一般处理方法有历史最近距离、Frechet距离[93, 94].

轨迹聚类在整个轨迹数据处理中尤为重要, 在轨迹压缩过程中, 通过轨迹聚类的方式减少轨迹数据挖掘的计算资源和存储资源的消耗.在无监督轨迹数据分类学习中, 首先需要通过轨迹聚类提取特征, 然后根据提取的特征进行数据分类.以上根据轨迹数据聚类的不同要求列出了主要的处理模式, 文献[95]中对轨迹聚类算法和轨迹相似度测量进行了很好的总结.首先, 对数据聚类算法进行了分类与归纳.同时, 系统化地介绍了轨迹数据算法, 从基于空间聚类、基于时间聚类、基于路网匹配聚类和语义轨迹聚类等方面进行介绍.轨迹数据聚类依赖于高效的原始数据存储索引结构和根据需要提供相应的查询算法, 本文第3节已对此进行了阐述与归纳.轨迹聚类在轨迹数据隐私保护中也有交叉应用, 如文献[96]将轨迹聚类应用于基于轨迹数据发布的隐私保护策略中, 其首先分析了轨迹数据隐私保护 (k, δ)-anoymity模型的局限性, 即, 无法获取轨迹数据动态变化不确定性特征且难以适用于真实环境, 其通过将轨迹数据转化为不确定区域进行聚类, 很好地融合了两种算法, 提升了隐私保护的效果.

到目前为止, 传统的基于轨迹点或轨迹相似性的研究已经比较完善, 目前, 研究人员对于轨迹数据聚类从场景上来说主要从语义轨迹聚类和基于路网匹配聚类方面进行研究.

●  语义轨迹聚类.语义轨迹通常在于人为地赋予其场景特征或行为模式特征, 在轨迹数据处理过程中, 人们关心的是轨迹数据代表的丰富的语义信息, 如其所在场景、轨迹速度、在某个轨迹点的运行模式等, 而轨迹数据本身不具备这样的信息特征, 通过语义信息能够更好地适应于真实环境.如, 目前人们通过语义轨迹聚类挖掘相似性用户[97]、推荐用户下一个目的地[98]以及轨迹数据中热点区域识别[99];

●  基于轨迹聚类的路网匹配.原始数据中的轨迹点映射在路网中会形成一个基于地图的用户行为轨迹集合.在真实的生活环境中, 存在着3种轨迹形态类型:第1种是自由空间的轨迹, 如鸟的飞行活动轨迹; 第2种是不确定环境的轨迹环境, 如公园或广场散步轨迹; 第3种是基于空间约束的轨迹, 即路网轨迹.在城市轨迹数据处理中, 往往轨迹聚类需要考虑复杂的路网信息.在本文第2.4节介绍了路网匹配相关技术, 文献[100]结合路网匹配和轨迹聚类算法提供了交通轨迹数据聚类和分类的框架即相似性测量、轨迹聚类、产生聚类后的代表性子轨迹、轨迹分类.文献[101]提出了NEAT聚类框架, 考虑路网环境限制、路网邻近度和交通流情况进行轨迹聚类, 该方法的性能优于一般的基于密度的轨迹聚类方法.

在大数据时代, 如何快速、高效地进行轨迹聚类, 是研究人员关注的重要问题.对于轨迹大数据处理中轨迹数据聚类采用的工具和算法模型将在第6节进行归纳总结, 本小节不再赘述.

轨迹数据分类的主要目的是区分轨迹或段的不同状态, 例如交通出行方式、人类活动等.一般来说, 轨迹数据种类繁多, 通过轨迹数据分类可以挖掘更多趋势性、价值性规律.一般轨迹分类主要分为3个步骤.

(1) 使用分段方法将轨迹分割成段;

(2) 从段中或者采样点中提取特征;

(3) 通过建立模型划分段或者采样点.

常用方法有动态贝叶斯网络 (dynamic Bayesian network, 简称DBN)、隐马尔可夫模型 (hidden Markov model, 简称HMM)、条件随机场 (conditional random field, 简称CRF) 等.文献[102]首先通过基于主成分分析 (principal component analysis, 简称PCA) 估计多变量概率密度函数, 使用高斯混合模型 (Gaussian mixture model, 简称GMM) 处理轨迹数据.但是GMM无法获取实体之间的时序关系和次序, 基于此种缺陷, 研究人员使用基于HMM算法处理轨迹数据.文献[103]提出了改进的HMM模型, 即SD-HMM模型, 在处理人类活动认知方面具有更好的适应性, 降低了整体误差率.使用HMM处理轨迹数据的研究还有很多, 如文献[104, 105].

文献[106]利用DBN提出了两层认知模型, 提出的模型相对于仅仅使用DBN模型, 算法在精确度方面表现显著.文献[107]提出了使用滑动窗口的人类动作轨迹分析算法, 通过DBN作为分类器进行分类推理, 相对于固定窗口的动作分割具有很好的适应性.

除此之外, 文献[108]提出了层次马尔可夫模型来推导用户日常行为特征, 使用Rao-Blackwellised粒子滤波器处理多层次模型.Abidine等人[109]针对挖掘人类活动行为比较了3种算法的分类精确度, 即C-SVM, CRF和LDA算法.通过比较发现, C-SVM识别效率更高.

海量的轨迹数据出现, 特别是个人用户轨迹数据, 必然会带来隐私泄露的风险.目前, 对于轨迹数据隐私保护的策略有很多, 在参考大量文献之后进行了相应的总结与分析.目前, 针对轨迹数据的隐私保护主要从两个方面考虑:第一是基于位置服务的轨迹隐私保护, 此类研究主要集中在基于LBSN (location based service network) 环境下的隐私保护, 在时间层面提出了更高的要求; 第二是基于轨迹数据发布的隐私保护, 此类数据保护侧重于数据发布之前的数据处理, 相对于前者, 在时间层面要求相对宽松.

本节首先对轨迹数据的隐私与分类进行了总结, 第5.2节主要阐述隐私保护的度量标准与技术分类, 为隐私保护策略选取提供衡量标准.在第5.3节和第5.4节, 分别对基于位置服务的轨迹隐私保护和基于轨迹数据发布的隐私保护进行概括和总结, 两方面的隐私保护技术主要集中于假数据法、泛化法和抑制法等进行阐述.

移动终端、全球定位系统 (GPS, AGPS) 的普及和移动互联网的发展, 促进了基于位置服务 (location based services, 简称LBS) 的发展.LBS应用的领域包括社交网络、兴趣点检索、交通检测等.对于移动用户来说, LBS提供了有价值的服务, 一般LBS分为快照LBS和持续LBS[110].对于快照LBS, 用户通过提交当前位置信息获取服务信息; 而对于持续LBS, 是在一定周期或按需获取基于位置的连续服务信息.在轨迹数据隐私保护中, 持续LBS保护一般来说尤为重要, 连续性的轨迹数据暴露将会被攻击者获取其行为习惯或者其日常工作场景.

同时, 发布轨迹数据给第三方或者公众进行数据分析, 同样存在隐私泄露的风险.综合分析多种文献, 给出如下一些定义.

定义1(隐私).隐私是指个人、机构等实体不愿意被外部知晓的信息, 例如个人的行为模式、兴趣爱好、健康状况等.

定义2(个人隐私).个人隐私是数据所有者不愿意透露的敏感信息, 如个人的收入水平、旅游计划、活动场景、生活习惯等.一般来说, 用户不愿意透露的或者容易暴露用户行为特征的信息都可以称为隐私.

一般来说, 将时空轨迹隐私分为数据隐私、位置隐私和轨迹隐私这3种, 下面将给出对3种隐私进行描述和采取的保护办法.

很多机构或者组织经常需要公布微数据 (microdata), 微数据是指在使用匿名方法后可被发布的数据集.为了防止个人信息泄露, 一些明显的标识符被移除或者代替, 例如姓名、号码等信息.但是通过利用其他个人信息数据集与特定信息数据集结合处理, 往往可以推导出隐藏信息.如图 6所示, 通过链接投票注册信息数据集与医疗信息数据集相关性别信息、出生年月和邮政编码, 就可以挖掘出用户的医疗信息隐私.这样的链接信息称为准标识别符 (quasi-identifiers)[111], 即, 属性的值加在一起可能会找出一个单独的记录.

因此, 数据隐私保护主要为了实现微数据的匿名化.目前, 研究人员提出了相应的数据隐私保护原则用来限制匿名化微数据的泄露, 包括k-匿名原则 (k-anonymity)、l-多样性原则 (l-diversity) 和t-相近性 (t-closeness) 原则.

●  k-anonymity.Sweeney等人[112]提出了k-匿名 (k-anonymity) 方法, 该方法主要通过概括和隐藏技术发布精度较低的数据, 使得每一条记录至少与数据表中其他k-1条记录具有完全相同的准标识符属性值, 从而减少链接攻击所导致的隐私泄露.但是文献[113]发现:除了链接攻击之外, 发布数据表还存在同质攻击和背景知识攻击的隐私泄露风险;

●  l-diversity.为了避免k-匿名中存在的同质攻击和背景知识攻击, Machanavajjhala等人[113]提出了l-多样性原则, 要求在每个等价类中至少包含有l个“well-represented”敏感值, 而且给出了熵l-多样性和递归 (c, l)-多样性模型, 有效地保证了单敏感属性数据集的隐私泄露问题;

●  t-closeness.若敏感属性在一个等价类中的分布和该敏感属性在整个表中的分布不超过某一个阈值t, 则称该等价类是t-相近性的; 若表中所有等价类都满足t-相近性原则, 则表示该表满足t-相近性[114].

在请求基于位置的服务中, 移动用户向LBS服务商发出位置请求服务来获取物理定点位置, 但是持续性地请求位置服务将会暴露用户的移动轨迹和相关行为特征.为了在连续性请求服务中保护隐私, 需要匿名化用户和对象数据集.基于位置的隐私保护主要有:

●  假位置 (false location).用户发送一个关联真实地点的假地点信息[115, 116], 这样在LBS服务提供商记录的是假地点而真实位置信息被隐藏, 但是隐私保护程度和服务质量与假位置与真实位置的距离相关;

●  地点转换 (space transformation).将地点信息转化为在查询和数据之间的空间关系已经被编码的其他空间[117];

●  空间匿名 (spatial cloaking).空间混淆主要是为了把用户位置信息隐藏在空间区域[118], 用一个空间区域来表示用户的真实的精确位置, 区域形状不限.同时需要保证满足k-匿名原则或者满足隐私保护要求;

●  时空匿名 (spatio-temporal cloaking).在空间匿名基础上加入时间维度, 在扩大位置区域的同时设置安全时间距离或者延迟相应时间[119].

一个空间轨迹是一个移动的路径或由一个移动对象的一系列地理空间位置组成, 一般一个轨迹T:p1→ p2→…→pn包含位置信息和时间戳, 即pi=(xi, yi, ti).具有空间和时间属性的空间轨迹可以被认为是很强的准标识符, 可以连接到各种其他类型的物理数据对象.

例如图 7所示的医学数据[12], 医院将病人的轨迹数据公布给第三方研究机构, 轨迹数据中不包含任何明显的标识信息, 但却包含了敏感的属性信息, 如HIV, Flu等.图 7中, RID=1的记录标识轨迹包含 (1, 5), (6, 7), (8, 10) 和 (11, 8).假设一个病人Alice在时间戳分别为2, 5时去了位置 (1, 5), (8, 10), 那么只有RID=1满足此轨迹, 所以可以100%地确定其患了HIV.所以, 即使处理过的轨迹数据, 仍有可能暴露用户的隐私.在LBS中, 用户的活动轨迹往往容易暴露其工作场景, 如其家庭地址等.因为即使其轨迹经过匿名化, 但却可以通过其他人的轨迹推导出来.

(1) 隐私保护度.

通过轨迹隐私披露风险反映.披露风险越小, 隐私保护度越高.披露风险是在一定情况下, 轨迹数据隐私泄露的概率.披露风险依赖于攻击者掌握的背景知识, 攻击者掌握的背景知识越多, 隐私披露的风险越大[7].

(2) 数据质量/服务质量.

在轨迹数据发布中, 经过隐私保护技术处理后, 发布数据的可用性越好, 数据质量越好.一般采用信息扭曲度来衡量数据质量的好坏, 在基于位置的服务中, 一般用服务质量来衡量, 以反映用户的LBS查询经隐私保护技术处理后获得服务结果的好坏, 一般由查询响应时间和查询准确性来度量.在相同的隐私保护强度下, 用户获得的服务质量越高, 说明隐私保护技术越好[7, 8].

(3) 开销.

采用隐私保护技术所带来的代价, 包括预处理和运行时存储、计算和传输代价.一般采用时间复杂度和通信协议的通信复杂度来度量.

综合基于位置服务的隐私保护和基于轨迹数据发布的隐私保护采取的技术, 将轨迹隐私保护分为3类.

(1) 基于假数据的轨迹隐私保护.

通过添加假轨迹对原始数据进行干扰, 同时保证被干扰的轨迹数据不发生严重失真.假数据方法简单、开销小, 但是容易造成数据可用性低.假数据分为假位置点和假轨迹:假位置即不发布真实位置, 用假位置获得相应服务; 假轨迹是通过假轨迹降低敏感信息披露风险.一般生成假轨迹有两种方法.

●  随机生成法.随机生成一条连接起点与终点、连续运行且运行模式一致的假轨迹;

●  旋转模式生成法.以真实轨迹为基础, 利用真实轨迹中某些采样点为轴进行旋转, 旋转后的轨迹为生成的假轨迹.

(2) 基于泛化法的轨迹隐私保护.

将轨迹上所有的采样点都泛化为对应的匿名区域, 达到隐私保护的目的.但在保护数据真实性的同时, 却造成计算开销较大.

(3) 基于抑制法的轨迹隐私保护.

根据具体情况, 有条件地发布轨迹数据, 不发布轨迹数据中的敏感位置或频繁访问位置.此类方法减少了开销, 但是会导致某些信息丢失.

用户在获取LBS位置服务时, 需要提供自己的位置信息, 虽然可以通过匿名化等方式处理位置信息, 但是不一定能够保护移动对象的实时轨迹隐私.攻击者可以通过其他手段获得实时轨迹信息, 例如在利用位置k-匿名模型对发出连续查询的用户进行位置隐私保护时, 移动对象匿名框 (cloaking region) 的位置和大小产生连续性更新, 那么将这些连续性位置信息连接起来就可以获得实时轨迹路线.

1.假数据法

●   Path Protection[115, 120].利用假数据法思想处理在LBS中从起始地到目的地的查询, 通过混合真假起始地和目的地来获取所需查询服务信息, 一定程度上保护了轨迹隐私;

●   Dummy[115].综合考虑多项指标, 产生与真实用户移动模式相近的哑元位置, 将哑元位置与真实查询一起发给LBS提供商, 以达到保护真实位置的目的.但是往往哑元位置与真实位置的特征差距较大, 攻击者很容易区分出来, 文献[121]提出了DUMMY-Q方法, 考虑查询上下文与用户的运动模型, 将真实查询隐藏.

2.泛化法

●   KAT[122].结合用户的历史位置数据来增强用户的位置隐私, 确保每个位置提供给服务商至少已经被K个不同的人访问过;

●   Path Confusion[123].利用期望距离误差量化攻击者估计用户精确位置的准确度, 通过路径干扰获取隐私保护, 定义应用程序对一组用户路径容忍的平均位置错误, 每两个用户路径接近时, 就干扰用户路径使其交叉, 以达到迷惑攻击者跟踪的目的;

●   Split-Generalization[124].将二维空间划分为大小相等的正方形“格”, 根据用户隐私需求, 将一个或者多个“格”定义成一个“划分”, 在划分交界处, 采用边界位置延时发布匿名区域策略, 提升了数据服务质量;

●  其他.为了增强连续查询隐私保护力度与基于攻击者先验知识的隐私保护的有效性, 需要尽可能地减小隐形区域.同时, 考虑用户个性化隐私需求问题, 文献[125]提出了位置模糊模型 (FBP), 允许用户通过制定一个用户所在的公共区域来表示隐私需求, 并将该公共区域作为用户的位置发给服务器, 以降低攻击者的攻击风险.利用泛化技术处理位置服务的轨迹隐私有很多方法, 如文献[126]提出的GLON

模型.

3.抑制法

●   Location tracking[127].基于LBS特征和区域访问对象的多少将地图上的区域分成敏感区域和非敏感区域:当移动对象进入敏感区域时, 将抑制或者推迟其位置更新; 而对于非敏感区域, 算法并不限制移动对象的位置更新.

4.用户身份替换

●  假名.一般主要使用k-匿名技术[112], 使得某个位置的用户有k个, 而且这k个用户无法用ID加以区分, 即使攻击者得到某个用户的位置信息, 也无法准确地辨别真正的攻击对象;

●  混合区 (mix-zone).在移动过程中攻击基于位置查询服务的用户的前驱位置或者后续位置时, 为了防止攻击, 通过在某一攻击者无法监控的区域内秘密进行身份标识的更换, 使其在离开该区域时, 攻击者无法将用户与掌握边界数据的用户相关联, 以此阻断攻击者的位置攻击.所以, mix-zone[128]可以看作是一个黑盒区域.虽然minx-zone能够抵抗以假名为关联的位置轨迹攻击, 但对于通过历史位置信息进行推断的攻击算法仍然存在不足.后续人们也提出了相应的改进算法[129, 130].

5.空间加密技术

通过对位置加密达到匿名效果, 一般来说, 其位置服务的效果与加密方法有关.空间加密技术在确保服务可用性的情况下不会泄露任何用户的位置信息, 实现了更加严格的隐私保护.根据文献[8]的介绍, 列出其中空间加密技术.

●   PIR[8].隐私信息检索协议 (PIR) 允许用户在服务器不知道其任何查询请求的情况下, 从数据库中秘密地检索所需信息.按照隐私保护度的强弱, 分为基于计算能力的PIR协议和基于信息论的PIR协议:基于计算能力的PIR协议通过降低理论上不可解或计算上不可行难题的复杂度, 来保证攻击者无法区分用户对不同数据项的访问; 基于信息论的PIR协议是保证攻击者无法区分用户对不同数据项的访问, 无论攻击者的计算能力有多强, 但是基于信息论的PIR协议仍然存在开销过大的缺点;

●   HilCloak[117].在K最近邻居查询处理中, 使用基于Hilbert曲线的位置匿名HilCloak将整个空间旋转一个角度, 在旋转后的空间, 用密钥H建立Hilbert曲线, 密钥只有用户和可信实体知道.用SDK (space decryption key) 和TDK (textual decryption key) 可信实体把每个兴趣点转化为Hilbert值并且上传至服务器, 用户将基于位置服务的信息经防篡改终端生成密钥H并且上传服务器请求服务, 服务器返回距H最近的Hilbert值.

基于轨迹数据发布隐私保护主要是轨迹数据发布前的数据处理保护其中的敏感信息, 利用假数据、泛化法、抑制法、关联规则隐藏等方式变换或剔除敏感数据.轨迹数据发布前的匿名处理主要遵循的是k-anonymity原则等, 关于此类匿名处理在第5.1.1节已有阐述.

1.假数据法

●   Dummy[131].对于轨迹数据发布前的敏感数据处理, 可以通过添加假轨迹的方式来降低隐私泄露风险, 同时也要保证被干扰的轨迹数据某些统计属性不发生严重的信息失真.在第5.2.2节介绍了基于假数据隐私保护的两种方法, 文献[131]详细描述了如何通过两种方式进行轨迹数据的隐私保护.

2.泛化法

●  km-匿名[132].该算法是基于k-匿名的改进算法, 用于降低数据发布中用户身份信息泄露的风险, k表示隐私保护强度, m表示攻击者已经掌握用户之前访问过的m个位置点相关信息.通过基于距离的计算方式实现匿名, 不需要在轨迹数据发布前了解准标识符属性的详细信息, 也不需要区分敏感信息与非敏感信息;

●  NWA[133].用不确定轨迹数据在相同的时间周期内组合k个共定位轨迹 (co-localized trajectories) 来形成一个k-匿名骨干轨迹.将同一时间区间内处于同一区域的至少k-1条其他轨迹聚类成一个k-匿名集, 一个轨迹k-匿名集合至少应包含k条处于同一区域的轨迹, 并转换为一条聚合轨迹, 这条轨迹中, 每个位置节点都是该时刻所有轨迹节点的算术平均值;

●  Anonymity-Reconstruction.文献[119]提出了Anonymity-Reconstruction算法, 将原始轨迹数据集泛化为一组k-匿名轨迹集合, 使得k-匿名轨迹集合每条轨迹都是多个k-匿名区域组成的有序序列; 之后, 对于每条k-匿名轨迹, 在每个时刻所对应的匿名区域中, 通过均等地选择k个原子节点, 不重复地选取一个节点并连接起来, 实现k条轨迹的重构.

3.抑制法

●  Data-Suppression[134].根据攻击者掌握的移动对象部分轨迹情况, 提出了抑制部分信息来保护用户隐私的方法, 该方法主要是将轨迹数据库D转换为D*, 使得攻击者A不能以高于Pbr的概率推导出轨迹上的位置属于某个移动对象;

●  Time-to-Confusion.文献[135]提出了time-to-confusion (TTC) 度量的基于信息论对时序性位置隐私保护的方法, 通过抑制某些节点, 使得相邻节点间的不确定性增加, 从而增强保护能力.

4.关联规则隐藏

利用数据挖掘的方式进行敏感信息隐藏, 也是目前研究的热点[136].Ataiiah等人[137]提出了重要规则、敏感规则、数据清理等概念, 他们认为:问题的解决可以通过降低给定规则或规则集的重要性来实现, 同时, 尽可能地不对其他规则的重要性造成影响.

在大数据时代, 轨迹数据面对多种数据源、数据质量低、数据量庞大、挖掘需求多样化等问题, 需要采用新技术提高处理能力.在过去几年里, 以MapReduce模型为代表的分布式并行处理架构成为处理海量数据的新手段.面对海量数据, 轨迹数据从原始数据预处理、数据模式挖掘、数据隐私保护以分布式并行思想处理, 将更加快速、高效地获取处理结果.轨迹数据处理经过多年的发展, 其算法模型、存储结构、隐私保护策略模型等已经十分丰富, 研究人员更加注重将轨迹数据当作对象来处理, 注重解决轨迹数据的运算效率与挖掘效果, 以及赋予其更多的场景特征.因此, 按照轨迹大数据中轨迹数据的存储、处理到可视化层次进行支撑技术说明和归纳, 并且列举了一些用作轨迹数据研究的公开数据资源.

目前, 成熟的轨迹数据存储主要依赖于关系型数据库, 例如Oracle, PostgreSQL等, 但是面对海量轨迹数据管理、高并发读写和扩展性等方面存在一定的局限性.目前, 作为大数据支撑技术, 即云计算技术, 对于大数据存储和管理提供了很好的解决方案.传统的轨迹数据存储主要存储的是静态数据, 大数据时代, 数据的异构性和动态性都对数据的存储格式和存储方法提出了很大的挑战, 以NoSQL技术作为支撑的一系列数据库的出现, 为解决海量数据的存储提供了新模式[138].目前, 一些传统的关系型数据库已经开始支持NoSQL技术, 例如PostgreSQL.当然, 轨迹数据的存储依赖于高效的索引结构, 关于轨迹数据索引结构的介绍在第3节已经进行了总结, 关于大数据环境下的轨迹数据存储, 本节主要介绍几种常用的非关系型数据库和相关文献.

●  MongoDB.作为分布式文件存储数据库, 其具有高性能、易部署、高并发读写等特点.MongoDB不仅扩展了传统关系型数据库功能, 同时支持MapReduce模型和地理空间索引, 可以很好地应用在轨迹数据存储方面.例如, 文献[139]利用MongoDB存储轨迹数据和索引结构, 该文介绍了MongoDB中如何对R-tree结构命名、定义存储内容和存储结构.再如, 文献[140]针对危险品运输路径规划处理问题, 采用MongoDB存储危险品事件和运输轨迹数据;

●  HBase.作为一个分布式、面向列的开源数据库系统, 由于其开源性在海量数据存储中使用广泛, 并且HBase是Hadoop的一个子项目, 因此, HBase的使用与使用MapReduce模型进行数据处理有很大关系.文献[141]针对轨迹数据特点提出了基于HBase的可扩展空间数据存储模型HBaseSpatial, 并且设计了分布式存储和索引模型, 其架构如图 8所示, 并通过与MySQL, MongoDB数据存储进行对比.随着数据量的增大, 其优势更加明显;

●  其他.目前, 针对海量数据存储开源化的分布式存储系统越来越受到欢迎, HBase和MongoDB都是开源化存储系统.再如, Cassandra数据库系统作为混合型的非关系型数据库, 也能够很好地支持海量轨迹数据的存储需求.在轨迹数据存储管理方面, 最重要的是对轨迹数据建立高效的索引结构和查询算法.如何能够快速地建立轨迹数据索引结构、如何能够快速地查询目标轨迹区域, 是评价数据存储管理模型的重要参考条件.以上介绍的是基于分布式磁盘存储的数据库系统, 目前, 针对多核处理器的分布式内存计算也在一定程度上解决了轨迹数据的高性能查询需求.文献[142]提出了针对轨迹数据特征的基于列的内存数据库存储模型, 分析了传统关系型数据库对轨迹数据存储存在的缺陷, 将数据库划分为帧的形式, 把同一时刻的所有移动对象位置存储在一起, 同时, 将内存数据对齐, 很好地提高了内存的吞吐量, 减轻了对CPU高速缓存的压力.

MapReduce在处理大规模数据集时具有很大的优势, MapRuduce通过分割数据到每个节点, 并且通过周期性地返回各个节点的结果来更新全局状态, 实现分布式并行计算和提高数据处理能力.Hadoop分布式系统基础架构促进了传统轨迹数据处理向大数据平台处理的跨越.目前, 基于Hadoop平台下的轨迹数据处理获得了很大的发展, 尤其是在基于轨迹数据的地点推荐和轨迹数据聚类方面有众多文献.

(1) 基于Hadoop的轨迹聚类

轨迹聚类在轨迹数据处理中十分重要, 关于轨迹聚类的相关介绍已在第4.1.4节给出.而通过基于Hadoop分布式架构改进传统聚类方法越来越受到关注, 文献[143]通过Hadoop平台优化k-means算法处理海量出租车轨迹数据, 其详细给出了MapReduce下的三阶段轨迹数据处理流程和获取目标结果的处理框架.利用平方误差准则评判聚类效果的质量, 其算法效率和准确率方面都优于传统的k-means算法和两阶段并行算法[144].文献[145]通过改进传统k-means算法将轨迹聚类分成Map阶段、Shuffle阶段和Reduce阶段, 聚类过程结合改进的动态时间规整算法 (dynamic time warping, 简称DTW), 即FCDTW.通过实验, 其结果表明, 其算法性能随着数据量的增大优于传统的聚类算法.文献[146]则通过改进基于密度的DBSCAN算法进行轨迹聚类, 实现了基于MapReduce架构的四阶段聚类方法, 即预处理、局部DBSCAN、获取需要合并的集群、全局集群处理这4个阶段.目前, 研究人员集中于改进传统聚类算法以更好地适用于在MapReduce架构下的轨迹聚类处理.同时, 轨迹聚类的效果也会受到轨迹数据预处理结果的影响.

(2) 基于Hadoop的模式挖掘

相对于传统的轨迹数据模式挖掘, 结合Hadoop平台的模式挖掘将更加适合处理海量轨迹数据, 提高数据处理能力.一般地, 基于MapReduce模型的模式挖掘主要解决基于分布式架构的数据索引结构和传统算法的分布式解决策略.文献[147]提出了基于MapReduce编程模型的频繁移动模式挖掘, 为了解决海量轨迹数据下的网格固定性分辨率的局限性和资源消耗过大的问题, 提出了使用基于网格的四叉树搜索方法, 利用MapReduce模型加速计算.文献[148]提出了基于Hadoop平台从大量不确定序列数据中挖掘隐藏模式的算法, 该文首先分析了传统的Probability Suffix Tree (PST) 无法处理海量的不确定轨迹数据的局限性, 提出了基于改进PST的uPSTMR算法和$\text{uPST}_{\text{MR}}^{\text{+}}$.基于Hadoop平台构建PST的目的是为了计算每个节点的条件概率分布, 同时需要检测其是否符合条件.为了避免挖掘不符合条件的模式和平衡分布式计算过载问题, 该文构造了一个渐进、多层次和迭代的uPSTMR处理海量数据, 减少了迭代次数和运算时间, 在uPSTMR的基础上, 提出了$\text{uPST}_{\text{MR}}^{\text{+}}$算法, 其使用二维数据结构存储临时数据, 有效地减少了数据扫描的次数.通过实验, 其结果表明, 提出的算法具有很好的扩展性和稳定性.

(3) 其他

Hadoop在轨迹数据其他方面也有一定的应用, 例如轨迹查询.文献[149]介绍了一种针对空间数据的SpatialHadoop架构, 采用简单的空间高层次语言、双层空间索引结构、基于MapReduce层的基本空间组件和采用一个3层基础空间操作, 即范围查询、k-NN查询和空间连接操作.该文也进行了相应的结果对比演示.

(1) Spark平台.

美国加州伯克利大学开发的类Hadoop MapReduce的通用并行计算框架, Spark启用了内存分布数据集, 能够很好地优化迭代工作负载, 而轨迹数据对于迭代式计算能力要求更高.其能够更好地处理轨迹数据模式挖掘.

(2) Storm平台.

Twitter发布的分布式、容错实时计算系统, 更加适用于流式计算, 提升了对实时性的计算要求.流式计算目前也越来越受到重视, 在轨迹大数据处理领域, 对于实时性要求高、无法事先存储轨迹数据的轨迹数据, 采用流式计算框架很好地解决了此类轨迹数据的处理需求, 如智能交通、LBSN位置推荐等.

NVIDIA推出的CUDA并行计算架构推动了人们在基于GPU上实现并行计算, 目前, 研究人员也使用基于GPU的分布式架构进行轨迹数据处理, 其在轨迹数据索引、模式挖掘等方面有诸多应用[150].

●  轨迹索引与查询.文献[151]将GPU计算应用到轨迹的距离阈值相似度搜索上, 改进了传统的索引结构, 即空间索引、时间索引和时空索引, 从而适用于GPU计算.通过实验, 其结果表明, 其计算速度超过传统CPU计算的15.2倍.文献[152]使用R-tree实现了基于GPU架构的并行空间查询处理.GPU主要用来加速处理R-tree的批量加载和空间窗口查询处理, 设计了适用于GPU上R-tree处理的数据分布模式.实验结果表明, 其处理能力超过基于CPU计算的10倍.文献[153]同样针对构建并行R-tree, 受到树的非线性拓扑结构和GPU的单指令多线程架构 (single-instruction multiple-thread, 简称SIMT) 在实际工程应用中的局限性的限制, 对比目前存在的基于GPU的算法, 加速性能最快约20倍.该文通过构建一个非平凡的自上而下的树结构和设计有效的空间数据结构, 其加速性能远远超过原始的加速能力, 进一步提升了GPU实际的应用能力;

●  轨迹聚类.文献[154]结合Fréchet距离提出了基于GPU的子轨迹聚类算法, 在轨迹曲线之间, 利用连续Fréchet距离作为衡量相似度的标准.该算法性能优势明显.文献[155]提出了改进的OPTICS轨迹聚类算法Tra-POPTICS, 并且提出了基于GPU计算的G-Tra-POPTICS算法.基于STR-tree轨迹索引结构实现CPU线程数据分配, 每个CPU线程同时产生基于Hyper-Q的任务队列, 这样, Hyper-Q能够执行GPU并行化操作, G-Tra-POPTICS能够并行化Tra-POPTICS的3个计算过程, 即计算本地最小生成树、形成全局最小生成树和从全局最小生成树中获取聚类结果;

●  模式挖掘.文献[156]提出了基于GPU挖掘热门区域, 采用弱准则和强准则进行轨迹热门区域处理.同时, 在数据处理中允许受约束的输入和输出轨迹路径.文献[157]利用GPU挖掘轨迹数据flock模式, 讨论了3种变异flock模式, 即maximal flock, largest flock和longest flock.通过真实实验数据运行和对比目前的算法复杂度, 其优势明显, 即使longest flock是NP问题, 但在并行化计算情况下, 算法处理速度十分优秀.

轨迹数据描述移动对象的空间位置和时间属性, 同时, 在语义轨迹中也存在移动轨迹点的相关属性信息.如图 9所示, 轨迹数据可视化技术可以更加形象地展示轨迹数据挖掘效果.数据可视化对于快速了解数据结果之间的关系具有直观效果, 目前, 很多学者开展轨迹数据可视化研究, 轨迹数据种类众多, 处理方法也不尽相同.海量的轨迹数据从产生到后期的处理结果, 结合一定的可视化系统, 将会帮助研究人员更好地找出移动对象的规律或行为特征信息.

在大数据时代, 交互式可视化对于帮助研究人员快速理解数据特征和解释具有重要的意义, 交互式可视化更加注重在可视化系统中参与调整参数、数据排序、数据提取、模型选择、结果展示选择等方面.结合可视化系统, 能够辅助研究人员从轨迹数据预处理、模式挖掘、结果表示等过程更加清晰地了解与交互式参与.关于轨迹数据可视化的研究有很多, 本节根据轨迹数据的处理过程并结合文献[158], 将轨迹数据可视化分为直接可视化、抽象可视化和特征提取可视化.

直接可视化是最为基础的轨迹可视化方法, 即, 轨迹数据直接导入后绘制每条轨迹.对于GPS原始数据集来说, 其有固定的数据格式, 当数据量不是很大时, 可以借助Google地图或OziExplorer实现原始数据的可视化功能, 如图 9所示.文献[159]主要解决轨迹路径的可视化问题, 以突出显示轨迹的空间位置信息.文献[160]实现了基于时间维度的二维轨迹可视化, 突出轨迹数据更加丰富的时间维度信息.文献[161]提供了一种三维语义轨迹可视化框架, 该框架可以查询轨迹数据和实现轨迹数据的可视化功能.同时, 该框架实现语义注释和自动视觉提示匹配, 该可视化工具对于语义轨迹挖掘具有很大的用处.直接可视化可以直接表达原始轨迹数据特点, 但却不适用于大数据可视化, 或者难以实现对原始数据的可视化.

首先对轨迹数据进行聚集或聚类, 保留重要轨迹数据, 剔除冗余数据, 根据处理结果后可视化显示.轨迹数据有时间维度属性、空间维度属性和描述轨迹数据移动对象的各种属性特征, 根据处理目标需求的不同, 可以将抽象可视化分为时间维度可视化、空间维度可视化等.

●  时间维度.可视化的目的是为了关注轨迹数据基于时间维度上的特征信息, 文献[162]利用可视化技术关注基于时间维度的轨迹数据类别全局和局部特征, 用户选择移动对象、地点并且关注其随着时间变化而发生变化的情况.但是其主要解决少量分类轨迹数据的可视化动态显示问题, 对于大量分类数据并不适用.该文也针对数据量大提出了针对性的解决方案.文献[163]基于时间维度对历史气候变化数据进行了可视化展示与分析, 利用全球经向地图标记气候变化状态, 其提供的Time Series Discs可视化分析工具包括基本三角模块和旋转三角模块, 基本三角模块从4个方面展示气候变化情况, 即行数据、列数据、块数据、斜边数据, 旋转三角模块能更好地展示区域整体气候状态的变化情况;

●  空间维度.轨迹的空间属性一般指移动对象在空间中的位置信息和周边的地理情况.将原始数据抽象化后, 联合轨迹数据空间分布特征, 形象化地展示轨迹空间特征.同时, 根据空间划分策略, 采用不同的图形表示方式辅助研究人员进行特征分析.文献[164]针对城市轨迹数据中的出租车轨迹进行了可视化分析, 建立了出租车轨迹可查询模式, 很好地处理了大量轨迹数据的可视化问题, 因而涉及到大规模数据的存储.该文分析了SQLite和PostgreSQL两种数据库在构建空间索引需要消耗大量时间的缺陷, 提出了基于K-D树的空间分割索引结构, 大幅度减少了出租车数据索引构建的时间消耗, 并且结合OpenGL和Qt技术进行可视化界面渲染;

●  其他.在对轨迹进行抽象化表示时, 根据特定的需求, 可视化显示出不同的结果, 例如只关心移动轨迹的起始位置和目的位置而忽略中间过程[165], 或者在路网匹配处理中往往关心的是抽象化轨迹路径而不是具体的轨迹点[166].

可视化应用的最终目的是辅助研究人员发现和分析经过挖掘后的数据特征结果, 能够更加形象地展示研究人员所关注的局部特征.按照特征提取可视化所关注的局部特征或全局特征, 分成局部特征可视化和轨迹模式分析可视化.

●  局部特征可视化.注重基于轨迹段的事件特征分析, 其中, 满足一定条件的时间段称为事件.一般地, 轨迹段包含时间和空间信息, 研究人员首先提取符合特定条件的轨迹段构成事件数据集, 再对基于轨迹段的事件数据进行可视化显示与分析.如:文献[167]首先将出租车轨迹数据预处理后匹配到路网中, 在面对多条路径选择的问题上, 根据始发地和目的地之间的路径历史数据分析出热门路径候选集, 再根据相关参数, 如路径时间花费, 推荐最优路径, 并且利用不同颜色在可视化系统中加以标识;

●  群体特征可视化.相对于局部和个体特征数据分析, 其主要从多目标多轨迹数据中提取行为特征, 同时可以挖掘出多轨迹之间的相互关系.如:文献[168]结合可视化系统, 从时间维度分析群体中个体行为特征、群体内的行为特征和群体之间的群体特征, 可视化系统提供的时间折线图很好地展现出群体性轨迹特征.

在轨迹数据处理中, 首先需要针对所要处理的轨迹数据集进行数据预处理、建模、分析与结果展示.因此, 不同的轨迹数据集所采用的方法是不同的.同时, 不同的数据集也有不同的数据特征.在大数据环境下, 原始数据的收集越来越受到重视, 一般的原始轨迹数据量基本上达到TB级、甚至PB级.因此, 轨迹数据已经成为一种重要的数据资源.目前, 已有不少公开轨迹数据集用于轨迹数据处理研究.郑宇在文献[2]中已经列举了7种公开数据集, 包括人类轨迹、出租车轨迹、签到轨迹等方面.本小节补充几条公开数据集, 以帮助研究人员根据不同需求快速获取所需要的公开数据集.

1. Gowalla签到数据

Gowalla数据集是一个基于LBSN网站的数据集 (http://snap.stanford.edu/data/loc-gowalla.html), 由社交网络数据和签到地点数据集组成.社交网络数据包括196 591个节点和950 327条边数据, 签到地点数据收集了

196 591个用户从2009年2月~2010年10月期间6 442 890个签到点数据.其签到数据格式见表 3.

2. Brightkite签到数据

Brightkite签到数据是基于LBSN网站的公开数据集 (http://snap.stanford.edu/data/loc-brightkite.html), 由社交网络数据和签到数据组成.社交网络数据包括58 228个节点和214 078条边, 签到地点数据收集了58 228个用户从2008年4月~2010年10月共4 491 143个签到点数据, 其签到数据格式见表 4.

3. FOILing NYC’s Taxi Trip Data

该数据集由两部分组成, 即Trip Data和Fare Data (http://chriswhong.com/open-data/foil_nyc_taxi/).两部分数据文件下的单个文件数据均在1.5GB~2.5GB之间.Fare Data存储的是出租车收费记录, 包括消费金额、付款方式、时间等信息.Trip Data中, 每个文件有1 400行数据, 每一行存储了经纬度信息、上下车时间和乘坐距离等信息.

4. Taxi Service Trajectory

kaggle竞赛平台发布的一个出租车轨迹数据, 该数据集包含2013年7月1日~2014年6月30日442辆出租车在Porto城运行的轨迹数据 (https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i/data).该轨迹数据集有包括GPS位置信息、时间戳、出租车标签在内的9个特征描述.

轨迹数据处理很重要的处理方式包括轨迹分类、轨迹聚类、轨迹频繁集挖掘等, 对于轨迹数据挖掘算法理论的研究不仅要考虑挖掘方式与挖掘目的, 更重要地, 受存储空间和计算资源的限制往往无法快速地获取轨迹数据结果.而量子计算的出现, 逐步从理论层面解决了海量数据存储与计算对于空间资源与计算资源的需求.目前, 关于量子计算算法的研究主要分为基于量子独有特性的量子算法研究和基于经典算法的量子衍生算法研究.其主要区别在于:量子衍生算法主要针对目前已有的基于经典计算机的算法, 通过引入量子信息理论优化算法结构, 提升算法效率.

而目前, 对于量子计算与大数据算法研究主要集中于通用算法研究, 而没有建立针对性的背景理论体系.轨迹数据由于其具有时空特征, 在大数据研究领域是重要的分支之一.所以, 轨迹数据的海量数据特征通过量子计算技术处理, 很好地实现了大数据与量子计算的具体应用场景的结合, 将丰富轨迹数据处理理论.目前还没有针对轨迹数据背景下的量子算法系统研究, 本节将归纳总结在轨迹数据挖掘中常用的挖掘算法利用量子计算方式的实现.主要从数据分类、数据聚类、频繁模式挖掘和量子衍生算法这4个方面进行阐述, 帮助研究人员结合轨迹数据特征设计或改进基于通用量子算法的量子轨迹数据处理算法.

轨迹数据分类就是确定目标对象属于哪一个预定的目标类, 具体来说, 分类是通过学习得到一个目标函数f, 把每一个属性集x映射到一个预先定义的类标号y上去.在轨迹数据分类算法中, 常用决策树、贝叶斯网络等算法, 在此列出目前研究人员对于基于量子理论的此类算法研究情况.

●  量子决策树 (quantum decision tree).

作为最经典的数据分类算法, 决策树在轨迹数据处理中具有很重要的应用.文献[169]对于决策树算法与量子计算的结合, 提出了基于量子信息熵的决策树算法; 针对经典熵不纯度评价, 提出了相应的量子熵不纯度评价准则; 同时, 运用Grover算法完成对节点信息的搜索, 实现量子决策树分类.

●  量子最近邻算法 (QNN)/量子k-最近邻算法 (QKNN).

NN/KNN算法是经典的轨迹数据处理算法, 根据待分类数据和样本数据的相似度进行数据分类, 一般常用的相似度标准有内积、欧式距离、汉明距离等.对于相似度测量, 文献[170]提出了用保真度Fid(|a〉, |b〉)=|〈a|b〉|2表示量子态|a〉和|b〉的相似度测量.文献[171]基于文献[170]提出了高维向量空间计算的量子算法实现, 缩短了计算时间, 并且提出了邻近质心方法.针对邻近质心算法在真实环境中的不适应性, 文献[172]提出了最近邻算法 (nearest-neighbor algorithm, 简称NN), 在噪声环境和高维特征环境因素下具有更好的鲁棒性.关于量子KNN, 文献[173, 174]进行了相应的研究.

●  量子贝叶斯网络.

量子贝叶斯网络相对于传统贝叶斯网络, 利用量子态概率幅和酉算子构建模型[175].量子贝叶斯网络由标记图和节点矩阵集合组成, 通过基于量子理论构建的贝叶斯网络和结合Grover算法提升了构建效率.同时, 贝叶斯方法在量子态分类方面也具有独特的作用.

●  量子隐马尔可夫模型.

文献[176]首次提出了量子隐马尔可夫模型, 相对于经典隐马尔可夫模型, 融入量子理论后的模型不仅包括经典模型, 同时提供了一个更加丰富的动态处理过程, 减少了针对一些随机过程的内在状态的必要数量.

将聚类分析的问题应用量子的方法进行优化, 主要有两种方法:第1种方法是直接在经典聚类方法中加入Grover搜索算法来改进计算性能, 第2种方法是利用统计力学知识或量子力学的原理来优化算法.其中, k-means算法是最经典的聚类算法.

由于Grover搜索算法相对于经典搜索算法具有很高的效率, 所以对于k-means聚类算法中的距离计算, 利用Grover算法通过黑盒算子计算量子态之间的距离, 提升了运算效率[177, 178].文献[171]讨论了基于绝热量子计算的k-means算法, 绝热量子计算实施统一的门操作, 不断调整量子系统中的参数, 降低了k-means算法中对于向量计算的复杂度.

根据量子力学原理, Horn等人[179, 180]提出了新的聚类分析算法, 在基于传统的尺度空间算法 (scale-space algorithm) 中, 使用Parzen窗估算量 (Parzen-window estimator) 的极大值来确定聚类中心.

关联规则与量子计算的结合, 将极大地减少时间消耗与空间消耗.传统的Apriori算法需要很大的计算资源, Yu等人[181]提出了对于关联规则中频繁2-项集的基于纯态的量子化算法.利用密度矩阵处理频繁数据集矩阵计算.文献[182]利用量子关联规则进行隐私保护研究, 将原始的垂直数据库分割成Alice拥有和Bob拥有, 利用量子随机访问存储 (quantum random access memory, 简称QRAM) 实现数据库模型, 通过构建的量子协议进行关联规则挖掘, 在时间效率和存储效率方面有显著提升.

目前, 关于量子衍生算法的研究非常多, 其基于经典计算机的非线性处理能力对于改进传统算法具有重要的作用.例如量子遗传算法, 其相对于传统遗传算法, 有效地避免了收敛速度慢、易陷入早熟的缺点.量子衍生算法侧重于对传统算法的局部优化, 对于轨迹数据挖掘来说, 在轨迹数据隐私保护、轨迹数据模式挖掘中融入量子衍生算法, 并且结合具体应用场景将会进一步优化和提升算法效率.但是一般来说, 对于量子衍生算法的使用需要结合具体背景, 某些情况下, 量子衍生算法并不能比传统算法取得更优的结果.

●  量子遗传/进化算法.

1996年, Narayanan等人[183]正式提出量子遗传算法, 用量子概率编码表示染色体, 利用量子更新门优化种群, 使种群朝着最优方向进行演化.2002年, Han等人[184]对量子遗传算法作进一步优化, 引入种群迁移机制, 提出了量子进化算法.对于轨迹数据处理来说, 量子遗传算法和量子进化算法在轨迹数据聚类方法优化和轨迹数据模式挖掘中具有重要的作用, 结合具体轨迹数据特征, 利用此类算法进行优化具有更好的效果.文献[185]将量子遗传算法应用于室内轨迹规划中, 利用量子叠加态编码控制规则和利用量子旋转门实现染色体的进化.实验结果表明, 其具有更好的寻优精度.

●  量子粒子群算法.

粒子群算法[186]作为一种优化工具, 其在数据分类聚类、数值优化计算等方面有重要的应用[187, 188].量子粒子群算法是Sun等人[189]在标准粒子群算法中提出的可以在整个可行解的空间进行搜索, 从而可以寻求全局最优解的方法, 其具有更好的全局收敛性和搜索能力.量子粒子群算法在数据聚类方面有很好的应用, 如Zhang等人[190]针对有障碍约束的空间数据聚类, 提出了基于量子粒子群算法和蚁群优化算法的空间聚类方法, 并且通过实验表明其优良的聚类特性.

轨迹数据处理是在移动互联网发展与LBS技术进步的背景下催生出的热门研究领域之一.本文从轨迹数据挖掘、轨迹数据隐私保护、轨迹大数据支撑技术以及轨迹数据挖掘核心算法与量子算法这4个方面归纳总结了近年来轨迹数据预处理方法、索引与检索技术、数据挖掘技术、隐私保护方式等方面的主要技术和算法, 重点阐述了目前关于轨迹数据挖掘方案和隐私保护策略, 分析了在大数据时代海量轨迹数据存储、分布式处理和可视化技术方面的发展情况, 并且延伸了未来量子计算在轨迹数据处理领域中的应用.目前还没有针对轨迹数据特性进行量子算法设计的研究, 因此, 本文介绍了轨迹数据处理中所使用的核心算法所对应的量子方案实现.本文旨在为广大研究人员快速和较为全面地了解轨迹数据处理关键技术提供帮助, 为研究人员从轨迹数据挖掘、轨迹数据隐私保护和针对轨迹数据特性的量子算法设计这3个方面进行研究提供思路与方法.在大数据时代背景下, 面对海量轨迹数据的处理是一项复杂而系统性的工作, 未来对于轨迹数据研究所面临的挑战可以从以下几个方面进行总结与展望.

(1) 基于多源数据融合的轨迹大数据处理

轨迹数据作为轨迹大数据研究的对象, 研究人员已经从轨迹数据预处理、索引建立与查询、模式挖掘、分类等方面开展了数十年的研究.随着以MapReduce为代表的分布式架构的出现, 研究人员希望更加快速地处理海量轨迹数据.同时, 不仅仅单一地研究轨迹数据处理, 需要融合其他领域数据来扩大轨迹数据处理的应用范围和研究轨迹数据背后的语义信息.因此, 大数据时代下的多源数据融合对于全面刻画数据特征和深入挖掘数据本质具有重要作用.例如, 在LBSN的快速发展下, 传统的单一分析某一类数据集的方法已经不能全面刻画移动用户的特征, 融合用户社交网络数据和轨迹数据将在用户推荐和地点推荐方面发挥更大的作用.

(2) 基于分布式的轨迹大数据处理

大数据时代下, 传统的单一处理模式和处理方法已经无法适应多源、异构、海量的轨迹数据, 分布式处理是目前提升海量数据处理能力的重要手段.根据不同的轨迹数据处理要求, 如何选择合适的分布式处理框架与处理算法, 是未来研究人员关注的重点.

●  首先, 针对静态轨迹数据, 以经典Hadoop, Spark为代表的大数据批量计算架构在处理静态轨迹数据方面具有较大优势, 静态轨迹数据处理是先存储后计算的计算过程, 通过历史轨迹数据的挖掘来获取有价值的信息.目前, 工业界在此领域研究得比较多;

●  其次, 针对动态轨迹数据, 以Storm为代表的大数据流式计算架构处理实时轨迹数据具有重要的研究意义.动态轨迹数据无法进行数据事先存储, 但要求近乎实时的计算, 因而在基于LBSN的位置推荐、朋友推荐和智能交通领域具有重要的应用前景;

●  另外, 基于GPU并行计算架构在高性能计算方面具有很大的优势.随着GPU的可编程性的增强, 并且其多线程机制和内置的大量运算单元, 使得基于GPU的数据处理能力甚至超越了基于CPU的数据处理能力, 数据计算在GPU中的运算效率远远高于传统的基于CPU上的计算效率.目前, 基于GPU的轨迹数据处理也是研究的热点之一.

(3) 基于深度学习的轨迹大数据处理

深度学习最近几年成为计算机多项顶级会议讨论的重点话题, 特别是2016年3月, AlphaGo击败韩国世界围棋冠军李世石, 研究人员越来越发现人工智能在数据处理中的重要性, 因而, 深度学习从传统的自然语言处理 (natural language processing, 简称NLP) 延伸到各个领域探索的研究方向.随着计算机性能的不断提升, 尤其是NVIDIA推出的CUDA并行计算架构促进了深度学习在GPU并行架构中研究的发展, 深度学习成为NLP、计算机视觉、图像处理等领域研究的重点, 推动了神经网络在GPU中的应用.目前, 深度学习已经很好地应用于社交网络社团划分[191], 以RNN (recurrent neural network) 为代表的深度学习模型在处理时序数据方面展现了优秀的性能优势.例如, 文献[192]基于RNN模型实现了对轨迹兴趣点的预测.由于传统RNN对于长序列轨迹数据处理效率较低, 文献[193]融合社交网络数据和轨迹数据, 利用RNN, GRU (gated recurrent unit) 模型, 更加精准地推荐相似用户和兴趣点.未来, 以RNN为代表的深度学习模型, 如LSTM (long-short term memory)、Attention机制, 在轨迹数据聚类、地点推荐和基于轨迹数据的相似用户推荐方面具有重大的研究前景.同样, CNN (convolutional neural network) 和DNN (deep neural network) 深度学习模型在基于轨迹数据特征分析方面也具有重要的研究前景, 如城市人流预测.

(1) 完善隐私保护评价体系与个性化保护

关于轨迹数据的隐私保护, 主要分为基于位置服务的轨迹数据保护和基于轨迹数据发布的隐私保护.在基于LBS技术的轨迹数据隐私保护方法或技术中, 缺乏系统化的隐私保护度评价体系与性能质量保障体系, 对于轨迹数据的隐私保护处理力度, 很大程度上影响到请求位置服务质量.同时, 不同的轨迹数据语义环境下如何提供个性化的隐私保护模式, 也是需要充分考虑的问题.

(2) 复杂环境下的位置信息加密技术

在基于位置服务的隐私保护方法中, 可以利用加密技术处理敏感位置信息.但是面对多种类、多数量移动终端和频繁位置更新数据的情况下, 加密性能必然受到影响.因此, 考虑优化加密技术的位置服务隐私保护策略也是目前需要关注的方向之一.另外, 某些LBS服务商不一定拥有自己的云平台, 而是将位置数据外包给云服务商, 普通用户向云服务商请求查询服务, 云服务商返回满足条件的查询结果, 这种模式可能导致非可信云服务商窃取、备份、篡改用户位置数据.传统的加密技术在范围查询、KNN查询方面有诸多限制, 所以对于基于外包云服务商特征的位置信息加密技术和检索结果完整性验证的隐私保护技术也值得深入研究.

(3) 完善敏感数据与非敏感数据处理机制

在传统的轨迹隐私保护中, 使用最广泛的是k-匿名模型, 通过泛化技术、抑制技术等方式对轨迹数据发布前的处理需要考虑如何提高敏感数据的保护效果与发布数据的质量之间的平衡关系.与基于位置服务的隐私保护策略相似, 需要考虑轨迹数据所具有的语义特征与攻击者的不同背景, 较好地处理敏感数据与非敏感数据, 在提升保护力度的同时, 保障数据发布质量也是重点研究方向.

(4) 基于多源数据融合的轨迹数据挖掘隐私保护

在大数据环境下, 面对大规模的轨迹数据, 攻击者往往可以通过多数据源的融合, 再通过连接攻击对匿名后的数据源进行攻击与推测个人敏感信息, 这方面也是需要解决的安全问题之一.目前, 利用数据挖掘方式处理数据隐私保护也是研究方向之一, 如本文介绍的利用关联规则隐藏算法降低轨迹数据中敏感信息支持度, 达到保护效果, 等等.

目前, 越来越多的研究人员关注大数据与量子计算的结合, 即量子机器学习.而轨迹数据的海量特征需要消耗很大的空间资源与计算资源, 量子计算的超并行特征与高存储能力对于轨迹数据处理的研究是值得关注的领域.轨迹数据的海量数据特征, 通过量子计算技术处理可以实现大数据与量子计算在具体应用场景的结合, 丰富轨迹数据处理理论.目前, 对于量子算法的研究主要集中于经典算法的量子方案实现, 而没有考虑到数据本身所具有的特征, 对于具体的应用场景没有系统地介绍算法的存储过程与计算过程.所以, 针对轨迹数据的时空特征进行量子算法设计 (包括量子衍生算法的研究) 将丰富轨迹数据处理技术与方法理论, 也是未来量子领域在轨迹大数据发展的重要研究方向.

●  基于量子特性的轨迹大数据量子算法设计主要利用量子固有的特性设计量子算法.轨迹大数据处理算法中, 很多基本算法可以通过量子算法实现海量信息存储与计算能力加速.量子算法设计需要从量子态制备、量子态存储、量子态测量和量子态超并行计算等设计完整的方案, 才能真正将经典处理算法量子化.因此, 实现轨迹数据特征信息的存储与计算是量子计算与轨迹数据结合的难点, 也是未来的发展方向之一;

●  以量子遗传算法为代表的量子衍生算法主要采用量子信息编码方式来优化数据结果, 在进行轨迹数据处理中融合量子衍生算法来进行数据处理, 一定程度上会促进数据处理优势与结果反馈, 同时也促进了量子衍生算法在轨迹数据处理领域的延伸.