算法原理

如果用户喜欢物品 A，而物品 A 和物品 B 有很高的相似度，那么用户很有可能也喜欢物品 B。这就是基于物品的协同过滤（ItemCF）算法的基本思想。

例如，某位用户喜欢看《三国演义》，而《三国演义》和《水浒传》有很高的相似度，那么这位用户很有可能也喜欢看《水浒传》，如果用户没有看过《水浒传》，那么我们就可以推荐给用户看《水浒传》。

那么，推荐系统如何知道《三国演义》和《水浒传》有很高的相似度呢？思路：看过《三国演义》的用户，有多少人也看过《水浒传》？给《三国演义》好评的用户，有多少人也给《水浒传》好评？

算法实现

如上图所示，根据用户的历史行为日志，可以得到用户对部分已读物品的喜好程度（例如：点击记 1 分，点赞记 2 分，收藏记 3 分）。假设此时已知任意两个物品之间的相似度，那么我们可以结合两者预估用户对于每个候选物品的喜好程度。然后根据用户对候选物品的喜好程度，对候选物品进行排序，将排序靠前的物品推荐给用户。

用户对每个候选物品的喜好程度，可以通过下面的公式计算：

\[\sum_j{like(user, item_j) \times sim(item_j, item)}\]

其中，$like(user, item_j)$ 表示用户对物品 $item_j$ 的喜好程度，$sim(item_j, item)$ 表示物品 $item_j$ 和物品 $item$ 的相似度。

根据上面的公式，我们可以预估上图中用户对候选物品 item 的喜好程度：

\[2 \times 0.1 + 1 \times 0.4 + 4 \times 0.2 + 3 \times 0.6 = 3.2\]

物品相似度的计算

基于物品的协同过滤算法在计算物品相似度时的基本思想是：如果两个物品的受众有很多重合，那么这两个物品就很相似。例如，喜欢《三国演义》的读者和喜欢《水浒传》的读者重合度很高，那么《三国演义》和《水浒传》就很相似。

下面两张图片分别展示了两个物品的受众重合度，其中前者是两个物品不相似的情况，后者是两个物品相似的情况。

接下来介绍如何量化物品的相似度。假设喜欢物品 $i_1$ 的用户集合为 $W_1$，喜欢物品 $i_2$ 的用户集合为 $W_2$，$W_1$ 和 $W_2$ 的交集记为 $V = W_1 \cap W_2$，那么物品 $i_1$ 和物品 $i_2$ 的相似度可以通过下面的公式计算：

\[sim(i_1, i_2) = \frac{|V|}{\sqrt{|W_1| \cdot |W_2|}}\]

其中，$\lvert V \rvert$ 表示 $V$ 的元素个数，$\lvert W_1 \rvert$ 表示 $W_1$ 的元素个数，$\lvert W_2 \rvert$ 表示 $W_2$ 的元素个数。这样计算出来的物品相似度介于 0 和 1 之间，值越大表示物品越相似。

这种计算物品相似度的方法没有考虑到用户对物品的喜好程度，只考虑了用户是否喜欢物品。如果需要考虑到用户对物品的喜好程度，可以通过余弦相似度来计算物品的相似度。

\[sim(i_1, i_2) = \frac{\sum_{v \in V} {like(v, i_1) \times like(v, i_2)}}{\sqrt{\sum_{u_1 \in W_1} {like(u_1, i_1)^2}} \cdot \sqrt{\sum_{u_2 \in W_2} {like(u_2, i_2)^2}}}\]

除了余弦相似度，还有一种计算物品相似度的方法，叫做皮尔逊相关系数。皮尔逊相关系数的计算公式如下：

\[sim(i_1, i_2) = \frac{\sum_{v \in V} {(like(v, i_1) - \bar{like}(i_1)) \times (like(v, i_2) - \bar{like}(i_2))}}{\sqrt{\sum_{u_1 \in W_1} {(like(u_1, i_1) - \bar{like}(i_1))^2}} \cdot \sqrt{\sum_{u_2 \in W_2} {(like(u_2, i_2) - \bar{like}(i_2))^2}}}\]

其中，$\bar{like}(i)$ 表示物品 $i$ 的平均喜好程度。皮尔逊相关系数通过减去物品的平均喜好程度，可以消除物品的平均喜好程度对相似度的影响（消除物品评分偏差对结果的影响）。

还有一种皮尔逊相关系数的变种：

\[sim(i_1, i_2) = \frac{\sum_{v \in V} {(like(v, i_1) - \bar{like}(v)) \times (like(v, i_2) - \bar{like}(v))}}{\sqrt{\sum_{u_1 \in W_1} {(like(u_1, i_1) - \bar{like}(u_1))^2}} \cdot \sqrt{\sum_{u_2 \in W_2} {(like(u_2, i_2) - \bar{like}(u_2))^2}}}\]

其中，$\bar{like}(v)$ 表示用户 $v$ 的平均喜好程度。这种皮尔逊相关系数的变种通过减去用户的平均喜好程度，可以消除用户的平均喜好程度对相似度的影响（消除用户评分偏差对结果的影响）。

在实际应用中的完整流程

ItemCF 算法在实际召回应用中，我们需要事先建立两个索引表：

  • 用户-物品表：记录每个用户最近点击交互过的物品列表，以及每个物品的喜好程度，根据时间倒序排列，取前 $n$ 个物品。
  • 物品-物品表：记录每个物品与其相似的物品列表以及相似度，根据相似度倒序排列，取前 $k$ 个相似物品。

在线上实际应用中，我们可以通过“用户-物品表”来获得用户近期感兴趣的物品列表（last-n-items），然后通过“物品-物品表”来获得这些物品的相似物品列表（top-k-items），然后再根据公式预估用户对取回的这 $nk$ 个物品每兴趣分数，最后将分数最高部分物品推荐给用户（例如 Top100）。

总结

  1. ItemCF 算法的基本思想是：如果用户喜欢物品 A，那么用户也很可能喜欢与物品 A 相似的物品 B。

  2. 计算物品相似度：
    • 如果两个物品的受众有很多重合，那么这两个物品就很相似。

    • 只考虑用户是否喜欢物品，不考虑用户对物品的喜好程度：

      \[sim(i_1, i_2) = \frac{|V|}{\sqrt{|W_1| \cdot |W_2|}}\]

    • 基于余弦相似度计算物品相似度时，考虑到了用户对物品的喜好程度：

      \[sim(i_1, i_2) = \frac{\sum_{v \in V} {like(v, i_1) \times like(v, i_2)}}{\sqrt{\sum_{u_1 \in W_1} {like(u_1, i_1)^2}} \cdot \sqrt{\sum_{u_2 \in W_2} {like(u_2, i_2)^2}}}\]

    • 皮尔逊相关系数和皮尔逊相关系数的变种，通过减去物品的平均喜好程度或者用户的平均喜好程度，可以消除物品评分偏差或者用户评分偏差对相似度的影响：

      \[sim(i_1, i_2) = \frac{\sum_{v \in V} {(like(v, i_1) - \bar{like}(i_1)) \times (like(v, i_2) - \bar{like}(i_2))}}{\sqrt{\sum_{u_1 \in W_1} {(like(u_1, i_1) - \bar{like}(i_1))^2}} \cdot \sqrt{\sum_{u_2 \in W_2} {(like(u_2, i_2) - \bar{like}(i_2))^2}}}\] \[sim(i_1, i_2) = \frac{\sum_{v \in V} {(like(v, i_1) - \bar{like}(v)) \times (like(v, i_2) - \bar{like}(v))}}{\sqrt{\sum_{u_1 \in W_1} {(like(u_1, i_1) - \bar{like}(u_1))^2}} \cdot \sqrt{\sum_{u_2 \in W_2} {(like(u_2, i_2) - \bar{like}(u_2))^2}}}\]
  3. 线上做召回：
    • 维护两个索引表：用户-物品表（用户最近交互过的 $n$ 个物品列表）和物品-物品表（相似度最高的 $k$ 个物品列表）。
    • 利用两个索引表，每次返回分数最高的 $n \times k$ 个物品。

    • 预估用户对物品的喜好分数：

      \[score(u, i) = \sum_{i' \in top-k-items(i)} {like(u, i') \times sim(i, i')}\]
    • 返回用户喜欢的物品列表（例如 Top100），作为召回结果。

参考资料

  1. https://github.com/wangshusen/RecommenderSystem（本文图片均来自此repo）
  2. 王哲《深度学习推荐系统》