第1期 陆剑锋，等：基于时空约束密度聚类的停留点识别方法 ·65· 300 -ST DBSCAN DBSCAN_TE 544):263-270 250 ST DBSCAN GPSC DBSCAN [4]杨震，王红军.基于Adaboost-Markov模型的移动用户位 置预测方法U.计算机应用，2019,39(3675-680. 150 YANG Zhen,WANG Hongjun.Location prediction meth- od of mobile user based on Adaboost-Markov model[J] 100 Journal of computer applications,2019,39(3):675-680. 50 [5]石陆魁.张延茹，张欣.基于时空模式的轨迹数据聚类算 法[.计算机应用，2017,37(3)：854-859,895 SHI Lukui,ZHANG Yanru,ZHANG Xin.Trajectory data 图83种算法的运行时间对比 clustering algorithm based on spatiotemporal pattern[J]. Fig.8 Comparison of the running time of the three al- Journal of computer applications,2017,37(3):854-859, gorithms 895. 但是，ST DBSCAN方法仍存在一定的识别 [6]FU Zhongliang,TIAN Zongshun,XU Yanqing,et al.A 错误，其原因在于：部分停留点和移动点的簇的 two-step clustering approach to extract locations from indi- 特征特别相似。如人在特定状态时的不移动（属 vidual GPS trajectory data[J].ISPRS international journal 于停留点)与等车、等红绿灯和堵车（属于移动 of geo-information,2016,5(10):166. 点)的特征非常相近，因而在建立约束条件的时 [7]XIANG Longgang,GAO Meng,WU Tao.Extracting stops from noisy trajectories:a sequence oriented clustering ap- 候无法有效识别。 proach[J].ISPRS international journal of geo-information, 3结束语 2016,5(3):29 [8]GONG Lei,SATO H.YAMAMOTO T,et al.Identifica- 本文采用基于时空约束的密度聚类算法对 tion of activity stop locations in GPS trajectories by dens- GPS轨迹数据进行识别，首先对数据轨迹进行聚 ity-based clustering method combined with support vector 类分段，然后利用约束条件来获得停留点和移动 machines[J].Journal of modern transportation,2015, 点。实验结果表明本文的算法是有效的。本文还 23(3):202-213. 有许多需要提高的地方，比如在识别非常相似的 [9]GONG Lei,YAMAMOTO T,MORIKAWA T.Identifica- 簇时需要获得更有识别率的特征；在提高算法的 tion of activity stop locations in GPS trajectories by DB- 泛化能力方面，可进一步优化识别方法的约束条 SCAN-TE method combined with support vector ma- 件，减少约束参数。同时，实验结果也表明轨迹 chines[J].Transportation research procedia,2018,32: 146-154. 数据特征的不足，以后需要加入更多维度的特 [10]GINGERICH K,MAOH H,ANDERSON W.Classify- 征，此外，约束条件还会考虑其他的特征，如加速 ing the purpose of stopped truck events:an application of 度、方向角和方向变化率等，这些为本文的未来 entropy to GPS data[J].Transportation research part C: 研究方向。 emerging technologies,2016,64:17-27. 参考文献： [1]张鹏.基于蜂窝网络数据的用户移动性分析和兴趣区 挖掘D1.北京：北京邮电大学，2018：31-52. [1]吕志娟.基于Lifelog数据的个人轨迹模式挖掘算法的 ZHANG Peng.User mobility research and interest region 研究与应用D]沈阳：东北大学，2015：20-30. mining based on cellular networks traffic[D].Beijing: LYU Zhijuan.Research and application of personal traject- Beijing University of Posts and Telecommunications, ory pattern mining algorithm based on Lifelog data[D]. 2018:31-52. Shenyang:Northeastern University,2015:20-30. [12]向隆刚，邵晓天.载体轨迹停留信息提取的核密度法及 [2]JIANG Renhe,ZHAO Jing,DONG Tingting,et al.A dens- 其可视化[.测绘学报，2016,45(9)：1122-1131 ity-based approach for mining movement patterns from se- XIANG Longgang,SHAO Xiaotian.Visualization and mantic trajectories[Cl/TENCON 2015-2015 IEEE Region extraction of trajectory stops based on kernel-density[J]. 10 Conference.Macao,China,2015. Acta geodaetica et cartographica sinica,2016,45(9): [3]张文元，谈国新，朱相舟.停留点空间聚类在景区热点 1122-1131. 分析中的应用).计算机工程与应用，2018,54(4)： [13]LIAO Lin,FOX D,KAUTZ H.Extracting places and 263-270. activities from GPS traces using hierarchical conditional ZHANG Wenyuan,TAN Guoxin,ZHU Xiangzhou.Ap- random fields[J].International journal of robotics re- plication of stay points spatial clustering in hot scenic spots search,2007,26(1):119-134. analysis[J].Computer engineering and applications,2018. [14]李毓瑞，陈红梅，王丽珍，等.基于密度的停留点识别方300 250 200 150 100 50 0 user1/1 user1/2 user1/3 user2/1 user2/2 user2/3 user3/1 user3/2 user3/3 ST_DBSCAN ST_DBSCAN_GPS DBSCAN_TE C_DBSCAN 运行时间/s 图 8 3 种算法的运行时间对比 Fig. 8 Comparison of the running time of the three al￾gorithms 但是，ST_DBSCAN 方法仍存在一定的识别 错误，其原因在于：部分停留点和移动点的簇的 特征特别相似。如人在特定状态时的不移动 (属 于停留点) 与等车、等红绿灯和堵车 (属于移动 点) 的特征非常相近，因而在建立约束条件的时 候无法有效识别。 3 结束语 本文采用基于时空约束的密度聚类算法对 GPS 轨迹数据进行识别，首先对数据轨迹进行聚 类分段，然后利用约束条件来获得停留点和移动 点。实验结果表明本文的算法是有效的。本文还 有许多需要提高的地方，比如在识别非常相似的 簇时需要获得更有识别率的特征；在提高算法的 泛化能力方面，可进一步优化识别方法的约束条 件，减少约束参数。同时，实验结果也表明轨迹 数据特征的不足，以后需要加入更多维度的特 征，此外，约束条件还会考虑其他的特征，如加速 度、方向角和方向变化率等，这些为本文的未来 研究方向。 参考文献： 吕志娟. 基于 Lifelog 数据的个人轨迹模式挖掘算法的 研究与应用 [D]. 沈阳: 东北大学, 2015: 20–30. LYU Zhijuan. Research and application of personal traject￾ory pattern mining algorithm based on Lifelog data[D]. Shenyang: Northeastern University, 2015: 20–30. [1] JIANG Renhe, ZHAO Jing, DONG Tingting, et al. A dens￾ity-based approach for mining movement patterns from se￾mantic trajectories[C]//TENCON 2015-2015 IEEE Region 10 Conference. Macao, China, 2015. [2] 张文元, 谈国新, 朱相舟. 停留点空间聚类在景区热点 分析中的应用 [J]. 计算机工程与应用, 2018, 54(4): 263–270. ZHANG Wenyuan, TAN Guoxin, ZHU Xiangzhou. Ap￾plication of stay points spatial clustering in hot scenic spots analysis[J]. Computer engineering and applications, 2018, [3] 54(4): 263–270. 杨震, 王红军. 基于 Adaboost-Markov 模型的移动用户位 置预测方法 [J]. 计算机应用, 2019, 39(3): 675–680. YANG Zhen, WANG Hongjun. Location prediction meth￾od of mobile user based on Adaboost-Markov model[J]. Journal of computer applications, 2019, 39(3): 675–680. [4] 石陆魁, 张延茹, 张欣. 基于时空模式的轨迹数据聚类算 法 [J]. 计算机应用, 2017, 37(3): 854–859, 895. SHI Lukui, ZHANG Yanru, ZHANG Xin. Trajectory data clustering algorithm based on spatiotemporal pattern[J]. Journal of computer applications, 2017, 37(3): 854–859, 895. [5] FU Zhongliang, TIAN Zongshun, XU Yanqing, et al. A two-step clustering approach to extract locations from indi￾vidual GPS trajectory data[J]. ISPRS international journal of geo-information, 2016, 5(10): 166. [6] XIANG Longgang, GAO Meng, WU Tao. Extracting stops from noisy trajectories: a sequence oriented clustering ap￾proach[J]. ISPRS international journal of geo-information, 2016, 5(3): 29. [7] GONG Lei, SATO H, YAMAMOTO T, et al. Identifica￾tion of activity stop locations in GPS trajectories by dens￾ity-based clustering method combined with support vector machines[J]. Journal of modern transportation, 2015, 23(3): 202–213. [8] GONG Lei, YAMAMOTO T, MORIKAWA T. Identifica￾tion of activity stop locations in GPS trajectories by DB￾SCAN-TE method combined with support vector ma￾chines[J]. Transportation research procedia, 2018, 32: 146–154. [9] GINGERICH K, MAOH H, ANDERSON W. Classify￾ing the purpose of stopped truck events: an application of entropy to GPS data[J]. Transportation research part C: emerging technologies, 2016, 64: 17–27. [10] 张鹏. 基于蜂窝网络数据的用户移动性分析和兴趣区 挖掘 [D]. 北京: 北京邮电大学, 2018: 31–52. ZHANG Peng. User mobility research and interest region mining based on cellular networks traffic[D]. Beijing: Beijing University of Posts and Telecommunications, 2018: 31–52. [11] 向隆刚, 邵晓天. 载体轨迹停留信息提取的核密度法及 其可视化 [J]. 测绘学报, 2016, 45(9): 1122–1131. 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. [12] LIAO Lin, FOX D, KAUTZ H. Extracting places and activities from GPS traces using hierarchical conditional random fields[J]. International journal of robotics re￾search, 2007, 26(1): 119–134. [13] [14] 李毓瑞, 陈红梅, 王丽珍, 等. 基于密度的停留点识别方 第 1 期 陆剑锋，等：基于时空约束密度聚类的停留点识别方法 ·65·