面向企业用户的在线推荐算法研究
|
摘要
目前,电子商务领域中的推荐算法已经发展得比较成熟,尤其是协同过滤推荐算法以及由其所衍生出来的各种推荐算法。这些推荐算法主要应用于B2C的电子商务系统中。但是随着应用的不断深入,企业级的(B2B)电子商务系统越来越多,企业级电子商务系统对推荐算法的需求也愈加强烈。
传统的协同过滤推荐算法有诸多弊病,在用户首次注册并登陆系统时存在冷启动问题,在某些特殊的领域或面对某些特殊的用户时又存在数据稀疏性问题,基于用户的协同过滤算法的时间复杂度高,对服务器的负荷较大,而基于项目的协同过滤算法虽可线下预先运算,算法效率快,但却需要数据仓库的支持,给许多企业级电子商务系统带来麻烦,而且应用于企业用户的各种算法也在某种程度上有异于应用于B2C的算法。
本文设计并实现了一个业内领先的企业级电子商务系统——华贸易货交易所系统,并在对协同过滤等推荐算法进行深入研究,对比多种搜索、排序算法后,为该系统的商品推荐功能提供了一种面向企业用户的在线商品推荐算法,致力于追求高效率、高质量地推荐最热销又最符合客户需求的好商品。
本算法利用电子商务系统中普遍存在的商品和企业的多级分类‘结构,快速而准确地确定了企业用户的最近邻居以及待推荐商品所涉及的交易记录,通过这些交易记录对商品进行评分,避免了算法执行过程中遇到的冷启动以及数据稀疏性问题。通过有效建立堆的数据结构,方便高效地根据评分结果对待推荐的商品进行排序,提高了算法的执行效率。
由于时代的飞速发展,企业所需要的商品也在不断地更新换代,陈旧的商品显然不能满足企业日益增长的需求,因此本算法抛弃了对一定时间之前的交易记录,仅针对最近的交易记录进行分析,不仅优化了算法效率,更提高了推荐的质量,提高了客户满意度。由于根据交易记录所得出的推荐项可能存在商品已经售完的问题,因此本算法使用Levenshtein Distance(编辑距离)字符串相似性算法寻找商品原发布者重新上架用来代替已售罄商品的新商品,解决了推荐项无效的问题。
Currently, the recommendation algorithms in the e-commerce domain have been well developed, especially in collaborative filtering algorithms and the variety of recommendation algorithm derived from it. These recommendation algorithm is mainly used in B2C e-commerce system. But with the developing of applications, the number of business-to-business (B2B) e-commerce systems is highly increased, so the needs of the recommendation algorithm from B2B e-commerce system have become even more intense.
The traditional collaborative filtering algorithm has many drawbacks. Cold start problem exists when the user firstly register and log in the system, and data sparseness problem occurs in some specific areas or customers. User-based collaborative filtering algorithm has a high time complexity, high cost on server. Project-based collaborative filtering algorithm can be processed offline, efficiency, low time cost and faster, but it needs the support of data warehousing. These bring a lot of trouble to B2B e-commerce systems. The appliance of recommendation algorithms to corporate users are also somewhat different from the algorithms used in B2C systems.
In this paper, we designed and developed a leading B2B e-commerce system in certain domain which is Huamao barter exchange system. After deeply studied the collaborative filtering recommendation algorithm, compared to a variety of searching, sorting algorithm, we provide a online recommendation algorithm for corporate users for that system. The algorithm is committed to have high efficiency, high-quality and recommend the best selling and best products that meet the customer needs.
The algorithm takes advantage of multi-level classification structure which is prevalent in e-commerce systems to quickly and accurately determine the nearest neighbor of the enterprise and goods involved in the transaction records. They can be used to mark out the products we want to recommend. The algorithm resolves the sparse data problem and cold-start problem. Through the effective establishment of the heap data structure, we can conveniently and efficiently sort the goods based on score results that successfully improved the efficiency of the algorithm.
During the rapid development, the goods needed by businesses are constantly upgrading, the old product obviously does not meet the growing needs of businesses. So the algorithm abandon the transaction record which is long time ago. We only analyze the most recent transaction records, not only increase the efficiency of the algorithm, but also improve the quality of recommendations and customer satisfaction. The recommendation based on of the transaction log may bring a problem that the goods which is recommended may have been sold out. So the algorithm takes advantage of string similarity algorithm based on Levenshtein Distance to find the new product which is a replacement of the original product from the original publisher. That solves the problem of invalid recommendation.
传统的协同过滤推荐算法有诸多弊病,在用户首次注册并登陆系统时存在冷启动问题,在某些特殊的领域或面对某些特殊的用户时又存在数据稀疏性问题,基于用户的协同过滤算法的时间复杂度高,对服务器的负荷较大,而基于项目的协同过滤算法虽可线下预先运算,算法效率快,但却需要数据仓库的支持,给许多企业级电子商务系统带来麻烦,而且应用于企业用户的各种算法也在某种程度上有异于应用于B2C的算法。
本文设计并实现了一个业内领先的企业级电子商务系统——华贸易货交易所系统,并在对协同过滤等推荐算法进行深入研究,对比多种搜索、排序算法后,为该系统的商品推荐功能提供了一种面向企业用户的在线商品推荐算法,致力于追求高效率、高质量地推荐最热销又最符合客户需求的好商品。
本算法利用电子商务系统中普遍存在的商品和企业的多级分类‘结构,快速而准确地确定了企业用户的最近邻居以及待推荐商品所涉及的交易记录,通过这些交易记录对商品进行评分,避免了算法执行过程中遇到的冷启动以及数据稀疏性问题。通过有效建立堆的数据结构,方便高效地根据评分结果对待推荐的商品进行排序,提高了算法的执行效率。
由于时代的飞速发展,企业所需要的商品也在不断地更新换代,陈旧的商品显然不能满足企业日益增长的需求,因此本算法抛弃了对一定时间之前的交易记录,仅针对最近的交易记录进行分析,不仅优化了算法效率,更提高了推荐的质量,提高了客户满意度。由于根据交易记录所得出的推荐项可能存在商品已经售完的问题,因此本算法使用Levenshtein Distance(编辑距离)字符串相似性算法寻找商品原发布者重新上架用来代替已售罄商品的新商品,解决了推荐项无效的问题。
Currently, the recommendation algorithms in the e-commerce domain have been well developed, especially in collaborative filtering algorithms and the variety of recommendation algorithm derived from it. These recommendation algorithm is mainly used in B2C e-commerce system. But with the developing of applications, the number of business-to-business (B2B) e-commerce systems is highly increased, so the needs of the recommendation algorithm from B2B e-commerce system have become even more intense.
The traditional collaborative filtering algorithm has many drawbacks. Cold start problem exists when the user firstly register and log in the system, and data sparseness problem occurs in some specific areas or customers. User-based collaborative filtering algorithm has a high time complexity, high cost on server. Project-based collaborative filtering algorithm can be processed offline, efficiency, low time cost and faster, but it needs the support of data warehousing. These bring a lot of trouble to B2B e-commerce systems. The appliance of recommendation algorithms to corporate users are also somewhat different from the algorithms used in B2C systems.
In this paper, we designed and developed a leading B2B e-commerce system in certain domain which is Huamao barter exchange system. After deeply studied the collaborative filtering recommendation algorithm, compared to a variety of searching, sorting algorithm, we provide a online recommendation algorithm for corporate users for that system. The algorithm is committed to have high efficiency, high-quality and recommend the best selling and best products that meet the customer needs.
The algorithm takes advantage of multi-level classification structure which is prevalent in e-commerce systems to quickly and accurately determine the nearest neighbor of the enterprise and goods involved in the transaction records. They can be used to mark out the products we want to recommend. The algorithm resolves the sparse data problem and cold-start problem. Through the effective establishment of the heap data structure, we can conveniently and efficiently sort the goods based on score results that successfully improved the efficiency of the algorithm.
During the rapid development, the goods needed by businesses are constantly upgrading, the old product obviously does not meet the growing needs of businesses. So the algorithm abandon the transaction record which is long time ago. We only analyze the most recent transaction records, not only increase the efficiency of the algorithm, but also improve the quality of recommendations and customer satisfaction. The recommendation based on of the transaction log may bring a problem that the goods which is recommended may have been sold out. So the algorithm takes advantage of string similarity algorithm based on Levenshtein Distance to find the new product which is a replacement of the original product from the original publisher. That solves the problem of invalid recommendation.
引文
[1]http://www.ebarter.cn/League/index.shtm
[2]http://bci.bartercard.com/?page=about-bartercard
[3]http://baike.baidu.com/view/1381528.html?fromTaglist
[4]http://hi.baidu.com/lettoo/blog/item/ea2e871686cee11f962b435e.html
[5]http://developer.51cto.com/art/200906/128609.htm
[6]黎活明.EJB3.0实用教程——企业应用开发核心技术.北京传智播客教育有限公司
[7]http://www.kuqin.com/baike/20090215/34968.html
[8]Goldberg D, Nichols D, OkiB M, etal. Using collaborative filtering to weave an information tapestry[J]. Communications of the ACM. December,1992, 35(12):61-70.
[9]Resnick P, Iacovou N, Suchak M, et al. GroupLens:an open architecture for collaborative filtering of netnews [C]. In:Proceedings of CSCW'94,1994, 175-186.
[10]Wu Yan, Shen Jie, Gu Tian zhu, et al. Algorithm for sparse problem in collaborative filtering [J]. Application Research of Computers,2007,24 (6): 94-97.
[11]Y Chuan, X Jie ping. Recommendation algorithm combining the user-based classified regression and the item-based filtering[C].In:Processing of the International Conference on Electronic Commerce, Proceedings-the new E-commerce:Innovations for Conquering Current Barriers, Obstacles and Limitations to Conducting Successful Business on the Internet,2006,574-578.
[12]Breese J, Hecherman D, Kadie C. Empirical analysis of predictive algorithms for collaborative filtering [C]. In:Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UA I'98),1998,43-52.
[13]Arwar B, Karypls G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms [C]. In:P roceedings of the 10th International World Wide Web Conference,2001,285-295.
[14]Kim BM, LiQ, Park CS, et al. A new approach for combining content-based and collaborative filters[J]. Journal of Intelligent Information System,2006,27 (1):79-91.
[15]Karypis G. Evaluation of item-based top-n recommendation algorithms [C]. In: Proc. of the Tenth International Conference on Information and Knowledge Management,2001,247-254.
[16]Deng Ai21in, Zhu Yang yong, Shi Bai le. A collaborative filtering recommendation algorithm based on item rating prediction[J]. Journal of Software,2003,14 (9):1621-1628.
[17]Adrwar B, Karypis G, Konstan J, et al. Analysis of recommendation algorithms for E-commerce [C]. In:Processing of 2nd ACM Conference on Electronic Commerce,2000,158-167
[18]Liu Qun. Researches into some key aspects of Chinese-English machine translation[D]. Peking University,2004,47-50.
[19]Zhang Guang wei, Kang Jian chu, Li He song, et al. Context based collaborative filtering recommendation algorithm [J].
[20]Chen Gang, Liu Fa sheng. Method for data mining based on BP neural network [J]. Computer and Modernization,2006,10:20-22.
[21]Jia Li hui, Zhang Xiu ru. Analysis and improvements of BP algorithm [J]. Computer Technology and Development,2006,10 (16):101-103,107.
[22]Kim BM, LiQ, Park CS, et al. A new approach for combining content-based and collaborative filters[J]. Journal of Intelligent Information Systems,2006,27 (1):79-91
[23]Jung K Y. User preference through Bayesian categorization for recommendation [C]. In:Pricai 2006:Trends in Artificial Intelligence, Proceedings,2006,4099: 112-119.
[24]Zhang S, Wang W H, Ford J, et al. Using singular value decomposition approximation for collaborative filtering[C]. In:Proceedings of 7th IEEE International Conference on E-commerce Technology,2005,257-264.
[25]Vozalis M G, Margaritis K G. Applying SVD on item-based filtering [C]. In: Proceedings of 5th International Conference on Intelligent Systems Design and Applications (ISDA'05) 2005,464-469.
[26]Charu C Aggarwal. On the effects of dimensionality reduction on high dimensional similarity search [C]. In:Proc.12th ACM SIG2 MOD2S IGACT2S IGART Symposium on Principles of Database:2001,256-266.
[27]Goldberg K, Roeder T, Gupta D. Eigentaste:a constant time collaborative filtering algorithm [J]. Information Retrieval,2001,4 (1):133-151.
[28]AlMamunur Rashid, Istvan Albert, Dan Cosley, et al. Getting to know you: learning new user preferences in recommender systems[C]. In:Proceedings of the 7th International Conference on Intelligent User Interfaces,2002.
[29]Lu Q Q, Huang G Q. A model of collaborative filtering in E-business recommendation system based on interest measure[C]. In:Processing of the 5th Wuhan International Conference on e-business, vols 1-3- Integration and Innovation Through Measurement and Management,2006,562-567.
[30]Tso K, Schmidt Thieme L. Attribute-aware collaborative filtering [J]. From Data and Information Analysis to Knowledge Engineering,2006,614-621.
[31]马宏伟,张光卫,李鹏.协同过滤推荐算法综述.小型微型计算机系统.2009年7月第7期Vol130 No.72009
[32]HALL P A V, DOWLING G R. Approximate string matching[J]. ACM Computer Survey,1980,12(4):381-402.
[33]WAGNER R A, FISCHER M J. The string-to-string correction problem[J]. Journal of the ACM,1973,21(1):168-173.
[34]章成志.基于多层特征的字符串相似度计算模型[J].情报学报,2005,24(6)：696-701.
[35]MONGE A E, ELKAN C P. The field matching problem:Algorithm and applications[EB/OL]. [2008-06-16]. http://www.cecs.csulb. edu/～monge/Papers/kdd96.ps.
[36]NIRENBURG S, DOMASHNEV C, GRANNES D J. Two approaches to matching in example-based machine translation[EB/OL]. [2008-06-16]. http://www.mt2archive.info/TMI219932Nirenburg.pdf.
[37]LIPSKY O, PORAT E. Approximate matching in the L∞metric [J]. Information Processing Letters,2008,105(4):138-140.
[38]MICHAILIDIS P D,MARGARITIS K G. Processor array architectures for flexible approximate string matching[J]. Journal of Systems Architecture,2008, 54 (1-2):35-54.
[39]余建明,徐波,薛一波.基于网络处理器的高速字符串匹配[J].清华大学学报：自然科学版,2008,48(4)：590-592.
[40]LEVENSHTEIN V L. Binary codes capable of correcting deletions, insertions and reversals[J]. Doklady Akademii Nauk SSSR,1966,163(4):707-710.
[41]LOWRANCE R, WAGNER R A. An extension of the string-to-string correction problem [J]. Journal of the ACM,1975,22(2):177-183.
[42]赵作鹏,尹志民,王潜平,许新征,江海峰.一种改进的编辑距离算法及其在数据处理中的应用.计算机应用.第29卷第2期2009年2月：424-426.
[43]严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社
[2]http://bci.bartercard.com/?page=about-bartercard
[3]http://baike.baidu.com/view/1381528.html?fromTaglist
[4]http://hi.baidu.com/lettoo/blog/item/ea2e871686cee11f962b435e.html
[5]http://developer.51cto.com/art/200906/128609.htm
[6]黎活明.EJB3.0实用教程——企业应用开发核心技术.北京传智播客教育有限公司
[7]http://www.kuqin.com/baike/20090215/34968.html
[8]Goldberg D, Nichols D, OkiB M, etal. Using collaborative filtering to weave an information tapestry[J]. Communications of the ACM. December,1992, 35(12):61-70.
[9]Resnick P, Iacovou N, Suchak M, et al. GroupLens:an open architecture for collaborative filtering of netnews [C]. In:Proceedings of CSCW'94,1994, 175-186.
[10]Wu Yan, Shen Jie, Gu Tian zhu, et al. Algorithm for sparse problem in collaborative filtering [J]. Application Research of Computers,2007,24 (6): 94-97.
[11]Y Chuan, X Jie ping. Recommendation algorithm combining the user-based classified regression and the item-based filtering[C].In:Processing of the International Conference on Electronic Commerce, Proceedings-the new E-commerce:Innovations for Conquering Current Barriers, Obstacles and Limitations to Conducting Successful Business on the Internet,2006,574-578.
[12]Breese J, Hecherman D, Kadie C. Empirical analysis of predictive algorithms for collaborative filtering [C]. In:Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UA I'98),1998,43-52.
[13]Arwar B, Karypls G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms [C]. In:P roceedings of the 10th International World Wide Web Conference,2001,285-295.
[14]Kim BM, LiQ, Park CS, et al. A new approach for combining content-based and collaborative filters[J]. Journal of Intelligent Information System,2006,27 (1):79-91.
[15]Karypis G. Evaluation of item-based top-n recommendation algorithms [C]. In: Proc. of the Tenth International Conference on Information and Knowledge Management,2001,247-254.
[16]Deng Ai21in, Zhu Yang yong, Shi Bai le. A collaborative filtering recommendation algorithm based on item rating prediction[J]. Journal of Software,2003,14 (9):1621-1628.
[17]Adrwar B, Karypis G, Konstan J, et al. Analysis of recommendation algorithms for E-commerce [C]. In:Processing of 2nd ACM Conference on Electronic Commerce,2000,158-167
[18]Liu Qun. Researches into some key aspects of Chinese-English machine translation[D]. Peking University,2004,47-50.
[19]Zhang Guang wei, Kang Jian chu, Li He song, et al. Context based collaborative filtering recommendation algorithm [J].
[20]Chen Gang, Liu Fa sheng. Method for data mining based on BP neural network [J]. Computer and Modernization,2006,10:20-22.
[21]Jia Li hui, Zhang Xiu ru. Analysis and improvements of BP algorithm [J]. Computer Technology and Development,2006,10 (16):101-103,107.
[22]Kim BM, LiQ, Park CS, et al. A new approach for combining content-based and collaborative filters[J]. Journal of Intelligent Information Systems,2006,27 (1):79-91
[23]Jung K Y. User preference through Bayesian categorization for recommendation [C]. In:Pricai 2006:Trends in Artificial Intelligence, Proceedings,2006,4099: 112-119.
[24]Zhang S, Wang W H, Ford J, et al. Using singular value decomposition approximation for collaborative filtering[C]. In:Proceedings of 7th IEEE International Conference on E-commerce Technology,2005,257-264.
[25]Vozalis M G, Margaritis K G. Applying SVD on item-based filtering [C]. In: Proceedings of 5th International Conference on Intelligent Systems Design and Applications (ISDA'05) 2005,464-469.
[26]Charu C Aggarwal. On the effects of dimensionality reduction on high dimensional similarity search [C]. In:Proc.12th ACM SIG2 MOD2S IGACT2S IGART Symposium on Principles of Database:2001,256-266.
[27]Goldberg K, Roeder T, Gupta D. Eigentaste:a constant time collaborative filtering algorithm [J]. Information Retrieval,2001,4 (1):133-151.
[28]AlMamunur Rashid, Istvan Albert, Dan Cosley, et al. Getting to know you: learning new user preferences in recommender systems[C]. In:Proceedings of the 7th International Conference on Intelligent User Interfaces,2002.
[29]Lu Q Q, Huang G Q. A model of collaborative filtering in E-business recommendation system based on interest measure[C]. In:Processing of the 5th Wuhan International Conference on e-business, vols 1-3- Integration and Innovation Through Measurement and Management,2006,562-567.
[30]Tso K, Schmidt Thieme L. Attribute-aware collaborative filtering [J]. From Data and Information Analysis to Knowledge Engineering,2006,614-621.
[31]马宏伟,张光卫,李鹏.协同过滤推荐算法综述.小型微型计算机系统.2009年7月第7期Vol130 No.72009
[32]HALL P A V, DOWLING G R. Approximate string matching[J]. ACM Computer Survey,1980,12(4):381-402.
[33]WAGNER R A, FISCHER M J. The string-to-string correction problem[J]. Journal of the ACM,1973,21(1):168-173.
[34]章成志.基于多层特征的字符串相似度计算模型[J].情报学报,2005,24(6)：696-701.
[35]MONGE A E, ELKAN C P. The field matching problem:Algorithm and applications[EB/OL]. [2008-06-16]. http://www.cecs.csulb. edu/～monge/Papers/kdd96.ps.
[36]NIRENBURG S, DOMASHNEV C, GRANNES D J. Two approaches to matching in example-based machine translation[EB/OL]. [2008-06-16]. http://www.mt2archive.info/TMI219932Nirenburg.pdf.
[37]LIPSKY O, PORAT E. Approximate matching in the L∞metric [J]. Information Processing Letters,2008,105(4):138-140.
[38]MICHAILIDIS P D,MARGARITIS K G. Processor array architectures for flexible approximate string matching[J]. Journal of Systems Architecture,2008, 54 (1-2):35-54.
[39]余建明,徐波,薛一波.基于网络处理器的高速字符串匹配[J].清华大学学报：自然科学版,2008,48(4)：590-592.
[40]LEVENSHTEIN V L. Binary codes capable of correcting deletions, insertions and reversals[J]. Doklady Akademii Nauk SSSR,1966,163(4):707-710.
[41]LOWRANCE R, WAGNER R A. An extension of the string-to-string correction problem [J]. Journal of the ACM,1975,22(2):177-183.
[42]赵作鹏,尹志民,王潜平,许新征,江海峰.一种改进的编辑距离算法及其在数据处理中的应用.计算机应用.第29卷第2期2009年2月：424-426.
[43]严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社