基于公交车轨迹数据的道路GPS环境友好性评估

马连韬 王亚沙 彭广举 赵宇昕 何远舵 高敬月

1(高可信软件技术教育部重点实验室(北京大学) 北京 100871)2(北京大学信息科学技术学院 北京 100871)3(软件工程国家工程研究中心(北京大学) 北京 100871)4(北京大学(天津滨海)新一代信息技术研究院 天津 300450)(malt@pku.edu.cn)



基于公交车轨迹数据的道路GPS环境友好性评估

马连韬1,2,4王亚沙1,3,4彭广举1,2赵宇昕1,2何远舵1,2高敬月1,2

1(高可信软件技术教育部重点实验室(北京大学) 北京 100871)2(北京大学信息科学技术学院 北京 100871)3(软件工程国家工程研究中心(北京大学) 北京 100871)4(北京大学(天津滨海)新一代信息技术研究院 天津 300450)(malt@pku.edu.cn)

GPS是应用最为广泛的室外定位系统，随着技术的发展精度不断提升.然而城市中，由于GPS卫星信号被建筑遮挡，仍然可能产生较大的多径误差.此类误差已称为城市GPS定位误差的主要成分.评估城市道路中环境对GPS精度的负面影响，即环境的GPS友好度，将有助于对不同地段GPS的误差范围进行预判，从而提升位置服务相关应用的用户体验，并为理解环境特征与多径误差的关系，确定在何处部署辅助定位的设备提供支持.为此，提出了1种通过处理和分析海量公交车GPS轨迹历史数据，从而评估城市主要路段的环境友好性的方法.该方法充分利用公交车运行线路固定的特点，大幅提升数据处理的效率；针对路网数据可能存在的错误，提出了容错性的方案；利用相同车辆及相同路段在GPS误差上存在的内在关联，对缺失数据进行补全；并充分考虑到不同质量GPS端设备对环境友好性评估的影响，确定了基于端设备质量加权的评估计算策略.利用成都市二环内的4 869辆公交车1个月的数据，对共计5 648个不同路段的环境友好性进行了评估，并通过卫星地图和街景照片，分析验证了方法结果的合理性.

位置服务；GPS误差；数据分析；地图匹配；智慧城市

随着智慧城市建设的深入，定位技术在交通、旅游、社交等众多领域获得了广泛的应用.而GPS(global positioning system)作为一种精度高、适用范围广、终端设备造价低廉、免费提供服务的定位系统，已经得到广泛应用，GPS终端广泛嵌入到智能手机、腕表、车载装置等移动智能终端中，成为了室外定位技术的事实标准[1-2].然而，GPS的定位精度却受到端设备、定位过程中卫星的空间位置和地面环境的影响，波动较大.特别是在城市环境中，受高楼、立交桥等地面建筑的遮挡，卫星信号常常无法以直线的可视路径(line of sight)传播到终端设备，而是通过建筑或地表反射后，通过多条反射路径被终端设备接收，形成多径(multipath)现象.由于GPS终端设备无法区分接受到的卫星信号是通过可视路径还是反射路径到达设备的，统一按照可视路径计算卫星与设备之间的距离，从而导致计算终端设备位置时出现较大偏差.实测数据表明，城市环境中GPS的定位误差从空旷地段的数米，到多径环境中超过80 m不等.关于GPS误差原因分析和城市中环境对GPS精度影响的研究显示，由于卫星信号被建筑遮挡所产生的多径误差是GPS定位误差最主要的组成部分[2-4]，而且此类误差分布和偏差往往未知，难以消除[5].针对GPS在部分环境中精度不高的问题，研究者提出了一系列利用惯性、视频、WiFi(wireless-fidelity)等其他技术与GPS相结合的组合定位技术与系统，在多径环境中，利用其他定位设备的数据对GPS定位数据进行校准，显著提高了定位的精度.然而，这些组合定位技术，大多需要在城市环境中部署额外的辅助设备(如WiFi热点)或者采集额外的数据(如采集城市环境的视频、WiFi指纹等).

在此背景下，我们提出一种利用城市中公交车的GPS定位轨迹历史数据，分析评估城市道路环境对GPS定位精度产生负面影响程度的方法，并将评估指标称为“GPS环境友好性”.环境对GPS精度产生的负面影响越严重、造成误差越大，则环境友好性越差，反之则越佳.

虽然GPS定位的绝对误差，受端设备质量、天气情况、卫星位置、地面环境等多方面因素综合作用的影响，在无真值的条件下难以准确估计[3,6].但是，考虑到城市中建筑遮挡等环境因素造成的多径误差是误差的主要组成部分，因此对城市GPS环境友好性的评估将有助于辅助估计GPS误差的范围，另外也可以帮助用户建立起诸如“哪些路段的定位误差比另一些路段更大”这样的相对概念，从而提高用户满意度和用户体验.例如，近年来在国内兴起的实时公交APP(application)，通过处理和分析公交车GPS的数据，为移动用户提供公交车实时位置播报及到站时间预测等服务.此类软件需求量很大，在各大城市得到了广泛应用，然而却也因为其提供的数据准确性较差，普遍受到媒体的诟病[7].通过与部分APP研发团队的交流，我们发现城市部分路段GPS定位精度差，是影响此类服务数据准确性的主要原因.如果能事先评估不同路段的环境友好性，据此估计车辆位置数据的误差范围，并在发布给用户的数据中用颜色、字体等形式区分数据的精度和可信度，则可以帮助用户做出更合理的决策，显著提高用户体验.

除此以外，评估道路环境友好性，还将有助于识别城市中GPS误差较大的区域，为采用WiFi、视频等多种技术提升GPS精度的复合系统，提供部署设备、采集数据的选址优化决策依据.另外，受到采样数量的局限，当前针对多径误差与环境特征之间关联关系的研究，一般仅基于较小的数据集进行.而由于公交车轨迹对城市公路实现了大范围的覆盖，因此本文工作将得到不同道路环境友好性评估的大批量化结果.这些数据为GPS多径误差的分析提供了大量数据，并可能为揭示GPS误差受环境影响而变化的内在规律提供支持.

本文采用了2015年11月成都市二环线以内共计184条公交线路、4 869辆公交车，约6 300万条公交车GPS位置轨迹数据以及公交线路数据和开放地图*OSM是由志愿者自愿贡献数据，旨在建立全球范围免费地图的合作项目.相关资源可以通过访问网址：https://www.openstreetmap.org/得到.(open street map, OSM)中的路网数据对公交车轨迹覆盖的5 648个不同的路段进行了GPS环境友好性评估.评估过程大致可分为2个阶段：

1) 计算所有GPS数据的定位误差.为了描述方便，本文称GPS上报数据中标明的位置为报告位置，而车辆实际所在位置为真实位置，真实位置与报告位置之间的直线距离即为GPS定位误差.若将GPS定位误差分解为与道路平行和垂直2个方向的正交分量，研究表明，定位误差可以近似地用垂直道路方向的误差分量表示.原因是城市中建筑一般都位于道路两侧，而沿道路方向则一般没有建筑，因此由建筑遮挡所导致的多径误差中，平行道路方向的分量远小于垂直道路方向的分量，可以忽略[2-3].本阶段过程可以进一步分解为2个步骤：

步骤1. 地图匹配(map matching)，即为每一条GPS数据的报告位置，在地图中找到其真实位置所处的道路；

步骤2. 误差计算，即计算报告位置到匹配路段的垂直距离，并以此作为其定位误差的估计值.

2) 针对每一路段，综合所有GPS数据的误差，评估其总体的环境友好性.

以上2阶段方案并不简单，面临3个方面挑战：

1) 如何为海量GPS数据记录的地图匹配，提供一套高准确性且高效率的算法?本文提出的方法对地图匹配的准确性要求较高.一方面，因为前文所述的GPS定位误差计算方法中，准确的地图匹配是计算GPS定位误差的基础，对环境友好性评估效果有重要影响；另一方面，对GPS环境友好性的评估，要求对路网做较高分辨率的划分.因为GPS环境友好性与道路宽度、地形地势、路边建筑高度甚至树冠遮盖等环境因素密切相关.地图路网数据中，路段通常按照路网拓扑结构切分，存在大量长度超过100 m的较长路段.考虑到在1个长路段内，环境因素可能明显改变，不可作为评估环境友好性的原子单元，需要对长路段进行切分.在本文法中，经过切分将所有路段长度控制在20～100 m之间.而路段较短将导致落入每个路段的GPS报告较少，因此对地图匹配错误容忍的程度也会降低(即少量匹配错误，将对路段评估结果产生较大影响).地图匹配算法是GPS数据处理中1个较为成熟的研究领域，研究者们提出了一系列算法.考虑到问题的需求，我们选择了准确性较高但计算量也较大基于隐Markov模型的地图匹配算法[8-9]，作为本文地图匹配的算法原型.如何在此算法原型的基础上进行改进，使其能够在可接受的时间内处理城市级的海量GPS定位记录是本文面临的第1个挑战.

2) 如何兼容地图路网数据中存在的错误，提高GPS定位误差计算的准确率？OSM作为开源地图数据源，在研究领域得到了非常广泛的应用，本文也采用了此数据源中的路网数据.然而，实践中，我们发现OSM路网数据中存在部分路段数据缺失的情况[10-12].而缺失路段数据将导致地图匹配算法将本应匹配到此“缺失路段”上的所有GPS点都不得不匹配到其他路段上，并引发这些GPS点定位误差计算出错，并进而导致缺失路段附近其他路段出现GPS误差普遍较高、环境友好性较差的“假象”.如何解决利用GPS轨迹和路网数据发现并定位地图中缺失的道路，并补全这些道路避免上述错误，是本文面临的第2个挑战.

3) 如何考虑不同车载设备质量的差异，对所有路段的环境友好性做出公平的评估？通过对成都公交车GPS轨迹历史数据的初步观察和分析，我们发现不同车辆转配的GPS端设备，质量存在明显差异.图1显示了2辆不同的公交车在相同的时段，通过相同路段的GPS报告位置分布情况.可以直观地看到，图1(a)中车辆GPS位置点较之图1(b)中另一辆车明显更加分散、距离道路更远、误差也更大.这一现象与公交公司在不同时间、向不同供货商采购的GPS设备质量存在差异有关.根据公交车运行的规律，1辆车仅通过城市中的少量路段，而1个路段上也仅有部分车辆通过.设想A，B两个环境友好性完全相同的路段，就途径此2条路段的公交车载GPS端设备的质量而言，路段B中设备的质量明显优于路段A.如果仅观察匹配到路段上的GPS记录的误差，认为平均误差越小，则环境友好性就更好，则很容易得出路段B的环境友好性优于路径A的错误结论.在此条件下，如何考虑不同车辆车载GPS端设备的差异、公平的评估不同路段上的环境友好性是本文面临的第3个挑战.

Fig. 1 GPS error of different cars on the same road.图1 相同路段不同车辆定位误差差距明显

针对这3种挑战，本文提出了一套基于公交车轨迹数据的城市道路GPS环境友好性评估方法.在此方法中，1)利用公交车行驶路线固定的规律，缩小地图匹配中搜索的范围，显著提高了地图匹配的效率.2)分析相邻GPS位置报告误差较大数据集合，发现地图可能存在错误的区域，并通过拟合GPS位置点的轨迹路径，补充地图缺失的道路，实现对地图路网数据错误的容错.3)构造误差矩阵，每一行表达1辆车的误差向量，每一列表达1个路段的误差向量，矩阵元素为某辆车在某个路段上1个月的误差均值，由于每辆车仅途径少量路段，因此误差矩阵显然具有稀疏性.另外，从行向量的视角看，端设备质量较高的车辆较之端设备质量较差的车辆，在相同的路段上误差均值倾向于更小；同理，从列向量的视角看，相同的车辆途径环境友好性较好的路段，较之环境友好性较差的路段，其误差均值也倾向于更小.也就是说，此稀疏矩阵中的数据元素之间存在信息冗余，亦即，数据元素之间存在深层的相关性.利用这种相关关系，可以运用矩阵补全的算法，对矩阵缺失的数据进行估计和补全.补全后，每个路段中包含了所有车在此路段中的平均误差.4)基于上述补全后的矩阵，根据车辆GPS终端的质量，对各个路段上不同车辆误差的均值进行加权平均，并以此加权平均值作为最终路段环境友好性的评估结果.本文利用卫星地图和街景照片，对URFE在成都二环内路段中的地图补全和环境友好性评估结果进行了分析，发现了道路宽度、地面建筑高度等环境特征与环境友好性评估结果之间存在的相关性，验证了评估结果的合理性.

1 相关工作

相关工作主要包括3个方面： GPS定位精度估计以及影响因素研究、道路匹配与矩阵补全相关技术以及基于车辆GPS数据挖掘和分析的应用.

1.1 GPS定位精度估计及影响因素研究

文献[1,12-15]等工作从GPS定位原理的角度，对影响GPS采样数据精度的因素进行剖析.文献[1]根据卫星定位的原理，给出了表达GPS定位误差组成部分的模型，阐明了导致误差的3类主要原因：1)卫星误差，即卫星星历误差；2)传输误差，包括电离层误差、对流层误差以及多径效应误差；3)端设备误差，即接收端时钟偏差和接收端测量噪声.文献[1,6,14-15]等在文献[13]的基础上通过实测给出了量化误差估计和改进方案.如文献[14-15]提出卫星星历误差通常约为3 m，而电离层误差和对流层造成的误差分别约为5 m和2 m.文献[6]提出一种差分GPS技术，可以极大地减小卫星星历、大气层、端设备时钟带来的误差.文献[1]则指出影响GPS定位精度的主要因素是端设备质量和多径效应.

近些年来，文献[2-4]等工作在城市环境中，进行了一系列与GPS定位误差相关的现场实验，探究影响定位精度的要素.例如文献[3]利用不同种类设备，在1个中等大小城市的4 000多个参考点，分别进行了定位实验.依据采样数据、周围环境和设备质量参数，分析得出在城市中影响GPS精度的主要原因是楼宇建筑对卫星信号的遮挡造成的多径误差.文献[2]则在挑选的城市多径现象较少开阔区域和建筑物较为集中的市中心区域，分别收集了6 000余个GPS采样数据，并结合GPS系统的相关采样参数(例如速度、卫星数量等)，评估某个GPS采样数据的精确度等级，发现市中心GPS精度较开阔地带明显下降.文献[4]同样利用在城市的几个典型区域进行现场实验的方式，分析得出影响GPS定位精度的影响要素包括：端设备质量、楼宇建筑、端设备移动的速度和朝向等.

总结以上工作可见：GPS的定位精度受到端设备、定位过程中卫星的空间位置和以及地面环境的影响，且波动较大.近年来，随着定位算法的改进和端设备电子器件质量的提高，星历误差、端设备时钟偏差、平流层和对流层误差等逐渐减小，GPS定位精度不断提高.但是，在城市环境中，受高楼、立交桥等地面建筑的遮挡，多径现象仍然十分常见，多径误差尚未获得较好的改进方案，多径误差成为GPS误差最主要的组成成分.以上工作为本文研究城市道路环境友好性评估提供了启发和依据，然而这些工作都是在城市中的少量区域进行针对性的采样和实验，数据较少，覆盖范围有限，无法形成对城市范围内环境对GPS精度影响的全局视角.本文上述工作在研究思路上明显不同，利用覆盖城市绝大多数主要道路的公交车GPS轨迹历史数据以及其他补充信息，通过数据的分析挖掘，将形成城市中道路环境友好性较为完整的视图.

1.2 道路匹配与矩阵补全技术

本文研究内容涉及2项关键技术：1)如何将GPS采样点映射到路网地图上的1条道路；2)基于矩阵补全技术完成道路GPS友好程度评估.因此，下面对道路匹配和矩阵补全分别进行简要介绍.

道路匹配技术将车辆GPS数据映射到路段上，从而确定车辆在道路上的位置.常用的匹配算法包括几何匹配算法、拓扑匹配算法、统计匹配算法和高级匹配算法等.几何匹配算法只考虑道路的几何信息，实现简单，但是路况复杂时容易误判[2]；而拓扑匹配算法还利用了路网的拓扑结构，提高了匹配准确率[16-17]；统计匹配算法基于车辆GPS概率密度选择候选路段进行匹配，常用于实时导航的道路匹配，不适合对大规模定位数据进行道路匹配计算[18-19]；高级匹配算法包括基于隐Markov模型的道路匹配算法、卡尔曼滤波道路匹配算法[19-20]、基于模糊逻辑的道路匹配算法等[19-20]，考虑到问题的需求，我们选择了准确性较高但计算量却也较大的基于隐Markov模型的地图匹配算法.为减少计算量，本文利用公交车行驶线路固定的规律，缩小地图匹配中搜索的范围，显著提高了地图匹配的效率.

矩阵补全的常用技术包括K-NN算法(K-nearest neighbors,K-NN)、压缩感知、非负矩阵分解等.基于K-NN的矩阵补全技术利用了相邻数据间的相关性，寻找缺失数据的最相邻的K个数据点，对这些数据点与待补全点之间的距离加权平均，从而实现缺失数据的补全[21]；基于压缩感知的补全算法利用数据中存在的内在联系与冗余信息对初始矩阵进行重构，并且在补全的同时还能保持补全矩阵的低秩特性[22]；非负矩阵分解通过最小化补全矩阵与初始矩阵的欧氏距离或者Kullback-Leibler散度来实现缺失元素补全，该技术保证了补全数据的物理意义，即非负性，在推荐系统等现实场景中有广泛应用[23].本文的目标补全矩阵是1个非负矩阵，每一个元素是车辆GPS点到匹配路段上的平均偏差，因此本文选用了非负矩阵分解技术进行矩阵补全.

1.3 基于车辆GPS的智慧城市数据挖掘应用

近年来有很多基于车辆GPS的数据挖掘相关工作，它们大多结合了城市内其他多源异构数据(如POI、人群移动等)，综合使用多种机器学习技术，分析挖掘与城市相关知识，解决智慧城市建设中的相关问题.例如文献[24-25]基于对城市中大量公交GPS数据的模式挖掘，实时监测和预测城市道路的交通情况；文献[26]基于车载GPS数据分析车辆移动的轨迹模式，从而改进车联网中的路由算法；文献[27]则基于张量分解补全技术，利用出租车的GPS数据估计在城市任意2点之间乘车所消耗的时间；而文献[28]等利用出租车轨迹数据检测分析异常的载客线路.以上工作虽然也采用了城市规模的车载GPS数据，然而研究问题与本文不同.

2 方法框架

方法的总体框架如图2所示.研究中所用到的3个数据集:1)数据集1是“公交车GPS轨迹历史数据”,这部分数据包括了2015-11-01—2015-11-30，共计30 d中，成都市二环以内全部184条公交线路、4 869辆公交车的GPS报站轨迹数据.每辆公交车在其运营期间，1 min内产生2～4条定位数据记录，所有GPS定位数据记录共计62 783 111条，平均每天约210万条；2)数据集2是“公交车线路路径数据”,这部分数据集由公交公司提供的一系列人工标注的位置点组成，相邻位置点之间的距离不超过150 m，用于标明上述184条公交线路从首发站到结束站的运行路径,然而，由于城市道路建设、公交线路重新规划等问题，以上标示的线路并非完全准确，其中有约5%的位置点与公交车实际运行的轨迹不符;3)数据集3是“OSM路网数据”，是从OSM地图中获得成都市二环以内的路网数据，其中存在部分路径缺失的情况.如引言所述，为了提高路径环境友好性评估的合理性，我们对OSM路网数据中的长路径进行了切割，将公交车轨迹覆盖的所有道路分割成20～100 m长度的共计5 648个路段，每个路段作为环境友好性评估的1个原子单元.

Fig. 2 Framework of the URFE approach.图2 URFE方法的整体框架

方法整体上由3个核心算法组成，分别为兼容路网数据错误的高效地图匹配算法、基于非负矩阵分解的GPS定位误差矩阵补全算法以及基于设备质量加权的路段环境友好性评估算法.算法1的目标是高效准确地实现所有GPS数据的地图匹配.具体而言包括2个模块.其中，“基于隐Markov模型的2阶段地图匹配”模块，利用公交车大部分情况下运行路径固定的特点，缩减基于隐Markov模型的地图匹配算法的搜索空间，提高算法效率.另外，针对OMS地图存在缺失路段的问题，利用GPS轨迹历史数据发现并拟合缺失路径，修订地图路网中的错误，并对新增路径附近的GPS点执行重新匹配.

地图匹配完成后，可以计算得到每个GPS记录的定位误差并构造1个误差矩阵，每一行表达1辆车的误差向量，每表达1个路段的误差向量，矩阵元素为某辆车在某个路段上的平均误差.之后调用“基于NMF的GPS定位误差矩阵补全算法”，采用非负矩阵分解技术，利用矩阵元素之间的相关性，对缺失元素进行补全.

补全后的GPS定位误差矩阵中，可以利用行向量的模长衡量车中端设备的质量，而利用列向量的模长衡量路段的环境友好性.考虑到质量更好的端设备在衡量路段环境友好性时，应该享有更高的权重，因此“基于设备质量加权的路段环境更友好性评估算法”根据车辆端设备的质量加权计算得到路段的加权平均误差，并以此作为路段的环境友好性评估的依据.

3 兼容路网数据错误的高效地图匹配算法

3.1 基于隐Markov模型的2级地图匹配

由于本文方法对地图匹配准确性要求较高，因此采用基于隐Markov模型的地图匹配算法作为算法原型.基于隐Markov模型的地图匹配算法基于2条规则：1)某个GPS采样数据与某条路段的匹配概率，与该GPS采样的经纬度坐标位置到路段的偏移距离相关，距离越短，概率越大；2)由于车辆是连续前进的，因此当前GPS采样数据对应的路段应该与上一时刻采样数据对应的路段距离相近.基于以上这2条规则，算法以动态规划策略求解出具有最大概率的前进路径.

然而，若在本文的数据集中直接应用上述算法原型，计算量较大.实际上，相比于其他车辆轨迹数据(例如出租车数据)，公交轨迹数据有其自身的特点，基本固定不变的公交线路信息可以为道路匹配提供重要的补充信息，从而大大减少可能匹配的候选道路的数量.因此，本文根据公交数据本身的特点，提出2阶段算法以提高道路匹配的效率.

阶段1. 基于公交线路路径数据的地图匹配.每一个GPS点所关联计算的路段可由地图附近路段缩减至公交车指定线路，进而提高效率.其中，公交车线路同样由GPS指定，因此需要先将线网数据通过地图匹配算法匹配至路网，获得公交线路路段.随后将公交车GPS数据匹配至公交线路路段.

阶段2. 基于地图路网数据的地图匹配.与公交线路初步匹配后的公交车GPS数据仍然存在较多具有较高误差的点，即与所有公交线路路段都相距很远.主要原因是公交车并非完全按照给定的线路路径行驶，具体原因包括3个方面：1)因为道路施工临时改道、线路调整后路径数据未及时更新等原因，导致公交公司提供的线路路径数据并非完全准确；2)公交车可能因为检修、加油等原因，未按线路路径行驶；3)某个线路的公交车被临时调度开另一个线路.针对上述3个原因，首先根据第1阶段匹配结果，筛选出明显偏离匹配路段的GPS点集合，并分析GPS点与公交线路偏离的起始点，在此位置附近搜索地图上的其他路段，仍然采用基于隐Markov模型的地图匹配原型算法选择最佳匹配结果.

基于隐Markov模型的2级地图匹配算法具体算法描述如下：

输入: GPS序列G={gt|t=0,1,…,T-1}，其中gt为第t条GPS数据，包含经纬度坐标、时间戳等；公交车线路轨迹点序列B={bi|i=0,1,…,T-1}，其中bi为第i个线路轨迹点，包含经纬度坐标；路网数据NE={Nodes,Edges}，其中Nodes={ni|i=0,1,…,M-1}为节点集合，每个节点是地理上的坐标点，表示交叉路口、道路上拐点等，Edges={ri|i=0,1,…,N-1}为边集合，即路段集，每条边是2个节点之间的直线路段；

输出: 每条GPS数据与路段的映射关系以及偏移路段的距离MR={(rt,dt)|t=0,1,…,T-1}.伪代码如算法1所示.

算法1. 基于HMM的2阶段地图匹配.

①BMR=HMM_MapMatching(B,NE)；*公交线路路段*

②start=-1,end=-1；*初步匹配后仍 然误差较大的区间的起始、结束位置*

③ fori=0 toT-1 do*对误差较大区间内 的匹配结果进行临近路段重匹配*

④ ifMRi偏离距离超过50 m andstart=-1 then

⑤start=i；

⑥ endif

⑦ ifMRi偏离距离小于50 m andstart≠-1 then

⑧end=i-1；

⑨MRstart→end=HMM_MapMatching(Gstart→end,NE);*将误差较大的 点匹配至临近路段*

⑩start=-1；

3.2 基于局部加权线性回归的路网修正

以OSM为代表的路网地图含有缺失路段等错误,导致GPS点无法全部定位至地图已有路段上，从而错误地计算出大量匹配误差.本文提出了基于局部回归的路网修正算法，在基于临近路段重匹配的线路错误误差消除的结果上，挑选出GPS定位误差较仍然大的路段，将该路段上的全部GPS点进行局部加权的线性回归，进而以较小的计算量补充路段校准地图.

局部加权线性回归算法是一种常用的曲线拟合算法[29].其赋予每个数据点以一定的权值，以此为基础利用最小均方差来进行普通线性回归.相比于普通线性回归，局部加权线性回归可以无参地进行曲线拟合，缓解欠拟合问题.

但由于城市路段形状不定且局部加权线性回归对坐标系方向敏感，因此在进行路段拟合前还需要进行预处理，选取合适的坐标系方向.本文所采用的方法为：遍历尝试不同坐标系方向，在x轴上每5 m划定1个区间，计算该区间内全部公交GPS点的y值方差，最终计算全部区间内的平均y值方差，并选取最小平均方差所对应的坐标系.

基于局部加权线性回归的路网修正伪代码如算法2：

算法2. 基于局部加权线性回归的路网修正.

①OGPS←MR中偏离距离仍然超过50 m的 GPS点集合区间的集合；

② forOGinOGPSdo

③ 将OG中的坐标点旋转直到x轴方向上每个小区间中y值分布的标准差的均值最小；

④ 将OG中点做局部加权线性回归，拟合出一条新的路；

⑤ 更新MR；

⑥ endfor

⑦ returnMR.

3.3 实验结果与分析

1) 2级地图匹配结果

第1级地图匹配中，已有80.90%的公交车GPS数据点在误差阈值限定下匹配至公交线路，但仍有19.10%的定位点存在较大误差;第2级地图匹配将该部分GPS点利用路网数据进行重匹配，该部分数据中约81.09%在误差阈值限定下匹配至临近路段，至此全部GPS数据点的96.39%已完成地图匹配，结果如表1所示.剩余仍然误差较大的数据点将在路网修正后进一步匹配.

Table 1 Result of 2-Phase Map Matching

2) 算法效率提升

实验使用的服务器配置为Intel®Xeon®CPU E5-2650 v2 @ 2.60 GHz，32核，128 GB内存.我们开启15线程，对普通地图匹配算法(即将所有公交车GPS点直接在OSM地图上进行基于隐Markov模型的道路匹配)以及本文改进后的2级地图匹配算法效率进行了测试.结果如表2所示，本文算法极大地缩减匹配过程中候选路段的数量，提升了算法的效率.

3) 路网修正结果

本文基于局部加权线性回归的路网修正算法，对OSM路网地图在成都市二环内共补充路段20条，其中2条路段的修正结果如图3所示.

图3依次展示了2条缺失路段的原始OSM地图、对应的经过2级地图匹配后依然误差较大的公交车GPS数据、局部回归拟合后的补充道路(绿色线条)以及卫星对照图(红色标注部分为对应道路).

Table 2 Efficiency Comparison

(a)OriginalOSM(missingsegmentsaremarkedwithredcircles) (b)GPSdataofbuses (c)Roadsegmentscompletedbyourmethod(markedwithgreenlines) (d)Satellitephotos(completedsegmentsaremarkedwithredcircles)

Fig. 3 Results of supplement missing road segments of OSM (Qingyun South Street and North of Shuangqiaozi).
图3 OSM地图缺失路段补充结果(庆云南街与双桥子北)

根据对照结果可见，基于局部回归的路网修正算法借助公交车GPS数据，成功识别并拟合出了OSM地图上部分缺失的道路.

4 基于NMF的GPS定位误差矩阵补全算法

4.1 GPS定位误差矩阵构造

地图匹配完成后，可以通过计算每个GPS点位置与匹配路段的垂直距离作为该条GPS数据的定位误差.考虑到GPS定位误差不仅包括环境友好性的影响还涉及星座等随机因素，我们对每一辆公交车在其30 d内经过的每一个路段上的多次GPS定位记录计算误差平均值.如果某辆公交车在某条路段上的GPS数据记录少于20条，则该部分数据被视为不可靠数据抛弃.

至此我们可以进行误差矩阵的构造.该矩阵每一行表达1辆公交车的误差向量，每表达1个路段的误差向量，矩阵元素表示某辆车在某路段上的平均误差.由于成都市二环内有4 869辆不同的公交车且公交车轨迹共覆盖5 648个不同的路段，而每辆公交车经过的路段仅为总路段中的一小部分，因此将构造出1个4 869×5 648的非负稀疏矩阵.

我们试图利用该误差矩阵评估每条路段的GPS环境友好性.一个直观的想法是直接计算每条路段上所经过公交车的GPS平均偏差值，以此评估该路段的GPS环境友好性.但公交车的GPS端设备质量并不一致，如果通过某一路段的公交车所搭载的GPS设备普遍质量较差，则无论该路段是否GPS环境友好均会得到相对较高的GPS平均偏差值，即评估有失公平.

因此，本文引入非负矩阵分解技术进行矩阵补全，计算得到所有公交车在所有路段上的GPS偏差推测值，进而实现使用不同质量的端设备客观评估环境对误差的影响.

4.2 误差矩阵分解与补全

非负矩阵分解(non-negative matrix factorization, NMF)是在矩阵中所有元素均为非负数约束条件之下的经典矩阵分解方法.其利用矩阵元素之间的相关性，将任意非负矩阵分解为2个非负矩阵乘积的形式，进而重构原矩阵达到填补空缺值的效果，实现矩阵补全.

算法输入: 非负稀疏误差矩阵Mm×n,其中m表示总公交车数量，n表示全部路段数，矩阵每一行表达1辆车的误差向量，每表达1个路段的误差向量，矩阵元素Mi,j为第i辆公交车在第j个路段上的GPS平均定位误差.若Mi,j=0,则表示该车未经过该路段，没有相关数据.

算法参数: 矩阵分解的中间维度k，由经验法给出.

算法输出: 2个非负矩阵Lm×n,Rk×n.

由于NMF算法中并未考虑待分解矩阵M包含空缺值的情况，为此本文定义标识矩阵D：

非负矩阵分解算法中的目标函数定义为

算法采用梯度下降方法在迭代过程中不断降低目标函数值，最终求得矩阵L,R.迭代公式经推导得到：

在非负矩阵分解算法中，每轮迭代需要按照上述公式进行矩阵运算.以L的更新为例，计算MRT,LR,(D·LR)RT都各需要m×n×k次浮点运算(只考虑乘除)，计算D与LR的矩阵点乘需要m×n次浮点运算，计算L,MRT,1(D·LR)RT三者的矩阵点乘需要2×m×n次浮点运算，对R的更新与之相似，因此每轮迭代需要6(m×k×n)次浮点运算，时间复杂度为O(m×k×n).设定进行T轮迭代，则整体时间复杂度为O(T×m×k×n).此外，根据分解得到L,R,恢复原有矩阵需要一次矩阵乘法，其时间复杂度为O(m×k×n).

4.3 实验结果与分析

本文采用三次10折交叉验证法，验证矩阵补全结果准确性.

将矩阵M中非零位置随机划分为相同大小的10个部分(P1,P2,…,P10)，对于每个部分Pi，遮盖住这一部分(将相应位置的元素值设为0)，保留其余9个部分，对M′进行1次补全，对于本次补全得到的矩阵L′R′计算偏差率(estimate-error)如下：

对所有部分分别进行遮盖后得到最终的偏差率：

重新将非零部分进行划分，上述步骤重复3次后将每次得到的偏差率求和取平均，最终求得偏差率18.28%.根据文献[22-23]该偏差率处于较低范围，验证了基于NMF的GPS定位误差矩阵补全算法的有效性与准确性.

5 基于设备质量加权的路段环境友好性评估

5.1 加权迭代排序

通过补全GPS定位误差矩阵，我们已经获得了每辆公交车在每个路段的大致GPS定位误差.矩阵中的行向量模长可以衡量车中端设备的质量，而利用列向量的模长可以衡量路段的环境友好性.

考虑到质量较差的端设备在GPS定位时具有较高不确定性，质量更好的端设备在衡量路段环境友好性时应该享有更高的权重.同样，GPS环境友好的路段在衡量公交车端设备质量时，也应具有较高的权重.本文据此提出了加权迭代排序算法,该算法根据公交车GPS定位加权误差、路段上加权误差的高低排名赋予公交车与路段不同的权值，并以此重新计算全部车辆与路段的加权定位误差.通过不断迭代直至算法收敛，即全部车辆与路段的排序趋于稳定,最终获得全部路段的加权误差以及排序结果，并以此作为路段的环境友好性评估的依据.

算法输入: 补全后的误差矩阵Mm×n、最多迭代次数Maxlt.

算法输出: 车的排序结果Bus_Rank，路的排序结果Road_Rank.

算法描述如下，流程如算法3所示.

初始给予所有车以及路段相同的权重.以Bus_Wt,i表示第i辆车在第t次迭代时的权重，以Road_Wt,j表示第j条路段在第t次迭代时的权重，则：

根据当前权重计算所有车、路的误差值.以Bus_Distt,i表示第i辆车在第t次迭代时的误差加权均值，Road_Distt,i表示第j条路段在第t次迭代时的误差加权值，则：

根据上述误差加权均值分别对车和路排序，并计算与上一次迭代后排序结果的偏差.以Bus_Rank_Dt表示第t次迭代后车辆排序的变动状况，Road_Rank_Dt表示第t次迭代后路段排序的变动状况，则：

Bus_Rank_Dt=

Road_Rank_Dt=

其中，Bus_Rankt,i表示第i辆车在第t次迭代结束后的排名，Road_Rankt,j表示第j条路段在第t次迭代后的排名.

算法3. 加权迭代排序.

① 初始公交车权重Bus_W0,i；

② 初始路段权重Road_W0,j；

③ 初始公交车排名Bus_Rank0={0,1,…,m-1}；

④ 初始路段排名Road_Rank0={0,1,…,n-1}；

⑤ fort←1 toMaxItdo

⑥ fori←0 tom-1 do

⑦ UpdateBus_Distt,i；

⑧ endfor

⑨ forj←0 ton-1 do

⑩ UpdateRoad_Distt,j；

如果Bus_Rank_Dt与Road_Rank_Dt同时为0，则表明排序稳定，评估结果不再发生变化，算法停止.或者若达到最大迭代次数，算法停止.否则，按照低误差车辆、路段权重高，反之权重低的原则，重新计算权值：

进入下一轮迭代，直至满足停止条件.

5.2 实验结果与分析

本文基于设备质量加权的路段环境友好性评估算法考虑不同车载设备的质量差异对路段环境友好性评估的影响，通过端设备权值计算与路段GPS友好性评估的多次迭代计算，得到最终结果.我们还设置了简单的对比方法，通过GPS误差矩阵构造得到稀疏误差矩阵后，直接利用已有数据对所有路段求得平均误差，并以此评判路段的GPS环境友好性.2个方法的结果如表3所示：

Table 3 Evaluation Results of Road Friendliness

我们按照误差范围，将路段划分至3个级别，并统计出路段数量，如表4所示.误差小于20 m定为GPS环境友好性较高(在图4线路中以绿色标注)，误差20～30 m之间定为GPS友好性中等(以黄色标注)，误差大于30 m定为环境友好性较差(红色标注).

Table 4 Evaluation Degree Comparison

Fig. 4 Environment friendliness evaluation of road segments inside the 2-ring road in Chengdu.图4 成都市二环以内路段环境友好性分级结果

GPS信号质量良好的路段，相对而言路况简单并且视野开阔，一般道路宽度比较宽，位于城市主干道路或者快速路高架桥上，环境遮蔽物通常相距较远或只位于道路单侧，整体受环境遮蔽物影响小.

GPS信号质量一般的路段，道路环境介于红色路段和绿色路段之间，路宽适中，通常存在数种环境遮挡物中的一种或几种.

GPS信号质量较差的路段，其道路周边环境会对信号造成较大影响.首先，这些道路宽度一般较窄，往往集中于非主干道路，双向单车道或双向双车道居多；其次，这些道路周围的环境遮蔽物较为密集，包括建筑物和密集的道旁树木等，这些路段受多路径误差影响大.部分路段街景如图5所示，其中GPS环境友好的4条路段对应于图4中圈注G1-G4，友好性中等路段对应于Y1-Y4，友好性较差路段对应于R1-R4.

本文方法与基本方法对比，共有1 355条路段分级发生变化，其中1 279条路段评级变好(590条路段是由红变绿的、689条路段由红变黄或由黄变绿)，76条路段评级变坏.

由红变绿的路段当中，经过车辆平均排名2 331(公交车总数4 869)，即经过这些路段的车大部分端设备质量较差，导致对比方法对路段的GPS环境友好性低估.而基于设备加权的路段环境友好性评估算法将误差矩阵补全，根据车辆端设备的质量加权计算得到路段的加权平均误差，进而公平评估路段的环境友好性，使得被对比方法误判的道路评级上升.

(a)Goodenvironmentfriendliness(markedwithgreeninFig．4(b))(b)Normalenvironmentfriendliness(markedwithyellowinFig．4(b))(c)Badenvironmentfriendliness(markedwithredinFig．4(b))

Fig. 5 Street view of road segments which have different level in environment friendliness evaluation.
图5 环境友好性不同级别路段的街景图示例

以某路段为例，其共经过238辆车，平均排名为2 477.对比方法计算其平均误差为42 m，环境友好性被评估为不友好.但本文提出算法计算其误差加权均值为15 m，环境友好性被评估为友好.

街景图6显示，该路段地势平坦开阔，没有高楼、高架桥等建筑物阻挡，GPS环境友好性较高.验证本文提出算法的有效性.

Fig. 6 Street view of good GPS environment friendliness.图6 GPS环境友好街景验证

6 结 论

本文提出了一种基于海量公交车载GPS历史轨迹数据评估城市主要路段的环境友好性的方法.该方法首先利用公交车运行线路固定的特点，高效地将GPS数据映射到城市的路段上，并针对路网数据可能存在的错误，提出了容错方案.其次，利用相同车辆及相同路段在GPS误差上存在的内在关联，对缺失数据进行补全，并充分考虑到不同质量GPS端设备对环境友好性评估的影响，提出了一种基于端设备质量加权的评估计算策略.利用成都市二环内的4 869辆公交车1个月的数据，本文对共计5 648个不同路段的环境友好性进行了评估，并通过卫星地图和街景照片的分析，验证了方法的合理性.

未来工作主要关注3个方面：1)实地测量和验证.本文目前通过查看部分路段的百度街景地图对结果的合理性进行分析和验证.未来我们将前往成都市，并携带相应GPS端设备进行实地测量，进一步验证方法结果的合理性.2)基于本文中车辆端设备质量和道路环境友好性评估结果，为实时公交APP等应用，建立公交车实时位置及到站时间预测等分析结果的可信性评估模型，并利用评估结果提高此类应用的用户体验.3)将环境友好性评估结果作为训练数据，利用城市街景图片，提取环境特征，对没有公交轨迹数据的城市路段的GPS环境友好性进行预测.

[1]Meguro J, Murata T, Takiguchi J, et al. GPS multipath mitigation for urban area using omnidirectional infrared camera[J]. IEEE Trans on Intelligent Transportation Systems, 2009, 10(1): 22-30

[2]Drawil N M, Amar H M, Basir O A. GPS localization accuracy classification: A context-based approach[J]. IEEE Trans on Intelligent Transportation Systems, 2013, 14(1): 262-273

[3]Modsching M, Kramer R, ten Hagen K. Field trial on GPS accuracy in a medium size city: The influence of built-up[C] //Proc of the 3rd Workshop on Positioning, Navigation and Communication. Hannover: WPNC, 2006: 209-218

[4]Ahlers D, Pielot M, Wichmann D, et al. GNSS quality in pedestrian applications-a developer perspective[C] //Proc of the Workshop on Positioning. Piscataway, NJ: IEEE, 2008:45-54

[5]Syed S, Cannon M E. Fuzzy logic-based map matching algorithm for vehicle navigation system in urban canyons[C] //Proc of the 2004 National Technical Meeting of the Institute of Navigation. San Diego, CA: ION, 2004: 26-28

[6]Han S C, Kwon J H, Jekeli C. Accurate absolute GPS positioning through satellite clock error estimation[J]. Journal of Geodesy, 2001, 75(1): 33-43

[7]Tian Yang, Liu Mian. Bus real-time software is mostly not Reliable[N]. Beijing Daily, 2016-03-16 (in Chinese)(田阳, 刘冕. 公交实时软件大多不靠谱[N]. 中国日报, 2016-03-16)

[8]Newson P, Krumm J. Hidden Markov map matching through noise and sparseness[C] //Proc of the 17th ACM SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2009: 336-343

[9]Ren Ming, Karimi H A. A hidden Markov model-based map-matching algorithm for wheelchair navigation[J]. Journal of Navigation, 2009, 62(3): 383-395

[10]Girres J F, Touya G. Quality assessment of the French OpenStreetMap dataset[J]. Trans in GIS, 2010, 14(4): 435-459

[11]Kounadi O. Assessing the quality of OpenStreetMap data[D]. London: University College of London, Department of Civil, Environmental and Geomatic Engineering, 2009

[12]Haklay M. How good is volunteered geographical information? A comparative study of OpenStreetMap and ordnance survey datasets[J]. Environment and Planning B: Planning and Design, 2010, 37(4): 682-703

[13]Wells D E, Beck N, Delikaraoglou D, et al. Guide to GPS Positioning[M]. Fredericton, NB, Canada: Canadian GPS Associates, 1986

[14]Grewal M S, Weill L R, Andrews A P. Global Positioning Systems, Inertial Navigation, and Integration[M]. New York: John Wiley & Sons, 2007

[15]Rankin J. An error model for sensor simulation GPS and differential GPS[C] //Proc of Position Location and Navigation Symp. Piscataway, NJ: IEEE, 1994:260-266

[16]Greenfeld J S. Matching GPS observations to locations on a digital map[C] //Proc of of the 81st Annual Meeting of the Trans Research Board. Washington, DC: Transportation Research Board, 2002

[17]Quddus M A, Ochieng W Y, Zhao Lin, et al. A general map matching algorithm for transport telematics applications[J]. GPS Solutions, 2003, 7(3): 157-167

[18]Ochieng W Y, Quddus M, Noland R B. Map-matching in complex urban road networks[J]. Revista Brasileira De Cartografia, 2003, 55(2):1-14

[19]Krakiwsky E J, Harris C B, Wong R V C. A Kalman filter for integrating dead reckoning, map matching and GPS positioning[C] //Proc of Position Location and Navigation Symp. Piscataway, NJ: IEEE, 1988: 39-46

[20]Obradovic D, Lenz H, Schupfner M. Fusion of map and sensor data in a modern car navigation system[J]. Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology, 2006, 45(1/2): 111-122

[21]Bell R, Koren Y, Volinsky C. Chasing $1, 000, 000: How we won the Netflix progress prize[J]. ASA Statistical and Computing Graphics Newsletter, 2007, 18(2): 4-12

[22]Zhu Yanmin, Li Zhi, Zhu Hongzi, et al. A compressive sensing approach to urban traffic estimation with probe vehicles[J]. IEEE Trans on Mobile Computing, 2013, 12(11): 2289-2302

[23]Lee D D, Seung H S. Algorithms for non-negative matrix factorization[C] //Advances in Neural Information Processing Systems. La Jolla, CA: NIPS, 2001: 556-562

[24]Zhou Pengfei, Jiang Shiqi, Li Mo. Urban traffic monitoring with the help of bus riders[C] //Proc of Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2015: 21-30

[25]Wang Yuqi, Cao Jinnong, Li Wengen, et al. Mining traffic congestion correlation between road segments on GPS trajectories[C] //Proc of 2016 IEEE Int Conf on Smart Computing. Los Alamitos, CA: IEEE Computer Society, 2016:1-8

[26]Zhang Fusang, Jin Beihong, Wang Zhaoyong, et al. On geocasting over urban bus-based networks by mining trajectories[J]. IEEE Trans on Intelligent Transportation Systems, 2016, 17(6):1-14

[27]Wang Yilun, Zheng Yu, Xue Yexiang. Travel time estimation of a path using sparse trajectories[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 25-34

[28]Zhang Daqing, Li Nan, Zhou Zhihua, et al. iBAT: Detecting anomalous taxi trajectories from GPS traces[C] //Proc of the 13th Int Conf on Ubiquitous Computing. New York: ACM, 2011: 99-108

[29]Harrington P. Machine Learning in Action[M]. Greenwich, CT: Manning, 2012Ma Liantao, born in 1994. PhD candidate in Institute of Software, School of Electronics Engineering and Computer Science, Peking University. His main Research interests include ubiquitous computing, machine learning.

Wang Yasha, born in 1975. Received his PhD degree in Northeastern University, Shenyang, China, in 2003. Professor and associate director of National Engineering Research Center of Software Engineering in Peking University, China. His main research interests include urban data analytics, ubiquitous computing, software reuse, and online software development environment.

Peng Guangju, born in 1995. Postgraduate of the School of Electronics Engineering and Computer Science, Peking University. His main research interest is ubiquitous computing.

Zhao Yuxin, born in 1995. Undergraduate of the School of Electronics Engineering and Computer Science, Peking University. Her main research interests include urban data analytics and ubiquitous computing.

He Yuanduo, born in 1992. Received his bachelor degree in Peking University, Beijing, in 2014. PhD candidate in Institute of Software, School of Electronics Engineering and Computer Science, Peking University. His main research interests include ubiquitous computing, mobile computing, and data mining.

Gao Jingyue, born in 1997. Undergraduate of the School of Electronics Engineering and Computer Science, Peking University. His main research interest include urban data analytics and ubiquitous computing.

Evaluation of GPS-Environment Friendliness of Roads Based on Bus Trajectory Data

Ma Liantao1,2,4, Wang Yasha1,3,4, Peng Guangju1,2, Zhao Yuxin1,2, He Yuanduo1,2, and Gao Jingyue1,2

1(Key Laboratory of High Confidence Software Technologies (Peking University), Ministry of Education, Beijing 100871)2(SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871)3(NationalEngineeringResearchCenterofSoftwareEngineering(PekingUniversity),Beijing100871)4(Beida(Binhai)InformationResearch,Tianjin300450)

GPS is the most widely-used outdoor positioning system. With the advance of relevant technologies, positioning accuracy of GPS has been increasing continuously. However, as the GPS satellite signal can be blocked by buildings, multi-path error becomes the major cause of positioning error in a city. Evaluating the negative effects of GPS error on urban environments, which is referred as environment friendliness in this paper, will help the prediction of GPS error range in different road segments. Furthermore, it enhances user experiences of location-based services, reveals the relationship between environmental characteristics and multi-path error, and helps to determine where to deploy supplementary positioning devices. In this paper, we have proposed an urban road friendliness evaluation (URFE) approach, based on the processing and analyzing of massive historical bus GPS trajectory data. Specifically, URFE first takes full advantage of the unique features of fixed bus routes to significantly improve the efficiency of data processing. Then, it adopts a fault-tolerant method to deal with the possible errors of street maps; Finally, URFE completes the missing data by utilizing the inherent relationship between GPS errors of the same cars and roads, and utilizes an evaluation strategy by taking the influence of different GPS terminal devices’ qualities into account. Using the bus trajectory data within the second ring road of Chengdu during one month, we evaluate the effectiveness of our approach. Environments friendliness of 5648 different road segments has been evaluated, whose rationality has been verified by checking real satellite maps and street views.

location based service; GPS positioning error; data analysis; map matching; smart city

2016-08-16；

2016-10-27

国家自然科学基金重点项目(91546203) This work was supported by the Key Program of the National Natural Science Foundation of China (91546203).

王亚沙(wangyasha@pku.edu.cn)

TP391