基于改进LSH的协同过滤推荐算法

摘要/Abstract

摘要： 协同过滤是个性化推荐系统中应用较为成功与广泛的技术之一,影响协同过滤推荐质量的关键在于获取目标用户的k近邻用户,然后基于k近邻对其未评价的项目进行评分预测与推荐。针对用户评分数据的规模大、维度高、高度稀疏以及直接进行相似性度量的实时性差等对推荐性能的影响,提出一种基于LSH的协同过滤推荐算法,并对其进行改进。该算法基于p稳态分布的局部敏感哈希对用户评分数据进行降维与索引,并采用多探寻的机制对其进行改进,缓解多个哈希表对内存的压力,快速获取目标用户的近邻用户集合,然后采用加权方法来预测用户评分并产生推荐。标准数据集上的实验结果表明,该方法能有效克服评分数据的高维稀疏,并在保证一定推荐精度的前提下,大幅度提高推荐效率和降低内存消耗。

关键词: 推荐系统,近似近邻,协同过滤,相似性度量,局部敏感哈希

Abstract: Collaborative filtering is one of the key technologies widely applied in personalized recommendation system with great success.The critical step of collaborative filtering is to get k nearest neighbors (kNNs),which is utilized to predict user ratings and recommend.In order to improve the recommendation quality which is affected by the matter that rating data is characterized by its large scalability,high dimensionality,extreme sparsity,and the lower real-time ability by direct similarity measuring method in finding the nearest neighbors,we proposed a collaborative filtering re-commendation algorithm based on locality-sensitive hashing,and improved it.The algorithm applies locality-sensitive ha-shing technology based on p-state distribution to get lower dimensionality and index for large rating data.Then a multi-probe mechanism is utilized to improve the algorithm with great efficiency in obtaining the approximate nearest users of target user.Then,a weighted method is used to predict the user ratings,and finally perform collaborative filtering recommendation.Experiment results on typical dataset show that the proposed algorithm can overcome the limitation of high dimensionality and sparsity in some degree,and has good recommendation performance,high efficiency and less memory consumption.

Key words: Recommendation system,Approximate nearest neighbor,Collaborative filtering,Similarity measuring,Locali-ty-sensitive hashing

李红梅,郝文宁,陈刚. 基于改进LSH的协同过滤推荐算法[J]. 计算机科学, 2015, 42(10): 256-261. https://doi.org/

LI Hong-mei, HAO Wen-ning and CHEN Gang. Collaborative Filtering Recommendation Algorithm Based on Improved Locality-sensitive Hashing[J]. Computer Science, 2015, 42(10): 256-261. https://doi.org/

参考文献

[1] 孟祥武,胡勋,王立才,等.移动推荐系统及其应用[J].软件学报,2013,24(1):91-108 Meng Xiang-wu,Hu Xun,Wang Li-cai,et al.Mobile Recommender Systems and Their Applications[J].Journal of Software,2013,4(1):91-108
[2] 罗辛,欧阳元新,熊璋,等.通过相似度支持度优化基于K近邻的协同过滤算法[J].计算机学报,2010,33(8):1437-1445 Luo Xin,Ouyang Yuan-xin,Xiong Zhang,et al.The Effect of Similarity Support in K-nearest-neighborhood Based Collaborative Filtering[J].Chinese Journal of Computers,2010,3(8):1437-1445
[3] Deng A L,Zhu Y Y,Shi B L.A collaborative filtering recommendation algorithm based on item rating prediction[J].Journal of Software,2003,14(9):1621-1628
[4] Zheng S,Wang W H,Ford J,et al.Learning from incompleteratings using non-negative matrix factorization[C]∥Ghosh J,ed.Proc.of the 6th SIAM Conf.on Data Mining.Bethesda:SIAM,2006:549-553
[5] 韦素云,业宁,朱健,等.基于项目聚类的全局最近邻的协同过滤算法 [J].计算机科学,2012,39(12):149-152Wei Su-yun,Ye Ning,Zhu Jian,et al.Collaborative filtering re-commendation algorithm based on item clustering and global similarity [J].Computer Science,2012,39(12):149-152
[6] Anand D,Bharadwaj K K.Utilizing various sparsity measures for enhancing accuracy of collaborative recommender systems based on local and global similarities [J].Expert Systems with Applications,2011,38(5):5101-5109
[7] Goldberg K,Roeder T,Gupta D,et al.Eigentaste:a constant time collaborative filtering algorithm [J].Information Retrieval,2001,4(2):133-151
[8] 曾小波,魏祖宽,金在弘.协同过滤系统的矩阵稀疏性问题的研究[J].计算机应用,2010,30(4),1079-1082 Zeng X B,Wei Z K,Jin Z H.Research of matrix sparsity for collaborative filtering[J].Journal of Computer Applications,2010,30(4):1079-1082
[9] 方耀宁,郭云飞,丁雪涛,等.一种基于局部结构的改进奇异值分解推荐算法[J].电子与信息学报,2013,35(6):1284-1289 Fang Y N,Guo Y F,Ding X T,et al.An improved singular value decomposition recommender algorithm based on local structures[J].Journal of Electronic & Information Technology,2013,35(6):1284-1289
[10] Cai Rui,Zhang Chao,Zhang Lei,et al.Scalable Music Recommendation by Search [C]∥International Multimedia Confe-rence.2007:1065-1074
[11] Andoni A,Indyk P.Nearest-optimal hashing algorithms for approximate nearest neighbor in high dimensions[J].Communications of the ACM,2008,1(1):117-122
[12] 高毫林,彭天强,李弼程,等.近似最近邻搜索算法——位置敏感哈希[J].信息工程大学学报,2013,14(3):332-340 Gao H L,Peng T Q,Li B C,et al.Approximate nearest neighbor searching algorithm—locality sensitive hashing[J].Journal of Information Engineering University,2013,14(3):332-340
[13] Slaney M,Casey M .Locality-sensitive Hashing for Finding Nearest Neighbors [J].IEEE Signal Processing Magazine,2008,8(3):128-131
[14] Indyk P,Motwani R.Approximate nearest neighbors:towardsremoving the curse of dimensionality[C]∥The Symposium on Theory of Computing.1998:604-613
[15] Datar M,Indyk P,Iimmorlica N,et al.Locality-Sensitive Ha-shing scheme Based on p-stable Distributions [C]∥Proceedings of the Twentieth Annual Symposium on Computational Geometry.2004:253-262

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed