DP-BPR: Destination prediction based on Bayesian personalized ranking

Abstract

Destination prediction has attracted widespread attention because it can help vehicle-aid systems recommend related services in advance to improve user driving experience. However, the relevant research is mainly based on driving trajectory of vehicles to predict the destinations, which is challenging to achieve the early destination prediction. To this end, we propose a model of early destination prediction, DP-BPR, to predict the destinations by users’ travel time and locations. There are three challenges to accomplish the model: 1) the extremely sparse historical data make it challenge to predict destinations directly from raw historical data; 2) the destinations are related to not only departure points but also departure time so that both of them should be taken into consideration in prediction; 3) how to learn destination preferences from historical data. To deal with these challenges, we map sparse high-dimensional data to a dense low-dimensional space through embedding learning using deep neural networks. We learn the embeddings not only for users but also for locations and time under the supervision of historical data, and then use Bayesian personalized ranking (BPR) to learn to rank destinations. Experimental results on the Zebra dataset show the effectiveness of DP-BPR.

Keywords

destination prediction / embedding learning / top-N prediction / Bayesian personalized ranking

References

[1] DashM, KooK K, KrishnaswamyS P, JinY, Shi-NashA. Visualize people’s mobility-both individually and collectively-using mobile phone cellular data [C]. IEEE International Conference on Mobile Data Management. IEEE, 2016, 1: 341-344

[2] de BRÉBISSON A, SIMON É, AUVOLAT A, VINCENT P, BENGIO Y. Artificial neural networks applied to taxi destination prediction [EB/OL]. 2015: arXiv: 1508.00021 [cs.LG]. https://arxiv.org/abs/1508.00021. DOI: https://doi.org/10.13140/RG.2.2.20264.26888.

[3] KeY-BTravel destination prediction based on deep learning and regression classification model [D], 2018, Hangzhou, Zhejiang University(in Chinese)

[4] HeY-NTravel destination prediction based on Markov model [D], 2017, Changchun, Jilin University(in Chinese)

[5] LvJ-m, SunQ-h, LiQ, Moreira-MatiasL. Multi-scale and multi-scope convolutional neural networks for destination prediction of trajectories [J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(8): 3184-3195

[6] XuJ-j, ZhaoJ, ZhouR, LiuC-f, ZhaoP-p, ZhaoL. Destination prediction a deep learningbased approach [J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 33(2): 651-666

[7] ZhangL-y, HuT, MinY, WuG-b, ZhangJ-y, FengP-c, GongP-h, YeJ-PA taxi order dispatch model based on combinatorial optimization [C], 2017, New York, NY, USA, ACM, 21512159

[8] ZongF, TianY-d, HeY-n, TangJ-j, LvJ-Y. Trip destination prediction based on multi-day GPS data [J]. Physica A: Statistical Mechanics and its Applications, 2019, 515: 258-269

[9] BesseP C, GuillouetB, LoubesJ M, RoyerF. Destination prediction by trajectory distribution-based model [J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 19(8): 2470-2481

[10] GaoJ-x, JuanZ-c, NiA-N. Modeling and application of traveler destination selection behavior based on Bayesian network [J]. Journal of System& Management, 2015, 24(1): 32-37

[11] LiuR-HResearch on user behavior analysis based on vehicle trajectory data [D], 2019, Beijing, University of Chinese Academy of Sciences(in Chinese)

[12] ZhouL-TResearch on the destination prediction algorithm based on the historical traveling track [D], 2015, Guangzhou, South China University of Technology(in Chinese)

[13] ZhouX-YResearch on traveling destination prediction technology based on multi-scale convolution neural network [D], 2019, Beijing, Beijing University of Posts and Telecommunications(in Chinese)

[14] ZhangX-c, ZhaoZ-x, ZhengY, LiJ-Y. Prediction of taxi destinations using a novel data embedding method and ensemble learning [J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 21(1): 68-78

[15] JIANG Jian, LIN Fei, FAN Jin, LV Hang, WU Jia. A destination prediction network based on spatiotemporal data for bike-sharing [J]. Complexity, 2019: 7643905. DOI: https://doi.org/10.1155/2019/7643905.

[16] LiuY, JiaR, XieX, LiuZ-Y. A two-stage destination prediction framework of shared bicycles based on geographical position recommendation[J]. IEEE Intelligent Transportation Systems Magazine, 2018, 11(1): 42-47

[17] LiW-t, GaoM, LiH, XiongQ-y, WenJ-h, LingB. A shilling attack detection algorithm based on the feature of popularity classification [J]. Acta Automatica Sinica, 2015, 41(9): 1563-1576

[18] ZhouT, HanX-p, YanX-y, YangZ-m, ZhaoZ-d, WangB-H. Statistical mechanics of time and space characteristics of human behavior [J]. Journal of University of Electronic Science and Technology of China, 2013, 42(4): 481-540

[19] WangX, LuW, EsterM, WangC, ChenC. Social recommendation with strong and weak ties [C]. Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 2016, New York, NY, USA, ACM, 514

[20] ZhaoT, McauleyJ, KingILeveraging social connections to improve personalized ranking for collaborative filtering [C], 2014, New York, ACM Press, 261270

[21] WangL, YuZ-w, GuoB, KuT, YiF. Moving destination prediction using sparse dataset [J]. ACM Transactions on Knowledge Discovery from Data, 2017, 11(3): 1-33

[22] DC competition [EB/OL]. https://www.pkbigdata.com/common/bbs/topicDetails.html?tid=2949.

[23] TangJ-x, WangK. Personalized top-N sequential recommendation via convolutional sequence embedding [C]. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining-WSDM’18, 2018, New York, NY, ACM Press, 565573

[24] ZhangS-c, LiX-l, ZongM, ZhuX-f, WangR-L. Efficient KNN classification with different numbers of nearest neighbors [J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 29(5): 1774-1785

[25] Breimanl. Random forests [J]. Machine Learning, 2001, 45(1): 5-32

[26] HWANG C S, KAO Y C, YU Ping. Integrating multiple linear regression and multicriteria collaborative filtering for better recommendation [C]// 2010 International Conference on Computational Aspects of Social Networks. IEEE, 2010: 229–232. DOI: https://doi.org/10.1109/CASoN.2010.59.

[27] LiuL-b, QiuZ-l, LiG-b, WangQ, OuyangW-l, LinL. Contextualized spatial-temporal network for taxi origin-destination demand prediction [J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(10): 3875-3887

[28] TopalliI, KilincS. Modelling user habits and providing recommendations based on the hybrid broadcast broadband television using neural networks [J]. IEEE Transactions on Consumer Electronics, 2016, 62(2): 182-190