推荐系统（二）—— 基于用户行为推荐

用户行为不是随机的，而是蕴含着很多模式，这里面最著名的例子就是啤酒和尿布的例子。基于用户行为分析的推荐算法是个性化推荐系统的重要算法，学术界一般将这种类型的算法称为协同过滤算法(Collaborative Filtering, CF)。顾名思义，协同过滤就是指通过用户和网站的不断交互，齐心协力过滤掉用户不感兴趣的物品。

基于邻域的方法(neighborhood-based)

基于邻域的推荐方法是最著名的、在业界得到最广泛应用的算法。基于邻域的算法分为两大类：

1. 基于用户的协同过滤：给用户推荐和他相似的其他用户喜欢的物品
2. 基于物品的协同过滤：给用户推荐和他之前喜欢的物品相似的物品

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

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

基于用户的协同过滤主要包含两个步骤：

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

计算用户间相似度

常用的计算两个用户的兴趣相似度的方法有以下几种：

（1）Jaccard公式：

$$w_{uv}=\frac{\left | N(u)\bigcap N(v) \right |}{\left | N(u)\bigcup N(v) \right |}$$

（2）余弦相似度：

$$w_{uv}=\frac{\left | N(u)\bigcap N(v) \right |}{\sqrt{\left | N(u) \right |\left | N(v) \right |}}$$

（3）改进后的余弦相似度：两个用户都买过某个热门物品，并不能代表他们兴趣相似，因此需要惩罚热门物品对相似度的影响

$$w_{uv}=\frac{\sum_{i \in N(u)\bigcap N(v)}\frac{1}{log(1+\left | N(i) \right |)}}{\sqrt{\left | N(u) \right |\left | N(v) \right |}}$$

• $N(u)$：用户u曾经有过正反馈的物品集合；
• $N(i)$：对物品i有过正反馈的用户集合；

计算余弦相似度的Python代码：

train = {'A':set('abcd'),'B':set('bcdw'),'C':set('cdeft'),'D':set('abef')}

# 计算余弦相似度，时间复杂度O(m^2*n)，m表用户数，n表每个用户平均喜欢物品数
def similarity(train):
    """
    计算用户间兴趣的余弦相似度
    @train:{用户:喜欢的物品集合}
    @return:{u:{v:w,...]}，用户作为节点，用户间如果有相同物品，代表有边，物品数代表边的权值
    """
    W = collections.defaultdict(dict)
    for u in train.keys():
        for v in train.keys():
            if u != v:
                a = len(train[u] & train[v])
                b = (len(train[u]) * len(train[v])) ** 0.5
                cur = round(a / b if b else 0,3)
                W[u][v] = cur
    return W

similarity(train)
defaultdict(dict,
            {'A': {'B': 0.75, 'C': 0.447, 'D': 0.5},
             'B': {'A': 0.75, 'C': 0.447, 'D': 0.25},
             'C': {'A': 0.447, 'B': 0.447, 'D': 0.447},
             'D': {'A': 0.5, 'B': 0.25, 'C': 0.447}})

# 如果用户很多，而且大多数用户之间没有共同喜欢的物品时，可以通过建立物品到用户的倒查表，将代码优化到O(m*n)
def similarity(train):
    # 建立物品-用户倒查表
    item_users = collections.defaultdict(set)
    for u,items in train.items():
        for i in items:
            item_users[i].add(u)
    # 计算用户喜欢物品数、用户间公共物品数
    W = collections.defaultdict(dict)
    N = {}
    for i,users in item_users.items():
        for u in users:
            N[u] = N.get(u,0) + 1
            for v in users:
                if u != v:
                    W[u][v] = W[u].get(v,0) + 1            
    # 计算余弦相似度
    for u,vs in W.items():
        for v,cuv in vs.items():
            cur = round(W[u][v] /(N[u] * N[v]) ** 0.5,3)
            W[u][v] = cur
    return W

similarity(train)
defaultdict(dict,
            {'A': {'B': 0.75, 'C': 0.447, 'D': 0.5},
             'B': {'A': 0.75, 'C': 0.447, 'D': 0.25},
             'C': {'A': 0.447, 'B': 0.447, 'D': 0.447},
             'D': {'A': 0.5, 'B': 0.25, 'C': 0.447}})

计算用户对物品兴趣度

得到用户间的兴趣相似度后，就可以根据和目标用户u最相似的前K个用户对目标物品i的兴趣度来预测目标用户u对目标物品i的兴趣度了：

$$p(u,i)=\sum_{v \in S(u,K)}w_{uv}r_{vi}$$

• $S(u,K)$：包含和用户u兴趣最接近的K个用户
• $r_{vi}$：代表用户v对物品i的兴趣度，因为使用单一行为的隐反馈数据，所以取1

基于用户相似度为用户生成推荐列表的Python代码：

def recommend(train, user, W, k):
    rank = dict()
    u_items = train[user]
    for v,wuv in sorted(W[user].items(), key=lambda x:-x[1])[:k]:
        for i in train[v]:
            if i not in u_items:
                rank[i] = rank.get(i,0) + round(wuv, 3)
    return rank

W = similarity(train)
recommend(train, 'B', W, 3)
{'a': 1.0, 'e': 0.697, 'f': 0.697, 't': 0.447}

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

ItemCF是目前业界应用最多的算法，无论是亚马逊网，还是Netflix、Hulu、YouTube，其推荐算法的基础都是该算法。有以下两个原因使得ItemCF比UserCF更加常用：

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

ItemCF算法主要分两步：

1. 计算物品之间的相似度：ItemCF并不是通过物品属性而是通过用户历史行为来计算物品相似度，两个物品的相似度可以被定义为有多少个人同时喜欢这两个物品
2. 根据物品间的相似度和用户的历史行为为用户生成推荐列表

计算物品间的相似度

（1）亚马逊显示相关物品推荐时的标题是“Customers Who Bought This Item Also Bought”（购买了该商品的用户也经常购买的其他商品）。从这句话的定义出发，我们可以用下面的公式定义物品的相似度：

$$w_{ij}=\frac{\left | N(i) \bigcap N(j) \right |}{\left | N(i) \right |}$$

（2）余弦相似度：类似的，为了消除热门产品对产品相似度的影响，我们需要惩罚热门物品品对目标物品相似度的影响：

$$w_{ij}=\frac{\left | N(i) \bigcap N(j) \right |}{\sqrt{\left | N(i) \right | \left | N(j) \right |}}$$

• $N(i)$：对物品i有过正反馈的用户集合

和UserCF类似，我们通过建立用户到物品的倒查表，然后对每个用户，将他物品列表中的物品两两在共现矩阵中加1，python代码如下：

def similarity(train):
    """
    返回物品两两间的相似度
    @train:{用户:喜欢的物品集合}
    @return:{i:{j:w,...}物品作为节点，物品间如果有共同用户，代表有边，共同用户数代表权值
    """
    W = collections.defaultdict(dict)
    N = {}
    # 计算共现矩阵(用字典表示稀疏矩阵)
    for u, items in train.items():
        for i in items:
            N[i] = N.get(i,0) + 1
            for j in items:
                if i != j:
                    W[i][j] = W[i].get(j,0) + 1
    
    # 计算物品间的相似度
    for i in W:
        for j in W[i]:
            cur = round(W[i][j] / (N(i) * N(j)) ** 0.5, 3)
            W[i][j] = cur
    return W

计算用户对物品的兴趣度

在得到物品之间的相似度后，ItemCF 通过如下公式计算用户 u 对一个物品 i 的兴趣：

$$p(u,i)=\sum_{j \in S(i,K)\bigcap N(u)}r_{uj}w_{ji}$$

• $S(i,K)$:和物品x最相似的K个物品集合

基于物品相似度为用户生成推荐列表的Python代码：

def reconmendation(train, user, W, k):
    """
    生成用户user的推荐列表
    @train:{用户:喜欢的物品集合}
    @user:用户id
    @W:{i:{j:w,...}
    @k:推荐与用户喜欢过的每个物品最相似的前k个物品
    """
    rank = {}
    ru = train[user]
    for i in ru:
        for j,wj in sorted(W[i].items(), key=lambda x:-x[1])[:k]:
            rank[j] = rank.get(j,0) + wj
    return rank

一个简单的基于物品推荐的例子：

Karypis在研究中发现如果将ItemCF的相似度矩阵按最大值归一化，可以提高推荐的准确率和覆盖率（因为几乎所有物品与热门物品的相似度都比较高，所以归一化之前更倾向于推荐热门物品），其研究表明，如果已经得到了物品相似度矩阵w，那么可以用如下公式得到归一化之后的相似度矩阵w’：

$$w_{ij} = \frac{w_{ij}}{\underset{j}{max}\ w_{ij}}$$

对比UserCF和ItemCF

	原理	特点	适用
UserCF	给用户推荐那些和他有共同爱好的用户喜欢的物品	社会化	物品个性化程度较低，物品更多、更新更快的领域，如新闻
ItemCF	给用户推荐那些和他之前喜欢的物品类似的物品	个性化	物品个性化程度较高，用户更多、更新更快的领域，如图书、电子商务

UserCF和ItemCF算法在不同K值下的召回率曲线：

UserCF和ItemCF算法在不同K值下的覆盖率曲线：

UserCF和ItemCF算法在不同K值下的流行度曲线：

隐语义模型(latent factor model)

隐语义模型LFM（latent factor model）最早在文本挖掘领域被提出，用于找到文本的隐含语义，相关名词有LSI、pLSA、LDA和Topic Model，这些技术和方法本质上是相通的，其中很多方法都可以用于个性化推荐系统。

LFM基于隐含特征/类别联系用户和信息，通过如下公式计算用户u对物品i的兴趣：

$$p(u,i)=r_{ui}=p_{u}^Tq_{i}=\sum_{f=1}^{F}p_{uk}q_{ik}$$

• $p_{uk}$：可以看做用户u对隐含类别k的兴趣度；
• $q_{ik}$：可以看做物品i属于隐含类别k的概率；

可以通过机器学习方法训练得到这两个参数：

数据集：可以用一个用户-物品二元组(u,i)代表训练集和测试集中的样本，用u是否对i有正反馈作为标签$r{ui}$，如果用户u对i有正反馈操作，则记$r{ui}=1$，否则记$r_{ui}=0$（负样本可以通过抽样得到）。

损失函数：我们使用均方误差作为损失函数

$$L = \sum_{(u,i) \in K}(r_{ui}- \hat{r}_{ui})^2=\sum_{(u,i) \in K}(r_{ui}-\sum_{f=1}^{F}p_{uk}q_{ik})^2+\lambda \left \| p_u \right \|^2+\lambda \left \| q_i \right \|^2$$

• $\lambda \left | p_u \right |^2+\lambda \left | q_i \right |^2$：用来防止过拟合的正则化项

算法：可以通过梯度下降或你牛顿法训练出最优参数

评价：

1. LFM具有比较好的理论基础：它是一种学习方法，基于邻域的方法是一种基于统计的方法，并没有学习过程
2. 离线空间复杂度：基于邻域的方法需要维护一张离线的相关表，假设是用户相关表，那么需要的存储空间是O(MM)，假设是物品相关表，那么需要的存储空间是O(NN)；而LFM在建模过程中，如果是F个隐类，那么需要的存储空间是O(F*(M+N))，在M和N都很大时能够很好地节省离线计算内存
3. 离线时间复杂度：LFM需要多次迭代，总体上和基于邻域的方法没有本质区别
4. 推荐解释：LFM计算出的隐类在语义上确实代表了一类兴趣和物品，但很难用自然语言描述并生成解释展示给用户

基于图的随机游走(random wolk on graph)

用户-物品模型很容易用二分图表示，因此很多图的算法都可以用到推荐系统中。

二分图

令G(V,E)表示用户-物品二分图，$V=VU\bigcup V_I$由用户顶点集合和物品顶点集合组成，如果用户u对物品i有正反馈，对应顶点u和顶点i之间的一条边$e{ui}$。下图是一个简单的用户-物品二分图，其中圆形节点代表用户，方形节点代表物品，圆形节点和方形节点之间的边代表用户对物品的行为：

PersonalRank算法

用户-用户之间的相似性、用户-物品之间的兴趣度、物品-物品之间的相似性可以转化为度量顶点之间的相关性。研究人员设计了很多计算图中顶点之间相关度的方法，下面介绍一种基于随机游走的PersonalRank算法来计算用户u对物品i的相似度：

1. 初始化顶点u的概率为1，其余所有顶点的概率为0
2. 重复以下过程，直至不满足迭代条件：
   1. 从用户u节点出发进行随机游走，游走到任意节点时，按概率p决定是否继续向下游走：
      1. 如果决定向下游走，则从当前节点指向的节点中随机选择一个节点前进；
      2. 否则停止这次游走，重新从u节点出发
3. 经过很多次迭代游走之后，每个物品节点被访问的概率会收敛到一个数，将这个数作为用户u对物品i的兴趣度

通过以上过程得到用户u对每个物品i的兴趣度p(i)可以用以下公式表示：

p(i) = \left\{\begin{matrix}
p\sum_{j \in in(i)} \frac{p(j)}{\left | out(j) \right |}& j\neq i \\ 
(1-p)+p\sum_{j \in in(i)} \frac{p(j)}{\left | out(j) \right |} & j=i
\end{matrix}\right.

def personal_rank(G, p, u):
    """
    @G:图的邻接表
    @p:选择继续游走的概率
    @u:用户
    """
    rank = {x:0. for x in G.keys()}
    rank[u] = 1.
    for k in xrange(1000):
        pre = rank.copy()
        for i in G:
            for j in G[i]:
                rank[j] = p * pre[i] / len(G[i])
                if j == u:
                    rank[j] += 1- p
        rank = pre
    return rank

以上算法在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，直至收敛，这一过程时间复杂度非常高。可以将PersonalRank算法转化为矩阵运算，令M表示二分图的转移概率矩阵，即:

$$M(i,j)=\frac{1}{\left | out(i) \right |}$$

迭代公式可以写作：

$$r=(1-\alpha )r_0+\alpha M^Tr$$

得：

$$r=(1-\alpha )(1-\alpha M^T)^{-1}r_0$$

只需计算一次稀疏矩阵的逆$(1-\alpha M^T)^{-1}$。

总结

1、推荐算法的核心是计算用户u对物品i的兴趣度：

• UserCF:

$$p(u,i)=\sum_{v \in S(u,K)}w_{uv}r_{vi}$$

• ItemCF:

$$p(u,i)=\sum_{j \in S(x,K),x \in N(u)}w_{ji}r_{ui}$$

• LFM:

$$p(u,i)=r_{ui}=p_{u}^Tq_{i}=\sum_{f=1}^{F}p_{uk}q_{ik}$$

• 二分图:

$$r=(1-\alpha )r_0+\alpha M^Tr$$

2、计算A,B相似度的一般思路：一般通过A,B的某项集合属性的重叠度来度量A,B的相似度。如通过用户购买过的物品集合的重合度来度量用户间的相似度；通过物品的购买者集合的重叠度来度量物品间的相似度；通过标签下物品集合的重叠度来度量标签之间的相似度；

3、通常需要对热门物品进行惩罚，可以直接过滤掉热门物品或者除以物品的流行度；