Taxi Trajectory Destination Prediction With Long-term Dependencies

With the rapid development of information,communication technology and Global Positioning System(GPS),the trajectory data generated by the moving objects such as vehicles,human beings and animals during the moving process shows an explosive growth trend.Widespread use of LBS(Location-Based Services)makes it urgent to predict the trajectory destination.Trajectory prediction has become a hot research topic.The trajectory prediction for taxis is more representative of people’s daily activities as taxis have become the first choice for people to travel daily.This thesis takes taxi trajectory destination prediction as a research issue,and studies destination prediction methods.The main contents are as shown follows.(1)Prediction taxi destination by regularized RNN with SDZ from trajectories with long-term dependenciesTrajectory destination prediction suffers from the “long-term dependencies” problem,which affects the prediction accuracy.The traditional Markov methods rely on 2 or 3 GPS points before destination only,which is not suitable for trajectories with long dependencies.The long-term dependencies occur when the number of GPS points that the destination depends on increases,and the correlative points of prediction are too far from the output time.The multiple hidden layers of RNN(Recurrent Neural Network)can store the dependencies,thus solving the impact of long-term dependencies on prediction accuracy.However,with the growth of dependencies and the depth of layers,the hidden layers of RNN become very sensitive to smaller perturbations which cause the wrong components of middle state to be exponentially amplified.Smaller perturbations can cause the parameters to exponentially decrease or increase when back propagation,resulting in gradient disappearance or gradient explosion.The “Memory Loss” occurs while RNN unable to learn dependencies between trajectories,which leads to lower prediction accuracy.The SDZ regularization method is applied to solve the long-term dependencies and improve the prediction accuracy,and this thesis proposed PDLRS(Prediction taxi Destination with Long-term dependencies by regularized RNN with SDZ).Firstly,SDZ preserves some output neurons in RNN probably,the parameters of abandoned neurons are also abandoned,which reduces the number of parameters in RNN and improves generalization ability.Secondly,SDZ uses the feedback loop to calculate the output of preserved neurons,and controls the gradient within a certain range,which can avoid the gradient disappearance,gradient explosion effectively,“Memory Loss” and solve the long-term dependencies,improving the robustness of RNN.In particular,the parameters are not updated when the feedback ratio is zero.Thereby the number of update times is reduced and training time is saved.Experiments with Porto Taxi Trajectories dataset show that PDLRS improves the prediction accuracy by 12% than the ordinary RNN prediction methods with general regularization,at the same time,the training time is reduced by 7%.(2)Fast prediction of taxi destination with long-term dependenciesThe calculation of current hidden state and memory cell state depends on the hidden state of the previous moment when using RNN to predict the trajectory destination.The order dependence of this state calculation requires a lot of time and hardware resources,affecting the prediction accuracy.In order to speed up the training and prediction speed,and make the model have better processing ability for long-term dependencies at the same time,this thesis proposed Fast resolution of taxi Destination Prediction with Long-term dependencies(FDPL).On the one hand,FDPL replaces the RNN cell with SRU(Simple Recurrent Unit)to speed up training and prediction.SRU can eliminate the dependence of current state on the previous moment hidden layer state.The current states are calculated with the simple multiply by element-wise rather than complex matrix multiplication,improving the efficiency of training.On the other hand,SDZ regularization method reduces the number of parameters and update times,saves training time,avoids “Memory Loss” and solves long-term dependencies.The combination of SRU and SDZ can quickly resolve long-term dependencies,achieve fast prediction.Experiments with Porto Taxi Trajectories dataset show that the training time of FDPL is 1/4 of RNN or LSTM ordinary prediction methods.(3)Multi-features taxi destination prediction with frequency domain processingThe simple prediction methods using neural network input the GPS points as spatial point sequences into the artificial neural network sequentially,ignoring the spatiotemporal relationships between trajectory data.Then,many methods transform the GPS trajectories into two-dimensional images,expressing the spatiotemporal relationships by images.However,the transformed images are sparse and contains noise because the trajectories are sparse and complex.Since the frequency domain of images can represent the change degree of images,removing the noise,and different frequency domain representations of trajectory images can reveal different features.So,this thesis proposed Multi-features Taxi Destination Prediction with Frequency Domain Processing(MTDP-FD)by importing frequency domain processing to trajectory destination prediction.Frequency domain process reduces noise while alleviating data sparsity by enriching features.Firstly,MTDP-FD transforms the trajectory images into frequency domain representations by fast Fourier transform and its reverse,reducing the noise and revealing features.Then,CNN(Convolutional Neural Network)is adapted to extract the deep features from the processed trajectory images to reduce dimension as CNN has a significant learning ability to images.Next,RNN is adapted to predict the taxi destination,the deep features are combined with trajectory data,trajectory metadata which act as the input of RNN,alleviating data sparsity by feature combination effectively.Experiments with Porto Taxi Trajectories dataset show that the average distance error of MTDP-FD is 0.14 km lower than that of existing methods,and obtain the best combination ways of data and features.