Research On Clustering Spatio-Temporal Trajectories Of Moving Point Objects Compressed By Interesting Places

Recently, with the increasing use of wireless communication devices and the ability to track people and objects cheaply and easily, the amount of spatio-temporal data is growing substantially. The need for patio-temporal data mining and analysis techniques is growing.In this context, research on clustering patio-temporal trajectories of moving point objects compressed by interesting places in this dissertation has deployed. The review of the patio-temporal trajectory representation, similarity measurement and clustering analysis has been carried out. The research works is shown as follows:First, a new method to represent patio-temporal trajectory is proposed. By sorting the speed of moving objects and selecting the appropriate parameters, a DESCAN (a Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise) variation algorithm is applied to extract some interesting semantic places according to underlying application domain. So the trajectory data is replaced by interesting places sequence, in which the core information is kept and the memory of data storage is reduced dramatically.Second, some similarity measurement formulae are proposed. Fully taking into account, movement of objects is often constrained by an underlying space network, thus a new spatial similarity measurement formula is analyzed which is based on the minimum distance on road network space. During the progress of designing temporal distance of trajectories, a new method to calculate hierarchy variables’distance is proposed. An integrated patio-temporal similarity measurement method is also given.Third, in the stage of clustering patio-temporal trajectory, there is a difficult problem, which is how to effectively identify different moving object sets with different walking speed. We propose an algorithm — AP clustering (Affinity Propagation Clustering) based on Reversible Jump Markov Chain Monte Carlo (RJMCMC). AP clustering algorithm does not need to define the clustering centers before it runs, it will take all the data points as potential cluster centers. According to the similarity clustering energy function for each data point, AP algorithm deploys an iterative cycle of continuous evidence collection and transfer (also known as message passing) to produce the high quality class. AP clustering method can be quickly and accurately get the clustering results in homogeneous density data, but it cannot deal with the data from different types of density (such as pedestrians, bicycles and cars with a pre-existing condition). To solve this problem, we propose to use a Reversible Jump Markov Chain Monte Carlo (RJMCMC) method to classify moving objects into various types of density data subsets, and then run AP clustering algorithm, the design meets the reality of different density nested in a data set.Fourth, the proposed models and algorithms are applied to a case study of datasets generated by Generator (which is a new generator for spatiotemporal data). The experiments’results show the effectivity and efficiency of our clustering methods in processing trajectories with different lengths and irregular sampling time. And the results are more interpretable and more understandable.Finally, some recommendations and further researches are proposed, which include how to obtain effective clusters from trajectories with different spatio-temporal scales and how to extend traditional concepts of spatio-temporal proximity based on "flow" and how to combine the clustering results with spatio-temporal visualization technology, and so on.