协同过滤算法的研究

引言

二十一世纪互联网的迅猛发展,把人们推向了一个信息爆炸的时代。基于互联网的系统相比于过去，数据量每时每刻都在迅速地增长。用户从海量的信息中挑选自己需要的信息，将变得愈加困难。为了使用户能够感受到良好的体验从而吸引更多的用户，面向用户的系统需要对海量信息进行筛选、过滤，预测用户最可能关注和感兴趣的信息并呈现在用户面前。这即提高了系统工作的效率，也节省了用户筛选信息的时间。因此对信息的筛选和过滤成为一个系统重要组成部分。搜索引擎可以在一定程度上解决信息筛选问题，但还远远无法满足需求。搜索引擎需要用户提供关键词来对信息进行筛选。但当用户无法准确描述自己的需求时，捜索引擎的筛选效果将大打折扣。在此背景下，推荐系统出现了，推荐系统的任务就是解决上述的问题。

1协同过濾系统

协同过滤系统是第一代被提出并得到广泛应用的推荐系统，其最大的优点是对推荐对象没有特殊的要求，能处理音乐、电影等难以进行文本结构表示的对象。其原理就是利用已知的物品信息和用户打分信息，去预测某用户对某物品的打分,并根据预测的分数来决定是否向用户推荐该物品。设U={U1，"2，…，Un}为所有用户集合,S={S1，S2,…，sN}为所有物品的集合，5为用户"对物品s的打分，而这个打分是未知的，需要通过协同过滤系统的算法去预测。得到了预测分数后，再根据此预测分数所在的分数区间，判断用户是否有可能对该物品感兴趣。若经过判断，用户可能对该物品感兴趣，贝懵该物品推荐给用户。

协同过滤系统的算法可以分为两类:一是基于用户(User-Based)的算法，二是基于物品(Item-based)的算法。

2基于用户(User-Based)的协同过濾算法

基于用户的算法以用户为出发点，先根据已打过分的物品信息计算用户U与其他用户之间的相似度，得到最为邻近的k个用户，将这k个用户的集合标记为U，然后根据相似度加权得到5。用sim(u,u)表示两用户之间的相似度,Pu.s表示预测的分数，则最通用的加权预测公式：

公式中用户u和u越相似，sim(u,u)的值越大，从而饥将具有更大的权重用于计算用户可能的打分Pu,s。

最常用的计算相似度的方法有明考斯基(Minkowski)距离法、Pearson相关系数法和Cosine相似性法。

2.1明考斯基(Minkowski)距离法

明考斯基距离法非常直观，且易于计算，复杂度较低。距离越短，说明用户x和y之间的相似度越高。用户x和y之间的明考斯基距离公式：

由于在明考斯基距离法中，距离值越小，表示两用户越相似，因此在利用上述预测公式时，需要对距离进行一步转换：

通过转换，便可得到相似度值，并满足预测公式的对相似度值的要求。

2.2Pearson相关系数法

在实际中，不同用户给物品打分的习惯不同：有的人会避免极端分数(避免最高和最低分);有的只在某个分数段内打分。这会导致不同用户对同一产品打的分数所代表的意义不同。在这种情况下，直接利用明考斯基距离法，可能会无法如实反映用户之间的相似度。利用Pearson相关系数表示相似度,可以解决明考斯基距离法隐含的缺陷，有效的解决用户打分习惯不同这一问题。

Pearson相关系数的值在［-1，1］之间变化。1表示相似度最高，-1表示相似度最低。

但是上述公式有一个严重的缺点：需要多趟遍历数据。这大大提高了算法的时间复杂度。因此一般釆用下述的Pearson相关系数的近似公式：

式中：Sxy 表示用户 x 和 y 共同打分的物品的集合，card（Sxy）为集合 Sxy 中元素的个数。该近似公式看似复杂，但只需遍历一遍数据即可，因此，一般用此近似公式来计算 Pearson 相关系数。

2.3Cosine相似性

计算相似性时，只会用到用户共同打分的产品的信息，其余产品信息，在计算两个用户之间相似性时是必须抛弃的，因此上述两种方法必须首先找到两个用户共同打分的物品，才能计算相似度。在许多系统中，单个用户只会给庞大的物品集合中有限的物品打分。此时，若采用上述两种方法，会有大量操作和时间用在查找两用户共同打分的物品上。

Cosine相似性法［3,8］可以有效的解决上述问题。在Cosine相似性法中，用户x和y都用n(n为全部物品的个数)维向量表示x,y,向量的元素为用户对所有产品的评分，若用户对该产品没有打分，则用零值表示。因此用户之间的相似性可用它们对应的向量之间的余弦值表示：

其中x·y表示两个向量的点积，S为整个物品集合。在计算过程中，由于乘法的作用，会自然消除两用户没有共同打分的物品对相似度计算的影响。由于不必专门去查找两用户共同打分的物品，这极大地提高了效率，因此该算法非常适用于有效数据非常稀疏的情形。

基于用户的协同过滤算法利用两两用户之间的相似度来做出预测，相似度算法的选择决定了预测的精度。上述三种计算相似度的方法是最常见，此外还有许多其它已被提出的计算相似度的方法。

3基于物品(Item-Based)的协同过濾

基于用户的协同过滤算法在过去已经取得了很大的成功，但随着它的广泛应用，渐渐发现了两方面的主要问题:

一是规模性：获得最邻近用户的计算量随着用户数和物品数的增加而迅速上升。有着百万用户和物品的网络推荐系统在使用基于用户的协同过滤算法时将遇到非常严重的规模性问题。

二是稀疏性：许多商业推荐系统(例如，亚马逊图书推荐系统)拥有巨大的物品集合。即使最活跃的用户购买书的数量也不到所有书籍总量的1%。。所以，用户很有可能与其他任何用户都没有共同打分的书籍。在这样的情况下，基于用户的推荐系统很有可能无法给一个用户做出任何推荐。

此外，基于用户之间相似度的方案需要实时计算相似度。而且，计算相似度要求必须已知最少数量的物品打分，如果已知的数据太少，计算相似度的结果会非常不准确，进而无法给用户做出合理的推荐。

3.1AdjustedCosine相似性

基于物品的协同过滤算法一般也需要计算相似度，但是与基于用户的协同过滤算法的不同之处在于：前者计算的是物品之间的相似度，而后者计算的是用户之间的相似度。计算物品的相似度，也可以利用上述的Cosine相似性算法，但是利用Cosine相似性算法有一个严重的缺点：没有考虑不同用户打分习惯的不同。而AdjustedCosine相似性算法作为Cosine相似性算法的改进，通过减去相应用户打分的平均值，来消除Cosine相似性算法的缺陷。利用AdjustedCosine相似性算法计算物品i和j之间的相似度的公式为：

其中云为用户u的所有打分平均值。根据物品之间的相似度得到最相似物品集合i后，利用加权方式预测用户u对物品i的打分:

3.2Slopeone

Slopeones算法既使用了两两物品的打分的相对关系信息，也使用了用户对除待预测物品以外其他物品的打分信息。Slopeone算法可以被分成两个部分：一、事先（在用户访问量较少的时刻，如午夜）计算出两两物品之间打分的偏差;二、预测用户对待预测物品的打分。Slopeone算法有多种，其中WeightedSlopeone算法是比较常用的。

计算物品i相对于物品，的打分偏差公式：

用WeightedSlopeone方法预测用户u对物品j的打分公式为：

式中：j表示对物品i和j都打过分的用户集合，cji=card（Uj表示集合Uj中用户的数量。

Slopeone算法在有着较高精确度的前提下，具有易实现、复杂度低的优点。最关键的是，Slopeone算法的第一步是可以在系统空闲的时刻提前计算的，这大大降低了查询时刻的计算量，极大地提高了系统的推荐效率。

基于物品的协同过滤算法利用物品之间的关系，很好地解决了上述基于用户的协同过滤算法的稀疏性问题，且Slopeone算法中物品之间的打分偏差都在事先计算出来，在一定程度上解决了基于用户的协同过滤算法的规模性问题。

4结语

协同过滤系统中每种算法都有其最适用的场合，综合各种算法，协同过滤系统有着非常广泛的应用。构建协同过滤系统时，应该仔细分析系统的数据特点，综合考量各种算法的优缺点，选择最适合的。但是，协同过滤系统算法也存在着共同的制约问题。随着数据量的增大，使用各种算法构建的系统都面临计算负荷越来越大的问题。比较可行的方案是设计某种近似的动态算法，每次都利用到以前的计算结果，而不需要完全重新的计算。关于这方面算法的研究若取得进展，则可以极大地提高推荐系统的效率。

20211121_619a03831ebe1__协同过滤算法的研究