Incremental clustering for trajectories

作者: Zhenhui Li , Jae-Gil Lee , Xiaolei Li , Jiawei Han

DOI: 10.1007/978-3-642-12098-5_3

关键词: Clustering high-dimensional dataData stream clusteringCorrelation clusteringComputer scienceCURE data clustering algorithmFuzzy clusteringConstrained clusteringCluster analysisData miningCanopy clustering algorithm

摘要: Trajectory clustering has played a crucial role in data analysis since it reveals underlying trends of moving objects. Due to their sequential nature, trajectory are often received incrementally, e.g., continuous new points reported by GPS system. However, existing algorithms developed for static datasets, they not suitable incremental with the following two requirements. First, should be processed efficiently can frequently requested. Second, huge amounts must accommodated, as will accumulate constantly. An framework trajectories is proposed this paper. It contains parts: online micro-cluster maintenance and offline macro-cluster creation. For part, when bunch arrives, each simplified into set directed line segments order find clusters subparts. Micro-clusters used store compact summaries similar segments, which take much smaller space than raw trajectories. When added, micro-clusters updated incrementally reflect changes. user requests see current result, macro-clustering performed on rather all over whole time span. Since number that original trajectories, macro-clusters generated show result Experimental results both synthetic real sets our achieves high efficiency well quality.

参考文章(16)
Hans-Peter Kriegel, Martin Ester, Jörg Sander, Michael Wimmer, Xiaowei Xu, Incremental Clustering for Mining in a Data Warehousing Environment very large data bases. pp. 323- 333 ,(1998)
Hans-Peter Kriegel, Martin Ester, Jörg Sander, Xiaowei Xu, A density-based algorithm for discovering clusters in large spatial Databases with Noise knowledge discovery and data mining. pp. 226- 231 ,(1996)
Scott J. Gaffney, Andrew W. Robertson, Padhraic Smyth, Suzana J. Camargo, Michael Ghil, Probabilistic clustering of extratropical cyclones using regression mixture models Climate Dynamics. ,vol. 29, pp. 423- 440 ,(2007) , 10.1007/S00382-007-0235-Z
Jae-Gil Lee, Jiawei Han, Kyu-Young Whang, Trajectory clustering Proceedings of the 2007 ACM SIGMOD international conference on Management of data - SIGMOD '07. pp. 593- 604 ,(2007) , 10.1145/1247480.1247546
Igor V. Cadez, Scott Gaffney, Padhraic Smyth, A general probabilistic framework for clustering individuals and objects knowledge discovery and data mining. pp. 140- 149 ,(2000) , 10.1145/347090.347119
Jae-Gil Lee, Jiawei Han, Xiaolei Li, Trajectory Outlier Detection: A Partition-and-Detect Framework international conference on data engineering. pp. 140- 149 ,(2008) , 10.1109/ICDE.2008.4497422
Scott Gaffney, Padhraic Smyth, Trajectory clustering with mixtures of regression models knowledge discovery and data mining. pp. 63- 72 ,(1999) , 10.1145/312129.312198
Tian Zhang, Raghu Ramakrishnan, Miron Livny, BIRCH: an efficient data clustering method for very large databases international conference on management of data. ,vol. 25, pp. 103- 114 ,(1996) , 10.1145/233269.233324
Dimitris Sacharidis, Kostas Patroumpas, Manolis Terrovitis, Verena Kantere, Michalis Potamias, Kyriakos Mouratidis, Timos Sellis, On-line discovery of hot motion paths extending database technology. pp. 392- 403 ,(2008) , 10.1145/1353343.1353392
Jae-Gil Lee, Jiawei Han, Xiaolei Li, Hector Gonzalez, TraClass: trajectory classification using hierarchical region-based and trajectory-based clustering very large data bases. ,vol. 1, pp. 1081- 1094 ,(2008) , 10.14778/1453856.1453972