想要了解一个算法，最好的做好就是自己实现一遍。前面简单讲了什么是协同过滤，那么在本文，将会尝试实现它。本文实现的是基于用户的协同过滤算法 ——这种算法给用户推荐和他兴趣相似的其他用户喜欢的物品。感谢《推荐系统实践》一书的对这方面详细描述。


数据集的准备

采用GroupLens提供的MovieLens数据集。MovieLens数据集有3个不同的版本，这里采用中等大小的数据集。该数据集包含6000多用户对4000多部电影的100万条评分。该数据集是一个评分数据集，用户可以给电影评5个不同等级的分数(1~5分)。数据集下载地址

解压后可以看到以下文件

数据集


算法实现

1、求用户的相似度

通过余弦相似度公式计算，给定用户u和用户v，令N(u)表示用户u曾经有过正反馈的物品集合，令N(v)
为用户v曾经有过正反馈的物品集合。


用下图举例说明UserCF计算用户兴趣相似度的例子。在该例中，用户A对物品{a, b, d}有过行为，用户B对物品{a, c}有过行为，

图片来源于《推荐系统实战》

利用余弦相似度公式计算用户A和用户B的兴趣相似度为:

实际上，很多用户相互之间并没有对同样的物品产生过行为，所以公式中的 $|N(u) \cap N(v)|$ 大多数时候为0。因此我们可以先找出$|N(u) \cap N(v)| \ne 0$ 的用户对，然后再做计算。

相关实现如下：

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
void calc_user_sim() {
        set<int> C[usernum]; // 两个用户有看过同一部电影
        map<int, int> C_count[usernum]; // 记录两个用户共同看的电影数，即|N(u) \cap N(v)|
        int N[usernum]; // 用户看过的电影数目
        memset(N, 0, sizeof N);
        // 计算两个用户之间看过的相同电影，计算与当前用户u看过同一部电影的其他用户v
        for (auto movie : movies) {
            for (auto u : movie2user[movie]) { // movie2user指的是看过这部电影的用户有哪些
                N[u]++;
                for (auto v : movie2user[movie]) {
                    if (u == v) continue;
                    C[u].insert(v);
                    C_count[u][v]++;
                }   
            }
        }
        // 计算用户相似度
        for (int u = 1; u < usernum; u++) {
            for (auto related_user : C[u]) {
                W[u][related_user] = C_count[u][related_user]*1.0 / sqrt(N[u]*N[related_user]);
                // printf("%d %d %lf\n", u, related_user, W[u][related_user]);
            }
        }
        printf("用户相似度计算完成...\n");
    }


2、计算推荐

得到用户的相似度之后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。下面的公式度量了UserCF算法中用户u对物品i的感兴趣程度:

其中，$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
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
vector<pair<int, double> > recommend(int userId) {
        int K = 0;

        map<int, double> tmp_rank; // 计算中间的计算过程，保存的是p(u, i)
        vector<pair<int, double> > rnk; // 最后的返回数组

        vector<pair<int, double> > k_sim_users;
        set<int> watched_movies;

        for (auto val : trainset[userId])
            watched_movies.insert(val.first);
		
    	// 这里做的是map按value从大到小排序操作，得到前k个相似用户
        for (auto it = W[userId].begin(); it != W[userId].end(); it++) {
            k_sim_users.push_back(make_pair(it->first, it->second));
        }
        sort(k_sim_users.begin(), k_sim_users.end(), 
            [](const pair<int, double> &x, const pair<int, double> &y) -> double {
                return x.second > y.second;
            });


        for (auto it = k_sim_users.begin(); K < n_sim_user && it != k_sim_users.end(); it++) {
            int similar_user = it->first;
            double similarity_factor = it->second;
            for (auto movie : trainset[similar_user]) {
                if (watched_movies.find(movie.first) != watched_movies.end())
                    continue;
				// 计算p(u, i)
                tmp_rank[movie.first] += similarity_factor;
            }
            K++;
        }

        for (auto it : tmp_rank) {
            rnk.push_back(make_pair(it.first, it.second));
        }

        sort(rnk.begin(), rnk.end(), 
            [](const pair<int, double> &x, const pair<int, double> &y) -> double {
                return x.second > y.second;
            });
        printf("推荐列表前 %d 项已生成...\n", n_rec_movie);
        return rnk;

    }


3、得到推荐列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
数据集分割成功...
训练集大小: 700387, 测试集大小: 299822
训练集电影数: 3649, 训练集用户数: 6040
用户相似度计算完成...

推荐列表前 10 项已生成...
推荐给用户 23 的电影:
电影编号    推荐系数
    110 2.673651
   1573 2.673130
   3471 2.672973
   1210 2.668150
   3702 2.346376
    356 2.345560
   3527 2.344213
    527 2.328069
   1610 2.328069
   1387 2.327529

总用时: 258.973253s


完整代码

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <map>
#include <math.h>
#include <vector>
#include <time.h>
#include <string>
#include <set>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;

#define Node pair<int, int> 
#define usernum 7000
#define movienum 200000

class UserBaseCF {
public:
    UserBaseCF() {}

    void test() {
        clock_t start, stop;
        start = clock();
        generate_dataset("", 7); // 这里填入数据文件地址
        calc_user_sim();
        std::vector<pair<int, double> > v = recommend(23); 
        stop = clock();
        printf("推荐给用户 23 的电影:\n");
        printf("电影编号    推荐系数\n");
        for (int i = 0; i < n_rec_movie; i++)
            printf("%7d %lf\n", v[i].first, v[i].second);

        printf("\n总用时: %fs\n", (double)(stop-start)/CLOCKS_PER_SEC);

    }

private:
    vector<Node> trainset[usernum];
    vector<Node> testset[usernum];

    int n_sim_user = 10;    // 相似用户数
    int n_rec_movie = 10;   // 推荐电影数

    set<int> users;
    set<int> movies;
    set<int> movie2user[movienum];

    map<int, double> W[usernum];

protected:
    void generate_dataset(const char* filename, int k) {
        FILE* fp = fopen(filename, "rt");
        int userId, movieId, timestamp;
        double rating;

        int train_len, test_len;

        train_len = test_len = 0;

        srand(time(0));

        while (fscanf(fp, "%d::%d::%lf::%d", &userId, &movieId, &rating, &timestamp) != EOF) {
            if (rand()%10 < k) {
                users.insert(userId);
                movies.insert(movieId);

                // 电影-用户倒排表
                movie2user[movieId].insert(userId);

                trainset[userId].push_back(make_pair(movieId, rating));
                train_len++;
            } else {
                testset[userId].push_back(make_pair(movieId, rating));
                test_len++;
            }
        }

        printf("数据集分割成功...\n");
        printf("训练集大小: %d, 测试集大小: %d\n", train_len, test_len);
        printf("训练集电影数: %lu, 训练集用户数: %lu\n", movies.size(), users.size());

        fclose(fp);
    }

    void calc_user_sim() {

        // for (auto movie : movies) {
        //     printf("%d:", movie);
        //     for (auto i : movie2user[movie]) 
        //         printf("%d ", i);
        //     printf("\n");
        // }

        set<int> C[usernum]; // 两个用户有看过同一部电影
        map<int, int> C_count[usernum]; // 记录两个用户共同看的电影数
        int N[usernum]; // 用户看过的电影数目
        memset(N, 0, sizeof N);

        for (auto movie : movies) {
            for (auto u : movie2user[movie]) {
                N[u]++;
                for (auto v : movie2user[movie]) {
                    if (u == v) continue;
                    C[u].insert(v);
                    C_count[u][v]++;
                }   
            }
        }

        // for (auto i : users) {
        //     printf("%d:", i);
        //     for (auto j : C[i]) {
        //         printf("%d ", j);
        //     }
        //     printf("\n");
        // }

        for (int u = 1; u < usernum; u++) {
            for (auto related_user : C[u]) {
                W[u][related_user] = C_count[u][related_user]*1.0 / sqrt(N[u]*N[related_user]);
                // printf("%d %d %lf\n", u, related_user, W[u][related_user]);
            }
        }
        printf("用户相似度计算完成...\n");
    }


    vector<pair<int, double> > recommend(int userId) {
        int K = 0;

        map<int, double> tmp_rank;
        vector<pair<int, double> > rnk;

        vector<pair<int, double> > k_sim_users;
        set<int> watched_movies;

        for (auto val : trainset[userId])
            watched_movies.insert(val.first);

        for (auto it = W[userId].begin(); it != W[userId].end(); it++) {
            k_sim_users.push_back(make_pair(it->first, it->second));
        }

        sort(k_sim_users.begin(), k_sim_users.end(), 
            [](const pair<int, double> &x, const pair<int, double> &y) -> double {
                return x.second > y.second;
            });


        for (auto it = k_sim_users.begin(); K < n_sim_user && it != k_sim_users.end(); it++) {
            int similar_user = it->first;
            double similarity_factor = it->second;
            for (auto movie : trainset[similar_user]) {
                if (watched_movies.find(movie.first) != watched_movies.end())
                    continue;

                tmp_rank[movie.first] += similarity_factor;
            }
            K++;
        }

        for (auto it : tmp_rank) {
            rnk.push_back(make_pair(it.first, it.second));
        }

        sort(rnk.begin(), rnk.end(), 
            [](const pair<int, double> &x, const pair<int, double> &y) -> double {
                return x.second > y.second;
            });
        printf("推荐列表前 %d 项已生成...\n", n_rec_movie);
        return rnk;

    }

};

int main(int argc, char const *argv[])
{
    UserBaseCF *test = new UserBaseCF();
    test->test();
    return 0;
}


写在最后

在这里，我用的是c++语言实现，其中有很多的不足之处，欢迎大家指出。如果觉得这份c++代码实现的UserCF不好理解，可以看看python实现的UserCF。

实际中的UserCF实现要复杂很多。除此之外，还有ItemCF，算法过程差不多，这里就不做实现了。

评价一个推荐算法的好坏可以通过以下指标：

  • 对用户u推荐N个物品(记为R(u))，令用户u在测试集上喜欢的物品集合为T(u)，然后可以通

    过准确率/召回率评测推荐算法的精度:

    召回率描述有多少比例的用户—物品评分记录包含在最终的推荐列表中，而准确率描述最终
    的推荐列表中有多少比例是发生过的用户—物品评分记录

  • 覆盖率反映了推荐算法发掘长尾的能力，覆盖率越高，说明推荐算法越能够将长尾中的物品推荐给用户。

    覆盖率表示最终的推荐列表中包含多大比例的物品。如果所有的物品都被推荐给至少一个用户，那么覆盖率就是100%。