OPTICS与离线批处理在轨迹聚类中的应用

doi:10.19678/j.issn.1000-3428.0054309

计算机工程 ›› 2020, Vol. 46 ›› Issue (7): 72-77,83. doi: 10.19678/j.issn.1000-3428.0054309

OPTICS与离线批处理在轨迹聚类中的应用

郭雨^1,2, 陈金勇², 张新宇¹, 李梁¹, 孙未未¹

1. 复旦大学计算机科学技术学院, 上海 201203;
2. 中国电子科技集团公司航天信息应用技术重点实验室, 石家庄 050081

收稿日期:2019-03-20 修回日期:2019-07-04 发布日期:2019-07-13
作者简介:郭雨(1997-),男,硕士研究生,主研方向为空间数据处理、LBS定位;陈金勇,研究员;张新宇、李梁,硕士研究生;孙未未,教授。
基金资助:
国家自然科学基金面上项目（61772138）；中国电子科技集团公司航天信息应用技术重点实验室开放基金。

Application of OPTICS and Offline Batch Processing in Trajectory Clustering

GUO Yu^1,2, CHEN Jinyong², ZHANG Xinyu¹, LI Liang¹, SUN Weiwei¹

1. School of Computer Science, Fudan University, Shanghai 201203, China;
2. CETC Key Laboratory of Aerospace Information Applications, Shijiazhuang 050081, China

Received:2019-03-20 Revised:2019-07-04 Published:2019-07-13

摘要/Abstract

摘要： 轨迹聚类是时空轨迹处理中的重要步骤，常用的轨迹聚类算法如TRACLUS算法，时间复杂度通常较高且对输入参数敏感，在寻找最优参数的过程中会消耗大量的时间。针对该问题，对TRACLUS算法运用离线批处理技术与OPTICS算法进行改进，在缓解输入参数敏感性的同时，减少对多组参数进行轨迹聚类的时间，从而减轻人为参数调试的工作量。实验结果表明，在最优参数未知需要对多组参数进行测试时，改进算法可使运行效率得到大幅提升。

关键词: 时空轨迹聚类, 密度聚类, OPTICS算法, 离线批处理, TRACLUS算法

Abstract: Trajectory clustering is an important step in spatio-temporal trajectory processing.Common trajectory clustering algorithms,such as TRACLUS algorithm,usually have high time complexity and are sensitive to input parameters,thus consuming a lot of time to find optimal parameters.In order to solve this problem,this paper improves the TRACLUS algorithm by using offline batch processing technology and OPTICS algorithm.This optimization reduces the sensitivity of input parameters and the time for trajectory clustering of multiple sets of parameters,so the workload of the manual parameter debugging is reduced.Experimental results show that the time efficiency of the algorithm has been greatly improved when the optimal parameters are unknown and multiple sets of parameters need to be tested.

Key words: spatio-temporal trajectory clustering, density clustering, OPTICS algorithm, offline batch processing, TRACLUS algorithm

中图分类号:

TP18

郭雨, 陈金勇, 张新宇, 李梁, 孙未未. OPTICS与离线批处理在轨迹聚类中的应用[J]. 计算机工程, 2020, 46(7): 72-77,83.

GUO Yu, CHEN Jinyong, ZHANG Xinyu, LI Liang, SUN Weiwei. Application of OPTICS and Offline Batch Processing in Trajectory Clustering[J]. Computer Engineering, 2020, 46(7): 72-77,83.

https://www.ecice06.com/CN/Y2020/V46/I7/72

参考文献

[1] GIANNOTTI F,NANNI M,PEDRESCHI D,et al.Unveiling the complexity of human mobility by querying and mining massive trajectory data[J].The VLDB Journal,2011,20(5):695-719.
[2] YU Zheng.Trajectory data mining:an overview[J].ACM Transactions on Intelligent Systems and Technology,2015,6(3):1-29.
[3] PARENT C,SPACCAPIETRA S,RENSO C,et al.Semantic trajectories modeling and analysis[J].ACM Computing Surveys,2013,45(4):1-42.
[4] PICIARELLI C,FORESTI G L.On-line trajectory clustering for anomalous events detection[J].Pattern Recognition Letters,2006,27(15):1835-1842.
[5] FU Zhouyu,HU Weiming,TAN Tieniu.Similarity based vehicle trajectory clustering and anomaly detection[C]//Proceedings of IEEE International Conference on Image Processing.Washington D.C.,USA:IEEE Press,2005:602-605.
[6] WU Peili,LIU Kui’en,HAO Shengang,et al.Rapid traffic congestion monitoring based on floating car data[J].Journal of Computer Research and Development,2014,51(1):189-198.(in Chinese) 吴佩莉,刘奎恩,郝身刚,等.基于浮动车数据的快速交通拥堵监控[J].计算机研究与发展,2014,51(1):189-198.
[7] ROH G P,HWANG S W.NNCluster:an efficient clustering algorithm for road network trajectories[C]//Proceedings of International Conference on Database Systems for Advanced Applications.Berlin,Germany:Springer,2010:47-61.
[8] WON J I,KIM S W,BAEK J H,et al.Trajectory clustering in road network environment[C]//Proceedings of IEEE Symposium on Computational Intelligence and Data Mining.Washington D.C.,USA:IEEE Press,2009:299-305.
[9] HAN B,LIU L,OMIECINSKI E.NEAT:road network aware trajectory clustering[C]//Proceedings of the 32nd IEEE International Conference on Distributed Computing Systems.Washington D.C.,USA:IEEE Press,2012:142-151.
[10] WU Yingjie,TANG Qingming,NI Weiwei,et al.A clustering hybrid based algorithm for privacy preserving trajectory data publishing[J].Journal of Computer Research and Development,2013,50(3):578-593.(in Chinese) 吴英杰,唐庆明,倪巍伟,等.基于聚类杂交的隐私保护轨迹数据发布算法[J].计算机研究与发展,2013,50(3):578-593.
[11] CHI Xiangsong,PI Dechang,GUAN Peng.High-density sub-trajectory clustering algorithm for moving objects[J].Journal of Chinese Computer Systems,2016,37(9):2014-2018.(in Chinese) 迟相松,皮德常,关鹏.移动对象高密度子轨迹聚类算法[J].小型微型计算机系统,2016,37(9):2014-2018.
[12] ANJUM N,CAVALLARO A.Multifeature object trajectory clustering for video analysis[J].IEEE Transactions on Circuits and Systems for Video Technology,2008,18(11):1555-1564.
[13] ALON J,SCLAROFF S,KOLLIOS G,et al.Discovering clusters in motion time-series data[C]//Proceedings of 2003 IEEE Computer Society Conference on Computer Vision and Pattern.Washington D.C.,USA:IEEE Press,2003:1-5.
[14] SUN Hong,CHEN Suo.Spatio-temporal trajectory prediction algorithm based on clustering based hidden markov model[J].Journal of Chinese Computer Systems,2019,40(3):472-476.(in Chinese) 孙红,陈锁.一种聚类隐马尔可夫模型的时空轨迹预测算法[J].小型微型计算机系统,2019,40(3):472-476.
[15] BUZAN D,SCLAROFF S,KOLLIOS G.Extraction and clustering of motion trajectories in video[C]//Proceedings of the 17th International Conference on Pattern Recognition.Washington D.C.,USA:IEEE Press,2004:521-524.
[16] NANNI M,PEDRESCHI D.Time-focused clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems,2006,27(3):267-289.
[17] LEE J G,HAN J W,WHANG K Y.Trajectory clustering:a partition-and-group framework[C]//Proceedings of 2007 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2007:593-604.
[18] LEE J G,HAN J,LI X L.Trajectory outlier detection:a partition-and-detect framework[C]//Proceedings of the 24th IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2008:140-149.
[19] LEE J G,HAN J W,LI X L,et al.TraClass:trajectory classification using hierarchical region-based and trajectory-based clustering[J].Proceedings of the VLDB Endowment,2008,1(1):1081-1094.
[20] LI Z H,LEE J G,LI X L,et al.Incremental clustering for trajectories[C]//Proceedings of IEEE International Conference on Database Systems for Advanced Applications.Washington D.C.,USA:IEEE Press,2010:32-46.
[21] SUNG C,FELDMAN D,RUS D.Trajectory clustering for motion prediction[C]//Proceedings of 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems.Washington D.C.,USA:IEEE Press,2012:1547-1552.
[22] CHEN Jinyang,SONG Jiatao,LIU Liangxu.Trajectory clustering algorithm based on improved Hausdorff distance[J].Computer Engineering,2012,38(17):157-161.(in Chinese)陈锦阳,宋加涛,刘良旭.基于改进Hausdorff距离的轨迹聚类算法[J].计算机工程,2012,38(17):157-161.
[23] JIANG Yuling,XIONG Zhennan,TANG Jihong.Ship trajectory clustering algorithm based on DBSCAN[J].Navigation of China,2019,42(3):1-5.(in Chinese)江玉玲,熊振南,唐基宏.基于轨迹段DBSCAN的船舶轨迹聚类算法[J].中国航海,2019,42(3):1-5.
[24] SHI Chonglin,GAN Wenyan,WU Lin,et al.Clustering trajectories of entities in computer wargames[J].Journal of Software,2013,24(3):465-475.(in Chinese)石崇林,淦文燕,吴琳,等.计算机兵棋作战实体轨迹聚类算法[J].软件学报,2013,24(3):465-475.
[25] ANKERST M,BREUNIG M M,KRIEGEL H P,et al.Optics:ordering points to identify the clustering structure[J].ACM SIGMOD Record,1999,28(2):49-60.
[26] ESTER M,KRIEGEL H P,SANDER J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data.New York,USA:ACM Press,1996:226-231.

选择文件类型/文献管理软件名称

选择包含的内容

OPTICS与离线批处理在轨迹聚类中的应用

Application of OPTICS and Offline Batch Processing in Trajectory Clustering

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价

[1]	王治和, 曹旭琰, 杜辉. 一种优化初始点与自适应半径的密度聚类算法[J]. 计算机工程, 2022, 48(1): 51-59.
[2]	李文斌, 何冉. 基于深度神经网络的遥感图像飞机目标检测[J]. 计算机工程, 2020, 46(7): 268-276.
[3]	安建瑞,张龙波,王雷,金超,怀浩,王晓丹. 一种基于网格与加权信息熵的OPTICS改进算法[J]. 计算机工程, 2017, 43(2): 206-209.
[4]	许合利,牛丽君. 基于层次与密度的任意形状聚类算法[J]. 计算机工程, 2016, 42(7): 159-164.
[5]	费欢,李光辉. 基于K-means聚类的WSN异常数据检测算法[J]. 计算机工程, 2015, 41(7): 124-128.
[6]	张恒;邹开其;崔杰;张敏. 一种改进的基于密度聚类模糊支持向量机[J]. 计算机工程, 2009, 35(5): 194-196.
[7]	祁立;刘玉树. 基于两阶段聚类的模糊支持向量机 [J]. 计算机工程, 2008, 34(1): 4-6.
[8]	单世民;邓贵仕;何英昊. 基于密度的微粒群优化混合聚类算法[J]. 计算机工程, 2007, 33(08): 170-172.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

OPTICS与离线批处理在轨迹聚类中的应用

Application of OPTICS and Offline Batch Processing in Trajectory Clustering

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价