推荐系统---（二）利用用户数据

1、用户行为数据

用户行为可以分为：（1）显示反馈行为（包括用户明确表示对物品喜好的行为）；（2）隐式反馈行为（不明确反应用户喜好的行为，如页面浏览行为。）。

比较类别	显示反馈数据	隐式反馈数据
用户兴趣	明确	不明确
数量	较少	庞大
存储	数据库	分布式文件系统
实时读取	实时	有延迟
正负反馈	都有	只有正反馈

常见的数据集：

（1）无上下文信息的隐式反馈数据集：每一条行为记录仅仅包含用户ID和物品ID。

http://www.informatik.uni-freiburg.de/~cziegler/BX/

（2）无上下文信息的显式反馈数据集：每一条行为记录包含用户ID、物品ID和对物品的评分。

（3）有上下文信息的隐式反馈数据集：每一条行为记录包含用户ID、物品ID和用户对物品产生行为的时间戳。

http://www.dtic.upf.edu/~ocelma/MusicRecommendationDataset/lastfm-1K.html

（4）有上下文信息的显示反馈数据集：每一条行为记录包含用户ID、物品ID、用户对物品的评分和评分发生行为的时间戳。http://netflixprize.com/

2、用户行为分析

（1）用户活跃度和物品流行度的分析

令$f_n(k)$fn​(k)为对k个物品产生过行为的用户数，令$f_i(k)$fi​(k)为被k个用户产生过行为的物品数，那么它们都符合长尾分布：$f_u(k)=\alpha_u k^{\beta_u}$fu​(k)=αu​kβu​和$f_i(k)=\alpha_i k^{\beta_i}$fi​(k)=αi​kβi​。
即大部分用户都是新用户，而老用户占据很少的比例；热门的物品占据的比例很少。
一般认为，新用户倾向于浏览热门的物品，而老用户会逐渐开始浏览冷门的物品。

（2）协同过滤算法

仅仅基于用户行为数据设计的推荐算法即协同过滤算法。
常用的方法有：

• ①基于邻域的方法（neighborhood-based）
  • （i）基于用户的协同过滤算法：给用户推荐和他兴趣相似的其他用户喜欢的物品。
  • （ii）基于物品的协同过滤算法：给用户推荐和他之前喜欢的物品相似的物品。
• ②隐语义模型（latent factor model）
• ③基于图的随机游走算法（random walk on graph）等。

3、基于邻域的算法

（1）基于用户的协同过滤算法UserCF

步骤：
①找到和目标用户兴趣相似的用户集合；
②找到这个集合中的用户喜欢的、且目标用户没有听说过的物品推荐给目标用户。

Step1：计算用户的兴趣相似度

步骤①的关键是计算两个用户的兴趣相似度。令N(u)表示用户u曾经有过正反馈的物品集合，令N(v)为用户v曾经有过正反馈的物品集合，那么可以利用Jaccard公式简单地计算u和v的兴趣相似度：
$w_{uv} = \frac{|N(u)∩N(v)|}{|N(u)∪N(v)|}$wuv​=∣N(u)∪N(v)∣∣N(u)∩N(v)∣​
或
$w_{uv} = \frac{|N(u)∩N(v)|}{\sqrt{|N(u)||N(v)|}}$wuv​=∣N(u)∣∣N(v)∣​∣N(u)∩N(v)∣​
或改进为John S. Breese提出的公式：
$w_{uv} = \frac{\sum_{i∈N(u)∩N(v)}{\frac{1}{log(1+|N(i)|)}}}{\sqrt{|N(u)||N(v)|}}$wuv​=∣N(u)∣∣N(v)∣​∑i∈N(u)∩N(v)​log(1+∣N(i)∣)1​​

Step2：为物品打分

得到用户之间的兴趣相似度后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户u对物品i的感兴趣程度：
$p(u,i)=\sum_{v∈S(u,K)∩N(i)}{w_{uv}r_{vi}}$p(u,i)=v∈S(u,K)∩N(i)∑​wuv​rvi​
其中，S(u,K)包含和用户u兴趣最接近的K个用户，N(i)是对物品i有过行为的用户集合，$w_{uv}$wuv​是用户u和用户v的兴趣相似度，$r_{vi}$rvi​代表用户v对物品i的兴趣，因为使用的是单一行为的隐式反馈数据，所以所有的$r_{vi}=1$rvi​=1。
参数K（可以随机选出或者按照某个算法获得）对UserCF的各种指标都会有影响：①准确率和召回率（非线性关系，结果不是特别敏感）。②流行度（K越大推荐结果越热门）。③覆盖率（K越大覆盖率越低。）

（2）基于物品的协同过滤算法ItemCF

基于用户的协同过滤算法的劣势：用户兴趣相似度矩阵会随着用户数目的增大而计算困哪，且很难对推荐结果作出解释。
步骤：
①计算物品之间的相似度。
②根据物品的相似度和用户的历史行为给用户生产推荐列表。

Step1：计算物品间相似度

步骤①中物品间的相似度可以定义为：
$w_{i,j} = \frac{|N(i)∩N(j)|}{|N(i)|}$wi,j​=∣N(i)∣∣N(i)∩N(j)∣​
其中，分母|N(i)|是喜欢物品i的用户数，而分子|N(i)∩N(j)|是同时喜欢物品i和物品j的用户数。
但是如果i很热门，$w_{i,j}$wi,j​会趋向1没有意义，所以我们可以用以下公式：
$w_{i,j} = \frac{|N(i)∩N(j)|}{\sqrt{|N(i)||N(j)|}}$wi,j​=∣N(i)∣∣N(j)∣​∣N(i)∩N(j)∣​
或改进为John S. Breese提出的公式，该公式增加修正参数IUF使得活跃用户对物品相似度的贡献应该小于不活跃的用户：
$w_{ij} = \frac{\sum_{i∈N(i)∩N(j)}{\frac{1}{log(1+|N(u)|)}}}{\sqrt{|N(i)||N(j)|}}$wij​=∣N(i)∣∣N(j)∣​∑i∈N(i)∩N(j)​log(1+∣N(u)∣)1​​
Karypis在研究中发现如果将ItemCF的相似度矩阵按最大值归一化，可以提高推荐的准确率及推荐的覆盖率和多样，即：
$w'_{ij}=\frac{w_{ij}}{max_j w_{ij}}$wij′​=maxj​wij​wij​​

Step2：为物品打分

步骤②中用户u对一个物品j的兴趣可以定义为：
$p_{uj}=\sum_{i∈N(u)∩S(j,K)}{w_{ji} r_{ui}}$puj​=i∈N(u)∩S(j,K)∑​wji​rui​
这里N(u)是用户喜欢的物品的集合，S(j,K)是和物品j最相似的K个物品的集合，$w_{ji}$wji​是物品j和i的相似度，$r_{ui}$rui​是用户u对物品i的兴趣（对于隐式反馈数据集，如果用户u对物品i有过行为，即可令$r_{ui}=1$rui​=1）。和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名。
参数K（可以随机选出或者按照某个算法获得）对ItemCF的各种指标都会有影响：①准确率和召回率（非线性关系）。②流行度（K越大推荐结果越热门，但是会趋于平稳）。③覆盖率（K越大覆盖率越低。）

（3）UserCF对比ItemCF

比较内容	UserCF	ItemCF
性能	适用于用户较少的场合，如果用户较多，计算用户相似度矩阵代价很大	适用于物品数明显小于用户数的场合，如果物品很多，计算物品相似度矩阵代价很大
领域	时效性较强，用户个性化兴趣不太明显的领域	长尾物品丰富，用户个性化需求强烈的邻域
实时性	用户有新行为，不一定造成推荐结果的立即变化	用户有新行为，一定会导致推荐结果的实时变化
冷启动	在心哟用户对很少的物品产生行为后，不能立即对他进行个性化推荐，因为用户相似度是每隔一段时间离线计算的。新物品上线后一段时间，一旦有用户对物品产生行为，就可以将新物品推荐给和对它产生行为的用户兴趣相似的其他用户。	新用户只要对一个物品产生行为，就可以给他推荐和该物品相关的其他物品。但没有办法在不离线更新物品相似度表的情况下将新物品推荐给用户。
推荐理由	很难提供令用户信服的推荐解释	利用用户的历史行为给用户做推荐解释，可以令用户比较信服

4、隐语义模型

（1）基础算法

核心思想：通过隐含特征（latent factor）联系用户兴趣和物品。
隐语义模型（LFM）通过如下公式计算用户u对物品i的兴趣：
$Prefence(u,i)=r_{ui}=p^{T}_{u} q_i = \sum_{f=1}^{F}p_{u,k} q_{i,k}$Prefence(u,i)=rui​=puT​qi​=f=1∑F​pu,k​qi,k​
其中$p_{u,k}$pu,k​和$q_{i,k}$qi,k​是模型的参数，$p_{u,k}$pu,k​度量了用户u的兴趣和第k个隐类的关系，$q_{i,k}$qi,k​度量了第k个隐类和物品i之间的关系。通过一个训练集，包含了每个用户u喜欢的物品和不感兴趣的物品，学习这个训练集可以获得这两个参数。
在显示反馈数据集上LFM可以获得很好的精度。但是隐式反馈数据集中只有正样本（用户喜欢什么物品），而没有负样本（用户对什么物品不感兴趣），所以如何生成负样本是关键：①对每个用户，要保证正负样本的平衡；②对每个用户采样负样本时，要选取那些很热门，而用户却没有行为的物品。
经过采样，可以得到一个用户-物品集K={(u,i)}，其中如果(u,i)是正样本，那么$r_{ui}=1$rui​=1，否则$r_{ui}=0$rui​=0。然后，需要优化如下的损失函数来找到最合适的参数p和q：
$C=\sum_{(u,i)∈K}(r_{ui} - \hat{r_{ui}})^2=\sum_{(u,i)∈K}(r_{ui} - \sum_{k=1}^{K} p_{u,k} q_{i,k})^2 + \lambda||p_u||^2 + \lambda ||q_i||^2$C=(u,i)∈K∑​(rui​−rui​^​)2=(u,i)∈K∑​(rui​−k=1∑K​pu,k​qi,k​)2+λ∣∣pu​∣∣2+λ∣∣qi​∣∣2
其中，$\lambda||p_u||^2 + \lambda ||q_i||^2$λ∣∣pu​∣∣2+λ∣∣qi​∣∣2是用来防止过拟合的正则化项，$\lambda$λ可以通过试验获得，我们使用随机梯度下降法即可最小化上面的损失函数。
在LFM中，有4个重要参数：①隐特征的个数F；②学习速率$\alpha$α（随机梯度下降法中的参数）；③正则化参数$\lambda$λ；④负样本/正样本比例ratio。

（2）LFM和基于邻域的方法比较

比较类别	LFM	基于邻域
理论基础	有较好的理论基础，是一种学习方法，通过优化一个设定的指标建立最优的模型	基于统计的方法，没有学习的过程
离线计算的空间复杂度	O(F*(M+N))，F个隐类，M个用户，N个物品	UserCF：O(MM)，ItemCF：O(MN)
离线计算的时间复杂度	O(KFS)，K条行为记录，迭代S次	O(M*(K/M)^2)
在线实时推荐	当有了新用户后，推荐列表不会发生变化	一旦用户有了新的行为，推荐列表就会发生变化
推荐解释	难以用自然语言描述隐类	ItemCF有很好的解释性

5、基于图的模型

（1）用户行为数据的二分图表示

用户若对物品产生行为则有边连接。

（2）基于图的推荐算法

图中顶点的相关性取决于：
①两个顶点之间的路径数；
②两个顶点之间路径的长度；
③两个顶点之间的路径经过的顶点。
而相关性高的一对顶点一般具有如下特征：
①两个顶点之间有很多路径相连；
②连接两个顶点之间的路径长度都比较短；
③连接两个顶点之间的路径不会经过出度比较大的顶点。
基于如上因素可以设计计算图中顶点之间相关性的方法。

（3）基于随机游走的PersonalRank算法

假设要给用户u进行个性化推荐，可以从用户u对应的节点$v_u$vu​开始在用户物品二分图上进行随机游走。游走到任何一个节点时，首先按照概率α决定是否继续游走，还是停止这次游走并从$v_u$vu​节点开始重新游走。如果决定继续游走，那么就从当前结点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品节点被访问到的概率会收敛到一个数。最终的推荐列表中的物品的权重就是物品节点的访问概率。
即满足如下公式：
$PR(v) = \begin{cases} \alpha \sum_{v'∈in(v)} \frac{PR(v')}{|out(v')|} \qquad & (v\ne v_u) \\ (1-\alpha) + \alpha \sum_{v'∈in(v)} \frac{PR(v')}{|out(v')|} \qquad & (v= v_u) \end{cases}$PR(v)={α∑v′∈in(v)​∣out(v′)∣PR(v′)​(1−α)+α∑v′∈in(v)​∣out(v′)∣PR(v′)​​(v​=vu​)(v=vu​)​
此方法在时间复杂度上有明显的缺点，不能在线提供实时推荐。
解决方案：①减少迭代次数，但是会影响最终精度；
②从矩阵论出发，重新设计算法。
令M为用户物品二分图的转移概率矩阵：$M(v,v')=\frac{1}{|out(v)|}$M(v,v′)=∣out(v)∣1​

那么迭代公式可以转化为：$r=(1-\alpha)r_0 + \alpha M^{T}r=(1-\alpha)(1-\alpha M^{T})^{-1}r_0$r=(1−α)r0​+αMTr=(1−α)(1−αMT)−1r0​