0%

ALS 算法

发表于 分类于

ALS 算法是矩阵分解的一种，用于评分预测。

矩阵分解

假设我们有一批用户数据，其中包含 m 个 User 和 n 个 Item, 用户和物品的关系是一个三元组，, 即用户对物品的评分，因此我们得到矩阵 Rm×nRm×nR{m\times n}, 其中的元素 ruiruir{ui}表示第 u 个用户对第 i 个 item 的评分。

评分矩阵通常规模很大，并且通常是稀疏矩阵，因为一个用户不可能给所有商品评分。矩阵中缺失的评分，称为 missing item.

接下来将这个矩阵分解为两个子矩阵，使得两个子矩阵能近似得到原矩阵：

如下图所示，左边 X 矩阵实际代表用户的隐矩阵，即每个用户用一个 k 维向量表示，而右边的矩阵代表物品的隐矩阵，即每个物品用一个 k 维向量表示。k 的值通常远小于 n 和 m.

为了使低秩矩阵 XY 的乘积接近于 R, 得到了我们的目标函数：

通常加入正则项，得到：

我们的目标就是优化上式，得到训练结果 X, Y。预测时，我们只要将 User 和 Item 代入 rui=xTuyirui=xuTyir_{ui}=x_u^Ty_i 就能得到相应的评分预测值。

此外，由于训练出了每个用户和物品的隐向量，因此根据向量比较 User 和 Item 之间的相似度。

ALS 优化

直接优化公式 2 比较困难，因此需要用 ALS 中的核心概念：交替。先固定其他维度，只优化其中一个维度。

对 xuxux_u 求导，将 yiyiy_i 当作常量，可得：

令导数为 0，可得：

同理，对 yiyiy_i 求导，由于 X 和 Y 是对称的，得到：

因此，整个迭代优化过程为：

  1. 随机生成 X, Y

    repeat until convergence {

  2. 固定 Y, 使用公式 3 更新 xuxux_u

  3. 固定 X, 使用公式 4 更新 yiyiy_i

    }

一般使用 RMSE 评估误差是否收敛：

算法复杂度：

  1. 求 xuxux_u:O(k2N+k3m)O(k2N+k3m)O(k^2N+k^3m)

  2. 求 yiyiy_i:O(k2N+k3n)O(k2N+k3n)O(k^2N+k^3n)

可以看出来当 k 一定的时候，这个算法的复杂度是线性的。

因为这个迭代过程，交替优化 X 和 Y，因此又被称作交替最小二乘算法（Alternating Least Squares，ALS）。

ALS 与隐式反馈

隐式反馈与 ALS 的结合，有 ALS-WR 算法，即加权的 ALS 算法。

显示反馈：用户对商品的评分。

隐式反馈：用户对商品的行为，如点击，收藏，搜索，购买记录等。

隐式反馈的特点：

  1. 没有负面反馈，用户一般会直接忽略不喜欢的商品，而不是给予负面评价

  2. 隐式反馈包含大量噪声

  3. 隐式反馈难以量化

  4. 显式反馈表现的是用户的喜好（preference），而隐式反馈表现的是用户的信任（confidence）。比如用户最喜欢的一般是电影，但观看时间最长的却是连续剧。大米购买的比较频繁，量也大，但未必是用户最想吃的食物。

很多人在决定是否看一部电影之前都会去豆瓣看下评分作为参考，看完电影也会给一个自己的分数。 每个人对每个商品或者电影或是音乐都有一个心理的分数，这个分数 表 明用户是否对这个内容满意。 作为内容的提供方，如果可以预测出每个用户对于内容的心理分数，就能更好的理解用户，并给用户提供好的内容推荐。 今天就介绍下如何通过 ALS 矩阵分解算法实现用户对于音乐或者电影的评分预测。

ALS 算法介绍

ALS 算法是基于模型的推荐算法，基本思想是对稀疏矩阵进行模型分解，评估出缺失项的值，以此来得到一个基本的训练模型。 然后依照此模型可以针对新的用户和物品数据进行评估。 ALS 是采用交替的最小二乘法来算出缺失项的，交替的最小二乘法是在最小二乘法的基础上发展而来的。

从协同过滤的分类来说，ALS 算法属于 User-Item CF，也叫做混合 CF，它同时考虑了 User 和 Item 两个方面。

我们通过音乐打分这个案例介绍下交替最小二乘法的原理，首先拿到的原始数据是每个听众对每首歌的评分矩阵 A，这个评分可能是非常稀疏的，因为不是每个用户都听过所有的歌，也不是每个用户都会对每首歌评分。

ALS 矩阵分解会把矩阵 A 分解成两个矩阵的相乘，分别是 X 矩阵和 Y 矩阵，

矩阵A=矩阵X和矩阵Y的转秩的乘积

x 的列表示和 Y 的横表示可以称之为 ALS 中的因子，这个因子是有隐含定义的，这里假设有 3 个因子，分别是性格、教育程度、爱好。 A 矩阵经过 ALS 分解出的 X、Y 矩阵可以分别表示成：

(上图为 x 矩阵)

(上图为 Y 矩阵)

数据经过这样的拆解就很容易做用户对音乐的评分预测。 比如有听众 6，他从没听过 “红豆“这首歌，但是我们可以拿到听众 6 在矩阵分解中 X 矩阵的向量 M，这时候只有把向量 M 和” 红豆 “在 Y 矩阵中的对应向量 N 相乘，就能预测出听众 6 对于” 红豆“这首歌的评分。

ALS 在 PAI 实验

现在在 PAI 上面对 ALS 算法案例进行实验。 整体流程只需要包含输入数据源和 ALS 矩阵分解组件即可。 本案例已经集成于 PAI-STUDIO 首页模板：

创建后如图：

1. 数据源

输入数据源包含 4 个字段

User: 用户 ID

Item： 音乐 ID

score： user 对 item 的评分

2.ALS 矩阵分解

需要设置 3 个对应字段，

参数名称

参数描述

取值范围

是否必选，默认值

userColNameuser 列名列的类型必须是 bigint，可以不连续编号必选
itemColNameitem 列名列的类型必须是 bigint，可以不连续编号必选
rateColName打分列名列的类型必须是数值类型必选
numFactors因子数正整数可选，默认值 100
numIter迭代数正整数可选，默认值 10
lambda正则化系数浮点数可选，默认值 0.1
implicitPref是否采用隐式偏好模型布尔型可选，默认值 false
alpha隐式偏好系数浮点数，大于 0可选，默认值 40

3. 结果分析

本案例中会输出 2 张表，对应 ALS 算法介绍中说的 X 矩阵和 Y 矩阵。

X 矩阵表如图：

Y 矩阵表如图：

比如要预测 user1 对音乐 item994556636 的评分，只要将下方两个向量相乘即可

User1： [-0.14220297,0.8327106,0.5352268,0.6336995,1.2326205,0.7112976,0.9794858,0.8489773,0.330319,0.7426911]

item994556636： [0.71699333,0.5847747,0.96564907,0.36637592,0.77271074,0.52454436,0.69028413,0.2341857,0.73444265,0.8352135]