两种基本协同过滤算法比较.pdf

两种基本的协同过滤算法比较
基于条目 (Item-Based)和基于用户 (User-Based)的协同过滤算法，是个性化推荐系统中最
基本的两种算法。由于实现简单， 并且推荐效果往往能达到或接近预期，特别是针对不
同数据集的鲁棒性好，这两种算法也是推荐系统在工业界中应用最普遍的算法。相信作为
互联网行业的算法工程师，大家对这两种基本的算法都很熟悉了。但在实际应用的过程
中，还是有些需要我们格外注意的问题。本文试图从算法的计算复杂性和算法与产品适配
这两个角度来讨论这两种协同过滤算法的异同，希望能帮助大家更加透彻的了解和应用这
两种基本算法。
⼀ 相似性矩阵的计算复杂性
无论是基于条目的还是基于用户的协同过滤算法，其基本流程都是⼀致的，分为两步：
1. 根据相似性度量计算相应的条目相似性矩阵或用户相似性矩阵
2. 依据相似性矩阵和用户收藏为用户做推荐
相似性度量有很多种选择，最常用的是采用公式（ 1）所示的余弦相似性，即把用户或条
目收藏看做高维空间的向量，把向量之间夹角的余弦当做两个向量的相似性度量。采用余
弦相似性时，往往事先会对用户条目收藏矩阵做归⼀化预处理，这样⼀来，求相似性的操
作就可以转化为矩阵相乘操作了，进行理论推导或编码实现时都比较方便。
  ∑ rx,iry,i
  x ⋅ y i∈Ixy
sim(x, y) = cos(x, y) =   = (1)
x × y r2 r2
2 2 ∑ x,i ∑ y,i
i∈Ixy i∈Ixy
计算相似性矩阵是做个性化推荐的第⼀步，也是整个算法的基础。下面我们详细分析⼀下
在不同的情况下相似性矩阵的计算复杂度以及对整个推荐算法的影响。
1. 收藏数据均匀分布
考察最简单的情况， Um×n 是经过归⼀化的 m 个用户对 n 个条目的评分（或收藏）矩阵，
我们假设 中有 个非零元素， ；同时我们假设这些非零元素在行和列上都
Um×n C C  m × n
是均匀分布的，记 L = C / m 为平均每行的个非零元素个数， L' = C / n 为平均每列的个非
零元素个数，我们有 ' ，即平均每位用户收藏的条目和平均每个条目
max(L, L )