Path Recommendation Research Based On GPS Data And Frequent Pattern Mining

With the development of the economy,urban road construction is becoming more and more perfect.However,the rapid acceleration of the urbanization makes the supply speed of road construction still cannot catch up with the growth speed of people's demand for transportation.As the infrastructure of the national economy,road traffic plays an important role in the economic development,Therefore,the coordination and optimization of urban road traffic become very important.optimizing the travel route is an effective method to relieve traffic pressure,and it is also a research focus in the world.The traditional path recommendation method usually considers the road distance or the travel time,they usually convert road network into a graph,and exhaust the path according to the depth-first search or the breadth-first search,and finally calculate the optimal path that meets the requirements.However,it often becomes a difficult problem in the case of a large road network because of exhausting the path,and cannot meet the requirements of computational efficiency.Moreover,when we have massive GPS historical data,the path can be recommended in combination with data mining.So,this paper combines the massive GPS historical trajectory data and imports frequent pattern mining,to recommend the path between the two points in terms of use frequency.In the aspect of data preprocessing,this paper proposes an effective data cleaning method for the characteristics of the open source GPS,to identify and filter the defect data and trajectory data which is sampled sparsely or misses point information,and the drift data is smoothed to ensure the integrity and richness of the trajectory data information.Secondly,based on the trajectory shape,this paper identifies and extracts the road network ports by calculating the direction angle of the trajectory.In this process,the information redundancy and the number of iterations of the algorithm are reduced by processing the stagnation point of GPS trajectory data.and the inflection point clustering is simplified by the distance judgment mechanism at the same time.The experimental analysis shows that the intersection extraction method has high accuracy and calculation speed under massive data.In the aspect of path recommendation,this paper introduces PrefixSpan algorithm,and on this basis,a new frequent pattern mining algorithm Path-PrefixSpan which can adapt to the path are proposed,with this algorithm,we can construct a candidate frequent path set containing all the start-end points.And according to the characteristics of the set,we proposed an efficient index structure to realize the fast query of candidate frequent paths from any starting point to the end point.We also proposed an indicator of frequency to calculate the most frequent path between two points.It solves the problems of existing algorithms,for example,recommended path has infrequently used segment or has low turnover rate or has low usage rate.Finally,this paper conducts experiments to prove the feasibility and efficiency of the proposed algorithm.