Visualization and Extraction of Trajectory Stops Based on Kernel-density

doi:10.11947/j.AGCS.2016.20150347

Abstract

Abstract: Trajectory stops imply important semantic information, and the extraction of trajectory stops is the premise to carry out advanced Stop/Move analysis. This paper, based on the idea of kernel density, firstly introduces the concept of stop index, which is derived by cumulating spatio-temporal contribution of neighboring points, and further designs stop index graph to intuitively visualize the evolution of spatio-clustering degree during a trajectory. Importantly, stops index and its graph are related to spatial scale through neighboring radius, which then can be exploited to analyze trajectory stops under multiple scales. In addition, this paper introduces stop sequence rooted from stop index, and proposes an algorithm for the automatic extraction of trajectory stops by progressively merging stop sequences. According to the algorithm, a stop under strong GPS signal exactly corresponds to a stop sequence, while a stop under weak GPS signal could be derived by merging multiple stop sequences. Experiments based on own-acquired and GeoLife trajectories show that the algorithm has achieves the balance between the completeness and accuracy of stop extraction, and could effectively discover and extract complex and diverse trajectory stops. Even facing trajectories with serious drift noises, the algorithm still achieves a high rate of accuracy on stop extraction.

Key words: kernel density, trajectory, stop index, stop, spatio-temporal contribution

CLC Number:

P208

XIANG Longgang, SHAO Xiaotian. Visualization and Extraction of Trajectory Stops Based on Kernel-density[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(9): 1122-1131.

References

[1] SPACCAPIETRA S, PARENT C, DAMIANI M L, et al. A Conceptual View on Trajectories[J]. Data and Knowledge Engineering, 2008, 65(1): 126-146.
[2] YAN Zhixian, CHAKRABORTY D, PARENT C, et al. Semantic Trajectories: Mobility Data Computation and Annotation[J]. ACM Transactions on Intelligent Systems and Technology, 2013, 4(3): 49.
[3] PARENT C, SPACCAPIETRA S, RENSO C, et al. Semantic Trajectories Modeling and Analysis[J]. ACM Computing Surveys, 2013, 45(4): 42.
[4] 向隆刚, 吴涛, 龚健雅. 面向地理空间信息的轨迹模型及时空模式查询[J]. 测绘学报, 2014, 43(9): 982-988. DOI: 10.13485/j.cnki.11-2089.2014.0121. XIANG Longgang, WU Tao, GONG Jianya. A Geo-spatial Information Oriented Trajectory Model and Spatio-temporal Pattern Querying[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(9): 982-988. DOI: 10.13485/j.cnki.11-2089.2014.0121.
[5] 齐凌艳, 陈荣国, 温馨. 基于语义轨迹停留点的位置服务匹配与应用研究[J]. 地球信息科学学报, 2014, 16(5): 720-726. QI Lingyan, CHEN Rongguo, WEN Xin. Research on the LBS Matching Based on Stay Point of the Semantic Trajectory[J]. Journal of Geo-Information Science, 2014, 16(5): 720-726.
[6] VIEIRA M, BAKALOV P, TSOTRAS V J. Querying Trajectories Using Flexible Patterns[C]//Proceedings of the 13th International Conference on Extending Database Technology. New York: ACM, 2010: 406-417.
[7] GIANNOTTI F, NANNI M, PEDRESCHI D, et al. Trajectory Pattern Mining[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 330-339.
[8] ZHENG Yu, ZHANG Lizhu, XIE Xing, et al. Mining Interesting Locations and Travel Sequences from GPS Trajectories[C]//Proceedings of the 18th International Conference on World Wide Web. New York: ACM, 2009: 791-800.
[9] ALVARES L, BOGORNY V, KUIJPERS B, et al. A Model for Enriching Trajectories with Semantic Geographical Information[C]//Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems. New York: ACM, 2007.
[10] ROCHA J M R, TIMES V C, OLIVEIRA G, et al. DB-SMoT: A Direction-based Spatio-temporal Clustering Method[C]//Proceedings of the 5th IEEE International Conference Intelligent Systems. London: IEEE, 2010: 114-119.
[11] STOPHER P, JIANG Q, FITZGERALD C. Processing GPS Data from Travel Surveys[C]//Proceedings of the 2nd International Colloquium on the Behavioral Foundations of Integrated Land-use and Transportation Models: Frameworks, Models and Applications. Toronto: [s.n.], 2005.
[12] TIETBOHL A, BOGORNY V, KUIJPERS B, et al. A Clustering-based Approach for Discovering Interesting Places in Trajectories[C]//Proceedings of the 2008 ACM Symposium on Applied Computing. New York: ACM, 2008: 863-868.
[13] TRAN L H, NGUYEN Q V H, NGOC H, et al. Robust and Hierarchical Stop Discovery in Sparse and Diverse Trajectories[EB/OL]. (2012-06-15)[2015-09-24]. http://cn.bing.com/academic/profile?id=1894965895&v=paper_preview&mkt=zh-cn
[14] ZIMMERMANN M, KIRSTE T, SPILIOPOULOU M. Finding Stops in Error-Prone Trajectories of Moving Objects with Time-based Clustering[M]//TAVANGARIAN D, KIRSTE T, TIMMERMANN D, et al. Intelligent Interactive Assistance and Mobile Multimedia Computing. Berlin: Springer, 2009, 53: 275-286.
[15] 张治华. 基于GPS轨迹的出行信息提取研究[D]. 上海: 华东师范大学, 2010. ZHANG Zhihua. Deriving Trip Information from GPS Trajectories[D]. Shanghai: East China Normal University, 2010.
[16] Microsoft Research. GeoLife GPS Trajectories[EB/OL]. [2015-06-10]. http://research.microsoft.com/en-us/downloads/b16d359d-d164-469e-9fd4-daa38f2b2e13.
[17] 向隆刚, 龚健雅, 吴涛, 等. 一种面向Stop/Move抽象的轨迹时空关系[J]. 武汉大学学报(信息科学版), 2014, 39(8): 956-962. XIANG Longgang, GONG Jianya, WU Tao, et al. Spatio-temporal Trajectory Relationships Based on Stop/Move Abstraction[J]. Geomatics and Information Science of Wuhan University, 2014, 39(8): 956-962.
[18] PARZEN E. On Estimation of a Probability Density Function and Mode[J]. The Annals of Mathematical Statistics, 1962, 33(8): 1065-1076.
[19] 王远飞, 何洪林. 空间数据分析方法[M]. 北京: 科学出版社, 2007: 57-93. WANG Yuanfei, HE Honglin. Spatial Data Analysis Methods[M]. Beijing: Science Press, 2007: 57-93.
[20] 禹文豪, 艾廷华. 核密度估计法支持下的网络空间POI点可视化与分析[J]. 测绘学报, 2015, 44(1): 82-90. DOI: 10.11947/j.AGCS.2015.20130538. YU Wenhao, AI Tinghua. The Visualization and Analysis of POI Features under Network Space Supported by Kernel Density Estimation[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(1): 82-90. DOI: 10.11947/j.AGCS.2015.20130538.
[21] SCHABENBERGER O, GOTWAY C A. Statistical Methods for Spatial Data Analysis[M]. Boca Raton: Chapman & Hall /CRC, 2005.
[22] MILLER H J. Tobler's First Law and Spatial Analysis[J]. Annals of the Association of American Geographers, 2004, 94(2): 284-289.
[23] 李小文, 曹春香, 常超一. 地理学第一定律与时空邻近度的提出[J]. 自然杂志, 2007, 29(2): 69-71. LI Xiaowen, CAO Chunxiang, CHANG Chaoyi. The First Law of Geography and Spatial-temporal Proximity[J]. Chinese Journal of Nature, 2007, 29(2): 69-71.
[24] CHANDRA S, BHARTI A K. Speed Distribution Curves for Pedestrians during Walking and Crossing[J]. Procedia-social and Behavioral Sciences, 2013(104): 660-667.