基于集成朴素贝叶斯模型的在线地图匹配方法

韩京宇，陈可佳，刘茜萍

（南京邮电大学 计算机学院 计算机技术研究所，江苏 南京210003）

0 引 言

交通路网上移动对象追踪是智能交通、实时导航等位置相关服务的关键技术。其中地图匹配即移动对象实时采集的GPS经纬度坐标准确映射到电子地图上，是实现路网上移动对象跟踪或交通流分析的前提。由于GPS误差（几米到十几米）和地图数据本身的误差，准确的地图匹配是一个难点问题［1］。目前地图匹配分成离线全局算法和在线局部算法。前者根据轨迹上的观测点序列来匹配最可能的交通路网［1－4］，这类方法不仅具有较高的计算复杂度，而且不能满足在线地图匹配的要求。在线局部算法主要根据前一个已经匹配的路网点和当前的观测点来匹配路网［1，3，5－7］。目前这些方法主要根据各种空间距离相似度、拓扑结构等来判断匹配的路网，不能够对非空间因素和历史匹配轨迹加以利用，匹配精度不够理想。

历史是最好的老师，本文提出根据历史轨迹训练朴素贝叶斯模型，充分量化各种非确定因素，实现在线地图的概率匹配。同时，为了克服数据噪声和单个模型假设的偏差，采用集成学习（ensemble learning）技术训练多个匹配器，通过投票来确定最可能匹配的路网。本方法不仅考虑了空间、时间、拓扑等可直接观测因素，同时考虑了各种隐含因素对道路选择的影响，可以取得更好的匹配效果。

1 移动对象的地图匹配框架

一个典型的移动对象应用中，成千上万的移动对象在路网上运动，每个移动对象根据一定的位置汇报策略，不断将其当前观测点信息发送到服务器。服务器进行在线地图匹配，并存储和索引移动对象的轨迹，以响应从客户端发来的各种查询［8－10］。整个系统如图1所示。在这个系统中涉及到如下基本概念。

图1 路网上的移动对象管理框架

定义1 GPS轨迹：GPS轨迹T＝（g1，…，gi，…，gn）是一个GPS观测点序列，每个观测点gi＝（lat，lng，v，st），其中lat是观测点纬度，lng 是观测点经度，v 是观测点瞬时速度，st是观测点时间。

定义2 交通路网：交通路网G 定义为G＝（R，J），其中R 是路段集合，J 是路口结点集合。

定义3 路段：路段r＝（rid，start，end，len，geo），其中，rid 是道路标志，start是起点，end 是终点，len 是道路长度。geo是道路几何形状，用一条折现pl来表示，即pl＝（pi－1，pi）i＝1n，其中p0是pl的起点，pn是道路的终点，每个pi－1pi是一个线段。

定义4 结点：结点j 定义为j＝（jid，loc），其中jid是路网结点标志，loc＝（x，y）是j的地理位置坐标。

定义5 路径：给定路网上的两个点vi和vj，从点vi到点vj的一条路径ph 是前后相连的路段序列ph＝r1→r2→…→rn，其中r1.start＝vi，rn.end＝vj。

在移动对象运动中，给定移动对象当前GPS 观测点gi、前一个观测点gi－1和其匹配的路网位置点pi－1，地图匹配计算gi在路网上的位置点pi。

本文提出根据历史GPS轨迹的对应路径，采用集成学习策略训练多个朴素贝叶斯分类器进行地图匹配，最大程度地减小可能的误差。方法框架如下所述：

（1）对历史轨迹进行离线训练，采用集成学习技术，确定多个朴素贝叶斯分类器。

（2）对路网进行预处理，建立网格 （grid）索引GI［10］，以支持在线地图匹配中对观测点附件路段的快速检索。

（3）根据上一个匹配点pi－1和当前观测点gi，取pi－1和gi的欧式距离为搜索半径，在网格索引GI上以gi为圆心检索所有可能匹配的路段｛r1，r2，…，rn｝。然后，根据多个贝叶斯分类器的投票结果来预测最可能匹配的边。

在上述计算过程中，经常度量观测点到一个路段的距离，定义如下。

定义6 点线投影：给定一个GPS观测点gi和一个待匹配路段rj，gi在rj上的投影点pi应当满足

式中：dist（ck，gi）——ck和gi的欧氏距离。

定义7 点线垂直距离：给定一个GPS观测点gi和一个待匹配的边rj，gi到rj的垂直距离是gi到其在rj上投影点的欧氏距离。

2 地图匹配算法

本文综合考虑天气（wea）、时间段（time）、道路等级（level）、垂直距离（ds）、偏离夹角（di）、行程速度（sp）进行路网匹配。各因素含义如下：

（1）wea表示天气状况，取晴天、阴天和雨雪3 个不同的离散值。不同的天气，车辆倾向于选择不同的路段。

（2）time代表当前时间段，取离散值。不同的时间段由于作息规律、日照、灯光等原因，车辆对道路有不同的选择倾向。

（3）level代表道路等级，是离散变量，分成快速路、主干路、次干路和支路。一般来说，用户倾向于选择宽敞、快速的高等级路段。

（4）ds代表当前观测点到匹配路段的垂直距离，即点线垂直距离。一般来说，点线垂直距离越短，匹配该路段的概率越大。

（6）sp 代表从前一个观测点到当前观测点时间内的平均行驶速度。不同道路有不同的规定行驶速度。假设从pi－1到pi的路程为s，则s／（ti－ti－1）应该以高的概率拟合pi所在路段的规定速度。该变量充分考虑时间因素。

除上述可直接观测因素外，道路选择还受安全状况、拥堵状况、周边环境等因素的影响。这些因素很难以直接观测，但会通过大量的路径选择体现出来。为此，通过对历史轨迹的分析，获得道路选择的概率模型。

2.1 朴素贝叶斯模型的应用和训练

对历史GPS轨迹匹配进行挖掘分析，确定不同天气和时间段的朴素贝叶斯模型参数库，记为B。bp（wea＝a，time＝b）∈B 表示天气为a，时间段为b的朴素贝叶斯模型。确定了针对不同天气和时间段的模型参数后，对各个天气和时间段的GPS观测点按照算法1进行地图匹配。

算法1：matchBySingleBayes

输入：已经匹配的路径p0，…，pi－1；观测数据G＝（w，t，g），w、t、g 分别代表天气、时间段和GPS观测点；模型库B；索引GI；匹配半径ρ

输出：观测点G.g 的匹配点pi

（1）以GPS观测点g 为圆心，根据半径ρ查询GI 索引，获得m 条可能匹配路段｛r1，…，rk，…，rm｝。

（2）针对每个可能匹配路段rk计算level，ds，di，sp这4个特征变量（levelk，dsK，dik，spK），记为Xk＝（x1，…，x4）。

（3）在B 中选取满足bp.wea＝w 并且bp.time＝t的朴素贝叶斯模型。根据bp 和g，计算各个条件概率p（xj｜rk）（1≤j≤4，1≤k≤m）。

（5）在m 个路段中，选取满足p（rd｜g）≥p（rw｜g）（1≤w≤m）的路段rd。

（6）返回g 在rd的投影点。

道路等级参数学习：车辆行驶时，以不同的概率选择不同的道路等级。对相同的天气、时间段的所有GPS匹配路网进行如下统计：

（1）针对某类相同的天气和时间段，假设所有匹配的路径共包含n个点（p1，…，pn），将其分割成n－1个相邻匹配对（pi－1，pi）（2≤i≤n）。

（2）用ym和yn分别表示匹配点pi－1和pi的道路等级，可得

垂直距离参数学习：给定一个GPS观测点g，其到路段r的垂直距离按照定义7计算。距离越短，观测点属于r的概率越大。对相同的天气和时间段，匹配r 的点到r 的垂直距离服从高斯分布

这里x＝dist（g，r）代表g 到路段r 的垂直距离，u取0。方差在历史数据上挖掘获得，其无偏估计为

这里xi表示训练样本上观测点到匹配路段的垂直距离，取＝0。

这里夹角期望取uθ＝0，在训练样本上学习：针对相同天气和时间段，根据每一个路段上的所有匹配点，计算的无偏估计量。

行程速度参数学习：相对前一个匹配点pi－1，g 的n个可能的匹配点产生n 条可能的路径。在时间ti－ti－1内移动对象行驶的路程以高的概率拟合其行驶的速度。具体计算步骤如下：

（1）对于每一个可能的匹配点pi，采用改进的A＊算法在线计算pi－1pi的最短路径［11］，进而确定其行驶的路程，记为s。计算最短路径时，为了避免搜索过度，在grid索引上，以g为圆心，在vmax（ti－ti－1）半径范围内采用A＊算法进行搜索，其中vmax＝max（vi－1，vi）。

（2）计算可能匹配路段上的平均速度v＝s／（ti－ti－1）。

（3）在各个路段r上，速度分布符合高斯分布

这里uv代表该路段的速度期望，δ2v为该路段的速度方差。

不同的天气和时间段，不同的路段会有不同的速度期望和方差。针对不同天气和时间段，计算各个路段上的速度参数：uv和的无偏估计分别是和

2.2 集成学习算法设计

为了克服数据噪声和单个分类假设的偏差，在训练样本集合上，对不同样本赋予不同的权重，学习多个分类假设。算法如下所示。

算法2：ensembleLearningClassifier

输入：朴素贝叶斯匹配器个数M，训练样本Ω＝｛（E1，c1），…，（EN，cN）｝

输出：匹配器集合｛CF1，…，CFM｝，匹配器的权重向量wc

返回分类器集合｛CF1，…，CFM｝和权重向量wc；

算法输入中Ei代表训练样本特征即（wea，time，level，ds，di，sp），ci表示匹配结果。首先赋予每个样本初始权重1／N，这里N 代表训练样本数目。在样本集合上训练得到第一个分类器CF1。在测试过程，这个匹配器会将有些GPS轨迹点正确匹配，有些错误匹配。为了提高匹配精度，在新一轮迭代中，提高被错误匹配的样本的权重，同时降低正确匹配的样本的权重，产生匹配器CF2。如此程持续，产生M 个匹配器。

给定一个观测点g，M 个匹配器依据权重投票决定匹配路段，从而获得准确鲁棒的匹配结果。

3 实 验

以南京市区地图为基础，分别在实际轨迹数据和模拟轨迹数据上实验。南京市区地图从openmap 上下载（http：／／www.openstreetmap.org／），有732条道路，2432个交叉路口。道路等级通过人工确认标注，分成快速路、主干路、次干路和支路。实际的车辆在南京市道路上跑，对10辆安装了GPS的车辆附加了用单片机烧写的位置更新协议。收集了30天的实际数据，选取其中涉及40 条道路的轨迹数据，人工进行匹配确认。天气数据从http：／／www.weather.com.cn／上获得。模拟轨迹数据在南京市区地图上产生。具体模拟过程如下：100个移动对象在路网上不间断地运行48个小时，每隔30～60秒取一个GPS观测点。不同天气｛晴天、阴天、雨雪｝、时间段（一天分成12 个等长的时间段）和道路等级采用不同的速度参数。对每个GPS观测点根据高斯函数产生垂直距离、方向角偏差。不同的交叉路口采用不同的路段选择概率。表1给出了模拟数据的参数设置。

表1 模拟GPS轨迹参数

地图匹配精度prec定义如下

3.1 地图匹配性能分析

（1）搜索半径ρ对性能的影响

地图匹配时每次以ρ为半径在索引上查找可能匹配的路段，半径ρ越大，可能匹配的路段数目越多。设定ρ＝100，200，300，400，500，600米。图2 显示了在实际数据集和模拟数据集上随着搜索半径的增大，匹配精度的变化。从图2可以看出随着半径的增大，匹配精度起初线性提高。随后，伴随搜索半径的增大，精度提高迅速衰减。当达到一定数值后，随着半径增大，精度几乎没有变化。这是由于当搜索半径很小时，某些本该匹配的路段会丢失。随着搜索半径的增大，丢失的概率会变小，从而取得更高的匹配精度。但当半径达到一定程度后，新增加的备选路段一般不会是匹配的路段，因此精度不会再继续提高。

图2 匹配精度随搜索半径变化（实际和模拟数据）

（2）匹配器数目M 对精度的影响

该实验验证了集成多个匹配器的效果。图3显示了在实际数据集和模拟数据集上匹配精度随M 的变化。从图上可以看出，随着M 的增大，路网匹配的精度随之提高。在实际数据集上当M 达到6以后，在模拟数据集上M 增大到8以后，随着M 的增大，匹配精度基本上趋于稳定。

图3 匹配精度随M 变化（实际和模拟数据）

3.2 相关工作比较

本文方法，记为BA 和文献［1］中的greedy算法进了比较。文献［1］中根据垂直距离和偏离夹角来判断最可能匹配的路段。两种方法在不同的数据规模上取10次匹配精度的平均值，图4汇报了在实际数据和模拟数据上的匹配精度比较。从图上可以看出本文提出的方法稳定地优于文献［1］中提出的方法。主要原因在于本文方法不仅考虑了各种不能直接观测到的影响因素。而且针对不同天气和时间段，利用历史数据来训练概率模型，针对不同路段获得精准的模型参数，从而获得更好的匹配效果。

4 结束语

图4 性能比较（实际和模拟数据）

本文根据历史数据训练地图匹配的朴素贝叶斯模型；同时，为了克服数据噪声和单个模型的偏差，采用集成学习策略训练多个匹配器。在线地图匹配时，多个匹配器投票确定地图匹配点。本文的主要贡献在于：①提出根据历史数据训练朴素贝叶斯模型进行在线地图匹配，给出了各个概率参数的计算方法。②采用集成学习技术来提高匹配的精度和鲁棒性。

在实际数据和模拟数据上的实验表明该方法可以获得好的在线地图匹配性能。下一步研究将结合轨迹衍生模型进一步提高地图匹配性能。

［1］Matt Weber，Liu Ling，Kipp Jones，et al.On map－matching of wireless positioning data：A selective look－ahead approach［C］／／Proc of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems，2010：290－299.

［2］Lou Yin，Zhang Chengyang，Zheng Yu，et al.Map－matching for low－sampling－rate GPS trajectories ［C］／／Proc of 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2009：352－361.

［3］Paul Newson，John Krumm.Hidden Markov map matching through noise and sparseness ［C］／／Proc of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2009：336－343.

［4］Stefan funke，sabine storandt.Path shapes：An alternative method for map matching and fully autonomous self－localization［C］／／Proc of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2011：319－328.

［5］Ahmed Jawad，Kristian Kersting.Kernelized map matching［C］／／Proc of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems，2010：454－457.

［6］Adel Javanmard，Maya Haridasan，Li Zhang.Poster：Multitrack map matching ［C］／／Proc of the 10th International Conference on Mobile Systems，Applications，and Services，2012：503－504.

［7］SHEN Bin，JIANG Changjun，ZHANG Zhaohui，et al.Design and realization of a distributed map－matching system for massive GPS data［J］.Journal of Chinese Computer Systems，2007，28 （3）：479－481 （in Chinese）. ［沈斌，蒋昌俊，章昭辉，等.一种基于海量GPS 数据的分布式地图匹配系统的设计与实现 ［J］.小型微型计算机系统，2007，28 （3）：479－481.］

［8］DING Zhiming.Data model，query language，and real－time traffic flow analysis in dynamic transportation network based moving objects databases［J］.Journal of Software，2009，20（7）：1866－1884 （in Chinese）. ［丁治明.移动对象数据库模型、查询语言及实时交通流分析 ［J］.软件学报，2009，20（7）：1866－1884.］

［9］Nguyen T，He Z，Zhang R.Boosting moving object indexing through velocity partitioning ［C］／／Proceedings of the VLDB Endowment，2012，5 （9）：860－871.

［10］ZHOU Aoying，YANG Bin，JIN Cheqing，et al.Locatonbased service：Architecture and progress ［J］.Chinese Journal of Computers，2011，34 （7）：1155－1171 （in Chinese）.［周傲英，杨彬，金澈清，等.基于位置的服务：架构与进展［J］.计算机学报，2011，34 （7）：1155－1171.］