Research On Frequent Trajectory Expression And Its Pattern Mining Algorith

In the context of big data,frequent pattern mining of spatial-temporal trajectories is a research hotspot in the field of data mining.It is an important method to analyze the behavior patterns and rules of moving objects.It has made good applications in many aspects such as location-based service based urban planning,transportation,travel services,tourism recommendations,and has brought far-reaching impact on economic development and social life.As one of the frequent patterns,the trajectory frequent pattern,on the one hand,spatial-temporal trajectory data not only has the three characteristics of time,location and semantics,but also has the characteristics of different lengths and complexity,which leads to the difficulty of trajectory expression and the difficulty of applying traditional frequent pattern mining algorithms directly.On the other hand,trajectory data belongs to massive large-scale data,and the mining efficiency restricts its application and development.To solve the above problems,this thesis proposes the research of frequent trajectory expression and its pattern mining algorithm based on the distributed computation mode.The main contents are as follows:(1)Aiming at the difficulty of trajectory expression caused by the characteristics of trajectory data such as different length and complexity,a heuristic distributed clustering algorithm for trajectory segments is proposed and designed to divide the common sub-line segments in the trajectory.The algorithm first determines the number of trajectory segment clusters,selects the center segment of each cluster,and then calculates the distance of the centroid of among other all trajectory segments and each center segment,and merges each trajectory segment into its nearest center segment cluster,and the clustering result with stable convergence is obtained through multiple iterations.The proposed algorithm uses geometric method to find cluster centers of trajectory line segments and cluster neighboring trajectories,reducing the influence of noise trajectories.Finally,experimental validation is performed using public datasets,and the results show that the proposed algorithm effectively improves the trajectory expression effect.(2)Aiming at the problem of large scale of trajectory data and low processing efficiency of single machine,a trajectory frequent pattern mining algorithm based on prefix pruning is proposed and designed based on the distributed computing framework.First of all,take advantage of Spark’s memory based computing to obtain frequent trajectory 1-item set.Secondly,in order to reduce the production scale of the projection datasets and reduce the scanning times,the projection datasets are constructed by prefix pruning on the basis of the frequent trajectory 1-item set,which are then connected to the prefix item to form a frequent trajectory sequence to further mine the frequent trajectory paths.Finally,the algorithm is compared with other algorithms in terms of running time,performance and scalability,and the experimental results on the public datasets show that the proposed algorithm in this thesis has good performance and improves the efficiency of trajectory data mining.