to be continued

第1章好的推荐系统

什么是推荐系统

推荐系统的基本任务是联系用户和物品，解决信息过载的问题。
　　社会化推荐(social recommendation)：向朋友咨询
　　基于内容的推荐(content-based filtering)：寻找和自己之前喜欢的物品相似的物品
　　基于协同过滤(collaborative filtering)：找到和自己历史兴趣相似的用户所喜欢的物品

第2章利用用户行为数据

基于用户行为分析的推荐算法是个性化推荐系统的重要算法，学术界一般将这种类型的算法称为协同过滤算法。
　　按反馈的明确性分，显式反馈（explicit feedback）和隐式反馈（implicit feedback）
　　按反馈的方向分，正反馈（用户的行为倾向于指用户喜欢该物品）和负反馈（用户的行为倾向于指用户不喜欢该物品）
　　有代表性的数据集：
　　无上下文信息的隐性反馈数据集：每一条行为记录仅仅包含用户ID和物品ID。
　　无上下文信息的显性反馈数据集：每一条记录包含用户ID、物品ID和用户对物品的评分。
　　有上下文信息的隐性反馈数据集：每一条记录包含用户ID、物品ID和用户对物品产生行为的时间戳。
　　有上下文信息的显性反馈数据集：每一条记录包含用户ID、物品ID、用户对物品的评分和评分行为发生的时间戳。

用户活跃度和物品流行度的分布

PowerLaw分布（长尾分布）

f(x)=αx^k

令 $f_u(k)$ 为对k个物品产生过行为的用户数，令 $f_i(k)$ 为被k个用户产生过行为的物品数。它们都满足长尾分布。

f_i(k)=a_ik^{β_i}

f_u(k)=a_uk^{β_u}

物品的流行度指对物品产生过行为的用户总数。
　　用户的活跃度为用户产生过行为的物品总数。

用户活跃度和物品流行度的关系

仅仅基于用户行为数据设计的推荐算法一般称为协同过滤算法。
　　基于邻域的方法（neighborhood-based）：基于用户的协同过滤算法（推荐和用户兴趣相似的其他用户喜欢的物品）、基于物品的协同过滤算法（推荐和他之前喜欢的物品相似的物品）
　　隐语义模型（latent factor model）
　　基于图的随机游走算法（random walk on graph）

基于邻域的算法

基于用户的协同过滤算法

基础算法

步骤：

找到和目标用户兴趣相似的用户集合。
找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户。
　　步骤1关键是计算两个用户的兴趣相似度。
　　利用行为的相似度计算兴趣相似度。Jaccard公式计算用户u和用户v的兴趣相似度。

w_{uv}=\frac{|{N(u)∩N(v)}|}{|{N(u)∪N(v)}|}

或者通过余弦相似度

w_{uv}=\frac{|{N(u)∩N(v)}}{|\sqrt{|{N(u)||N(v)}|}}

N(u)表示用户u曾经有过正反馈的物品集合，N(v)为用户曾经有过正反馈的物品集合。
　　时间复杂度：O(|U|*|U|)
　　用户数很大时耗时，并且很多时候|N(u)∩N(v)|=0。

改进算法

用户相似度计算的改进：User-IIF算法
　　两个用户对冷门物品采取同样的行为更能说明他们兴趣的相似度。

w_uv = \frac{\sum i\epsilon N(u)∩N(v)\frac{1}{log1+|N(i)|}}{\sqrt{|N(u)||N(v)|}}

该公式通过 $\frac{1}{log1+|N(i)|}$ 惩罚了用户u和用户v共同兴趣列表中热门物品对他们相似度的影响。

基于物品的协同过滤算法

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

计算物品之间的相似度
根据物品的相似度和用户的历史行为给用户生成推荐列表

w_{ij}=\frac{|N(i)∩N(j)|}{|N(i)|}

|N(i)|是喜欢物品i的用户数，分子|N(i)∩N(j)|是同时喜欢物品i和物品j的用户数。
　　公式可理解为喜欢物品i的用户中有多少比例的用户也喜欢物品j。

公式问题：若物品j很热门，很多人都喜欢，则 $w_{ij}$ 很大，接近1。造成任何物品都会和热门物品有很大的相似度，这对致力于挖掘长尾信息的推荐系统来说不好。为避免出热门的物品，改进：

w_{ij}=\frac{|N(i)∩N(j)|}{\sqrt{|N(i)||N(j)|}}

该公式惩罚了物品j的权重，因此减轻了热门物品和很多物品相似的可能性。

从定义可看出，在协同过滤中两个物品产生相似度是因为它们共同被很多用户喜欢，即每个用户都可以通过他们的历史兴趣列表给物品贡献相似度。

用户活跃度对物品相似度的影响

每个用户对相似度的贡献应该不同。
　　ItemCF-IUF(Inverse User Frequence)，即用户活跃度对数的倒数的参数。活跃用户对物品相似度的贡献小于不活跃的用户。

w_uv = \frac{\sum u\epsilon N(i)∩N(j)\frac{1}{log1+|N(u)|}}{\sqrt{|N(i)||N(j)|}}

物品相似度的归一化

w_{ij} = \frac{w_{ij}}{max w_{ij}}

UserCF和ItemCF对比

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

UserCF使用场景：新闻推荐
　　ItemCF使用场景：图书、电子商务、电影网站

在实际的互联网中，用户数目往往非常庞大，而在图书、电子商务网站中，物品的数目则是比较少的。此外，物品的相似度相对于用户的兴趣一般比较稳定，因此使用ItemCF是比较好的选择。当然，新闻网站是个例外，在那儿，物品的相似度变化很快，物品数目庞大，相反用户兴趣则相对固定（都是喜欢看热门的），所以新闻网站的个性化推荐使用UserCF算法的更多。

隐语义模型

基础算法

思想：通过隐含特征（latent factor）联系用户兴趣和物品。
　　基于兴趣分类的方法大概需解决三个问题：

如何给物品进行分类？
如何确定用户对哪些类的物品感兴趣，以及感兴趣的程度？
对于一个给定的类，选择哪些属于这个类的物品推荐给用户，以及如何确定这些物品在一个类中的权重？

隐含语义分析技术采取基于用户行为统计的自动聚类。
　　隐含语义分析技术从诞生到今天产生了很多著名模型和方法：pLSA、LDA、隐含类别模型（latent class model）、隐含主题模型（latent topic model）、矩阵分解（matrix factorization）。

LFM

用户u对物品i的兴趣：

Preference(u,i) = r_{ui} = p_u^Tq_i = \sum_{f=1}^Fp_{u,k}q_{i,k}

$p_{u,k}$ 和 $q_{i,k}$ 是模型参数， $p_{u,k}$ 度量了用户u的兴趣和第k个隐类的关系，而 $q_{i,k}$ 度量了第k个隐类和物品i之间的关系。
　　这两个参数是从数据集中计算出来的。要计算这两个参数，需要一个训练集，对于每个用户u，训练集里都包含了用户u喜欢的物品和不感兴趣的物品，通过学习这个数据集，就可以获得上面的模型参数。

推荐系统的用户行为分为显性反馈和隐性反馈。 LFM在显性反馈数据(也就是评分数据)上解决评分预测问题并达到了很好的精度。
隐性反馈数据集：只有正样本（用户喜欢什么物品），没有负样本（用户对什么物品不感兴趣）。
在隐性反馈数据集上应用LFM解决TopN推荐的第一个关键问题就是如何给每个用户生成负样本。

生成负样本方法：

对于一个用户，用他所有没有过行为的物品作为负样本。//负样本太多，正负样本数目相差悬殊，计算复杂度很高，结果精度差。
对于一个用户，从他没有过行为的物品中均匀采样出一些物品作为负样本。
对于一个用户，从他没有过行为的物品中采样出一些物品作为负样本，但采样时，保证每个用户的正负样本数目相当。
对于一个用户，从他没有过行为的物品中采样出一些物品作为负样本，但采样时，偏重采样不热门的物品。
第三种好于第二种，第二种好于第四种。

对负样本采样时应遵循以下原则：

对每个用户，要保证正负样本的平衡（数目相似）。
对每个用户采样负样本时，要选取那些很热门，而用户却没有行为的物品。
一般认为，很热门而用户却没有行为更加代表用户对这个物品不感兴趣。因为对于冷门的物品，用户可能是没发现这个物品，所以谈不上是否感兴趣。
LFM模型在实际使用中有一个困难：它很难实现实时的推荐。

LFM和基于领域的方法比较

理论基础
LFM具有比较好的理论基础，它是一种学习方法，通过优化一个设定的指标建立最优的模型。基于邻域的方法更多的是一种基于统计的方法，并没有学习过程。
离线计算的空间复杂度
用户相关表，则需要O(M*M)的空间，而对于物品相关表，则需要O(N*N)的空间。
LFM在建模过程中，如果是F个隐类，那么它需要的存储空间是O(F*(M+N))，这在M和N很大时可以很好地节省离线计算的内存。
离线计算的时间复杂度
假设有M个用户、 N个物品、 K条用户对物品的行为记录。UserCF计算用户相关表的时间复杂度是O(N * (K/N)^{2)，而ItemCF计算物品相关表的时间复杂度是O(M*(K/M)}2)。而对于LFM，如果用F个隐类，迭代S次，那么它的计算复杂度是O(K * F * S)。总体上没有质的差别。
在线实时推荐
UserCF、ItemCF可，LFM不可。
推荐解释
ItemCF解释很好，LFM无法解释。

基于图的模型（graph-based model）

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

很多研究者把基于邻域的模型也称为基于图的模型，因为基于邻域的模型可看做基于图的模型的简单形式。
二元组（u, i）表示用户u对物品i产生过行为。令G（V, E）表示用户物品二分图，其中 $V = V_U∪V_1$ 由用户顶点集合 $V_U$ 和物品顶点集合 $V_1$ 组成。对于数据集中每一个二元组（u, i），图中都有一套对应的边e（ $v_u$ , $v_i$ ），其中 $v_u\epsilon V_U$ 是用户u对应的顶点， $v_i\epsilon V_1$ 是物品i对应的顶点。

图中是一个简单的用户物品二分图模型，其中圆形节点代表用户，方形节点代表物品，圆形节点和方形节点之间的边代表用户对物品的行为。比如图中用户节点A和物品节点a、 b、 d相连，说明用户A对物品a、 b、 d产生过行为。

基于图的推荐算法（graph-based model）

可把基于领域的模型看做基于图的模型的简单形式。
相关性高的一对顶点一般具有如下特征：

两个顶点之间有很多路径相连
连接两个顶点之间的路径长度都比较短
连接两个顶点之间的路径不会经过出度比较大的顶点

基于随机游走的PersonalRank算法

假设要给用户u进行个性化推荐，可以从用户u对应的节点vu开始在用户物品二分图上进行随机游走。游走到任何一个节点时，首先按照概率α决定是继续游走，还是停止这次游走并从vu节点开始重新游走。如果决定继续游走，那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品节点被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。

缺点：复杂度高，耗时

第三章冷启动问题

冷启动问题（cold start）分三类：
用户冷启动（新用户到来）、物品冷启动（新物品到来）、系统冷启动（新开发网站，没有用户和用户行为，只有物品信息）
解决方法：

提供非个性化推荐：比如热门排行榜
利用用户注册时提供的年龄、性别等数据做粗粒度的个性化
利用用户社交网络账号（需用户授权），导入用户好友信息，给用户推荐好友喜欢的物品
要求用户登录时对物品进行反馈，收集兴趣信息从而推荐和物品相似的物品
新加入的物品利用内容信息，将它们推荐给喜欢过相似物品的用户
系统冷启动引入专家知识

用户注册信息分3种：

人口统计学信息：年龄、性别、职业、民族、学历和居住地
用户兴趣描述
其它网站导入用户站外行为数据

基于人口统计学特征的推荐系统其典型代表是Bruce Krulwich开发的Lifestyle Finder。

基于注册信息的个性化推荐流程：

获取用户的注册信息；
根据用户的注册信息对用户分类；
给用户推荐他所属分类中用户喜欢的物品。

有两个推荐系统数据集包含了人口统计学信息，BookCrossing数据集和Last.fm数据集。
BookCrossing数据集包含用户对图书的行为信息，包含3个文件。
BX-Users.csv，包含用户的ID、位置和年龄。
BX-Books.csv，包含图书的ISBN、标题、作者、发表年代、出版社和缩略。
BX-Book-Ratings.csv，包含用户对图书的评分信息。

ItemCF算法存在严重的冷启动问题。

一般来说，物品的内容可以通过向量空间模型（Vector Space Model）表示，该模型会将物品表示成一个关键词向量。
从文本生成关键词向量的主要步骤：文本–>分词–>实体检测–>关键词排名–>关键词向量
对物品d，它的内容表示成一个关键词向量：

d_i = {(e_1, w_1),(e_2,w_2),...}

其中 $e_i$ 是关键词， $w_i$ 是关键词权重。
若物品是文本，可用信息检索领域著名的TF-IDF公式计算词的权重：

…先让我更新一下友链

《推荐系统实践》笔记

第1章好的推荐系统

什么是推荐系统

推荐系统评测

实验方法

评测指标

评测维度

第2章利用用户行为数据

用户活跃度和物品流行度的分布

用户活跃度和物品流行度的关系