移动轨迹聚类方法研究综述

doi:10.13474/j.cnki.11-2246.2018.0001

摘要/Abstract

摘要：

轨迹数据是人类移动行为的表征，能够映射出人的出行模式和社会属性等信息。怎样有效挖掘轨迹数据蕴藏的人类活动规律一直是研究的热点。通过轨迹聚类发现行为相似的类簇，从而探究群体的移动模式是轨迹挖掘和深度应用常见的方法之一。本文首先根据轨迹数据的特点，将轨迹数据模型分为轨迹点模型和轨迹段模型，并据此定义相应的相似性度量：空间相似性度量和时空相似性度量；然后，对两类模型的聚类方法进行了综述，并总结不同聚类算法的优缺点，以期为不同应用选取聚类算法提供科学依据；最后对移动轨迹数据聚类方法研究的发展趋势进行了讨论。

关键词: 移动轨迹数据, 数据挖掘, 聚类方法, 研究综述

Abstract:

Mobile trajectory data is the representation of human mobile behavior.Mining this kind of data and discovering their latent semantic information can map the people's travel patterns and social attribute,etc.The clustering method based on similarity is a common method of data mining.Trajectory clustering can be used to find the object group of the similar behavior,so as to find the relevant moving patterns.According to the characteristics of the trajectory data,the trajectory data model is divided into trajectory point model and trajectory segment model,and the corresponding similarity measure is defined:spatial similarity measure and spatio-temporal similarity measure.Then,the clustering methods of two models are reviewed,and the advantages and disadvantages of the algorithms are also summarized,which provide the basis for effective selection of clustering algorithms.Finally,the development trend of the research on the clustering method of the moving trace data is discussed.

Key words: mobile trajectory data, data mining, the clustering method, research summary

中图分类号:

P208

牟乃夏, 徐玉静, 张恒才, 陈洁, 张灵先, 刘希亮. 移动轨迹聚类方法研究综述[J]. 测绘通报, 2018, 0(1): 1-7.

MOU Naixia, XU Yujing, ZHANG Hengcai, CHEN Jie, ZHANG Lingxian, LIU Xiliang. A Review of the Mobile Trajectory Clustering Methods[J]. 测绘通报, 2018, 0(1): 1-7.

参考文献

[1] 牟乃夏,张恒才,陈洁,等.轨迹数据挖掘城市应用研究综述[J].地球信息科学学报,2015,17(10):1136-1142.
[2] 李石坚,齐观德,张王晟.移动轨迹数据分析与智慧城市[J].中国计算机学会通讯,2012,8(5):31-37.
[3] 李清泉,李德仁.大数据GIS[J].武汉大学学报(信息科学版),2014,39(6):641-644.
[4] 郑宇.城市计算概述[J].武汉大学学报(信息科学版),2015,40(1):1-13.
[5] YE Y,ZHENG Y,CHEN Y,et al.Mining Individual Life Pattern Based on Location History[C]//Tenth International Conference on Mobile Data Management:Systems.Taipei:[s.n.],2009.
[6] 刘瑜,康朝贵,王法辉.大数据驱动的人类移动模式和模型研究[J].武汉大学学报(信息科学版),2014,39(6):660-666.
[7] 龚玺,裴韬,孙嘉,等.时空轨迹聚类方法研究进展[J].地理科学进展,2011,30(5):522-534.
[8] 刘瑜,肖昱,高松,等.基于位置感知设备的人类移动研究综述[J].地理与地理信息科学,2011,27(4):8-13.
[9] YUAN J,ZHENG Y,XIE X.Discovering Regions of Different Functions in a City Using Human Mobility and POIs[C]//ACM Sigkdd International Conference on Knowledge Discovery and Data Mining.[S.l.]:ACM,2012.
[10] MOUSAVI S M,HARWOOD A,KARUNASEKERA S,et al.Geometry of Interest (GOI):Spatio-temporal Destination Extraction and Partitioning in GPS Trajectory Data[J].Journal of Ambient Intelligence and Humanized Computing,2016:1-16.
[11] PANG L X,CHAWLA S,LIU W,et al.On Detection of Emerging Anomalous Traffic Patterns Using GPS Data[J].Data & Knowledge Engineering,2013,87(9):357-373.
[12] 龙瀛,张宇,崔承印.利用公交刷卡数据分析北京职住关系和通勤出行[J].地理学报,2012,67(10):1339-1352.
[13] 徐金垒,方志祥,萧世伦,等.城市海量手机用户停留时空分异分析——以深圳市为例[J].地球信息科学学报,2015,17(2):197-205.
[14] 陈佳,胡波,左小清,等.利用手机定位数据的用户特征挖掘[J].武汉大学学报(信息科学版),2014,39(6):734-738.
[15] 常晓猛,乐阳,李清泉,等.利用位置的虚拟社交网络地理骨干网提取[J].武汉大学学报(信息科学版),2014,39(6):706-710.
[16] 李婷,裴韬,袁烨城,等.人类活动轨迹的分类、模式和应用研究综述[J].地理科学进展,2014,33(7):938-948.
[17] KOBAYASHI T,SHINAGAWA N,WATANABE Y.Vehicle Mobility Characterization Based on Measurements and Its Application to Cellular Communication Systems (Special Issue on Multimedia Mobile Communication Systems)[J].Ieice Transactions on Communications,1999,82(12):2055-2060.
[18] 许宁,尹凌,胡金星.从大规模短期规则采样的手机定位数据中识别居民职住地[J].武汉大学学报(信息科学版),2014,39(6):750-756.
[19] WON J I,KIM S W,BAEK J H,et al.Trajectory Clustering in Road Network Environment[J].IEEE Symposium on Computational Intelligence and Data Mining,2009(3):299-305.
[20] 吴笛,杜云艳,易嘉伟,等.基于密度的轨迹时空聚类分析[J].地球信息科学学报,2015,17(10):1162-1171.
[21] 宋乐怡.海量出租车轨迹数据分析与位置推荐服务[D].上海:华东师范大学,2015.
[22] HAN J,KAMBER M.Data Mining:Concepts and Technique[M].[S.l.]:Morgan Kaufmann Publishers Inc.,2006.
[23] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.
[24] MACQUEEN J.Some Methods for Classification and Analysis of Multivariate Observations[C]//Proceedings of Berkeley Symposium on Mathematical Statistics and Probability.[S.l.]:University of California Press,1967.
[25] KAUFMAN L,ROUSSEEUW P J.Finding Groups in Data:An Introduction to Cluster Analysis[M].[S.l.]:John Wiley & Sons,Inc.,2008.
[26] DEMPSTER A,LAIRD N,RUBIN D. Maximum Likelihood Eitimation from Imcomplete Data via EM Algorithm[J].Journal of the Royal Statistical Society:Series B,1977,39:1-38.
[27] MOHAMED O O K,EL-SHARKAWI M E,MOKHTAR H,et al.Mining Moving Objects Trajectories[J].2012.
[28] PARK H S,JUN C H.A Simple and Fast Algorithm for K-medoids Clustering[J].Expert Systems with Applications,2009,36(2):3336-3341.
[29] 何彬彬,方涛,郭达志.基于不确定性的空间聚类[J].计算机科学,2004,31(11):196-198.
[30] ZHONG C,MIAO D,FRÄNTI P.Minimum Spanning Tree Based Split-and-merge:A Hierarchical Clustering Method[J].Information Sciences,2011,181(16):3397-3410.
[31] ZHANG T,RAMAKRISHNAN R,LINVY M.BIRCH:An Efficient Data Clustering Method for Very Large Databases[J].ACM Sigmod International Conference on Management of Data,1996,25(2):103-114.
[32] ROUSSEEUW P J,KAUFMAN L.Finding Groups in Data[J].Series in Probability & Mathematical Statistics,1990,34(1):111-112.
[33] GUHA S,RASTOGI R,SHIM K.ROCK:A Robust Clustering Algorithm for Categorical Attributes[J].Information Systems,1999,25(5):345-366.
[34] TU Y,LIU Y,LI Z.Online Segmentation Algorithm for Time Series Based on BIRCH Clustering Features[C]//International Conference on Computational Intelligence and Security.Nanning:SCIS,2010.
[35] SHAO X,CHENG W.Improved CURE Algorithm and Application of Clustering for Large-scale Data[C]//International Symposium on IT in Medicine and Education (ITME).Guangzhou:IEEE,2011.
[36] HINNEBURG A,KEIM D A.An Efficient Approach to Clustering in Large Multimedia Databases with Noise[C]//Proceedings of the Fourth Data Mining.New York:AAAI Press,1998.
[37] ESTER M,KRIEGEL H P,SANDER J,et al.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]//Proceeding of the Second International Conference on Knowledge Discovery and Data Mining. Portland:AAAI Press,1996.
[38] ANKERST M,BREUNIG M M,KRIEGEL H,et al.OPTICS:Ordering Points to Identify the Clustering Structure[J].ACM SIGMOD Record,1999,28(2):49-60.
[39] SCHOIER G.On the MDBSCAN Algorithm in a Spatial Data Mining Context[J].Data Mining Concepts Methodologies Tools & Applications,2013,7974:375-388.
[40] EDLA D R,JANA P K.A Grid Clustering Algorithm Using Cluster Boundaries[J].Information and Communication Technologies,2013,15(3):254-259.
[41] 周涛,陆惠玲.数据挖掘中聚类算法研究进展[J].计算机工程与应用,2012,48(12):100-111.
[42] 赵慧,刘希玉,崔海青.网格聚类算法[J].计算机技术与发展,2010,20(9):83-85.
[43] WANG W,YANG J,MUNTZ R R.STING:A Statistical Information Grid Approach to Spatial Data Mining[C]//Proceedings of International Conference on Very Large Data Bases.Athens,Greece:Morgan Kaufmann Publishers Inc.,1997.
[44] AGRAWAL R,GEHRKE J,GUNOPULOS D,et al.Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[J].ACM,1998,27(2):94-105.
[45] 邓敏,刘启亮,李光强,等.基于场论的空间聚类算法[J].遥感学报,2010,14(4):694-709.
[46] IZAKIAN Z,MESGARI M S,ABRAHAM A.Automated Clustering of Trajectory Data Using a Particle Swarm Optimization[J].Computers,Environment and Urban Systems,2016,55:55-65.
[47] LI Y,HAN J,YANG J.Clustering Moving Objects[C]//Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Seattle:ACM,2004.
[48] 贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究,2007,24(1):10-13.
[49] TUNG A K H,HOU J,HAN J,et al.Spatial Clustering in the Presence of Obstacles[C]//2013 IEEE 29th International Conference on Data Engineering.Herdelberg:ICDE,2001:359-367.
[50] LIU W,FENG J,WANG Z.Constrained Clustering Objects on a Spatial Network[C]//2009 WRI World Congress on Computer Science and Information Engineering.Los Angeles:IEEE,2009.
[51] 廖律超,蒋新华,邹复民,等.浮动车轨迹数据聚类的有向密度方法[J].地球信息科学学报,2015,17(10):1152-1161.
[52] 王金凤,邢长征.基于道路网络的移动对象聚类[J].计算机工程与应用,2016,52(7):74-78.
[53] 马林兵,李鹏.基于子空间聚类算法的时空轨迹聚类[J].地理与地理信息科学,2014,30(4):7-11.
[54] LEE J G,HAN J,WHANG K Y.Trajectory Clustering:A Partition-and-group Framework[C]//ACM SIGMOD International Conference on Management of Data.Beijing:ACM,2007.
[55] HAN B,LIU L,OMIECINSKI E.NEAT:Road Network Aware Trajectory Clustering[C]//IEEE International Conference on Distributed Computing Systems.[S.l.]:IEEE,2012.