Research On Moving Objects Gathering Pattern Mining Method Based On Trajectory Data

In recent years, with the popularity of GPS (Global Positioning System), we have obtained huge trajectory data from public transportation trajectory (taxicab and bus trajectory) and the check-in data from the social network. The trajectory data can be represented as a curve on a two-dimensional map in chronological order during the movements of objects. Researchers will analyze the position, destination and moving status by using the techniques of trajectory data mining. However, it is difficult to get the group pattern by just analyzing the single moving object. Hence, researchers have proposed the concept of gathering pattern mining.The gathering pattern is a behavior pattern of a set of spatio-temporal moving objects, moving together within a certain period of time.Researchers are trying to analyze the gathering pattern or the movement pattern of moving objects by using the pattern mining techniques. It is commonly used to predict the anomalies in traffic system. However,effectively and efficiently discovering the gathering pattern turns to be a remaining challenging issue since the large number of moving objects will generate high volume of trajectory data. This paper investigated the effectiveness and efficiency of gathering pattern mining method and makes the following contributions:1. We propose a moving object gathering pattern mining method based on trajectory data clustering. In this method, firstly we use an improved density based clustering algorithm (RT-DBScan) to collect the moving object clusters. Then, we maintain a spatio-temporal graph (STG) to store the moving clusters. Finally, an effective gathering mining algorithm is developed to search the gathering sets which meet the spatio-temporal constraints from the STG. This method introduces the concept of STG which is composed by the moving clusters. Each node of the graph not only contains the knowledge of moving objects, but also contains the emerging time and location of the clusters. Each edge of the graph represents the spatio-tempoal relation between the clusters. The STG shows the spatio-temporal evolving process between moving clusters. We have proposed a gathering pattern mining algorithm (GR) based on STG.In the algorithm, the maximum clique search process is used to find gathering pattern sets which meet the spatio-temporal constraints. The experimental results show the effectiveness of the proposed method is outperformed other methods on both real and large trajectory data.2. We have proposed two effective gathering pattern method. The first is an improved gathering pattern mining algorithm (GR+) based on the characteristic of gathering. It uses the efficient algorithm (Bron-Kerbosch)to search the maximum cliques. The pruning rules are proposed to reduce the search space. The second is a ?-nearest neighbor pruning algorithm is used to reduce the search space based on the STG features. The algorithm first reduces the search space by cutting the border nodes and noise node.Then it will discover the gathering pattern by using necessary and sufficient conditions of the maximum clique. The experimental results show the efficiency of the proposed algorithms are outperformed other algorithms on both real and large trajectory data.3. We propose a method to discover the taxicabs' gathering pattern by analyzing the passengers' status derived from the trajectory data in urban area. In order to have a deep undersanding of taxicabs' supply and demand, this paper first introduces the concept of TSR (Taxicab Service Rate) based on the knowledge of passengers' status. In this method, we use the KS measures (Kurtosis-Skewness) to test the normality and the Parzen window method to get the PDF (Probability Density Function) of TSR. Then, it will calculate the mean value of the TSR of a certain time period. At last, we use a neural network based method, which name isNeural Network Gathering Discovering (NNGD), to detect the gathering pattern. The neural network is trained by the knowledge of historical taxicabs' gathering pattern data. This method can make a balance between effectiveness and efficiency. On one hand, it will effectively discover gathering pattern from the taxicabs' supply and demand pattern. On the other hand, it can avoid the complex process of trajectory clustering,which will make the method more efficient.