Mining Spatial-Temporal Patterns In Trajectory Data Of Moving Objects

Trajectory is a common type of spatial-temporal data,which describes the moving information of moving objects from the space and time dimensions.Most of moving objects are related to human behaviors,thus their trajectories contain the laws of huma n behaviors in time and space.By extracting the spatial-temporal patterns of moving objects from trajectory data,it is possible to recognize the identity,discover movement patterns,monitor movement states,detect anomalies,identify intentions,and predict movement behaviors for important objects in specific regions and periods so as to support analysts' analysis,assessment,management and decision-making on these objects.The applications of trajectory spatial-temporal pattern mining include huma n behavior analysis,urban computing,transportation and logistics,emergency and evacuation management,animal habits analysis,marketing,natural phenomena analysis and many other fields.In addition,in the field of national security,especially for the military intelligence department,the spatial-temporal pattern mining technologies for trajectories is a powerful tool for handling data-driven intelligence discovery.In an era of big data,mining trajectory data faces new challenges: large data volume,properties of dynamic and real-time,high data dimensions,multiple data sources,changing in data granularities,and high temporal and spatial correlation.These characteristics of trajectory data bring challenges to traditional data analysis and mining techniques.It is urgent to develop new mining technologies to discover interesting knowledge from trajectory databases.This paper focuses on the issue of mining spatial-temporal patterns from large trajectory data of moving object,takes full account of the characteristics of trajectory data,and conducts a series of works:Firstly,based on the fractal characteristics of the trajectory,an efficient and effective method for extracting the trajectory shape pattern and representating the trajectory is proposed.The time complexity of the algorithm increases linearly with the number of points of the trajectory.Different from traditional methods for extracting trajectory shape through calculation of angles,this method converts the trajectory topological feature into a multi-dimensional shape vector from the perspective of fractal geometry,so as to facilitate the application of machine learning techniques,e.g.,shape-based trajectory clustering and classification.In addition,for the first time,the self-similar characteristics of vessel trajectory are theoretically analyzed.Secondly,for the problem of rapid clustering and anomaly detection for large-scale trajectories,a two-stage spatial clustering algorithm(KMDD)based on density and distance is proposed.It has the ability of rapidly discovering clusters with multiple shape and densities in large-scale spatial datasets.It is the first method to merge subclusters using the concept of density and distance.The quality of clustering result is superior to the widely used spatial clustering algorithms,and the running time is linear to the data size and the data dimension.Thirdly,the conception and problem definition of trajectory spatial-temporal co-occurrence pattern are proposed,and the solution method to the problem is given.This paper proposes to mine the spatial-temporal co-occurrence pattern by solving two-dimensional and multi-dimensional co-clustering models.Based on real vessel trajectories,an AIS data processing framework is proposed and the spatial-temporal co-occurrence patterns are extracted from a large number of vessel trajectory data to reveal the ships' coordinated behaviors in multiple dimensions.Finally,in order to mine typical paths and typical timestamps,speeds and directions from trajectory data,a frequent trajectory pattern mining method based on region sequence and annotation sequence is proposed.The existing frequent trajectory patterns are based on time annotations.However,this paper proposes two new frequent trajectory patterns,namely,frequent trajectory patterns with speed and direction annotations.Becides,a new method for extraction of hotspot regions is proposed,namely,the turning-region extraction method.In addition,the concept of adjacency trajectory pattern and its mining method are proposed,and a new method for mining the annotation sequence pattern is proposed.The feasibility and effectiveness of these methods are verified by experiments.