第3章推荐系统冷启动问题

如何在没有大量用户数据的情况下设计个性化推荐系统并且让用户对推荐结果满意从而愿意使用推荐系统，就是冷启动的问题。
本章简单介绍一下冷启动问题的分类，以及如何解决不同种类的冷启动问题。

3.1 冷启动问题简介

冷启动问题(cold start)主要分3类。

用户冷启动 用户冷启动主要解决如何给新用户做个性化推荐的问题。
物品冷启动 物品冷启动主要解决如何将新的物品推荐给可能对它感兴趣的用户这一问题。
系统冷启动 系统冷启动主要解决如何在一个新开发的网站上（还没有用户，也没有用户行为，只有一些物品的信息）设计个性化推荐系统，从而在网站刚发布时就让用户体验到个性化推荐服务这一问题。

对于这3种不同的冷启动问题，有不同的解决方案。一般来说，可以参考如下解决方案。

提供非个性化的推荐。 非个性化推荐的最简单例子就是热门排行榜。
利用用户注册时提供的年龄、性别等数据做粗粒度的个性化。
利用用户的社交网络账号登录（需要用户授权），导入用户在社交网站上的好友信息，然后给用户推荐其好友喜欢的物品。
要求用户在登录时对一些物品进行反馈，收集用户对这些物品的兴趣信息，然后给用户推荐那些和这些物品相似的物品。
对于新加入的物品，可以利用内容信息，将它们推荐给喜欢过和它们相似的物品的用户。
在系统冷启动时，可以引入专家的知识，通过一定的高效方式迅速建立起物品的相关度表。

3.2 利用用户注册信息

用户的注册信息分3种。

人口统计学信息 包括用户的年龄、性别、职业、民族、学历和居住地。
用户兴趣的描述 有一些网站会让用户用文字描述他们的兴趣。
从其他网站导入的用户站外行为数据 比如用户通过豆瓣、新浪微博的账号登录，就可以在得到用户同意的情况下获取用户在豆瓣或者新浪微博的一些行为数据和社交网络数据。

基于人口统计学特征的推荐系统其典型代表是Bruce Krulwich开发的Lifestyle Finder(参见论文Bruce Krulwich的“Lifestyle finder : intelligent user profiling using large scale demographic data”（1997）) 。书上这部分有关于该算法的简略介绍和评测，但并没有涉及该算法是具体如何根据人口统计学属性进行分类的，详情见书。

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

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

基于用户注册信息的推荐算法其核心问题是计算每种特征的用户喜欢的物品。也就是说，对于每种特征$f$，计算具有这种特征的用户对各个物品的喜好程度$p(f, i)$。
$p(f,i)$可以简单地定义为物品$i$在具有$f$的特征的用户中的热门程度：$$p(f,i)=\vert N(i) \cap U(f) \vert$$其中$N(i)$是喜欢物品$i$的用户集合，$U(f)$是具有特征$f$的用户集合。

上面这种定义可以比较准确地预测具有某种特征的用户是否喜欢某个物品。但是，在这种定义下，往往热门的物品会在各种特征的用户中都具有比较高的权重。也就是说具有比较高的$\vert N (i) \vert$的物品会在每一类用户中都有比较高的$p(f ,i)$。给用户推荐热门物品并不是推荐系统的主要任务，推荐系统应该帮助用户发现他们不容易发现的物品。因此，可以将$p( f , i )$定义为喜欢物品$i$的用户中具有特征$f$的比例：$$p(f,i) = \frac {\vert N(i) \cap U(f) \vert}{\vert N(i) \vert + \alpha}$$这里分母中使用参数$\alpha$的目的是解决数据稀疏问题。比如有一个物品只被1个用户喜欢过，而这个用户刚好就有特征$f$，那么就有$p(f,i)$。但是，这种情况并没有统计意义，因此为分母加上一个比较大的数，可以避免这样的物品产生比较大的权重。

有两个推荐系统数据集包含了人口统计学信息，一个是 BookCrossing 数据集。另一个是Lastfm数据集。

BookCrossing数据集:
参见http://www.informatik.uni-freiburg.de/~cziegler/BX/
Lastfm数据集：
参见http://www.dtic.upf.edu/~ocelma/MusicRecommendationDataset/lastfm-360K.html

作者在这两个数据集上做实验验证，证明基于人口统计学特征的推荐系统准确率、召回率和覆盖率确实更高，而且利用的用户人口统计学特征越多，越能准确地预测用户兴趣，详情见书。

3.3 选择合适的物品启动用户的兴趣

对于通过让用户对物品进行评分来收集用户兴趣，从而对用户进行冷启动的系统，它们需要解决的首要问题就是如何选择物品让用户进行反馈。

一般来说，能够用来启动用户兴趣的物品需要具有以下特点。

比较热门 因为用户需要知道这个物品是什么，才能对它们作出准确反馈。
具有代表性和区分性 启动用户兴趣的物品不能是大众化或老少咸宜的，因为这样的物品对用户的兴趣没有区分性。
启动物品集合需要有多样性 冷启动时，由于不清楚用户的兴趣，并且用户用户兴趣的可能性非常多，为了匹配多样的兴趣，为此需要提供具有很高覆盖率的启动物品集合，这些物品能覆盖几乎所有主流的用户兴趣。

上面这些因素都是选择启动物品时需要考虑的，但还需要考虑的是如何设计一个选择启动物品集合的系统？Nadav Golbandi在论文中(“Adaptive Bootstrapping of Recommender Systems Using Decision Trees”，下载地址为 http://research.yahoo.com/pub/3502) 探讨了这个问题，提出可以用一个决策树解决这个问题。
首先，给定一群用户，Nadav Golbandi用这群用户对物品评分的方差度量这群用户兴趣的一致程度。如果方差很大，说明这一群用户的兴趣不太一致，反之则说明这群用户的兴趣比较一致。令$\sigma_u \in U’$为用户集合$U’$中所有评分的方差，Nadav Golbandi的基本思想是通过如下方式度量一个物品的区分度$D(i)$:$$D(i) = \sigma_{u \in N^+(i)} + \sigma_{u \in N^-(i)} + \sigma_{u \in \bar N(i)}$$其中，$N^+(i)$是喜欢物品i的用户集合，$N^-(i)$是不喜欢物品i的用户集合，$\bar N(i)$是没有对物品$i$评分的用户集合。$ \sigma_{u \in N^+(i)}$是喜欢物品i的用户对其他物品评分的方差，$\sigma_{u \in N^-(i)}$是不喜欢物品$i$的用户对其他物品评分的方差，$\sigma_{u \in \bar N(i)}$是没有对物品$i$评分的用户对其他物品评分的方差。也就是说，对于物品$i$，Nadav Golbandi将用户分成3类——喜欢物品i的用户、不喜欢物品i的用户和不知道物品i的用户（即没有给i评分的用户）。如果这3类用户集合内的用户对其他的物品兴趣很不一致，说明物品i具有较高的区分度。
Nadav Golbandi的算法首先会从所有用户中找到具有最高区分度的物品i，然后将用户分成3类。然后在每类用户中再找到最具区分度的物品，然后将每一类用户又各自分为3类，也就是将总用户分成9类，然后这样继续下去，最终可以通过对一系列物品的看法将用户进行分类。而在冷启动时，我们从根节点开始询问用户对该节点物品的看法，然后根据用户的选择将用户放到不同的分枝，直到进入最后的叶子节点，此时我们就已经对用户的兴趣有了比较清楚的了解，从而可以开始对用户进行比较准确地个性化推荐。

3.4 利用物品的内容信息

物品冷启动需要解决的问题是如何将新加入的物品推荐给对它感兴趣的用户。

第2章介绍了两种主要的推荐算法——UserCF和ItemCF算法。首先需要指出的是，UserCF算法对物品冷启动问题并不非常敏感。因为，UserCF在给用户进行推荐时，会首先找到和用户兴趣相似的一群用户，然后给用户推荐这一群用户喜欢的物品。在很多网站中，推荐列表并不是给用户展示内容的唯一列表，那么当一个新物品加入时，总会有用户从某些途径看到这些物品，对这些物品产生反馈。那么，当一个用户对某个物品产生反馈后，和他历史兴趣相似的其他用户的推荐列表中就有可能出现这一物品，从而更多的人就会对这个物品产生反馈，导致更多的人的推荐列表中会出现这一物品，因此该物品就能不断地扩散开来，从而逐步展示到对它感兴趣用户的推荐列表中。
但是，有些网站中推荐列表可能是用户获取信息的主要途径，比如豆瓣网络电台。那么对于UserCF算法就需要解决第一推动力的问题，即第一个用户从哪儿发现新的物品。只要有一小部分人能够发现并喜欢新的物品，UserCF算法就能将这些物品扩散到更多的用户中。解决第一推动力最简单的方法是将新的物品随机展示给用户，但这样显然不太个性化，因此可以考虑利用物品的内容信息，将新物品先投放给曾经喜欢过和它内容相似的其他物品的用户。
对于ItemCF算法来说，物品冷启动就是一个严重的问题了。因为ItemCF算法的原理是给用户推荐和他之前喜欢的物品相似的物品。ItemCF算法会每隔一段时间利用用户行为计算物品相似度表（一般一天计算一次），在线服务时ItemCF算法会将之前计算好的物品相关度矩阵放在内存中。因此，当新物品加入时，内存中的物品相关表中不会存在这个物品，从而ItemCF算法无法推荐新的物品。解决这一问题的办法是频繁更新物品相似度表，但基于用户行为计算物品相似度是非常耗时的事情，主要原因是用户行为日志非常庞大。而且，新物品如果不展示给用户，用户就无法对它产生行为，通过行为日志计算是计算不出包含新物品的相关矩阵的。为此，我们只能利用物品的内容信息计算物品相关表，并且频繁地更新相关表（比如半小时计算一次）。

一般来说，物品的内容可以通过向量空间模型(参见维基百科Vector Space Model词条)表示，该模型会将物品表示成一个关键词向量。如果物品的内容是一些诸如导演、演员等实体的话，可以直接将这些实体作为关键词。但如果内容是文本的形式，则需要引入一些理解自然语言的技术抽取关键词。图3-11展示了从文本生成关键词向量的主要步骤。对于中文，首先要对文本进行分词，将字流变成词流，然后从词流中检测出命名实体（如人名、地名、组织名等），这些实体和一些其他重要的词将组成关键词集合，最后对关键词进行排名，计算每个关键词的权重，从而生成关键词向量。
关键词向量的生成过程
对于物品$d$，它的内容表示成一个关键词向量如下：$$d_i = \{ (e_1,w_1),(e_2,w_2), ···\}$$其中$e_i$是关键词，$w_i$是关键词对应的权重。如果物品是文本，我们可以用信息检索领域著名的TF-IDF公式计算词的权重：$$w_i = \frac {TF(e_i)}{\log DF(e_i)}$$

向量空间模型的优点是简单，缺点是丢失了一些信息，比如关键词之间的关系信息。不过在绝大多数应用中，向量空间模型对于文本的分类、聚类、相似度计算已经可以给出令人满意的结果。

在给定物品内容的关键词向量后，物品的内容相似度可以通过向量之间的余弦相似度计算：$$w_{ij} = \frac {d_i \cdot d_j}{\sqrt {\Vert d_i \Vert \Vert d_j \Vert}}$$
在具体计算物品之间的内容相似度时，最简单的方法当然是对两两物品都利用上面的余弦相似度公式计算相似度，如下代码简单实现了这种方法：

def CalculateSimilarity(D):
    for di in D:
        for dj in D:
            w[i][j] = CosineSimilarity(di, dj) 
    return w

D是文档集合。

但这种算法的时间复杂度很高。假设有$N$个物品，每个物品平均由$m$个实体表示，那么这个算法的复杂度是$O( N^2m)$。在实际应用中，可以首先通过建立关键词—物品的倒排表加速这一计算过程，关于这一方法已经在前面介绍UserCF和ItemCF算法时详细介绍过了，所以这里直接给出计算的代码：

def CalculateSimilarity(entity-items)
    w = dict() 
    ni = dict() 
    for e,items in entity_items.items():
        for i,wie in items.items(): 
            addToVec(ni, i, wie * wie) 
            for j,wje in items.items(): 
                addToMat(w, i, j, wie, wje) 
    for i, relate_items in w.items():
        relate_items = {x:y/math.sqrt(ni[i] * ni[x]) for x,y in relate_items.items()}

得到物品的相似度之后，可以利用上一章提到的ItemCF算法的思想，给用户推荐和他历史上喜欢的物品内容相似的物品。

既然内容相似度计算简单，能频繁更新，而且能够解决物品冷启动问题，那么为什么还需要协同过滤的算法?书中这部分在MovieLens和GitHub两个数据集上进行了实验，并加以说明，详情见书。

话题模型

向量空间模型在内容数据丰富时可以获得比较好的效果。以文本为例，如果是计算长文本的相似度，用向量空间模型利用关键词计算相似度已经可以获得很高的精确度。但是，如果文本很短，关键词很少，向量空间模型就很难计算出准确的相似度。举个例子，假设有两篇论文，它们的标题分别是“推荐系统的动态特性”和“基于时间的协同过滤算法研究”。如果读者对推荐系统很熟悉，可以知道这两篇文章的研究方向是类似的，但是它们标题中没有一样的关键词。其实，它们的关键词虽然不同，但却是相似的。“动态”和“基于时间”含义相似，“协同过滤”是“推荐系统”的一种算法。换句话说，这两篇文章的关键词虽然不同，但关键词所属的话题是相同的。在这种情况下，首先需要知道文章的话题分布，然后才能准确地计算文章的相似度。如何建立文章、话题和关键词的关系是话题模型（topic model）研究的重点。

代表性的话题模型有LDA。关于LDA的详细理论介绍可以参考DM Blei的论文“Latent Dirichlet Allocation” (参见David M. Blei、 Andrew Y. Ng、 Michael I. Jordan的“ Latent dirichlet allocation”（Journal of Machine Learning Research 3， 2003）)。
任何模型都有一个假设，LDA作为一种生成模型，对一篇文档产生的过程进行了建模。话题模型的基本思想是，一个人在写一篇文档的时候，会首先想这篇文章要讨论哪些话题，然后思考这些话题应该用什么词描述，从而最终用词写成一篇文章。因此，文章和词之间是通过话题联系的。
LDA中有3种元素，即文档、话题和词语。每一篇文档都会表现为词的集合，这称为词袋模型(bag of words)。每个词在一篇文章中属于一个话题。令$D$为文档集合，$D[i]$是第$i$篇文档。$w[i][j]$是第$i$篇文档中的第$j$个词。$z[i][j]$是第$i$篇文档中第$j$个词属于的话题。

LDA的计算过程包括初始化和迭代两部分。首先要对$z$进行初始化，而初始化的方法很简单，假设一共有$K$个话题，那么对第$i$篇文章中的第$j$个词，可以随机给它赋予一个话题。同时，用$NWZ(w,z)$记录词$w$被赋予话题$z$的次数，$NZD(z,d)$记录文档$d$中被赋予话题$z$的词的个数。

foreach document i in range(0,|D|):
    foreach word j in range(0, |D(i)|):
        z[i][j] = rand() % K 
        NZD[z[i][j], D[i]]++ 
        NWZ[w[i][j], z[i][j]]++ 
        NZ[z[i][j]]++

在初始化之后，要通过迭代使话题的分布收敛到一个合理的分布上去。伪代码如下所示：

while not converged:
    foreach document i in range(0, |D|):
        foreach word j in range(0, |D(i)|): 
            NWZ[w[i][j], z[i][j]]--
            NZ[z[i][j]]--
            NZD[z[i][j], D[i]]--
            z[i][j] = SampleTopic() 
            NWZ[w[i][j], z[i][j]]++ 
            NZ[z[i][j]]++ 
            NZD[z[i][j], D[i]]++

LDA可以很好地将词组合成不同的话题。

在使用LDA计算物品的内容相似度时，可以先计算出物品在话题上的分布，然后利用两个物品的话题分布计算物品的相似度。比如，如果两个物品的话题分布相似，则认为两个物品具有较高的相似度，反之则认为两个物品的相似度较低。计算分布的相似度可以利用KL散度(参见http://en.wikipedia.org/wiki/Kullback-Leibler_divergence) ：$$D_{KL}(p||q) = \sum_i p(i)ln \frac{p(i)}{q(i)}$$其中$p$和$q$是两个分布，KL散度越大说明分布的相似度越低。

3.5 发挥专家的作用

书中这部分对个性化网络电台Pandora和电影推荐网站Jinni如何利用专家对物品进行标注，进而建立推荐系统作了介绍。

第3章 推荐系统冷启动问题