Research On Abnormal Clusters Query Algorithms In Spatial Arrival-departure Data

With the development of location based service technology,such as phones with GPS,taxis,a large amount of spatio-temporal data is created including trajectory data,media data with geographical tags and check-in data.The query and mining based on these also received widely attentions whose researches contribute to the location based service,the facility selection,and so on.There is a new type of spatio-temporal data which records the position where users arrive at or depart from at a certain time,called arrival-departure data.It can be the check-in data from the social networking sites,the stay points in trajectories,the arrival or departure data of passengers.The clusters of arrival departure data can reflect the aggregation behavior of users in a particular area and at a certain time.Based on the arrival-departure data,this paper proposed abnormal clusters query problem.We partitioned the arrival data periodically,and clustered the data in every period by using spatio-temporal cluster algorithms.After comparing the clusters' degree of abnormal from different period,we find the first k clusters with the most abnormal degree.At the same time,this paper studied the corresponding relationship between arrival clusters and departure clusters.Given a arrival cluster,we find the most similar departure one in this period.Finding abnormal clusters could be useful in the management of urban safety,the service based on the location and transportation scheduling etc.The challenges of this research are the effective clustering of arrival-departure data,the measurement of clusters' abnormal degree and the efficient abnormal discovery algorithms.According to the characteristics of arrival-departure data,this paper proposed the region-sensitive clustering algorithm by considered time and cluster's size constraints based on traditional DBSAN.This algorithm can get the results that fit with the region size.In the computation of the abnormal degree of clusters,we proposed an abnormal measurement of clusters based on bipartite graph matching;In addition,this paper designed efficient abnormal clusters discovery algorithms including basic two stages algorithm,optimized two stages algorithm and dynamic construction and matching algorithm.The dynamic construction and matching algorithm combines the building and matching processing,which creates edges of graphes on demand.Thus,the efficiency of the algorithm is improveds.In addition,we present an effective algorithm for matching the arrival and departure clusters.This paper extracts arrival-departure data sets from the real taxi data,and uses the datasets to test and verify the effectiveness of algorithms.Experimental results show the following conclusions.First,we found the matching between results and specific events,which validates the meaning of the proposed query.Second,according to the visualization analysis of the two cluster algorithms,IDBSCAN T can be more suitable for our study than DBSCAN.Next,through the abnormal clustering and the corresponding of arrival and departure clusters results,we have proved the rationality of proposed measurement and the correctness of abnormal clusters query algorithms.Finally,by comparing the running time of the three kinds of algorithms with different parameter settings,we found the dynamic construction and matching algorithm is the most effective one because of the dynamic construction and matching method.