协同过滤算法如何实现(python 协同过滤)

简介：说到ALS，我相信每个人都应该不知道。 不认识的人进来干嘛[遮住脸]。 这是一种协同过滤，集成在Spark的Mllib库中。 本文介绍了ALS的基本原理，实现了携手并肩的该算法。 原理篇我们用人的语言而不是长数学公式来谈论ALS是怎么回事。

说到ALS，谁都应该不会觉得陌生。 为什么你进来做什么[遮住脸]。 是协同过滤的一种，集成在Spark的Mllib库中。 本文介绍了ALS的基本原理，实现了携手并肩的该算法。

原理篇我们用人的语言而不是长数学公式来谈论ALS是怎么回事。

1.1你听说过推荐算法吗

如果我是豆瓣的首席执行官，很多豆瓣的用户会用豆瓣电影给电影评分。 那么，根据这个评分数据，除了这些用户自己评价过高的电影以外，你能知道你喜欢哪部电影吗？ 这就是典型的推荐问题，解决这种问题的算法称为推荐算法。

1.2什么是协同过滤

协同过滤的英文全名是Collaborative Filtering，简称CF。 请注意，这不是游戏！ 从字面上分析，协同是指寻找共同点，过滤是指筛选出优质内容。

1.3协同过滤的分类

一般来说，协同过滤建议分为三种类型。

基于用户的协同过滤，计算用户与用户的相似度，从而得到与用户a相似的用户b、c， d…，并根据向a推荐这些用户喜欢的内容的物品(item-based )的协同过滤，通过计算物品和物品的相似度来找到与物品1相似的物品2、3、4，并将这些物品推荐给看到物品1的用户主流方法可分为矩阵分解、相关算法、聚类算法、分类算法、回归算法、神经网络。 1.4基质降解

矩阵分解(decomposition，factorization )是将矩阵分解为几个矩阵的乘积。 例如豆瓣电影有m个用户，有n个电影。 那么用户对电影的评价可以形成m行n列的矩阵r，可以找到m行k列的矩阵u和k行n列的矩阵I，从U * I得到矩阵r。

1.5 ALS

如果想用矩阵分解的方法实现基于模型的协同过滤，ALS是一个很好的选择，其英文全名是Alternating Least Square，翻译起来是交替最小二乘法。 假设用户为a，项目为b，分数矩阵为r[m，n]，则可以将其分解为用户矩阵u[k，m]和项目矩阵I[k，n]。 其中m、n和k表示矩阵的维度。 前方短公式低能警告：

根据矩阵分解的定义，有

以MSE为损失函数，为了简化，将加法符号左侧的常数变更为-1/2

可以用类似于为损耗函数确定U_a的一阶偏导数并使一阶偏导数等于0的方式来证明

1.6求解用户矩阵u和物品矩阵I

矩阵r是已知的，我们随机生成用户矩阵u，

1.5的公式5，根据r和u求出I的1.5的公式6，根据r和I求出u，这样交替执行步骤1和步骤2，最终用RMSE评价模型的好坏，直到算法收敛或反复次数超过最大限制。

实现篇本人用全宇宙最简单的编程语言——Python实现ALS算法，不依赖第三方库，学习和使用方便。 简要说明实现过程，更详细的注释请参考本人github上的代码。

注意：代码中使用的矩阵类是我写的矩阵类，可以检索矩阵的行或列，并计算矩阵的乘法、倒排和逆。

2.1创建als类

初始化，存储用户ID、项目ID、用户ID与用户矩阵列号对应关系、项目ID与项目矩阵列号的对应关系、用户看到了哪个项目、得分矩阵的Shape和RMSE。

classals(object ) :

def __init__(self ) :

self.user_ids=None

self.item_ids=None

self.user_ids_dict=None

self.item_ids_dict=None

self.user_matrix=None

self.item_matrix=None

self.user_items=None

self.shape=None

self.rmse=None2.2数据预处理

处理训练数据，得到用户ID、物品ID、用户ID与用户矩阵列号的对应关系、物品ID与物品矩阵列号的对应关系、得分矩阵的Shape、得分矩阵及得分矩阵的转置。

def_process_data(self，x ) :

self.user_ids = tuple((set(map(lambda x: x[0], X)))) self.user_ids_dict = dict(map(lambda x: x[::-1], enumerate(self.user_ids))) self.item_ids = tuple((set(map(lambda x: x[1], X)))) self.item_ids_dict = dict(map(lambda x: x[::-1], enumerate(self.item_ids))) self.shape = (len(self.user_ids), len(self.item_ids)) ratings = defaultdict(lambda: defaultdict(int)) ratings_T = defaultdict(lambda: defaultdict(int)) for row in X: user_id, item_id, rating = row ratings[user_id][item_id] = rating ratings_T[item_id][user_id] = rating err_msg = "Length of user_ids %d and ratings %d not match!" % ( len(self.user_ids), len(ratings)) assert len(self.user_ids) == len(ratings), err_msg err_msg = "Length of item_ids %d and ratings_T %d not match!" % ( len(self.item_ids), len(ratings_T)) assert len(self.item_ids) == len(ratings_T), err_msg return ratings, ratings_T

2.3 用户矩阵乘以评分矩阵

实现稠密矩阵与稀疏矩阵的矩阵乘法，得到用户矩阵与评分矩阵的乘积。

def _users_mul_ratings(self, users, ratings_T): def f(users_row, item_id): user_ids = iter(ratings_T[item_id].keys()) scores = iter(ratings_T[item_id].values()) col_nos = map(lambda x: self.user_ids_dict[x], user_ids) _users_row = map(lambda x: users_row[x], col_nos) return sum(a * b for a, b in zip(_users_row, scores)) ret = [[f(users_row, item_id) for item_id in self.item_ids] for users_row in users.data] return Matrix(ret)

2.4 物品矩阵乘以评分矩阵

实现稠密矩阵与稀疏矩阵的矩阵乘法，得到物品矩阵与评分矩阵的乘积。

def _items_mul_ratings(self, items, ratings): def f(items_row, user_id): item_ids = iter(ratings[user_id].keys()) scores = iter(ratings[user_id].values()) col_nos = map(lambda x: self.item_ids_dict[x], item_ids) _items_row = map(lambda x: items_row[x], col_nos) return sum(a * b for a, b in zip(_items_row, scores)) ret = [[f(items_row, user_id) for user_id in self.user_ids] for items_row in items.data] return Matrix(ret)

2.5 生成随机矩阵

def _gen_random_matrix(self, n_rows, n_colums): data = [[random() for _ in range(n_colums)] for _ in range(n_rows)] return Matrix(data)

2.6 计算RMSE

def _get_rmse(self, ratings): m, n = self.shape mse = 0.0 n_elements = sum(map(len, ratings.values())) for i in range(m): for j in range(n): user_id = self.user_ids[i] item_id = self.item_ids[j] rating = ratings[user_id][item_id] if rating > 0: user_row = self.user_matrix.col(i).transpose item_col = self.item_matrix.col(j) rating_hat = user_row.mat_mul(item_col).data[0][0] square_error = (rating - rating_hat) ** 2 mse += square_error / n_elements return mse ** 0.5

2.7 训练模型

数据预处理

变量k合法性检查

生成随机矩阵U

交替计算矩阵U和矩阵I，并打印RMSE信息，直到迭代次数达到max_iter

保存最终的RMSE

def fit(self, X, k, max_iter=10): ratings, ratings_T = self._process_data(X) self.user_items = {k: set(v.keys()) for k, v in ratings.items()} m, n = self.shape error_msg = "Parameter k must be less than the rank of original matrix" assert k < min(m, n), error_msg self.user_matrix = self._gen_random_matrix(k, m) for i in range(max_iter): if i % 2: items = self.item_matrix self.user_matrix = self._items_mul_ratings( items.mat_mul(items.transpose).inverse.mat_mul(items), ratings ) else: users = self.user_matrix self.item_matrix = self._users_mul_ratings( users.mat_mul(users.transpose).inverse.mat_mul(users), ratings_T ) rmse = self._get_rmse(ratings) print("Iterations: %d, RMSE: %.6f" % (i + 1, rmse)) self.rmse = rmse

2.8 预测一个用户

预测一个用户感兴趣的内容，剔除用户已看过的内容。然后按感兴趣分值排序，取出前n_items个内容。

def _predict(self, user_id, n_items): users_col = self.user_matrix.col(self.user_ids_dict[user_id]) users_col = users_col.transpose items_col = enumerate(users_col.mat_mul(self.item_matrix).data[0]) items_scores = map(lambda x: (self.item_ids[x[0]], x[1]), items_col) viewed_items = self.user_items[user_id] items_scores = filter(lambda x: x[0] not in viewed_items, items_scores) return sorted(items_scores, key=lambda x: x[1], reverse=True)[:n_items]

2.9 预测多个用户

循环调用2.8，预测多个用户感兴趣的内容。

def predict(self, user_ids, n_items=10): return [self._predict(user_id, n_items) for user_id in user_ids]

3 效果评估

3.1 main函数

使用电影评分数据集，训练模型并统计RMSE。

@run_time def main(): print("Tesing the accuracy of ALS...") X = load_movie_ratings() model = ALS() model.fit(X, k=3, max_iter=5) print() print("Showing the predictions of users...") user_ids = range(1, 5) predictions = model.predict(user_ids, n_items=2) for user_id, prediction in zip(user_ids, predictions): _prediction = [format_prediction(item_id, score) for item_id, score in prediction] print("User id:%d recommedation: %s" % (user_id, _prediction))

3.2 效果展示

设置k=3，迭代5次，并展示了前4个用户的推荐内容，最终RMSE为0.370，运行时间46.5秒，效果还算不错~

点击“了解更多”获取文章使用的工具函数

关键字：算法、Python、搜索推荐