text: 基于历史数据的缺失路径恢复方法与流程
  轨迹数据的准确性直接影响了服务的质量，然而现实生活中由于各种因素，如设备电力、存储空间、在线传输成本等原因，GPS数据的采样并不是高频率的，即有大量轨迹数据采样间隔在1分钟以上。
  低采样率的GPS轨迹数据直接带来了用户行驶路径的缺失，这些数据的缺失将会极大地影响基于位置的服务质量，如路径推荐、路况预计、轨迹预测、频繁模式挖掘等与行驶路径有关的应用。
  对于这些缺失路径的轨迹数据，如果能够利用剩下的部分高采样率的轨迹数据对其缺失部分进行恢复，那么毫无疑问将会提高数据的利用率。
  现有路径恢复技术主要归纳为非数据驱动型与数据驱动型两类:
  (1)非数据驱动型的路径恢复技术:
  非数据驱动型的路径恢复技术仅仅根据道路网络特征对缺失路径进行恢复。
  具体地，一般通过定义路段的开销，如信号灯、转弯、道路等级等道路属性，最后选取开销最小的路径来补全缺失的路径。
  此类方法由于没有参考历史数据，根据人为设定的道路开销很难满足一些复杂的情况。
  (2)数据驱动的路径恢复技术
  数据驱动型的路径恢复技术不但使用道路的固有属性，还同时参考历史轨迹数据来进行推断。
  本发明属于这类技术。
  传统的数据驱动型的路径恢复技术分为两种，一种是扫描历史数据，通过将历史轨迹根据特定规则构建遍历图后，在图上进行最短路径查询。
  这种方法是基于经验式的，没有理论保障，且在某些情况下，该方法会退化为直接在原路网中使用最短路径补全，效果变差。
  另一种是利用最热门路径，通过从历史数据中找出需要恢复路径的首尾路段之间的最热门路径来作为缺失路径的恢复结果。
  这种方法在长距离的缺失下会产生一定的问题，且对历史数据的数量有一定的要求。
  是当路径的缺失距离变长后，历史数据中在缺失路径的首尾路段之间的轨迹数量也将减少，且路径的多样性也将会变多，导致热门路径的特异性不强，最终导致恢复结果不理想。
  本发明的目的在于针对现有技术的不足，提出一种在长距离的缺失情况下也能够保持算法的可靠性和准确性的基于历史数据的缺失路径的恢复方法。
  本发明提出的基于历史数据的缺失路径的恢复方法，具体步骤如下:
  1.训练阶段，根据历史数据训练模型参数
  2.在线查询阶段，利用训练好的模型对缺失路径进行恢复
  →s d ，作为恢复的缺失路径。
  其箭头表示路径方向，下同。
  本发明利用MDP模型对历史轨迹进行建模，通过将历史数据的后验概率最大化来得到模型代求参数R。
  在恢复缺失路径阶段，利用MDP模型得到道路之间转移的概率，对路径的概率进行马尔可夫假设，即路径的概率为相邻两条道路之间转移的概率的乘积。
  最终，将概率最高的路径作为缺失路径的恢复结果。
  本发明方法，参考了历史数据中蕴含的丰富的信息，利用概率论的理论推导，对轨迹数据使用了合理的模型进行建模，并根据历史数据训练模型参数，并对缺失路径利用进行恢复。
  整个方法，通过概率模型的理论基础保障，使得在长距离的缺失情况下也能够保持算法的可靠性和准确性。
  图3为实施例中几种方法在不同的缺失长度下的准确率
  下面结合具体实例来说明本发明的具体实施过程:
  1.根据历史数据训练模型参数
  (2)每个状态的初始回报函数定义为其道路长度，
  (d)计算，
  2.利用训练好的模型对缺失路径进行恢复
  (4)转移概率计算
  (c)计算每两个相邻状态之间转移的概率，如
  (5)构建图G
  s 17 }，
  下面通过真实数据集上的实验来验证路径算法的准确性，以及在长距离缺失下的有效性。
  我们使用葡萄牙共78万条出租车轨迹的数据集，通过对原数据进行人为消除路径后让算法进行恢复以检测其正确率。
  正确率的评判标准为总共恢复出的路径的长度比上总缺失的路径长度。
  我们使用了最短路径、最快路径、最热门路径，数据驱动型方法的最新工作(HRIS
  图3为这几种方法在不同的缺失长度下的准确率，可以看出，本发明方法在长距离路径缺失的情况下，依然具有很高的准确率。