Swing

传统ItemCF的局限性

热门物品偏差：热门物品容易频繁共现，导致相似度虚高，比如书店里《哈利波特》和《新华字典》被大量客户购买，但二者并无实际关联

稀疏性问题：用户-物品交互数据稀疏时，传统相似度（如余弦）虽然可以用，但是计算不稳定。

Swing 的改进思路

如果两个物品被同一批用户交互过，则它们可能相似

进一步考虑共现用户的重叠程度，避免热门物品的干扰。

相似度计算公式为

$$
\text{Sim}(i, j) = \sum_{u \in U_i \cap U_j} \sum_{v \in U_i \cap U_j} \frac{1}{\alpha + |I_u \cap I_v|}
$$

其中：

• $U_i$：交互过物品 $i$ 的用户集合
• $I_u$：用户 $u$ 交互过的物品集合
• $\alpha$：平滑参数（通常取1，防止分母为 0）

这么计算的原因是如果两个用户u和v都交互了物品i和j，且它们共同交互的其他物品很少（即$|I_u \cap I_v|$小），则i和j的相似度更高

这样可以降低热门物品的权重，因为热门物品通常会被很多用户共同交互。

Swing的算法流程

步骤1：构建用户-物品共现图

• 对于每个物品i，记录交互过它的用户集合$U_i$
• 对于每对物品(i,j)，找到共同交互的用户$U_i \cap U_j$

步骤2：计算物品相似度

• 对于每对共现用户(u,v)，计算他们共同交互物品数$|I_u \cap I_v|$
• 使用Swing公式计算相似度

步骤3：归一化

对相似度矩阵进行归一化（如最大值归一化）。

为什么要归一化？

直接计算的相似度可能数值范围差异很大（例如某些物品对的相似度为 100，另一些为 0.1），导致推荐结果偏向少数高分物品。将相似度缩放到统一范围（如 [0, 1]），避免数值量纲影响推荐排序。

步骤4：生成推荐

找出候选物品：遍历用户历史物品$I_u$，找到每个物品Top-K个相似物品，合并去重后得到候选池C

例如：

• $A$ 的相似物品：${B, D, E}$（相似度分别为 $0.8,\ 0.6,\ 0.5$）
• $B$ 的相似物品：${A, C, F}$（相似度分别为 $0.8,\ 0.7,\ 0.4$）

计算推荐分数：对候选池中的每个物品j∈C，计算其与用户历史物品的加权相似度

$$
\text{Score}(j) = \sum_{i \in I_u} \text{Sim}_{\text{norm}}(i, j)
$$

基于用户历史物品$I_u = {A, B}$，计算物品D的分数：

$$
\text{Score}(D) = \text{Sim}(A, D) + \text{Sim}(B, D) = 0.6 + 0 = 0.6
$$

排序并生成推荐：按$\text{Score}(j)$降序排列候选物品，取Top-N作为推荐结果

Top-3 推荐结果：$[C, D, E]$

时间复杂度分析

Swing 算法的时间复杂度是多少？如何优化其在大规模数据下的性能？

时间复杂度：$O(n^2m^2)$（$n$ 为物品数，$m$ 为平均用户交互数），最坏情况下需遍历所有物品对和用户对。

优化方法

• 剪枝：仅计算共现用户数超过阈值的物品对。
• 分片：按物品类别分片并行计算。
• 近似：使用局部敏感哈希（LSH）快速查找相似用户对。