计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 251-259.doi: 10.11896／j.issn.1002-137X.2019.01.039
张怀峰, 皮德常, 董玉兰
ZHANG Huai-feng, PI De-chang, DONG Yu-lan
摘要： 移动对象轨迹聚类在城市规划、公共空间设计、移动对象行为预测等领域具有重要的理论指导意义和实际应用价值。针对传统聚类算法(如k-means,DBSCAN)在移动对象轨迹方面聚类效果不佳的问题,提出一种新的轨迹聚类算法iBTC。该算法首先对轨迹进行分段,根据最小描述长度原理,将轨迹分段问题转换为求无向图的最短路径问题,使用Dijkstra算法求得轨迹的最佳分段;然后将轨迹聚类问题转换为一种特殊的异常检测问题,并基于独立森林的思想,使用细分-合并过程对轨迹数据进行聚类;最后在模拟数据集和监控视频记录的行人轨迹公开数据集上进行实验,结果表明该算法能够取得较好的聚类效果。
中图分类号:
| [1]ACHTERT E,KRIEGEL H P,ZIMEK A.Deriving quantitative models for correlation clusters[C]//ACM SIGKDD Internatio-nal Conference on Knowledge Discovery and Data Mining.ACM,2006:4-13.<br /> [2]周志华.机器学习[M].北京:清华大学出版社,2016.<br /> [3]LLOYD S.Least squares quantization in PCM[J].IEEE Transactions on Information Theory,1982,28(2):129-137.<br /> [4]ZHANG T,RAMAKRISHNAN R,LIVNY M.BIRCH:An Effcient Data Clustering Method for Very Large Databases[C]//ACM SIGMOD Int’l Conference on Management of Data.ACM,1996:103-114.<br /> [5]ESTER M,KRIEGEL H P,XU X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]//International Conference on Knowledge Discovery and Data Mining.AAAI Press,1996:226-231.<br /> [6]WANG W,YANG J,MUNTZ R R.STING:A Statistical Information Grid Approach to Spatial Data Mining[C]//Internatio-nal Conference on Very Large Data Bases.Morgan Kaufmann Publishers Inc,1997:186-195.<br /> [7]NICOL F,PUECHMOREL S.Trajectories clustering:a minimum entropy approach[C]//The Second International Confe-rence on Big Data,Small Data.Linked Data and Open Data,2016:35-41.<br /> [8]LEE J G,HAN J,WHANG K Y.Trajectory clustering:a partition-and-group framework[C]//ACM SIGMOD International Conference on Management of Data.ACM,2007:593-604.<br /> [9]ZHANG D,LI N,ZHOU Z H,et al.iBAT:detecting anomalous taxi trajectories from GPS traces[C]//International Conference on Ubiquitous Computing.ACM,2011:99-108.<br /> [10]PALMA A T,BOGORNY V,KUIJPERS B,et al.A clustering-based approach for discovering interesting places in trajectories[C]//ACM Symposium on Applied Computing.DBLP,2008:863-868.<br /> [11]MASCIARI E.A Framework for Trajectory Clustering[C]//International Conference on Geosensor Networks.Springer-Verlag,2009:102-111.<br /> [12]HUNG C C,PENG W C,LEE W C.Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J].Vldb Journal,2015,24(2):169-192.<br /> [13]FLORIAN T,POKORNY F T,GOLDBERG K,et al.Topological trajectory clustering with relative persistent homology[C]//IEEE International Conference on Robotics and Automation.IEEE,2016:16-23.<br /> [14]GAFFNEY S,SMYTH P.Trajectory clustering with mixtures of regression models[C]//ACM SIGKDD International Confe-rence on Knowledge Discovery and Data Mining.ACM,1999:63-72.<br /> [15]IZAKIAN Z,MESGARI M S,ABRAHAM A.Automated clustering of trajectory data using a particle swarm optimization[J].Computers Environment & Urban Systems,2016,55:55-65.<br /> [16]NANNI M,PEDRESCHI D.Time-focused clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems,2006,27(3):267-289.<br /> [17]MITSCH S,MLLER A,RETSCHITZEGGER W,et al.A Survey on Clustering Techniques for Situation Awareness[M]//Web Technologies and Applications.Springer Berlin Heidelberg,2013:815-826.<br /> [18]YASODHA M,PONMUTHURAMALINGAM P.A survey on temporal data clustering[J].International Journal of Advanced Research in Computer and Communication Engineering,2016,1(9):768-772.<br /> [19]YUAN G,XIA S,ZHANG L,et al.An efficient trajectory-clustering algorithm based on an index tree[J].Transactions of the Institute of Measurement & Control,2012,34(7):850-861.<br /> [20]LI Z,JAEGIL L,LI X,et al.Incremental Clustering for Trajectories[C]//International Conference on Database Systems for Advanced Applications.Springer-Verlag,2010:32-46.<br /> [21]LIU F T,KAI M T,ZHOU Z H.Isolation Forest[C]//Eighth IEEE International Conference on Data Mining.IEEE Computer Society,2008:413-422.<br /> [22]CHEN M,CHOWDHURYR A,RAMACHANDRAN V,et al.Priority Queues and Dijkstra’s Algorithm.USA:University of Texas,2007:1-25.<br /> [23]FISHER B.Edinburgh informatics forum pedestrian database [OL].http://homepages.inf.ed.ac.uk/rbf/FORUMTRACKING. |
| [1] | 柴慧敏, 张勇, 方敏. 基于特征相似度聚类的空中目标分群方法 Aerial Target Grouping Method Based on Feature Similarity Clustering 计算机科学, 2022, 49(9): 70-75. https://doi.org/10.11896/jsjkx.210800203 |
| [2] | 鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于分层抽样优化的面向异构客户端的联邦学习 Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients 计算机科学, 2022, 49(9): 183-193. https://doi.org/10.11896/jsjkx.220500263 |
| [3] | 刘丽, 李仁发. 医疗CPS协作网络控制策略优化 Control Strategy Optimization of Medical CPS Cooperative Network 计算机科学, 2022, 49(6A): 39-43. https://doi.org/10.11896/jsjkx.210300230 |
| [4] | 鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于DBSCAN聚类的集群联邦学习方法 Clustered Federated Learning Methods Based on DBSCAN Clustering 计算机科学, 2022, 49(6A): 232-237. https://doi.org/10.11896/jsjkx.211100059 |
| [5] | 郁舒昊, 周辉, 叶春杨, 王太正. SDFA:基于多特征融合的船舶轨迹聚类方法研究 SDFA:Study on Ship Trajectory Clustering Method Based on Multi-feature Fusion 计算机科学, 2022, 49(6A): 256-260. https://doi.org/10.11896/jsjkx.211100253 |
| [6] | 毛森林, 夏镇, 耿新宇, 陈剑辉, 蒋宏霞. 基于密度敏感距离和模糊划分的改进FCM算法 FCM Algorithm Based on Density Sensitive Distance and Fuzzy Partition 计算机科学, 2022, 49(6A): 285-290. https://doi.org/10.11896/jsjkx.210700042 |
| [7] | 陈景年. 一种适于多分类问题的支持向量机加速方法 Acceleration of SVM for Multi-class Classification 计算机科学, 2022, 49(6A): 297-300. https://doi.org/10.11896/jsjkx.210400149 |
| [8] | 陈佳舟, 赵熠波, 徐阳辉, 马骥, 金灵枫, 秦绪佳. 三维城市场景中的小物体检测 Small Object Detection in 3D Urban Scenes 计算机科学, 2022, 49(6): 238-244. https://doi.org/10.11896/jsjkx.210400174 |
| [9] | 邢云冰, 龙广玉, 胡春雨, 忽丽莎. 基于SVM的类别增量人体活动识别方法 Human Activity Recognition Method Based on Class Increment SVM 计算机科学, 2022, 49(5): 78-83. https://doi.org/10.11896/jsjkx.210400024 |
| [10] | 朱哲清, 耿海军, 钱宇华. 面向化学结构的线段聚类算法 Line-Segment Clustering Algorithm for Chemical Structure 计算机科学, 2022, 49(5): 113-119. https://doi.org/10.11896/jsjkx.210700131 |
| [11] | 张宇姣, 黄锐, 张福泉, 隋栋, 张虎. 基于菌群优化的近邻传播聚类算法研究 Study on Affinity Propagation Clustering Algorithm Based on Bacterial Flora Optimization 计算机科学, 2022, 49(5): 165-169. https://doi.org/10.11896/jsjkx.210800218 |
| [12] | 左园林, 龚月姣, 陈伟能. 成本受限条件下的社交网络影响最大化方法 Budget-aware Influence Maximization in Social Networks 计算机科学, 2022, 49(4): 100-109. https://doi.org/10.11896/jsjkx.210300228 |
| [13] | 杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009 |
| [14] | 韩洁, 陈俊芬, 李艳, 湛泽聪. 基于自注意力的自监督深度聚类算法 Self-supervised Deep Clustering Algorithm Based on Self-attention 计算机科学, 2022, 49(3): 134-143. https://doi.org/10.11896/jsjkx.210100001 |
| [15] | 蒲实, 赵卫东. 一种面向动态科研网络的社区检测算法 Community Detection Algorithm for Dynamic Academic Network 计算机科学, 2022, 49(1): 89-94. https://doi.org/10.11896/jsjkx.210100023 |
|
||
首页