Trajectory prediction enhanced by geographic knowledge graph and multi-spatio temporal constraints

doi:10.11947/j.AGCS.2024.20230571.

Abstract

Abstract:

Trajectory prediction methods based on machine learning typically rely on the quantity and quality of historical trajectories. But social media check-in data has a low update frequency, that would lead to difficulties in learning and overfitting during trajectory prediction. To overcome the difficulty of low-quality trajectories data in prediction tasks, we propose a trajectory prediction method enhanced by geographic knowledge graph and multi-spatio temporal constraints. The proposed model transforms complex and heterogeneous multi-source geographic information into a geographic knowledge graph composed of several triples for unified expression, and mines entity associations through knowledge embedding models to enhance the feature representation of trajectories. At the same time, the model utilizes a multi-head self-attention with multi-spatio temporal constraints to extract multiple features from check-in trajectories. The proposed model is validated on Foursquare social media check-in data from New York. It's shown in experiment results that proposed model has improved to varying degrees in hit rate (HR) and mean reciprocal rank (MRR) evaluation indicators, comparing with other representation learning methods and prediction models. The result indicate that the proposed model can effectively enhance the representation of check-in trajectories, extract multiple temporal features of trajectories, and improve the prediction accuracy of social media user check-in trajectories.

Key words: trajectory prediction, multi-source geographic information, social media, geographic knowledge graph, multi-spatio temporal constraints

CLC Number:

P208

Jia LI, Jing LI, Haiyan LIU, Chuanwei LU, Xiaohui CHEN, Junnan LIU, Wen SHI. Trajectory prediction enhanced by geographic knowledge graph and multi-spatio temporal constraints[J]. Acta Geodaetica et Cartographica Sinica, 2024, 53(10): 2021-2033.

Figures/Tables 16

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Tab.1

Tab.2

Tab.3

Tab.4

Tab.5

Tab.6

Fig.8

Tab.7

Fig.9

References 47

[1]	BARABÁSI A L. The origin of bursts and heavy tails in human dynamics[J]. Nature, 2005, 435(7039):207-211.
[2]	BROCKMANN D, HUFNAGEL L, GEISEL T. The scaling laws of human travel[J]. Nature, 2006, 439(7075):462-465.
[3]	SONG Chaoming, QU Zehui, BLUMM N, et al. Limits of predictability in human mobility[J]. Science, 2010, 327(5968):1018-1021.
[4]	李静, 刘海砚, 郭文月, 等. 基于深度学习的人群活动流量时空预测模型[J]. 测绘学报, 2021, 50(4):522-531. DOI:. doi: 10.11947/j.AGCS.2021.20200230
	LI Jing, LIU Haiyan, GUO Wenyue, et al. A spatio-temporal network for human activity prediction based on deep learning[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(4):522-531. DOI:. doi: 10.11947/j.AGCS.2021.20200230
[5]	ZHANG Junbo, ZHENG Yu, QI Dekang. Deep spatio-temporal residual networks for citywide crowd flows prediction[C]//Proceedings of 2017 AAAI Conference on Artificial Intelligence. San Francisco: AAAI Press, 2017: 1655-1661.
[6]	郭旦怀, 张鸣珂, 贾楠, 等. 融合深度学习技术的用户兴趣点推荐研究综述[J]. 武汉大学学报(信息科学版), 2020, 45(12):1890-1902.
	GUO Danhuai, ZHANG Mingke, JIA Nan, et al. Survey of point-of-interest recommendation research fused with deep learning[J]. Geomatics and Information Science of Wuhan University, 2020, 45(12):1890-1902.
[7]	ZHANG Jiawei, QI Hua. Data mining and spatial analysis of social media text based on the BERT-CNN model to achieve situational awareness: a case study of COVID-19[J]. Journal of Geodesy and Geoinformation Science, 2022, 5(2):38-48.
[8]	HE Zhengbing, QI Geqi, LU Lili, et al. Network-wide identification of turn-level intersection congestion using only low-frequency probe vehicle data[J]. Transportation Research Part C: Emerging Technologies, 2019, 108:320-339.
[9]	朱秋圳, 邬群勇, 姚铖鑫, 等. 基于DBI和稀疏轨迹数据的交通状态精细划分与识别[J]. 地球信息科学学报, 2022, 24(3):458-468.
	ZHU Qiuzhen, WU Qunyong, YAO Chengxin, et al. Fine classification and identification of traffic states based on DBI and sparse tra-jectory data[J]. Journal of Geo-information Science, 2022, 24(3):458-468.
[10]	CHENG Chen, YANG Haiqin, KING I, et al. Fused matrix factorization with geographical and social influence in location-based social networks[C]//Proceedings of 2012 AAAI Conference on Artificial Intelligence. Toronto: AAAI Press, 2012: 17-23.
[11]	GIANNOTTI F, NANNI M, PINELLI F, et al. Trajectory pattern mining[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose: ACM Press, 2007: 330-339.
[12]	MATHEW W, RAPOSO R, MARTINS B. Predicting future locations with hidden Markov models[C]//Proceedings of the 2012 ACM Conference on Ubiquitous Computing. New York: ACM Press, 2012: 911-918.
[13]	YE Jihang, ZHU Zhe, CHENG Hong. What's your next move: user activity prediction in location-based social networks[C]//Procee-dings of 2013 SIAM International Conference on Data Mining. Philadelphia: Society for Industrial and Applied Mathematics, 2013: 171-179.
[14]	ZHANG Jiadong, CHOW C Y, LI Yanhua. LORE: exploiting sequential influence for location recommendations[C]//Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Dallas: ACM Press, 2014: 103-112.
[15]	LIU Qiang, WU Shu, WANG Liang, et al. Predicting the next location: a recurrent model with spatial and temporal contexts[C]//Proceedings of 2016 AAAI Conference on Artificial Intelligence. Phoenix: AAAI Press, 2016.
[16]	SUN Ke, QIAN Tieyun, CHEN Tong, et al. Where to go next: modeling long- and short-term user preferences for point-of-interest recommendation[C]//Proceedings of 2020 AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2020: 214-221.
[17]	WU Yuxia, LI Ke, ZHAO Guoshuai, et al. Personalized long- and short-term preference learning for next POI recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(4):1944-1957.
[18]	FENG Jie, LI Yong, ZHANG Chao, et al. DeepMove: predicting human mobility with attentional recurrent networks[C]//Proceedings of 2018 World Wide Web Conference on World Wide Web. Lyon: ACM Press, 2018: 1459-1468.
[19]	ZHAO Pengpeng, LUO Anjing, LIU Yanchi, et al. Where to go next: a spatio-temporal gated network for next POI recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(5):2512-2524.
[20]	YANG Song, LIU Jiamou, ZHAO Kaiqi. GETNext: trajectory flow map enhanced transformer for next POI recommendation[C]//Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. Madrid: ACM Press, 2022: 1144-1153.
[21]	刘纪平, 张志然, 杨超伟, 等. 城市街区和签到数据结合的个性化城市兴趣区域推荐方法[J]. 测绘学报, 2022, 51(8):1797-1806. DOI:. doi: 10.11947/j.AGCS.2022.20210094
	LIU Jiping, ZHANG Zhiran, YANG Chaowei, et al. Personalized city region of interests recommendation method based on city block and check-in data[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(8):1797-1806. DOI:. doi: 10.11947/j.AGCS.2022.20210094
[22]	段晓旗, 张彤, 田有亮, 等. 居民出行异质性与城市活动结构[J]. 测绘学报, 2023, 52(1):155-166. DOI:. doi: 10.11947/j.AGCS.2023.20210368
	DUAN Xiaoqi, ZHANG Tong, TIAN Youliang, et al. Residents' travel heterogeneity and urban mobility structure[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(1):155-166. DOI:. doi: 10.11947/j.AGCS.2023.20210368
[23]	BENGIO Y, COURVILLE A, VINCENT P. Representation learning: a review and new perspectives[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(8):1798-1828.
[24]	曹翰林, 唐海娜, 王飞, 等. 轨迹表示学习技术研究进展[J]. 软件学报, 2021, 32(5):1461-1479.
	CAO Hanlin, TANG Haina, WANG Fei, et al. Survey on trajectory representation learning techniques[J]. Journal of Software, 2021, 32(5):1461-1479.
[25]	LIU Xin, LIU Yong, LI Xiaoli. Exploring the context of locations for personalized location recommendations[C]//Proceedings of the 25th International Joint Conference on Artificial Intelligence. New York: AAAI Press, 2016: 1188-1194.
[26]	YAN Bo, JANOWICZ K, MAI Gengchen, et al. From ITDL to Place2Vec: reasoning about place type similarity and relatedness by learning embeddings from augmented spatial contexts[C]//Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Redondo Beach: ACM Press, 2017: 1-10.
[27]	FENG Shanshan, CONG Gao, AN Bo, et al. POI2Vec: geographical latent representation for predicting future visitors[C]//Procee-dings of the 31st AAAI Conference on Artificial Intelligence. San Francisco: AAAI Press, 2017: 102-108.
[28]	YUAN Quan, CONG Gao, SUN Aixin. Graph-based point-of-interest recommendation with geographical and temporal influences[C]//Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. Shanghai: ACM Press, 2014: 659-668.
[29]	刘真, 王娜娜, 王晓东, 等. 位置社交网络中谱嵌入增强的兴趣点推荐算法[J]. 通信学报, 2020, 41(3):197-206.
	LIU Zhen, WANG Nana, WANG Xiaodong, et al. Spectral clustering and embedding-enhanced POI recommendation in location-based social network[J]. Journal on Communications, 2020, 41(3):197-206.
[30]	LI Yang, CHEN Tong, LUO Yadan, et al. Discovering collaborative signals for next POI recommendation with iterative Seq2Graph augmentation[C]//Proceedings of 2021 International Joint Conference on Artificial Intelligence. Montreal: International Joint Conferences on Artificial Intelligence Organization, 2021.
[31]	XIE Min, YIN Hongzhi, WANG Hao, et al. Learning graph-based POI embedding for location-based recommendation[C]//Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. Indianapolis: ACM Press, 2016: 15-24.
[32]	方金凤, 孟祥福. 基于LBSN和多图融合的兴趣点推荐[J]. 测绘学报, 2022, 51(5):739-749. DOI:. doi: 10.11947/j.AGCS.2022.20210156
	FANG Jinfeng, MENG Xiangfu. POI recommendation based on LBSN and multi-graph fusion[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(5):739-749. DOI:. doi: 10.11947/j.AGCS.2022.20210156
[33]	QIN Yifang, WANG Yifan, SUN Fang, et al. DisenPOI: disentangling sequential and geographical influence for point-of-interest recommendation[C]//Proceedings of the 16th ACM International Conference on Web Search and Data Mining. Singapore: ACM Press, 2023: 508-516.
[34]	QIN Yifang, WU Hongjun, JU Wei, et al. A diffusion model for POI recommendation[J]. ACM Transactions on Information Systems, 2024, 42(2):1-27.
[35]	陆锋, 余丽, 仇培元. 论地理知识图谱[J]. 地球信息科学学报, 2017, 19(6):723-734.
	LU Feng, YU Li, QIU Peiyuan. On geographic knowledge graph[J]. Journal of Geo-Information Science, 2017, 19(6):723-734.
[36]	刘知远, 孙茂松, 林衍凯, 等. 知识表示学习研究进展[J]. 计算机研究与发展, 2016, 53(2):247-261.
	LIU Zhiyuan, SUN Maosong, LIN Yankai, et al. Knowledge representation learning: a review[J]. Journal of Computer Research and Development, 2016, 53(2):247-261.
[37]	刘俊楠, 刘海砚, 陈晓慧, 等. 基于地理空间数据的知识图谱构建技术研究[J]. 中文信息学报, 2020, 34(11):29-36.
	LIU Junnan, LIU Haiyan, CHEN Xiaohui, et al. Construction of knowledge graph based on geo-spatial data[J]. Journal of Chinese Information Processing, 2020, 34(11):29-36.
[38]	LI Jing, LIU Haiyan, LI Jia, et al. A knowledge-based approach for estimating the distribution of urban mixed land use[J]. International Journal of Digital Earth, 2023, 16(1):965-987.
[39]	VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]//Proceedings of the 31st Conference on Neural Information Processing Systems. Red Hook: Curran Associates Inc., 2017: 6000-6010.
[40]	CURL J S. A dictionary of architecture and landscape architecture[M]. 2nd ed. Oxford: Oxford University Press, 2006.
[41]	BORDES A, USUNIER N, GARCIA-DURÁN A, et al. Translating embeddings for modeling multi-relational data[C]//Proceedings of the 26th International Conference on Neural Information Processing Systems. Red Hook: Curran Associates Inc., 2013: 2787-2795.
[42]	LIN Yankai, LIU Zhiyuan, SUN Maosong, et al. Learning entity and relation embeddings for knowledge graph completion[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence. Austin: AAAI Press, 2015: 2181-2187.
[43]	KAZEMI S M, GOEL R, EGHBALI S, et al. Time2Vec: learning a vector representation of time[EB/OL]. [2023-11-12]. https://arxiv.org/abs/1907.05321v.
[44]	TANG Gongbo, MÜLLER M, RIOS A, et al. Why self-attention? A targeted evaluation of neural machine translation architectures[C]//Proceedings of 2018 Conference on Empirical Methods in Natural Language Processing. Stroudsburg: Association for Computational Linguistics, 2018.
[45]	YANG Dingqi, QU Bingqing, YANG Jie, et al. Revisiting user mobility and social relationships in LBSNs: a hypergraph embedding approach[C]//Proceedings of 2019 World Wide Web Conference. San Francisco: ACM Press, 2019: 2147-2157.
[46]	HAKLAY M, WEBER P. OpenStreetMap: user-generated street maps[J]. IEEE Pervasive Computing, 2008, 7(4):12-18.
[47]	CUI Qiang, ZHANG Chenrui, ZHANG Yafeng, et al. ST-PIL: spatial-temporal periodic interest learning for next point-of-interest recommendation[C]//Proceedings of the 30th ACM International Conference on Information & Knowledge Management. Queensland: ACM Press, 2021: 2960-2964.

距离/km	HR@1/(%)	HR@5/(%)	HR@10/(%)	HR@20/(%)	MRR/(%)
0.5	22.28	41.81	48.63	53.48	31.17
1	24.66	44.17	50.44	55.44	33.51
2	23.79	42.35	48.47	53.76	32.33
3	23.60	41.94	47.87	52.46	31.72

维度	HR@1/(%)	HR@5/(%)	HR@10/(%)	HR@20/(%)	MRR/(%)
16	18.44	37.84	44.21	50.28	28.48
32	22.42	41.35	48.12	52.90	30.88
64	24.66	44.17	50.44	55.44	33.51
128	22.63	42.46	48.54	53.95	31.53

表示学习方法	约束条件	HR@1	HR@5	HR@10	HR@20	MRR
One-hot	Transformer	13.43	28.10	32.45	35.73	19.56
Word2vec		13.48	29.42	33.52	36.68	20.95
Geohash		19.47	40.07	46.69	50.62	29.19
TransE		22.38	40.97	48.27	53.08	31.05
TransR		23.82	43.24	49.22	53.43	32.41
One-hot	Transformer⁺	15.59	29.21	33.91	37.43	21.90
Word2vec		16.66	31.41	35.78	40.40	23.41
Geohash		20.34	41.37	47.89	52.16	29.78
TransE		22.72	42.01	48.92	53.87	31.81
TransR		24.66	44.17	50.44	55.44	33.51

约束条件	HR@1	HR@5	HR@10	HR@20	MRR
去除类别	24.03	43.33	49.54	53.58	32.47
去除时间	24.36	43.89	49.96	54.41	32.80
去除街区	23.92	43.68	49.77	53.63	32.52

模型	HR@1	HR@5	HR@10	HR@20	MRR
ST-RNN	13.44	27.34	30.72	32.78	20.23
DeepMove	15.78	28.47	31.85	33.95	21.44
PLSPL	15.38	38.24	45.63	52.16	25.82
GETNext	19.39	38.95	47.53	53.06	28.05
本文方法	24.66	44.17	50.44	55.44	33.51