英语原文共 41 页
3.轨迹数据预处理
本节介绍了在开始数据挖掘任务之前处理轨迹所需的四项基本技术，包括噪声滤波，停留点检测，轨迹压缩和轨迹分割。
3.1 噪声滤波
由于传感器噪声和其他因素，比如在城市峡谷中收到较差的定位信号，空间轨迹永远不会完全准确。 有时，错误是可接受的（例如，车辆的几个 GPS 点落在实际驾驶车辆的道路之外），这可以通过地图匹配算法来修复（在 3.5 节中介绍）。在其他情况下，如图 2 所示，像 p5 这样的噪声点的误差太大（例如距离其真实位置几百米），以得出诸如行进速度等有用的信息。因此，在开始采矿任务之前，我们需要从轨迹中滤除这些噪点。虽然这个问题还没有完全解决，但现有的方法分为三大类。
均值（或中值）滤波器[Mean (or Median) Filter]：对于测量点zi，（未知）真实值的估计是zi 及其 n-1 个前驱在时间上的平均值（或中值）。均值（中值）滤波器可以被认为是覆盖时间上相邻zi 值的 Sliding Window。在图 2 所示的例子中，如果我们使用 Sliding Window 大小为 5 的均值滤波器，则。处理极端误差时，中值滤波器比均值滤波器鲁棒性强。均值（中值）滤波器适用于处理具有密集表示的轨迹中的各个噪声点，如 p5。然而，当处理多个连续的噪声点时，例如 p10，p11 和 p12，需要较大尺寸的 Sliding Window。这导致计算的均值（或中值）和点的真实位置之间的误差更大。当轨迹的采样率非常低（即
两个连续点之间的距离可能长于几百米）时，均值和中值滤波器不再是很好的选择。
Kalman 和粒子滤波器[Kalman and Particle Filters]：从 Kalman 滤波器估计的轨迹是测量和运动模型之间的折衷。 除了给出符合物理学规律的估计之外，Kalman 滤波器还给出了诸如速度等高阶运动状态的原理估计。虽然 Kalman 滤波器通过假设线性模型和 Guass 噪声来获得效率，但是粒子滤波器放宽了这些假设，以获得更一般但效率较低的算法。Lee 和 Krumm [2011]可以找到使用 Kalman 和粒子滤波器修复噪声轨迹点的类似教程的介绍。
粒子滤波的初始化步骤是从初始分布生成 P 粒子，j =1, 2, . . . , P。例如，这些粒子将具有零速度并且在 Guass 分布的初始位置测量周围聚集。第二步是“重要性抽样”，它使用动态模型 P(xi|xi-1)概率地模拟粒子在一个时间步长上的变化。第三步使用测量模型计算所有粒子的“重要性权重”。更重要的权重对应于更好地被测量支持的粒子。然后重要的权重被归一化，所以它们相加到一个。当从与归一化重要性权重成正比的 中选择一组新的 P 粒子时，循环中的最后一步是“选择步骤”。最后，我们可以通过 来计算权重和。
Kalman 和粒子滤波器模拟测量噪声和轨迹的动力学。然而，它们取决于初始位置的测量。
如果轨迹中的第一点嘈杂，则两个滤镜的有效性会显着下降。
基于启发式的异常检测[Heuristics-Based Outlier Detection]：虽然先前提到的滤波器在轨迹中用估计值替代噪声测量，但是第三类方法通过使用异常值检测算法从轨迹直接去除噪声点。噪声滤波方法已被用于 T-Drive [Yuan et al. 2010a，2011a，2013a]和 GeoLife [Zheng et al. 2009a 的; Zheng et al.2010]项目，首先根据点与其后继者之间的时间间隔和距离（我们称之为段）计算轨迹中每个点的行进速度。切断速度大于阈值（例如，300km / h）的片段，例如 p4 → p5, p5 → p6, 和 p9 → p10（图 2 中虚线所示）。假设噪声点的数量比普通点小得多，像 p5 和 p10 这样的分离点可以被认为是异常值。一些基于距离的异常值检测可以很容易地找出在距离 d 内的 p5 的邻居的数量小于整个轨迹中的点的比例。同样，可以过滤 p10，p11 和 p12。虽然这样的算法可以处理轨迹中的初始误差和数据稀疏问题，但是设置阈值d和p仍然基于启发式。
3.2 停留点检测
空间点在轨迹上并不是等重要的。有些地方表示人们停留了一段时间的地方，如购物中心和旅游景点，或加油车辆的加油站，我们称这种点为“停留点”。如图 3（a）所示，轨迹中出现两种停留点。一个是单点位置，例如，Stay Point 1，用户保持静止一段时间。这种情况是非常罕见的，因为用户的定位设备通常在相同的位置产生不同的读数。第二种类型，如图 3 （a）所示的“Stay Point 2”，更为普遍地观察到轨迹，表示人们移动的地方（例如，如图 3（b）和 3（c）所示）或保持静止但定位读数会转移。
有了这样的停留点，我们可以将一系列时间戳-空间点 P 的轨迹转化为有意义的地方 S，
因此促进了各种应用，如旅游建议[Zheng and Xie 2011b; Zheng et al. 2011c]，目的地预测[Ye et al. 2009]，出租车推荐[Yuan et al. 2011b, 2013b]和天然气消费量估计[Zhang et al. 2013, 2015]。另一方面，在一些应用中，例如，估计路径的行进时间[Wang et al. 2014]和行车路线建议[Yuan et al. 2013a]，这样的停留点应该在预处理期间从轨迹中移除。
Li 等[2008]首先提出了停留点检测算法。该算法首先检查定位点（例如，p5）与其后继者之间的距离是否大于给定阈值（例如，100m）的轨迹。然后，它测量定位点和距离阈值内的最后一个后继（即 p8）之间的时间间隔。如果时间间隔大于给定的阈值，则检测到停留点（由 p5，p6，p7 和 p8 表征）;该算法开始从 p9 检测下一个停留点。Yuan 等[2011b, 2013b] 基于密度聚类的思想改进了这种停留点检测算法。在找到 p5 到 p8 是候选停留点（使用 p5 作为定位点）之后，他们的算法进一步检查 p6 的后继点。例如，如果从 p9 到 p6 的距离小于阈值，则 p9 将被添加到停留点。
3.3 轨迹压缩
基本上，我们可以每秒记录移动物体的时间戳地理坐标。但是，这需要大量的电池电量和通信，计算和数据存储的开销。此外，许多应用程序并不真正需要这样的位置精度。为了解决这个问题，提出了两类轨迹压缩策略（基于轨迹的形状），旨在减少轨迹的大小，同时不会损害其新数据表示的精确度[Lee and Krumm 2011]。一种是线下压缩（即批处理模式），它可以在轨迹完全生成后减小轨迹的大小。另一种是在线压缩，当对象行进时，立即压缩轨迹。
距离度量[Distance Metric]：除了两种策略之外，还有两个距离度量来测量压缩误差：垂直 Euclid 距离和时间同步 Euclid 距离。如图 4 所示，假设我们将具有 12 个点的轨迹压缩成三个点（即 p1, p7 和 p12）的表示，则两个距离度量是连接 pi 和的段的长度的总和， 图 4（a）和 4（b）。后一距离假定在 p1 和 p7 之间行进恒定速度，通过时间间隔计算上每个原始点的投影。
离线压缩[Offline Compression]：给定由一系列时间戳点组成的轨迹，批量压缩算法旨在通过从原始轨迹丢弃具有可忽略的误差的一些点来生成近似轨迹。这与线简化问题相似，已经在计算机图形学和地图学研究领域进行了研究[McMaster 1986]。
一个称为 Douglas-Peucker[Douglas and Peucker 1973] 的著名算法被用于近似原始轨迹。如图 5（a）所示， Douglas-Peucker 的想法是用近似的线段代替原始轨迹，例如。如果替换不符合指定的错误要求（在本例中使用垂直 Euclid 距离），则通过选择贡献最大误差的点作为分割点（例如 p4），将原始问题递归地分解为两个子问题。该过程一直持续到近似值和原始轨迹之间的误差低于指定误差。原始 Douglas-Peucker 算法的复杂度为，其中 N 是轨迹中的点数。其改进实现了 [Hershberger and Snoeyink 1992]。为了确保近似
轨迹是最佳的，Bellman 算法[Bellman 1961]采用了一种复杂度为的动态规划技术。
在线数据缩减[Online Data Reduction]： 随着许多应用程序需要及时传输轨迹数据，已经提出了一系列在线轨迹压缩技术来确定新获取的空间点是否应当保留在轨迹中。在线压缩方法有两大类。一种是基于窗口的算法，例如 Sliding Window 算法[Keogh et al. 2001]和 Open
Window 算法[Maratnia and de By 2004]。另一个是基于移动物体的速度和方向。
Sliding Window 算法的想法是使具有有效线段的增长 Sliding Window 中的空间点适应，并继续增长 Sliding Window，直到近似误差超过某个误差界限。如图 5（b）所示，p5 将首先保留为 p3 的错误超过阈值。然后，算法从 p5 开始并保留 p8。其他几点可以忽略不计。与 Sliding Window 算法不同，Open Window 算法[Maratnia and de By 2004]应用 Douglas-Peucker 算法的启发式来选择窗口中最大误差的点（例如，图 5（b）中的 p3）到近似轨迹段。然后将此点用作新的定位点来近似其后继。
另一类算法将速度和方向作为在线轨迹压缩的关键因素。例如，Potamias 等[2006]使用从最后两个位置导出的安全区域和给定的阈值来确定新获取的点是否包含重要信息。如果新的数据点位于安全区域内，则该位置点被认为是冗余的，因此可以被丢弃;否则，它被包括在近似轨迹中。
压缩与语义含义[Compression with Semantic Meaning]：一系列研究[Richter et al. 2012; Chen et al. 2009]旨在在压缩轨迹时保持轨迹的语义含义。例如，在基于位置的社会网络[Zheng 2011]中，用户留下来的一些特殊点，拍摄照片或者改变方向将比其他显示轨迹语义含义更重要。 Chen 等[2009]提出了一种轨迹简化（TS）算法，其考虑了形状骨架和上述特征点。
TS 首先使用轨迹分割算法将轨迹划分为步行和非行进段（Zheng et al. 2008a]（见第 3.4 节）。
一个点由其航向变化度和与其邻居的距离加权。
另一个研究分支[Kellaris et al. 2009 年;Song et al. 2014]考虑了运输网络约束的轨迹压缩。例如，我们可以减少同一路段上的冗余点。只要移动物体在从定位点到当前位置的最短路径上行进，
我们甚至可以在定位点之后丢弃所有新获取的点。这个工作分支通常需要地图匹配算法的支持（参见第 3.5 节）。2014 年，PRESS [Song et al. 2014]被提出将轨迹的空间表示与其时间表示相分离。PRESS 由混合空间压缩算法和误差有限时间压缩算法组成，分别压缩轨迹的空间和时间信息。空间压缩将频繁的序列模式挖掘技术与 Huffman 编码相结合，以减小轨迹的大
小;也就是说，频繁行进的路径可以用较短的代码表示，因此可节省存储空间。
3.4 轨迹分割
在许多情况下，例如轨迹聚类和分类，我们需要进一步将一个轨迹进行分割。分割不仅减少了计算复杂度，而且使我们能够挖掘更丰富的知识，如子轨迹模式，从而超出了我们从整个轨迹中学到的知识。一般来说，有三种类型的分割方法。
第一类是基于时间间隔。例如，如图 6（a）所示，如果两个连续采样点之间的时间间隔大于给定的阈值，则将轨迹在两点分为两部分，即 p1 → p2 和 p3 → · ·
资料编号：[3931]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
