Self-driving tour route mining based on sparse trajectory clustering
YANG Fengyi1,2,3, MA Yupeng1,3, BAO Hengbin1,2,3, HAN Yunfei1,3, MA Bo1,2,3
1. The Xinjiang Technical Institute of Physics & Chemistry, Chinese Academy of Sciences, Urumqi Xinjiang 830011, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China; 3. Xinjiang Laboratory of Minority Speech and Language Information Processing, Urumqi Xinjiang 830011, China
Abstract:Aiming at the difficulty of constructing real tour routes from sparse refueling trajectories of self-driving tourists,a sparse trajectory clustering algorithm based on semantic representation was proposed to mine popular self-driving tour routes. Different from traditional trajectory clustering algorithms based on trajectory point matching,in this algorithm, the semantic relationships between different trajectory points were considered and the low-dimensional vector representation of the trajectory was learned. Firstly,the neural network language model was used to learn the distributed vector representation of the gas stations. Then,the average value of all the station vectors in each trajectory was taken as the vector representation of this trajectory. Finally,the classical k-means algorithm was used to cluster the trajectory vectors. The final visualization results show that the proposed algorithm mines two popular self-driving tour routes effectively.
杨奉毅, 马玉鹏, 包恒彬, 韩云飞, 马博. 基于稀疏轨迹聚类的自驾车旅游路线挖掘[J]. 计算机应用, 2020, 40(4): 1079-1084.
YANG Fengyi, MA Yupeng, BAO Hengbin, HAN Yunfei, MA Bo. Self-driving tour route mining based on sparse trajectory clustering. Journal of Computer Applications, 2020, 40(4): 1079-1084.
[1] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]//Proceedings of the 2013 Conference on Neural Information Processing Systems. Cambridge:MIT Press,2013:3111-3119. [2] 常亮, 孙文平, 张伟涛, 等. 旅游路线规划研究综述[J]. 智能系统学报,2019,14(1):82-92.(CHANG L,SUN W P,ZHANG W T,et al. Review of tourism route planning[J]. CAAI Transactions on Intelligent Systems,2019,14(1):82-92.) [3] ZHENG Y,ZHANG L,MA Z,et al. Recommending friends and locations based on individual location history[J]. ACM Transactions on the Web,2011,5(1):No. 5. [4] ZHENG Y,ZHANG L,XIE X,et al. Mining interesting locations and travel sequences from GPS trajectories[C]//Proceedings of the 18th International Conference on World Wide Web. New York:ACM,2009:791-800. [5] ZHENG V W,ZHENG Y,XIE X,et al. Collaborative location and activity recommendations with GPS history data[C]//Proceedings of the 19th International Conference on World Wide Web. New York:ACM,2010:1029-1038. [6] CUI G,LUO J,WANG X. Personalized travel route recommendation using collaborative filtering based on GPS trajectories[J]. International Journal of Digital Earth,2018,11(3):284-307. [7] JIANG S,QIAN X,SHEN J,et al. Author topic model-based collaborative filtering for personalized POI recommendations[J]. IEEE Transactions on Multimedia,2015,17(6):907-918. [8] WEI L Y,ZHENG Y,PENG W C. Constructing popular routes from uncertain trajectories[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2012:195-203. [9] 刘艳平, 保继刚, 黄应淮, 等. 基于GPS数据的自驾车游客时空行为研究——以西藏为例[J]. 世界地理研究,2019,28(1):149-160. (LIU Y P, BAO J G, HUANG Y H, et al. Study on spatio-temporal behaviors of self-driving tourists based on GPS data:a case study of Tibet[J]. World Regional Studies,2019,28(1):149-160.) [10] ZHENG Y. Trajectory data mining:an overview[J]. ACM Transactions on Intelligent Systems and Technology,2015,6(3):No. 29. [11] LEE J G, HAN J, WHANG K Y. Trajectory clustering:a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York:ACM,2007:593-604. [12] TANG W,PI D,HE Y. A density-based clustering algorithm with sampling for travel behavior analysis[C]//Proceedings of the 2016 International Conference on Intelligent Data Engineering and Automated Learning,LNCS 9937. Cham:Springer,2016:231-239. [13] BESSE P C,GUILLOUET B,LOUBES J M,et al. Review and perspective for distance-based clustering of vehicle trajectories[J]. IEEE Transactions on Intelligent Transportation Systems, 2016,17(11):3306-3317. [14] YI B K,JAGADISH H V,FALOUTSOS C. Efficient retrieval of similar time sequences under time warping[C]//Proceedings of the 14th International Conference on Data Engineering. Piscataway:IEEE,1998:201-208. [15] VLACHOS M,KOLLIOS G,GUNOPOULOS D. Discovering similar multidimensional trajectories[C]//Proceedings of the 18th International Conference on Data Engineering. Piscataway:IEEE, 2002:673-684. [16] CHEN L,ÖZSU M T,ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York:ACM,2005:491-502. [17] WANG J,HUANG P,ZHAO H,et al. Billion-scale commodity embedding for e-commerce recommendation in Alibaba[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2018:839-848. [18] KENTHAPADI K,LE B,VENKATARAMAN G. Personalized job recommendation system at LinkedIn:practical challenges and lessons learned[C]//Proceedings of the 11th ACM Conference on Recommender Systems. New York:ACM,2017:346-347. [19] RADOSAVLJEVIC V,GRBOVIC M,DJURIC N,et al. Smartphone app categorization for interest targeting in advertising marketplace[C]//Proceedings of the 25th International Conference Companion on World Wide Web. New York:ACM,2016:93-94. [20] GRBOVIC M, CHENG H. Real-time personalization using embeddings for search ranking at Airbnb[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2018:311-320. [21] PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk:online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2014:701-710. [22] WIETING J,BANSAL M,GIMPEL K,et al. Towards universal paraphrastic sentence embeddings[EB/OL].[2019-09-20]. https://arxiv.org/pdf/1511.08198.pdf.