Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2020, Vol. 54 Issue (9): 1736-1745    DOI: 10.3785/j.issn.1008-973X.2020.09.009
    
Personalized potential route recommendation based on hidden Markov model
Xiao PAN(),Yun-dan YANG,Xin YAO,Lei WU*(),Shu-hai WANG
School of Economics and Management, Shijiazhuang Tiedao University, Shijiazhuang 050043, China
Download: HTML     PDF(964KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

Most of the existing work on route recommendation were based on the similarities among historical trajectories, however, these approaches cannot return potential routes. Thus, hidden Markov was used to model the personalized potential route recommendation problem, and a new path based on hidden Markov model (HMMPath) was proposed, which generated an access point sequence according to the user-specified category keyword sequence. A route was recommended by combining the length of the route, the personalized route score, and the possibility of accessing the sequence, so that the personalized access requirement was satisfied. Finally, experiments were performed on the real check-in data set by changing the data set size, the number of query category keywords, the type of query category keywords, and the number of recommended routes. The recommendation accuracy of the proposed method can reach more than 70% when the number of query keywords is less than 4, showing high recommendation accuracy.



Key wordshidden Markov model      route recommendation      trajectory big data      personalized recommendation      hidden routes     
Received: 16 August 2019      Published: 22 September 2020
CLC:  TP 391  
Corresponding Authors: Lei WU     E-mail: smallpx@stdu.edu.cn;outhunder@126.com
Cite this article:

Xiao PAN,Yun-dan YANG,Xin YAO,Lei WU,Shu-hai WANG. Personalized potential route recommendation based on hidden Markov model. Journal of ZheJiang University (Engineering Science), 2020, 54(9): 1736-1745.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2020.09.009     OR     http://www.zjujournals.com/eng/Y2020/V54/I9/1736


基于隐马尔科夫模型的潜在个性化路线推荐

现有路线大多基于历史轨迹的相似性进行推荐,容易忽略潜在新路线. 为解决这一问题,利用隐马尔科夫模型对个性化的潜在路线推荐问题进行建模,提出一种可发现隐藏路线的推荐算法(HMMPath);根据用户指定的类别关键字序列生成访问点序列,结合路线长度、个性化路线分数以及访问点序列的可能性,为用户推荐满足个性化需求的路线;在真实签到数据集上通过改变数据集大小、查询类别关键字数量、查询类别关键字类型和推荐路线数量等参数验证所提算法的准确率和运行效率。结果表明,所提方法在包含4个以下短查询类别序列上的推荐准确率在70%以上,表现出了较好的推荐准确度.


关键词: 隐马尔科夫模型,  路线推荐,  轨迹大数据,  个性化推荐,  隐藏路线 
Fig.1 Hidden Markov-based model
①POI标签可以是“西班牙餐厅”、“西餐厅”、“牛排”等,均从属于“餐饮”类别,因此,“餐饮”类别在此POI上共出现3次.
Tab.1 
前一状态 后一状态
v1 v2 v3
v1 0 2/3 1/3
v2 0 0 1
v3 1/2 1/2 0
Tab.1 Transfer probability matrix between POI
地点 类别
c1 c2 c3 c4 c5
v1 2/5 0 2/5 1/5 0
v2 1/4 1/4 0 0 1/2
v3 0 1/3 1/3 0 1/3
Tab.2 Transfer probability matrix between POI and category texts
城市 用户数量 地点数量 轨迹数量
洛杉矶 8 539 11 051 18 604
纽约 10 005 15 697 31 539
Tab.3 Statistical information of data sets on users, venues, and trajectories
Fig.2 Frequency variation of different keyword categories
类别代号 类别文本 词频
C1 Arts&Entertainment
C2 College&University
C3 Food
C4 Great Outdoors
C5 Home, Work, Other
C6 Nightlife Spot
C7 Shop
C8 Travel Spot
Tab.4 Category text and frequency
Fig.3 Change of accuracy and running time on different sizes of datasets
Fig.4 Change of accuracy and running time with different numbers of query keywords
数据集 $\varLambda$ T/s
高频 低频 随机 高频 低频 随机
纽约 1.00 1.00 0.94 2.28 2.16 2.22
洛杉矶 1.00 1.00 1.00 1.55 1.53 1.49
Tab.5 Accuracy and running time over different types of keywords
Fig.5 Change of accuracy and running time with different numbers of recommended routes
[1]   陈霞, 陈超, 刘凯 多源异构众包数据风景旅行路线规划[J]. 浙江大学学报: 工学版, 2016, 50 (5): 1183- 1188
CHEN Xia, CHEN Chao, LIU Kai Scenic travel route planning based on multi-sourced and heterogeneous crowd-sourced data[J]. Journal of Zhejiang University: Engineering Science, 2016, 50 (5): 1183- 1188
[2]   AKABANE A, PAZZI R, MADEIRA E, et al. Modeling and prediction of vehicle routes based on hidden Markov model [C] // Proceedings of 86th Vehicular Technology Conference of IEEE (VTC-Fall). Toronto: IEEE, 2017: 1-5.
[3]   CHEN D W, ONG C S, XIE L X. Learning points and routes to recommend trajectories [C] // Proceedings of the 25th ACM International on Conference on Information and Knowledge Management (CIKM). Indianapolis: ACM, 2016: 2227–2232.
[4]   YOON H, ZHENG Y, XIE X, et al Social itinerary recommendation from user-generated digital trails[J]. Personal and Ubiquitous Computing, 2012, 16 (5): 469- 484
doi: 10.1007/s00779-011-0419-8
[5]   QIAO S J, SHEN D Y, WANG X T, et al A self-adaptive parameter selection trajectory prediction approach via hidden Markov models[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16 (1): 284- 296
doi: 10.1109/TITS.2014.2331758
[6]   BRAUNHOFER M, RICCI F, LAMCHE B, et al. A context-aware model for proactive recommender systems in the tourism domain [C] // Proceedings of the 17th International Conference on Human-Computer Interaction with Mobile Devices and Services Adjunct (MobileHCI). New York: ACM, 2015: 1070-1075.
[7]   CHEN C, CHEN X, WANG L Y, et al MA-SSR: a memetic algorithm for skyline scenic routes planning leveraging heterogeneous user-generated digital footprints[J]. IEEE Transactions on Vehicular Technology, 2017, 66 (7): 5723- 5736
[8]   LI Y J, YANG W D, DAN W, et al. Keyword-aware dominant route search for various user preferences [C] // Proceedings of international Conference on Database Systems for Advanced Applications (DASFAA). Hanoi: Springer, 2015: 207-222.
[9]   CHEN C, ZHANG D Q, GUO B, et al TripPlanner: personalized trip planning leveraging heterogeneous crowdsourced digital footprints[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16 (3): 1259- 1273
doi: 10.1109/TITS.2014.2357835
[10]   JIE B, YU Z, MOKBEL M F. Location-based and preference-aware recommendation using sparse geo-social networking data [C] // Proceedings of the 20rd ACM International Conference on Advances in Geographical Information Systems (SIGSPATIAL). Redondo Beach: ACM, 2012: 199-208.
[11]   WEI L Y, ZHENG Y, PENG W C. Constructing popular routes from uncertain trajectories [C] // Proceedings of the 18th SIGKDD conference on Knowledge Discovery and Data Mining. Beijing: Spinger, 2012: 195-203.
[12]   PAN X, MA A, ZHANG J W, et al Approximate similarity measurements on multi-attributes trajectories data[J]. IEEE Access, 2019, 7: 10905- 10915
doi: 10.1109/ACCESS.2018.2889475
[1] Tai-bo CHEN,Cui-fang ZHANG. Keyword recognition based on twice fusion of Posteriorgram and filler model[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(6): 1170-1176.
[2] Yan ZHANG,Bin GUO,Qian-ru WANG,Jing ZHANG,Zhi-wen YU. SeqRec: sequential-based recommendation model with long-term preference and instant interest[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(6): 1177-1184.
[3] JIA Wen-chao, HU Rong-gui, SHI Fan, XU Cheng-xi. Injection vulnerability threat detection method with multi-feature correlation[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(3): 524-530.
[4] WANG Hua, YING Jing, JIANG Chao. Proactive self-adaptation of software based on inspecting uncertainty[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(2): 213-219.