Trajectory Clustering Analysis Based On NMAST Density Function And Its Application

Clustering analysis is an important branch of data mining,and widely used in the fields of computer science,engineering,economics,geography,life sciences,medicine and social sciences etc.Trajectory clustering is a typical application of clustering technology in trajectory data analysis.By clustering massive trajectory data set,important information and knowledge can be found,thus laying a solid foundation for further analysis of trajectories(behavior /pattern analysis,event prediction,decision support,etc.).Due to the characteristics of spatiotemporal sequence,no frequency sampling and poor trajectory quality,the effect of traditional clustering method on the data sets is not satisfactory,and there are still some shortcomings,such as separating time and space before clustering,insufficient consideration of movement characteristics of complex or special trajectories,large clusters easily divided into multiple small clusters by noise data,repeated clustering the same geographical location bringing unnecessary time and space costs.In the thesis,density clustering method of trajectory data are deeply studied by using the theories of neighborhood move ability,data domain and incremental clustering.The main research results are as follows:(1)A trajectory clustering algorithm based on NMAST(Neighborhood Move Ability and Stay Time)density function is presented.In the algorithm,the density function NMAST is defined according to the moving characteristic of trajectory segments,the stay time and the distribution features of data points.Then,the noise tolerance value is introduced to reduce the influence of noise data.Finally,experimental results show that the algorithm can reflect the temporal and spatial distribution density of data points more realistically.When dealing with complex trajectories,the clustering accuracy of the algorithm does not fluctuate significantly with the increase of trajectory complexity,and is more stable and higher than other algorithms.(2)An incremental clustering algorithm based on NMAST density function is presented.Firstly,a initial center set CP and stays(clusters)fororiginal trajectory data set are generated by using the above algorithm.Secondly,the CP is used in a newly added trajectory data set to find the existing stays,deleting the trajectory data objects which have been divided into clusters,and generating a subset of the above new trajectory data set.Thirdly,the subset is clustered by above algorithm and the center point set CP is updated.In the end,experimental results validate that the proposed incremental clustering algorithm can effectively utilize the space-time correlations between trajectories to solve the problem of spatial and temporal waste,and to enhance the time efficiency of trajectory clustering.(3)A trajectory clustering prototype system based on NMAST density function is designed and implemented.The prototype system mainly includes functional modules of data preprocessing,trajectory visualization,density curve generation,stop point extraction,result preservation etc.Running results of the system show that an effective way for trajectory visualization and trajectory clustering analysis is provided.