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

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

用户行为分类

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

常用算法

基于邻域的算法

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

基于用户的协同过滤算法

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

wuv=|N(u)∩N(v)||N(u)∪N(v)|

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

wuv=|N(u)∩N(v)||N(u)||N(v)|

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

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

wAB=|{a,b,d}∩{a,c}||{a,b,d}||{a,c}|=16

wAC=|{a,b,d}∩{b,e}||{a,b,d}||{b,e}|=16

wAD=|{a,b,d}∩{c,d,e}||{a,b,d}||{c,d,e}|=13

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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)=∑v∈S(u,K)∩N(i)wuvrvi

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

具体的逻辑实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def recommend(user, users, w, k):
    """
    :param user: 计算指定用户的物品推荐程度
    :param users: 数据集
    :param w: 前一步计算得到的用户兴趣相似度
    :param k: 取k个兴趣最相似的用户
    :return:
    """
    rank = defaultdict(float)
    
    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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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)
    
    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。

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

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

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

基于物品的协同过滤算法

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

wij=|N(i)∩N(j)||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  |

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

number = 'number'
def item_similarity(train):
    
    
    c = defaultdict(lambda: defaultdict(int))
    for user, items in train.items():
        for i in items:
            
            c[i][number] += 1
            
            for j in items:
                if i == j:
                    continue
                c[i][j] += 1
    
    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的兴趣

puj=∑i∈N(u)∩S(j,K)wjirui

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def recommend(interacted_items: Union[set, dict], w, k):
    """
    :param interacted_items: 指定用户交互过的物品
    :param w: 物品的相似度
    :param k: 取最相似的k个物品
    :return:
    """
    if isinstance(interacted_items, set):  
        interacted_items = {k: 1 for k in interacted_items}
    rank = defaultdict(float)
    
    for item, score in interacted_items.items():
        
        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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

import math
from collections import defaultdict
from typing import Union

number = 'number'


def item_similarity(train):
    
    
    c = defaultdict(lambda: defaultdict(int))
    for user, items in train.items():
        for i in items:
            
            c[i][number] += 1
            
            for j in items:
                if i == j:
                    continue
                c[i][j] += 1

    
    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):  
        interacted_items = {k: 1 for k in interacted_items}
    rank = defaultdict(float)
    
    for item, score in interacted_items.items():
        
        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)联系用户兴趣和物品，它可以通过对数据进行分类来实现推荐。这种基于用户对数据的兴趣分类的方式，需要解决如下三个问题：

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

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

评测指标

一个推荐系统好不好，可以从用户满意度、预测准确度、覆盖率、多样性、新颖性、惊喜度、信任度、实时性、健壮性、商业目标等多个角度来进行评测

准确度

我们可以使用TopN推荐的方式来计算准确度，TopN的准确度一般通过准确率（precision）/召回率（recall）来进行度量。令R(u)是根据用户在训练集上的行为给用户作出的推荐列表，而T(u)是用户在测试集上的行为列表。那么，推荐结果的召回率定义为：

Recall=∑u∈U|R(u)∩T(u)|∑u∈U|T(u)|

推荐结果的准确率定义为：

Precision=∑u∈U|R(u)∩T(u)|∑u∈U|R(u)|

简单来说，R(u)代表系统推荐给用户u的Top-N列表（预测值），T(u)代表用户实际喜欢或点击过的项目（真实值），召回率和准确率公式的分子都是同时存在于推荐列表和用户喜欢列表的物品数。召回率的分母是用户喜欢的物品数，召回率是看系统有没有把用户喜欢的物品推荐出来。准确率的分母是系统推荐的物品总数，目的是看推荐有多少是对的。

我们可以把召回率和准确率的计算通过如下代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def precision_recall(test_data, train_data, n, recommend_func):
    """
    计算推荐系统在测试集上的准确率和召回率

    :param test_data: dict，用户 -> 测试集中真实交互物品列表
    :param train_data: dict，用户 -> 训练集中交互物品列表（用于生成推荐）
    :param n: int，每个用户推荐的物品数量
    :param recommend_func: function(user, n, train_data)，返回推荐物品列表
    :return: [recall, precision]
    """
    hit = 0  
    total_actual = 0  
    total_recommend = 0  

    for user, actual_items in test_data.items():
        
        recommended_items = recommend_func(user, n, train_data)
        
        hit += len(set(recommended_items) & set(actual_items))
        
        total_actual += len(actual_items)
        
        total_recommend += len(recommended_items)

    recall = hit / total_actual if total_actual else 0
    precision = hit / total_recommend if total_recommend else 0
    return [recall, precision]

参考

推荐系统实践