BLOG

个人博客,记录学习与生活

协同过滤(Collaborative Filtering)

Published Oct. 22, 2020, 10:07 p.m. by kkk

协同过滤指的是人们协同起来,互帮互组,通过各自对文档、商品的反应来帮助别人过滤信息。1

协同过滤可分为Memory-based, Model-based两种,前者利用整个的商品-用户数据库进行商品评价预测和商品推荐,包括User-based和Item-based;后者有Matrix Decomposition, Bayesian networks, clustering, Horting。2,主要形式为前者。

  1. 基于用户的协同过滤(User-based CF):给用户推荐相似用户所喜欢的产品
  2. 基于物品的协同过滤(Item-based CF):给用户推荐与之前喜欢过的物品相似的物品。

1. 协同过滤的基本问题形式

有一组用户列表$U={u_1, u_2, \cdots, u_m}$和商品列表$I={i_1, i_2,\cdots,i_n}$,每个用户$u_i$都有一组已经进行过评论的商品$I_{u_i}$,评价通常是属于特定区间的数值,例如0-5分,对于用户$u_a$,有两个任务:

  1. 预测。给出该用户对商品$i_j$的预测评价,其中$i_j \notin I_{u_a}$
  2. 推荐。为该用户推荐他会最喜欢的一组商品$I_r$,数量为$N$,其中$I_r \cap I_{u_a}=\emptyset$。也称为TopN推荐

2. 实现协同过滤的步骤

  1. 收集用户偏好(评分、浏览记录、购物记录等等)
  2. 找到相似用户(User-based)或物品(Item-based)
  3. 计算并排序

3. 如何计算相似性?

3.1 相似度

通常有几种方法:Jaccard相似性、余弦近似性、皮尔逊相关系数(例如不同用户对商品的评分标准不同)

  1. Jaccard相似性

是一种衡量两个集合间相似度的指标,计算的是两集合中交集与并集的比例。具体而言,如果$N(u), N(v)$分别表示用户$u, v$交互的两个商品集合,两者Jaccard相似性为: $$ sim_{uv} = \frac{\vert N(u)\cap N(v) \vert }{\sqrt{\vert N(u)\vert \cup \vert N(v)\vert}} $$ 缺点:细粒度比较低,只能简单的考虑对某商品是否喜欢,而没有考虑到具体的喜好程度(如评分)。

  1. 余弦相似性

高中数学内容,就是求两向量间的夹角余弦值,一个优势是自带归一化。具体而言,同上集合描述: $$ sim_{uv} = \frac{\vert N(u) \cap N(v)\vert}{\sqrt{\vert N(u)\vert \cdot \vert N(v)\vert}} $$ 缺点:没有考虑到不同用户平均打分的偏差情况

  1. 皮尔逊相关系数

皮尔逊相关系数,相较于余弦相似度,引入用户的平均分,对各自独立评分进行修正,减小了用户评分偏置的影响。 $$ sim_{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}} $$

3.2 用户相似度的改进

上述计算相似性的公式都忽略了一的问题,即物品的热门程度,对于有些热门物品比如新华字典,可能很多人都买过,如果两个用户都买过该物品不能就认定两者是相似的。

John S.Breese在论文中提出了如下公式,对共同兴趣物品中的热门商品进行了惩罚($N(i)$是对物品$i$有过行为的用户集合): $$ sim_{uv} = \frac{\sum_{i\in N(u)\cap N(v)}\frac{1}{\log 1 + \vert N(i)\vert}}{\sqrt{\vert N(u)\vert \vert N(v)\vert}} $$

3.3 API

# 余弦相似度
from sklearn.metrics.pairwise import cosine_similarity
cosine_similarity(i, j) 

# 皮尔逊相关系数(下面两种都可以)
import numpy as np
np.corrcoef([i, j])

from scipy.stats import pearsonr
pearsonr(i, j)

4. 评估指标

如果$R(u)$是给用户$u$的推荐列表(根据训练集计算的,对测试集上物品的预测),$T(u)$是用户在测试集上的行为列表,$U$是所有需要进行推荐用户的集合。通常按时间顺序给数据进行训练集和测试集分割。

4.1 准确率

$$ Precision = \frac{\sum_{u\in U}\vert R(u)\vert \cap \vert T(u)\vert}{\sum_{u\in U}\vert R(u)\vert} $$

4.2 召回率

$$ Recall = \frac{\sum_{u\in U}\vert R(u)\vert \cap \vert T(u)\vert}{\sum_{u \in U}T(u)} $$

5. 数据倒排

根据用户-物品表计算相似度时,有几个问题:

  • 相似度高,为$O(n^2)$
  • 很多用户交互过的物品很少,交互物品并集为空,也会被保存

提升措施:建立物品-用户倒排表(键为物品,值为用户及评分)

优势:

  • 没有过行为的用户直接被过滤了,最终得到的都是有行为的表,降低的时间复杂度
  • 将计算的用户$u$和用户$v$的相似度矩阵单独存储起来,减少了计算量

除了建立物品-用户倒排表,同时建立用户-用户共现矩阵(键为物品,值为用户及两者具有共同行为的次数),用户评分次数字典)(键为用户,值为用户总行为数)。

此时相似度,如余弦相似度计算如下(设物品-用户倒排表为$T$,用户-用户共现矩阵为$C$,用户评分次数字典为$N$,相似度矩阵为S): $$ S[u][v] = \frac{T[u][v]}{\sqrt{N[u]\cdot N[v]}} $$

5. User-based CF

5.1 步骤

当决定是否给某用户推荐某商品时,参考最相似的K个用户对该商品的评价,进行确定。进行TopN推荐步骤:

  1. 生成商品用户共现矩阵
  2. 计算与其它用户间的相似性,构建出用户相似度矩阵
  3. 选择相似度最高的K个用户
  4. 根据K个相似用户,将所有未交互过的物品进行评分
  5. 将为交互物品评分后进行排名,选出TopN个作为最终推荐列表

5.2 对最终评价的确定方式

对于商品$i$和用户$u$,$u$的最相似用户集为$S$,$s$为其中元素,假设用户$u$、用户$s$对商品的评价分为别:$R_{ui}, R_{si}$,对商品$i$有过行为的用户集为$N(i)$。计算得两用户的相似性为$w_{us}$,则用户$u$对商品$p$的评价预测为: $$ R_{ui} = \frac{\sum_{s\in S} w_{us}R_{si}}{\sum_{s\in S} w_{us}} $$

上述方式将各相似用户对目标商品的评价按相似性权重进行了加权,得到的结果作为最终预测结果。另外还有一种方式,考虑了用户内心的评分情况,相当于把相似用户对商品的评分都减去了自身对所用商品的平均评分,再加上用户的平均评分,并且只考虑有过行为的用户,相比之下会更加符合情况。 $$ R_{up} = \bar R_u + \frac{\sum_{s\in S \cap N(i)}w_{us}(R_{si}- \bar R_s)}{\sum_{s\in S\cap N(i)}w_{us}} $$

5.3 缺点

  • 计算量、存储量大。通常用户数量远大于商品数量,对于一个用户,计算其他每个用户跟他之间相似度具有极大的计算量,同时要存储该相似度需要较大的存储空间。

  • 稀疏性,用户对商品的评价数据稀疏。通常大量用户都只接触过少量的商品,导致对于某些用户的相似度计算不准确,导致推荐效果不佳。

  • 并行性。获取topN时采取的是最近邻,需要计算所有的用户之间的相似性,当用户量不断增加的时候会出现拓展性问题。

5.4 CODE

篇幅略长,见本人Github页面User-basedCF notebook

6. Item-based CF

给用户的推荐商品,是该用户喜欢(好评、点赞、评价高等)的商品的近似商品。相较User-based的优势:商品间的关系通常是固定的,不像用户之间的关系是发生变化的(因为用户的兴趣是变化的),通过计算商品间的关系可以减少计算量。

6.1 步骤

  1. 构建用户商品共现矩阵
  2. 获取该用户历史数据中的感兴趣物品
  3. 利用物品相似度矩阵,针对目标用户行为中的感兴趣物品,找出TopN个相似物品
  4. 对TopN相似物品进行排序,生成最终推荐列表

6.2 问题

最终推荐结果的头部效应明显,处理稀疏向量能力较弱,难以对长尾物品进行推荐。

6.3 CODE

篇幅略长,见本人Github页面User-basedCF notebook



  1. [Earliest CF] Using Collaborative Filtering to Weave an Information Tapestry (PARC 1992) 

  2. [ItemCF] Item-Based Collaborative Filtering Recommendation Algorithms (UMN 2001) 


Share this post
< Pre: 推荐系统概念 Pos: 矩阵分解和因子分解机 >
49 comments
Similar posts
Add a new comment