【推荐系统入门到项目实战】（三）：矩阵分解和ALS算法

• 🌸个人主页：JOJO数据科学
• 📝个人介绍：统计学top3高校统计学硕士在读
• 💌如果文章对你有帮助，欢迎✌关注、👍点赞、✌收藏、👍订阅专栏
• ✨本文收录于【推荐系统入门到项目实战】本系列主要分享一些学习推荐系统领域的方法和代码实现。

@[toc]

引言

之前我们介绍了推荐系统的基础框架。了解了基础的推荐系统算法。我们首先来回顾一下推荐算法的常见方法。主要分为两大类

• 1.基于内容的推荐
• 2.基于协同过滤的推荐

而基于协同过滤的推荐是推荐系统的主流思想之一。其中矩阵分解是一个重要的模块。本文我们来讨论一下矩阵分解ALS的原理与实现。

在正式介绍矩阵分解之前，我们先来讨论一下一些基础的问题

什么是隐语义模型：

用户与物品之间存在着某些隐含的联系。通过隐含特征（Latent Factor） 联系用户兴趣和物品，基于用户行为的自动聚类。我们可以指定隐特征的个数，粒度可粗（隐特征少），可细（隐特征多）。计算物品属于每个隐特征的权重，但是可解释性差。

有了基础的前置知识，我们来看看正式来看看矩阵分解吧

矩阵分解（MF）

首先，我们的目标是：为用户找到其感兴趣的item推荐给他

矩阵分解要做的是预测出矩阵中缺失的评分，使得预测评分能反映用户的喜欢程度。可以把预测评分最高的前K个电影推荐给用户了。

其中，只有评分矩阵是已知的，我们要做的是如何预测出User矩阵和Item矩阵。这是一个最优化问题，我们的目标是使得User矩阵×Item矩阵与评分矩阵中已知的评分差异最小。

现在我们来看一个具体的例子，用矩阵表示收集到的用户行为数据，一共12个用户，9部电影并对其进行了评分。

现在假设我们得到的矩阵分解结果如下：user矩阵和item矩阵

• 观察User矩阵：用户的观影爱好体现在User向量上，例如用户1，最喜欢动作片
• 观察Item矩阵，电影的风格也会体现在Item向量上。例如红海行动、战狼2，这些都是动作片。
• 矩阵分解用user向量和item向量的内积去拟合评分矩阵中该user对该item的评分，内积的大小反映了user对item的喜欢程度。内积大匹配度高，内积小匹配度低。
• 隐含特征个数k，k越大，隐类别分得越细，计算量越大。

然后根据得到的两个矩阵，进行矩阵乘法，可以得到电影的预测评分

某个用户u对电影i的预测评分 = User向量和Item向量的内积

评分值越大，表示用户喜欢该电影的可能性越大，该电影就越值得推荐给用户

那么我们如何进行矩阵分解呢？

我们先来看看矩阵分解的目标函数

矩阵分解的目标函数

其中:

• $r_{ui}$是实际评分
• $x_u$是用户矩阵（user-matrix）
• $y_i$是物品矩阵（item-matrix)
• $\lambda$是正则化系数

我们的目标是找出使得上述目标函数最小的$x_u$和$y_i$。首先我们明确的是，上述我们要解决的是显示评分问题。

显性评分

ALS, Alternative Least Square, ALS，交替最小二乘法

Step1，固定Y 优化X

如下所示

Step2，固定X 优化Y，和step1一样

重复Step1和2，直到X 和Y 收敛。每次固定一个矩阵，优化另一个矩阵，都是最小二乘问题。

隐性评分

除了针对显式评分矩阵，ALS还可以对隐式矩阵进行分解。很多时候，用户的行为也会反映其对某种商品的偏好，但是这种行为是一直隐性的，没有具体的评分值。例如，将评分看成行为的强度，比如浏览次数，阅读时间

当$r_{ui}>0$时，用户u对商品i有行为

当$r_{ui}=0$时，用户u对商品i没有行为

$$ p_{ui}=1,r_{ui}>0\\p_{ui}=0,r_{ui}=0 $$

$p_{ui}$ 称为用户偏好：

当用户u 对物品i 有过行为，认为用户u 对物品i感兴趣，$p_{ui}=1$

当用户u 对物品i 没有过行为，认为用户u 对物品i 不感兴趣，$p_{ui}=0$

对隐式矩阵进行分解：

引入置信度：

当$r_{ui}$>0时，$c_{ui}与r_{ui}线性递增$

当$r_{ui}=0$时，$c_{ui}=1$，也就是$c_{ui}$最小值为1

此时目标函数目标函数

将目标函数转化为矩阵形式，并进行求导

Step1，固定Y优化X

求解得

Λu 为用户u 对所有物品的置信度 $c_{ui}$ 构成的对角阵

Step2，固定X优化Y

同理，求解得

Λi 为所有用户对物品i 的偏好的置信度构成的对角矩阵

代码实现

下面我们来看一下如何使用ALS算法进行求解。

import pandas as pd
import numpy as np
import random
from collections import defaultdict

class ALS(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 = None


    def _process_data(self, X):
        """ 将评分矩阵X转化为稀疏矩阵
            输入参数X:
                X {list} -- 2d list with int or float(user_id, item_id, rating)
            输出结果:
                dict -- {user_id: {item_id: rating}}
                dict -- {item_id: {user_id: rating}}
        """        
        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

     
    def _users_mul_ratings(self, users, ratings_T):
        """ 用户矩阵(稠密) 与 评分矩阵（稀疏）相乘
            The result(items) is a k * n matrix, n stands for number of item_ids.
            Arguments:
                users {Matrix} -- k * m matrix, m stands for number of user_ids.
                ratings_T {dict} -- The items ratings by users.
                {item_id: {user_id: rating}}
            Returns:
                Matrix -- Item matrix.
        """
        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)

    def _items_mul_ratings(self, items, ratings):
        """ item矩阵（稠密）与评分矩阵（稀疏）相乘
        The result(users) is a k * m matrix, m stands for number of user_ids.
        Arguments:
            items {Matrix} -- k * n matrix, n stands for number of item_ids.
            ratings {dict} -- The items ratings by users.
            {user_id: {item_id: rating}}
        Returns:
            Matrix -- User matrix.
        """
        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)

    # 生成随机矩阵
    def _gen_random_matrix(self, n_rows, n_colums):
        #print(n_colums, ' ', n_rows)
        #data = [[random() for _ in range(n_colums)] for _ in range(n_rows)]
        #d = 2
        data = np.random.rand(n_rows, n_colums)
        return Matrix(data)


    # 计算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

    # 模型训练
    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

    # Top-n推荐，用户列表：user_id, n_items: Top-n
    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]

    # 预测多个用户
    def predict(self, user_ids, n_items=10):
        return [self._predict(user_id, n_items) for user_id in user_ids]

def format_prediction(item_id, score):
    return "item_id:%d score:%.2f" % (item_id, score)

def load_movie_ratings(file_name):
    f = open(file_name)
    lines = iter(f)
    col_names = ", ".join(next(lines)[:-1].split(",")[:-1])
    print("The column names are: %s." % col_names)
    data = [[float(x) if i == 2 else int(x)
             for i, x in enumerate(line[:-1].split(",")[:-1])]
            for line in lines]
    f.close()

    return data

print("使用ALS算法") 
model = ALS()
# 数据加载
X = load_movie_ratings('MovieLens/ratings_small.csv')
# 运行max_iter次
model.fit(X, k=3, max_iter=2)
"""
X = np.array([[1,1,1], [1,2,1], [2,1,1], [2,3,1], [3,2,1], [3,3,1], [4,1,1], [4,2,1],
              [5,4,1], [5,5,1], [6,4,1], [6,6,1], [7,5,1], [7,6,1], [8,4,1], [8,5,1], [9,4,1], [9,5,1],
              [10,7,1], [10,8,1], [11,8,1], [11,9,1], [12,7,1], [12,9,1]])
# 运行max_iter次
model.fit(X, k=3, max_iter=20)
"""

print("对用户进行推荐")
user_ids = range(1, 13)
# 对用户列表user_ids，进行Top-n推荐
predictions = model.predict(user_ids, n_items=2)
print(predictions)
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))

使用ALS算法
The column names are: userId, movieId, rating.
Iterations: 1, RMSE: 3.368115
Iterations: 2, RMSE: 0.393883
对用户进行推荐
[[(593, 0.14406097730654768), (1198, 0.14358259103963905)], [(318, 2.059017427702032), (260, 1.923258591494868)], [(260, 1.2102151320443484), (2571, 1.0787785902899518)], [(318, 3.686989610157476), (593, 3.6010162010338984)], [(296, 2.0071412668514), (318, 1.8489213945544887)], [(593, 0.6176565451297263), (1198, 0.5291764793134027)], [(296, 2.1991835206619252), (593, 1.7899558400858702)], [(608, 2.3390885141087048), (1, 2.2529122594512856)], [(296, 0.8503498053957818), (1198, 0.8349697071072679)], [(593, 0.8445440715644625), (296, 0.7889019418410842)], [(356, 0.5262573842686891), (318, 0.5049187078106891)], [(593, 0.407095000056158), (3578, 0.40234869950041907)]]
User id:1 recommedation: ['item_id:593 score:0.14', 'item_id:1198 score:0.14']
User id:2 recommedation: ['item_id:318 score:2.06', 'item_id:260 score:1.92']
User id:3 recommedation: ['item_id:260 score:1.21', 'item_id:2571 score:1.08']
User id:4 recommedation: ['item_id:318 score:3.69', 'item_id:593 score:3.60']
User id:5 recommedation: ['item_id:296 score:2.01', 'item_id:318 score:1.85']
User id:6 recommedation: ['item_id:593 score:0.62', 'item_id:1198 score:0.53']
User id:7 recommedation: ['item_id:296 score:2.20', 'item_id:593 score:1.79']
User id:8 recommedation: ['item_id:608 score:2.34', 'item_id:1 score:2.25']
User id:9 recommedation: ['item_id:296 score:0.85', 'item_id:1198 score:0.83']
User id:10 recommedation: ['item_id:593 score:0.84', 'item_id:296 score:0.79']
User id:11 recommedation: ['item_id:356 score:0.53', 'item_id:318 score:0.50']
User id:12 recommedation: ['item_id:593 score:0.41', 'item_id:3578 score:0.40']

可以看出我们得到了预测的结果

但是上面这种方法只是最简单的对一个原始评分矩阵进行了分解。但是没有考虑到有些电影平均评分很高（或很低），我们称之为热门电影（冷门电影，俗称烂片）。

例如，肖申克的救赎，大家对它的评分一般都不会很低。（我给了9.8分，太好看了）

有的用户也会比较偏向性的给所有电影较高的评分，我们称为热心用户（我自己瞎起的名字，大家理解就行）在这种情况下，这类用户对所有的电影可能都会给一个较高的评分。但是我们刚刚上面的方法没有办法识别出这种关系，下面我们介绍一些其他的方法。

总结

矩阵分解（MF） 是一种隐语义模型，它通过隐类别匹配用户和item来做推荐。
矩阵分解的基本思想是对原有的评分矩阵R进行降维，分成了两个小矩阵：User矩阵和Item矩阵，User矩阵每一行代表一个用户的向量，Item矩阵的每一列代表一个item的向量。将User矩阵和Item矩阵的维度降低到隐类别个数的维度。

根据用户的行为，矩阵分解又可以分为显式矩阵分解和隐式矩阵

• 在显式MF中，用户向量和物品向量的内积拟合的是用户对物品的实际评分
• 在隐式MF中，用户向量和物品向量的内积拟合的是用户对物品的偏好(0或1)，拟合的强度由置信度控制，置信度又由行为的强度决定。

主要的两大应用场景

• 评分预测（Rating Prediction）

主要用于评价网站，比如用户给自己看过的电影评多少分（MovieLens），或者用户给自己看过的书籍评价多少分（Douban）。矩阵分解技术主要应用于评分预测问题。（这种情况下评分矩阵往往存在严重的稀疏性问题）

• Top-N推荐（Item Ranking）

常用于购物网站，拿不到显式评分，通过用户的隐式反馈为用户提供一个可能感兴趣的Item列表。排序任务，需要排序模型进行建模。

在本文中，我们使用ALS进行求解矩阵分解。但是实现这种方法的缺点是没有办法反应整体平均的情况，下一章我们将继续讨论baseline算法和slopeOne算法。