论文研究 一种针对稀疏数据进行路径预测的方法 .pdf

一种针对稀疏数据进行路径预测的方法，范恒飞，姚文斌，精确且及时的位置预测可以为车联网用户提供更好的服务，同时也可以预测道路车辆流量，甚至在某些情况下可以检测到一些潜在的危险图武获记义在线在车联网轨迹追踪中有重要的作用。城市道路指的是城市中的主干路网及某些可以通车的非主干路冈。该算法分为两个阶段:重要位置标点和路网标点。其流程如图所示:开始选取重要位置数据集中的位置记录其坐标信息重要位置是否都标记结束是从路网中选取条道路进行标点否是否所有道路均已标点二将所有固定点按照经纬度数值从小到大排列结束图城市地图顶处理流程图其中,对单条道路进行标点的过程为()记录道路开始位置的坐标信息()从当前点向前移动固定的距离,并记录其坐标信息()查看当前坐标点与道路结束位置距离是否小于()中的固定距离()查看相邻两个固定点间是否有多个路段()对连个相邻固定点间有多个路段的,对两点间所有路段用更小的了粒度进行递归标记。该过程如图所示:图武获记义在线开始记录道路开始位置的坐标信息从当前点向前移动固定的距离,并记录其GPS坐标信息当前点是否为道路终点,或距离终点距离小于分段固定值是两点问所有路段用更小相邻两个固定点间是否有多个路段二>否的了粒度进行递归标记是结束图单条道路标点流稈图对地图进行预处理后,得到了一系列的固定点,用这些固定点来描述地图。将地图预处理后产生的固定点先按经度从小到大,再按照纬度从小到大进行排列,并存储起来。地图匹配地图匹配是将原始车辆轨迹转换为道路信息,将其与嵱网联系起来的过程。的地图匹配算法,基于中的地图预处理结果进行的。对于原始轨迹上的每个坐标点,查找距离其最近的中得到的地图固定点。查找算法的过程为:()使用轨迹原始坐标点纬度,在得到的固定点中进行二分查找,得到纬度与其最近的固定点集合。()使用轨迹原始坐标点经度,在()中得到的固定点集合中进行分查找,得到距离其最近的固定点。()用()中得到的固定点代替原始轧迹中的坐标点国武蔹论义在线轨迹相似度本文提出的轨迹相似度计算方法包含三个部分:()将两条轨迹对齐;()计算两条轨迹中位置点的相似度;()对位貿点相似度加权,得到轨迹相似度。总的流程如图:将轨迹对齐计算轨迹中点的相似度对轨迹中点相似度加权,得到轨迹相似度图路径相似度计算流程轨迹对齐的任务是将两条轨迹中的点对应起来,用于后续的计算。轨迹对齐过程是对两条轨迹进行处理,得到的结果是两条轨迹点个数相同,且一一对应的两条轨迹。轨迹对齐的过程为()将两条轨迹中相同的点对应起米;()在轨迹中相同的点处,将两条轨迹分段()对每段轨迹遍历()以坐标点数较少的轨迹段为主,对每个坐标点进行遍历,选择另·条轨迹段中距离该坐标点最近的坐标点作为其对应的坐标点。()舍弃两条轨迹中没有对应点的坐标点位置点相似度指的是对齐之后的两条轨迹中,对应坐标点之间的相似度。对于两条轨迹P=1p2…m)和Q=(qlq2.…qm),其第1≤t≤n对坐标点之间的相似度衣示为公式:f(PD={1,W-q≤otherwiseE是阙值,|pi-qi是和之间的距离轨迹相似度是两条轨迹之间的相似度,其计算是基于位置点相似度进行的。在进行位置预测的时候,距离当前点近的坐标点比距离远的坐标点更具参考性。因此在使用坐标点相似度计算路径相似度时,进行了加权处理,且距离当前坐标点越近,其权值越大,权值的定义如公式W(m)=m(1+m)其中代表第个位置点相似度的杈值由公式()和()及本文提出的路径相似度计算方法,可以得知两条轨迹间的相似度可表图武获记义在线示为公式():u(P,Q)=>w(m)*f(P, Q,m)(3)=1其中,m表示两条轨迹的长度,(P,Q)表示轨迹P,Q之间的相似度。位置预测的位置预测是基于轨迹相似度进行的。通常,在利用轨迹相似度进行位置预测时仅选取其中相似度最大的历史路径来进行狈测。但是这种方式在某种特殊情况下会失效。例如,两辆车的岀发地和目的地相同,选择的形势路线也相同,但是第·辆车在路途某地到加油站。在这种情况下,使用第一辆车的历史路径,对第辆车的位置进行预测,则可能出现第二辆车会进入加汕站的预测结果。但是,并非所有车辆都会进入加汕站,进入加汕站只是第一辆车特有的行为。在这种特殊情况下,预测将会失效。针对以上问题,本文提出」基于多条历史路径的位置预测算法。算法沇程如图所示:开始计算路径相似度是否超过特定值>是添加该路径到预测集预测集路径条数是否达到特定值否<是否所有路径均已计算是用预测集中的所有路径预测是选择出现频率最高的点作为最终结果(结束图车辆位置预测算法流程图国武蔹论义在线实验与分析本节通过实验评估本方法的有效性,采用的度量指标为预测准确度,预测时间和覆盖率。其中,预测准确度指的是预测结果正确的次数与总的预测结果的次数的比值,预测时间指的是完成次预测所需的平均时间,覆盖率指的是能够产生预测结果和所有预测次数的比值。我们选择与方法进行对比是一种基于网格划分的交通路径预测方法。考虑到解决了数据稀疏性的问题,且性能优于其他方式,所以与其进行对比。共完成了两个实验:第·个实验测试了在不同的和之下本方法的预沨准桷度,第个实验测试了在不同的和之下本方法的计算时间预测准确度我们通过多次实验,分析总结了影响预测准确度的因素,包括路径集中的路径数目,路径最小相似度,其中路径条数分别为,路径最小相似度均为图到图是实验的结果,其中轴代表道路最小相似度,轴代表预测准确度。预测准确度的定义如公式所示Nr(n, s)A(n, s)(4)Nr(n, s)+Nwir,s其中表示最大轨迹数为,最小相似度为时预测准确度。表示预测结果止确的次数,表示预测结果错误的次数在图中,路径条数为,从图中可以看出,随着最小相似度的增加,预测准确度也在增加,且增幅明显。总体预测准确度髙于,但差距不明显,且随着最小相似度的增加,预测准确度差距变得更小。n=200.9∈0.94o92五096)8RBLS08GSIGP0.840.82日卧8怼胡8588只min similarity图最小路径数为时,最小相似度对预测准确度的影响图武获记义在线在图中,路径条数为,从图中可以看出,随着最小相似度的增加,预测准确度也在增加,最小相似度的值较低时增ⅷ比较明显,随着最小相似度的增大增幅变小。总体预测准确度高于,且差距大于路径条数为时的差距。n=300.050.94下0930.92C RBLS0.910.900这88西。d白西mIn slmllarlty图最小路径数为时,最小相似度对颈测准确度的景响在图中,路径条数为,从图中可以看出,在相似度较低阶段,随着最小相似度的增加,预测准确度堦幅明显,在最小相似度最高的时候,预测准确度冇少许的降低。总体预测准确度高于两者之间差距与路径条数为时相近。n=400.9550.909450.946093520925RBLSSIGP0.9150.910.905囝S呙曷因图88罰min similarity图最小路径数为时,最小相似度对预测准确度的影响国武获记义在线对图到图的结果进行分析,可以得知,随着最大路径数的增大,预测准确度整伓増大,在最大路径数较小的时候,增幅明显,随着最大路径数的増加,増幅变小,甚至岀现下降。从总体来看,在最小相似度为,路径条数为时,预测准确度达到最大值预测时间我们通过多次实验,分析总结了影响预测时间的因素,包括路径集中的路径数目,路径最小相似度,其中路径条数均为,路径最小相似度分别为。其中轴表示最大路径数,轴衣示在特定的道路相似度下每个最大路径数对应的计算时间。预测时间定义如公式():T(a, n)∑=t(i,n,a)k(5)表示最大路径数为,预测准确度为时的轨迹预测时间。第次预测的时间,表小顶测总次数。图表示的是路径最小相似度为时,路径条数与预测时间的关系。从图中可以看出,随着路径条教的增加,计算时间在增加,且增加比较平稳。从总体来看所用吋间少于图表示的是路径最小相似度为时,路径条数与预测时间的关系。从图中可以看岀随着路径条数的増加,计算时间也在增加。从总体来看所用时间少于图表示的是路径最小相似度为时,路径条数与预测时间的关系。从图中可以看岀随着路径条数的増加,计算时间也在増加。岀路径条数较大时计算时间基本保持不变。从总体来看所用时间少于a=08200180160140100己30E60HHSIGP402020304050404550556065max trajectory route num图最小相似度为是,最大路径数对预测时间的影响国武获记义在线对图到图的结果进行分析,可以发现在最小相似度不变时,随着最大路径数的增加,计算时间整体增加。最小相似度值较小时,计算时间增加速度比较快且比较均匀,最小相似度值较大时,计算时间随最大路径数增加较缓慢。a=085200且150己100- RBlSSGP2030405040455055665max trajectory route num图最小相似度为是,最大路径数对预测时间的影响a=09200150100SGP2030405040455055max trajectory route num佟最小相似度为时,最大路径数对预测时间的影响结论本文给出了针对稀疏数据进行预测车辆位置的新方法。RBLS是基于城市地图道路标点方式的车辆轨迹预测方式,在进行位置预测时使川了多条历史路径。通过实验证明,该方法较SIGP相比,在预测准确度,预测时间,预测覆盖率方面均有提