推荐系统实践 - 02利用用户行为数据
–未经授权，禁止转载–
第二章 利用用户行为数据
-
1 用户行为数据分析
-
2 基于邻域的算法
-
- 2.1 基于用户的协同过滤算法（UserCF）
- 2.2 基于物品的协同过滤算法（ItemCF）
- 2.3 UserCF和ItemCF对比
-
3 隐语义模型
-
4 基于图的模型
1 用户行为数据分析
用户行为数据最简单的存在形式就是日志。
用户行为在个性化推荐系统中一般分为显性反馈行为（explicit feedback）和隐性反馈行为（implicit feedback）
- 显性反馈行为 ：明确反映用户对物品喜好的行为，如评分
- 隐性反馈行为 ：不能明确反映用户喜好的行为，如页面浏览、购买等行为
- 显性、隐性反馈行为区别 ：显性反馈行为能明确反馈用户兴趣，但数据较少，存储在数据库中，能够实时读取，有正反馈和负反馈；隐性反馈行为不能明确反馈用户兴趣，但数据量庞大，存储在分布式文件系统中，有一定的延迟，只有正反馈。
用户行为的统一表示 ：用户、行为对象、行为分类（如购买or浏览）、产生行为的上下文（时间、地点等）、行为的权重（如观看时长、评分的分数等）、行为内容（评论文本、打的标签等）
用户行为数据中的一般规律 ：互联网上很多数据分布都满足长尾分布（Power Law分布）。如对x个物品产生过用户行为的用户数和被x个用户产生过行为的物品数都满足长尾分布。
f(x)=ax^{k}
用户活跃度和物品流行度关系 ：用户越活跃，越倾向于浏览冷门物品
仅仅基于用户行为数据设计的算法称谓协同过滤算法。协同算法包括基于邻域的方法（neighborhood-based）、隐语义模型（latent factor model）、基于图的随机游走算法（random walk on graph）等。
协同过滤算法（基于用户行为数据）存在的问题：两个不同领域的最热门物品之间往往具有较高的相似度。比如说，父辈喜欢看新闻联播，之后看晚八点档电视剧。那么黄金时期的电视剧和新闻联播相似度就会很高。
2 基于邻域的算法
基于邻域的算法主要包括基于用户的协同过滤算法（User Collaborative Filter, UserCF）和基于物品的协同过滤算法（item-based collaborative filtering, ItemCF）。
2.1 基于用户的协同过滤算法（UserCF）
基于用户的协同过滤算法：给用户推荐和他兴趣相似的用户喜欢的商品。
算法步骤：
1）找到和用户兴趣相似的用户集合 。即计算两个用户的兴趣相似度。给定用户u和用户v，N(u)表示用户u曾经有过正反馈的物品集合，N(v)表示用户v曾经有过正反馈的物品集合。可以通过Jaccard公式、余弦相似度等方法计算兴趣相似度。
Jaccard公式：
W_{uv}=\frac{N(u)\cap{N(v)}}{N(u)\cup{N(v)}}
余弦相似度：
W_{uv}=\frac{N(u)\cap{N(v)}}{\sqrt{N(u){N(v)}}}
如果按照穷举的思维计算所有用户两两间的相似度非常耗时，因为很多用户没有对同一个物品有过行为，即N(u)\cap{N(v)}=0。为改进方法，可以先计算出N(u)\cap{N(v)}\neq{0}的用户，再进行计算。具体过程如下：
2）得到用户兴趣相似度之后，就可以给用户推荐和他兴趣最相似的K个用户喜欢的物品 。
利用以下公式计算UserCF算法中用户u对物品i的感兴趣程度：
- u，v：用户
- i：物品
- S(u, K)：和用户u兴趣最接近的K个用户
- N(i)：对物品i有过行为的用户集合
- w_{uv}：用户u和v的兴趣相似度
- r_{vi}：用户v对商品i的兴趣，单一行为的隐反馈r_{vi}=1
p(u,i)=\sum{_{v\in{S(u,K)\cap{N(i)}}}w_{uv}r_{vi}}
如对用户A的推荐过程如下：
参数K的选择：
- 准确率和召回率：不和K呈线性关系。当K\approx{80}时，算法精度较好
- 流行度：K越大，流行度越大
- 覆盖率：K越大，覆盖率越小
余弦相似度的改进公式：
热门物品相似可能不代表用户兴趣，如大多数人都购买过《新华字典》。对冷门物品有过相同行为更能说明兴趣相似度。新公式惩罚了用户u和v共同列表中热门物品的相似度影响。N(i)为喜欢物品i的用户数。
UserCF： W_{uv}=\frac{N(u)\cap{N(v)}}{\sqrt{N(u){N(v)}}}
UserCF-IIF（IIF（Inverse Item Frequence）即物品流行度对数的倒数）: W_{uv}=\frac{\sum{_{i\in{N(u)\cap{N(v)}}}\frac{1}{\log{(1+N(i))}}}}{\sqrt{N(u)N(v)}}
2.2 基于物品的协同过滤算法（ItemCF）
基于物品的协同过滤算法：推荐和用户之前喜欢的物品相似的物品，如购买该商品的用户也经常购买的商品。
算法步骤：
1）计算物品之间相似度
ItemCF并不利用物品的内容属性计算物品相似度，通过分析用户的行为记录计算物品之间的相似度，N(i)为对物品i有过行为的用户。
W_{ij}=\frac{N(i)\cap{N(j)}}{N(i)}
相似度公式的改进公式：
如果物品j很热门，那么相似度就会约等于1。为了避免推荐热门商品，可以改进为
W_{ij}=\frac{N(i)\cap{N(j)}}{\sqrt{N(i)N(j)}}
过程如下：
2）根据物品相似度和用户历史行为给用户生成推荐列表
用户u对物品j的兴趣如下：
- N(u)：用户u喜欢的物品集合
- S(j,K)：和物品j最相似的K个物品
- w_{ji}：物品j和i的相似度
- r_{ui}：用户u对物品i的兴趣
p_{uj}=\sum{_{i\in{N(u)\cap{S(j,k)}}}w_{ji}r_{ui}}
如对用户C的推荐过程如下：
参数K的选择：
- 准确率和召回率：不和K呈线性关系。当K\approx{10}时，算法精度较好
- 流行度、覆盖率：不和K呈线性关系。
物品相似度的改进公式：
用户行为相关可能不代表物品相似，如书店老板一次性购买了80%的书，但不意味着这80本书之间两两有关联。活跃度低的用户的行为更能说明物品相似度。新用户惩罚了用户活跃度。（在实际应用中，也可直接忽略特殊用户的兴趣列表）
ItemCF： W_{ij}=\frac{N(i)\cap{N(j)}}{N(i)}
ItemCF-IUF（IUF（Inverse User Frequence）即用户活跃度对数的倒数）: W_{ij}=\frac{\sum{_{u\in{N(i)\cap{N(j)}}}}\frac{1}{\log{(1+N(u))}}}{N(i)}
将物品相似度矩阵最大值归一化：
可以提高推荐准确率， 同时可以提高推荐算法覆盖率。
（存疑：好像并没有改变结果）
2.3 UserCF和ItemCF对比
| UserCF | ItemCF | |
|---|---|---|
| 原理 | 给用户推荐和他兴趣相似的用户喜欢的商品 | 推荐和用户喜欢的物品相似的物品，如购买该商品的用户也经常购买的商品 |
| 性能 | 适合用户较少的场景。如果用户数过大，计算用户相似度矩阵代价很大 | 适合物品数明显小于用户数的场景，如果物品数过大（如网页），计算物品相似度矩阵代价很大 |
| 领域 | 时效性较强，适合用户个性化兴趣不明显的领域 | 长尾物品丰富，用户个性化需求强烈的领域 |
| 实时性 | 用户有新行为，推荐结果不一定立即变化 | 用户有新行为，推荐结果实时变化 |
| 冷启动 | 新用户对很少的物品产生行为后，不能立即对他进行个性化推荐，因为用户相似度是每隔一段时间离线计算的 | 新用户对一个物品产生行为，就可以给他推荐和该物品相关的其他用户 |
| 新物品上线后，一旦有用户对物品产生行为，就可以将新物品推荐给和对它产生行为的用户兴趣相似的其他用户 | 不能在不离线更新物品相似度表的情况下将新物品推荐给用户 | |
| 推荐理由 | 很难对推荐结果做出解释 | 可以利用用户历史行为对推荐结果做出解释 |
3 隐语义模型
基础算法
隐语义模型（latent factor model，LFM）的核心思想是通过隐含特征联系用户兴趣和物品。
具体过程如下：给物品分类；确定用户对物品的感兴趣程度；选择属于用户感兴趣的物品推荐给用户。
传统的解决方案有诸多问题，但隐语义分析技术能够很好地解决（以图书推荐为例）：
- 编辑的意见不能代表各种用户的意见。隐语义分析统计用户的行为，能够代表用户对物品分类的看法。
- 人工难以控制分类的粒度。隐语义分析可以设置分类个数，从而控制分类粒度。
- 人工难以给一个物品多个分类。隐语义分析能够计算出物品属于每个类的权重。
- 人工难以出多维度的分类。隐语义分析基于用户多维兴趣分类。
- 人工难以决定一个物品在某分类中的权重。隐语义分析可以计算物品在某分类中的权重。
LFM公式如下，表述为【用户对第k类物品的兴趣度*物品i在第k类物品分类中的权重】通过训练集梯度下降获得最优的p_{u,k}（用户对第k类物品的兴趣度）和q_{i,k}（物品i在第k类物品分类中的权重）：
Preference=r_{ui}=P_{u}^{T}q_{i}=\sum{_{k=1}^{K}p_{u,k}q_{i,k}}
在使用中，隐反馈数据集无法提供负反馈数据，所以要生成负样本。可以使用以下方法（性能由低到高）：
- 将用户没有过行为的物品作为负样本
- 从用户没有过行为的物品中采样一些物品作为负样本，采样时偏重采样不热门的物品
- 从用户没有过行为的物品中采样一些物品作为负样本
- 从用户没有过行为的物品中采样一些物品作为负样本，采样时保证每个用户的正负样本数量相当
对负样本采样原则：
- 每个用户的正负样本数目相近
- 选取热门但用户没有行为的物品作为负样本
LFM和基于邻域的方法的比较：
| LFM | 基于邻域的方法 | |
|---|---|---|
| 理论基础 | 是一种学习、优化方法 | 是一种基于统计的方法 |
| 空间复杂度 | 占据内存较小，需要4G左右内存 | 占据很大的内存，UserCF需要30G左右内存 |
| 时间复杂度 | 一般情况下LFM需要经过多次迭代，时间复杂度稍高于基于邻域的方法，但时间复杂度没有质的区别 | 时间复杂度稍低于LFM，但时间复杂度没有质的区别 |
| 实时性 | 物品多时无法实时预测，但是可以先用较为快速的算法生成物品候选列表，从而加快物品推荐过程。另外，LFM基于数据库的数据，不能主动实时推荐 | 可以实时预测 |
| 推荐解释 | LFM无法提供推荐解释 | ItemCF可以利用用户的历史行为提供解释 |
4 基于图的模型
令G(V, E)为用户物品二分图。其中，V=V_U\cup{}V_I由用户顶点集合V_U和物品顶点集合V_I组成。e(v_u, v_i)为边，v_u\in{}V_U是用户对应的顶点，v_i\in{}V_I是物品i对应的顶点。用户行为数据的二分图表示如下图所示：
基于图的推荐算法：给用户u推荐物品任务，即度量用户顶点v_u与v_u没有边直接相连的物品节点在图上的相关性。
度量两个顶点的相关性有三个方面：
- 两个顶点之间的路径条数，相对性高的两个顶点有多种路径
- 两个顶点之间的路径长度，相对性高的两个顶点路径长度较短
- 两个顶点之间的路径经过的顶点，相对性高的两个顶点路径不会经过出度比较大的顶点
如顶点A和c，顶点A和e的相关度：
A和c、e都没有直接相连的边，但是，A和c有一条长度为3的路径，A和e有两条长度为3的路径，所以顶点A和e的相关度高于顶点A和c：
对于顶点A和e，路径（A, d, D ,e）的出度（3, 2, 3, 2）比（A, b,C,e）的出度（3 ,2 ,2, 2）大，所以路径（A, b,C,e）对相关性的贡献低：
PersonalRank算法：
假设对u做个性化推荐，则从u对应的节点v_u开始在二分图上随机游走，游走到任意节点，按照概率\alpha决定继续游走还是停止游走重新开始。这样经过多次游走之后，每个物品节点被访问的概率就会收敛到一个数，最终推荐列表物品的权重就是物品节点的访问概率。总结公式如下：
PR(v) = \left \{ \begin{aligned} & \alpha\sum_{v'\in{in(v)}}\frac{PR(v')}{|out(v')|}\quad{}v\neq{v_{u}} \\ &(1-\alpha)+ \alpha\sum_{v'\in{in(v)}}\frac{PR(v')}{|out(v')|}\quad{}v=v_{u} \end{aligned} \right.
如对A进行推荐过程如下，令\alpha=0.6：
因为PR(d)>PR(b)，所以推荐列表为｛d, b｝