﻿ 基于机器学习的智能出租车预测系统
 计算机系统应用  2018, Vol. 27 Issue (9): 61-67 PDF

1. 福建师范大学 数学与信息学院, 福州 350007;
2. 厦门大学 信息科学与技术学院, 厦门 361005

Intelligent Taxi Forecasting System Based on Machine Learning
YE Feng1, OUYANG Zhi-Chao2, CHEN Wei-Biao1, ZHOU Yi-Qin1, ZHOU Xiao-Ling1
1. School of Mathematics and Informatics, Fujian Normal University, Fuzhou 350007, China;
2. School of Information Science and Engineering, Xiamen University, Xiamen 361005, China
Foundation item: Natural Science Foundation of Fujian Province (2017J01739); Research Project on Teaching Reform of Fujian Normal University (I201602015)
Abstract: To bring more reasonable scheduling of taxi resources, this study proposes an intelligent taxi forecasting system based on machine learning. Firstly, the GPS data set of Porto taxi is preprocessed, and a part of the training sets are taken as the research object. Then the echo state network algorithm is used to predict the travel destination of the taxi under the premise of predicting the travel destination. Finally, the taxi arrival time is predicted by using random forest algorithm in the same circumstances. Experiments show that the system can predict the actual taxi destination of the part of the journey and the time required for the journey, thus achieved the purpose of reducing the waste of taxi resources based on the current Porto taxi GPS data set.
Key words: taxi forecast     Porto data set     echo state network     random forest

1 系统总体结构设计与分析

 图 1 系统总体结构图

 图 2 系统工作流程图

2 波尔图出租车GPS数据集 2.1 数据集描述

2.2 数据集分割

1) 分割的脚本命令:

split -l 200,000 train.csv -d -a 2 train_

2) 把原来1.80 GB的train数据集分割成每个200 MB的数据集并对其批处理重新命名:

for i in *

do mv $i$i".csv"

done

2.3 数据集预处理

1) TRIP_ID(String):它包含每个行程的唯一标识符.

2) POLYLINE(String):它包含映射为字符串的GPS坐标(即WGS84格式)列表. 字符串的开始和结尾分别用括号(即“[”和“]”)标识. 每对坐标也由与[LONGITUDE, LATITUDE]相同的括号确定. 该列表包含每15 s行程的一对坐标.

3 基于回声状态网络算法预测目的地 3.1 预测流程

 图 3 回声状态网络算法预测目的地流程图

3.2 评估指标

 $\alpha {\rm{ = }}{\sin ^2}(\frac{{{\phi _2} - {\phi _1}}}{2}) + \cos ({\phi _1})\cos ({\phi _2}){\sin ^2}(\frac{{{\lambda _2} - {\lambda _1}}}{2})$ (1)
 $d = 2 \cdot r \cdot \alpha \tan (\sqrt {\frac{a}{{1 - a}}} )$ (2)

3.3 算法描述

ESN是一种特殊类型的递归神经网络, 其基本思想: 使用大规模随机连接的递归网络, 取代传统神经网络中的中间层, 从而简化网络的训练过程.

 图 4 回声状态网络结构图

 $\left\{\begin{gathered} u(n) = {[{u_1}(n),{u_2}(n),\cdots,{u_K}(n)]^{\rm T}} \hfill \\ x(n) = {[{x_1}(n),{x_2}(n),\cdots,{x_N}(n)]^{\rm T}} \hfill \\ y(n) = {[{y_1}(n),{y_2}(n),\cdots,{y_L}(n)]^{\rm T}}\hfill \\ \end{gathered} \right.$ (3)

 $\left\{\!\begin{gathered} x(n + 1) = f({\rm W}x(n) + {{\rm W}_{\rm {in}}}u(n) + {{\rm W}_{\rm {back}}}y(n)) \hfill \\ y(n + 1) = {f_{\rm {out}}}({{\rm W}_{\rm {out}}}[x(n + 1),u(n + 1),y(n)] + {\rm W}_{\rm {bias}}^{\rm {out}}) \hfill \\ \end{gathered} \right.$ (4)

3.4 模型建立

 图 5 回声状态网络模型

ESN使用具有泄漏集的离散时间连续值单元的递归神经网络(Recurrent Neural Networks, RNN)类型. 一般的更新方程如下[7]:

 ${\tilde x}(n) = \tanh ({\rm {W_{in}}}[1;u(n)] + {\rm W}x(n - 1))$ (5)
 $x(n) = (1 - \alpha )x(n - 1) + \alpha {\tilde x}(n)$ (6)

 $y(n) = {{\rm {W_{out}}}}[1;u(n);x(n)]$ (7)

${\rm{W_{out}}}$ 训练是根据岭回归进行的, 公式如下:

 ${\rm{W_{out}}} = {Y_{\rm{target}}}{X^{\rm T}}{(X{X^{\rm T}} + \lambda I)^{ - 1}}$ (8)

1) 训练阶段

 ${Y_{\rm {targ et}}}{X^{\rm T}} + = {y_{\rm {targ et}}}(n) \times x{(n)^{\rm T}}$ (9)
 $X{X^{\rm T}} + = x(n) \times x{(n)^{\rm T}}$ (10)

${Y_{\rm{targ et}}}{X^{\rm T}}$ $X{X^{\rm T}}$ 的尺寸分别为( ${N_y} \times {N_x}$ )和( ${N_x} \times {N_x}$ ). 如果我们考虑到目前为止所描述的架构, 并将连接输入和偏置的 $x$ 重写为 $[1;U;x]$ , ${N_x}$ 变为( $1 + {N_u} + {N_x}$ ).

2) 测试阶段

3.5 参数选择和评估

1) Nr, 储备池规模大小;

2) rho或sigma, 光谱半径或最大奇异值;

3) $\alpha$ , 泄漏率;

4) Lambda, 岭回归正则化参数;

5) Conn, 连接因子, 默认情况下为100%.

4 基于随机森林算法预测抵达时间 4.1 预测流程

4.2 评估指标

 $RMSLE = \sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {{{(\ln ({p_i} + 1) - \ln ({a_i} + 1))}^2}} }$ (11)

4.3 算法描述

 图 6 随机森林算法预测抵达时间流程图

4.4 抽取特征预测抵达时间

a)旅行时间和10个最邻近的Haversine距离.

b)内核回归特征.

a)在迄今为止观察到的部分轨迹的最后 $d$ 米和整个不完全行程上计算的平均速度, 其中 $d \in$ {10,20,50,100,200}. 这些功能在进行预测时传达最新的交通状况.

b)到目前为止观察到的不完整旅行的最后 $d$ 米的平均加速度, 其中 $d \in \{ 10,20,50,100,200\}$ .

c)形状复杂度: (欧几里德)行进距离与第一个和最后一个GPS位置之间的Haversine距离之间的比率. 具有更高复杂性的旅行(例如“z - zag之旅”(zig- zag trips)往往是出租车司机在城市周围开车寻找乘客的行程. z-zag的旅行时间往往较长, 所以事先确定这些行程是合理的.

d)通过计算任何一对连续GPS更新之间的速度来识别GPS踪迹中的缺失值. 如果估计的速度超过速度限制 $\hat v$ km / h, 即使在部分观察到的行程中只有一对连续的GPS更新, 该行程被标记为缺少GPS更新的行程. 我们使用速度限制 $\hat v \in \{ 100,120,140,160\}$ km/h, 缺少值的旅行往往有更长的旅程时间.

5 检测结果分析

5.1 出租车目的地预测实验结果

 图 7 部分训练集终点

5.2 出租车抵达时间预测实验结果

6 结语

 [1] Kusner M, Tyree S, Weinberger KQ, et al. Stochastic neighbor compression. In: Jebara T, Xing EP, eds. Proceedings of the 31st International Conference on Machine Learning. 2014. 622–630. [2] 本文使用的波尔图出租车GPS数据集下载官方网址: https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i/rules [3] Lukosevicius M, Jaeger H. Reservoir computing approaches to recurrent neural network training. Computer Science Review, 2009, 3(3): 127-149. DOI:10.1016/j.cosrev.2009.03.005 [4] Gallicchio C, Micheli A. Architectural and Markovian factors of echo state networks. Neural Networks, 2011, 24(5): 440-456. DOI:10.1016/j.neunet.2011.02.002 [5] Breiman L. Random forests. Machine Learning, 2001, 45(1): 5-32. DOI:10.1023/A:1010933404324 [6] Fulkerson B. Pattern recognition and neural networks. Technometrics, 2009, 39(2): 233-234. DOI:10.1080/00401706.1997.10485099 [7] Lukoševičius M. A practical guide to applying echo state networks. In: Montavon G, Orr GB, Müller KR, eds. Neural Networks: Tricks of the Trade. Lecture Notes in Computer Science, vol 7700. Springer. Berlin, Heidelberg. 2012. 86–124. [doi: 10.1007/978-3-642-35289-8_36] [8] Tiesyte D, Jensen C. Similarity-based prediction of travel times for vehicles traveling on known routes. Annals of GIS, 2008, 14(1): 1-10. DOI:10.1080/10824000809480633 [9] Lam HT, Bouillet E. Flexible sliding windows for kernel regression based bus arrival time prediction. Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2015. Lecture Notes in Computer Science. Springer. Cham. 2015. 68–84. [doi: 10.1007/978-3-319-23461-8_5] [10] Friedman JH. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 2001, 29(5): 1189-1232. DOI:10.1214/aos/1013203451 [11] Geurts P, Ernst D, Wehenkel L. Extremely randomized trees. Machine Learning, 2006, 63(1): 3-42. DOI:10.1007/s10994-006-6226-1