协同过滤算法（Collaborative Filtering）

协同过滤算法既是推荐系统中最古老的算法，也是推荐系统中最常用的方法

---

从 k-NN 引入协同过滤

平时生活中，当我们需要买东西但是不知道去哪个商场更好时，很自然的一个想法就是去问问身边的朋友，因为身边的朋友往往和自己有相似的偏好，从而能推荐更适合自己的商场，而这就像是之前文章里介绍的 k-NN 算法。k-NN 算法每一次都在训练集去寻找与目标样本最接近的 k 个实例，然后根据这 k 个实例的分类结果来产生目标样本的预测结果。而当我们把 k-NN 引入到推荐系统中时，再稍稍加工之后，就产生了协同过滤算法。

---

基于用户的协同过滤算法（UserCF）

当上述 k-NN 算法中的 k 指的是 k 个用户时，即每次都去训练用户中寻找与目标用户“兴趣”最接近的 k 个用户，然后在这 k 个用户的喜好的物品中，寻找目标用户还没有听说过的物品并推荐给该目标用户，这样的方法就称为基于用户的协同过滤算法（UserCF）。不难看出 UserCF 最主要有两个步骤：
(1) 寻找与目标用户兴趣最相似的 k 个用户形成的用户集合
(2) 在这个用户集合喜欢的物品的集合中，寻找目标用户还没有听说过的并最有可能感兴趣的 N 物品推荐给目标用户
步骤 1 的关键就是计算用户之间的相似度，在协同过滤算法中，一般利用用户的行为相似度来代表用户之间的相似度。给定两个用户 u 和 v，令 N(u)、N(v) 分别表示他们有过正反馈的物品集合，那么可以使用 Jaccard 公式简单地计算他们之间的兴趣相似度：

或者使用余弦相似度计算：

计算余弦相似度的代码如下：

def UserSimilarity(train):
    W = dict()
    for u in train.keys():
        for v in train.keys():
            if (u == v):
                continue
            else:
                W[u][v] = len(train[u] & train[v])
                W[u][v] /= math.sqrt(len(train[u]) * len(train[v]))
    return W

然而，因为现实情况中，很多用户之间并没有对同样的物品产生过行为，即很多时候 | N(u) ∩ N(v) | = 0，而上述算法将太多计算浪费在了计算这种用户的相似度上。如果反向思考，我们先计算出 | N(u) ∩ N(v) | ≠ 0 的用户对 (u, v) ，然后只对这种情况除以分母，则可以大大提高计算效率。为此，我们可以先建立从物品到用户的倒排表，然后建立矩阵 C，令 C[u][v] = | N(u) ∩ N(v) |，最后再计算所有 C[u][v] ≠ 0 的用户对
(u, v) 之间相似度，代码如下：
pass

---

基于物品的协同过滤算法（ItemCF）

pass

---

UserCF 和 ItemCF 的应用场景和效果差异

pass

---

参考资料

《推荐系统实战》，项亮