想要了解一个算法,最好的做好就是自己实现一遍。 前面简单讲了什么是协同过滤 ,那么在本文,将会尝试实现它。本文实现的是基于用户的协同过滤算法 ——这种算法给用户推荐和他兴趣相似的其他用户喜欢的物品。感谢《推荐系统实践》 一书的对这方面详细描述。
数据集的准备 采用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]; 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 (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 ("用户相似度计算完成...\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; 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; }
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, ×tamp) != 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 () { 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 (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 ("用户相似度计算完成...\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%。