0%

推荐系统:协同过滤方法

打分矩阵

协同过滤中的 $UserCF$ 和 $ItemCF$ 都是基于打分矩阵的:

非个性化的解决方案

Just Average

$$ P_{ai} = \frac {\sum_{u=1}^n r_{ui}} {n} $$
存在的问题: 不同用户的给分程度是不一样的,如有的用户很严苛,给分都很低,有的很慷慨,给分都很高,所以需要减去其给分的均值。

Rating Normalization

$$ P_{ai} = \bar r_a + \frac {\sum_{u=1}^n (r_{ui}-\bar r_u)} {n} $$
存在的问题:这个打分可能超出打分区间,但是做推荐只需要一个顺序,所以并没有什么关系。

个性化的解决方案

$$ P_{ai} = \bar r_a + \frac {\sum_{u=1}^n (r_{ui}-\bar r_u)w_{a,u}} {\sum_{u=1}^nw_{a,u}} $$

  1. $w_{a,u}$ 表示的是用户之间的相似度,可以使用 $Pearson$ 相关系数来计算
  2. 在计算均分时只考虑与当前用户 $a$ 相似的用户对物品 $i$ 的打分
  3. 如果 $w_{a,u}$ 是负值,则去掉该用户,或者等价设置为 $0$
    存在的问题:如何选择相似用户

USER-USER 协同过滤方法

$UUCF$ 的一个直观理解:兴趣相近的用户可能会带来新颖的东西,对于一个用户 $u$ ,首先找到与其相似的一个用户集,这个相似是通过它们的打分来判定的,然后推荐用户集中用户喜欢的物品给用户 $u$。

基本假设

算法描述

存在问题

理论问题

  • 对于一个新用户,几乎没有打分,这样就找不到相似用户
  • 对于一个新物品,用户的所有邻居在该物品上都几乎没有打分

实际问题

在实际运算过程中,算法面临的最大的问题就是复杂度高。

改进策略

用户相似度:Similarities

重要性度量:Significance Weighting

共同打分多的用户相似的可能性更高,$50$ 是一个计算上界

权重差异:Variance Weighting

考虑特定的 $item$ 的差异波动,例如恐怖片,可能不同的人对此打分有很大的差异。因为喜欢恐怖片的用户和不喜欢恐怖片的用户其打分肯定相差大,但是在 $UserCF$ 中这个方法并没有取得什么优化。

物品归一化:Normalizing Ratings

归一化主要解决的就是不同用户的给分程度是不一样的问题
$$ P_{ai} = \bar r_a + \frac {\sum_{u=1}^n (r_{ui}-\bar r_u)} {n} $$

$$ P_{ai} = \bar r_a + \sigma_a \frac {\sum_{u=1}^n z_{ui}} {n} $$

其中,$\sigma_a$ 表示的是用户 $a$ 所有打分的均方差,$z_{ui} = \frac {r_{ui} - \bar r_u} {\sigma_u} $

邻居选择:Selecting Neighborhoods

步骤

数量

  • 在不同的 $item$ 上使用相同的 $user group$
  • 目标 $item$ 的打分过少时,放弃个性化推荐

总结:Summary

ITEM-ITEM 协同过滤方法

$ItemCF$ 的一个直观理解,用户可能喜欢相似的物品。 $ItemCF$ 算法并不利用物品的内容属性计算物品之间的相似度,它主要通过分析用户的行为记录计算物品之间的相似度。

算法动机

$UserCF$ 在很多情况下的表现性能都非常好,但是也存在很多问题:

  1. Lower Coverage,对一个很大的数据集来讲,某些物品的打分较少将会影响整体的推荐效果
  2. Computational performance,用户较多的情况,计算用户相似度是一件很耗时的工作,并且用户的画像是在不断变化的,所以需要频繁地更新用户相似度。

$ItemCF$ 适用于物品比用户少的情况,物品的属性值相对来说是恒定的,可以在很大程度上减少计算量,并且物品的相似度可以提前计算。

基本假设

算法的基本假设是用户的口味需要符合大众口味,算法的局限性也很明显,因为是通过用户在相似的物品集上的打分来预测在新物品上的打分,这就使算法过分依赖于矩阵的稀疏程度,若用户打分的物品和相似物品集合重合度较低,则预测效果较差。

算法描述

选择相似物品

  • 如果 $Itemset_u$ 和 $Neighbor_i$ 的交点过少,则应当放弃推荐
  • 在 $k$ 的选择上,如果 $k$ 较大可能会有噪声的影响,如果 $k$ 较小则可能会出现稀疏问题,通常情况下 $k=30$ 是一个较好的选择
  • 需要注意的是在求物品相似度之前一定要进行打分的归一化,因为不同用户的打分倾向不同

计算物品得分

$$ P_{ui} = \frac {\sum_{j \in N} sim(i,j) r_{uj}} {\sum_{j \in N} |sim(i,j)|} $$

即通过用户在 $itemj$ 上的打分来预测用户对 $itemi$ 的喜好程度

算法示例

$$r_51 = (0.412 + 0.593)/(0.41 + 0.59) = 2.6$$

改进策略

物品相似度:Similarities

在计算物品相似度之前,首先需要进行归一化操作,为防止不同用户的打分习惯造成的影响,随后再进行求相似度

重要性度量:Significance Weighting

作用不大,因为一个 $item$ 上面的打分数量会比较多

权重差异:Variance weighting

考虑不同 $user$ 之间打分的差异, $UserCF$ 是考虑特定 $item$ 打分的不同

物品归一化:Normalizing Ratings

不需要

邻居选择:Selecting Neighborhoods

和 $UserCF$ 上的方法相同

一元数据上的 ItemCF


那些喜欢很多 $item$ 的用户通常会提供较少的有效信息。

UserCF 和 ItemCF 的比较

$UserCF$ 的推荐结果着重于反映和用户兴趣相似的小群体的热点,而 $ItemCF$ 的推荐结果着重于维系用户的历史兴趣。换句话说,$UserCF$ 的推荐更社会化,反映了用户所在的小型兴趣群体中物品的热门程度,而 $ItemCF$ 的推荐更加个性化,反映了用户自己的兴趣传承。

从技术上考虑,$UserCF$ 需要维护一个用户相似度的矩阵,而 $ItemCF$ 需要维护一个物品相似度矩阵。从存储的角度说,如果用户很多,那么维护用户兴趣相似度矩阵需要很大的空间,同理,如果物品很多,那么维护物品相似度矩阵代价较大。所以 $UserCF$ 更适合用于个性化新闻推荐, $ItemCF$ 更适合于图书、电子商务和电影的个性化推荐。

考虑如下表所示的一个打分矩阵:打分

$$\begin{array}{c|lcr} & I_1 & I_2 & I_3 & 4_1 & I_5 \\ \hline U_1 & & 5 & 3 & 1 & 1 \\ U_2 & 4 & 5 & 3 & & 2 \\ U_3 & 2 & 1 & & 5 & 4 \\ U_4 & & 2 & 3 & & 3\\ U_5 & 5 & 1 & 2 & 4 & ?\\ \end{array}$$

$UUCF: r_{55} = r_{45} = 3 \;\;\; IICF: r_{55} = r_{54} = 4$

基于降维分解的协同过滤方法

FunkSVD

$FunkSVD$ 的训练过程是利用已有值进行矩阵分解,在训练过程中可以忽略矩阵中空缺的数据,$R_{n\times m} \approx U_{n\times k}V_{k\times m}$,在计算出 $UV$ 之后,相乘就可以对原本打分矩阵中空缺的值进行预测。其中, $R$ 表示待分解的打分矩阵,$U$ 表示用户矩阵,$V$表示物品矩阵。

目标函数

$$J(a,i) = \mathop{argmin} \limits_{u_a, v_i} \;\frac 1 2 \left( \sum_{r_{ai} \in ratings} (r_{ai} - \bar u_a · \bar v_i)^2 + \gamma(\sum_a||u_a||^2 + \sum_i||v_i||^2) \right)$$

每一个 $user\,a$ 都对应一个向量 $u_a$,每一个 $item\,i$ 也对应一个向量 $v_i$,这两个向量的点积就是 $user$ 在 $item$ 上的打分 $r_ui$。在分解过程中相当于把 $u_a$ 的打分映射到一个 $k$ 维的隐向量上,再用这个 $k$ 的隐向量表示 $v_i$。

求解方法

求解使用梯度下降方法,参数更新公式如下所示

在适用性方面,$FunkSVD$ 只适用于有打分的数据,不适用与一元数据。

分解更新

如果有新的 $user$ 加入的话,无需全部重新学习,而只需要学习新加入的 $user$ 的向量表示,其对应的损失函数如下:

$$ \sum_{i} = (r_{m+1, i} - u_{m+1}·v_i^2) + \gamma||r_{m+1}||^2 $$

协同过滤的冷启动问题

用户冷启动

最简单的方法就是给用户推荐热门排行。再进一步,如果知道用户的分类(如:男或者女用户),或者能够通过一些信息(如:用户的注册信息)来获得用户的分类,在这个分类中,根据已有的用户统计这个分类下的排行,再把这个排行结果推荐给新用户。如果用户的注册信息不多,且用户填写的比较全面,则这些信息可以形成一个决策树的组织形式,新用户总会落到树的一个叶子节点(分类)中,推荐该节点下的热门排行。

系统冷启动

让用户回答一个问题列表,这个列表随着用户的回答而改变问题,每次给用户提出最具区分力的物品,问用户是否感兴趣。对于一群用户和一些物品,如果用户对这些物品的打分的方差很大,说明这些用户的兴趣不一致;其次,对于某一个物品,用户的反应是,喜欢、不喜欢、无所谓(没有打分),这三种反应可以将用户分为三个群体;那么就可以使用此物品作为决策问题对用户进行分类。

物品冷启动

$UserCF$ 对物品冷启动问题并不敏感,因为总有用户会访问到新物品,此时给那些相似的用户推荐这个物品,就会有越来越多的人来访问这个物品,形成良性循环。在 $ItemCF$ 中,物品冷启动就是比较严重的问题了,因为使用新物品的用户比较少,不容易计算新物品同其他物品的相似度,解决方法是通过物品的内容来计算物品之间的相似度,并作为 $ItemCF$ 的补充。

附:信息表达方式

参考文献:
[1] 罗平,《网络数据挖掘》,中国科学院大学2017年秋季研究生课程