推荐系统学习(一)：召回-协同过滤-UserCF

基于用户的协同过滤(userCF)

第一步：用户相似度计算

杰卡德相似系数

被推荐用户A，另一个用户B，只计算他们共同 item 数 占 A item 数 的比值。公式表现为：

w_{uv} = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}

余弦相似度

通过向量化表示用户，对两个用户求向量夹角，可以体现出两个人兴趣方向是否相似，相比于杰卡德系数消除了热点造成的影响。在transformer里也有类似的求向量相似度，不过是使用比较简单的点积而非余弦。余弦相似度的公式是：

w_{uv} = \frac{|N(u) \cap N(v)|}{\sqrt{|N(u)|\cdot|N(v)|}}

上面是集合形式的表达，由于喜欢，不喜欢是二元向量，所以可以如上表达，真正的余弦相似度公式是：

\text{similarity} = \cos(\theta) = \frac{A \cdot B}{\|A\| \|B\|}

皮尔逊相关系数

有具体评分而不是只有二元关系时使用，可以去除每个人打分标准不同导致的误差。公式：

w_{uv} = \frac{\sum_{i \in I}(r_{ui} - \bar{r}_u)(r_{vi} - \bar{r}_v)}{\sqrt{\sum_{i \in I}(r_{ui} - \bar{r}_u)^2}\sqrt{\sum_{i \in I}(r_{vi} - \bar{r}_v)^2}}

第二步： 候选物品推荐

简单加权平均

直接用第一步得到的相似度来加权计算，然后多个用户的值平均，就是被推荐用户 u 对这个物品 p 的预测评分,公式：

\hat{r}_{u,p} = \frac{\sum_{v \in S_u} w_{uv} \, r_{v,p}}{\sum_{v \in S_u} w_{uv}}

考虑评分偏置

考虑其他用户的平均评分来减少误差，并根据目标用户的平均评分进行调整，公式：

\hat{r}_{u,p} = \bar{r}_{u} + \frac{\sum_{v \in S_u} w_{uv} \, (r_{v,p} - \bar{r}_{v})}{\sum_{v \in S_u} w_{uv}}

第三步：一些优化

UserCF看起来很简单，但有个大问题：当用户数量很大时，计算所有用户对之间的相似度会非常耗时，时间复杂度达到 $O(|U|^2)$
但仔细观察就会发现，很多用户对之间根本没有共同行为的物品，相似度必然为0，计算它们就是浪费时间。我们可以利用这个特点来优化算法。

下面这个对离线计算相似度的优化的时间复杂度就不是和 u 指数级增长的了，而是和物品数成线性相关以及和每个物品被喜欢的用户数 $N(i)$ 指数级相关，虽然依然大，但是比用户指数级好的多，时间复杂度是$O(Σ|N(i)|²) ≈ O(N * k²)$，
N 是遍历所有物品** i** ,**k 是平均每个物品被喜欢的用户数，所以 k² **是处理一个物品的平均计算量。

如果用R表示用户-物品的总交互数，用$\bar{n}$表示每个物品的平均用户数，公式也可以表达为$O(R \cdot \bar{n})$

基于物品倒排表的优化：

1. 构建倒排表：为每个物品维护一个用户列表，记录哪些用户对这个物品有过行为。这样就可以通过物品快速找到相关用户。
2. 稀疏矩阵计算：创建一个矩阵$C[u][v]$来记录用户 u 和 v 的共同物品数量。遍历每个物品的用户列表，将列表中的用户两两配对，对应的$C[u][v]$值加1。
3. 计算最终相似度：矩阵给出了余弦相似度公式的分子，再除以分母$\sqrt{|N(u)||N(v)|}$就得到了用户相似度。
   上面说离线相似度矩阵是被推荐用户u和某用户v的，是单次计算，这个相似度矩阵要用于线上推荐，但是不能计算出所有用户对结果并全部存入矩阵拿给线上推荐，而是在离线时会存下**top k **个最相似的矩阵。
4. 线上召回：有了用户相似度矩阵，UserCF的推荐流程通常采用以下策略来提高效率：
   收集 top k 里用户交互过的物品作为候选物品，并计算用户 u 对候选物品 i 的兴趣分数

p(u, i) = \sum_{v \in S_u \cap N(i)} w_{uv} \cdot r_{vi}

$S_u$是与用户 u 最相似的K个用户集合，$N(i)$是对物品 i 有过行为的用户集合，$w_{uv}$是用户相似度，$r_{vi}$表示用户对物品的兴趣强度（可以是简单的1，也可以根据评分、交互时间等设置权重）。

最终，系统对所有候选物品按兴趣分数排序，选择Top-N物品作为UserCF通道的推荐结果。这种“相似用户扩展”的方式既保证了推荐的个性化质量，又避免了对全量物品的无效计算。