协同过滤推荐算法综述

基于协同过滤的推荐算法综述

Survey of Collaborative Filtering Based Recommedation Algorithm

论文作者                        

院    系                  

课    程                      

学    号                    

指导老师                        

完成日期              

基于协同过滤推荐算法综述

**

（首都师范大学 **学院 ，北京 100048）

摘 要：在当今这个电子商务时代，推荐系统越来越受到重视和普及。其中，基于协同过滤的推荐是目前应用最广泛的系统。本文首先将介绍协同过滤的基本概念和原理，其次会展示当前主流的几种基于协同过滤推荐算法，并指出这些算法相应的优点，最后，对此类算法的问题及对策进行说明。

关键词：协同过滤   推荐   电子商务

Survey of Collaborative Filtering Based Recommedation Algorithm

ZHOU Tian

（College of Information Engineering,Capital Normal University, BeiJing  100048）

Abstract： Recommander system becomes more and more important and popular in this E-commerce Age.Among them,Collaborative Filtering Recommendation is the most widely used now.This paper first introduce the basic concept and principle of Collaborative Filtering.Then, shows some mainstream method and points out the corresponding advantages.At last, it presents some problems and solutions of this algorithm.

Keywords：Collaborative Filtering, Recommendation Algorithm,E-commerce

一．引言

近20年，网络飞速发展，随之而兴起的是电子商务的崛起，一些大的网络购物网站慢慢出现。在日常生活中，越来越多的人逐渐适应了这种便捷的购物方式。就商家而言，如何为用户提供适合自己的商品是一个必须要解决的问题。在这种背景下，推荐系统应声而出[2]。所谓推荐，就是从复杂的系统或商品中，为用户选择出适合用户，并且用户喜欢的信息或者商品。推荐系统是一个比较复杂的过程，它包括了四个步骤：数据采集；数据与处理；形成推荐；结果显示[1]。主流的推荐算法有基于内容的推荐，基于协同过滤的推荐，基于知识的推荐等。这其中，本文介绍的基于协同过滤的推荐算法应用的最广，同时也具有最好的应用前景。协同过滤的概念是由Goldberg、Nicols、Oki以及Terry在1992年首次提出的[3]，其中心思想是：对于某个用户，如果其他邻居用户与他有着相近的喜好，那么邻居用户喜欢的东西，他也可能喜欢。因此，协同过滤技术适用于用户群量少兴趣密度高而用户评价信息较多的系统。Schafer称协同过滤推荐为“人与人的相关性推荐”[4]。它最大的优点就是，对推荐对象没有特殊的要求，能处理音频、视频等非结构化的复杂对象。这个算法是基于一个假设的，要求找到用户的邻居，然后根据邻居选择的东西来对用户进行推荐[5]。本文将介绍几种现在应用最多的协同过滤推荐算法，之后还要分析一下此类算法的问题和对策。

二．基础的协同过滤的推荐算法

1.基于用户的协同过滤推荐算法

此算法是目前应用最广的个性化推荐技术，它的中心思想是将具有相同爱好的用户感兴趣的项目推荐给目标用户。如果一个用户与目标用户相邻，则可以根据此用户的喜好来对目标用户进行推荐或者预测目标用户对某项目的喜好程度[3]。

基于用户的协同过滤推荐算法可以分为三个步骤：

（1）构建用户—项目评价矩阵[6]

用一个M*N的矩阵来表示M个用户对N个项目的看法或者喜爱程度，在矩阵中的每个元素rij表示的是第i个用户对第j个项目的喜爱程度。

（2）产生邻居

这是基于用户的协同过滤推荐算法的核心部分。通过计算系统中所有用户的相似度，为目标用户生成最近的K个邻居。计算用户相似度的方法共有三种[7]：

1余弦相似性：

用户对项目的评价可以看做在空间中的N维向量，两个用户的相似性可以通过二者向量夹角的余弦体现出来

用户i与用户j的相似性sim(i,j)用向量夹角余弦表示，||||表示i向量的模[8]。

2皮尔森（Pearson）相关系数[8,9]：

这种方法是在用户共同评分项目的基础上衡量二者的相似度，设Iij为用户i与用户j共同评分的项目集，二者的相似性系数表示如下：

ric表示用户i对项目c的评分， i与j分别表示用户i和用户j对项目的平均评分。通过大量的实验表明，皮尔森能很好的衡量用户或者项目的相似程度。

3修正的余弦相似度[8]

余弦相似度方法没有考虑到不同用户的评价尺度问题，在修正后的方法中改进了这一点，同时将用户i与用户j的评价项目集合考虑在内，算法如下：

ric表示用户i对项目c的评分， i与j分别表示用户i和用户j对项目的平均评分。

可以通过以上的三种方法来找出目标用户的邻居。

（3）产生推荐

目标用户的“最近邻居”集产生后，可以计算目标用户对项目的评价集，根据邻居喜爱的项目进行推荐，可用到TOP-N算法[2]，此处不详述。

基于用户的协同过滤推荐算法很容易让人理解，与其他算法相比较具有较强的推荐精度，而且它可以推荐视频，图片等项目[10]。在这个系统中，所有用户都可以从邻居的反馈中受益，形成了一个良性循环。它也可以挖掘出用户的潜在兴趣。因此，在实际应用中此类算法比较实用。

2.基于项目的协同过滤推荐算法

一般情况下，网站用户数量增长比较快，而待评价项目比较稳定，因此计算出的项目相似度矩阵的更新频率比较低，所以此矩阵可以使用较长时间。基于项目的协同过滤推荐算法认为，用户对不同项目的评分具有相似性，先计算项目之间的相似性，当需要估计用户对某一项目的评分时，可以参照用户对其他项目的评分来进行判断[11]。

和基于用户的协同过滤推荐算法相似，该算法也分为三步：

（1）建立用户—项目矩阵

M表示有m个用户，n为项目数量，矩阵中的Rij表示用户i对项目j的评价，可选取一定的范围数字表示。

（2）获取目标用户邻居

根据用户—项目矩阵，计算目标项目与其他项目的相似度，获得目标项目的项目邻居列表，其中，项目的相似度可根据上文提到的余弦相似性，皮尔森相似系数以及修正的余弦相似系数计算出来，从而采用TOP-N算法产生最近邻居集[2]。

（3）进行推荐

根据邻居对项目的评分来预测目标用户对项目的评分，可采用下面的一个公式：

U为邻居用户集，sim(T,n)表示目标项目与最近邻居的相似性，Ru, n表示用户u 对项目n 的评分; RT 和Rn 分别表示对项目T 和项目n的平均评分[11]。

基于项目的协同过滤推荐技术可以对基于一些复杂的，难以表达的概念（信息质量、品位)进行过滤，同时也可以推荐一些新特性。

3.基于项目与用户组合的协同过滤推荐算法

针对稀疏矩阵的问题，此算法将用户与项目结合起来，预测稀疏矩阵中的未知项。在这个过程中，不仅考虑到了用户之间的关联性，也考虑到了项目之间的关联性，对用户未评分的项目进行预测，有效提高了推荐的精度[12]。

此算法可分为三个基本步骤组合加权的矩阵补缺，虚拟预测评分和综合预测[13]。

（1）组合加权的矩阵补缺

组合评分包括用户与项目评分，考虑到不同用户对同一项目评分的差异性以及不同项目所获得的评分用户数目的不一致，使用加权平分：

Ri,j   =   

其中的Ri和Rj分别表示用户与项目的平均评分，最终的结果Ri,j是组合之后用户i对项目j的评分[12]。

（2）虚拟预测评分

经过第一步的补缺，评分矩阵已经不再是一个稀疏矩阵了，但这个矩阵并没有体现出来目标用户与各个用户之间的相似度，使用如下公式继续修正，得到一个虚拟的预测评分矩阵。

其中，u∈N,N 为最近邻居集，Rau,i表示目标客户a 的最近邻居集内的用户u 对项目i 的预测值，Ra和Ru分别表示目标用户a 和最近邻居集内用户u 的平均评分，sim(u,a)表示目标用户a 和邻居集内用户u 的相似度[14]。

（3）综合预测

综上两步得到了一个修正的预测评分矩阵，再根据基于用户的协同过滤算法中的相关算法得出邻居集，并对目标用户进行推荐。

该算法有效提高了推荐效率，比前两种推荐算法更加好用。目前的推荐算法，大多都对上述三种方法进行了改进，例如采用聚类技术[10]，可以有效地减少运算量，让用户在与自己相近的类中寻找邻居，比较快捷[15]。当然，基于协同过滤推荐算法也有不少缺点，下面就介绍一下主要缺点。

三．协同过滤推荐算法的问题及解决办法

1.稀疏性问题

这是推荐系统面临的主要问题。在实际的电子商务系统中有成千上万的商品，而在这些商品中，被用户评价过的哪怕是只有很少的评价的商品通常只占了不到1%，导致了用户—项目矩阵稀疏【16】。在计算相似度的时候，需要考虑两个用户对同一项目的评分，这样，在寻找目标用户的邻居时十分不准确，进而影响到推荐，算法甚至找不到商品进行推荐。

目前，解决稀疏性的一种方法是维规约技术【2】，采用奇异值分解方法删除那些不重要的或噪音用户和项目，降低评分矩阵维数，采用潜在语义索引技术将两个用户投影到一个低维空间上，进而计算二者相似度。维规约技术一方面可以提高算法效率，另一方面通过充分挖掘隐含在数据中的潜在模式。

采用矩阵填充技术【3】或者在系统中嵌入自动关联评分系统也是可以的，这两种方法都可以使矩阵不再稀疏，但是适用场合有一定的。

2.冷启动问题

在一个系统中，如果有一个新用户加入，但是系统中没有此用户的浏览或购买信息，甚至连该用户的浏览信息都没有，则无法进行推荐。考虑另外一种情况，一个新项目的加入，同样，没有用户对新项目进行过评价，因此，这个新项目无法被推荐出去。这两种情况成为冷启动问题【17】，冷启动问题大大影响了电子商务的推荐进度。

为了解决冷启动问题，普遍采用基于内容的最近邻居查找技术【3】，其基本思想是：

利用聚类技术将用户按照属性相似性聚类，从项目属性的角度找到新项目的最近邻居；

用新项目K的所有最近邻居的平均评分来代替已有评分的平局值Rk。

3.可扩展性问题

现在的电子商务系统，随着时间的变化，用户数量和商品数量增长迅速，随之而来的影响是导致了推荐算法的效率下降，而电子商务系统的实时性要求较高，推荐系统面临着巨大的可扩展性问题【18】。

通常可以采用聚类、降维、分类技术来解决这种问题。使用聚类技术可以大大缩小用户或项目的最近邻居搜索范围从而提高推荐的实时性。EM算法通过估计用户或项目属于某一类的概率对用户或项目进行聚类；k-means算法通过用户对项目评分的相似性对项目进行聚类并生成相应的聚类中心, 然后计算目标项目与各聚类中心的相似度, 选出与目标项目相似度最高的k 个聚类中心对应的聚类, 在这k 个聚类中搜索目标项目的最近邻居, 从而达到在尽量少的项目空间中找到目标项目的大部分最近邻居【3】。还有模糊聚类【3】方法也可以解决此类问题。

4.其他问题

除了上述的几个问题之外，推荐系统还面临着许多问题【2】，如托攻击问题、隐私问题，许多用户并不乐意提交自己的数据。可以通过提升推荐系统的信誉度，并建立和采取相应的隐私保护制度来保护用户的隐私数据。在实际应用中，由于人的灵动性，导致算法不可能完全符合用户的心思，这也是可以理解的。

四．结束语

经过20多年的发展，推荐技术取得了长足的进步，随着应用领域的不断拓展，讲其他领域技术与推荐技术相结合将会是一个研究热点，并且具有十分广阔的应用前景。推荐系统技术的发展离不开各种困难和挑战，我们要不断开拓进取，使推荐技术朝着更智能，更优化的方向发展。

参考文献

1Wu Heng-liang,Zhang Wei-wei.Comparative Reserch about Recommadation Techniques in E-commerce Recommendation System[J].Logistics,2009,No.11:57-59.

2Yang Bo,Zhao Peng-fei.Survey of Recommendation Algorithm[J].Journal of Shanxi University(Nat.Sci.Ed.),2011, 34-3:337-350.

3Ma Hong-wei,Zhang Guang-wei,Li Peng.Survey of  Collaborative Filtering Algorithms[J].Journal of Chinese Computer Systems,2009,Vol.30,No.7:1282-1288.

4Li Xing-xing,Huang Xiao-qin,Zhu Qing-sheng.An Exploration of the Recommender Systems in E-Commerce[J].COMPUTER ENGINEERING&SCIENCE, 2004,Vol.26,No.5:7-10.

5You Wen,Ye Shui-sheng.A Survey of Collaborative Filtering Algorithm Applied in E-commerce Recommender System[J].COMPUTER TECHNOLOGY AND DEVELOPMENT,2006,Vol.16,No.9:70-72.

6Zhou Qiang.Researches into Recommendatory Algorithm of Coordinated Filtration in View of Consummers[J].Journal of Nanchang Junior College,2006,No.3:88-.

7Lu Pei.An Improved Project Clustering-Based Collaborative Filtering Recommendation Algorithm[J].Public Communication of Science&Technology,2011,No.1:205-206.

8Tao Jun,Zhang Ning.Collaborative Filtering Algorithm Based on Interest-Class[J].Computer Systems&Applications,2011,No.5:55-59

9Chen Zhi-min,Li Zhi-qiang.Collabrative Filtering Recommendation Algorithm based on user characteristics and item attributes[J].Journal of Computer Applications,2011,No.7:1748-1755.

10Xia Jian-xun.Technology of Collaborative Filtering Recommedation base on user[J].Market Modernization,2009,No.9:178-179.

11Fu He-gang,Wang Zhu-wei.Improvement of Item-Based Collaborative Filtering Algorithm[J].Journal of Chongqing University of Techonology(Natural Science),2011,No.9:69-74.

12Yan Zhou,Shi Liu-hong.An Improved Collaborative Filtering Algorithm Base on Combining User with Item[J].Computer Knowledge and Technology,2011,No.16:3969-3971.

13Shi Hua.Item-Based and User-Based double clustering Collaborative Filtering Recommendation Algorithm[D].Changchun:Dongbei Normal Univesity,2009:20.

14Wang Hui-min,Nie Gui-hua.Research on Collaborative Filtering Algorithm Based on Fusing User and Item’s Correlative Information[J].Journal of Wuhan University of Technology,2007,No.7:160-163.

15Zha Wen-qin,Liang Chang-yong,Cao Lei.Collaborative Filtering Recommendation Method Based on Clustering of Users[J].COMPUTER TECHONOLOGY AND DEVELOPMENT,2009,No.6:69-75.

16Xu Min,Qiu Yu-hui.On Study of the Issues and Corresponding Countermeasures of Current Recommender Systems[J].Computer Science,2001,No.4:122-124.

17Wu Yue-ping,Zheng Jian-guo.Improved Collaborative Filtering Recommendation Algorithm[J].Computer Engineering and Design,2011,No.9:3019-3021.

18Yang Huai-zhen,Cong Xiao-qi,Liu Mei-lian.Research of Collaborative Filtering E-commerce Recommendation System’s Modeling[J].China Management Informationization,2008,No.21:96-98.