ItemCF算法解析

核心思想：物以类聚，好东西总会扎堆

“物品之间存在着一种内在的、稳定的关联。喜欢一个东西的人，很可能也喜欢和它相似的另一个东西。”

ItemCF是基于物品相似度进行推荐的协同过滤算法。通过计算共现矩阵中物品列向量的相似度得到物品之间的相似矩阵，再找到用户的历史正反馈物品的相似物品进行进一步排序和推荐。一言以蔽之，ItemCF算法的最终目的就是找出所有物品之间的“相似”关系，并把它量化成一个具体的“相似度分数”。

算法的具体步骤

1. 基于历史数据，构建以用户（假设用户总数为m）为行坐标，物品（物品总数为n）为列坐标的m×n维的共现矩阵。

2. 计算共现矩阵两两列向量间的相似性（可通过计算向量的余弦值得到）​，构建n×n维的物品相似度矩阵。

3. 获得用户历史行为数据中的正反馈物品列表。

4. 利用物品相似度矩阵，针对目标用户历史行为中的正反馈物品，找出相似的To p k个物品，组成相似物品集合

5. 对相似物品集合中的物品，利用相似度分值进行排序，生成最终的推荐列表。如果一个物品与多个用户行为历史中的正反馈物品相似，那么该物品最终的相似度应该是多个相似度的累加。 $R(u, j) = \sum_{i} S(j, i) \times P(u, i)$

   其中：

   • $R(u, j)$：用户u对物品j的推荐分数
   • $S(j, i)$：物品j与物品i的相似度
   • $P(u, i)$：用户u对物品i的偏好程度（这里为1表示喜欢，0表示不喜欢）

算法拆解

已知信息

• 有3个用户："用户1"、"用户2"、"用户3"
• 有5门课程：课程A为数学，课程B为物理，课程C为化学，课程D为生物，课程E为历史

第一步：建立"花名册"(构建用户-物品交互矩阵)

这里我们基于所有人的"上课记录"整理出一张巨大的总表，上过某个科目记为1，没有上过记为0。

第二步：绘制"物品关系网" (计算物品相似度矩阵)

首先对于任何一门课程（比如课程i），我们都可以用一个向量Vi来表示它（其实就是第一步花名册的列向量）。这个向量在每个"用户维度"上的取值如下：

• 如果第 k 个用户上过课程 i，那么向量 Vi在第 k 个维度上的值就是 1。
• 如果第 k 个用户没上过课程 i，那么向量 Vi在第 k 个维度上的值就是 0。

课程A数学、课程B物理的向量可以表示为：

$V_A = (u_1: 1, u_2: 1, u_3: 0) \Rightarrow [1, 1, 0]$

$V_B = (u_1: 1, u_2: 0, u_3: 1) \Rightarrow [1, 0, 1]$

明确了课程向量的表示后，我们就可以来计算课程向量的相似度了。这里我们通过"余弦相似度"公式来进行计算。

$\text{sim}(i,j) = \frac{V_i \cdot V_j}{\|V_i\| \cdot \|V_j\|} = \frac{|N(i) \cap N(j)|}{\sqrt{|N(i)| \cdot |N(j)|}}$

我们依次计算每门课程的相似度：

• 数学课程A vs 物理课程B:

  • 上过数学的有: 用户1和用户2，共2人。
  • 上过物理的有: 用户1和用户3，共2人。
  • 同时上过的有: 用户1，共1人。
  • 相似度 = $\frac{1}{\sqrt{2 \times 2}} = 0.5$

• 数学课程A vs 化学课程C:

  • 上过数学的有: 用户1和用户2，共2人。
  • 上过化学的有: 用户2和用户3，共2人。
  • 同时上过的有: 用户2，共1人。
  • 相似度 = $\frac{1}{\sqrt{2 \times 2}} = 0.5$

• 化学课程C vs 生物课程D:

  • 上过化学的有: 用户2和用户3，共2人。
  • 上过生物的有: 用户2，共1人。
  • 同时上过的有: 用户2，共1人。
  • 相似度 = $\frac{1}{\sqrt{2 \times 1}} ≈ 0.71$

计算完所有课程的相似度后，我们可以总结出下面的"物品关系网"（相似度矩阵）：

第三步：计算吸引力分数

现在当我们要为"用户1"推荐一门新课时，我们会经过以下的步骤：

1. 找到"用户1"的喜好源头。查看"用户1"的"花名册"，发现该用户上过数学A和物理B。这是我们推荐的出发点。

2. 计算每一门新课的"吸引力"。遍历所有"用户1"没上过的课程（化学C、生物D、历史E），利用算法步骤五中的公式计算它们的吸引力分数。

   • 化学C的吸引力:
     • 来自数学A的贡献：S(C,A) × P(用户1,A) = 0.5 × 1 = 0.5
     • 来自物理B的贡献：S(C,B) × P(用户1,B) = 0.5 × 1 = 0.5
     • 总吸引力 = 0.5 + 0.5 = 1.0
   • 生物D的吸引力:
     • 来自数学A的贡献：S(D,A) × P(用户1,A) = 0.71 × 1 = 0.71
     • 来自物理B的贡献：S(D,B) × P(用户1,B) = 0 × 1 = 0
     • 总吸引力 = 0.71 + 0 = 0.71
   • 历史E的吸引力:
     • 来自数学A的贡献：S(E,A) × P(用户1,A) = 0 × 1 = 0
     • 来自物理B的贡献：S(E,B) × P(用户1,B) = 0.71 × 1 = 0.71
     • 总吸引力 = 0 + 0.71 = 0.71

3. 排序，给出最终推荐。我们把分数从高到低一排：

   1. 化学C: 1.0分
   2. 生物D: 0.71分
   3. 历史E: 0.71分

于是，系统向"用户1"推荐：化学C！

ItemCF的优缺点

优点

• 可解释性强：推荐理由非常直观，"因为用户喜欢数学和物理，而化学和这两门课关系都很近，所以推荐化学"。
• 性能好：最复杂的“物品关系网”可以提前离线算好，线上推荐时计算量很小。
• 对新用户友好：只要新用户产生一个行为（上过课），就能立刻根据这个物品的关系网为他推荐。

缺点:

• 缺乏惊喜度：推荐结果往往和用户历史兴趣高度相似，很难发现用户的潜在新兴趣。
• 对新物品不友好：一个新上架的课程，因为没人上过，无法进入“物品关系网”，也就无法被推荐出去。

Q&A

深入理解“余弦相似度”公式

深入理解吸引力分数计算公式