《基于多分类的车辆轨迹地图匹配算法的研究》由会员分享，可在线阅读，更多相关《基于多分类的车辆轨迹地图匹配算法的研究（9页珍藏版）》请在金锄头文库上搜索。
1、基于多分类的车辆轨迹地图匹配算法的研究 王丽娟 徐州工业职业技术学院信息与电气工程学院 摘 要： 在车辆导航系统中, 显示在电子地图上的车辆移动轨迹反映了通过 GPS 测量设备实时定位的结果。本研究探索了一种基于多分类算法进行地图匹配的方法, 采用支持向量机 (SVM) 对训练数据进行预处理, 设计了寻找 ELM 最优参数选择算法。实验结果表明, 本论文提出的基于多分类算法的地图匹配能够得到精度较高的匹配结果和较快的匹配速度。关键词： 地图匹配; 模式识别; 多分类; 极限学习机; 支持向量机; 作者简介：王丽娟 (1981-) , 女, 硕士, 讲师, 主要研究方向:数据库、图数据。收稿日期
2、：2017-10-31基金：江苏省高等职业院校教师专业带头人高端研修项目 (2017TDFX003) Research on map matching of the vehicle tracks based on multi-classification algorithmsWANG Lijuan Department of Information and Electrical Engineering, Xuzhou College of Industrial and Technology; Abstract： In the vehicle navigation system, the mov
3、ement track of vehicle on the electronic map reflects the real-time measurement of the GPS devices. This thesis explores a kind of map-matching method based on multi-classification algorithms, adopts SVM to preprocess the training data and designs an algorithm to select the best parameter of ELM. Th
4、e experimental results show that the multi-classification-based approach can achieve higher accuracy and faster matching speed.Keyword： map matching; pattern recognition; multi-classification; ELM; SVM; Received： 2017-10-310 引言在车辆导航系统中, 电子地图上显示的车辆移动轨迹反映了通过 GPS 测量设备实时定位的结果。然而, 显示在地图上的车辆轨迹可能与真实轨迹不一致,
5、一些轨迹可能偏离了实际路网中的道路, 很多定位点并不在道路上, 导航效果不是很理想。因此, 在进一步挖掘和分析地理信息之前, 检测这些误差是很有必要的。地图匹配是一种基于软件技术的定位修正方法, 其基本思想是将车辆定位轨迹结合所在区域的道路网数据集, 由此估计车辆在地图上的路段信息。本文的研究重点就是如何快速准确地完成地图匹配。本研究中使用的数据集包括 GPS 采样数据集和北京市路网数据集, 在预处理过程中使用了 Arcgis 软件划分路网和格式转换, 此外, 使用了 Hadoop 平台下的MapReduce 计算框架提取车辆轨迹。研究中的另一关键部分是分类算法, 包括支持向量机算法和极限学习
6、机算法。1 数据分析及算法框架1.1 问题定义在本论文中, 根据数据集特征和算法设计分析的需要, 对以下概念进行说明。定义 1 路段一个路段 r 是在两个道路结点间的路径。一个路段通常包括了一些必要的其它属性, 比如 r.id 表示路段 r 的 id, r.oneway 表示路段 r 是单向道还是双向道。定义 2 GPS 点 GPS 点是通过 GPS 芯片得到的测量点, 包括出租车 ID、时间戳、出租车状态、经度、纬度、出租车速度和方向角。考虑正常运营出租车的 3 种状态, 分别是空车 (0) 、载客 (1) 和泊车 (2) 。方向角指的是出租车行进方向与正北方向的夹角, 这里角度浮动范围在
7、0360, 顺时针方向增加, 且取整数。定义 3 车辆轨迹一条轨迹包含了同一辆车在一个连续时间段内的连续的 GPS 点。一辆出租车在一天内可以有多条轨迹。获取轨迹时, 只考虑正常运营出租车的两种状态, 分别是空车 (0) , 载客 (1) 。下面两条观察结果有助于设计本论文中的地图匹配算法。为了避免采样误差的影响, 只考虑方向角在对应路段角度上下浮动 15的 GPS 点。具体内容如下。1) 观察 1 在单向道上, 车辆只能在一个方向上行驶。在这种类型的道路上, GPS 点的方向角围绕一个定角小范围变化, 这个定角由道路形状和道路位置综合确定。2) 观察 2 在双向道上, 车辆允许在两个方向上行
8、驶。对某个道路结点, 假设所在路段与正北方向夹角是 (0180) , 另一个夹角就是 +180。因此, 在双向道上的 GPS 点的方向角分别在 和 +180周围小范围浮动。问题定义给定路网数据集 D, 历史 GPS 点集合 P, 确定元素 p 所属的路段 r.id, 其中, pP, rD。概括地说, 地图匹配过程是 GPS 点集合映射到路网数据集的过程, 即 PD。评估标准实验结果采用 ACCURACY 指标来衡量被正确预测的 GPS 点数;CORRECT表示在测试集中被正确匹配的 GPS 点;SUM 表示测试集中输入的 GPS 点的总数。ACCURACY 指标可做如下定义:1.2 数据集在本
9、论文中, 使用的历史 GPS 数据集是由 12 000 辆北京出租车在 2012 年 11 月收集到的数据, 基本完整地记录了北京市出租车的移动情况, 也大致能够覆盖北京市的所有道路。另外, 一个数据集是北京市的路网数据集, 北京市路网十分复杂密集。路网的基本要素为:点实体 (节点) 和线实体 (路段) 。1.3 研究框架本论文提出的基于多分类的车辆轨迹地图匹配算法的研究框架如图 1 所示。图 1 研究框架图 Fig.1 Research framework map 下载原图2 基于多分类的车辆轨迹地图匹配2.1 基于网格划分的数据预处理在多分类算法中, 当训练的类别越多, 需要的训练时间也会
10、越长。因为研究的路网数据集中有 433 391 个路段, 全部一起训练的话, 需要的训练时间是相当长的。因此, 拟定采用网格划分对数据进行预处理, 每个网格内的操作能够并行处理。2.1.1 路网的划分假设路网地图长为 L, 高为 H。研究将整个地图划分为 NN 个大小相同的网格, 每一个网格长为 l=L/N, 高为 h=H/N。又设路网地图左上角的坐标为 p_0 (lat_0, lon_0) , 地图内任意一点的坐标为 p (lat, lon) , 那么点 p 所属的网格 ID 由如下公式运算得出:这里, floor () 为向下取整函数。确定网格划分方案后, 继而使用 Arc Map 中提供
11、的裁剪功能, 用于创建一个新的特征文件, 即感兴趣的区域 (Area of interest, 简称 AOI) 或研究区域, 通常, 输入的特征文件是一个比较大的文件, 裁剪出来的文件是另一个特征文件的子集, 包含了输入特征文件的地理特性。而设计过程可分述展开如下。首先, 创建裁剪形状图层。裁剪形状也必须是一个图层, 在 Arc Catlog 目录下新建一个 shapefile 文件, 创建好的文件保存在 default.gdb 目录下, 然后用Arc Map 打开, 编辑成需要的形状, 此处则编辑成对应位置的矩形框。然后, 用裁剪工具处理。打开 Arc Map, 在 Geoprocessin
12、g 功能选项里, 选择clip 裁剪选项。需要选择输入的特征文件、形状特征文件, 此处分别为原始的北京市路网文件和先前创建编辑的特征文件。通过特征文件能够看到对应的道路网信息也被保存下来, 该网格有 583 个路段, 与原始的道路网相比, 路段数量大大减少。同时, 数据格式与原来完整的路网保持一致。将输出的特征文件利用 Arc Map 里的转换工具 layer to kml, 转换成 KML (或 KMZ) 文件, 用于在地球浏览器中显示地理数据。2.1.2 纠正路网直接打开所得的路网裁剪后的 KMZ 文件, 用 Google Earth 显示。显然, 矢量路网 KMZ 文件和卫星地图上的道路
13、存在着偏移, 一些主干道与卫星地图上的道路并不重合。实验处理过程中要对 GPS 点进行标记, 不过 GPS 点显示在 Arc Map 上偏移很大。此外, 路网在 Arc Map 上虽然有道路信息, 但不能准确地把 GPS 点所在的道路分辨出来。所以尝试将矢量路网地图和卫星地图叠加起来以供分析。叠加之前, 需要利用谷地软件进行纠偏, 实验中对源点坐标和目标点坐标进行参数设置, 通过该软件的坐标纠正功能生成最终的 KML 文件。纠正以后基本能和卫星地图重合, 把卫星地图和矢量电子地图叠加在一起, 直接双击 KML 文件上的路段, 能够获取到道路信息。2.1.3 出租车轨迹的提取根据网格区域来获取每
14、辆出租车的 GPS 采样轨迹, 本文选择 MapReduce 计算框架来应用于历史 GPS 点数据的研究讨论中。分析过程内容如下。首先, 在 Map 函数中, 只提取出租车状态为 0 或 1 的点记录 (分别为空车和载客两种运营状态的记录) , 同时对每个数据项的类型进行字符检查和字符数目检查, 以防出现乱码。MapReduce 框架将所有键相同的值归集在一起传递给对应的 Reduce 函数, 此时, 键是出租车标识符。在 Reduce 函数里, 只保留落在网格区域内的点记录, 将点记录按照时间依次延展排序。同时, 计算当前记录时间和上一条记录时间的差值, 只有当差值大于 30 s 才记录当前
15、的点记录。此外, 还需判断前后记录的坐标数据是否相同, 若前后两点的记录是相同的, 只保留一条该位置的记录。最后, 研究得到每一辆出租车在同一天、同一网格内的 GPS 点记录。为方便后续处理, 输出以 Excel 文件格式组织, 每一个 Excel 文件对应一辆出租车的轨迹记录。然后使用 Excel to kml 转换工具, 将满足要求格式的点记录 Excel 文件转换成 KML 文件, 用于在地球浏览器中显示地理数据。2.2 获取训练数据2.2.1 利用 GPS 数据集进行标注本文已经得到了目标网格内纠正好的路网矢量地图和 2012 年 11 月中在目标网格内每一辆出租车的轨迹。研究将这些轨
16、迹转换成能够在电子地图上直观显示的格式。为了方便标注, 将路网矢量地图和网格内的轨迹叠加显示在卫星地图上。根据坐标、时间顺序和出租车的行驶方向, 就能够为每一个 GPS 点标注其所在路段的 ID。将卫星地图、纠正后的矢量电子地图和车辆轨迹叠加在一起, 再用上述方法标注每一个 GPS 点, 得到的训练集数据 A, 可以有效避免由误差导致的匹配不精确。这样得到的带标签的 GPS 点记录准确度比较高。2.2.2 利用路网中的 GPS 数据进行标注为了对路网做进一步分析, 将目标网格的路网数据 (gdb 格式) 转换成 json 格式的文件, 由此发现每条路段本身含有大量的 GPS 点坐标数据, 将这些点提取出来 (本文用 Python 语言编写功能程序) , 再利用 kml to excel 工具转换成KML 文件, 并用 Google Earth 软件显示在地图上。结果显示:其中包含了大量的点, 弯曲的路段上的点更加密集。接下来, 深入观察路段上的点, 发现这些点正好落在每条道路上, 因此, 这些
