协同过滤(Collaborative Filtering)

协同过滤指的是人们协同起来，互帮互组，通过各自对文档、商品的反应来帮助别人过滤信息。[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. 协同过滤的基本问题形式

有一组用户列表协同过滤 - 图1和商品列表协同过滤 - 图2，每个用户协同过滤 - 图3都有一组已经进行过评论的商品协同过滤 - 图4，评价通常是属于特定区间的数值，例如0-5分，对于用户协同过滤 - 图5，有两个任务：

  1. 预测。给出该用户对商品协同过滤 - 图6的预测评价，其中协同过滤 - 图7
  2. 推荐。为该用户推荐他会最喜欢的一组商品协同过滤 - 图8，数量为协同过滤 - 图9，其中协同过滤 - 图10。也称为TopN推荐

2. 实现协同过滤的步骤

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

3. 如何计算相似性？

3.1 相似度

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

  1. Jaccard相似性
    是一种衡量两个集合间相似度的指标，计算的是两集合中交集与并集的比例。具体而言，如果协同过滤 - 图11%2C%20N(v)#card=math&code=N%28u%29%2C%20N%28v%29)分别表示用户协同过滤 - 图12交互的两个商品集合，两者Jaccard相似性为： 协同过滤 - 图13%5Ccap%20N(v)%20%5Cvert%20%7D%7B%5Csqrt%7B%5Cvert%20N(u)%5Cvert%20%5Ccup%20%5Cvert%20N(v)%5Cvert%7D%7D%0A#card=math&code=sim_%7Buv%7D%20%3D%20%5Cfrac%7B%5Cvert%20N%28u%29%5Ccap%20N%28v%29%20%5Cvert%20%7D%7B%5Csqrt%7B%5Cvert%20N%28u%29%5Cvert%20%5Ccup%20%5Cvert%20N%28v%29%5Cvert%7D%7D%0A)


缺点：细粒度比较低，只能简单的考虑对某商品是否喜欢，而没有考虑到具体的喜好程度（如评分）。

  1. 余弦相似性
    高中数学内容，就是求两向量间的夹角余弦值，一个优势是自带归一化。具体而言，同上集合描述： 协同过滤 - 图14%20%5Ccap%20N(v)%5Cvert%7D%7B%5Csqrt%7B%5Cvert%20N(u)%5Cvert%20%5Ccdot%20%5Cvert%20N(v)%5Cvert%7D%7D%0A#card=math&code=sim_%7Buv%7D%20%3D%20%5Cfrac%7B%5Cvert%20N%28u%29%20%5Ccap%20N%28v%29%5Cvert%7D%7B%5Csqrt%7B%5Cvert%20N%28u%29%5Cvert%20%5Ccdot%20%5Cvert%20N%28v%29%5Cvert%7D%7D%0A)


缺点：没有考虑到不同用户平均打分的偏差情况

  1. 皮尔逊相关系数
    皮尔逊相关系数，相较于余弦相似度，引入用户的平均分，对各自独立评分进行修正，减小了用户评分偏置的影响。 协同过滤 - 图15(R%7Bvi%7D-%5Cbar%20R%7Bv%7D)%7D%7B%5Csqrt%7B%5Csum%7Bi%5Cin%20I%7D(R%7Bui%7D-%5Cbar%20Ru)%5E2%7D%5Csqrt%7B%5Csum%7Bi%5Cin%20I%7D(R%7Bvi%7D-%5Cbar%20R_v)%5E2%7D%7D%0A#card=math&code=sim%7Buv%7D%20%3D%20%5Cfrac%7B%5Csum%7Bi%5Cin%20I%7D%28R%7Bui%7D-%5Cbar%20R%7Bu%7D%29%28R%7Bvi%7D-%5Cbar%20R%7Bv%7D%29%7D%7B%5Csqrt%7B%5Csum%7Bi%5Cin%20I%7D%28R%7Bui%7D-%5Cbar%20R_u%29%5E2%7D%5Csqrt%7B%5Csum%7Bi%5Cin%20I%7D%28R_%7Bvi%7D-%5Cbar%20R_v%29%5E2%7D%7D%0A)

3.2 用户相似度的改进

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

John S.Breese在论文中提出了如下公式，对共同兴趣物品中的热门商品进行了惩罚（协同过滤 - 图16#card=math&code=N%28i%29)是对物品协同过滤 - 图17有过行为的用户集合）：

协同过滤 - 图18%5Ccap%20N(v)%7D%5Cfrac%7B1%7D%7B%5Clog%201%20%2B%20%5Cvert%20N(i)%5Cvert%7D%7D%7B%5Csqrt%7B%5Cvert%20N(u)%5Cvert%20%5Cvert%20N(v)%5Cvert%7D%7D%0A#card=math&code=sim%7Buv%7D%20%3D%20%5Cfrac%7B%5Csum%7Bi%5Cin%20N%28u%29%5Ccap%20N%28v%29%7D%5Cfrac%7B1%7D%7B%5Clog%201%20%2B%20%5Cvert%20N%28i%29%5Cvert%7D%7D%7B%5Csqrt%7B%5Cvert%20N%28u%29%5Cvert%20%5Cvert%20N%28v%29%5Cvert%7D%7D%0A)

3.3 API

  1. # 余弦相似度
  2. from sklearn.metrics.pairwise import cosine_similarity
  3. cosine_similarity(i, j) 
  5. # 皮尔逊相关系数
  6. import numpy as np
  7. np.corrcoef([i, j])
  8. from scipy.stats import pearsonr
  9. pearsonr(i, j)

4. 评估指标

如果协同过滤 - 图19#card=math&code=R%28u%29)是给用户协同过滤 - 图20的推荐列表（根据训练集计算的，对测试集上物品的预测），协同过滤 - 图21#card=math&code=T%28u%29)是用户在测试集上的行为列表，协同过滤 - 图22是所有需要进行推荐用户的集合。通常按时间顺序给数据进行训练集和测试集分割。

4.1 准确率

协同过滤 - 图23%5Cvert%20%5Ccap%20%5Cvert%20T(u)%5Cvert%7D%7B%5Csum%7Bu%5Cin%20U%7D%5Cvert%20R(u)%5Cvert%7D%0A#card=math&code=Precision%20%3D%20%5Cfrac%7B%5Csum%7Bu%5Cin%20U%7D%5Cvert%20R%28u%29%5Cvert%20%5Ccap%20%5Cvert%20T%28u%29%5Cvert%7D%7B%5Csum_%7Bu%5Cin%20U%7D%5Cvert%20R%28u%29%5Cvert%7D%0A)

4.2 召回率

协同过滤 - 图24%5Cvert%20%5Ccap%20%5Cvert%20T(u)%5Cvert%7D%7B%5Csum%7Bu%20%5Cin%20U%7DT(u)%7D%0A#card=math&code=Recall%20%3D%20%5Cfrac%7B%5Csum%7Bu%5Cin%20U%7D%5Cvert%20R%28u%29%5Cvert%20%5Ccap%20%5Cvert%20T%28u%29%5Cvert%7D%7B%5Csum_%7Bu%20%5Cin%20U%7DT%28u%29%7D%0A)

5. 数据倒排

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

  • 相似度高，为协同过滤 - 图25#card=math&code=O%28n%5E2%29)
  • 很多用户交互过的物品很少，交互物品并集为空，也会被保存

提升措施：建立物品-用户倒排表（键为物品，值为用户及评分）

优势：

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

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

此时相似度，如余弦相似度计算如下（设物品-用户倒排表为协同过滤 - 图28，用户-用户共现矩阵为协同过滤 - 图29，用户评分次数字典为协同过滤 - 图30，相似度矩阵为S）：

协同过滤 - 图31

5. User-based CF

5.1 步骤

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

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

5.2 对最终评价的确定方式

对于商品协同过滤 - 图32和用户协同过滤 - 图33，协同过滤 - 图34的最相似用户集为协同过滤 - 图35，协同过滤 - 图36为其中元素，假设用户协同过滤 - 图37、用户协同过滤 - 图38对商品的评价分为别：协同过滤 - 图39，对商品协同过滤 - 图40有过行为的用户集为协同过滤 - 图41#card=math&code=N%28i%29)。计算得两用户的相似性为协同过滤 - 图42，则用户协同过滤 - 图43对商品协同过滤 - 图44的评价预测为：

协同过滤 - 图45

上述方式将各相似用户对目标商品的评价按相似性权重进行了加权，得到的结果作为最终预测结果。另外还有一种方式，考虑了用户内心的评分情况，相当于把相似用户对商品的评分都减去了自身对所用商品的平均评分，再加上用户的平均评分，并且只考虑有过行为的用户，相比之下会更加符合情况。

协同过滤 - 图46%7Dw%7Bus%7D(R%7Bsi%7D-%20%5Cbar%20Rs)%7D%7B%5Csum%7Bs%5Cin%20S%5Ccap%20N(i)%7Dw%7Bus%7D%7D%0A#card=math&code=R%7Bup%7D%20%3D%20%5Cbar%20Ru%20%2B%20%5Cfrac%7B%5Csum%7Bs%5Cin%20S%20%5Ccap%20N%28i%29%7Dw%7Bus%7D%28R%7Bsi%7D-%20%5Cbar%20Rs%29%7D%7B%5Csum%7Bs%5Cin%20S%5Ccap%20N%28i%29%7Dw_%7Bus%7D%7D%0A)

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

7. 工业上的流程

7.1 数据处理

  • 对对行为很少的用户进行过滤
  • 对用户中的热门物品进行过滤
  • 对用户的相似用户（包含非常活跃用户）进行适当过滤

7.2 数据缓存

对相似度矩阵和N个相似用户的TopK物品进行保存

7.3 模型更新

定期更新，可能是一天一次，可能是多长时间间隔，更新数据为前N天的活跃用户数据

8. 方法使用

UserCF给用户推荐与自身兴趣相投用户的物品，ItemCF是给用户推荐那些和他之前最喜欢物品类似的物品。

User-based CF场景（社交化）

新闻

Item-based CF场景（个性化）

图书、电子商务、电影等

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

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