论文部分内容阅读
随着经济的持续快速发展，中国汽车保有量的持续增长与有限的城市道路资源之间的矛盾日益加剧。在汽车保有量中，私家车所占比例尤为突出。在中国，据公安部的统计，截至2019年12月31日，中国汽车保有量已增加到2.6亿辆，与2018年底相比，增加了2122万辆，增长比为8.83％。随着汽车的持续增加，将进一步加剧城市交通拥堵等问题。随着定位技术，信息处理和数据挖掘等技术的发展，为获取私家车大规模的轨迹数据带来了便利。在当今的智能交通系统中，大规模的车辆轨迹数据具有很高的利用价值。在大多数情况下，广泛使用的GPS(全球定位系统)定位技术可以准确提供实时的车辆位置信息。
在当今的大数据时代，庞大的数据量达到了越来越难以理解的程度，而随着社会的不断发展，我们将拥有越来越多的数据集，尤其是汽车轨迹数据集。其中数据挖掘技术可以从大量的轨迹数据中提取有价值的信息，但是需要收集大量的高质量原始轨迹数据，但是庞大的轨迹数据将给存储，传输，查询，分析和挖掘带来巨大挑战。例如，原始轨迹数据在传输和存储方面会占用过多的网络带宽和存储容量，同时会增加传感器与服务器之间的通信数量和功耗。此外，海量原始轨迹数据的查询，分析和挖掘也将引起诸如延迟之类的问题，因此研发一种有效的轨迹数据压缩技术变得愈发重要和迫切。
轨迹数据压缩源自基本数据压缩技术。在简化多条线段的基础上，将原始轨迹替换为由多条线段连接的折线，并且通过简化折线以减少轨迹点。其中最原始的轨迹压缩算法只是减少轨迹点的数量，但是在线段简化过程并未考虑轨迹数据本身包含的各种重要信息，例如时间，速度，方向，位置等因素，因此通过大量简化轨迹信息，在压缩的过程中显著降低了存储压力。一方面轨迹压缩应基于保留重要的轨迹信息，而信息量少的轨迹点应被视为冗余数据，可以删除以达到压缩的目的；另一方面，如果保留的轨迹点太少，尽管有利于传输，存储等，但是由于轨迹数据中包含的信息严重丢失，因而使压缩轨迹无法表达原始轨迹，最后失去了轨迹压缩的意义，因此，轨迹数据压缩的要求是在考虑保留轨迹基本信息的基础上同时减少轨迹点的数量。
随着对轨迹数据的深入研究发现，许多的压缩算法是基于轨迹数据特征，例如在原始轨迹数据中保留具有重要空间信息的轨迹点。同时外部因素也对运动物体的轨迹数据产生影响，例如，出租车的轨迹受到道路网络结构和交通状况的限制。基于道路网络的轨迹压缩方法用于处理由受地理空间限制的运动对象生成的轨迹。对于实时更新的轨迹数据，还可以参考道路网络信息进行预判断，由于其压缩效率高，可以处理离线和在线轨迹数据。但是由于道路网络的限制，不可能基于道路网络处理轨迹数据。与此同时，随着语义概念的提出和发展，语义已经
逐渐引入并应用于轨迹压缩领域。研究中所收集的轨迹数据通常由纬度，经度，高度，时间和其他数据组成，但是由于轨迹数据不可视化，用户经常无法阅读和理解轨迹，因此可以使用一系列简单明了的描述来解释轨迹数据。通过使用标记，交叉点，转弯点等描述车辆的行驶轨迹，然后保存的这些语义状态或事件也可以大致表示运动对象的状态。基于语义的轨迹压缩将事件的整个轨迹数据进行分割，并且替换边缘位置的轨迹点，从而达到压缩目的。压缩后，仅保留相应移动对象的部分运动状态，从而大大减少了空间开销。尽管压缩的语义轨迹比原始轨迹更容易阅读和理解，但是原始轨迹的纬度，经度，高度和其他信息已经完全丢失，这影响了压缩轨迹的后续使用，同时对位置服务的应用支持不高，因此轨迹压缩方法的基于语义的应用有非常大的局限性。
本项研究是在实验室团队的基础上，联合了深圳市麦谷科技有限公司，进行的专项研究，并因此成立了专项研究实验室。基于以上条件，实验室团队和公司研发了一种集成的导航和定位系统。私家车轨迹数据主要是通过收集车载OBD位置终端设备。车载OBD位置终端设备由三个主要功能模块组成：带内置SIM卡的GPRS通信模块，GPS定位模块和OBD接口模块。它可以实时收集车辆轨迹数据，并在此基础上为车主提供防盗跟踪，电子围栏，行程管理和车辆故障诊断服务。私家车的轨迹数据涵盖了中国所有主要城市，本文在以上导航和定位系统的基础上，针对收集的轨迹数据，具体进行了如下研究：
(1)在结合了Viterbi算法和Baum-Welch算法的基础上，提出了一种了基于隐马尔可夫模型(HMM)的地图匹配方法。首先，我们确定与HMM模型的参数相对应的参数值。隐马尔可夫模型可以解决三种类型的问题。关于评估问题，对观察到的序列最可能的系统进行了匹配，并使用前向算法对其进行了求解。关于解码问题，我们需要确定最有可能产生观察序列的隐藏序列。在基于HMM的匹配算法中，对于每个GPS轨迹点，首先确定一组候选路段。每个候选路段在马尔可夫链中表示为隐藏状态，并具有观察状态概率，这是观察GPS点是否与候选路段匹配的可能性。如果发现GPS点非常靠近特定路段，则将较高的概率值分配给该路段。然后，计算连接马尔可夫链中每对相邻顶点边的权重，即状态转移概率。在马尔可夫链上找到具有最高观测状态概率和状态转移概率的最大似然路径。通常，使用维特比算法来解决该问题。关于学习问题，需要确定最有可能由模型参数提供的一系列观察结果。Baum-Welch算法用于解决此问题。Baum-Welch是Expectation-Maximization算法，用于训练HMM参数。在每次迭代中都使用前向和后向算法。该算法使用动态编程的原理来有效地计算两次获得后边际分布所需的值。前进和后退算法不用于训练HMM参数，而仅用于平滑：计算状态序列的边际可能性。Baum-Welch算法估计离散发射概率或与状态关联的均值和协方差。Baum-Welch算法可以运行给定的次数来研究模型的参数。在此过程中，可学习参数的内部表示在每次迭代后都会更新。转换提供的概率函数应从状态空间获取两个对象，并返回从第一个对象移至第二个参数的概率。由于这是在内部处理的，因此该函数无需进行标准化，即在所有状态下的总和为1。隐马尔可夫模型需要一个函数，当给出观测值和状态时，该函数返回某个观测值的发射概率。在基于地图匹配方法的隐马尔可夫模型中，实例化一个对象后，可以访问和估计诸如解码之类的方法，该方法返回估计的隐藏状态序列。在仿真中，假设以有向图的形式建立了道路网络，则所提出的地图匹配算法会将一系列点随机匹配到支路。在此仿真中，Frobenius范数用于评估所提出算法的性能。
(2)针对私家车数据的轨迹压缩问题，提出一种基于预测模型的轨迹压缩方法。在大多数情况下，私家车的使用反映了用户的出行需求，同时私家车的频繁移动也反映了用户的出行特征。私家车倾向于在特定区域驾驶，例如住宅区，工作场所和热门地点，因此，私家车的轨迹具有特殊的轨迹特性。基于用户行为，私家车的行驶轨迹在理论上可以相对稳定，因此基于预测模型的轨迹压缩是可能的。该方法将轨迹分解为两个组成部分-空间和时间轨迹信息，为此，提出了不同的预测算法。空间压缩算法使用部分匹配算法来预测路段。这个过程分为两个阶段：一个是根据历史数据生成预测模型；另一个是通过预测模型压缩轨迹。时间压缩算法还基于使用训练数据学习的预测模型，但是，目标不是预测路段，而是预测车辆的行驶时间。该实验是从2016年1月至2016年6月的六个月内，在深圳收集了6000辆设定目标私家车的轨迹数据集进行的。压缩方法是通过使用版本为3.6.3数据集，通过编译Python代码实现和测试的。该实验的数据集分为80％的轨迹用于训练，而20％的对象用于压缩。实验表明，基于预测模型的轨迹压缩的优点是可以帮助轨迹压缩具有更好的性能。提出的方法在针对真实数据集的空间和时间压缩方面实现了高压缩比。
在当今的大数据时代，庞大的数据量达到了越来越难以理解的程度，而随着社会的不断发展，我们将拥有越来越多的数据集，尤其是汽车轨迹数据集。其中数据挖掘技术可以从大量的轨迹数据中提取有价值的信息，但是需要收集大量的高质量原始轨迹数据，但是庞大的轨迹数据将给存储，传输，查询，分析和挖掘带来巨大挑战。例如，原始轨迹数据在传输和存储方面会占用过多的网络带宽和存储容量，同时会增加传感器与服务器之间的通信数量和功耗。此外，海量原始轨迹数据的查询，分析和挖掘也将引起诸如延迟之类的问题，因此研发一种有效的轨迹数据压缩技术变得愈发重要和迫切。
轨迹数据压缩源自基本数据压缩技术。在简化多条线段的基础上，将原始轨迹替换为由多条线段连接的折线，并且通过简化折线以减少轨迹点。其中最原始的轨迹压缩算法只是减少轨迹点的数量，但是在线段简化过程并未考虑轨迹数据本身包含的各种重要信息，例如时间，速度，方向，位置等因素，因此通过大量简化轨迹信息，在压缩的过程中显著降低了存储压力。一方面轨迹压缩应基于保留重要的轨迹信息，而信息量少的轨迹点应被视为冗余数据，可以删除以达到压缩的目的；另一方面，如果保留的轨迹点太少，尽管有利于传输，存储等，但是由于轨迹数据中包含的信息严重丢失，因而使压缩轨迹无法表达原始轨迹，最后失去了轨迹压缩的意义，因此，轨迹数据压缩的要求是在考虑保留轨迹基本信息的基础上同时减少轨迹点的数量。
随着对轨迹数据的深入研究发现，许多的压缩算法是基于轨迹数据特征，例如在原始轨迹数据中保留具有重要空间信息的轨迹点。同时外部因素也对运动物体的轨迹数据产生影响，例如，出租车的轨迹受到道路网络结构和交通状况的限制。基于道路网络的轨迹压缩方法用于处理由受地理空间限制的运动对象生成的轨迹。对于实时更新的轨迹数据，还可以参考道路网络信息进行预判断，由于其压缩效率高，可以处理离线和在线轨迹数据。但是由于道路网络的限制，不可能基于道路网络处理轨迹数据。与此同时，随着语义概念的提出和发展，语义已经
逐渐引入并应用于轨迹压缩领域。研究中所收集的轨迹数据通常由纬度，经度，高度，时间和其他数据组成，但是由于轨迹数据不可视化，用户经常无法阅读和理解轨迹，因此可以使用一系列简单明了的描述来解释轨迹数据。通过使用标记，交叉点，转弯点等描述车辆的行驶轨迹，然后保存的这些语义状态或事件也可以大致表示运动对象的状态。基于语义的轨迹压缩将事件的整个轨迹数据进行分割，并且替换边缘位置的轨迹点，从而达到压缩目的。压缩后，仅保留相应移动对象的部分运动状态，从而大大减少了空间开销。尽管压缩的语义轨迹比原始轨迹更容易阅读和理解，但是原始轨迹的纬度，经度，高度和其他信息已经完全丢失，这影响了压缩轨迹的后续使用，同时对位置服务的应用支持不高，因此轨迹压缩方法的基于语义的应用有非常大的局限性。
本项研究是在实验室团队的基础上，联合了深圳市麦谷科技有限公司，进行的专项研究，并因此成立了专项研究实验室。基于以上条件，实验室团队和公司研发了一种集成的导航和定位系统。私家车轨迹数据主要是通过收集车载OBD位置终端设备。车载OBD位置终端设备由三个主要功能模块组成：带内置SIM卡的GPRS通信模块，GPS定位模块和OBD接口模块。它可以实时收集车辆轨迹数据，并在此基础上为车主提供防盗跟踪，电子围栏，行程管理和车辆故障诊断服务。私家车的轨迹数据涵盖了中国所有主要城市，本文在以上导航和定位系统的基础上，针对收集的轨迹数据，具体进行了如下研究：
(1)在结合了Viterbi算法和Baum-Welch算法的基础上，提出了一种了基于隐马尔可夫模型(HMM)的地图匹配方法。首先，我们确定与HMM模型的参数相对应的参数值。隐马尔可夫模型可以解决三种类型的问题。关于评估问题，对观察到的序列最可能的系统进行了匹配，并使用前向算法对其进行了求解。关于解码问题，我们需要确定最有可能产生观察序列的隐藏序列。在基于HMM的匹配算法中，对于每个GPS轨迹点，首先确定一组候选路段。每个候选路段在马尔可夫链中表示为隐藏状态，并具有观察状态概率，这是观察GPS点是否与候选路段匹配的可能性。如果发现GPS点非常靠近特定路段，则将较高的概率值分配给该路段。然后，计算连接马尔可夫链中每对相邻顶点边的权重，即状态转移概率。在马尔可夫链上找到具有最高观测状态概率和状态转移概率的最大似然路径。通常，使用维特比算法来解决该问题。关于学习问题，需要确定最有可能由模型参数提供的一系列观察结果。Baum-Welch算法用于解决此问题。Baum-Welch是Expectation-Maximization算法，用于训练HMM参数。在每次迭代中都使用前向和后向算法。该算法使用动态编程的原理来有效地计算两次获得后边际分布所需的值。前进和后退算法不用于训练HMM参数，而仅用于平滑：计算状态序列的边际可能性。Baum-Welch算法估计离散发射概率或与状态关联的均值和协方差。Baum-Welch算法可以运行给定的次数来研究模型的参数。在此过程中，可学习参数的内部表示在每次迭代后都会更新。转换提供的概率函数应从状态空间获取两个对象，并返回从第一个对象移至第二个参数的概率。由于这是在内部处理的，因此该函数无需进行标准化，即在所有状态下的总和为1。隐马尔可夫模型需要一个函数，当给出观测值和状态时，该函数返回某个观测值的发射概率。在基于地图匹配方法的隐马尔可夫模型中，实例化一个对象后，可以访问和估计诸如解码之类的方法，该方法返回估计的隐藏状态序列。在仿真中，假设以有向图的形式建立了道路网络，则所提出的地图匹配算法会将一系列点随机匹配到支路。在此仿真中，Frobenius范数用于评估所提出算法的性能。
(2)针对私家车数据的轨迹压缩问题，提出一种基于预测模型的轨迹压缩方法。在大多数情况下，私家车的使用反映了用户的出行需求，同时私家车的频繁移动也反映了用户的出行特征。私家车倾向于在特定区域驾驶，例如住宅区，工作场所和热门地点，因此，私家车的轨迹具有特殊的轨迹特性。基于用户行为，私家车的行驶轨迹在理论上可以相对稳定，因此基于预测模型的轨迹压缩是可能的。该方法将轨迹分解为两个组成部分-空间和时间轨迹信息，为此，提出了不同的预测算法。空间压缩算法使用部分匹配算法来预测路段。这个过程分为两个阶段：一个是根据历史数据生成预测模型；另一个是通过预测模型压缩轨迹。时间压缩算法还基于使用训练数据学习的预测模型，但是，目标不是预测路段，而是预测车辆的行驶时间。该实验是从2016年1月至2016年6月的六个月内，在深圳收集了6000辆设定目标私家车的轨迹数据集进行的。压缩方法是通过使用版本为3.6.3数据集，通过编译Python代码实现和测试的。该实验的数据集分为80％的轨迹用于训练，而20％的对象用于压缩。实验表明，基于预测模型的轨迹压缩的优点是可以帮助轨迹压缩具有更好的性能。提出的方法在针对真实数据集的空间和时间压缩方面实现了高压缩比。