基于Spark与粒子滤波算法的公交到站时间预测系统

来源:用户上传      作者:

　　摘 要：针对公交车到站时间预测准确性不高的问题，选用具有流式计算特点的粒子滤波（PF）算法，建立了一个公交到站时间预测模型。为更好地解决使用PF算法过程中存在的预测误差及粒子优化选择问题，通过引入上一趟公交车的行驶速度和构造观测值的方法对预测模型进行改进，使之具有更贴近实际路况的公交到站时间预测精度，并且能同时预测多个公交到达时间。基于该模型和Spark平台实现了一套公交到站时间实时预测软件系统，所有到站时间预测结果与实际相比，平峰的最大绝对误差为207s，平均绝对误差为71.67s;高峰的最大绝对误差为270s，平均绝对误差为87.61s，而预测结果的平均绝对误差在2min以内是公认的理想结果。实验结果表明，所提模型及实现系统能准确预测公交到站时间，满足乘客实际需求。
　　关键词：公交到站时间预测;粒子滤波算法;流计算;Spark
　　中图分类号： TP311
　　文献标志码：A
　　Abstract： To improve the accuracy of bus arrival time prediction， a Particle Filter （PF） algorithm with stream computing characteristic was used to establish a bus arrival time prediction model. In order to solve the problems of prediction error and particle optimization in the process of using PF algorithm， the prediction model was improved by introducing the latest bus speed and constructing observations， making it predict bus arrival time closer to the actual road conditions and simultaneously predict the arrival times of multiple buses. Based on the above model and Spark platform， a real-time bus arrival time prediction software system was implemented. Compared with actual results， for the off-peak period， the maximum absolute error was 207s， and the mean absolute error was 71.67s; for the peak period， the maximum absolute error was 270s， and the mean absolute error was 87.61s. The mean absolute error of the predicted results was within 2min which was a recognized ideal result. The experimental results show that the proposed model and implementated system can accurately predict bus arrival time and meet passengers actual demand.
　　Key words： bus arrival time prediction; Particle Filter （PF） algorithm; stream computing; Spark
　　0 引言
　　构建云计算支撑的智慧交通平台是大数据等新技术在城市公共交通领域的重要应用，其中，公交车辆到站时间预测是核心研究内容和研究热点，利用公交大数据及有效数据分析模型准确地预测公交车到站时间，能够为市民带来更好的城市出行体验，对推进城市公共交通的发展、提升智慧交通普及推广具有重要意義[1]。
　　对于人口密集、路况复杂多变的城市，很难找到一个通用且准确高效的公交车到站时间预测模型，尤其是那些由于城市建设、道路维护等原因使得公交路线经常发生改变的城市，由于这类状况的持续时间长短不一，对公交车的到站时间预测是一个很大的挑战。目前，现有公交车到站时间预测相关研究已取得较多进展，但仍然存在以下问题：首先，基于大数据训练挖掘的预测模型往往由于训练的数据量不够大而导致所构建的模型预测精度不高，难以应对上述复杂公交行驶情况;此外，近年来兴起的基于实时数据处理的模型因较多应用限制条件也往往存在预测精度不高的问题。其次，目前大多研究都将重点放在预测模型的理论研究及实验评估方面，而在实际中，需要的不仅仅是一个适用、准确的模型，更是一个从数据采集、接入、存储、清洗到数据处理的一整套大数据平台化的解决方案，上述每一个环节都是公交车到站时间预测系统的重要部分，特别地，预测模型若使用成熟的大数据分析相关技术加以优化支撑，其预测效率将会大大提高。
　　本文在具有流式计算特点的粒子滤波（Particle Filter， PF）算法的基础上进行优化，建立了一个公交到站时间预测模型，并通过引入最近上一趟公交车的行驶速度和构造观测值的方法，改善了使用PF算法预测公交车到站时间时存在的预测误差及粒子优化选择问题，使改进后的PF算法具有更高的预测精度，并且能够同时预测多个公交到达时间。此外，本文还利用Hadoop Spark平台的优势，使用Spark Streaming流式计算框架实现了一套基于上述改进模型的公交到站时间实时预测软件系统，该系统能够准确高效地预测公交系统中所有未到终点站的公交车到达其后各站点到站时间，充分满足乘客对公交车到站时间的日常需求。 　　1 相關工作
　　公交车到站时间预测模型及方法主要基于机器学习类算法，如支持向量机（Support Vector Machine， SVM）和人工神经网络等，以及基于滤波算法，如卡尔曼滤波（Kalman Filtering， KF）和粒子滤波（PF）等。典型研究详述如下。
　　文献[2]中使用基于多标签分类的神经网络对公交车到站时间进行预测，实验结果发现神经网络的表现要好于决策树、随机森林和朴素贝叶斯方法;该文还探讨了使用AdaBoost算法和RakEL算法的集成神经网络，发现RakEL集成模型在多标签精度方面表现得更好。
　　文献[3]中提出了一种聚类和神经网络相结合的公交车到站时间预测模型。该模型中结合了天气、节假日等因素，分时段对公交车的到站时间进行预测。实验表明该模型要优于传统的BP神经网络，而且因为关键算法使用了MapReduce框架进行实现，所以模型适合处理海量数据。基于人工神经网络进行建模的方法在实际应用中存在两类问题：首先训练神经网络需要大量的数据和时间，一个训练好的模型很难适用到不同路况中，使得训练过程需要不间断地进行，消耗大量的计算能力;其次，计算结果很难即时体现出城市公共交通、道路建设以及路况等这些实时性较高的因素对预测结果的影响。
　　文献[4]中将KF算法应用到公交车的到站时间预测问题中，实验表明使用KF模型或者使用基于KF的混合模型在预测公交车到站时间时具有较好的预测精度。文献[5]中提出了一种基于SVM和KF算法的快速公交系统到站时间预测混合模型，首先使用SVM对到站时间进行预测，然后使用KF算法对预测结果进行动态调整。实验表明，该模型的预测精度高于基于KF的预测模型。文献[6]中提出了一种基于长短期记忆神经网络和KF算法的公交车到站时间预测模型，同样先使用长短期记忆神经网络作为静态模型进行预测，随后使用KF模型进行动态调整。实验表明，联合使用长短期记忆神经网络和Kalman模型在预测精度和预测结果稳定性方法要好于联合使用SVM和Kalman模型。但是KF在非高斯程度较大的系统中，会发生预测精度下降的问题。
　　文献[7]中将PF算法运用到公交车到站时间预测的问题中提出了一种基于PF的公交车到站实时预测系统。该文使用相对百分误差（Mean Absolute Percentage Error， MAPE）以及与基于KF方法作对比的方式对预测结果进行评估，结果表明该文中的PF模型实验结果的精度优于KF算法，而且该模型能够较好地捕捉高度变化的路况信息;但文中缺乏将模型在应用层面的实现并需针对实际需求作进一步完善。
　　2 公交到站时间预测模型
　　公交到站时间预测模型的分析和建立包括：预测计算需求的分析，基于需求的计算框架的选择及平台搭建，基于行驶数据的数据预处理，以及基于计算框架预测算法的选择及改进，最后给出基于改进PF算法的公交到站时间实时预测模型。
　　2.1 计算需求的分析
　　首先需要对公交到站时间预测问题作计算上的需求分析，确定所使用的计算框架，并据此选择合适的算法来建立预测模型。
　　2.1.1 计算框架的选择
　　经过对呼和浩特公交现状调研发现，所有公交车上的GPS设备每隔一个固定的时间段（通常为15s）会将自身的包括位置信息在内的行驶数据发送给服务器，这种数据具有实时到达且不受系统管理等流式数据的特点。对于服务器而言，每趟公交车行驶数据的到达时间是可知且均匀的，且数据流量不会发生猛烈的波动。经过以上的分析发现，公交车到站时间实时预测系统的应用场景具有一定的实时计算需求，但是这种计算能力又与Samza和Storm这种实时计算框架在使用场景中提供的计算能力不同。对于公交车的到站时间，计算并不需要发生在每一条GPS记录到达的时刻，即计算不需要时刻进行，只需要每隔一小段时间对一小批新的GPS记录计算一次即可。具有小批次处理特点的Spark流计算框架更适合上述应用场景，且计算能力足够应对预测计算需求[7]。
　　其次，在对公交车的到站时间进行预测时，往往需要实时数据与历史数据互相配合来进行计算，而Spark自身的Spark Streaming流计算框架中的窗口操作支持对一段时间（如一天或一周）之内的数据集合进行流式处理，这样可以满足预测过程中需要部分历史数据的需求。
　　5 结语
　　本文基于具有流式计算特点的PF算法研究公交到站时间预测问题，通过引入最近上一趟公交车的行驶速度和构造观测值的方法，构建新的预测模型，解决了使用基本PF算法过程中存在的预测误差及粒子优化选择问题。基于该模型和Spark平台实现一套公交到站时间实时预测软件系统，实验结果表明，本文所提模型及实现系统具有较高的公交到达时间预测精度，能满足公交到站时间的日常需求。
　　参考文献：
　　[1] LI J L， GAO J， YANG Y， et al. Bus arrival time prediction based on mixed model [J]. China Communications， 2017， 14（5）： 38-47.
　　[2] KEE C Y， WONG L P， KHADER A T， et al. Multi-label classification of estimated time of arrival with ensemble neural networks in bus transportation network [C]// Proceedings of the 2nd IEEE International Conference on Intelligent Transportation Engineering. Piscataway， NJ： IEEE， 2017， pp.150-154. 　　[3] 谢芳，顾军华，张素琪，等.基于MapReduce聚类和神经网络的公交车到站时间预测模型[J].计算机应用，2017，37（S1）：118-122. （XIE F， GU J H， ZHANG S Q， et al. Predicting model of bus arrival time based on MapReduce clustering and neural network [J]. Journal of Computer Applications， 2017， 37（S1）： 118-122.）
　　[4] YU B， YANG Z， YAO B. Bus arrival time prediction using support vector machines [J]. Journal of Intelligent Transportation Systems， 2006， 10（4）： 151-158.
　　[5] 陳旭梅，龚辉波，王景楠.基于SVM和Kalman滤波的BRT行程时间预测模型研究[J].交通运输系统工程与信息，2012，12（4）：29-34. （CHEN X M， GONG H B， WANG J N. BRT vehicle travel time prediction based on SVM and Kalman filter [J]. Journal of Transportation Systems Engineering and Information Technology， 2012， 12（4）： 29-34.）
　　[6] 范光鹏，孙仁诚，邵峰晶.基于LSTM和Kalman滤波的公交车到站时间预测[J].计算机应用与软件，2018，35（4）：91-96. （FAN G P， SUN R C， SHAO F J. Bus Arrival time prediction based on LSTM and Kalman filtering [J]. Computer Applications and Software， 2018， 35（4）： 91-96.）
　　[7] DHIVYABHARATHI B， KUMAR B A， VANAJAKSHI L. Real time bus arrival time prediction system under Indian traffic condition [C]// Proceedings of the 2016 IEEE International Conference on Intelligent Transportation Engineering. Piscataway， NJ： IEEE， 2016：18-22.
　　[8] ZAHARIA M， CHOWDHURY M， FRANKLIN M J， et al. Spark： cluster computing with working sets [C]// Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing. Berkeley， CA： USENIX， 2010： 10.
　　[9] 王法胜，鲁明羽，赵清杰，等.粒子滤波算法[J].计算机学报，2014，37（8）：1679-1694. （WANG F S， LU M Y， ZHAO Q J， et al. Particle filtering algorithm [J]. Chinese Journal of Computers， 2014， 37（8）： 1679-1694）.
　　[10] 周雪梅，彭昌溆，宋兴昊，等.基于前车数据的动态公交车辆到站时间预测模型研[J].交通与运输（学术版），2011（B12）：52-56. （ZHOU X M， PENG C X， SONG X H， et al. Prediction model of dynamic bus arrival time based on the front bus data [J]. Traffic & Transportation， 2011（B12）： 52-56.）
　　[11] 涂利明.基于前车与经验数据的车辆到站时间预测模型[J].计算机时代，2015（1）：1-3. （TU L M. Prediction model of bus arrival time based on front bus data and empirical data[J]. Computer Era， 2015（1）： 1-3.）
　　[12] The Scala Programming Language [EB/OL]. [2017-10-08]. https：//www.scala-lang.org
　　[13] Apache Kafka： a distributed streaming platform [EB/OL]. [2017-05-03]. http：//kafka.apache.org
转载注明来源:https://www.xzbu.com/8/view-14941679.htm