EN中文

地理科学进展 >

2011 , Vol. 30 >Issue 5: 522 - 534

DOI: https://doi.org/10.11820/dlkxjz.2011.05.002

研究综述

时空轨迹聚类方法研究进展

展开
  • 1. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室, 北京 100101;
    2. 中国科学院烟台海岸带研究所, 烟台 264003;
    3. 中国科学院研究生院, 北京 100049;
    4. 香港中文大学地理与资源管理学系, 香港
龚玺(1986-),男,硕士研究生,主要研究方向为空间数据挖掘。E-mail: gongx@lreis.ac.cn

收稿日期: 2010-10-01

  修回日期: 2011-02-01

  网络出版日期: 2011-05-25

基金资助

中国科学院知识创新工程重要方向项目(KZCX2-YW-QN303)；中国科学院地理资源所自主部署创新项目(200905004)；863 项目(2009AA12Z227)。

收起

Review of the Research Progresses in Trajectory Clustering Methods

Expand
  • 1. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China;
    2. Yantai Institute of Coastal Zone Research, CAS, Yantai 264003, Shandong,China;
    3. Graduate University of Chinese Academy of Sciences, Beijing 100049, China;
    4. Department of Geography and Resource Management, The Chinese University of Hong Kong, Hong Kong, China

Received date: 2010-10-01

  Revised date: 2011-02-01

  Online published: 2011-05-25

Fold

摘要

时空轨迹(Trajectory)是移动对象的位置和时间的记录序列。作为一种重要的时空对象数据类型和信息源,时空轨迹的应用范围涵盖了人类行为、交通物流、应急疏散管理、动物习性和市场营销等诸多方面。通过对各种时空轨迹数据进行聚类分析,可以提取时空轨迹数据中的相似性与异常特征,并有助于发现其中有意义的模式。本文根据时空轨迹数据的特点,系统综述了时空轨迹聚类方法的研究进展。首先,从理论、可行性和应用的角度分析了时空轨迹数据及其聚类方法研究的重要性,并论述了时空轨迹的定义、模型与表达；然后,按照相似性度量所涉及的不同时间区间将现有的时空轨迹聚类方法划分为6 类,并对每一类方法的原理及特点进行了评述；最后,讨论了现有方法面临的主要问题和挑战,并对时空轨迹聚类研究的发展进行了展望。

关键词： 聚类; 时空轨迹; 时空数据挖掘; 相似性度量; 研究进展

本文引用格式

龚玺, 裴韬, 孙嘉, 罗明 . 时空轨迹聚类方法研究进展[J]. 地理科学进展, 2011 , 30(5) : 522 -534 . DOI: 10.11820/dlkxjz.2011.05.002

Abstract

A trajectory is a sequence of the location and timestamp of a moving object. It is not only an important type of spatio-temporal data, but also a critical source of information. Extracting patterns from different trajectory data can help people understand the drives and outcomes of individual and collective spatial dynamics, such as human behavior patterns, transport and logistics, emergency evacuation management, animal behavior, and marketing. Recently, a larger number of trajectory data are available for analyzing the temporal and spatial pattern, as the result of the improvements of tracking facilities and sensor networks. Therefore, clustering analysis needs to be used to find the implicit patterns in it. Based on the characteristics and the similarity measurements of trajectory data, this paper reviewed the research progresses in trajectory clustering methods. Firstly, the significance of research on trajectory data and its clustering methods was presented. Then the definition, models as well as several visualization methods of trajectories were summarized. After that, the authors classified the existing trajectory clustering methods into 6 main categories according to the similarity measurement of them, and analyzed each of the trajectory clustering methods, along with their respective pros and cons by category. Finally, some research challenges and future directions were discussed.

Key words： clustering; research progress; similarity measurement; spatio-temporal data mining; trajectory

参考文献

[1] 王家耀, 魏海平, 成毅, 等. 时空GIS的研究与进展. 海洋测绘, 2004, 24(5): 1-4.

[2] Han J, Kamber M, Tung A K H. Spatial clustering methodsin data mining//Miller H J, Han J. Geographic DataMining and Knowledge Discovery. London: Taylor &Francis, 2001: 188 - 217.

[3] Han J, Kamber M. Data Mining: Concepts and Techniques.2th ed. San Francisco: Morgan Kaufmann, 2006:383.

[4] Li X, Han J, Kim S, et al. Roam: Rule- and motif-basedanomaly detection in massive moving object data sets//Proceedings of the Seventh SIAM International Conferenceon Data Mining. Philadelphia: SIAM, 2007.

[5] Nanni M. Clustering methods for spatio-temporal data. Pisa,Italy: University of Pisa[D], 2002.

[6] Theodoridis Y, Silva J R O, Nascimento MA. On the generationof spatiotemporal datasets. Advances in SpatialDatabases, 1999, 1651/1999: 147-164.

[7] Giannotti F, Mazzoni A, Puntoni S, et al. Synthetic generationof cellular network positioning data//Proceedings ofthe 13th annual ACM International Workshop on GeographicInformation Systems. New York, NY, USA:ACM, 2005: 12-20.

[8] Tzouramanis T, Vassilakopoulos M, Manolopoulos Y. Onthe generation of time-evolving regional data. Geoinformatica,2002, 6(3): 207-231.

[9] Saglio J M, Moreira J. Oporto: A realistic scenario generatorfor moving objects. Geoinformatica, 2001, 5(1):71-93.

[10] Saltenis S, Jensen C S, Leutenegger S T, et al. Indexingthe positions of continuously moving objects. Sigmod Record,2000, 29(2): 331-342.

[11] Tao Y, Papadias D. Time-parameterized queries in spatio-temporal databases//Proceedings of the 2002 ACMSIGMOD International Conference on Management ofdata. New York, NY, USA: ACM, 2002: 334-345.

[12] Li Y, Han J, Yang J. Clustering moving objects//Proceedingsof the tenth ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining. NewYork, NY, USA: ACM, 2004: 617-622.

[13] Hägerstrand T. What about people in regional science?Papers in Regional Science, 1970, 24(1): 6-21.

[14] Lenntorp B. Paths in space-time environments: Atime-geographic study of movement possibilities of individuals.Environment and Planning A, 1977, 9: 961-972.

[15] Miller H J. Modelling accessibility using space-timeprism concepts within geographical information systems.International Journal of Geographical Information Systems,1991, 5(3): 287-301.

[16] Kwan M, Hong X. Network-based constraints-orientedchoice set formation using GIS. Geographical Systems,1998, 5: 139-162.

[17] Yu H, Shaw S L. Exploring potential human activities inphysical and virtual spaces: A spatio-temporal GIS approach.International Journal of Geographical InformationScience, 2008, 22(4): 409-430.

[18] Shaw S L, Yu H B. A GIS-based time-geographic approachof studying individual activities and interactionsin a hybrid physical-virtual space. Journal of TransportGeography, 2009, 17(2): 141-149.

[19] Berezansky M, Greenspan H, Cohen-Or D, et al. Segmentationand tracking of human sperm cells using spa-tio-temporal representation and clustering. Medical Imaging2007: Image Processing, 2007, 6512: 65122M.1-65122M.12.

[20] Erez K, Goldberger J, Sosnik R, et al. Analyzing movementtrajectories using a markov bi-clustering method.Journal of Computational Neuroscience, 2009, 27(3):543-552.

[21] Gabarro-Arpa J, Revilla R. Clustering of a molecular dynamicstrajectory with a hamming distance. Computersand Chemistry, 2000, 24(6): 693-698.

[22] Cape J N, Methven J, Hudson L E. The use of trajectorycluster analysis to interpret trace gas measurements atMace Head, Ireland. Atmospheric Environment, 2000, 34(22): 3651-3663.

[23] Camargo S J, Robertson A W, Gaffney S J, et al. ClusterAanalysis of typhoon tracks. Part I: General properties.Journal of Climate, 2007, 20(14): 3635-3653.

[24] Camargo S J, Robertson A W, Gaffney S J, et al. Clusteranalysis of typhoon tracks. Part II: Large-scale circulationand Enso. Journal of Climate, 2007, 20(14):3654-3676.

[25] Kang C H, Hwang J R, Li K J. Trajectory analysis for soccerplayers//Proceedings of the Sixth IEEE InternationalConference on Data Mining Workshops. Washington,DC, USA: IEEE Computer Society, 2006: 377-381.

[26] Laube P, Imfeld S, Weibel R. Discovering relative motionpatterns in groups of moving point objects. InternationalJournal of Geographical Information Science, 2005, 19(6): 639-668.

[27] 蔡元龙. 模式识别. 西安: 西北电讯工程学院出版社,1986: 18.

[28] Tan P N, Steinbach M, Kumar V. Introduction to DataMining. Boston: Pearson Addison-Wesley, 2006: 60-65.

[29] Agrawal R, Faloutsos C, Swami A. Efficient similaritysearch in sequence databases. Foundations of Data Organizationand Algorithms, 1993, 730: 69-84.

[30] Chen L, Özsu M, Oria V. Robust and fast similaritysearch for moving object trajectories//Proceedings of the2005 ACM SIGMOD International Conference on Managementof Data. New York, NY, USA: ACM, 2005:491-502.

[31] Lee S, Chun S, Kim D, et al. Similarity search for multidimensionaldata sequences//Proceedings of the 16th InternationalConference on Data Engineering. Washington D.C. USA: IEEE Computer Society, 2000: 599-608.

[32] Elnekave S, Last M, Maitnon O. Incremental clusteringof mobile objects//Proceedings of the 2007 IEEE 23rd InternationalConference on Data Engineering Workshop.Washington, DC, USA: IEEE Computer Society, 2007:585-592.

[33] Sankoff D, Kruskal J. Time Warps, String Edits, and Macromolecules:The Theory and Practice of Sequence Comparison.MA, USA: Addison-Wesley, 1983.

[34] Agrawal R, Lin K I, Sawhney H S, et al. Fast similaritySsearch in the presence of noise, scaling, and translationin time-series databases//Proceedings of the 21th InternationalConference on Very Large Data Bases. San Francisco,CA, USA: Morgan Kaufmann Publishers Inc., 1995:490-501.

[35] Crochemore M, Rytter W. Text Algorithms. New York,NY, USA: Oxford University Press, 1994.

[36] Lee J G, Han J, Whang K Y. Trajectory clustering: A partition-and-group framework//Proceedings of the 2007ACM SIGMOD International Conference on Managementof Data. New York, NY, USA: ACM, 2007:593-604.

[37] Nanni M, Pedreschi D. Time-focused clustering of trajectoriesof moving objects. Journal of Intelligent InformationSystems, 2006, 27(3): 267-289.

[38] Kalnis P, Mamoulis N, Bakiras S. On discovering movingclusters in spatio-temporal data//Medeiros C B,EgenhoferM, Bertino E. Proceedings of the 9th InternationalSymposium on Advances in Spatial and Temporal Databases.Berlin: Springer-Verlag, 2005: 364-381.

[39] Gao Y, Zheng B, Chen G, et al. Algorithms for constrainedK-nearest neighbor queries over moving objecttrajectories. Geoinformatica, 2010, 14(2): 241-276.

[40] Alt H, Godau M. Computing the fréchet distance betweentwo polygonal curves. International Journal of ComputationalGeometry and Applications, 1995, 5(1): 75-91.

[41] Lin B, Su J. One way distance: For shape based similaritysearch of moving object trajectories. Geoinformatica,2008, 12(2): 117-142.

[42] Perng C S, Wang H, Zhang S R, et al. Landmarks: A newmodel for similarity-based pattern querying in time seriesdatabases//Proceedings of the 16th International Conferenceon Data Engineering, 2000: 33-42.

[43] Faloutsos C, Jagadish H, Mendelzon A, et al. A signaturetechnique for similarity-based queries//Proceedings ofthe Compression and Complexity of Sequences 1997.Washington, DC, USA: IEEE Computer Society, 1997:2-20.

[44] Pelekis N, Kopanakis l, Ntoutsi I, et al. Mining trajectorydatabases via a suite of distance operators//Proceedingsof the 2007 IEEE 23rd International Conference on DataEngineering Workshop. Washington, DC, USA: IEEEComputer Society, 2007: 575-584.

[45] Faloutsos C, Ranganathan M, Manolopoulos Y. Fast sub-sequence matching in time-series databases. ACM SIGMODRecord, 1994, 23(2): 419-429.

[46] Chan K. Efficient time series matching by wavelets//Proceedingsof the 15th International Conference on DataEngineering. Washington, DC, USA: IEEE Computer Society,1999: 126-133.

[47] Chakrabarti K, Keogh E, Mehrotra S, et al. Locally adaptivedimensionality reduction for indexing large time seriesdatabases. ACM Transactions on Database Systems(TODS), 2002, 27(2): 188-228.

[48] Yanagisawa Y, Akahani J, Satoh T. Shape-based similarityquery for trajectory of mobile objects//Proceedings ofthe 4th International Conference on Mobile Data Management.London, UK: Springer-Verlag, 2003: 63-77.

[49] Keogh E, Palpanas T, Zordan V, et al. Indexing large human-motion databases//Proceedings of the Thirtieth InternationalConference on Very Large Data Bases. VLDBEndowment, 2004: 780-791.

[50] Berndt D, Clifford J. Using dynamic time warping to findpatterns in time series//Proceedings of KDD-94 Work-Shop, 1994: 359-370.

[51] Sakurai Y, Yoshikawa M, Faloutsos C. FTW: Fast similaritysearch under the time warping distance//Proceedingsof the Twenty-fourth ACM SIGMOD-SIGACT-SIGARTSymposium on Principles of Database Systems. NewYork, NY, USA: ACM, 2005: 326-337.

[52] Vlachos M, Hadjieleftheriou M, Gunopulos D, et al. Indexingmulti-dimensional time-series with support formultiple distance measures//Proceedings of the NinthACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining. New York, NY, USA: ACM,2003: 216-225.

[53] Little J, Gu Z. Video retrieval by spatial and temporalstructure of trajectories//Proceedings of SPIE, the InternationalSociety for Optical Engineering SPIE, 2001:545-552.

[54] Vlachos M, Gunopulos D, Das G. Rotation invariant distancemeasures for trajectories//Proceedings of the TenthACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining. New York, NY, USA: ACM,2004: 707-712.

[55] Vlachos M, Kollios G, Gunopulos D. Discovering similarmultidimensional trajectories//Agrawal R, Dittrich K,Ngu A H H. Proceedings of the 18th International Conferenceon Data Engineering. Washington, DC, USA: IEEEComputer Society, 2002: 673-684.

[56] Bozkaya T, Yazdani N, Özsoyoglu M. Matching and indexingsequences of different lengths//Proceedings of theSixth International Conference on Information andKnowledge Management. New York, NY, USA: ACM,1997: 128-135.

[57] Chen L, Ng R. On the marriage of lp-norms and edit distance//Proceedings of the Thirtieth International Conferenceon Very Large Data Bases. VLDB Endowment,2004: 792-803.

[58] Liu J P, Zhang Y L, Liu G. Partition and density-basedclustering for moving objects Trajectories//Proceedingsof the Third International Conference on Computer Science& Education. Xiamen: Xiamen University Press,2008: 182-187.

[59] Lee J G, Han J, Li X, et al. Traclass: Trajectory classificationusing hierarchical region-based and trajectory-Basedclustering//Proceedings of International Conference onVery Large Data Base(VLDB'08). VLDB Endowment,2008: 1081-1094.

[60] Ankerst M, Breunig M M, Kriegel H P, et al. Optics: Orderingpoints to identify the clustering structure//Proceedingsof the 1999 ACM SIGMOD International Conferenceon Management of Data. New York, NY, USA:ACM, 1999: 49-60.

[61] Zhang T, Ramakrishnan R, Livny M. Birch: An efficientdata clustering method for very large databases. ACMSIGMOD Record, 1996, 25(2): 103-114.

[62] Nanni M, Kuijpers B, Körner C, et al. Spatiotemporal datamining//Giannotti F,Pedreschi D. Mobility, Data Mining,and Privacy: Geographic Knoweledge Discovery.Berlin: Springer-Verlag, 2008: 267-296.

[63] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matchingvehicle tracking data//Proceedings of the 31st InternationalConference on Very Large Data Bases. VLDB Endowment,2005: 853-864.

[64] Schreck T, Bernard J, Tekusova T, et al. Visual clusteranalysis of trajectory data with interactive kohonen maps.Information Visualization, 2009, 8: 14-29.

[65] Yu W, Gertz M. Constraint-based learning of distancefunctions for object trajectories//Proceedings of the 21stInternational Conference on Scientific and Statistical DatabaseManagement. Berlin, Heidelberg: Springer-Verlag,2009: 627-645.

[66] Gaffney S, Smyth P. Trajectory clustering with mixturesof regression models//Proceedings of the Fifth ACM SIGKDDInternational Conference on Knowledge Discoveryand Data Mining. New York, NY, USA: ACM, 1999:63-72.

[67] Chudova D, Gaffney S, Mjolsness E, et al. Translation-invariantmixture models for curve clustering//Proceedingsof the Ninth ACM SIGKDD International Conference onKnowledge Discovery and Data Mining. New York, NY,USA: ACM, 2003: 79-88.

[68] Alon J, Sclaroff S, Kollios G, et al. Discovering clustersin motion time-series data//Proceedings of IEEE ComputerSociety Conference on Computer Vision and PatternRecognition (CVPR'03). Washington, DC, USA: IEEEComputer Society, 2003: 375-381.

[69] Ketterlin A. Clustering sequences of complex objects//Proceeding of the 3rd Interernational Conference onKnowledge Discovery and Data Mining (KDD-97).AAAI Press, 1997: 215-218.

[70] Agrawal R, Psaila G, Wimmers E L, et al. Queryingshapes of histories//Proceedings of the 21th InternationalConference on Very Large Data Bases. San Francisco,CA, USA: Morgan Kaufmann Publishers Inc., 1995:502-514.

[71] Kim S W, Yoon J, Park S, et al. Shape-based retrieval ofsimilar subsequences in time-series databases//Proceedingsof the 2002 ACM Symposium on Applied Computing.New York, NY, USA: ACM, 2002: 438-445.
Options
文章导航

/

〈 〉