时空轨迹分类研究进展

doi:10.3724/SP.J.1047.2017.00289

摘要/Abstract

摘要：

时空轨迹分类旨在为一条轨迹预测类别。时空轨迹分类在城市规划、个性化用户推荐等方面具有重要应用价值,其过程主要包括轨迹数据预处理、特征提取、建立分类器3个阶段。本文综述了近年来时空轨迹分类的研究进展,首先对时空轨迹分类的过程进行概述;然后将时空轨迹分类算法按特征提取的方式分为基于运动特征的轨迹分类算法、基于分类规则的轨迹分类算法和基于图像信号分析的轨迹分类算法3类,分别论述了这些算法的基本思想和优缺点;之后对现有的轨迹分类算法从数据来源、分类器、特征提取方式等方面进行对比分析;最后讨论现有的时空轨迹分类算法面临的挑战。

关键词: 时空轨迹分类, 时空轨迹挖掘, 时空数据挖掘

Abstract:

Spatial-temporal trajectory classification aims at predicting the category of a spatial-temporal trajectory. The classification of spatial-temporal trajectories plays an important role in urban planning, personalized user recommendation and so on. The process of trajectory classification includes three stages: trajectory preprocessing, feature extraction and classification. This paper reviews the recent research progress on trajectory classification. Firstly, we introduce the process of trajectory classification. Then, the trajectory classification algorithms are classified into three categories according to the method of feature extraction, including the trajectory classification algorithm based on motion feature, the trajectory classification algorithm based on classification rule and the trajectory classification algorithm based on image signal analysis. We also discuss the basic ideas, advantages and disadvantages of these algorithms. Thirdly, we compare the existing classification algorithms according to the sensors, feature extraction and classifiers used in these algorithms. Finally, we introduce the challenges of the existing trajectory classification algorithms.

Key words: spatial-temporal trajectory classification, spatial-temporal trajectory mining, spatial-temporal mining

赵竹珺, 吉根林. 时空轨迹分类研究进展[J]. 地球信息科学学报, 2017, 19(3): 289-297.DOI:10.3724/SP.J.1047.2017.00289

ZHAO Zhujun,JI Genlin. Research Progress of Spatial-temporal Trajectory Classification[J]. Journal of Geo-information Science, 2017, 19(3): 289-297.DOI:10.3724/SP.J.1047.2017.00289

图/表 10

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

各轨迹分类算法比较"

算法类别	轨迹采集方式	分类器	轨迹特征	作者	优缺点
运动特征	GPS	专家系统	最大速度的95%,平均速度,平均移动速度,段出现的位置是否有基础设施且接近程度值	Biljecki F^[1]	该类方法结合轨迹的特点以及统计学知识,提取具有较强识别能力的运动特征,但没有考虑到轨迹出现的地点以及具体时间信息
	GPS	决策树、支持向量机、贝叶斯网络、条件随机域	角度变化率 (HCR),停留次数比例 (SR)与速度变化率 (VCR)	Zheng Y^{[3, 18]}
	GPS	无监督学习	最大速度分布情况	Lin M^[17]
	GPS	决策树+隐马尔可夫	单条轨迹特征,前后段轨迹类别转换特征,地理数据特征	Zhu Y^[6]
	GPS、加速度计数据、陀螺仪数据	k近邻、支持向量机、决策树、Bagging与随机森林	加速度、速度、谱熵等165个特征值	Jahangiri A^[19]
	GPS	支持向量机	运动轨迹的全局特征与局部特征	朱进^[23]
	GPS	支持向量机	加速度、减速度、加速度和减速度标准偏差	Sun Z^[32]
	加速度计、陀螺仪	支持向量机、神经网络、决策树、Boosted Decision Tree、随机森林与朴素贝叶斯	两传感器数据标准差、偏度和峰度	Shafique M A^[20]
	GPS	神经网络	平均速度、停留时间、关键点信息等	Gonzalez P A^[11]
	GPS	高斯混合模型	速度信息	Zhu W^[15]
	GPS,加速度计	决策树+隐马尔可夫模式	均值,方差等	Reddy S^[21]
	GPS、真实交通数据	贝叶斯、决策树、随机森林	速度信息、平均车辆亲密度、平均铁路亲密度、平均候选车辆亲密度	Stenneth L^[33]
	GPS	支持向量机	速度、加速度	Bolbol A^[22]
	gms、wifi	决策树	基站信息、信号强度、接入wifi的持续时间等	Mun M^[34]
分类规则	GPS、呼叫详细记录	支持向量机	起点位置、终点位置、从起点到终点的运动时间	Wang H^[14]	该类方法充分利用训练数据,挖掘具有较强识别能力的分类规则,考虑到轨迹的时间以及地点信息,但仅适用于训练数据足够充分,便于挖掘规律的情况
分类规则	GPS	支持向量机	区域分类规则、路径分类规则	Brinkhoff T^[28]、Lee J G^[4]、 Patel D^[5]
图像信号	加速度计	Adaboost+隐马尔可夫	基于帧的特征、基于峰值的特征(加速度)、基于段的特征值	Hemminki S^[35]	该类方法更加注重轨迹形状对轨迹分类结果的影响,但轨迹转化为图像或信号时,并不能将时间信息考虑进去
	GPS	支持向量机	墨西哥帽小波、回归系数等5种特征的平均值与标准差	Macdonald A^[30]
	GPS	逻辑回归、支持向量机、决策树	转化为图像,使用神经网络自动生成特征	Endo Y^[31]

表1

参考文献 36

[1]	Biljecki F, Ledoux H, Van Oosterom P.Transportation mode-base segmentation and classification of movement trajectories[J]. International Journal of Geographical Information Science, 2013,27(2):385-407. doi: 10.1080/13658816.2012.692791
[2]	Mountain D, Raper J.Modelling human spatio-temporal behaviour: A challenge for location-based services[C]//Proceedings of 6th International Conference on Geocomputation. Brisbane: Australia, 2001:24-26.
[3]	Zheng Y, Chen Y, Li Q, et al.Understanding transportation modes based on GPS data for web applications[J]. Acm Transactions on the Web, 2010,4(1):495-507. doi: 10.1145/1658373.1658374
[4]	Lee J G, Han J, Li X, et al.TraClass: trajectory classification using hierarchical region-based and trajectory-based clustering[J]. Proceedings of the Vldb Endowment, 2008,1(1):1081-1094. doi: 10.14778/1453856.1453972
[5]	Patel D.Incorporating duration and region association information in trajectory classification[J]. Journal of Location Based Services, 2012,7(4):246-271. doi: 10.1109/ICDE.2012.72
[6]	Zhu Y, et al.Inferring taxi status using GPS trajectories. Tech.Rep.MSR-TR-2011-144, Microsoft Research, Asia, March 2011.
[7]	Lee J G, Han J, Li X. Trajectory outlier detection: Apartition and detect framework[C]//In: Proceedings of the 24th International Conference on Data Engineering. Washington:USA, 2008:140-149.
[8]	Krumm J, Horvitz E.LOCADIO: Inferring motion and location from Wi-Fi signal strengths[C]// International Conference on Mobile and Ubiquitous Systems: NETWORKING and Services. Boston: USA, 2004:4-13.
[9]	Yin J, Chai X, Yang Q.High-level goal recognition in a wireless LAN[C]// Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, 2004:578-584.
[10]	Zheng Y.Trajectory data mining: An overview[J]. Acm Transactions on Intelligent Systems & Technology, 2015,6(3):1-41. doi: 10.1145/2743025
[11]	Gonzalez P A, Weinstein J S, Barbeau S J, et al.Automating mode detection using neural networks and assisted GPS data collected using GPS-enabled mobile phones[C]// 15th World Congress on Intelligent Transport Systems and ITS America's 2008 Annual Meeting. New York, USA, 2008:30267-30279
[12]	肖艳丽,张振宇,杨文忠.移动数据的交通出行方式识别方法[J].智能系统学报,2014,9(5):536-543. doi: 10.3969/j.issn.1673-4785.201404045
	[ Xiao Y L, Zhang Z Y, Yang W Z.Research of the identification methods for transportation modes based on mobile data[J]. CAAI Transactions on Intelligent Systems, 2014,9(5):536-543. ] doi: 10.3969/j.issn.1673-4785.201404045
[13]	Assemi B, Safi H, Mesbah M, et al.Developing and validating a statistical model for travel mode identification on smartphones[J]. IEEE Transactions on Intelligent Transportation Systems, 2016,17(7):1920-1931. doi: 10.1109/TITS.2016.2516252
[14]	Wang H, Calabrese F, Di Lorenzo G, et al.Transportation mode inference from anonymized and aggregated mobile phone call detail records[C]//13th International IEEE Conference on Intelligent Transportation Systems (ITSC),Funchal: Portugal, 2010:318-323.
[15]	Zhu W, Ash J, Li Z, et al.Applying semi-supervised learning method for cellphone-based travel mode classification[C]//Smart Cities Conference (ISC2).London:UK, 2015:1-6.
[16]	Su X, Caceres H, Tong H, et al.Online travel mode identification using smartphones with battery saving considerations[J]. IEEE Transactions on Intelligent Transportation Systems, 2016,99(1):1-14. doi: 10.1109/TITS.2016.2530999
[17]	Lin M, Hsu W J, Lee Z Q.Detecting modes of transport from unlabeled positioning sensor data[J]. Journal of Location Based Services, 2013,7(4):272-290. doi: 10.1080/17489725.2013.819128
[18]	Zheng Y, Li Q, Chen Y, et al.Understanding mobility based on GPS data[C]//Ubiquitous Computing, International Conference, UBICOMP, Seoul: Korea, 2008:312-321.
[19]	Jahangiri A, Rakha H A.Applying machine learning techniques to transportation mode recognition using mobile phone sensor data[J]. IEEE transactions on intelligent transportation systems, 2015,16(5):2406-2417. doi: 10.1109/TITS.2015.2405759
[20]	Shafique M A, Hato E.A Comparison among various classification algorithms for travel mode detection using sensors' data collected by smartphones[C]//International Conference on Computers in Urban Planning and Urban Management, 2015.
[21]	Reddy S, Mun M, Burke J, et al.Using mobile phones to determine transportation modes[J]. Acm Transactions on Sensor Networks, 2010,6(2):662-701. doi: 10.1145/1689239.1689243
[22]	Bolbol A, Cheng T, Tsapakis I, et al.Inferring hybrid transportation modes from sparse GPS data using a moving window SVM classification[J]. Computers Environment & Urban Systems, 2012,36(6):526-537. doi: 10.1016/j.compenvurbsys.2012.06.001
[23]	朱进,江南,胡斌.移动对象多种运动参数在轨迹分类的应用[J].地球信息科学学报,2016,18(2):143-150. doi: 10.3724/SP.J.1047.2016.00143
	[ Zhu J, Jiang N, Hu B.The application of multiple movement parameters in trajectory classification for moving objects[J]. Journal of Geo-information Science, 2016,18(2):143-150. ] doi: 10.3724/SP.J.1047.2016.00143
[24]	Lin M, Hsu W J.Mining GPS data for mobility patterns: A survey[J]. Pervasive & Mobile Computing, 2014,12(11):1-16. doi: 10.1016/j.pmcj.2013.06.005
[25]	Fradkin D, Mörchen F.Mining sequential patterns for classification[J]. Knowledge & Information Systems, 2015,45(3):731-749. doi: 10.1007/s10115-014-0817-0
[26]	Cheng H, Yan X, Han J, et al.Discriminative frequent pattern analysis for effective classification[C]//IEEE, International Conference on Data Engineering. Istanbul:Turkey, 2007:716-725.
[27]	Cheng H, Yan X, Han J, et al.Direct discriminative pattern mining for effective classification[C]//2008 IEEE 24th International Conference on Data Engineering. Cancun: Mexico, 2008:169-178.
[28]	Brinkhoff T.A framework for generating network-based moving objects[J]. Geoinformatica, 2002,6(2):153-180. doi: 10.1023/A:1015231126594
[29]	Lee J G, Han J, Li X, et al.Mining discriminative patterns for classifying trajectories on road networks[J]. IEEE Transactions on Knowledge & Data Engineering, 2011,23(5):713-726.
[30]	Macdonald A, Ellen J.Multi-level resolution features for classification of transportation trajectories[C]//IEEE, International Conference on Machine Learning and Applications. Miami: FL, 2015:713-718.
[31]	Endo Y, Toda H, Nishida K, et al.Deep feature extraction from trajectories for transportation mode estimation[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. Auckland, New:Zealand, 2016:54-66.
[32]	Sun Z, Ban X.Vehicle classification using GPS data[J]. Transportation Research Part C Emerging Technologies, 2013,37(3):102-117. doi: 10.1016/j.trc.2013.09.015
[33]	Stenneth L, Wolfson O, Yu P S, et al.Transportation mode detection using mobile phones and GIS information[C]//ACM Sigspatial International Symposium on Advances in Geographic Information Systems, Chicago: USA, 2011:54-63.
[34]	Mun M Y, Seo Y W.Everyday mobility context classification using radio beacons[C]//Consumer Communications and NETWORKING Conference. IEEE, Las Vegas: NV, 2013:112-117.
[35]	Hemminki S, Nurmi P, Tarkoma S.Accelerometer-based transportation mode detection on smartphones[C]//ACM Conference on Embedded Networked Sensor Systems.Rome: Italy, 2013:1-14.
[36]	Boukhechba M, Bouzouane A, Bouchard B, et al.Online recognition of people's activities from raw GPS data: Semantic Trajectory Data Analysis[C]//Proceedings of the 8th ACM International Conference on Pervasive Technologies Related to Assistive Environments, 2015:575-578.