基础算法
1992 年提出 UCF,UCF 的两个步骤
- 找到和目标用户相似的用户集合
- 找到这个集合中用户喜欢的,且用户未见过的物品推荐
如何计算两个用户 u,v 的兴趣相似度?
- N(u) 表示用户 u 曾经有过正反馈的物品集合
- N(v) 表示用户 v 曾经有过正反馈的物品集合
利用 Jaccard 公式 (余弦也行) 计算用户 u,v 的兴趣相似度 wuv
wuv=|N(u)∩N(v)||N(u)∪N(v)|
余弦相似度,重点
wuv=|N(u)∩N(v)|√|N(u)||N(v)|

用户行为记录举例
用户 A 对物品 {a,b,d} 有过正反馈,用户 B 对物品 {a,c} 有过正反馈,利用 余弦相似度 计算得出
wAB=|{a,b,d}∩{a,c}|√{a,b,d}||{a,c}|=1√6
同理可以计算出用户 A 和 用户 C,D 的相似度
wAC=|{a,b,d}∩{b,e}|√|{a,b,d}||{b,e}|=1√6wAD=|{a,b,d}∩{c,d,e}|√|{a,b,d}||{c,d,e}|=13
我们可以撸一遍余弦相似度计算的代码,反正就是两个 for
循环
1 | def UserSimilarity(train): |

用户 - 物品倒排表
如何 快速 计算两个用户 u,v 的兴趣相似度?
难点
参考 这里,计算时间复杂度为 O(|U|2)。事实上很多用户并没有对同一物品产生过反馈,即 |N(u)∩N(v)|=0。如果计算这种用户的相似度(肯定为 0),无疑是浪费了时间。怎么办呢?
解决思路是,先计算出|N(u)∩N(v)|≠0 的用户 pair(u,v),然后再对这种情况除以分母 √|N(u)||N(v)|。
首先,建立 item→user 的倒排表,建立物品和反馈用户列表之间的关系。
然后考虑,建立 用户稀疏矩阵,大小为 用户数 × 用户数
C[u][v]=|N(u)∩N(v)|
假设用户 u 和 用户 v 同时反馈过 K 个物品,就有 C[u][v]=K。
好了,这里我们扫描刚刚建立好的 倒排表 的用户列表,将这个列表中的两两用户 u,v 对应的 C[u][v] 加 1。最终就可以得到用户之间不为 0 的 C[u][v]。
比之,之前的方法,这里我们这里有两点变化:第一,遍历 item,这个长,但是只有一遍 ;第二,针对item→user 的 user_list 两两(u,v)+1, 这个需要遍历两遍,但是很短。
最后,在第二步我们建立了余弦距离的分子 C[u][v],计算的时候,拿出分母 √|N(u)||N(v)| 即可,N(u) 的定义是用户反馈的 item 集合, 相对容易计算。
改进之后的代码
1 | def UserSimilarity(train): |
如何度量 UCF 算法中,用户 u 对物品 i的兴趣程度?
- S(u,K) 和用户 u 兴趣最接近的 K 个用户的集合
- N(i) 对物品 i 有过反馈的用户集合
- wuv 是用户 u,v 的兴趣相似度
- rvi 用户 v 对物品 i 的兴趣,默认为 1
这里计算的方式就是,先找到用户 u 的 Top K 的好基友,问问这些基友有没有买过 N(i)(比如 airpods)。基友们对新款 airpods 的评分是 rvi,我们再把用户 u 对各个基友 v 的人品评价记作 wuv,作为权重。最后一步,把 权重 × 评价 就是最后的 评分。到底买不买,就看这个评分了!
p(u,i)=∑v∈S(u,K)∩N(i)wuvrvi
1 | def Recommand(user, train, w): |
这里 K 是超参数,评价指标为准确率,召回率,覆盖率,流行度。
- 准确率和召回率对 K 不是很敏感
- K越大,流行度上越趋近于全局热门物品
- K 越大,覆盖率越低
用户相似度的改进
根据用户行为计算用户的兴趣相似度,惩罚用户 u 和用户 v 共同兴趣列表中的热门物品!
wtvv=∑i∈N(u)∩N(v)1log1+|N(i)|√|N(u)||N(v)|
注意这里分子的变化
|N(u)∩N(v)|⟶∑i∈N(u)∩N(v)1log1+|N(i)|
1log1+|N(i)| 惩罚了每一个共同兴趣,我们把改进后的算法叫做User-IIFF 算法。
我们再撸一遍代码
1 | def UserSimilarity(train): |
实验证明 UserCF-IIF 在各项性能上略优于 UserCF。
参考资料:推荐系统实践,项亮,第二章
v1.5.2