协同过滤(Collaborative Filtering)作为推荐算法中最经典的类型,包括在线的协同离线的过滤两部分。所谓在线协同,就是通过在线数据找到用户可能喜欢的物品,而离线过滤,则是过滤掉一些不值得推荐的数据,比比如推荐值评分低的数据,或者虽然推荐值高但是用户已经购买的数据。

协同过滤的模型一般为m个物品,n个用户的数据,只有部分用户和部分数据之间是有评分数据的,其它部分评分是空白,此时我们要用已有的部分稀疏数据来预测那些空白的物品和数据之间的评分关系,找到最高评分的物品推荐给用户。

一般来说,协同过滤推荐分为三种类型。
第一种是基于用户(user-based)的协同过滤
第二种是基于物品(item-based)的协同过滤
第三种是基于模型(model based)的协同过滤

基于用户(user-based)的协同过滤主要考虑的是用户和用户之间的相似度,只要找出相似用户喜欢的物品,并预测目标用户对对应物品的评分,就可以找到评分最高的若干个物品推荐给用户。

而基于物品(item-based)的协同过滤和基于用户的协同过滤类似,只不过这时我们转向找到物品和物品之间的相似度,只有找到了目标用户对某些物品的评分,那么我们就可以对相似度高的类似物品进行预测,将评分最高的若干个相似物品推荐给用户。比如你在网上买了一本机器学习相关的书,网站马上会推荐一堆机器学习,大数据相关的书给你,这里就明显用到了基于物品的协同过滤思想。

我们可以简单比较下基于用户的协同过滤和基于物品的协同过滤:基于用户的协同过滤需要在线找用户和用户之间的相似度关系,计算复杂度肯定会比基于基于物品的协同过滤高。但是可以帮助用户找到新类别的有惊喜的物品。而基于物品的协同过滤,由于考虑的物品的相似性一段时间不会改变,因此可以很容易的离线计算,准确度一般也可以接受,但是推荐的多样性来说,就很难带给用户惊喜了。

一般对于小型的推荐系统来说,基于物品的协同过滤肯定是主流。但是如果是大型的推荐系统来说,则可以考虑基于用户的协同过滤,当然更加可以考虑我们的第三种类型,基于模型的协同过滤。

基于模型(model based)的协同过滤是目前最主流的协同过滤类型了,我们的一大堆机器学习算法也可以在这里找到用武之地。


1. 基于用户的协同过滤(User-based Collaborative Filtering)

概念

首先用一个词就能很好的解释什么叫做基于用户的协同过滤算法:【臭味相投】。虽然是贬义词,但也说明了,具有类似特征的人群,他们喜欢的东西很多也是一样的。因此,在推荐系统中,假设要为A用户推荐物品,可以通过寻找他的“邻居”——与A具有相似兴趣的用户。把那些用户喜欢的,而A用户却不曾听说的东西推荐给A。

相似度算法

那么问题来了,我们如何判断A用户与哪些用户相似呢?关键就是根据用户过去的行为轨迹,计算用户相似度。
目前较多的相似度算法有:

1. 计算用户间的相似度

假设A用户喜欢{a,b,d},B用户喜欢{a,c},则他俩相似度计算过程如下:

(1)余弦相似度算法(Ochiai coefficient落和系数)计算用户间的相似度

N(u)表示用户u感兴趣的物品集合,N(v)表示用户v感兴趣的物品集合,简单解释一下这个公式,分母是两个集合绝对值相乘的平方根,分子是集合的交集的绝对值,**集合绝对值是这个集合中元素的个数**。

(2)Jaccard相似度算法(Jaccard coefficient)计算用户间的相似度

N(u)表示用户u感兴趣的物品集合,N(v)表示用户v感兴趣的物品集合,简单解释一下这个公式,分母是两个集合的并集的绝对值,分子是集合的交集的绝对值,集合绝对值是这个集合中元素的个数

2. 倒排

但是这么简单粗暴是有问题的,因为很多用户其实完全没有共同喜好的,也就是分子会为0。这么多无意义的计算会给我们增加很大的开销,所以我们应该先做一个预处理,把有关联的用户筛选出来,只计算这些有关联的用户的兴趣相似度。倒排法有效的为我们解决了这个问题:

2.1 首先将用户—物品表转化为物品—用户表(倒排表)
2.2 根据倒排表画出相似度矩阵(比如倒排表第一行说明AB BC AC有关联,就在矩阵中置1,第二行说明AC有关联,又加1变为了2)

矩阵中为0的我们就不需要去计算它们的兴趣相似度了。
得到用户相似度之后,我们开始计算用户对物品的兴趣度。

3. 计算用户对物品的兴趣度
用户u对物品i的感兴趣程度公式如下:

S(u, K)是与用户u兴趣最接近的K个用户的集合, N(i)是对物品i有过行为的用户集合,既然要判断u对物品i的兴趣程度,当然是要从兴趣最接近的K个用户中挑出对i有过行为的,所以取交集。 是用户u和用户v的兴趣相似度, 代表用户v对物品i的兴趣,因为使用的是单一行为的隐反馈数据,所以另其等于1。

上图中,用户B对物品b和d没有过行为,我们来计算用户B对物品b和d的感兴趣程度

3.1 计算B 与 A C D的用户相似度,取前两名,显然是用户C(W=0.5)与用户A(W=0.41)
3.2 计算B对物品b的兴趣度:用户A和C都对b有过行为,所以累加,结果0.5+0.41=0.91
3.3 计算B对物品d的兴趣度:只有A对d有过行为,因此S(u, K)交N(i)只剩下A,结果0.41

4. Top-N分析法
得到用户对物品的兴趣度后,我们使用Top-N推荐。

TOP-N分析法就是通过TOP-N算法从研究对象中得到所需的N个数据,并从排序列表中选取最大或最小的N个数据,这就是一个TOP-N算法。即对所有物品进行P(u,i)计算兴趣度后进行降序,取前N个物品推荐给用户

缺陷和改进

看似很完美了~其实还有个问题~
试问:我和XXX都买了英语六级教程,那能说明咱们兴趣一样吗?不一定吧,买六级只是考试必备,对大部分人而言是一种无奈的操作。。。因此,我们要精确判断两人兴趣一样,不应该拿这些热门的物品做决策。冷门的产品更能说明问题。比如,我和XXX都买了java教程,那么应该就能说明我们有共同的兴趣了。所以有了一个更精确的公式:

1/log1+|N(i)| 惩罚了用户u和用户v共同兴趣列表中热门物品对他们相似度的影响,使得结果更为精确。

2. 基于物品的协同过滤算法(Item-based Collaborative Filtering)

概念

假设某天你购买了机器学习书籍,那么淘宝会给你推荐python书籍。因为机器经过判断得出这两者相似度很高,你既然会喜欢机器学习那么理应喜欢python。

基于物品的协同过滤算法就是给用户推荐那些和他们之前喜欢的物品相似的物品。

不过, ItemCF算法并不利用物品的内容属性计算物品之间的相似度,它主要通过分析用户的行为记录计算物品之间的相似度。该算法认为,物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品B。

1. 计算物品间的相似度

这里我们使用余弦相似度算法(Ochiai coefficient落和系数)

2. 倒排
跟上面一样,我们要过滤出物品i和j完全没关系的,不做不必要的计算。因为上面详细解释过,这里就粗略的画一下结果图,省略了中间那个物品对用户的图。

通过计算得到Wab=0.82,Wac=0.58,Wad=0.58

3. 计算用户对物品的兴趣度
用户u对物品j的感兴趣程度计算公式:

此公式与上面基于用户的公式非常相像。S(j,K)表示与j物品最相似的k个物品的集合。N(u)表示用户喜欢的物品集合。Wji表示物品之间的相似度。rui是用户u对物品i的兴趣。(对于隐反馈数据集,如果用户u对物品i有过行为,即可令rui=1。)

Top-N分析
同上,计算出之后,对其排序,取前几名作为推荐物品推荐给用户。


3. 基于模型的协同过滤(Model-based Collaborative Filtering)

概念

基于模型的协同过滤作为目前最主流的协同过滤类型,其相关算法可以写一本书了,当然我们这里主要是对其思想做有一个归类概括。我们的问题是这样的m个物品,n个用户的数据,只有部分用户和部分数据之间是有评分数据的,其它部分评分是空白,此时我们要用已有的部分稀疏数据来预测那些空白的物品和数据之间的评分关系,找到最高评分的物品推荐给用户。

对于这个问题,用机器学习的思想来建模解决,主流的方法可以分为:用关联算法,聚类算法,分类算法,回归算法,矩阵分解,神经网络,图模型以及隐语义模型来解决。下面我们分别加以介绍。

3.1 用关联算法做协同过滤

一般我们可以找出用户购买的所有物品数据里频繁出现的物品集活序列,来做频繁集挖掘,找到满足支持度阈值的关联物品的频繁N项集或者序列。如果用户购买了频繁N项集或者序列里的部分物品,那么我们可以将频繁项集或序列里的其他物品按一定的评分准则推荐给用户,这个评分准则可以包括支持度,置信度和提升度等。

常用的关联推荐算法有Apriori,FP Tree和PrefixSpan。

3.2 用聚类算法做协同过滤

用聚类算法做协同过滤就和前面的基于用户或者项目的协同过滤有些类似了。我们可以按照用户或者按照物品基于一定的距离度量来进行聚类。如果基于用户聚类,则可以将用户按照一定距离度量方式分成不同的目标人群,将同样目标人群评分高的物品推荐给目标用户。基于物品聚类的话,则是将用户评分高物品的相似同类物品推荐给用户。

常用的聚类推荐算法有K-Means, BIRCH, DBSCAN和谱聚类。

3.2 用分类算法做协同过滤

如果我们根据用户评分的高低,将分数分成几段的话,则这个问题变成分类问题。比如最直接的,设置一份评分阈值,评分高于阈值的就是推荐,评分低于阈值就是不推荐,我们将问题变成了一个二分类问题。虽然分类问题的算法多如牛毛,但是目前使用最广泛的是逻辑回归。为啥是逻辑回归而不是看起来更加高大上的比如支持向量机呢?因为逻辑回归的解释性比较强,每个物品是否推荐我们都有一个明确的概率放在这,同时可以对数据的特征做工程化,得到调优的目的。目前逻辑回归做协同过滤在BAT等大厂已经非常成熟了。

常见的分类推荐算法有逻辑回归和朴素贝叶斯,两者的特点是解释性很强。

3.4 用回归算法做协同过滤

用回归算法做协同过滤比分类算法看起来更加的自然。我们的评分可以是一个连续的值而不是离散的值,通过回归模型我们可以得到目标用户对某商品的预测打分。

常用的回归推荐算法有Ridge回归,回归树和支持向量回归。

3.5 用矩阵分解做协同过滤

用矩阵分解做协同过滤是目前使用也很广泛的一种方法。由于传统的奇异值分解SVD要求矩阵不能有缺失数据,必须是稠密的,而我们的用户物品评分矩阵是一个很典型的稀疏矩阵,直接使用传统的SVD到协同过滤是比较复杂的。

目前主流的矩阵分解推荐算法主要是SVD的一些变种,比如FunkSVD,BiasSVD和SVD++。这些算法和传统SVD的最大区别是不再要求将矩阵分解为的形式,而变是两个低秩矩阵的乘积形式。    

3.6 用神经网络做协同过滤

用神经网络乃至深度学习做协同过滤应该是以后的一个趋势。目前比较主流的用两层神经网络来做推荐算法的是限制玻尔兹曼机(RBM)。在目前的Netflix算法比赛中, RBM算法的表现很牛。当然如果用深层的神经网络来做协同过滤应该会更好,大厂商用深度学习的方法来做协同过滤应该是将来的一个趋势。

3.7 用图模型做协同过滤

用图模型做协同过滤,则将用户之间的相似度放到了一个图模型里面去考虑,常用的算法是SimRank系列算法和马尔科夫模型算法。对于SimRank系列算法,它的基本思想是被相似对象引用的两个对象也具有相似性。算法思想有点类似于大名鼎鼎的PageRank。而马尔科夫模型算法当然是基于马尔科夫链了,它的基本思想是基于传导性来找出普通距离度量算法难以找出的相似性。

3.8 用隐语义模型做协同过滤

隐语义模型主要是基于NLP的,涉及到对用户行为的语义分析来做评分推荐,主要方法有隐性语义分析LSA和隐含狄利克雷分布LDA。


三种协同过滤比较:

基于用户的协同过滤需要在线找用户和用户之间的相似度关系,计算复杂度肯定会比基于基于项目的协同过滤高。但是可以帮助用户找到新类别的有惊喜的物品

基于项目的协同过滤,由于考虑的物品的相似性一段时间不会改变,因此可以很容易的离线计算,准确度一般也可以接受,但是推荐的多样性来说,就很难带给用户惊喜了。

一般对于小型的推荐系统来说,基于项目的协同过滤肯定是主流。但是如果是大型的推荐系统来说,则可以考虑基于用户的协同过滤,当然更加可以考虑我们的第三种类型,基于模型的协同过滤。基于模型(model based)的协同过滤是目前最主流的协同过滤类型了,我们的一大堆机器学习算法也可以在这里找到用武之地。


协同过滤总结

协同过滤作为一种经典的推荐算法种类,在工业界应用广泛,它的优点很多,模型通用性强,不需要太多对应数据领域的专业知识,工程实现简单,效果也不错。这些都是它流行的原因。

当然,协同过滤也有些难以避免的难题,比如令人头疼的“冷启动”问题,我们没有新用户任何数据的时候,无法较好的为新用户推荐物品。同时也没有考虑情景的差异,比如根据用户所在的场景和用户当前的情绪。当然,也无法得到一些小众的独特喜好,这块是基于内容的推荐比较擅长的。   


参考文章:
推荐算法概述
基于用户(UserCF)和基于物品(ItemCF)协同过滤算法原理