协同过滤

8/2/2021 协同过滤

# 请简述基于用户的协同过滤UserCF的推荐过程。

UserCF(User Collaboration Filter),即基于用户的协同过滤算法。其中协同过滤的含义是不同的用户通过与item的互动比如点赞、收藏等,使自己的推荐列表过滤掉自己不感兴趣的物品,从而得到最终的推荐结果。

以电商网站为例,他的步骤一般分为:

1)构成用户交互行为共现矩阵

假如用户对商品有浏览、收藏、加入购物车、购买这四种交互行为,我们分别给他们赋予分数 1分/3分/5分/10分,然后转化为共现矩阵,其中第一列表示用户,第一行表示商品,如下:

item1 item2 item3 item4 item5 item6
A 1 5 3
B 3 3
C 5 3 10
D 10 5
E 10 5 1

2)用户相似度计算

生成共现矩阵之后,问题就转为预测共现矩阵中空白位置的值。UserCF通过计算用户之间的相似度,找到用户相似度最高的topN个用户。

关于相似度计算,我们会在下一个问答中进行详细描述。

3)最终结果排序

得到相似度最高的N个用户之后,我们假定目标用户与其相似用户的喜好是相似的,可以根据其相似用户的已有评价对目标用户的偏好进行预测。往往通过加权平均的方式计算:

其中表示用户u和用户s的相似度,表示用户s对物品p的评分。最终的推荐列表根据预测得分进行排序即可。

# 在基于用户的协同过滤中,如何计算用户的相似度?

计算两个向量相似度的方式很多,cosine余弦是被证明在很多场景效果都不错的一个算法,但并不是所有场景cosine余弦都是最好的,需要针对不同场景做尝试和对比。

共现矩阵中的行向量表示用户向量,计算用户i和用户j的相似度问题,就是计算用户向量i和用户向量j之间的相似度,往往有以下几种方法:

  • 余弦相似度

余弦相似度的缺陷是认为缺失值是0,但实际上并不总是如此。它衡量了用户向量i和用户向量j之间的向量夹角大小,夹角越小,余弦相似度越大,用户则越相似。

针对隐式反馈(用户只有点击等行为,没有评分),向量的元素要么为1要么为0,直接用cosine余弦公式效果不是很好,可以对隐式反馈进行打分,比如浏览给1分,收藏给3分,分享给5分等,取用户对item所有的隐式反馈行为中得分最高的.

  • 皮尔逊相关系数

皮尔逊相似度使用用户平均分对评分进行修正,减小了用户评分偏置的影响。缺失值也是按用户平均分计算。其中表示用户i对物品p的打分,表示用户i对所有物品的平均均分,p表示所有物品的集合。

也可引入物品相似度的方式对其改造,从而减少物品评分偏置对结果的影响。其中代表物品p得到所有评分的平均分。

  • Jaccard相似度

杰拉德相似度没有考虑评分大小,仅仅计算用户之间的交集和并集物品的大小。

# 基于用户的协同过滤UserCF存在哪些缺陷?

1)在一个典型的互联网产品中,比如京东、淘宝、豆瓣、知乎,用户数往往远远大于物品的数量,而基于用户的协同过滤需要维护一个用户相似性矩阵,以便可以快速找出TopN相似用户。而维护该用户相似度矩阵所需的存储开销巨大,且随着业务发展,用户数的增长会导致用户相似度矩阵的空间复杂度以的速度快速增长,会导致在线存储系统无法承载。

2)用户的行为矩阵往往是非常稀疏的,他点击过或者发生过行为的物品只占全量物品的很小一部分,而对于这样行为很稀疏的用户来说,通过相似度矩阵去寻找相似用户,准确度很低,存在很大的偶然性,并不能说明其确实存在相似性。对于那些反馈获取很少的产品来说,很难有好的推荐效果。

# 请简述基于物品的协同过滤ItemCF的推荐过程。

ItemCF(Item Collaboration Filter),即基于物品的协同过滤算法,它通过计算共现矩阵中物品列向量的相似度得到物品之间的相似度矩阵,再找到用户的历史正反馈物品的相似物品进行进一步排序和推荐。具体过程如下:

1)构成共现矩阵

item1 item2 item3 item4 item5 item6
A 1 5 3
B 3 3
C 5 3 10
D 10 5
E 10 5 1

2)物品相似度矩阵计算

计算共现矩阵两两列向量(物品向量)之间的相似度,构建物品相似度矩阵。

3)最终结果排序

针对用户历史正反馈物品列表,根据物品相似度矩阵,找出相似的TopN的物品,最终的物品排序计算逻辑如下:

其中为用户历史正反馈物品列表,是物品与物品的相似度,是用户对物品的已有评分。

# 请简述一下基于物品的协同过滤算法的离线工程实现(spark)

假设共现矩阵为

item1 item2 item3 item4 item5
userA 1 5 3
userB 3 2 3
userC 5 3 2
  1. 首先将所有用户有过反馈的item收集起来,形成一个用户行为向量RDD,格式为,具体如下:

  2. 对每个user的有过反馈的item做包含自身的笛卡尔积,并将对应的score相乘,得到如下的RDD:

  3. 将相同的item对进行group后相加:

这样我们就得到了计算cosine相似度时所需的分子

而分母就是上述第3步得到的RDD过滤出item相同的,因为数量至多为item的个数,可将其广播出来,通过collectAsMap得到一个key为item,value为score的map。

这样分子分母都出来了,就可以计算item与item之间的相似度了。

以上步骤得到item之间的相似度,接下来计算每个item最相似的item的topK:

如果我们把每个item最相似的K个标的物及相似度看成一个列向量的话,那么我们计算出的item相似度其实可以看作方阵,该矩阵每列K个非零元素。

到此为止,我们通过Spark提供的一些Transformation操作及一些工程实现上的技巧计算出了每个标的物topK最相似的标的物,下面我们来说明一下为用户生成个性化推荐的过程:

假设给定需要推荐的用户行为矩阵为,其中n是用户数,m是item的数量,第i行第j列的元素代表了用户i对物品j的偏好。

物品相似度矩阵为,这两个都是稀疏矩阵,我们通过计算这两个矩阵的乘积(Spark上是可以直接计算两个稀疏矩阵的乘积的),最终的结果矩阵就可以方便用来为用户推荐了:

其中的第i行代表的是用户i对每个标的物的偏好得分,我们从这个列表中过滤掉用户操作过的item,然后按照得分从高到低降序排列取topN就是最终给用户的推荐。

也可以将item的相似度矩阵broadcast到各个节点上,并转化为map结构,有了item之间的相似度map,为用户计算推荐的过程可以基于用户行为RDD,在每个Partition中,针对每个用户u计算u与每个标的物之间的偏好度,再取topN就得到该用户的推荐结果了。

# 协同过滤算法计算过程中的大规模稀疏矩阵相乘在spark中的现有方案(multiply)有什么缺陷?如何改进?

spark 可以通过 BlockMatrix 进行矩阵相乘,如下:

from pyspark.mllib.linalg.distributed import *
M_rdd = sc.parallelize([(0,0, 1), (0,1, 2), (0,2, 3), (1,0, 4), (1,1, 5), (1,2, 6)])
N_rdd = sc.parallelize([(0,0, 7), (0,1, 8), (1,0, 9), (1,1, 10), (2,0, 11), (2,1, 12)])
M = CoordinateMatrix(M_rdd).toBlockMatrix()
N = CoordinateMatrix(N_rdd).toBlockMatrix()
M.multiply(N).toCoordinateMatrix().entries.collect()
1
2
3
4
5
6

但在spark 的官方文档中关于 multiply 这个方法的描述:

Left multiplies this BlockMatrix by other, another BlockMatrix. The colsPerBlock of this matrix must equal the rowsPerBlock of other. If other contains any SparseMatrix blocks, they will have to be converted to DenseMatrix blocks. The output BlockMatrix will only consist of DenseMatrix blocks. This may cause some performance issues until support for multiplying two sparse matrices is added.
1

就是说,BlockMatrix 在进行矩阵乘法时会先把稀疏矩阵转换成稠密矩阵!!对于一个 10000 x 10000 的稀疏矩阵,实际存储的可能只有几万个非零元素,而转换成稠密矩阵后,你需要对所有 10000 x 10000 = 1亿 个元素提供存储空间!!而实际场景面对的稀疏矩阵的维度远远大于 10000,所以 BlockMatrix 无法适用于大规模稀疏矩阵运算。

如何去解决呢?我们先来看一下矩阵乘法的公式:

$$P_{i,k}=\sum_jm_{ij}*n_{jk} $$

从矩阵乘法公式可知,矩阵相乘主要有以下环节:

  1. 左矩阵的列号(j)与右矩阵的行号(j)相同的元素进行两两相乘得到
  2. 对所有具有相同下标(ik)的 进行相加,即得到

我们可以基于 RDD 实现矩阵乘法

思路:

  1. 先通过 map 函数构建以左矩阵的列号(j)和右矩阵的行号(j)作为 key 的数据结构。即
  2. 对上一步骤进行 join 运算得到
  3. 对上一步骤的值通过 map 函数构建以左矩阵的行号(i)和右矩阵的列号(k)作为 key , 且对应元素的积作为 value 的数据结构。即
  4. 对上一步骤进行 reduceByKey, 对 (i,k) 相同的两两结果进行相加即得到第i行第k列的结果, 即
from pyspark.mllib.linalg.distributed import *
M_rdd = sc.parallelize([(0, 0, 1), (0, 1, 2), (0, 2, 3), (1, 0, 4), (1, 1, 5), (1, 2, 6)])
N_rdd = sc.parallelize([(0, 0, 7), (0, 1, 8), (1, 0, 9), (1, 1, 10), (2, 0, 11), (2, 1, 12)])
M = CoordinateMatrix(M_rdd)
N = CoordinateMatrix(N_rdd)
 
M = M.entries.map(lambda entry: (entry.j, (entry.i, entry.value)))
N = N.entries.map(lambda entry: (entry.i, (entry.j, entry.value)))
 
matrix_entries = M.join(N).values().map(
    lambda x: ((x[0][0], x[1][0]), x[0][1] * x[1][1])
).reduceByKey(
    lambda x, y: x + y
).map(
    lambda x: MatrixEntry(x[0][0], x[0][1], x[1])
)
 
matrix = CoordinateMatrix(matrix_entries)
matrix.entries.collect()
 
######## 输出 #############
# [MatrixEntry(0, 0, 58.0),
#  MatrixEntry(1, 0, 139.0),
#  MatrixEntry(0, 1, 64.0),
#  MatrixEntry(1, 1, 154.0)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

也可以基于DataFrame 实现矩阵乘法

  • 基于 DataFrame 方式并非将每一列号作为一个单独字段,而是将矩阵里面的每一个元素看成一个三维数据,即(行号,列号,值),将一个矩阵转化为一个包含三个字段的 table,对于一个稀疏矩阵,只需要记录非零元素,即 100 个非零元素就对应 DataFrame 的 100 行。
  • 计算逻辑与 RDD 方式非常相似,主要有三个流程 join => groupby => agg。
  • 基于 DataFrame 方式能大幅度提升运算速度,因为 DataFrame 相比 RDD 有更佳的优化支持。
from pyspark.mllib.linalg.distributed import *
from pyspark.sql import SparkSession, functions as F
 
ss = SparkSession.builder.appName("test") \
    .config("spark.serializer", "org.apache.spark.serializer.KryoSerializer") \
    .getOrCreate()
 
M_rdd = sc.parallelize([(0, 0, 1), (0, 1, 2), (0, 2, 3), (1, 0, 4), (1, 1, 5), (1, 2, 6)])
N_rdd = sc.parallelize([(0, 0, 7), (0, 1, 8), (1, 0, 9), (1, 1, 10), (2, 0, 11), (2, 1, 12)])
 
M = ss.createDataFrame(M_rdd, ['l_row', 'l_column', 'l_val'])
N = ss.createDataFrame(N_rdd, ['r_row', 'r_column', 'r_val'])
M.join(
    N, M['l_column']==N['r_row']
).groupBy(
    'l_row', 'r_column'
).agg(
    F.sum(M['l_val']*N['r_val'])
).toDF('row', 'column', 'val').show()

######## 输出 #############
# +---+------+---+
# |row|column|val|
# +---+------+---+
# |  1|     1|154|
# |  0|     1| 64|
# |  1|     0|139|
# |  0|     0| 58|
# +---+------+---+

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

以下是这三种方法的性能对比:

  • DataFrame 方式性能上最好;
  • BlockMatrix 方式虽然比 RDD 方式速度更快,但当矩阵维度增大后非常容易出现 OOM 问题;

# 请简述协同过滤算法的优缺点

  • 优点

1、算法原理朴素简单,即“物以类聚,人以群分”,已得到工业界验证过的一类重要算法,在Netflix、Google、Amazon及国内大型互联网公司都有很好的落地和应用; 2、易利用Spark分布式平台来实现,因此可以通过增加计算节点很容易处理大规模数据集; 3、可以很好的为用户推荐多样性、新颖性的item。特别是当群体规模越大,用户行为越多,推荐的效果越好。 4、只依赖用户的操作行为,不依赖具体user相关和item相关的信息就可以实现,往往user信息和item信息都是比较复杂的半结构化或者非结构化的信息,处理起来很不方便。这是一个极大的优势,正因为这个优势让协同过滤算法在工业界大放异彩。

缺点:

1、冷启动问题

协同过滤算法依赖用户的行为来为用户做推荐,如果用户行为少(比如新上线的产品或者用户规模不大的产品),这时就很难发挥协同过滤算法的优势和价值,甚至根本无法为用户做推荐

对于新入库的item,由于只有很少的用户操作行为,这时相当于用户行为矩阵中该item对应的列基本都是零,这时无法计算出该item的相似item,同时,该item也不会出现在其他标的物的相似列表中,因此无法将该item推荐出去。这时,可以采用人工的策略将该item在一定的位置曝光,或者强行以一定的比例或者概率加入推荐列表中,通过收集该item的行为解决该标的物无法被推荐出去的问题。

2、稀疏性问题

互联网产品用户基数大,item数量多(特别是新闻、UGC短视频类产品),一般用户只对很少量的item产生操作行为,这是用户操作行为矩阵是非常稀疏的,太稀疏的行为矩阵计算出的item相似度往往不够精准,最终影响推荐结果的精准度。

# 在实际业务中,为了让协同过滤有更好的效果,对业务产生较大的价值,我们在使用该算法时需要注意哪些问题?

1、考虑是使用userCF还是itemCF:

在互联网产品中一般会采用itemCF协同过滤,因为user相对于item变化更大,用户是增长较快的,item增长相对较慢(这也不是绝对的,像新闻、短视频类应用标的物也是增速巨大的),利用itemCF算法效果更稳定。

2、时间加权

一般来说,用户的兴趣是随着时间变化的,越是久远的行为对用户当前的兴趣贡献越小,基于此,可以对用户行为矩阵做时间加权处理。将用户评分加上一个时间惩罚因子,对久远的行为进行一定的惩罚,可行的惩罚方案可以采用指数衰减的方式。例如,我们可以采用如下的公式来对时间做衰减,我们可以选择一个时间作为基准值,比如当前时间,下式中的n是item操作时间与基准时间相差的天数(n=0时,w(0)=1)。

3、隐式反馈评分

在真实业务场景中,用户不一定对item评分,可能只有操作行为。这时可以采用隐式反馈的方式来做协同过滤,虽然隐式反馈的效果可能会差一些。

但同时,我们是可以通过一些方法和技巧来间接获得隐式反馈的评分,主要有如下两类方法,通过这两类方法获得评分,是非常直观的,效果肯定比隐式反馈直接用0或者1好。

基于用户的浏览、点击、点赞、购买、收藏、分享、评论等隐式行为的投入度,即投入的时间成本、资金成本、社交压力等,投入成本越大给定越高的分数,对这些行为人为打分,比如浏览给1分,点赞给2分,转发给4分等等。这样我们就可以针对用户不同的行为生成差异化的评分。

对于像音乐、视频、文章等,我们可以记录用户在消费这些item上所花的时间来计算评分。拿视频来说,如果一个电影总时长是100分钟,如果用户看了60分钟就退出了,那么我们就可以给用户打6分。

# 协同过滤算法会存在冷启动的问题,主要体现在哪里?

  • 用户冷启动

用户冷启动就是新用户没有太多的行为,我们无法为他计算个性化推荐。这时可行的推荐策略是为这类用户推荐热门标的物、通过人工编排筛选出的标的物。或者用户只有很少的行为,协同过滤效果也不好,这时可以采用基于内容的推荐算法补充。

  • 物品冷启动

新的标的物加入系统,没有用户操作行为,这时协同过滤算法也无法将该标的物推荐给用户。可行的解决方案有三个:

  1. 人工曝光到较好的推荐位上,在短时间内获取足够多的用户行为,但如果该item不够主流,会影响用户体验;
  2. 在推荐算法上做一些策略,可以将这类新的item以一定的概率混杂在用户的推荐列表中,让这些标的物有足够多的曝光,在曝光过程中收集用户行为,同时该方法也可以提升用户推荐的多样性。
  3. 通过基于内容的推荐算法来分发出去
  • 系统冷启动

所谓系统冷启动,就是该产品是一个新开发不久的产品,还在发展用户初期阶段,这时协同过滤算法基本无法起作用,最好采用基于内容的推荐算法或者直接利用编辑编排一些多样性的优质内容作为推荐备选推荐集。

# 协同过滤算法可以用于哪些推荐业务场景?

1、完全个性化推荐

即为每个用户推荐不一样的标的物推荐列表,比如淘宝猜你喜欢;

2、item关联item推荐

利用该item相似度可以计算某个item最相似的K个item,这K个最相似的标的物就可以作为该标的物的关联推荐。比如豆瓣的相似影片推荐。

3、其他应用形式及场景

将用户或者物品用向量表示(用户行为矩阵中的行向量和列向量),有了用户和标的物的向量表示,我们就可以对用户和物品做聚类了。

对用户聚类后,当然可以用于做推荐,将同一类中其他用户操作过的标的物推荐给该用户就是一种可行的推荐策略。同时,用户聚类后,也可以用于做lookalike类的商业化(如广告)尝试。

对物品聚类后,也可以用于做物品关联推荐,将同一类中的其他物品作为关联推荐结果。另外,物品聚类后,这些类可以作为专题供编辑或者运营团队来作为一种内容分发的素材。

# 请简述近实时协同过滤算法的工程实现

近实时的协同过滤主要用于对时效性要求比较高的产品形态,比如新闻、短视频等应用。这些应用item更新快,用户消耗一个item(读一篇文章、看一段短视频)所花的时间较短,这类应用一般是用于填补用户的碎片化时间的。而对于电商、视频等产品,近实时的协同过滤不是必须的。