推荐系统实践读书笔记（二）

第2章 利用用户行为数据

用户行为数据中蕴涵着很多不是那么显而易见的规律，而个性化推荐算法的任务就是通过计算机去发现这些规律，从而为产品的设计提供指导，提高用户体验。
基于用户行为分析的推荐算法是个性化推荐系统的重要算法，学术界一般将这种类型的算法称为协同过滤算法。顾名思义，协同过滤就是指用户可以齐心协力，通过不断地和网站互动，使自己的推荐列表能够不断过滤掉自己不感兴趣的物品，从而越来越满足自己的需求。

2.1 用户行为数据简介

用户行为数据的存在形式

用户行为数据在网站上最简单的存在形式就是日志。网站在运行过程中都产生大量原始日志(raw log)，并将其存储在文件系统中。很多互联网业务会把多种原始日志按照用户行为汇总成会话日志(session log)，其中每个会话表示一次用户行为和对应的服务。比如，在搜索引擎和搜索广告系统中，服务会为每次查询生成一个展示日志(impression log)，其中记录了查询和返回结果。如果用户点击了某个结果，这个点击信息会被服务器截获并存储在点击日志(click log)中。 一个并行程序会周期性地归并展示日志和点击日志，得到的会话日志中每个消息是一个用户提交的查询、得到的结果以及点击。类似地，推荐系统和电子商务网站也会汇总原始日志生成描述用户行为的会话日志。

用户行为数据的分类

用户行为在个性化推荐系统中一般分两种——显性反馈行为(explicit feedback)和隐性反馈行为(implicit feedback)。显性反馈行为包括用户明确表示对物品喜好的行为，主要形式就是评分和喜欢/不喜欢。和显性反馈行为相对应的是隐性反馈行为。隐性反馈行为指的是那些不能明确反应用户喜好的行为。最具代表性的隐性反馈行为就是页面浏览行为。
按照反馈的明确性分，用户行为数据可以分为显性反馈和隐性反馈，但按照反馈的方向分，又可以分为正反馈和负反馈。正反馈指用户的行为倾向于指用户喜欢该物品，而负反馈指用户的行为倾向于指用户不喜欢该物品。在显性反馈中，很容易区分一个用户行为是正反馈还是负反馈，而在隐性反馈行为中，就相对比较难以确定。

显性反馈数据和隐性反馈数据的区别

下图从几个方面比较了显性反馈数据和隐性反馈数据。

用户行为的表示方式

下图给出了一种表示方式，它将一个用户行为表示为六部分，即产生行为的用户和行为的对象。行为的种类、产生行为的上下文、行为的内容和权重。

很多时候我们并不使用统一结构表示所有行为，而是针对不同的行为给出不同表示。有时可能会忽略一些信息(比如上下文)，但有些信息不能忽略(比如产生行为的用户和行为的对象就是所有行为都必须包含的)。

数据集的分类

不同的数据集针对不同的情况，根据所包含行为的不同将数据集进行分类，目前比较有代表性的数据集有如下几个：

• 无上下文信息的隐性反馈数据集 每一条行为记录仅仅包含用户ID和物品ID。Book-Crossing(参见“Book-Crossing Dataset”，地址为http://www.informatik.uni-freiburg.de/~cziegler/BX/) 就是这种类型的数据集。
• 无上下文信息的显性反馈数据集 每一条记录包含用户ID、物品ID和用户对物品的评分。
• 有上下文信息的隐性反馈数据集 每一条记录包含用户ID、物品ID和用户对物品产生行为的时间戳。Lastfm数据集(参见http://www.dtic.upf.edu/~ocelma/MusicRecommendationDataset/lastfm-1K.html) 就是这种类型的数据集。
• 有上下文信息的显性反馈数据集 每一条记录包含用户ID、物品ID、用户对物品的评分和评分行为发生的时间戳。Netflix Prize(参见http://netflixprize.com/) 提供的就是这种类型的数据集。

2.2 用户行为分析

在利用用户行为数据设计推荐算法之前，研究人员首先需要对用户行为数据进行分析，了解数据中蕴含的一般规律，这样才能对算法的设计起到指导作用。

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

长尾分布

很多关于互联网数据的研究发现，互联网上的很多数据分布都满足一种称为Power Law(参见“浅谈网络世界的Power Law现象”，地址为http://mmdays.com/2008/11/22/power_law_1/) 的分布，这个分布在互联网领域也称长尾分布。$$f(x) = \alpha x^k$$
1932年，哈佛大学的语言学家Zipf在研究英文单词的词频时发现，如果将单词出现的频率按照由高到低排列，则每个单词出现的频率和它在热门排行榜中排名的常数次幂成反比。这个现象表明，在英文中大部分词的词频其实很低，只有很少的词被经常使用。
用户行为数据也蕴含着这种规律。令$f_u(k)$为对k个物品产生过行为的用户数，令$f_i(k)$为被k个用户产生过行为的物品数。那么，$f_u(k)$和$f_i(k)$都满足长尾分布。也就是说：$$f_u(k)= \alpha_u k^{\beta_u}$$ $$f_i(k)= \alpha_i k^{\beta_i}$$

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

用户越活跃，越倾向于浏览冷门的物品。
仅仅基于用户行为数据设计的推荐算法一般称为协同过滤算法。 学术界对协同过滤算法进行了深入研究，提出了很多方法，比如基于邻域的方法（ neighborhood-based ）、隐语义模型（ latent factor model）、基于图的随机游走算法（random walk on graph）等。在这些方法中，最著名的、在业界得到最广泛应用的算法是基于邻域的方法， 而基于邻域的方法主要包含下面两种算法。

• 基于用户的协同过滤算法
• 基于物品的协同过滤算法

2.3 实验设计和算法评测

2.3.1 数据集

采用GroupLens提供的MovieLens数据集(数据集详细信息见 http://www.grouplens.org/node/73) 介绍和评测各种算法，并且忽略了数据集中的评分记录。

2.3.2 实验设计

协同过滤算法的离线实验一般如下设计。首先，将用户行为数据集按照均匀分布随机分成M份，挑选一份作为测试集，将剩下的M-1份作为训练集。然后在训练集上建立用户兴趣模型，并在测试集上对用户行为进行预测，统计出相应的评测指标。为了保证评测指标并不是过拟合的结果，需要进行M次实验，并且每次都使用不同的测试集。然后将M次实验测出的评测指标的平均值作为最终的评测指标。

下面的代码描述了将数据集随机分成训练集和测试集的过程：

def SplitData(data, M, k, seed):
    test = []
    train = []
    random.seed(seed)
    for user, item in data:
        if random.randint(0,M) == k:
            test.append([user,item])
        else: 
            train.append([user,item])
    return train, test

这里，每次实验选取不同的k（0≤k≤M-1）和相同的随机数种子seed，进行M次实验就可以得到M个不同的训练集和测试集，然后分别进行实验，用M次实验的平均值作为最后的评测指标。这样做主要是防止某次实验的结果是过拟合的结果（over fitting），但如果数据集够大，模型够简单，为了快速通过离线实验初步地选择算法，也可以只进行一次实验。

2.3.3 评测指标

召回率和准确率

计算方法和第一章预测准确度中TopN推荐部分一样

覆盖率

同样与之前介绍的一致。如下代码可以用来计算推荐算法的覆盖率：

def Coverage(train, test, N):
    recommend_items = set() 
    all_items = set() 
    for user in train.keys():
        for item in train[user].keys():
            all_items.add(item)
        rank = GetRecommendation(user, N)
        for item, pui in rank:
            recommend_items.add(item) 
    return len(recommend_items) / (len(all_items) * 1.0)

新颖度

使用推荐列表中物品的平均流行度度量推荐结果的新颖度。如果推荐出的物品都很热门，说明推荐的新颖度较低，否则说明推荐结果比较新颖。

def Popularity(train, test, N):
    item_popularity = dict() 
    for user, items in train.items():
        for item in items.keys() 
            if item not in item_popularity:
                item_popularity[item] = 0 
            item_popularity[item] += 1 
    ret = 0 
    n = 0 
    for user in train.keys():
        rank = GetRecommendation(user, N)
        for item, pui in rank:
            ret += math.log(1 + item_popularity[item]) 
            n += 1 
    ret /= n * 1.0 
    return ret

计算平均流行度时对每个物品的流行度取对数，这是因为物品的流行度分布满足长尾分布，在取对数后，流行度的平均值更加稳定。

2.4 基于近邻的算法

基于邻域的算法分为两大类，一类是基于用户的协同过滤算法，另一类是基于物品的协同过滤算法。

2.4.1 基于用户的协同过滤算法(UserCF算法)

基于用户的协同过滤算法是推荐系统中最古老的算法。这个算法的诞生标志了推荐系统的诞生。该算法在1992年被提出，并应用于邮件过滤系统，1994年被GroupLens用于新闻过滤。在此之后直到2000年，该算法都是推荐系统领域最著名的算法。

1.基础算法

在一个在线个性化推荐系统中，当一个用户A需要个性化推荐时，可以先找到和他有相似兴趣的其他用户，然后把那些用户喜欢的、而用户A没有听说过的物品推荐给A。这种方法称为基于用户的协同过滤算法。
基于用户的协同过滤算法主要包括两个步骤。

1. 找到和目标用户兴趣相似的用户集合。
2. 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户。

步骤(1)的关键是计算两个用户的兴趣相似度。协同过滤算法主要利用行为的相似度计算兴趣的相似度。给定用户u和用户v，令$N(u)$表示用户u曾经有过正反馈的物品集合，令$N(v)$为用户v曾经有过正反馈的物品集合。可以通过如下的Jaccard公式简单计算用户u和用户v的兴趣相似度：$$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)|}}$$
实现余弦相似度可以利用如下的伪码：

def UserSimilarity(train):
    W = dict() 
    for u in train.keys():
        for v in train.keys():
            if u == v:
                continue 
            W[u][v] = len(train[u] & train[v]) 
            W[u][v] /= math.sqrt(len(train[u]) * len(train[v]) * 1.0) 
    return W

该代码对两两用户都利用余弦相似度计算相似度。这种方法的时间复杂度是$O(|U|*|U|)$，这在用户数很大时非常耗时。由于实际上很多用户户相互之间并没有对同样的物品产生过行为，即$|N(u)\cap N(v)| = 0 $，因此会将很多时间浪费在计算用户之间相似度上。换个思路，首先计算出$|N(u)\cap N(v)|\neq 0$的用户对$(u, v)$，然后再对这种情况除以分母$\sqrt{|N(u)||N(v)|}$。
为此，首先建立物品到用户的倒排表，对于每个物品都保存对该物品产生过行为的用户列表。令稀疏矩阵$C[u][v]= N(u) \cap N(v)$ 。那么，假设用户u和用户v同时属于倒排表中K个物品对应的用户列表，就有$C[u][v]=K$。从而，可以扫描倒排表中每个物品对应的用户列表，将用户列表中的两两用户对应的$C[u][v]$加1，最终就可以得到所有用户之间不为0的$C[u][v]$。下面的代码实现了上面提到的算法：

def UserSimilarity(train):
    # build inverse table for item_users 
    item_users = dict() 
    for u, items in train.items():
        for i in items.keys():
            if i not in item_users: 
                item_users[i] = set() 
            item_users[i].add(u)
            
    #calculate co-rated items between users 
    C = dict() 
    N = dict() 
    for i, users in item_users.items():
        for u in users:
            N[u] += 1 
            for v in users: 
                if u == v: 
                    continue 
                C[u][v] += 1
                
    #calculate finial similarity matrix W 
    W = dict() 
    for v, cuv in related_users.items(): 
        W[u][v] = cuv / math.sqrt(N[u] * N[v]) 
    return W

得到用户之间的兴趣相似度后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户u对物品i的感兴趣程度：$$p(u,i)=\sum_{v \in S(u,K) \cap N(i)} w_{uv}r_{vi}$$
其中，$S(u,K)$包含和用户u兴趣最接近的K个用户，$N(i)$是对物品i有过行为的用户集合，$w_{uv}$是用户u和用户v的兴趣相似度，$r_{vi}$代表用户v对物品i的兴趣，因为使用的是单一行为的隐反馈数据，所以所有的$r_{vi}=1$。

如下代码实现了上面的UserCF推荐算法：

def Recommend(user, train, W):
    rank = dict() 
    interacted_items = train[user] 
    for v, wuv in sorted(W[u].items, key=itemgetter(1), \
        reverse=True)[0:K]:
        for i, rvi in train[v].items:
            if i in interacted_items:
                # we should filter items user interacted before
                continue 
            rank[i] += wuv * rvi 
    return rank

参数K是UserCF的一个重要参数，它的调整对推荐算法的各种指标都会产生一定的影响。

• 准确率和召回率 选择合适的K对于获得高的推荐系统精度比较重要。推荐结果的精度对K也不是特别敏感，只要选在一定的区域内，就可以获得不错的精度。
• 流行度 K越大，参考的人越多，结果就越来越趋近于全局热门的物品。
• 覆盖率 K越大，则UserCF推荐结果的覆盖率越低。覆盖率的降低是因为流行度的增加，随着流行度增加，UserCF越来越倾向于推荐热门的物品，从而对长尾物品的推荐越来越少，因此造成了覆盖率的降低。

2.用户相似度计算的改进

之前介绍的通过余弦相似度公式计算兴趣相似度，但是由于这个公式过于粗糙，于是需要改进该公式来提高UserCF的推荐性能。
研究表明，用户对冷门物品采取与热门物品同样的行为更能说明他们兴趣的相似度。因此，John S. Breese在论文(参见John S. Breese、 David Heckerman和 Carl Kadie的论文“ Empirical Analysis of Predictive Algorithms for Collaborative Filtering”（Morgan Kaufmann Publishers，1998）)中提出了如下公式，根据用户行为计算用户的兴趣相似度：$$w_{uv} = \frac {\sum_{i \in N(u) \cap N(v)}\frac{1}{\log 1 + |N(i)|}}{\sqrt{|N(u)||N(v)|}}$$
该公式通过$\frac{1}{\log 1 + |N(i)|}$惩罚了用户u和用户v共同兴趣列表中热门物品对他们相似度的影响。

将基于上述用户相似度公式的UserCF算法记为User-IIF算法。下面的代码实现了上述用户相似度公式。

def UserSimilarity(train):
    # build inverse table for item_users
    item_users = dict() 
    for u, items in train.items():
        for i in items.keys():
            if i not in item_users: 
                item_users[i] = set() 
            item_users[i].add(u)
            
    #calculate co-rated items between users 
    C = dict() 
    N = dict() 
    for i, users in item_users.items():
        for u in users:
            N[u] += 1 
            for v in users:
                if u == v:
                    continue 
                C[u][v] += 1 / math.log(1 + len(users))

    #calculate finial similarity matrix W 
    W = dict() 
    for u, related_users in C.items():
        for v, cuv in related_users.items(): 
            W[u][v] = cuv / math.sqrt(N[u] * N[v]) 
    return W

通过实验评测证明计算用户兴趣相似度时考虑物品的流行度对提升推荐效果的质量确实有帮助。

3.实际在线系统中使用UserCF的例子

相比我们后面要讨论的基于物品的协同过滤算法(ItemCF)，UserCF在目前的实际应用中使用并不多。其中最著名的使用者是Digg，书中这部分介绍了Digg的推荐系统设计思路。

4.UserCF算法的缺点

首先，随着网站的用户数目越来越大，计算用户兴趣相似度矩阵将越来越困难，其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系。其次，基于用户的协同过滤很难对推荐结果作出解释。

2.4.2 基于物品的协同过滤算法(ItemCF)

基于物品的协同过滤（item-based collaborative filtering）算法是目前业界应用最多的算法。无论是亚马逊网，还是Netflix、Hulu、YouTube，其推荐算法的基础都是该算法。

1.基础算法

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

基于物品的协同过滤算法主要分为两步：

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

为了避免推荐出热门的商品，用下面的公式定义物品的相似度：$$w_{ij}=\frac {|N(i)\cap N(j)|} {\sqrt{|N(i)||N(j)|}}$$
这个公式惩罚了物品j的权重，因此减轻了热门物品会和很多物品相似的可能性。

和UserCF算法类似，用ItemCF算法计算物品相似度时也可以首先建立用户—物品倒排表（即对每个用户建立一个包含他喜欢的物品的列表），然后对于每个用户，将他物品列表中的物品两两在共现矩阵C中加1。

详细代码如下所示：

def ItemSimilarity(train):
    #calculate co-rated users between items 
    C = dict() 
    N = dict() 
    for u, items in train.items():
        for i in users:
            N[i] += 1 
            for j in users:
                if i == j:
                    continue 
                C[i][j] += 1

    #calculate finial similarity matrix W 
    W = dict() 
    for i,related_items in C.items():
        for j, cij in related_items.items(): 
            W[u][v] = cij / math.sqrt(N[i] * N[j]) 
    return W

在得到物品之间的相似度后，ItemCF通过如下公式计算用户u对一个物品j的兴趣：$$p_{uj}=\sum_{i\in N(u) \cap S(j,K)} {w_{ji}r_{ui}} $$
这里$N(u)$是用户喜欢的物品的集合，$S(j,K)$是和物品$j$最相似的$K$个物品的集合，$w_{ji}$是物品$j$和$i$的相似度，$r_{ui}$是用户$u$对物品$i$的兴趣。（对于隐反馈数据集，如果用户$u$对物品$i$有过行为，即可令$r_{ui}$ =1。）该公式的含义是，和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名。

该公式的实现代码如下所示。

def Recommendation(train, user_id, W, K):
    rank = dict() 
    ru = train[user_id] 
    for i,pi in ru.items():
        for j, wj in sorted(W[i].items(), / key=itemgetter(1), reverse=True)[0:K]: 
            if j in ru:
                continue 
            rank[j] += pi * wj 
    return rank

ItemCF的一个优势就是可以提供推荐解释，即利用用户历史上喜欢的物品为现在的推荐结果进行解释。

如下代码实现了带解释的ItemCF算法：

def Recommendation(train, user_id, W, K):
    rank = dict() 
    ru = train[user_id] 
    for i,pi in ru.items():
        for j, wj in sorted(W[i].items(), / key=itemgetter(1), reverse=True)[0:K]: 
            if j in ru:
                continue 
            rank[j].weight += pi * wj 
            rank[j].reason[i] = pi * wj 
    return rank

参数K同样也是ItemCF算法中的一个重要参数。

• 精度(准确率和召回率) ItemCF推荐结果的精度也是不和K成正相关或者负相关的，因此选择合适的K对获得最高精度是非常重要的。
• 流行度 和UserCF不同，参数K对ItemCF推荐结果流行度的影响也不是完全正相关的。随着K的增加，结果流行度会逐渐提高，但当K增加到一定程度，流行度就不会再有明显变化。
• 覆盖率 K增加会降低系统的覆盖率。

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

John S. Breese在论文中(参见John S. Breese、 David Heckerman和 Carl Kadie的“ Empirical Analysis of Predictive Algorithms for Collaborative Filtering”（Morgan Kaufmann Publishers ，1998）)提出了一个称为IUF(Inverse User Frequence)，即用户活跃度对数的倒数的参数，他认为活跃用户对物品相似度的贡献应该小于不活跃的用户，他提出应该增加IUF 参数来修正物品相似度的计算公式：$$w_{ij}=\frac{\sum_{u\in N(i)\cap N(j)} \frac{1}{\log1 + |N(u)|}}{\sqrt{|N(i)||N(j)|}}$$

上面的公式只是对活跃用户做了一种软性惩罚，对于很多过于活跃的用户，为了避免相似度矩阵过于稠密，在实际计算中一般直接忽略他的兴趣列表，而不将其纳入到相似度计算的数据集中。

下面代码实现了改进后的算法，并将改进后的算法记为ItemCF-IUF：

def ItemSimilarity(train):
    #calculate co-rated users between items 
    C = dict() 
    N = dict() 
    for u, items in train.items():
        for i in users:
            N[i] += 1 
            for j in users:
                 if i == j:
                     continue 
                 C[i][j] += 1 / math.log(1 + len(items) * 1.0)
                    
    #calculate finial similarity matrix W 
    W = dict() 
    for i,related_items in C.items():
        for j, cij in related_items.items(): 
            W[u][v] = cij / math.sqrt(N[i] * N[j]) 
    return W

通过离线算法评测该算法证明，ItemCF-IUF在准确率和召回率两个指标上和ItemCF相近，但ItemCF-IUF明显提高了推荐结果的覆盖率，降低了推荐结果的流行度。从这个意义上说，ItemCF-IUF确实改进了ItemCF的综合性能。

3.物品相似度的归一化

Karypis在研究中发现如果将ItemCF的相似度矩阵按最大值归一化，可以提高推荐的准确率(参见George Karypis的论文“ Evaluation of Item-based Top-N Recommendation Algorithms”)。其研究表明，如果已经得到了物品相似度矩阵w，那么可以用如下公式得到归一化之后的相似度矩阵$w’$：$$w_{ij}’ = \frac{w_{ij}}{max_j{w_{ij}}}$$
归一化的好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。从实验结果可以看到，归一化确实能提高ItemCF的性能，其中各项指标都有了比较明显的提高。

2.4.3 UserCF和ItemCF的综合比较

UserCF和ItemCF的应用领域比较及原因

UserCF多被用于新闻推荐比如Digg，而ItemCF则在电子商务和书籍电影推荐方面得到广泛应用比如Amazon和Netflix。
UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点，而ItemCF 的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反映了用户所在的小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反映了用户自己的兴趣传承。
在新闻网站中，用户的兴趣不是特别细化，绝大多数用户都喜欢看热门的新闻。即使是个性化，也是比较粗粒度的。因此，个性化新闻推荐更加强调抓住新闻热点，热门程度和时效性是个性化新闻推荐的重点，而个性化相对于这两点略显次要。因此，UserCF可以给用户推荐和他有相似爱好的一群其他用户今天都在看的新闻，这样在抓住热点和时效性的同时， 保证了一定程度的个性化。 这是 Digg在新闻推荐中使用UserCF的最重要原因。
UserCF适合用于新闻推荐的另一个原因是从技术角度考量的。因为作为一种物品，新闻的更新非常快，每时每刻都有新内容出现，而ItemCF需要维护一张物品相关度的表，如果物品更新很快，那么这张表也需要很快更新，这在技术上很难实现。绝大多数物品相关度表都只能做到一天一次更新，这在新闻领域是不可以接受的。而UserCF只需要用户相似性表，虽然UserCF对于新用户也需要更新相似度表，但在新闻网站中，物品的更新速度远远快于新用户的加入速度，而且对于新用户，完全可以给他推荐最热门的新闻，因此UserCF显然是利大于弊。
但是，在图书、电子商务和电影网站，比如亚马逊、豆瓣、Netflix中，ItemCF则能极大地发挥优势。首先，在这些网站中，用户的兴趣是比较固定和持久的。而且这些网站中有一些活跃度很高的人，例如技术人员。一个技术人员可能都是在购买 技术方面的书，而且他们对书的热门程度并不是那么敏感，事实上越是资深的技术人员，他们看的书就越可能不热门。此外，这些系统中的用户大都不太需要流行度来辅助他们判断一个物品的 好坏，而是可以通过自己熟悉领域的知识自己判断物品的质量。因此，这些网站中个性化推荐的任务是帮助用户发现和他研究领域相关的物品。因此，ItemCF算法成为了这些网站的首选算法。 此外，这些网站的物品更新速度不会特别快，一天一次更新物品相似度矩阵对它们来说不会造成太大的损失，是可以接受的。
同时，从技术上考虑，UserCF需要维护一个用户相似度的矩阵，而ItemCF需要维护一个物品相似度矩阵。从存储的角度说，如果用户很多，那么维护用户兴趣相似度矩阵需要很大的空间， 同理，如果物品很多，那么维护物品相似度矩阵代价较大。
在早期的研究中，大部分研究人员都是让少量的用户对大量的物品进行评价，然后研究用户兴趣的模式。对于他们来说，因为用户很少，计算用户兴趣相似度是最快也是最简单的方法。但在实际的互联网中，用户数目往往非常庞大，而在图书、电子商务网站中，物品的数目则是比较少的。此外，物品的相似度相对于用户的兴趣一般比较稳定，因此使用ItemCF是比较好的选择。当然，新闻网站是个例外，在那儿，物品的相似度变化很快，物品数目庞大， 相反用户兴趣则相对固定（都是喜欢看热门的），所以新闻网站的个性化推荐使用UserCF算法的更多。

UserCF与ItemCF的性能比较及原因

离线实验结果可见，ItemCF算法在各项指标上似乎都不如UserCF，特别是其推荐结果的覆盖率和新颖度都低于UserCF。
似乎与之前所说的不符合。首先要指出的是，离线实验的性能在选择推荐算法时并不起决定作用。首先应该满足产品的需求，比如如果需要提供推荐解释，那么可能得选择ItemCF算法。其次，需要看实现代价，比如若用户太多，很难计算用户相似度矩阵，这个时候可能不得不抛弃UserCF算法。最后，离线指标和点击率等在线指标不一定成正比。而且，这里对比的是最原始的UserCF和ItemCF算法，这两种算法都可以进行各种各样的改进。一般来说，这两种算法经过优化后，最终得到的离线性能是近似的。

哈利波特问题

亚马逊网的研究人员在设计ItemCF算法之初发现ItemCF算法计算出的图书相关表存在一个问题，就是很多书都和《哈利波特》相关。 也就是说，购买任何一本书的人似乎都会购买《哈利波特》。后来他们研究发现，主要是因为《哈利波特》太热门了，确实是购买任何一本书的人几乎都会购买它。
回顾一下ItemCF计算物品相似度的经典公式：$$w_{ij}=\frac {\vert N(i)\cap N(j) \vert} {\sqrt{\vert N(i)||N(j)\vert}}$$
这个问题的原因是，如果j非常热门， 那么上面公式的分子$N (i ) \cap N ( j )$就会越来越接近$N (i)$。 尽管上面的公式分母已经考虑到了$j$的流行度，但在实际应用中，热门的j仍然会获得比较大的相似度。

哈利波特问题有几种解决方案。
第一种是在分母上加大对热门物品的惩罚，比如采用如下公式：$$w_{ij} = \frac {\vert N(i) \cap N(j) \vert}{\vert N(i)\vert^{1-\alpha} \vert N(j)\vert^{\alpha}}$$
其中$\alpha \in [0.5,1]$。通过提高$\alpha$，就可以惩罚热门的j。

如果α＝0.5就是标准的ItemCF算法。从离线实验结果可以看到，α只有在取值为0.5时才会导致最高的准确率和召回率，而无论α＜0.5或者α＞0.5都不会带来这两个指标的提高。但是，如果看覆盖率和平均流行度就可以发现，α越大，覆盖率就越高，并且结果的平均热门程度会降低。因此，通过这种方法可以在适当牺牲准确率和召回率的情况下显著提升结果的覆盖率和新颖性（降低流行度即提高了新颖性）。
上述方法还不能彻底地解决哈利波特问题。每个用户一般都会在不同的领域喜欢一种物品。两个不同领域的最热门物品之间往往具有比较高的相似度。这个时候，仅仅靠用户行为数据是不能解决这个问题的，因为用户的行为表示这种物品之间应该相似度很高。此时，我们只能依靠引入物品的内容数据解决这个问题，比如对不同领域的物品降低权重等。这些就不是协同过滤讨论的范畴了。

2.5 隐语义模型

自从Netflix Prize比赛举办以来，LFM（latent factor model）隐语义模型逐渐成为推荐系统领域耳熟能详的名词。其实该算法最早在文本挖掘领域被提出，用于找到文本的隐含语义。

2.5.1 基础算法

隐语义模型的核心思想是通过特征(latent factor)联系用户兴趣和物品。
针对推荐问题除了UserCF、ItemCF算法，还有一种方法就是根据用户的兴趣进行分类。对于某个用户，首先得到他的兴趣分类，然后从分类中挑选他可能喜欢的物品。
这个基于兴趣分类的方法大概需要解决3个问题：

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

对于第一个问题的简单解决方案是找编辑给物品分类。但是，即使有很系统的分类体系，编辑给出的分类仍然具有以下缺点。

• 编辑的意见不能代表各种用户的意见。编辑的分类大部分是从书的内容出 发，而不是从书的读者群出发。
• 编辑很难控制分类的粒度。
• 编辑很难给一个物品多个分类。有的书不仅属于一个类，而是可能属于很多的类。
• 编辑很难给出多维度的分类。
• 编辑很难决定一个物品在某一个分类中的权重。

为了解决上面的问题，研究人员提出：为什么我们不从数据出发，自动地找到那些类，然后进行个性化推荐？于是，隐含语义分析技术（latent variable analysis）出现了。隐含语义分析技术因为采取基于用户行为统计的自动聚类，较好地解决了上面提出的5个问题。

• 编辑的意见不能代表各种用户的意见，但隐含语义分析技术的分类来自对用户行为的统计，代表了用户对物品分类的看法。隐含语义分析技术和ItemCF在物品分类方面的思想类似，如果两个物品被很多用户同时喜欢，那么这两个物品就很有可能属于同一个类。
• 编辑很难控制分类的粒度，但隐含语义分析技术允许我们指定最终有多少个分类，这个数字越大，分类的粒度就会越细，反正分类粒度就越粗。
• 编辑很难给一个物品多个分类，但隐含语义分析技术会计算出物品属于每个类的权重，因此每个物品都不是硬性地被分到某一个类中。
• 编辑很难给出多维度的分类，但隐含语义分析技术给出的每个分类都不是同一个维度的，它是基于用户的共同兴趣计算出来的，如果用户的共同兴趣是某一个维度，那么LFM给出的类也是相同的维度。
• 编辑很难决定一个物品在某一个分类中的权重，但隐含语义分析技术可以通过统计用户行为决定物品在每个类中的权重，如果喜欢某个类的用户都会喜欢某个物品，那么这个物品在这个类中的权重就可能比较高。

隐含语义分析技术从诞生到今天产生了很多著名的模型和方法，其中和该技术相关且耳熟能详的名词有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}^F p_{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推荐的第一个关键问题就是如何给每个用户生成负样本。 对于这个问题，Rong Pan在文章(参见“One-Class Collaborative Filtering”)中进行了深入探讨。他对比了如下几种方法。

• 对于一个用户，用他所有没有过行为的物品作为负样本。
• 对于一个用户，从他没有过行为的物品中均匀采样出一些物品作为负样本。
• 对于一个用户，从他没有过行为的物品中采样出一些物品作为负样本，但采样时，保证每个用户的正负样本数目相当。
• 对于一个用户，从他没有过行为的物品中采样出一些物品作为负样本，但采样时，偏重采样不热门的物品。

对于第一种方法，它的明显缺点是负样本太多，正负样本数目相差悬殊，因而计算复杂度很高，最终结果的精度也很差。对于另外3种方法，Rong Pan在文章中表示第三种好于第二种，而第二种好于第四种。

作者认为对负样本采样时应该遵循以下原则：

• 对每个用户，要保证正负样本的平衡（数目相似）。
• 对每个用户采样负样本时，要选取那些很热门，而用户却没有行为的物品。

下面的代码实现了负样本采样过程：

def RandomSelectNegativeSample(self, items):
    ret = dict() 
    for i in items.keys():
        ret[i] = 1 
    n = 0 
    for i in range(0, len(items) * 3): # 将上限设为len(items) * 3，主要是保证正、负样本数量接近
        item = items_pool[random.randint(0, len(items_pool) - 1)]
        if item in ret:
            continue
        ret[item] = 0
        n + = 1
        if n > len(items): 
            break 
    return ret

在上面的代码中，items_pool维护了候选物品的列表，在这个列表中，物品i出现的次数和物品i的流行度成正比。items是一个dict，它维护了用户已经有过行为的物品的集合。因此，上面的代码按照物品的流行度采样出了那些热门的、但用户却没有过行为的物品。经过采样，可以得到一个用户—物品集$K = {(u,i)}$，其中如果$(u, i)$是正样本，则有$r_{ui}$ = 1，否则有$r_{ui}$ = 0 。然后， 需要优化如下的损失函数来找到最合适的参数p和q：$$C = \sum_{(u,i) \in K} (r_{ui} - \hat r_{ui})^2 = \sum_{(u,i) \in K}(r_{ui} - \sum_{k=1}^K p_{u,k}q_{i,k})^2 + \lambda \Vert p_u \Vert^2 + \lambda \Vert q_i \Vert^2$$
这里$\lambda \Vert p_u \Vert^2 + \lambda \Vert q_i \Vert^2$用来防止过拟合的正则化项，$\lambda$可以通过实验获得。最小化上面的损失函数，可以利用随机梯度下降算法。该算法是最优化理论里最基础的优化算法，它首先通过求参数的偏导数找到最速下降方向，然后通过迭代法不断地优化参数。下面介绍优化方法的数学推导。

上面定义的损失函数里有两组参数$p_{u,k}$和$q_{i,k}$，随机梯度下降法需要首先对它们分别求偏导数，可以得到：$$\frac{\partial C}{\partial p_{uk}} = -2q_{ik} + 2\lambda p_{uk}$$ $$\frac{\partial C}{\partial q_{ik}} = -2p_{uk} + 2\lambda q_{ik}$$

然后，根据随机梯度下降法，需要将参数沿着最速下降方向向前推进，因此可以得到如下递推公式：$$p_{uk}=p_{uk} + \alpha(q_{ik}-\lambda p_{uk})$$ $$q_{ik} = q_{ik} + \alpha (p_{uk} - \lambda q_{ik})$$
其中，$\alpha$是学习速率(learning rate)，它的选取需要通过反复实验获得。

下面的Python代码实现了这一优化过程：

def LatentFactorModel(user_items, F, N, alpha, lambda):
    [P, Q] = InitModel(user_items, F) 
    for step in range(0,N):
        for user, items in user_items.items():
           samples = RandSelectNegativeSamples(items) 
            for item, rui in samples.items():
                eui = rui - Predict(user, item) 
                for f in range(0, F):
                    P[user][f] += alpha * (eui * Q[item][f] - \ lambda * P[user][f]) 
                    Q[item][f] += alpha * (eui * P[user][f] - \ lambda * Q[item][f])
        alpha *= 0.9

def Recommend(user, P, Q):
    rank = dict() 
    for f, puf in P[user].items():
        for i, qfi in Q[f].items():
            if i not in rank: 
                rank[i] += puf * qfi 
    return rank

经过离线实验评测证明，LFM确实可以实现通过用户行为将物品聚类的功能。

在LFM中，重要的参数有4个：

• 隐特征的个数F；
• 学习速率alpha；
• 正则化参数lambda；
• 负样本/正样本比例 ratio。

通过实验发现， ratio 参数对LFM的性能影响最大。随着负样本数目的增加， LFM 的准确率和召回率有明显提高。 不过当ratio>10以后，准确率和召回率基本就比较稳定了。同时，随着负样本数目的增加，覆盖率不断降低，而推荐结果的流行度不断增加，说明ratio参数控制了推荐算法发掘长尾的能力。当数据集非常稀疏时，LFM的性能会明显下降，甚至不如UserCF和ItemCF的性能。

2.5.2 基于LFM的实际系统的例子

雅虎的研究人员公布过一个使用LFM进行雅虎首页个性化设计的方案(参见Bee-Chung Chen、Deepak Agarwal、Pradheep Elango和Raghu Ramakrishnan的“Latent Factor Models for Web Recommender Systems”)。

雅虎的研究人员以CTR作为优化目标，利用LFM来预测用户是否会单击一个链接。为此， 他们将用户历史上对首页上链接的行为记录作为训练集。其中，如果用户u单击过链接i，那么就定义$(u, i)$是正样本，即$r_{ui}$ = 1。如果链接i展示给用户u，但用户u从来没有单击过，那么就定义$(u, i)$是负样本，即$r_{ui}$ = -1。然后，雅虎的研究人员利用前文提到的LFM预测用户是否会单击链接：$$\hat r_{ui} = p_u^T \cdot q_i$$

LFM模型在实际使用中有一个困难，那就是它很难实现实时的推荐。经典的LFM模型每次训练时都需要扫描所有的用户行为记录，这样才能计算出用户隐类向量$p_u$和物品隐类向量$q_i$。而且LFM的训练需要在用户行为记录上反复迭代才能获得比较好的性能。因此，LFM的每次训练都很耗时，一般在实际应用中只能每天训练一次，并且计算出所有用户的推荐结果。从而LFM模型不能因为用户行为的变化实时地调整推荐结果来满足用户最近的行为。为了解决传统LFM不能实时化，而产品需要实时性的矛盾，雅虎的研究人员提出了一个解决方案。

他们的解决方案分为两个部分。首先，他们利用新闻链接的内容属性（关键词、类别等）得到链接i的内容特征向量$y_i$。其次，他们会实时地收集用户对链接的行为，并且用这些数据得到链接i的隐特征向量$q_i$。然后，他们会利用如下公式预测用户u是否会单击链接i：$$r_{ui} = x^T_u \cdot y_i + p_u^T \cdot q_i$$

其中，$y_i$是根据物品的内容属性直接生成的，$x_{uk}$是用户u对内容特征k的兴趣程度，用户向量$x_{u}$可以根据历史行为记录获得，而且每天只需要计算一次。而$p_u$、$q_i$是根据实时拿到的用户最近几小时的行为训练LFM获得的。因此，对于一个新加入的物品i，可以通过$ x^T_u \cdot y_i$估计用户u对物品i的兴趣，然后经过几个小时后，就可以通过$p_u^T \cdot q_i$得到更加准确的预测值。

2.5.3 LFM和基于邻域的方法比较

LFM是一种基于机器学习的方法，具有比较好的理论基础。这个方法和基于邻域的方法（比如UserCF、ItemCF）相比，各有优缺点。下面将从不同的方面对比LFM和基于邻域的方法。

• 理论基础 LFM具有比较好的理论基础，它是一种学习方法，通过优化一个设定的指标建立最优的模型。基于邻域的方法更多的是一种基于统计的方法，并没有学习过程。
• 离线计算的空间复杂度 基于邻域的方法需要维护一张离线的相关表。在离线计算相关表的过程中，如果用户/物品数很多，将会占据很大的内存。假设有M个用户和N个物品，在计算相关表的过程中，我们可能会获得一张比较稠密的临时相关表（尽管最终我们对每个物品只保留K个最相关的物品，但在中间计算过程中稠密的相关表是不可避免的），那么假设是用户相关表，则需要$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)$。那么，如果$K / N > F * S$，则代表UserCF的时间复杂度低于LFM ，如果$K / M>F * S$，则说明ItemCF的时间复杂度低于LFM。在一般情况下，LFM的时间复杂度要稍微高于UserCF和ItemCF，这主要是因为该算法需要多次迭代。但总体上，这两种算法在时间复杂度上没有质的差别。
• 在线实时推荐 UserCF和ItemCF在线服务算法需要将相关表缓存在内存中，然后可以在线进行实时的预测。以ItemCF算法为例，一旦用户喜欢了新的物品，就可以通过查询内存中的相关表将和该物品相似的其他物品推荐给用户。因此，一旦用户有了新的行为， 而且该行为被实时地记录到后台的数据库系统中，他的推荐列表就会发生变化。而从LFM的预测公式可以看到，LFM在给用户生成推荐列表时，需要计算用户对所有物品的兴趣权重，然后排名，返回权重最大的N个物品。那么，在物品数很多时，这一过程的时间复杂度非常高，可达$O(M * N * F)$。因此，LFM不太适合用于物品数非常庞大的系统，如果要用，我们也需要一个比较快的算法给用户先计算一个比较小的候选列表，然后再用LFM重新排名。另一方面，LFM在生成一个用户推荐列表时速度太慢，因此不能在线实时计算，而需要离线将所有用户的推荐结果事先计算好存储在数据库中。因此，LFM不能进行在线实时推荐，也就是说，当用户有了新的行为后，他的推荐列表不会发生变化。
• 推荐解释 ItemCF算法支持很好的推荐解释，它可以利用用户的历史行为解释推荐结果。但LFM无法提供这样的解释，它计算出的隐类虽然在语义上确实代表了一类兴趣和物品，却很难用自然语言描述并生成解释展现给用户。

2.6 基于图的模型

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

在研究基于图的模型之前，首先需要将用户行为数据表示成图的形式。本章讨论的用户行为数据是由一系列二元组组成的，其中每个二元组$(u, i)$表示用户u对物品i产生过行为。
令$G(V,E)$表示用户物品二分图，其中$V = V_U \cup V_I$由用户顶点集合$V_U$和物品顶点集合$V_I$组成。对于数据集中每一个二元组$(u, i)$，图中都有一套对应的边$e(v_u,v_i)$，其中$v_u \in V_U$是用户u对应的顶点，$v_i \in V_I$是物品i对应的顶点。

2.6.2 基于图的推荐算法

如果将个性化推荐算法放到二分图模型上，那么给用户u推荐物品的任务就可以转化为度量用户顶点$v_u$和与$v_u$没有边直接相连的物品节点在图上的相关性，相关性越高的物品在推荐列表中的权重就越高。

度量图中两个顶点之间相关性的方法很多，但一般来说图中顶点的相关性主要取决于下面3个因素：

• 两个顶点之间的路径数；
• 两个顶点之间路径的长度；
• 两个顶点之间的路径经过的顶点。

而相关性高的一对顶点一般具有如下特征：

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

基于上面3个主要因素，研究人员设计了很多计算图中顶点之间相关性的方法(参见Fouss Francois、Pirotte Alain、Renders Jean-Michel和Saerens Marco的“Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation”(IEEE Transactions on Knowl edge and Data Eng ineering, 2007))。本节将介绍一种基于随机游走的PersonalRank算法(参见Taher H .Haveliwala的“Topic-Sensitive PageRank”（WWW 2002, 2002）)。

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

如果将上面的描述表示成公式，可以得到如下公式：
$$
PR(v) =
\begin{cases}
\alpha \sum_{v’ \in in(v)} \frac{PR(v’)}{\vert out(v’) \vert} & (v \neq v_u) \\
(1- alpha) + \alpha \sum_{v’ \in in(v)} \frac{PR(v’)}{\vert out(v’) \vert} & (v = v_u)
\end{cases}
$$

下面的代码简单实现了上面的公式：

def PersonalRank(G, alpha, root):
    rank = dict() 
    rank = {x:0 for x in G.keys()} 
    rank[root] = 1 
    for k in range(20):
        tmp = {x:0 for x in G.keys()}
        for i, ri in G.items():
            for j, wij in ri.items():
                if j not in tmp:
                    tmp[j] = 0 
                tmp[j] += 0.6 * rank[i] / (1.0 * len(ri)) 
                if j == root:
                    tmp[j] += 1 - alpha
        rank = tmp 
    return rank

虽然PersonalRank算法可以通过随机游走进行比较好的理论解释，但该算法在时间复杂度上有明显的缺点。因为在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，直到整个图上的每个顶点的PR值收敛。这一过程的时间复杂度非常高，不仅无法在线提供实时推荐，甚至离线生成推荐结果也很耗时。

为了解决PersonalRank每次都需要在全图迭代并因此造成时间复杂度很高的问题，给出两种解决方案。第一种就是减少迭代次数，在收敛之前就停止。这样会影响最终的精度，但一般来说影响不会特别大。另一种方法就是从矩阵论出发，重新设计算法。

对矩阵运算比较熟悉的读者可以轻松将PersonalRank转化为矩阵的形式。令M为用户物品二分图的转移概率矩阵，即：$$M(v, v’) = \frac {1}{\vert out(v) \vert}​$$
进而迭代公式可以转化为：
$$
\begin{align}
r& = (1-\alpha)r_0 + \alpha M^Tr \\
& = (1-\alpha)(1-\alpha M^T)^{-1}r_0
\end{align}
$$

因此，只需要一次$(1-\alpha M^T)^{-1}$，这里$1-\alpha M^T$是稀疏矩阵。关于如何对稀疏矩阵快速求逆，可以参考矩阵计算方面的书籍和论文(比如Song Li的“Fast Algorithms For Sparse Matrix Inverse Compuataions”（2009）)。