轨迹数据

1.轨迹数据在这一节，我们将轨迹的产生分为四大类，简单介绍了每个类别中的一些应用场景。轨迹数据代表了人的移动性能够帮助构建一个更好社会网络和旅行推荐。[152][154][156].（1）人的移动性：人们已经在很长一段时间被动或主动地以空间轨迹的形式记录了他们在真实世界的移动。主动记录：游客通过GPS轨迹记录他们的旅行路线，用来记住旅程还有和朋友分享。骑行者还有慢跑者记录他们的轨迹用来运动分析。在FLickr中，一系列地理标记的照片能够形成一个空间轨迹，因为每张照片都有该照片在何时何地拍摄的相应地点时间的一个地点标注和一个时间戳。同样，基于地点的社交网络中用户的“签到”，当按时间顺序排序的时候，可以被视为一个轨迹。被动记录：携带移动手机的用户无意中产生很多由蜂窝塔ID还有相应传输时间的序列表示的地点轨迹。另外，信用卡的交易记录也能表明信用卡持有者的空间轨迹，因为每个交易包含了一个时间戳还有一个商人ID来表示交易发生的地点。（2）运输车辆的移动性：大量装有GPS的车辆（例如出租车，公交，船，还有飞机）出现在我们的日常生活中。例如，主要城市的许多出租车已经配备了GPS传感器，是的他们可以以一定频率的报告带有时间戳的地点。这些报告形成了大量的空间轨迹，可以用来资源分配[127][129]，交通分析[104][125]，还可以提高运输网络[151]。（3）动物的移动性：生物学家已经收集了像老虎，鸟类的移动轨迹来研究动物的迁徙轨迹，行为还有生存状况[51][57].（4）自然现象的移动性：气象学家、环保主义者、气象学家和海洋学家都在忙着搜集一些自然现象的轨迹，如飓风，龙卷风，和洋流。这些轨迹捕捉到环境和气候的变化，帮助气象学家处理自然灾害并保护我们所居住的自然环境。2.轨迹数据预处理本节介绍了在开始挖掘任务之前处理轨迹的4种基本技术，包含噪声过滤，停留点检测，轨迹压缩，还有轨迹分割。3.1噪声过滤空间轨迹是从来没有完全准确的，由于传感器噪声和其他因素，如在城市峡谷接收比较差的定位信号。有时，错误是可以接受的（例如，远离车辆实际行驶的道路的车辆的一些GPS点），这可以被地图匹配算法修正（在3.5节介绍）。在其他情况下，（如图2所示），噪声点p5的误差太大（离它真实位置有几百米远）得不到任何有用信息（旅行速度之类的信息）。所以在开始挖掘任务之前，我们要过滤掉这些噪声点。尽管问题还没有被完全解决，现有方法情况下主要有三大类：均值（中心点）滤波：滤波窗口可以看成一个大小为N的滑动窗口，一个测量点和前N-1个测量点有关。中心点滤波在处理极限错误时鲁棒性更好。这种处理方式适用于处理密集点表示的轨迹中的独立点p5。当处理多重连续噪声点的时候就需要更大的滑动窗口。这将导致计算均值（或中心点）和该点真实值之间更大的误差。取样频率特别低的时候均值或中心点滤波不适合（因为采样频率低两个连续点之间距离就特别长。采用均值会有很大的误差）。卡尔曼粒子滤波：通过卡尔曼滤波估计的轨迹是运动和测量的一种折衷。除了服从物理规律外，卡尔曼滤波还给出了类似速度这种高阶运动状态的规则估计。卡尔曼滤波通过假设线性模型和高斯噪声起作用。粒子滤波器放宽这些假设会得到一个更普遍（但效率会更低）的算法。如何使用卡尔曼粒子滤波来修正噪声轨迹点在文献[53].粒子过滤的初始化步骤是从初始分布中产生P个粒子。这些粒子将有零速并用高斯分布在初始化地点测量聚类。第二步是“重要性采样”，采用动态模型来概率性地模拟粒子在一个时间步内如何改变。第三步对所有的粒子应用模型计算“重要性权重”。大的重要性权重对应于测量对粒子的支持度更高。重要性权重被归一化为和为1.最后一步在循环中是“选择步”，当从选择新的P粒子集合，按照第三步权重按比例选取。最后可以通过计算权重和。卡尔曼粒子滤波器，同时对测量噪声和轨迹的动态变化建模。然而，他们取决于初始地点的测量。如果轨迹中第一个点事噪声点，那么这两个滤波器的效率将显著下降。基于启发式的离群点检测：上面提到的过滤器都是用一个估计的值替换掉噪声点，第三类方法是用离群点检测算法直接从轨迹中移除噪声点。噪声过滤的方法已经被用在T-Drive[123][124][125]和GeoLife[145][153]项目中，首先根据时间间隔计算轨迹中每个点行进速度还有一个点和他的后继点之间的距离（我们把这叫做一个片段）。片段（在图2中可以看到），速度大于某个阈值会被舍去（例如300KM/h）。基于此噪声点就比正常点小得多了，分离的点P5，P10之类的被视为离群点。一些基于距离的离群点检测可以轻易找到P5在距离为d的邻居数目小于整个轨迹中点的p比例。同样p10,p11,p12，也能被过滤掉。虽然这样的算法可以处理轨迹的初始错误还有数据稀疏的问题，设置阈值d还有p也是基于启发式的。3.2停留点检测空间点在轨迹中并不是同等重要的。一些点表示人们停留了一段时间的地点，例如购物商场还有旅游景点，或者汽车加油的加油站，我们把这些点叫做“stayPoints”。像图3A展示的那样，在一个轨迹中有两种形式的停留点产生。一个是单独的点位置例如停留点1，用户在那停留了一段时间。这种情况非常少，因为用户的位置设备即使在同样的地点也经常产生不同的读数。第二种类型，像图3中的停留点2，这种在轨迹中更普遍观察到。代表着人们移动周围的一些地点。（例如图3中的B和C）或者保持静止但地点读数在周围变化。通过这些停留点，我们可以将一个轨迹由一系列盖有时间戳的空间点P转化为有意义的地点序列S，因此，促进多样性的应用，如旅行推荐[152][154]，目的地预测[116]，出租车推荐[127][129]，和天然气消费量估计[133][132]。另一方面，在某些应用中，例如估计一个路径的旅行时间[104]和驾驶方向的建议[125]，这样的停留点应在预处理过程中从一个轨迹中删除。李和郑等[54]首先提出了停留点检测算法。该算法首先检测在轨迹中一个锚点（例如P5）和他的后继点的距离是否大于一个给定的阈值（例如100米）。然后测量在距离阈值之间锚点与最后一个后继点（例如p8）的时间跨度。如果时间跨度大于给定的阈值，停留点（标记为p5,p6,p7,p8）就被检测到。算法又开始从p9检测下一停留点。元和郑等。[130][127]使用基于密度聚类的思想改进了此停留点检测算法。在找到p5-p8作为候选停留点后（使用p5作为锚点），算法进一步从p6检查后继点。举例来说，如果p9到p6的距离小于阈值的话，P9就被加入停留点。3.3轨迹压缩不每秒记录地理坐标，太费电，交流，计算，数据存储开销太大。为解决此问题提出轨迹压缩（基于轨迹形状）。目的新数据表达减少轨迹大小但是保持较高精度[53]。其一是线下压缩（块模式），产生完后再压缩。另一种是在线压缩，将轨迹当做移动对象立即压缩。距离度量：除了这两个策略，有两个距离标准来衡量压缩的错误：垂直欧氏距离和时间同步的欧氏距离。12个点，用3个点表示，p1,p7,和p12.两个距离度量片段长度和（P2和p2’;p3,p3’;p4,p4’;p5,p5’;p6,p6’）。先将三点相连，A为每个点做垂线。B假设p1和p7之间匀速，通过时间间隔投影每个点。线下压缩：给定所有点的集合，块压缩算法致力于通过舍弃拥有微不足道（小）错误的点得到大约的轨迹。很像线简化问题，这些在计算机图形学和制图研究社区学过。[68]比较出名的算法算法，来估计原轨迹。通过一条线段代替原轨迹例如p1p12，如果替换不符合错误要求，那么递归分，条件是对错误贡献最大的点来划分，第一个点为p4第二个点为p9，分分分，知道每条线与原轨迹的错误小于某个值。时间复杂度为o(N*N)，N是点的个数。改进算法达到o(N*logN)[39].保证估计轨迹可选，该算法运用了动态编程技巧（复杂度为O（N*N*N））。在线数据规约：许多应用实时性要求比较高，然后很多轨迹压缩技巧提出来了，决定新产生的空间点是否被保留。有两类在线压缩方法，其一是基于窗口的算法例如滑动窗口算法[46]和开放窗口算法[67].另一种方法是基于移动物体的速度和方向。滑动窗口算法是将空间点适应于拥有一个实线段的逐渐增长的滑动窗口，然后继续增长滑动窗口直到大致错误超出一些错误边界。如图5B所示。P5作为第一个停留点，p3的错误超出阈值（我觉得应该是开始有错误）。接着算法从P5开始然后保留P8.。（p1-p3,p1-p4,p1-p5）。其他点就可以忽略了。开放窗口算法[67]不同于滑动窗口算法该算法采用启发式的来选择窗口中错误最大的点p3用来近似轨迹段。然后再用这个点作为新的锚点，继续近似后继点。当进行在线轨迹压缩时，另一种方法使用速度和方向作为关键因素。举个例子Potamias等人[84]使用一个叫做安全区域，该区域由最后两个地点和一个给定的阈值形成，决定新产生的点是否包含重要信息。如果新点在安全区内，认为是个冗余点，舍弃掉。否则就缴入近似轨迹中。根据语义压缩：当进行轨迹压缩中一系列的研究[87][17]致力于保持轨迹的语义。在基于位置的社交网络【140】，用户停留的点，拍照或者方向改变较大的点在轨迹表达的语义意义中将比其他点有意义。陈等人【17】提出了一种轨迹简化算法（TS）考虑了形状，还考虑了前面讲的特殊点。TS首先使用轨迹分割算法【146】将轨迹分为步行和非步行片段。一个点根据他的朝向角和他与其邻居的距离衡量。另一系列研究【45】【90】考虑交通网络受限下的轨迹压缩。举例来说，我们可以减少同一路段的冗余点。只要移动物体在从锚点到当前位置的最短路径上移动我们甚至可以舍去所有新产生的点。这一系列工作经常需要地图匹配算法的支持（3.5节会介绍）。在2014年，PRESS【90】将轨迹的空间表达从他的时间表达中分开。Press包含了一个混合的空间压缩算法和一种带错误边界的时间压缩算法，分别压缩轨迹的时间和空间信息。空间压缩包括使用哈弗曼编码的频繁序列模式挖掘技巧。例如一个频繁的行进路径用一个短的编码表示，因此就能节约存储。3.4轨迹分割在很多场景下，例如轨迹聚类和分类，我们需要将轨迹分成片段来进一步处理。分段不仅能减少计算复杂性也使我们挖掘更丰富的知识，例如轨迹模式，这将比我们从整个轨迹中学到的多。通常，有3种分割方法。第一种基于时间间隔（可以说成时间片）。如图6A所示，连续采样点之间的时间间隔大于指定阈值就被分段，例如p1-p2,p3-p9。有时我们可以用相同时间长度来分段。第二种基于轨迹形状。如图6B所示，转向点朝向改变超出一定阈值进行分割。我们可以应用线简化算法，例如来确定保持轨迹形状的关键点，如图6C所示，用这些关键点将轨迹分割。李等人【51】提出了通过最少描述语言（MDL）来划分轨迹。由两部分构成，L(H)和L(D|H)。L(H)是分块段的总长度（例如p1-p7,p1-p9）,L(D|H)表示原轨迹和新分块轨迹的距离（垂直和角）。使用一种近似算法，找到轨迹中能最小化L（H）+L(D|H)的特征点。轨迹就被这些特征点分成片段。第三种方法基于轨迹中点的语义意义。图6D所示，轨迹根据其所包含的停留点被分成片段p1-p2-p3还有p8-p9。我们是否要保留划分结果中的停留点取决于应用。举例来说，在移动速度估计的例子中，在计程车停车等乘客的地方【125】，我们要从计程车轨迹中移除这些停留点。相反，要估计两个用户的相似度【52】，我们可以仅关注这些停留点序列，而跳过两个停留点之间的其他原生轨迹点。另一种基于语义意义的轨迹分割是将轨迹分成不同段的交通模式，例如驾车，乘公交，还有步行。举个例子，郑等人【144】【146】【149】提出了一种基于行走的分割方法。亮点是人们在不同的交通模式下转变。所以我们首先基于点的速度和及速度将轨迹中的步行点从非步行点中找出来。然后轨迹就能划分成步行段和非步行段，如图7A。但是实际上，如图B所示，一些非步行段的点可能被检测为步行点。例如当一辆公交车在交通拥堵时行进缓慢时。另一种情况是，因为定位错误，步行段的一些点超出了行进速度边界，因此就被认为是非步行点。为了解