Research On User Mobility Trajectory Pattern Mining Algorithms Based On MapReduee

In recent years, mobile communication technology and location-aware technology have gained rapid development. Intelligent mobile terminals with location-aware technology have become popular in people’s life. In addition, a variety of mobile applications, which are based on location-aware service, such as micro-blog, Facebook and Didi Taxi, have become popular. This makes it possible to access the accurate trajectory data of massive users.Billions of user movement trajectory data include such basic information as position, time and speed which can reflect users’ movement trajectory truly and effectively.And the mobility behaviors of most users often have certain habits and preferences, presenting a certain regularity on the time and space sequence.Using a specific algorithm to excavate these orbital data, we can find out the regularity of these users’ movement effectively, digging out those meaningful, potential trace sequences, which is the user movement trajectory pattern.These models have important practical significance, providing powerful decisions for city planning, user group distribution research, business activities and other fields.Aimed at the problems above, this paper studies relevant theories and algorithms in the domain of sequence mode excavation. First of all, due to the characteristics of the original data of user movement trajectory, incompleteness, containing noise and inconsistency, the original data containing noise goes through a process of washing and transformation and the arrest point sequence is abstracted from the original GPS sequence. Then a density-based CP-OPTICS cluster algorithm is proposed, which divides the data sets to a number of grid units at first, then introduces the concept of weighted information entropy to the divided grid units, and calculates the smallest density threshold value of each grid unit self-adaptively through calculating the weighted information entropy.The concept of dense grid is put forward to the grid cell which meets the smallest density threshold value. The method of replacing data point set of grid with centroid point is adopted so as to compress data points.At last, using original OPTICS to output the cluster ordered reachability graph, then extract the collection of users’ important place from arrest point sequence on the graph.The gathering of important places of these clients will be taken as the data resource of sequence mode excavation.Next, map the original user movement trajectory and collection of important places of the user, change into Boolean matrix, improve Apriori algorithm, which is the traditional association rule mining algorithm, and propose FMA_Mining sequence mode excavation algorithm, which introduces Flag logo identifying consecutive items by Flag logo and simplifies matrix elements reading and column vector operation.Specific to the large scale of data in dense-data-type environment, matrix segmentation and parallel process are introduced in the algorithm. By using the MapReduce parallel processing framework, Trajectory Sequence model is successfully exploited on the Hadoop platform.At last, a contrast test is carried out between the improved algorithm and current algorithms including DBSCAN, OPTICS and Apriori, proving that the algorithm suggested shows good accuracy and can meet the demand of sequence mode excavation of moving track in the data-intensive environment.