基于海量出租车轨迹数据的智能推荐系统研究

基于海量出租车轨迹数据的智能推荐系统研究

徐小奇 同济大学电子与信息工程学院

本文旨在通过对出租车历史行驶轨迹进行机器学习，分析乘客的移动模式和出租车司机揽客行为模式，研究和设计一个智能推荐系统。该系统主要有离线数据挖掘部分和在线数据资源发布部分组成，离线数据挖掘采用Oracle结合Hadoop进行，以SQL存储过程开发为主，在线数据资源发布采用Java Web编写发布程序。实验测试表明，本文设计的出租车服务智能推荐系统可为乘客推荐更容易找到空驶出租车的地点，为出租车司机推荐快速招揽到乘客的地点，并实现自适应实时路况的优化路径推荐。与传统关系数据库的方法比较，本文提出的Oralce与Hadoop结合的混合模式性能更高。

智能推荐；oracle；hadoop；数据挖掘；上客点；路段平均速度

引言

出租车是城市公共交通的重要组成,是以巴士、地铁、轻轨为主的大规模客运交通的合理补充，目前已投入运行的出租车调度管理系统效率比较低，不能适应城市交通状况与客源的时空变化，无法有效平衡出租车服务的供需关系。本系统旨在服务于乘客和出租车司机，一方面帮助乘客快速的找到空载出租车，另一方面为出租车司机提供寻找乘客的建议，并给出路径规划。为提高出租车运营的管理水平和效率，迫切需要建设一套符合杭州交通状况的出租车智能推荐系统。

1.系统功能的实现

1.1 功能模块实现

在系统需求分析中，提出了系统中各个模块的大致功能，下面对每个模块的功能进行叙述：离线挖掘模块,数据建模模块和在线推荐模块。

1.2 数据处理实现

离线数据处理包括预处理阶段和处理阶段，前者处理逻辑简单，侧重大数据的流式处理，后者分为停靠点侦测和路段平均速度计算。停靠点侦测采用潜在停靠点过滤算法对空闲旅程进行预过滤，设置时间阈值和距离阈值来判断该点是否为潜在停靠点。经过潜在停靠点算法过滤，相同路段上仍旧含有大量的点，接着使用聚类算法进行聚类，经过观察，当k=3或者k=4时，曲线趋于直线，结果得到有效收敛。

1.3 系统性能优化

数据挖掘过程，需要进行大量的运算，执行时间的长短影响挖掘的进度。本文提出三种优化机制，包括区域映射机制，Cache缓冲机制和多线程并行机制。

（1）区域映射机制[7][8]

区域优化: 采用区域机制，每个GPS点可以o(1)映射到区域Id，根据区域Id一般含有5～20路段，只需要判断200～400次，节省计算次数达到10～20倍。

（2）Cache缓冲机制

Cache优化：综合考虑内存消耗大小以及加载速度的问题，对路段、节点和停靠点进行一次性加载，对平均速度采取按照时间段进行分次加载，有效的减少访问数据库次数，加快系统整体的响应时间。

（3）多线程并行机制

多线程优化：单线程只能够分段从数据库中读取数据，且单次读取的数据不宜过多，否则加载数据会花费很长时间。多线程并行采用84个线程，每个线程处理1万个旅程，分10次读取，每次1000个旅程，同时写入数据库的过程采用Batch提交，能够极大提高写效率。

2.系统测试

本系统测试针对数据正确性测试，处理时间测试，功能测试等方面进行测试，其中数据正确性主要验证Oracle存储过程的处理逻辑，而时间处理性能则对数据挖掘部分的主要处理过程进行时间对比，最后测试系统功能路径规划。

（1）数据正确性测试

出租车行驶旅程转换成潜在停靠点，中间过程需要对相同路段上的潜在停靠点进行聚类。部分噪声点包括在其中，利用点与路段方向间夹角的特性对算法进行优化，聚类采用角度阈值进行过滤。

（2）处理时间测试

Hadoop集群(3台)处理的时间大为缩短，将出租车原始GPS记录从Oracle导入Hadoop集群的时间，Hadoop处理原始记录的时间，将处理得到的上下客、旅程等结果回导到Oracle中的时间，分别为10分钟、18分钟、5分钟，整体费时33分钟，相比Oracle存储过程需要200分钟，时间缩小6倍多，随着数据量的增大，Hadoop集群的优势会显得更加明显。

（3）系统功能测试

为了保证高度相似性，要求历史行驶数据的时间段与查询时间段相同，以及相同车辆不同天相同时间段行驶经过的路线，尽可能排除不同司机行驶行为习惯不一样导致的误差。如表格1所示。

表1 Oracle和Hadoop处理时间比较

3.结束语

本文工作首先对出租车智能推荐系统的背景进行研究，目前出租车调度管理系统使用对象以监管部门为主,乘客与出租车司机受益程度低，本系统针对乘客和出租车司机，对出租车原始GPS轨迹记录进行数据挖掘和数据建模，将信息发布供乘客和出租车司机使用。系统开发主要分成三部分，离线挖掘、数据建模和在线推荐。离线挖掘部分对出租车原始GPS记录进行处理，得到上下客热点以及路段的历史行驶速度，前者可以帮助乘客寻找上车点，出租车司机寻找乘客，后者用来进行路径规划，帮助出租车司机尽快到达目的地。数据建模部分，利用离线挖掘的数据以及道路网络信息可以完成路线的规划。在线推荐则将信息发布到网络上，方便乘客和出租车司机查询使用。最后，本文对离线挖掘部分大数据处理进行了些测试，对Oracle和Hadoop处理大数据的时间进行对比，与传统关系数据库的方法比较，本文提出的Oralce与Hadoop结合的混合模式性能更高。

[1]Fielding R T. Architectural styles and the design of network-based software architectures[D]. University of California, 2000.

[2]翟娜.Dijkstra最短路径算法改进研究及其在GIS-T仿真分析中的应用[J].测绘标准化,2010,(1);39-41.

[3]Jing Yuan , Yu Zheng , Liuhang Zhang , XIng Xie , Guangzhong Sun, Where to find my next passenger[C], Proceedings of the 13th international conference on Ubiquitous computing, September 17-21, 2011, Beijing, China

[4]Ankerst, Mihael, Markus M. Breunig, Hans-Peter Kriegel, and Jörg Sander. "OPTICS: ordering points to identify the clustering structure."[C] ACM SIGMOD Record 28, no. 2 (1999): 49-60.

[5]严寒冰,刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报,2000,23(2):210-215.

[6]Krishna, K., and M. Narasimha Murty. "Genetic K-means algorithm."[C] Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 29.3 (1999): 433-439.

[7]Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, andY. Huang. Map-matching for low-sampling-rate GPS trajectories[C]. In Proc. GIS. ACM, 2009.

[8]Powell J, Huang Y, Bastani F, et al. Towards reducing taxicab cruising time using spatio-temporal profitability maps[J]. Advances in Spatial and Temporal Databases, 2011: 242-260.