笔记：协同过滤推荐算法

随着电子商务的兴起，推荐系统得到了广泛的应用，同时也推进了对推荐算法的研究。例如：淘宝、京东、Amazon等都采用了智能的推荐系统。协同过滤（Collaborative filtering）算法是诞生最早的一种推荐算法，并被广泛采用。其主要思想是“利用群众的智慧”对信息进行过滤和筛选。协同过滤相对于集体智慧而言，它从一定程度上保留了个体的特征。一般来说，协同过滤推荐分为三种类型。第一种是基于用户(user-based)的协同过滤，第二种是基于项目(item-based)的协同过滤，第三种是基于模型(model based)的协同过滤。

协同过滤算法理论基础

一、几种常用的相似度计算方法

欧几里得距离（Euclidean Distance）

欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

二维空间下欧几里得公式 \[ d(x, y) = \sqrt{x^2+y^2} \]

皮尔逊相关系数（Pearson Correlation Coefficient）

皮尔逊相关系数一般用于计算两个定距变量间联系的紧密程度，它的取值在 [-1，+1] 之间。

下面给出基于用户的相似度计算公式

\[ p(x, y) = \frac{\sum_{i\in I(x)\cap I(y)}(r_{xi}-\overline{r_x})(r_{yi}-\overline{r_y})}{\sqrt{(r_{xi}-\overline{r_x})^2}\sqrt{(r_{yi}-\overline{r_y})^2}} \]

p(x, y)表示的是用户x, y之间基于皮尔逊相关系数的相似度，I(x)表示拥护x标z注的所有项目集合，I(y)表示用户y标注的所有项目集合, \(r_{xi}\) 表示用户x对项目i的标注，\(r_{yi}\) 表示用户y对项目i的标注，、表示用户x, y在所有项目上标注的均值。

类似的，我们也可以得到基于项目的相似度计算。

Cosine 相似度（Cosine Similarity）

计算个体间的相似程度，相似度度量的值越小，说明个体间相似度越小，相似度的值越大说明个体差异越大。广泛应用于计算文档数据的相似度。 \[ T(x, y) = \frac{\overrightarrow{x} \cdot \overrightarrow{y}}{\|\overrightarrow{x}\|\times\|\overrightarrow{y}\|} \]

杰卡德相似性度量（Jaccard Similarity）

两个集合的交集在该两个集合的并集所占的比例来度量两个集合的相似度。举例，新闻A和新闻B提取出词语集合的交集在新闻A和新闻B提取出词语集合的并集所占的比例就是AB的相似度。

二、求最近邻居

知道了相似度的计算方法后，我们还需要知道如何根据相似度找到用户-物品邻居，一般取出其中的K个。

三、计算推荐

User CF（基于用户的）

通常这些算法都可以总结成三步：

首先，使用用户已有的评分来计算用户之间的相似度；
然后，选择与目标用户相似度最高的K个用户，通常把这些用户称为邻居；
最后，通过对邻居用户的评分的加权平均来预测目标用户的评分。

Item CF（基于物品的）

基于物品的 CF 的原理和基于用户的 CF 类似，只是在计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似的物品，然后根据用户的历史偏好，推荐相似的物品给他。从计算的角度看，就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的物品，计算得到一个排序的物品列表作为推荐。图 3 给出了一个例子，对于物品 A，根据所有用户的历史偏好，喜欢物品 A 的用户都喜欢物品 C，得出物品 A 和物品 C 比较相似，而用户 C 喜欢物品 A，那么可以推断出用户 C 可能也喜欢物品 C。

主要分为两步：

计算物品之间的相似度；
根据物品的相似度和用户的历史行为给用户生成推荐列表。

推荐项目集产生:目标用户的最近邻居集产生后,可以得出目标用户对未评分项的预测分,将分值按照高低排列,产生TOP-N的推荐项目集合

四、协同过滤算法的不足

1、数据稀疏性问题

数据稀疏性问题是协同协同过滤算法面临的最大挑战，在实际的商业推荐系统中，用户和项目的数量十分的庞大,而用户往往只在很少的项目上有评分记录，这就导致了评价矩阵是非常稀疏的。在数据稀疏的情况下,由于共同标注的数量过少，一方面难以找到最近邻居用户集，另一方面进行相似性计算的耗费也会很大。在有的推荐系统中,用户的数量远远少于项目的数量,这就导致了许多项目从未被标注过,从而无法对这些项目进行推荐。

降维法解决这类问题的重要手段，常采用矩阵奇异值分解（SVD）和主成分分析（PCA）

2、冷启动问题( cold start problem)

是数据稀疏问题的另外一种表现，也称为新用户问题(new user problem)或者新项目问题( new item problem),在实际的推荐系统中，用户和项目的数量的增长速度都较快，这就意味着不断的有新的用户和项目加入到系统中,当新用户或项目刚加入系统时，由于缺乏对应的标注信息，导致无法对这些用户或项目进行推荐。目前，在协同过滤的相关研究工作，已经存在着相当一部分工作来解决数据稀疏性的问题。

3、可扩展性问题

在许多实际应用中，用户和项目数量的增长速度都非常快，由于计算资源和计算速度的限制,传统协同过滤算法在用户和项目的数量增长到一定程度时，效率将大大降低，以至于无法满足实际应用的需求。时间开销的增大，影响了系统的实时性。

4、鲁棒性问题

推荐系统能否识别此种情况，去除恶意用户及异常数据，提高推荐系统的可靠性，这也是目前推荐系统鲁棒性方面所需要重点关注的问题。