Research On Real-time Travel Destination Prediction Based On Sequential Patterns Mining

With the development of economy,the increasing number of travel modes and the continuous progress of GPS(Global Positioning System),sensors and other technologies,massive trajectory data become easy to obtain.These data not only describe the historical trajectory and spatio-temporal information of moving objects,but also reflect the intrinsic information of moving objects.Through the analysis and mining of trajectory data,real-time prediction of possible travel destinations can provide assistance in the overall traffic congestion prediction and road planning,on the other hand,it can also provide personalized services such as congestion avoidance for individual users according to the prediction results.Current trajectory prediction techniques are mostly based on off-line prediction of historical trajectories,which do not reflect the time constraints very well.This paper summarizes the related work of trajectory data processing and real-time data mining,proposes a real-time sequential pattern mining algorithm based on big data flow computing model.This algorithm can mine time-sensitive sequential patterns efficiently and accurately.On this basis,the algorithm is applied to the field of destination prediction,and a real-time travel destination prediction model is designed,which is verified on real data and the feasibility of the algorithm model is proved.The innovations of this paper mainly include the following two parts:Firstly,a computable real-time sequential pattern mining algorithm based on RTP(Real-Time Pattern)tree is proposed.On the problem of sequential pattern mining,traditional algorithms are mostly based on static data.For static data,data can be scanned many times in the process of mining,while real-time data is difficult to scan the current time data many times because of its continuous and massive characteristics.At the same time,in traditional mining scenarios,all sequential data are processed at one time,while real-time data are continuously transmitted.Traditional sequential pattern mining methods can not adapt to real-time problems very well.The main manifestation is that the generation of a large number of candidate sets will cause pressure on memory,multiple scanning reduces the operation speed,and can not meet the requirements of response time.And for real-time application scenarios,we need to mine time-sensitive sequential patterns.Traditional sequential pattern mining methods do not measure the time dimension.Therefore,this paper proposes an algorithm based on RTP tree,which combines the concept of time window in Spark stream computing and constructs RTP tree to store time stamps,patterns,frequencies in tree nodes,uses tree update and aging mechanisms to measure the time dimension reasonably,thus resolving the problems of data repeated scanning and memory pressure in real-time sequential pattern mining.Aiming at the realtime response requirement,based on GraphX,distributed large graph is used to effectively store and calculate the node data of the tree on a large scale.Secondly,a real-time travel destination prediction model is designed and implemented.Traditionally,the research of travel destination prediction focuses on the application and improvement of Markov model.In recent years,with the emergence of neural networks,there are more and more research on the application of neural network model to solve the problem.However,both Markov model and neural network have their limitations.Markov model is limited by the dimension of state transition,so the prediction accuracy is difficult to be guaranteed.Neural network has a strong learning ability,but it has a large amount of calculation,so it is difficult to meet the demand of real-time mining response.Therefore,this paper uses the real-time sequential pattern mining algorithm based on RTP tree and trajectory sequence processing method to design and implement the real-time travel destination prediction model.The model is divided into three steps.Firstly,the GPS data is mapped into the map grid.Then,the real-time sequential pattern mining algorithm based on RTP tree is used to obtain the current sequential pattern for a period of time.Finally,the prediction results are obtained by matching the target trajectory with the current frequent pattern.Through a series of experiments on real taxi data,it is proved that the model can predict possible real-time travel destinations in big data scenarios,and is better than Markov model in prediction accuracy.