基于GIS地图的轨迹相似度分析系统实现

摘 要

随着物联网、大数据的发展以及各种可定位智能设备在我们现实生活中的应用，我们可以获得各类事物的轨迹数据，比如车辆或是行人。本文基于GIS地图对获取到的各类轨迹数据进行相似度分析。

【关键词】GIS地图 轨迹 相似度

1 引言

随着GPS技术和手机等智能K端设备的快速发展和广泛应用，产成了越来越多由经纬度点组成的轨迹数据。在这些数据中蕴含着丰富的信息，如何对这些轨迹进行相似度分析，是研究轨迹数据的一个重要方面。鉴于此，本文基于GIS地图以一种较为简单的算法实现了轨迹相似度的计算。

2 总体设计

大体将轨迹数据分为两类，第一类轨迹由仅包含经纬度信息的点构成，第二类轨迹所包含的点除了经纬度信息外，还记录了经过该点的时间信息，轨迹数据表总体分为两组，存放轨迹点数据的数据点表和存放各轨迹之间相似度的相似度表，而每组又分为带时间和不带时间的数据表。点表中lon和lat字段分别表示点的经度和纬度，time字段代表时间，sort_id字段表示每个点的主键，而id字段则代表该点所属于的轨迹的id。相似度表中id1和id2字段分别代表比较的两条轨迹，且两者组成组合主键，dist字段代表经过计算得到的两条轨迹之间的编辑距离，之后可以通过公式获得两条轨迹之间的相似度。在本系统中，由于轨迹点的绝对位置是要参与比较的，因此，针对每条轨迹的归一化是不需要的。

对于轨迹相似度的计算，重点需要考虑的是经过各点的位置差异，经过各点的顺序以及经过各点的时间差。由于采集经纬度数据必定存在一些误差，所以对于两点重合的情况我们几乎可以不用考虑。对于两条轨迹，组成它们的点数量可能有所差异，但只要它们在形态上是相似的，那么就认为这两条轨迹相似。一条轨迹中点的数量对相似度的判断没有直接的影响。当然，如果一条轨迹中包含的点越多，那么它的形态会越复杂。在轨迹形态相似的情况下，经过各点的时间也是判断相似度的重要考量。在GIS地图中，根据经过两点的时间，就可以判断这两点之间的直线平均速度，可以作为相似度计算的一个度量。

3 具体实现

3.1 功能实现

3.1.1 计算

给定任意两条同类型（带时间或不带时间）的轨迹，计算出两者之间的相似度。

3.1.2 查询

对于用户指定的一条轨迹，查找与其相似的其他轨迹，并且按照相似度的高低对它们进行排序。

3.1.3 用户自定义轨迹

允许通过鼠标点击直接在地图界面上创建不带时间的轨迹路径，并且自动将轨迹保存于数据库中，之后可以将自定义绘制的轨迹以数据库中已有的轨迹进行相似度的计算，并且查询出数据库中与之较为相似的轨迹，按照相似度从高到底进行排序。

3.1.4 读取指定轨迹

该模块的主要功能是上传轨迹点的数据，自动在GIS地图上显示轨迹。

3.2 核心算法

步骤一：首先针对两条轨迹上次序相同的两个点，计算其转化距离，这里用空间位置上的欧几里得距离来计算，而对于带有时间的轨迹点求转化距离还需要带有时间跨度的计算，最后设置欧几里得距离和时间跨度的权值来获得两个点的转化距离。

欧几里德距离.计算轨迹间距离时可以利用：

symmetricRERP=（RERP（X，Y）+RERP（Y，X））/2 （2）

步骤二：得到不同轨迹上点之间的转化距离以后，对于两条轨迹的比较，可以采用LCSS算法来求得两条轨迹的编辑距离，其中两条轨迹的长度是可以不同的，即所包含的轨迹点的数目是不需要相同的，而其中元素的转化惩罚值即为轨迹点的转化距离。

步骤三：对于获得的两条轨迹的编辑距离，可以采用指数函数的方法，将最终的相似度作为编辑距离的底小于1的指数函数，满足当编辑距离为1时，相似度为1，即100%，而当编辑距离增大时，相似度减小，且减小的趋势越来越不明显，并且最终趋近于0，符合相似度的变化要求，如图1所示。

5 结语

综上所述，通过分析轨迹之间的转化距离，通过LCSS算法得到两条轨迹之间的编辑距离，采用指数函数的方法，最终得到两条轨迹的相似度。

参考文献

[1]刘坤，杨杰.基于编辑距离的轨迹相似性度量[J].上海交通大学学报，2009（43）.