基于主题序列模式的旅游产品推荐引擎
|
摘要
旅游产品推荐是当前推荐系统研究领域中的新兴议题之一.由于旅游产品描述信息维度多样复杂、"用户-产品"关联矩阵极为稀疏且冷启动问题突出,已经在电子商务领域获得成功的协同过滤推荐往往难以直接被应用于旅游产品推荐.提出基于主题序列模式的旅游产品推荐引擎SECT,试图通过在线旅游网站点击日志的挖掘产生推荐.首先,从页面语义描述文本中挖掘主题,以在泛化层面捕捉用户行为模式;其次,从页面访问时间序列数据中挖掘频繁序列模式及其候选产品集,形成序列模式库;最后,提出Markov n-gram模型,完成用户实时点击流与模式库匹配计算.为了提升在线匹配计算的效率,设计一种新的多叉树数据结构PSC-tree用于存储历史模式库,并与在线计算模块无缝衔接.在真实旅游数据集上的实验结果表明:该推荐引擎比传统推荐算法具有更优越的性能,而且能有效提升冷启动用户的推荐率和准确率.此外,针对长尾物品的推荐,SECT也优于基准算法.
Travel products recommendation has become one of emerging issues in the realm of recommendation systems.The widely-used collaborative filtering algorithms are usually difficult to be used for recommending travel products due to a number of reasons,including:1)the content of travel products is very complex,2)the user-item matrix is extremely sparse,and 3)the cold-start users are widely existing.To tackle these issues,we try to exploit Web server logs for generating recommendation,and present a novel recommendation engine(SECT for short)for travel products based on topic sequential patterns.In detail,we first extract topics from semantic description of every Web page.Then,we mine topic frequent sequential patterns and their target products to form click patterns library.At last,we propose a Markov n-gram model for matching the real-time click-stream of users with the click patterns library and thus computing recommendation scores.To enhance the efficiency of online computing,we design a new multi-branch tree data structures called PSC-tree to store the historical click patterns library and integrate with online computing module seamlessly.Experimental results on a real-world travel dataset demonstrate that the SECT prevails over the state-of-art baseline algorithms.In particular,SECT shows merits in improving both the coverage and accuracy for recommending products to cold-start users.Also,SECT is effective to recommend long tail items and outperform baseline algorithms.
Travel products recommendation has become one of emerging issues in the realm of recommendation systems.The widely-used collaborative filtering algorithms are usually difficult to be used for recommending travel products due to a number of reasons,including:1)the content of travel products is very complex,2)the user-item matrix is extremely sparse,and 3)the cold-start users are widely existing.To tackle these issues,we try to exploit Web server logs for generating recommendation,and present a novel recommendation engine(SECT for short)for travel products based on topic sequential patterns.In detail,we first extract topics from semantic description of every Web page.Then,we mine topic frequent sequential patterns and their target products to form click patterns library.At last,we propose a Markov n-gram model for matching the real-time click-stream of users with the click patterns library and thus computing recommendation scores.To enhance the efficiency of online computing,we design a new multi-branch tree data structures called PSC-tree to store the historical click patterns library and integrate with online computing module seamlessly.Experimental results on a real-world travel dataset demonstrate that the SECT prevails over the state-of-art baseline algorithms.In particular,SECT shows merits in improving both the coverage and accuracy for recommending products to cold-start users.Also,SECT is effective to recommend long tail items and outperform baseline algorithms.
引文
[1]Guo Hongyi,Liu Gongshen,Su Bo,et al.Collaborative filtering recommendation algorithms combining community structure and interest clusters[J].Journal of Computer Research and Development,2016,53(8):1664-1672(in Chinese)(郭弘毅,刘功申,苏波,等.融合社区结构和兴趣聚类的协同过滤推荐算法[J].计算机研究与发展,2016,53(8):1664-1672)
[2]Ge Yong,Xiong Hui,Tuzhilin A,et al.An energy-efficient mobile recommender system[C]Proc of the 16th ACMSIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2010:899-908
[3]Adomavicius G,Tuzhilin A.Toward the next generation of recommender systems:A survey of the state-of-the-art and possible extensions[J].IEEE Trans on Knowledge and Data Engineering,2005,17(6):734-749
[4]Liu Qi,Ge Yong,Li Zhongmou,et al.Personalized travel package recommendation[C]Proc of the 11th Int Conf on Data Mining.Los Alamitos,CA:IEEE Computer Society,2011:407-416
[5]Liu Qi,Chen Enhong,Xiong Hui,et al.A cocktail approach for travel package recommendation[J].IEEE Trans on Knowledge and Data Engineering,2014,26(2):278-293
[6]Ge Yong,Liu Qi,Xiong Hui,et al.Cost-aware travel tour recommendation[C]Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2011:983-991
[7]Ge Yong,Xiong Hui,Tuzhilin A,et al.Collaborative filtering with collective training[C]Proc of the 5th ACMInt Conf on Recommender Systems.New York:ACM,2011:281-284
[8]Pazzani M J,Billsus D.Content-Based Recommendation Systems[M].Berlin:Springer,2007:325-341
[9]Burke R.Hybrid Web Recommender Systems[M].Berlin:Springer,2007:377-408
[10]Jannach D,Zanker M,Fuchs M.Constraint-based recommendation in tourism:A multiperspective case study[J].Information Technology&Tourism,2009,11(2):139-155
[11]Hao Qiang,Cai Rui,Wang Changhu,et al.Equip tourists with knowledge mined from travelogues[C]Proc of the19th Int Conf on World Wide Web.New York:ACM,2010:401-410
[12]Tan Chang,Liu Qi,Chen Enhong,et al.Object-oriented travel package recommendation[J].ACM Trans on Intelligent Systems and Technology,2014,5(3):43:1-43:26
[13]Baltrunas L,Ludwig B,Peer S,et al.Context-aware places of interest recommendations for mobile users[C]Proc of the 14th Int Conf of Design,User Experience,and Usability.Berlin:Springer,2011:531-540
[14]Gavalas D,Konstantopoulos C,Mastakas K,et al.Mobile recommender systems in tourism[J].Journal of Network and Computer Applications,2014,39:319-333
[15]Zheng Yu,Xie Xing.Learning travel recommendations from user-generated GPS traces[J].ACM Trans on Intelligent Systems and Technology,2011,2(1):9:1-9:29
[16]Cao Xin,Cong Gao,Jensen C S.Mining significant semantic locations from GPS data[J].Proceedings of the VLDBEndowment,2010,3(1):1009-1020
[17]Drosatos G,Efraimidis P S,Arampatzis A,et al.Pythia:Aprivacy-enhanced personalized contextual suggestion system for tourism[C]Proc of the 39th Annual Int Conf Computers,Software&Applications.Los Alamitos,CA:IEEE Computer Society,2015:822-827
[18]Cheng Anjung,Chen Yanying,Huang Yenta,et al.Personalized travel recommendation by mining people attributes from community-contributed photos[C]Proc of the 19th ACM Int Conf on Multimedia.New York:ACM,2011:83-92
[19]Ge Yong,Liu Chuanren,Xiong Hui,et al.A taxi business intelligence system[C]Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2011:735-738
[20]Yuan Jing,Zheng Yu,Zhang Chengyang,et al.T-drive:Driving directions based on taxi trajectories[C]Proc of the18th SIGSPATIAL Int Conf on Advances in Geographic Information Systems.New York:ACM,2010:99-108
[21]Hariri N,Mobasher B,Burke R.Context-aware music recommendation based on latenttopic sequential patterns[C]Proc of the 6th ACM Conf on Recommender Systems.New York:ACM,2012:131-138
[22]Letham B,Rudin C,Madigan D.Sequential event prediction[J].Machine Learning,2013,93(2):357-380
[23]Zeng Xianyu,Liu Qi,Zhao Hongke,et at.Online consumptions prediction via modeling user behaviors and choices[J].Journal of Computer Research and Development,2016,53(8):1673-1683(in Chinese)(曾宪宇,刘淇,赵洪科,等.用户在线购买预测:一种基于用户操作序列和选择模型的方法[J].计算机研究与发展,2016,53(8):1673-1683)
[24]Chen Wei,Niu Zhendong,Zhao Xiangyu,et al.A hybrid recommendation algorithm adapted in e-learning environments[J].World Wide Web,2014,17(2):271-284
[25]Wright A P,Wright A T,McCoy A B,et al.The use of sequential pattern mining to predict next prescribed medications[J].Journal of Biomedical Informatics,2015,53(C):73-80
[26]Kennedy L S,Naaman M.Generating diverse and representative image search results for landmarks[C]Proc of the 17th Int Conf on World Wide Web.New York:ACM,2008:297-306
[27]Mei Qiaozhu,Liu Chao,Su Hang,et al.A probabilistic approach to spatiotemporal theme pattern mining on weblogs[C]Proc of the 15th Int Conf on World Wide Web.New York:ACM,2006:533-542
[28]Schafer J B,Frankowski D,Herlocker J,et al.Collaborative Filtering Recommender Systems[M].Berlin:Springer,2007:291-324
[29]Fu A W C,Keogh E,Lau L Y,et al.Scaling and time warping in time series querying[J].The VLDB Journal,2008,17(4):899-921
[30]Blei D M,Ng A Y,Jordan M I.Latent Dirichlet allocation[J].Journal of machine Learning research,2003,3(Jan):993-1022
[31]Kanungo T,Mount D M,Netanyahu N S,et al.An efficient k-means clustering algorithm:Analysis and implementation[J].IEEE Trans on Pattern Analysis and Machine Intelligence,2002,24(7):881-892
[32]Zaki M J.Scalable algorithms for association mining[J].IEEE Trans on Knowledge&Data Engineering,2000,12(3):372-390
[33]Rudin C,Letham B,et al.Sequential event prediction with association rules[C]Proc of the 24th Annual Conf on Learning Theory.New York:ACM,2011:615-63
[34]Peng Fuchun,Schuurmans D,Wang Shaojun.Augmenting naive bayes classifiers with statistical language models[J].Information Retrieval,2004,7(3):317-345
[35]Fakhraei S,Foulds J,Shashanka M,et al.Collective spammer detection in evolving multi-relational social networks[C]Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2015:1769-1778
[36]Ney H,Essen U,Kneser R.On structuring probabilistic dependences in stochastic language modelling[J].Computer Speech&Language,1994,8(1):1-38
[37]Chen S F,Goodman J.An empirical study of smoothing techniques for language modeling[C]Proc of the 34th Annual Meeting on Association for Computational Linguistics.New York:ACM,1996:310-318
[38]Resnick P,Iacovou N,Suchak M,et al.GroupLens:An open architecture for collaborative filtering of netnews[C]Proc of the 1994 ACM Conf on Computer Supported Cooperative Work.New York:ACM,1994:175-186
[39]Koren Y.Factorization meets the neighborhood:Amultifaceted collaborative filtering model[C]Proc of the14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2008:426-434
[40]Powers D M.Evaluation:From precision,recall and F-measure to ROC,informedness,markedness and correlation[J].Journal of Machine Learning Technologies,2011,2(1):37-63
[41]Ge Mouzhi,Delgado-Battenfeld C,Jannach D.Beyond accuracy:Evaluating recommender systems by coverage and serendipity[C]Proc of the 4th ACM Conf on Recommender Systems.New York:ACM,2010:257-260
[42]Jarvelin K,Kekalainen J.IR evaluation methods for retrieving highly relevant documents[C]Proc of the 23rd Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval.New York:ACM,2000:41-48
[43]Hu Meiqun,Lim Eepeng,Sun Aixin,et al.Measuring article quality in Wikipedia:Models and evaluation[C]Proc of the 16th ACM Conf on Information and Knowledge Management.New York:ACM,2007:243-252
[44]Yin Hongzhi,Cui Bin,Li Jing,et al.Challenging the long tail recommendation[J].Proceedings of the VLDBEndowment,2012,5(9):896-907
(1)STA Travel,URL:http://www.statravel.com/
(2)http://www.tuniu.com/
(1)http://grouplens.org/datasets/movielens/100k/
(1)http://mahout.apache.org/
[2]Ge Yong,Xiong Hui,Tuzhilin A,et al.An energy-efficient mobile recommender system[C]Proc of the 16th ACMSIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2010:899-908
[3]Adomavicius G,Tuzhilin A.Toward the next generation of recommender systems:A survey of the state-of-the-art and possible extensions[J].IEEE Trans on Knowledge and Data Engineering,2005,17(6):734-749
[4]Liu Qi,Ge Yong,Li Zhongmou,et al.Personalized travel package recommendation[C]Proc of the 11th Int Conf on Data Mining.Los Alamitos,CA:IEEE Computer Society,2011:407-416
[5]Liu Qi,Chen Enhong,Xiong Hui,et al.A cocktail approach for travel package recommendation[J].IEEE Trans on Knowledge and Data Engineering,2014,26(2):278-293
[6]Ge Yong,Liu Qi,Xiong Hui,et al.Cost-aware travel tour recommendation[C]Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2011:983-991
[7]Ge Yong,Xiong Hui,Tuzhilin A,et al.Collaborative filtering with collective training[C]Proc of the 5th ACMInt Conf on Recommender Systems.New York:ACM,2011:281-284
[8]Pazzani M J,Billsus D.Content-Based Recommendation Systems[M].Berlin:Springer,2007:325-341
[9]Burke R.Hybrid Web Recommender Systems[M].Berlin:Springer,2007:377-408
[10]Jannach D,Zanker M,Fuchs M.Constraint-based recommendation in tourism:A multiperspective case study[J].Information Technology&Tourism,2009,11(2):139-155
[11]Hao Qiang,Cai Rui,Wang Changhu,et al.Equip tourists with knowledge mined from travelogues[C]Proc of the19th Int Conf on World Wide Web.New York:ACM,2010:401-410
[12]Tan Chang,Liu Qi,Chen Enhong,et al.Object-oriented travel package recommendation[J].ACM Trans on Intelligent Systems and Technology,2014,5(3):43:1-43:26
[13]Baltrunas L,Ludwig B,Peer S,et al.Context-aware places of interest recommendations for mobile users[C]Proc of the 14th Int Conf of Design,User Experience,and Usability.Berlin:Springer,2011:531-540
[14]Gavalas D,Konstantopoulos C,Mastakas K,et al.Mobile recommender systems in tourism[J].Journal of Network and Computer Applications,2014,39:319-333
[15]Zheng Yu,Xie Xing.Learning travel recommendations from user-generated GPS traces[J].ACM Trans on Intelligent Systems and Technology,2011,2(1):9:1-9:29
[16]Cao Xin,Cong Gao,Jensen C S.Mining significant semantic locations from GPS data[J].Proceedings of the VLDBEndowment,2010,3(1):1009-1020
[17]Drosatos G,Efraimidis P S,Arampatzis A,et al.Pythia:Aprivacy-enhanced personalized contextual suggestion system for tourism[C]Proc of the 39th Annual Int Conf Computers,Software&Applications.Los Alamitos,CA:IEEE Computer Society,2015:822-827
[18]Cheng Anjung,Chen Yanying,Huang Yenta,et al.Personalized travel recommendation by mining people attributes from community-contributed photos[C]Proc of the 19th ACM Int Conf on Multimedia.New York:ACM,2011:83-92
[19]Ge Yong,Liu Chuanren,Xiong Hui,et al.A taxi business intelligence system[C]Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2011:735-738
[20]Yuan Jing,Zheng Yu,Zhang Chengyang,et al.T-drive:Driving directions based on taxi trajectories[C]Proc of the18th SIGSPATIAL Int Conf on Advances in Geographic Information Systems.New York:ACM,2010:99-108
[21]Hariri N,Mobasher B,Burke R.Context-aware music recommendation based on latenttopic sequential patterns[C]Proc of the 6th ACM Conf on Recommender Systems.New York:ACM,2012:131-138
[22]Letham B,Rudin C,Madigan D.Sequential event prediction[J].Machine Learning,2013,93(2):357-380
[23]Zeng Xianyu,Liu Qi,Zhao Hongke,et at.Online consumptions prediction via modeling user behaviors and choices[J].Journal of Computer Research and Development,2016,53(8):1673-1683(in Chinese)(曾宪宇,刘淇,赵洪科,等.用户在线购买预测:一种基于用户操作序列和选择模型的方法[J].计算机研究与发展,2016,53(8):1673-1683)
[24]Chen Wei,Niu Zhendong,Zhao Xiangyu,et al.A hybrid recommendation algorithm adapted in e-learning environments[J].World Wide Web,2014,17(2):271-284
[25]Wright A P,Wright A T,McCoy A B,et al.The use of sequential pattern mining to predict next prescribed medications[J].Journal of Biomedical Informatics,2015,53(C):73-80
[26]Kennedy L S,Naaman M.Generating diverse and representative image search results for landmarks[C]Proc of the 17th Int Conf on World Wide Web.New York:ACM,2008:297-306
[27]Mei Qiaozhu,Liu Chao,Su Hang,et al.A probabilistic approach to spatiotemporal theme pattern mining on weblogs[C]Proc of the 15th Int Conf on World Wide Web.New York:ACM,2006:533-542
[28]Schafer J B,Frankowski D,Herlocker J,et al.Collaborative Filtering Recommender Systems[M].Berlin:Springer,2007:291-324
[29]Fu A W C,Keogh E,Lau L Y,et al.Scaling and time warping in time series querying[J].The VLDB Journal,2008,17(4):899-921
[30]Blei D M,Ng A Y,Jordan M I.Latent Dirichlet allocation[J].Journal of machine Learning research,2003,3(Jan):993-1022
[31]Kanungo T,Mount D M,Netanyahu N S,et al.An efficient k-means clustering algorithm:Analysis and implementation[J].IEEE Trans on Pattern Analysis and Machine Intelligence,2002,24(7):881-892
[32]Zaki M J.Scalable algorithms for association mining[J].IEEE Trans on Knowledge&Data Engineering,2000,12(3):372-390
[33]Rudin C,Letham B,et al.Sequential event prediction with association rules[C]Proc of the 24th Annual Conf on Learning Theory.New York:ACM,2011:615-63
[34]Peng Fuchun,Schuurmans D,Wang Shaojun.Augmenting naive bayes classifiers with statistical language models[J].Information Retrieval,2004,7(3):317-345
[35]Fakhraei S,Foulds J,Shashanka M,et al.Collective spammer detection in evolving multi-relational social networks[C]Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2015:1769-1778
[36]Ney H,Essen U,Kneser R.On structuring probabilistic dependences in stochastic language modelling[J].Computer Speech&Language,1994,8(1):1-38
[37]Chen S F,Goodman J.An empirical study of smoothing techniques for language modeling[C]Proc of the 34th Annual Meeting on Association for Computational Linguistics.New York:ACM,1996:310-318
[38]Resnick P,Iacovou N,Suchak M,et al.GroupLens:An open architecture for collaborative filtering of netnews[C]Proc of the 1994 ACM Conf on Computer Supported Cooperative Work.New York:ACM,1994:175-186
[39]Koren Y.Factorization meets the neighborhood:Amultifaceted collaborative filtering model[C]Proc of the14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining.New York:ACM,2008:426-434
[40]Powers D M.Evaluation:From precision,recall and F-measure to ROC,informedness,markedness and correlation[J].Journal of Machine Learning Technologies,2011,2(1):37-63
[41]Ge Mouzhi,Delgado-Battenfeld C,Jannach D.Beyond accuracy:Evaluating recommender systems by coverage and serendipity[C]Proc of the 4th ACM Conf on Recommender Systems.New York:ACM,2010:257-260
[42]Jarvelin K,Kekalainen J.IR evaluation methods for retrieving highly relevant documents[C]Proc of the 23rd Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval.New York:ACM,2000:41-48
[43]Hu Meiqun,Lim Eepeng,Sun Aixin,et al.Measuring article quality in Wikipedia:Models and evaluation[C]Proc of the 16th ACM Conf on Information and Knowledge Management.New York:ACM,2007:243-252
[44]Yin Hongzhi,Cui Bin,Li Jing,et al.Challenging the long tail recommendation[J].Proceedings of the VLDBEndowment,2012,5(9):896-907
(1)STA Travel,URL:http://www.statravel.com/
(2)http://www.tuniu.com/
(1)http://grouplens.org/datasets/movielens/100k/
(1)http://mahout.apache.org/