协同过滤 / 开普饭

什么是协同过滤

协同过滤推荐（Collaborative Filtering recommendation）是在信息过滤和信息系统中正迅速成为一项很受欢迎的技术。与传统的基于内容过滤直接分析内容进行推荐不同，协同过滤分析用户兴趣，在用户群中找到指定用户的相似（兴趣）用户，综合这些相似用户对某一信息的评价，形成系统对该指定用户对此信息的喜好程度预测。
协同过滤是迄今为止最成功的推荐系统技术，被应用在很多成功的推荐系统中。电子商务推荐系统可根据其他用户的评论信息，采用协同过滤技术给目标用户推荐商品。

协同过滤算法

协同过滤算法主要分为基于启发式和基于模型式两种。
其中，基于启发的协同过滤算法，又可以分为基于用户的协同过滤算法（User-Based）和基于项目的协同过滤算法（Item-Based）。
 启发式协同过滤算法主要包含 3 个步骤：
1）收集用户偏好信息
2）寻找相似的商品或者用户
3）产生推荐

一、基于用户的协同过滤算法

基于用户的协同过滤算法主要分为两步：
（1）找到与目标用户兴趣相似的用户集合
（2）找到这个集合中用户喜欢的、并且目标用户没有听说过的物品推荐给目标用户

1.相似度的计算方法

皮尔逊相关系数：

其中，i 表示项，例如商品；Iu 表示用户 u 评价的项集；Iv 表示用户 v 评价的项集；ru，i 表示用户 u 对项 i 的评分；rv，i 表示用户 v 对项 i 的评分；表示用户 u 的平均评分；表示用户 v 的平均评分。
余弦相似度

2.计算用户 u 对未评分商品的预测分值

首先根据上一步中的相似度计算，寻找用户 u 的邻居集 N∈U，其中 N 表示邻居集，U 表示用户集。然后，结合用户评分数据集，预测用户 u 对项 i 的评分，计算公式如下所示：

s（u，u’）表示用户 u 和用户 u’的相似度。

3.通过例子理解

假设有如下电子商务评分数据集，预测用户 C 对商品 4 的评分。

表中？表示评分未知。根据基于用户的协同过滤算法步骤，计算用户 C 对商品 4 的评分，其步骤如下所示。
（1）寻找用户 C 的邻居从数据集中可以发现，只有用户 A 和用户 D 对商品 4 评过分，因此候选邻居只有 2 个，分别为用户 A 和用户 D。用户 A 的平均评分为 4，用户 C 的平均评分为 3.667，用户 D 的平均评分为3

根据皮尔逊相关系数公式：红色区域计算 C 用户与 A 用户，用户 C 和用户 A 的相似度为：

蓝色区域计算 C 用户与 D 用户的相似度为：

（2）预测用户 C 对商品 4 的评分根据上述评分预测公式，计算用户 C 对商品 4 的评分，如下所示：

二、基于项目的协同过滤

基于物品的协同过滤算法主要分为两步：
（1）计算物品之间的相似度，通过共现矩阵实现
（2）根据物品的相似度和用户的历史行为给用户生成推荐列表

1.相似度计算方法

分母|N(i)]|是喜欢物品 i 的用户数，|N(i)∩N(j)|是同时喜欢物品 i 和 j 的用户
计算物品相似度首先建立用户-物品倒排表，根据矩阵计算每两个物品之间的相似度 wij。W[i][j]记录了同时喜欢物品i和物品j的用户数。

得到物品之间的相似度后，可以根据如下公式计算用户 u 对于物品 j 的兴趣：

N(u)是用户喜欢的物品的集合，S(j,K)是和物品 j 最相似的 K 个物品的集合， wji 是物品 j 和 i 的相似度，rui 是用户 u 对物品 i 的兴趣。 i 的相似度，rui 是用户 u 对物品 i 的兴趣。（对于隐反馈数据集，如果用户 u 对物品 i 有过行为，即可令 rui=1。）该公式的含义是，和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名。
该公式的实现代码如下所示：
def Recommendation(train, user_id, W, K):
rank = dict()
ru = train[user_id]
for i,pi in ru.items():
for j, wj in sorted(W[i].items(), key=itemgetter(1), reverse=True)[0:K]:
if j in ru:
continue
rank[j] = pi * wj
return rank

2.通过例子理解：

现有用户的访问的记录如下图所示：

他的共现矩阵为：

通过公式计算相似度：

以此类推得到相似度的共现矩阵

此时若有新用户 E，访问的 a,b,d 三个物品，那么可以看做向量 P：

T为物品的共现矩阵，P为新用户对已有产品的向量，得到的 P`为新用户对每个产品的兴趣度。
此时得到了对于用户 E，c 和 e 两个物品的兴趣度是相同的。
理解公式 i∈N(u)∩S(j,K)
对于用户 E，已经访问了 a,b,d，那么，N(u)={a,b,d}；还有两个未访问物品 c,e，那么 j={c,e}；当 j=c 时，对于和物品 j 最相似的 K 个物品的集合为{a,d,e}，那么 S(j,K)={a,d,e}；得出N(u)∩S(j,K)={a,d},如下图所示：