A dual-threshold stay point detection method based on adaptive extended density peak clustering for sparse fixed-point trajectories

doi:10.11947/j.AGCS.2026.20250284

Abstract

Abstract:

Stay point detection serves as a critical preliminary step in trajectory data mining, providing essential support for related research such as point-of-interest mining and movement pattern classification. However, traditional detection methods are typically designed for dense trajectories, such as GPS data, and struggle to address the challenges posed by sparse fixed-point trajectories like those from traffic checkpoints or mobile signaling data. These challenges include insufficient feature extraction and threshold estimation biases due to uneven data density and complex distribution patterns. To tackle these issues, we propose a dual-threshold stay point detection method based on adaptive expanded density peak clustering (AE-DPC) for sparse fixed-point trajectories. First, global thresholds are derived from overall data characteristics to preliminarily identify candidate stay points. Then, local thresholds are further refined based on the clustering results of AE-DPC, which constructs initial clusters by considering neighborhood relationships and improved density peaks, followed by cluster expansion and merging to enhance clustering performance. Finally, the integration of global and local thresholds enables precise stay point detection. Experiments were conducted on both open-source synthetic datasets and real-world sparse fixed-point trajectory datasets to evaluate AE-DPC and the dual-threshold method, respectively. The results demonstrate that AE-DPC significantly outperforms comparative algorithms (such as DBSCAN, HDBSCAN, and SNN-DPC) in terms of the adjusted rand index (ARI) and adjusted mutual information (AMI). Moreover, the dual-threshold method leveraging AE-DPC-based local thresholds shows superior performance in real-world stay point detection tasks, achieving improvements in precision of 14.10% and 9.88% compared to the local threshold method based on HDBSCAN and the dynamic threshold approach, respectively.

Key words: stay point detection, sparse fixed-point trajectory, clustering algorithm, density peak

CLC Number:

P208

Junhao GUO, Mingzhi WU, Peixiao WANG, Hengcai ZHANG. A dual-threshold stay point detection method based on adaptive extended density peak clustering for sparse fixed-point trajectories[J]. Acta Geodaetica et Cartographica Sinica, 2026, 55(2): 249-260.

Figures/Tables 16

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Tab. 1

Tab. 2

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Tab. 3

Tab. 4

Fig. 11

Fig. 12

References 28

[1]	李婷, 裴韬, 袁烨城, 等. 人类活动轨迹的分类、模式和应用研究综述[J]. 地理科学进展, 2014, 33(7): 938-948.
	LI Ting, PEI Tao, YUAN Yecheng, et al. A review on the classification, patterns and applied research of human mobility trajectory[J]. Progress in Geography, 2014, 33(7): 938-948.
[2]	代维秀, 陈占龙, 谢鹏. 居民出行与轨迹行为交互模式挖掘与关联技术[J]. 测绘学报, 2021, 50(4): 532-543. DOI: . doi: 10.11947/j.AGCS.2021.20200072
	DAI Weixiu, CHEN Zhanlong, XIE Peng. Research on the interactive mode of residents' behavior based on trajectory data mining[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(4): 532-543. DOI: . doi: 10.11947/j.AGCS.2021.20200072
[3]	王培晓, 张恒才, 张岩, 等. 地理空间智能预测研究进展与发展趋势[J]. 地球信息科学学报, 2025, 27(1): 60-82.
	WANG Peixiao, ZHANG Hengcai, ZHANG Yan, et al. GeoAI-driven spatiotemporal prediction: progress and prospects[J]. Journal of Geo-information Science, 2025, 27(1): 60-82.
[4]	HWANG S, VANDEMARK C, DHATT N, et al. Segmenting human trajectory data by movement states while addressing signal loss and signal noise[J]. International Journal of Geographical Information Science, 2018, 32(7): 1391-1412.
[5]	ZHANG Weiqi, XIE Zhenzhen, VERA VENKATA SAI A M, et al. A local differential privacy trajectory protection method based on temporal and spatial restrictions for staying detection[J]. Tsinghua Science and Technology, 2024, 29(2): 617-633.
[6]	张宽, 赵卓峰, 郭炜强. 一种面向定点轨迹数据的行程识别方法[J]. 北京邮电大学学报, 2020, 43(4): 39-47.
	ZHANG Kuan, ZHAO Zhuofeng, GUO Weiqiang. Travel recognition method for fixed-point trajectory data[J]. Journal of Beijing University of Posts and Telecommunications, 2020, 43(4): 39-47.
[7]	YANG Yitao, JIA Bin, YAN Xiaoyong, et al. Identifying intracity freight trip ends from heavy truck GPS trajectories[J]. Transportation Research Part C: Emerging Technologies, 2022, 136: 103564.
[8]	ZHANG Bin, WANG Qiuxia, LI Jing, et al. Spatial-temporal grid clustering method based on frequent stay point recognition[J]. Neural Computing and Applications, 2022, 34(12): 9247-9255.
[9]	陆剑锋, 郭茂祖, 张昱, 等. 基于时空约束密度聚类的停留点识别方法[J]. 智能系统学报, 2020, 15(1): 59-66.
	LU Jianfeng, GUO Maozu, ZHANG Yu, et al. Stay point recognition method based on spatio-temporal constraint density clustering[J]. CAAI Transactions on Intelligent Systems, 2020, 15(1): 59-66.
[10]	姜晓红, 陈庆炜, 严亚丹, 等. 基于规则判别的末端配送停留点识别与出行链特征[J]. 交通运输系统工程与信息, 2024, 24(6): 232-241.
	JIANG Xiaohong, CHEN Qingwei, YAN Yadan, et al. Rule-based discriminative identification and travel chain characterization of last-mile delivery stops[J]. Journal of Transportation Systems Engineering and Information Technology, 2024, 24(6): 232-241.
[11]	QIAN Jiaxin, ZHOU You, HAN Xuming, et al. MDBSCAN: a multi-density DBSCAN based on relative density[J]. Neurocomputing, 2024, 576: 127329.
[12]	吴笛, 杜云艳, 易嘉伟, 等. 基于密度的轨迹时空聚类分析[J]. 地球信息科学学报, 2015, 17(10): 1162-1171.
	WU Di, DU Yunyan, YI Jiawei, et al. Density-based spatiotemporal clustering analysis of trajectories[J]. Journal of Geo-information Science, 2015, 17(10): 1162-1171.
[13]	周洋, 杨超. 基于时空聚类算法的轨迹停驻点识别研究[J]. 交通运输系统工程与信息, 2018, 18(4): 88-95.
	ZHOU Yang, YANG Chao. Anchors identification in trajectory based on temporospatial clustering algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(4): 88-95.
[14]	王培晓, 张恒才, 王海波, 等. ST-CFSFDP：快速搜索密度峰值的时空聚类算法[J]. 测绘学报, 2019, 48(11): 1380-1390. DOI: . doi: 10.11947/j.AGCS.2019.20180538
	WANG Peixiao, ZHANG Hengcai, WANG Haibo, et al. Spatial-temporal clustering by fast search and find of density peaks[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1380-1390. DOI: . doi: 10.11947/j.AGCS.2019.20180538
[15]	GONG Lei, YAMAMOTO T, MORIKAWA T. Identification of activity stop locations in GPS trajectories by DBSCAN-TE method combined with support vector machines[J]. Transportation Research Procedia, 2018, 32: 146-154.
[16]	徐晓, 丁世飞, 丁玲. 密度峰值聚类算法研究进展[J]. 软件学报, 2022, 33(5): 1800-1816.
	XU Xiao, DING Shifei, DING Ling. Survey on density peaks clustering algorithm[J]. Journal of Software, 2022, 33(5): 1800-1816.
[17]	白璐, 赵鑫, 孔钰婷, 等. 谱聚类算法研究综述[J]. 计算机工程与应用, 2021, 57(14): 15-26.
	BAI Lu, ZHAO Xin, KONG Yuting, et al. Survey of spectral clustering algorithms[J]. Computer Engineering and Applications, 2021, 57(14): 15-26.
[18]	YU Fudan, AO Wenxuan, YAN Huan, et al. Spatio-temporal vehicle trajectory recovery on road network based on traffic camera video data[C]//Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2022: 4413-4421.
[19]	TRAN L H, DANG T K, THOAI N. Hybrid stop discovery in trajectory records[C]//Proceedings of 2013 International Workshop on Database and Expert Systems Applications. Los Alamitos: IEEE, 2013: 9-14.
[20]	吕莉, 陈威, 肖人彬, 等. 面向密度分布不均数据的加权逆近邻密度峰值聚类算法[J]. 智能系统学报, 2024, 19(1): 165-175.
	LÜ Li, CHEN Wei, XIAO Renbin, et al. Density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets[J]. CAAI Transactions on Intelligent Systems, 2024, 19(1): 165-175.
[21]	PENG Ju, TANG Jianbo, DENG Min, et al. A two-stage method for detecting trajectory clusters of different densities with peak trajectories identification[J]. International Journal of Geographical Information Science, 2025, 39(10): 2177-2210.
[22]	RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[23]	ZANG Wenke, CHE Jing, MA Linlin, et al. Density peaks clustering based on density voting and neighborhood diffusion[J]. Information Sciences, 2024, 681: 121209.
[24]	陈梅, 魏礼磊, 尤远毓秀, 等. 基于k近邻图的密度峰值聚类算法[J]. 控制与决策, 2025, 40(7): 2242-2250.
	CHEN Mei, WEI Lilei, YOU Yuanyuxiu, et al. Density peaks clustering algorithm based on k-nearest neighbor graph[J]. Control and Decision, 2025, 40(7): 2242-2250.
[25]	ZHAO Jia, WANG Gang, PAN J S, et al. Density peaks clustering algorithm based on fuzzy and weighted shared neighbor for uneven density datasets[J]. Pattern Recognition, 2023, 139: 109406.
[26]	MOULAVI D, JASKOWIAK P A, CAMPELLO R J G B, et al. Density-based clustering validation[C]//Proceedings of 2014 SIAM International Conference on Data Mining. Philadelphia: Society for Industrial and Applied Mathematics, 2014: 839-847.
[27]	LIU Rui, WANG Hong, YU Xiaomei. Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J]. Information Sciences, 2018, 450: 200-226.
[28]	JU Hengrong, LU Yang, DING Weiping, et al. Three-way evidence theory-based density peak clustering with the principle of justifiable granularity[J]. Applied Soft Computing, 2024, 152: 111217.

数据集	样本数	特征数	簇数
Spiral	312	2	3
Ring	500	2	2
Ls3	1741	2	6
Compound	399	2	6
Jain	373	2	2
Jain2	500	2	4

数据集	算法	ARI	AMI	Arg-
Spiral	DBSCAN	1.000	1.000	0.05/3
	HDBSCAN	1.000	1.000	17/2
	SC	1.000	1.000	3/5
	OPTICS	1.000	1.000	4/0.12
	SNN-DPC	1.000	1.000	4/3
	3W-PEDP	1.000	1.000	3
	AE-DPC	1.000	1.000	10/31
Ring	DBSCAN	1.000	1.000	0.16/3
	HDBSCAN	1.000	1.000	2/3
	SC	1.000	1.000	2/8
	OPTICS	1.000	1.000	7/0.08
	SNN-DPC	1.000	1.000	3/2
	3W-PEDP	0.670	0.718	4
	AE-DPC	1.000	1.000	10/50
Ls3	DBSCAN	1.000	1.000	0.05/11
	HDBSCAN	1.000	1.000	9/1
	SC	1.000	1.000	6/25
	OPTICS	0.959	0.950	6/0.03
	SNN-DPC	0.719	0.807	70/6
	3W-PEDP	0.494	0.688	6
	AE-DPC	1.000	1.000	41/174
Compound	DBSCAN	0.949	0.908	0.05/3
	HDBSCAN	0.909	0.896	2/3
	SC	0.804	0.853	4/13
	OPTICS	0.882	0.864	6/0.05
	SNN-DPC	0.875	0.854	3/10
	3W-PEDP	0.820	0.821	6
	AE-DPC	0.969	0.933	9/21
Jain	DBSCAN	0.976	0.865	0.08/2
	HDBSCAN	0.976	0.934	20/2
	SC	1.000	1.000	2/9
	OPTICS	0.976	0.922	4/0.08
	SNN-DPC	0.811	0.832	2/3
	3W-PEDP	0.444	0.601	3
	AE-DPC	1.000	1.000	16/37
Jain2	DBSCAN	0.725	0.814	0.06/5
	HDBSCAN	0.871	0.838	5/4
	SC	0.705	0.688	4/47
	OPTICS	0.799	0.788	9/0.06
	SNN-DPC	0.927	0.921	7/4
	3W-PEDP	0.826	0.838	5
	AE-DPC	0.930	0.913	13/49

车辆	记录时间	监测设备	距离/m	时间/s	速度/（m/s）	簇	簇时间/s	簇速度/（m/s）	标签	结果	簇H	簇D
5f0^**	16：35：36	435^**	0	33	0	2059	600	5.44	－1	0	225	d3
5f0^**	17：26：10	484^**	3799	3034	1.25	4901	1833	5.21	2	2	825	d3
5f0^**	18：57：16	471^**	1421	5466	0.26	1095	2731	5.91	2	2	828	e3
5f0^**	18：58：17	459^**	8	61	0.13	1095	2731	5.91	0	0	828	e3
5f0^**	19：24：10	494^**	11 438	1553	7.367	1095	2731	5.91	1	0	-	f5
13f^**	15：37：31	441^**	0	0	0	1222	764	6.54	－1	0	311	d4
13f^**	15：37：36	441^**	0	5	0	1222	764	6.54	0	0	311	d4
13f^**	15：53：31	455^**	1335	955	1.39	2104	700	6.38	2	2	-	d4
13f^**	15：54：01	456^**	396	30	13.22	2104	700	6.38	0	0	-	d4
13f^**	15：54：23	410^**	181	22	8.26	2104	700	6.38	0	0	368	d4
13f^**	16：05：24	499^**	1831	661	2.77	2307	892	3.99	1	0	369	d4

识别方法	查准率	查全率
本文方法	0.89	0.83
基于HDBSCAN的局部阈值法	0.78	0.71
动态阈值法	0.81	0.82