摘 要

目前大多数路径推荐系统使用的是传统的路径推荐算法，这类算法虽然能够提供理论上的最优解，但是在实际的交通系统中，路径推荐需要考虑的因素十分繁杂，传统的路径推荐算法已经不能满足需求。在这个大数据时代，数据挖掘和机器学习算法正在兴起，大数据Spark计算框架也在近几年应运而生，其分布式计算能力和强大的机器学习算法库备受关注。但是在交通路径推荐领域，Spark平台的使用几乎没有。

本文利用Spark大数据平台，以武汉市两天之内的上千万条出租车GPS历史数据进行数据挖掘，完成一个出租车路径推荐系统。设计过程中完成的主要工作如下：

1. 设计一个基于出租车GPS数据的路径推荐算法，使用K-means聚类算法对OD坐标聚类分析，以当前时间段内的区域平均速度作为路径权值，输出一条当前时间段内的推荐路径；
2. 在云平台上搭建Spark分布式计算集群，使用Python语言编写程序操纵原始数据并实现路径推荐算法，实现数据处理模块；
3. 借助百度地图API以及web开发工具完成可视化的网页客户端，使用Python语言编写一个简单的HTTP服务端。
4. 整合模块并测试完整的功能，即根据用户输入的出发地与目的地，结合历史数据，为出租车司机推荐一条合理的驾车路径。

测试结果表明，在历史数据足够充足，出发地和目的地合理的情况下，该系统可以提供当前时间段内的一条合理的行车路径。该系统完全脱离了城市交通路网的拓扑结构，具备计算速度较快，可扩展性强的优势。

关键词：数据挖掘；路径推荐；机器学习

Abstract

At present most route recommendation systems are using traditional route recommendation algorithms which can output the best solution theoretically but cannot meet the need of practical transportation system because so many variables should be taken into account. In this era of big data, with the rise of data mining and machine learning Spark was born consequently and its powerful distributed computing ability and fantastic machine learning library have got much attention in recent years. Nevertheless, there is few transportation systems taking advantage of Spark.

Based on Spark and millions of taxi GPS data in two days, this paper illustrate how to build a visualized route recommendation system. The main work completed in the design process is as follows.

1. A route recommendation algorithm was designed with taxi GPS data, in which the K-means algorithm has been applied for clustering process of origin and destination coordinates and regional mean velocity is regarded as confidence variable.
2. The Spark distributed cluster was built on cloud platforms. The route recommendation algorithm and data processing module were accomplished in Python.
3. A visualized web client was finished by web development tool and Baidu Map API. The simple HTTP server was created in Python.
4. Integrating those modules illustrated above, the author has completed the system where a proper recommendation route output with proper origin and destination input by user and adequate historical data.

As the result proves, according to proper origin and destination input by user and adequate historical data, this system is able to recommend a practical route for taxi driver. This system can work completely without topology structure of transportation network and it is highly extendible.

Key Words: data mining; route recommendation; machine learning;

目 录

第1章 绪论 1

1.1 课题研究背景及意义 1

1.2 国内外发展现状 1

1.3 论文的主要工作和章节安排 2

第2章 系统需求分析及总体设计 4

2.1 系统需求分析 4

2.2 路径推荐系统的总体结构 5

2.3 Spark平台的搭建 6

2.4 RDD特征及操作介绍 7

2.4.1 RDD 7

2.4.2 RDD的主要操作 8

2.5 数据处理模块的架构 9

2.6 可视化模块的架构 9

第3章 路径推荐算法 11

3.1 传统的路径搜索算法 11

3.2 基于路径库的路径搜索算法 11

3.3 基于聚类的路径推荐算法 12

第4章 数据处理模块 15

4.1 数据源和数据处理模块结构综述 15

4.2 数据清洗 16

4.3 路径库提取 17

4.4 OD聚类分析 19

4.4.1 K-means聚类 19

4.4.2 MLlib中的K-means 19

4.4.3 OD聚类分析 20

4.5 地图网格化分析 22

4.6 地图偏移问题 23

4.7 路径生成 25

第5章 可视化模块 26

5.1 网页客户端功能介绍 26

5.2 地图模块 26

5.3 HTTP服务器实现 27

第6章 系统测试 29

6.1 OD聚类效果测试 29

6.2 数据处理模块测试 30

6.3 可视化模块测试 30

6.4 系统测试 32

第7章 总结与展望 35

7.1 总结 35

7.2 展望 35

参考文献 37

致谢 39

绪论

课题研究背景及意义

本次毕业设计的课题名称为“基于Spark的城市出租车出行路径分析专家系统”。众所周知，出租车是城市公共交通的重要组成部分，但出租车在实际运营中，由于缺乏合理的规划和管理，导致空驶率较高、运营效率低下、司机收益较差等问题。本课题针对这一问题，开发一个基于Spark的城市出租车出行路径分析专家系统，旨在通过城市出租车的GPS移动数据，分析其流动情况和城市道路交通动态，推荐最佳运行方式，通过交通诱导系统，引导车辆运行，实现城市道路运行状态的优化。

国内外发展现状

由于出租车对人们的日常生活影响较大，而智能交通系统的发展给出租车的路线规划提供了相当便利的条件，因此国内外学者对这个问题有不同角度的研究。研究过程的主要进展如表 1.1发展历程 所示：

表 1.1发展历程

Hai Yang等从整体的市场运营方面研究，重点关注乘客与出租车之间的相互作用，根据供求关系挖掘出影响整个系统的因素。在此基础之上，他们又根据出租车的价格模型，采用基于路程和基于时间的出租车费用结构，研究出租车市场的监管和平衡性。Liao Z.根据GPS技术研究了整个车队的调度方法，并且提出众多变量如人类系统相关接口和操作环境应该考虑以达到系统的满负荷。将出租车个体作为研究对象，徐超提出了一种最可盈利化的模型^[1]，并且说明了出租车的路径选择在本质上是一种带权有向图的最短路径搜索问题。最短路径问题在上世纪60年代就早有研究，最经典的是Dijkstra算法，它使用贪婪策略解决了单源最短路径问题，在选择合适的数据结构的情况下，对于图G=(V,E)该算法的时间复杂度为O(|E| |V|)，近几年对于这个经典算法的研究从未停止。一方面是对算法执行过程中数据结构的改进^[2-3]，还有的研究直接将算法的使用范围缩小至路网系统，从实际经验出发进一步降低其时间复杂度^[4-5]。由于大数据，多核多线程计算模式的兴起，Dijkstra算法的并行化改进也备受重视。抛开Dijkstra算法，使用机器学习算法解决最短路径问题的研究也有所进展^[7-9]，甚至出现了将传统算法与遗传算法^[10-13]、神经网络^[14-16]等机器学习算法结合使用的混合算法^[16-19]。在计算平台的选择上，OpenCL、OpenMp的框架被广泛运用^[15]。而近几年出现的大数据Spark平台展现了它的巨大优势，特别是机器学习算法、数据挖掘方面^[20-23]。