Research And Implement Of Next Position Prediction Method Based On Spatio-temporal Regularity

The technology of mobile internet and intelligent mobile phone greatly facilitate the popularity of location based mobile applications.Communication software(WeChat,etc)and social networks(Sina Weibo,etc)are used to share locations of users.Trajectory recording softwares(footprint,imxingzhe,etc)are popular for their track recording function.Lots of human position data are recorded every day.Position data,which contain user,time and position attributes,are common spatio-temporal trajectory data,as well as trajectory data.Potential value is contained in these trajectory data.Data mining based on user trajectory data has become a new branch of data mining subject,with great application value in fields of intelligent transportation,environmental monitoring,urban computing and so on.In the field of trajectory data mining,many researches have been proposed,such as recommendation system based on locations,destination prediction,trajectory prediction,public traffic condition prediction and user privacy protection.Trajectory data mining based on user trajectory has great application value in fields of intelligent city,environment monitoring and information protection.Among these application scenarios,one key step is user next position prediction.Overall,there are four steps to predict the next position of one usre.They are user trajectory recording,historical trajectory data filtering,trajectory pattern mining and next position prediction.A common method to record user position is installing tracing applications on intelligent mobile phone.Affected by obstacles,GPS signal would be too weak to realize accurate positioning,abnormal data might contained in original trajectory data.Before trajectory pattern mining,abnormal data should be filtered.Trajectory patterns are modeled in pattern mining stage,and then used to predict next position according to current position of the user.Grid based method and hidden Markov model based method are popular approaches to mine trajectory patterns.While,existing methods only utilize spatial information,and don't make the best of temporal information contained in trajectory data to perform pattern mining.In this paper,a position prediction system has been proposed,which utilizes not only spatial but also temporal regularity of object mobility.Historical trajectory data of the object is used to extract personal trajectory patterns to obtain candidate next positions.Each of the candidate next positions is scored by the proposed Spatio-Temporal Regularity-based Prediction(STRP)algorithm according to time components of patterns and current time.To fully utilize temporal information in trajectory,time similarity,trajectory periodicity and data velocity are taken into account in the algorithm.Furthermore,a sliding window based trajectory data preprocessing algorithm is proposed to remove abnormal data in original trajectories.An evaluation based on two different public trajectory data sets demonstrates that the proposed STRP algorithm achieves highly accurate position prediction,compared with benchmark algorithms like the Markov based approach,the hidden Markov based approach and the grid based approach.