Research And Implementation Of Significant Place Sequential Pattern Mining System Based On Spatial-Temporal Trajectory

In recent years,the trajectory data generated and stored by mobile devices has shown explosive growth.The potential significant places in the trajectory play a key role in providing location-aware services for users,and can reveal the important movement rules of users.In addition,the pattern mining considering the temporal relationship between items can identify the sequential rules hidden in significant places,and further obtain the user’s behavior habits,helping the offline real economy industry develop better.The existing research on significant place mining mainly focuses on density clustering,and there are difficulties in processing data with different local density and intuitive boundary point allocation problem.Additionally,the subsequent research on pattern mining ignores the temporal relationship and utility between significant places,resulting in the inability to effectively mine significant place high utility sequential patterns.Therefore,this thesis designs and implements a set of significant place sequential pattern mining system.Through studying the data field theory and community detection methods,mining and analyzing complex original trajectory data,identifying significant places,and completing the high utility sequential rule mining for non-semantic annotated significant place items,meeting the requirements of efficient and accurate significant place sequential pattern mining.The experiment shows that compared with the existing methods,the system has an average improvement of 16.8% and 72.8% in Silhouettes and significant place mining efficiency,respectively.Moreover,it can effectively complete the high utility sequential rule mining of significant places under the condition of low time and memory consumption.The main research contents of this thesis are as follows:(1)Extraction of spatial-temporal correlation characteristic points based on index neighborhood.Aiming at the problems of drift,redundancy and missing of trajectory data in real life,this thesis uses the index neighborhood to reduce the deviation of speed calculation.Using the raw trajectory data directly can improve the robustness of the subsequent clustering algorithm,but its traversal space is still huge.In view of this problem,this thesis proposes a corresponding low-velocity index neighborhood characteristic points extraction strategy to reduce the traversal space,which makes the subsequent label propagation based significant place mining algorithm require significantly less time and space.(2)Improvement of clustering method based on density distance measure.The traditional significantly place mining method mainly uses the measure based on density distance to cluster trajectories.However,the clustering method based on density distance measure is hard to deal with data with different local densities and intuitive boundary point allocation problem.Combining data field theory and community detection methods,this thesis proposes a significant place mining method based on label propagation,which uses graph structure to dynamically capture the domain radius and consider the local spatial-temporal structure of characteristic points,so as to better solve the above two problems and improve the accuracy of significant place mining results.(3)High utility serialization of significant place pattern mining.The significant places extracted from user trajectory mining constitute a sequence of significant places in time,while the existing pattern mining methods almost only consider unordered items.The high utility sequential rule mining method adopted in this thesis can better deal with the sequential relationship between significant places,and can also give different importance degrees,that is,utility,to different significant places according to user needs,so as to more effectively mine and analyze the high utility sequential rules existing between significant places of users.