《推荐系统实践》

从某种意义上说，推荐系统和搜索引擎对于用户来说是两个互补的工具。搜索引擎满足了用户有明确目的时的主动查找需求，而推荐系统能够在用户没有明确目的的时候帮助他们发现感兴趣的新内容。

基于用户行为分析的推荐算法是个性化推荐系统的重要算法，学术界一般将这种类型的算法称为协同过滤（Collaborative filtering）算法。顾名思义，协同过滤就是指用户可以齐心协力，通过不断地和网站互动，使自己的推荐列表能够不断过滤掉自己不感兴趣的物品，从而越来越满足自己的需求。

用户行为分类

用户行为在个性化推荐系统中一般分两种——显性反馈行为（explicit feedback）和隐性反馈行为（implicit feedback）。显示反馈行为是用户主动做的，比如给视频点赞、给书籍打分等等；隐式反馈行为的代表就是用户浏览页面，这种行为显示出来的用户偏好不是那么明显，但是数据量更大。

常用算法

基于邻域的算法

基于用户的协同过滤算法这种算法给用户推荐和他兴趣相似的其他用户喜欢的物品。
1. 找到和目标用户兴趣相似的用户集合（P45）。
2. 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户。
基于物品的协同过滤算法这种算法给用户推荐和他之前喜欢的物品相似的物品。
1. 计算物品之间的相似度（P53）。
2. 根据物品的相似度和用户的历史行为给用户生成推荐列表。

基于用户的协同过滤算法

计算两个用户的兴趣相似程度：给定用户u和用户v，N(u)表示用户u曾经有过正反馈的物品集合，N(v)表示用户v曾经有过正反馈的物品集合。可以使用Jaccard公式计算两个用户的兴趣相似程度

$w_{u v} = \frac{| N (u) \cap N (v) |}{| N (u) \cup N (v) |}$

或者使用余弦相似公式计算相似程度

$w_{u v} = \frac{| N (u) \cap N (v) |}{\sqrt{| N (u) | | N (v) |}}$

以余弦相似公式为例，假设有用户ABCD，物品abcde，用户喜欢的物品如下

用户	物品 a	物品 b	物品 c	物品 d	物品 e
A	☑️	☑️		☑️
B	☑️		☑️
C		☑️			☑️
D			☑️	☑️	☑️

那么我们可以得到用户A和BCD的相似度

$w_{A B} = \frac{| {a, b, d} \cap {a, c} |}{\sqrt{| {a, b, d} | | {a, c} |}} = \frac{1}{\sqrt{6}}$

$w_{A C} = \frac{| {a, b, d} \cap {b, e} |}{\sqrt{| {a, b, d} | | {b, e} |}} = \frac{1}{\sqrt{6}}$

$w_{A D} = \frac{| {a, b, d} \cap {c, d, e} |}{\sqrt{| {a, b, d} | | {c, d, e} |}} = \frac{1}{3}$

具体计算过程以AD的相似度计算为例

分子为交集并且交集为 {d}，|{d}| = 1，所以分子为1
分母为并集，3 x 3 = 9，开根号为3
最终值为 1 / 3

以上逻辑可以用代码进行实现：

def similarity(users):
    w = defaultdict(dict)
    for u, v in combinations(users.keys(), 2):
        r1 = len(users[u] & users[v])
        r2 = math.sqrt(len(users[u]) * len(users[v]) * 1.0)
        r = r1 / r2
        w[u][v], w[v][u] = r, r  # 保存两次，方便后面使用
    return w

def main():
    users = {
        'A': {'a', 'b', 'd'},
        'B': {'a', 'c'},
        'C': {'b', 'e'},
        'D': {'c', 'd', 'e'}
    }
    for k, v in similarity(users).items():
        print(f'{k}: {json.dumps(v)}')

执行后得到结果如下

A: {"B": 0.4082482904638631, "C": 0.4082482904638631, "D": 0.3333333333333333}
B: {"A": 0.4082482904638631, "C": 0.0, "D": 0.4082482904638631}
C: {"A": 0.4082482904638631, "B": 0.0, "D": 0.4082482904638631}
D: {"A": 0.3333333333333333, "B": 0.4082482904638631, "C": 0.4082482904638631}

据此我们就可以得到各个用户之间的兴趣相似度了。有了用户兴趣的相似度之后，我们可以给用户推荐和他兴趣最相似的K个用户喜欢的物品。我们可以使用如下公式计算用户u对物品i的感兴趣程度

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

其中，S(u, K)包含和用户u兴趣最接近的K个用户，N(i)是对物品i有过行为的用户集合，w_uv是用户u和用户v的兴趣相似度，r_vi代表用户v对物品i的兴趣，因为使用的是单一行为的隐反馈数据，所以所有的r_vi=1。

具体的逻辑实现如下：

def recommend(user, users, w, k):
    """
    :param user: 计算指定用户的物品推荐程度
    :param users: 数据集
    :param w: 前一步计算得到的用户兴趣相似度
    :param k: 取k个兴趣最相似的用户
    :return:
    """
    rank = defaultdict(float)
    # 获取指定用户和其它用户的兴趣相似度，并按照相似度从大到小排序，取前k个数据
    for v, wuv in sorted(w[user].items(), key=lambda item: item[1], reverse=True)[:k]:
        # 取出指定用户的数据集
        for i in users[v]:
            # 如果这个数据已经在当前用户的数据集里面，跳过，因为已经感兴趣的数据不需要再次推荐
            if i in users[user]:
                continue
            rank[i] += wuv
    return rank

通过这个代码我们就可以计算得到指定用户的物品推荐程度了。完整的代码如下：

import json
import math
from collections import defaultdict
from itertools import combinations


def similarity(users):
    w = defaultdict(dict)
    for u, v in combinations(users.keys(), 2):
        r1 = len(users[u] & users[v])
        r2 = math.sqrt(len(users[u]) * len(users[v]) * 1.0)
        r = r1 / r2
        w[u][v], w[v][u] = r, r  # 保存两次，方便后面使用
    return w


def recommend(user, users, w, k):
    """
    :param user: 计算指定用户的物品推荐程度
    :param users: 数据集
    :param w: 前一步计算得到的用户兴趣相似度
    :param k: 取k个兴趣最相似的用户
    :return:
    """
    rank = defaultdict(float)
    # 获取指定用户和其它用户的兴趣相似度，并按照相似度从大到小排序，取前k个数据
    for v, wuv in sorted(w[user].items(), key=lambda item: item[1], reverse=True)[:k]:
        # 取出指定用户的数据集
        for i in users[v]:
            # 如果这个数据已经在当前用户的数据集里面，跳过，因为已经感兴趣的数据不需要再次推荐
            if i in users[user]:
                continue
            rank[i] += wuv
    return rank


def main():
    users = {
        'A': {'a', 'b', 'd'},
        'B': {'a', 'c'},
        'C': {'b', 'e'},
        'D': {'c', 'd', 'e'}
    }

    w = similarity(users)
    for k, v in w.items():
        print(f'{k}: {json.dumps(v)}')

    rank = recommend('C', users, w, 3)
    for k, v in sorted(rank.items(), key=lambda item: item[1], reverse=True):
        print(f'{k}: {v}')


if __name__ == '__main__':
    main()

执行代码得到的结果如下

A: {"B": 0.4082482904638631, "C": 0.4082482904638631, "D": 0.3333333333333333}
B: {"A": 0.4082482904638631, "C": 0.0, "D": 0.4082482904638631}
C: {"A": 0.4082482904638631, "B": 0.0, "D": 0.4082482904638631}
D: {"A": 0.3333333333333333, "B": 0.4082482904638631, "C": 0.4082482904638631}
d: 0.8164965809277261
a: 0.4082482904638631
c: 0.4082482904638631

由上面的结果我们可以知道，针对用户C，最推荐的物品是物品d。

根据上面的例子我们已经简单了解了基于用户的协同过滤算法，不过这种算法存在问题，主要是

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

因此，在实际的使用中，更常见的是基于物品的协同过滤算法

基于物品的协同过滤算法

为了挖掘长尾信息，避免热门物品对推荐产生影响，减小二八定律的出现。可以用如下公式计算物品之间的相似度

$w_{i j} = \frac{| N (i) \cap N (j) |}{\sqrt{| N (i) | | N (j) |}}$

分子是同时喜欢物品i和物品j的用户数，分母是喜欢两个物品用户数的并集。为了减小计算量，我们可以构建一个矩阵来存储某个用户喜欢的物品集合。

举个例子，比如用户A喜欢物品 {a, b, d}，那我们可以构建如下矩阵

    |  a  |  b  |  c  |  d  |  e  |
----|-----|-----|-----|-----|-----|
a   |  0  |  1  |  0  |  1  |  0  |
b   |  1  |  0  |  0  |  1  |  0  |
c   |  0  |  0  |  0  |  0  |  0  |
d   |  1  |  1  |  0  |  0  |  0  |
e   |  0  |  0  |  0  |  0  |  0  |

因为a、b、d可以组成ab、ad、bd，所以将矩阵中的对应位置都填上1。这是一个用户的物品信息，对于多个用户，只需要把这些矩阵相加即可。例如有5个用户，他们的物品信息和生成的对应物品矩阵如下

用户 1: {a, c, d}

    |  a  |  b  |  c  |  d  |  e  |
----|-----|-----|-----|-----|-----|
a   |  0  |  0  |  1  |  1  |  0  |
b   |  0  |  0  |  0  |  0  |  0  |
c   |  1  |  0  |  0  |  1  |  0  |
d   |  1  |  0  |  1  |  0  |  0  |
e   |  0  |  0  |  0  |  0  |  0  |

用户 2: {b, c, e}

    |  a  |  b  |  c  |  d  |  e  |
----|-----|-----|-----|-----|-----|
a   |  0  |  0  |  0  |  0  |  0  |
b   |  0  |  0  |  1  |  0  |  1  |
c   |  0  |  1  |  0  |  0  |  1  |
d   |  0  |  0  |  0  |  0  |  0  |
e   |  0  |  1  |  1  |  0  |  0  |

用户 3: {a, d, e}

    |  a  |  b  |  c  |  d  |  e  |
----|-----|-----|-----|-----|-----|
a   |  0  |  0  |  0  |  1  |  1  |
b   |  0  |  0  |  0  |  0  |  0  |
c   |  0  |  0  |  0  |  0  |  0  |
d   |  1  |  0  |  0  |  0  |  1  |
e   |  1  |  0  |  0  |  1  |  0  |

用户 4: {b, d}

    |  a  |  b  |  c  |  d  |  e  |
----|-----|-----|-----|-----|-----|
a   |  0  |  0  |  0  |  0  |  0  |
b   |  0  |  0  |  0  |  1  |  0  |
c   |  0  |  0  |  0  |  0  |  0  |
d   |  0  |  1  |  0  |  0  |  0  |
e   |  0  |  0  |  0  |  0  |  0  |

用户 5: {a, b, c, e}

    |  a  |  b  |  c  |  d  |  e  |
----|-----|-----|-----|-----|-----|
a   |  0  |  1  |  1  |  0  |  1  |
b   |  1  |  0  |  1  |  0  |  1  |
c   |  1  |  1  |  0  |  0  |  1  |
d   |  0  |  0  |  0  |  0  |  0  |
e   |  1  |  1  |  1  |  0  |  0  |

将这5个用户的物品信息相加，得到矩阵

    |  a  |  b  |  c  |  d  |  e  |
----|-----|-----|-----|-----|-----|
a   |  0  |  1  |  2  |  3  |  2  |
b   |  1  |  0  |  3  |  2  |  3  |
c   |  2  |  3  |  0  |  2  |  3  |
d   |  3  |  2  |  2  |  0  |  2  |
e   |  2  |  3  |  3  |  2  |  0  |

在这个矩阵中值越高，代表物品的相关度越高。接下来我们将这个规则用代码进行实现

number = 'number'
def item_similarity(train):
    # c[i][number]表示使用物品i的用户数量
    # c[i][j]表示同时交互物品i和j的用户数
    c = defaultdict(lambda: defaultdict(int))
    for user, items in train.items():
        for i in items:
            # 统计每个物品被交互的总次数
            c[i][number] += 1
            # 统计物品i与其他物品的共现次数
            for j in items:
                if i == j:
                    continue
                c[i][j] += 1
    # 计算最终的相似度矩阵 w
    w = defaultdict(dict)
    for i, related_items in c.items():
        for j, cij in related_items.items():
            if j == number: continue
            # 余弦相似度公式
            similarity = cij / math.sqrt(c[i][number] * c[j][number])
            w[i][j] = similarity
    return w

如上我们先计算每个物品各自被用户喜欢的次数，再计算每个物品和其它物品同时被某个用户喜欢的次数，之后根据物品相似度公式即可计算出物品之间的相关性。为了简单起见，如上代码只使用了一个字典变量，物品自己被喜欢的次数被保存在key为number的字段中，物品和其它物品同时被喜欢的次数则保存在key为其它物品ID的字段中。

有了如上逻辑之后，我们就可以计算物品相似度了，假设有用户如下

{
  'A': {'a', 'b', 'd'},
  'B': {'a', 'c'},
  'C': {'b', 'e', 'a'},
  'D': {'c', 'd', 'e'}
}

计算得到的物品相似度

b: {'a': 0.8164965809277261, 'd': 0.5, 'e': 0.5}
a: {'b': 0.8164965809277261, 'd': 0.4082482904638631, 'c': 0.4082482904638631, 'e': 0.4082482904638631}
d: {'b': 0.5, 'c': 0.5, 'e': 0.5, 'a': 0.4082482904638631}
c: {'e': 0.5, 'd': 0.5, 'a': 0.4082482904638631}
e: {'b': 0.5, 'c': 0.5, 'd': 0.5, 'a': 0.4082482904638631}

可以看到物品a和物品b的相关度是最高的。在得到物品的相关度之后，我们可以使用如下公式计算用户u对一个物品j的兴趣

$p_{u j} = \sum_{i \in N (u) \cap S (j, K)} w_{j i} r_{u i}$

N(u)是用户喜欢的物品集合，S(j, K)是物品j最相似的K个物品的集合，w_ji是物品j和i的相似度，r_ui是用户对物品i的兴趣，可令r_ui为1。我们可以把这个逻辑使用代码进行实现

def recommend(interacted_items: Union[set, dict], w, k):
    """
    :param interacted_items: 指定用户交互过的物品
    :param w: 物品的相似度
    :param k: 取最相似的k个物品
    :return:
    """
    if isinstance(interacted_items, set):  # 如果只有物品，没有评分，那么将评分统一设置为1
        interacted_items = {k: 1 for k in interacted_items}
    rank = defaultdict(float)
    # 用户交互过的物品，和用户对这个物品的评分
    for item, score in interacted_items.items():
        # 物品的相似度信息，得到related_item和item的相似度similarity，按照相似度的值从大到小排序，取k个值
        for related_item, similarity in sorted(w[item].items(), key=lambda x: x[1], reverse=True)[:k]:
            # 如果这个物品已经被用户交互过了，跳过
            if related_item in interacted_items:
                continue
            # 计算相关的物品的相似度评分
            rank[related_item] += score * similarity
    return rank

有了计算用户和物品相关度的代码，我们就可以把逻辑结合起来，实现向用户推荐物品了。完整的代码实现如下

import math
from collections import defaultdict
from typing import Union

number = 'number'


def item_similarity(train):
    # c[i][number]表示使用物品i的用户数量
    # c[i][j]表示同时交互物品i和j的用户数
    c = defaultdict(lambda: defaultdict(int))
    for user, items in train.items():
        for i in items:
            # 统计每个物品被交互的总次数
            c[i][number] += 1
            # 统计物品i与其他物品的共现次数
            for j in items:
                if i == j:
                    continue
                c[i][j] += 1

    # 计算最终的相似度矩阵 w
    w = defaultdict(dict)
    for i, related_items in c.items():
        for j, cij in related_items.items():
            if j == number: continue
            # 余弦相似度公式
            similarity = cij / math.sqrt(c[i][number] * c[j][number])
            w[i][j] = similarity

    return w


def recommend(interacted_items: Union[set, dict], w, k):
    """
    :param interacted_items: 指定用户交互过的物品
    :param w: 物品的相似度
    :param k: 取最相似的k个物品
    :return:
    """
    if isinstance(interacted_items, set):  # 如果只有物品，没有评分，那么将评分统一设置为1
        interacted_items = {k: 1 for k in interacted_items}
    rank = defaultdict(float)
    # 用户交互过的物品，和用户对这个物品的评分
    for item, score in interacted_items.items():
        # 物品的相似度信息，得到related_item和item的相似度similarity，按照相似度的值从大到小排序，取k个值
        for related_item, similarity in sorted(w[item].items(), key=lambda x: x[1], reverse=True)[:k]:
            # 如果这个物品已经被用户交互过了，跳过
            if related_item in interacted_items:
                continue
            # 计算相关的物品的相似度评分
            rank[related_item] += score * similarity
    return rank


def main():
    users = {
        'A': {'a', 'b', 'd'},
        'B': {'a', 'c'},
        'C': {'b', 'e', 'a'},
        'D': {'c', 'd', 'e'}
    }
    w = item_similarity(users)
    for k, v in w.items():
        print(f'{k}: {dict(sorted(v.items(), key=lambda item: item[1], reverse=True))}')

    rank = recommend(users['B'], w, 3)
    for k, v in sorted(rank.items(), key=lambda item: item[1], reverse=True):
        print(f'{k}: {v}')


if __name__ == '__main__':
    main()

以上代码的执行结果如下，可见用户B和物品d的相关度最高

b: {'a': 0.8164965809277261, 'd': 0.5, 'e': 0.5}
d: {'b': 0.5, 'c': 0.5, 'e': 0.5, 'a': 0.4082482904638631}
a: {'b': 0.8164965809277261, 'd': 0.4082482904638631, 'c': 0.4082482904638631, 'e': 0.4082482904638631}
c: {'d': 0.5, 'e': 0.5, 'a': 0.4082482904638631}
e: {'b': 0.5, 'c': 0.5, 'd': 0.5, 'a': 0.4082482904638631}
d: 0.9082482904638631
b: 0.8164965809277261
e: 0.5

基于物品的推荐在工程中使用的比基于用户的推荐要多，因为UserCF（User Collaborative Filtering）的推荐更社会化，反映了用户所在的小型兴趣群体中物品的热门程度，而ItemCF（Item Collaborative Filtering）的推荐更加个性化，反映了用户自己的兴趣传承。

LFM（latent factor model）隐语义模型

隐语义模型核心思想是通过隐含特征(latent factor)联系用户兴趣和物品，它可以通过对数据进行分类来实现推荐。这种基于用户对数据的兴趣分类的方式，需要解决如下三个问题：

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

隐含语义分析技术（latent variable analysis）采取基于用户行为统计的自动聚类，来实现数据自动分类。

用户行为分类

常用算法

基于邻域的算法

基于用户的协同过滤算法

基于物品的协同过滤算法

LFM（latent factor model）隐语义模型

基于图的模型

冷启动：如何向刚刚注册的用户进行推荐

标签系统

利用上下文进行推荐