协同过滤技术在个性化推荐中的应用研究
|
摘要
随着Internet和信息技术的飞速发展,个性化推荐作为一种崭新的智能信息服务方式,根据用户提出的明确要求,或通过对用户个性、习惯、偏好的分析,准确地向用户提供感兴趣的信息和服务,从而有效地解决了“信息过载”和“信息迷失”带来的种种问题,成为许多学者关注和研究的热点。
个性化推荐的具体实现方法有很多,其中协同过滤推荐算法是目前运用的最为广泛也是比较有效的一种,主要包括User-based和Item-based推荐算法。然而,随着系统规模的不断扩大,用户评分数据极端稀疏等问题使其推荐质量严重下降。因此,必须对传统的协同过滤推荐算法加以改进。
本文所做的主要工作和创新点如下:
(1)对个性化推荐系统进行了深入研究,包括个性化推荐系统的应用现状、输入与输出、主要分类和推荐系统实现的具体方法,如:基于规则、基于内容、知识工程、数据挖掘和协同过滤方法。
(2)对协同过滤推荐算法进行研究分析,包括基于用户的协同过滤推荐算法和基于项目的协同过滤推荐算法。并且指出传统协同过滤推荐算法所存在的不足,主要包括:用户评分数据的稀疏性问题;推荐算法的实时性问题;推荐系统对于新用户的“冷开始”问题。
(3)提出了一种协同过滤推荐算法的改进方法,将User-based和Item-based协同过滤推荐算法的思想相结合,通过形成项目相似集,由用户对相似项目的评分来智能地预测用户对未评分项的评分,填充用户评分矩阵,有效解决了用户评分数据稀疏情况下传统相似性度算法所存在的不足。另外,在形成用户最近邻居时,引入高评分阈值,重点考虑高评分项目对推荐产生的影响,更能代表目标用户的实际兴趣爱好,从而显著提高个性化协同过滤推荐算法的推荐精度。
Along with the rapid development of Internet and information technology, personalization recommendation has become one method of the new intelligent service. According to the analysis of consumers' individuality, habit and favor, the system provides information and service to the consumer which they want. Consequently, the problem of "information overloading" and "information maze" has been solved. Today, more and more researchers have focused on this field.
There are many ways to actualize personalization recommendation. The most popular and effective one is Collaborative Filtering, including User-based and Item-based recommendation arithmetic. However, the efficiency of this technology decline by the increasing number of users and items, which results to extremely sparse data of users' assessments and other problems. Therefore the traditional arithmetic need improve.
The major contributions of the thesis are as follows:
(1) This thesis study deeply on personalization recommendation system, including its application status, input and output format, category and methods to actualize, for example, Rule-based, Content-based, Knowledge Engineering, Data Mining and Collaborative Filtering approach.
(2) Collaborative Filtering recommendation arithmetic is researched, including User-based and Item-based recommendation arithmetic. Then it is appointed that collaborative filtering approach suffer from many challenges, such as: sparsity, scalability and cold-start problem.
(3) The improved method of Collaborative Filtering recommendation is posed. It unites the ideas of User-based and Item-based recommendation arithmetic. It evaluates ratings of items by the similar items and may solve the problems such as sparsity. Further more, it calculates the nearest neighbors of target user by an improved way that only considers the records with high ratings. As result, it may get accurate results of Personality Recommendation quickly.
个性化推荐的具体实现方法有很多,其中协同过滤推荐算法是目前运用的最为广泛也是比较有效的一种,主要包括User-based和Item-based推荐算法。然而,随着系统规模的不断扩大,用户评分数据极端稀疏等问题使其推荐质量严重下降。因此,必须对传统的协同过滤推荐算法加以改进。
本文所做的主要工作和创新点如下:
(1)对个性化推荐系统进行了深入研究,包括个性化推荐系统的应用现状、输入与输出、主要分类和推荐系统实现的具体方法,如:基于规则、基于内容、知识工程、数据挖掘和协同过滤方法。
(2)对协同过滤推荐算法进行研究分析,包括基于用户的协同过滤推荐算法和基于项目的协同过滤推荐算法。并且指出传统协同过滤推荐算法所存在的不足,主要包括:用户评分数据的稀疏性问题;推荐算法的实时性问题;推荐系统对于新用户的“冷开始”问题。
(3)提出了一种协同过滤推荐算法的改进方法,将User-based和Item-based协同过滤推荐算法的思想相结合,通过形成项目相似集,由用户对相似项目的评分来智能地预测用户对未评分项的评分,填充用户评分矩阵,有效解决了用户评分数据稀疏情况下传统相似性度算法所存在的不足。另外,在形成用户最近邻居时,引入高评分阈值,重点考虑高评分项目对推荐产生的影响,更能代表目标用户的实际兴趣爱好,从而显著提高个性化协同过滤推荐算法的推荐精度。
Along with the rapid development of Internet and information technology, personalization recommendation has become one method of the new intelligent service. According to the analysis of consumers' individuality, habit and favor, the system provides information and service to the consumer which they want. Consequently, the problem of "information overloading" and "information maze" has been solved. Today, more and more researchers have focused on this field.
There are many ways to actualize personalization recommendation. The most popular and effective one is Collaborative Filtering, including User-based and Item-based recommendation arithmetic. However, the efficiency of this technology decline by the increasing number of users and items, which results to extremely sparse data of users' assessments and other problems. Therefore the traditional arithmetic need improve.
The major contributions of the thesis are as follows:
(1) This thesis study deeply on personalization recommendation system, including its application status, input and output format, category and methods to actualize, for example, Rule-based, Content-based, Knowledge Engineering, Data Mining and Collaborative Filtering approach.
(2) Collaborative Filtering recommendation arithmetic is researched, including User-based and Item-based recommendation arithmetic. Then it is appointed that collaborative filtering approach suffer from many challenges, such as: sparsity, scalability and cold-start problem.
(3) The improved method of Collaborative Filtering recommendation is posed. It unites the ideas of User-based and Item-based recommendation arithmetic. It evaluates ratings of items by the similar items and may solve the problems such as sparsity. Further more, it calculates the nearest neighbors of target user by an improved way that only considers the records with high ratings. As result, it may get accurate results of Personality Recommendation quickly.
引文
[1]Alexander Pretschner,Susan Gauch.Personalization on the Web.Technical Report M C-FY2000-TR-13591-01,December,1999.
[2]曾春,邢春晓,周立柱.个性化服务技术综述.软件学报,2002,13(10):1952-1960.
[3]Chickering D,Hecherman D.Efficient approximations for the arginal likelihood of Bayesian networks with hidden variables[J].Machine Learning,1997,29(2/3):181-212.
[4]Sarwar B,Karypis G;Konstan J,Riedl J.Analysis of recommendation algorithms for E-commerce[R].In:ACM Conference on Electronic Commerce,2000,pp.158-167.
[5]Dempster A,Laird N,Rubin D.Maximum likelihood from incomplete data via the EM algorithm[J].Journal of the Royal Statistical Society,1977,B39:1-38.
[6]Wolf J,Aggarwal C,Wu K-L,Yu P.Horting hatches an egg:A new graph-theoretic approach to collaborative filtering[R].In:Proceedings of the ACM SIGMOD International Conference on Knowledge Discovery and Data Mining,San Diego,1999,pp.201-212.
[7]周惠宏等.推荐技术在电子商务中的运用综述,计算机应用研究.2004,1:8-12.
[8]王大玲.支持个性化推荐的web挖掘关键技术的研究,东北大学博士论文,2003.
[9]Mobasher B,Dai H,Luo T,and Nakagawa M.Improving the Effectiveness of Collaborative Filtering on Anonymous Web Usage Data.In Proceedings of the UCAI 2001 Workshop on Intelligent Techniques for Web Personalization(ITWPO1),2001.
[10]Shneiderman B.Designing the User Interface:Strategies for Effective Human一Computer Interaction.Addison Wesley Inc,1998.
[11]Belkin N,Croft B.Information Filtering and Information Retrieval:Two sides of the same Coin.Communications of ACM,1992.
[12]Herlocker J.Understanding and Improving Automated Collaborative Filtering Systems.Ph.D.Thesis,Science Dept.University of Minnesota,2000.
[13]Herlocker J,Konstan LA,Borchers A,and Riedl J.An Algorithmic Framework for Perform collaborative Filtering.Proceedings of SIGIR,1999
[14]Goldberg D,Nichols D.Using Collaborative Filtering to Weave an Information Tapestry.Communications of the ACM,1992.
[15]Konstan J.A,Miller B.Group Lens:Applying Collaborative Filtering to Usenet News.Communications of the ACM,1997.
[16]D.M.Pennock and E.Horvitz,Collaborative filtering by personality diagnosis:A hybrid memory and model-based approach.In DCAI Workshop on Machine Learning for Information Filtering,Stockholm,Sweden,August 1999,International Joint Conference on Artificial Intelligence,1999.
[17]赵亮,胡乃静,张志守.个性化推荐算法设计.计算机研究与发展,Vol.39,No.8,Aug,2002.
[18]Charu C.Aggarwal,Joel L.Wolf,Kun-Lung Wu,Philip S.Yu..Horting Hatches an Egg:A New Graph-Theoretic Approach to Collaborative Filtering.In Proceedings of the ACM KDD'99 Conference.San Diego,CA.pp.201-212,1999.
[19]Fink J,Kobsa A and Nill A.User-oriented adaptivity and adaptability in the AVANTI project.Designing for the WEB:Empirical studies,Microsoft Usability group.Redmond,WA.
[20]Wexelblat A.and Maes P.Using history to assist information browsing.'RIAO' 97:Computer-assisted information retrieval on the Internet,Montreal,1997.
[21]D.S.W.Ngu and X.Wu.Site Helper:A localized agent that helps of the World Wide Web.In 6'0 incremental exploration International exploration of the World Wide Web conference,Santa Clara,CA 1997.
[22]Joachims T,Freitag D and Mitchell T.Web Watcher:A Tour Guide for the World Wide Web.Proceedings of the 15 International Joint Conference on Artificial Intelligence UCAI一97.
[23]Xin Jin,Yanzan Zhou,Bamshad Mobasher:A maximum entropy web recommendation system:combining collaborative and content features.KDD 2005:612-617.
[24]Nasraoui O,Frigui H,Joshi A,Krishnapuram,R.Mining Web access logs using relational competitive fuzzy clustering.To appear in the Proceedings of the Eight International Fuzzy Systems Association World Congress,August 1999.
[25]R.Cooley,B.Mobasher and J.Srrvastava.Grouping web page references into transactions for mining World Wide Web browsing patterns.Technical Report TR 97-021,University of Minnesota,Dept.of Computer Science,Minnerapolis,1997.
[26] Schecher S, Krishnan M and Smith M.D. Using path profiles to project HTTP requests.In Proceedings of 7th International World Wide Web Conference, Brisbane, Australia,1998.
[27] Mobasher B, Cooley R., and Srivastava J. Creationg Adaptive Web Sites Through Usage-Based Clustering of URLs. In Proceedings of the 1999 IEEE Knowledge and Data Engineering Exchange Workshop (KDEX99), 1999.
[28] Mobasher B, Dai H, Luo T, Sun Y, and Zhou J. Integrating Web Usage and Content Mining for More Effective Personalization. In Proceedings of the International Conference on E-Commerce and Web Technologies (ECWeb2000), 2000.
[29] Schafer J, Konstan J. Ecommerce Recommendation Applications. Data Mining and Knowledge Discovery, 2001.
[30] Schafer J.B, Konstan LA, Riedl J. Recommender Systems in E-Commerce. In ACM Conference on Electronic Commerce (EC99), 1999.
[31] Zan Huang, Wingyan Chun, and Hsinchun Chen. A Graph Model for E-Commerce Recommender Systems. In: Journal of the American Society for Information Science and Technology, 55(3):259-274, 2004.
[32] Kohavi R. Applications of Data Mining to Electronic Commerce. Data Mining and Knowledge Discovery, 2001
[33] Schafer J.B, Konstan J, Riedl J. E-Commerce Recommendations Journal of Data Mining and Knowledge Discovery, January — April 2001, Vol 5: 115-153.
[34] Sarwar B, Karypis G, Konstan J, and Riedl J. Incremental Singular Value Decomposition Algorithms for Highly Scalable Recommender Systems.
[35] Deng Cai, Zengxiang Lu, Yanda Li. Collaborative Filtering (in Chinese). Journal of Computer Science, Vol.29, No.6, pp. 1-4, 2002.
[36] Sarwar B, Karypis G, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms. In: Proceedings of the 10th International World Wide Web Conference. 2001:285-295.
[37] Sarwar B, Karypis G, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms. Proceedings of the 10th International World Wide Web Conference. 2001: 285-295.
[38] Sarwar B. M., Karypis G, Konstan, J.A, and Riedl J. Analysis of Recommender Algorithms for E-Commerce. In proc of the ACM E-Commerce 2000 Conf. Oct. 17-20,2000: 158-167.
[39] Mobasher B, Cooley R. Data Preparation for Mining World Wide Browsing Patterns.Knowledge and Information systems, 1999.
[2]曾春,邢春晓,周立柱.个性化服务技术综述.软件学报,2002,13(10):1952-1960.
[3]Chickering D,Hecherman D.Efficient approximations for the arginal likelihood of Bayesian networks with hidden variables[J].Machine Learning,1997,29(2/3):181-212.
[4]Sarwar B,Karypis G;Konstan J,Riedl J.Analysis of recommendation algorithms for E-commerce[R].In:ACM Conference on Electronic Commerce,2000,pp.158-167.
[5]Dempster A,Laird N,Rubin D.Maximum likelihood from incomplete data via the EM algorithm[J].Journal of the Royal Statistical Society,1977,B39:1-38.
[6]Wolf J,Aggarwal C,Wu K-L,Yu P.Horting hatches an egg:A new graph-theoretic approach to collaborative filtering[R].In:Proceedings of the ACM SIGMOD International Conference on Knowledge Discovery and Data Mining,San Diego,1999,pp.201-212.
[7]周惠宏等.推荐技术在电子商务中的运用综述,计算机应用研究.2004,1:8-12.
[8]王大玲.支持个性化推荐的web挖掘关键技术的研究,东北大学博士论文,2003.
[9]Mobasher B,Dai H,Luo T,and Nakagawa M.Improving the Effectiveness of Collaborative Filtering on Anonymous Web Usage Data.In Proceedings of the UCAI 2001 Workshop on Intelligent Techniques for Web Personalization(ITWPO1),2001.
[10]Shneiderman B.Designing the User Interface:Strategies for Effective Human一Computer Interaction.Addison Wesley Inc,1998.
[11]Belkin N,Croft B.Information Filtering and Information Retrieval:Two sides of the same Coin.Communications of ACM,1992.
[12]Herlocker J.Understanding and Improving Automated Collaborative Filtering Systems.Ph.D.Thesis,Science Dept.University of Minnesota,2000.
[13]Herlocker J,Konstan LA,Borchers A,and Riedl J.An Algorithmic Framework for Perform collaborative Filtering.Proceedings of SIGIR,1999
[14]Goldberg D,Nichols D.Using Collaborative Filtering to Weave an Information Tapestry.Communications of the ACM,1992.
[15]Konstan J.A,Miller B.Group Lens:Applying Collaborative Filtering to Usenet News.Communications of the ACM,1997.
[16]D.M.Pennock and E.Horvitz,Collaborative filtering by personality diagnosis:A hybrid memory and model-based approach.In DCAI Workshop on Machine Learning for Information Filtering,Stockholm,Sweden,August 1999,International Joint Conference on Artificial Intelligence,1999.
[17]赵亮,胡乃静,张志守.个性化推荐算法设计.计算机研究与发展,Vol.39,No.8,Aug,2002.
[18]Charu C.Aggarwal,Joel L.Wolf,Kun-Lung Wu,Philip S.Yu..Horting Hatches an Egg:A New Graph-Theoretic Approach to Collaborative Filtering.In Proceedings of the ACM KDD'99 Conference.San Diego,CA.pp.201-212,1999.
[19]Fink J,Kobsa A and Nill A.User-oriented adaptivity and adaptability in the AVANTI project.Designing for the WEB:Empirical studies,Microsoft Usability group.Redmond,WA.
[20]Wexelblat A.and Maes P.Using history to assist information browsing.'RIAO' 97:Computer-assisted information retrieval on the Internet,Montreal,1997.
[21]D.S.W.Ngu and X.Wu.Site Helper:A localized agent that helps of the World Wide Web.In 6'0 incremental exploration International exploration of the World Wide Web conference,Santa Clara,CA 1997.
[22]Joachims T,Freitag D and Mitchell T.Web Watcher:A Tour Guide for the World Wide Web.Proceedings of the 15 International Joint Conference on Artificial Intelligence UCAI一97.
[23]Xin Jin,Yanzan Zhou,Bamshad Mobasher:A maximum entropy web recommendation system:combining collaborative and content features.KDD 2005:612-617.
[24]Nasraoui O,Frigui H,Joshi A,Krishnapuram,R.Mining Web access logs using relational competitive fuzzy clustering.To appear in the Proceedings of the Eight International Fuzzy Systems Association World Congress,August 1999.
[25]R.Cooley,B.Mobasher and J.Srrvastava.Grouping web page references into transactions for mining World Wide Web browsing patterns.Technical Report TR 97-021,University of Minnesota,Dept.of Computer Science,Minnerapolis,1997.
[26] Schecher S, Krishnan M and Smith M.D. Using path profiles to project HTTP requests.In Proceedings of 7th International World Wide Web Conference, Brisbane, Australia,1998.
[27] Mobasher B, Cooley R., and Srivastava J. Creationg Adaptive Web Sites Through Usage-Based Clustering of URLs. In Proceedings of the 1999 IEEE Knowledge and Data Engineering Exchange Workshop (KDEX99), 1999.
[28] Mobasher B, Dai H, Luo T, Sun Y, and Zhou J. Integrating Web Usage and Content Mining for More Effective Personalization. In Proceedings of the International Conference on E-Commerce and Web Technologies (ECWeb2000), 2000.
[29] Schafer J, Konstan J. Ecommerce Recommendation Applications. Data Mining and Knowledge Discovery, 2001.
[30] Schafer J.B, Konstan LA, Riedl J. Recommender Systems in E-Commerce. In ACM Conference on Electronic Commerce (EC99), 1999.
[31] Zan Huang, Wingyan Chun, and Hsinchun Chen. A Graph Model for E-Commerce Recommender Systems. In: Journal of the American Society for Information Science and Technology, 55(3):259-274, 2004.
[32] Kohavi R. Applications of Data Mining to Electronic Commerce. Data Mining and Knowledge Discovery, 2001
[33] Schafer J.B, Konstan J, Riedl J. E-Commerce Recommendations Journal of Data Mining and Knowledge Discovery, January — April 2001, Vol 5: 115-153.
[34] Sarwar B, Karypis G, Konstan J, and Riedl J. Incremental Singular Value Decomposition Algorithms for Highly Scalable Recommender Systems.
[35] Deng Cai, Zengxiang Lu, Yanda Li. Collaborative Filtering (in Chinese). Journal of Computer Science, Vol.29, No.6, pp. 1-4, 2002.
[36] Sarwar B, Karypis G, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms. In: Proceedings of the 10th International World Wide Web Conference. 2001:285-295.
[37] Sarwar B, Karypis G, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms. Proceedings of the 10th International World Wide Web Conference. 2001: 285-295.
[38] Sarwar B. M., Karypis G, Konstan, J.A, and Riedl J. Analysis of Recommender Algorithms for E-Commerce. In proc of the ACM E-Commerce 2000 Conf. Oct. 17-20,2000: 158-167.
[39] Mobasher B, Cooley R. Data Preparation for Mining World Wide Browsing Patterns.Knowledge and Information systems, 1999.