徐细林，李毅

（四川大学计算机学院，成都 610065）

0 引言

笔者在某家互联网公司承担过视频直播和电台的推荐系统的设计和开发工作，矩阵分解算法是所用到的推荐策略中的一种。笔者将在这里详细介绍矩阵分解算法如何运用在有大量用户的手机App或者网站的推荐系统上。

一个活跃度较高的App每天会产生很多新的内容，每天会有大量用户去点击观看，如何找出用户喜欢看的内容推荐给用户成为一个关键性的问题。

对于一个大型的直播app来说，每日的活跃用户在几千万左右，活跃主播在数十万左右。如何做个性化推荐，在数十万个主播中找出每个用户他喜欢的数十到数百个主播是推荐系统要解决的问题。

1 数据收集和数据预处理

每天用户打开App后，用户会对展示给用户的主播或者电台进行点击、观看、打赏。通过Nginx+kafka来收集这些用户的日志数据。对收集的JSON数据做简单解析后以天为分区存入到hive当中。

在不能直接获取到用户对item的评分时，充分利用最可能表达用户对item的喜好程度的观看时长和打赏这两项数据来表示用户对主播的评分。

依据存入到hive当中的数据，获取每天单个用户对每一个主播的打赏金额p和观看时长t，以s=1000*p+t作为单个用户对单个主播的评价基本依据。计算从当前往过去推15天的用户-主播的累加的s值。

由此可以得到一张具有用户id，主播id，评价值s这三个字段的二维表。对评价值s这一个字段的具体数值做一个min-max标准化：

为了防止作弊的情况以及头部主播流量过于聚焦，smax不直接取最大的数，一般取前1%大的数。对于超出smax的数，直接设置为1，小于smax的数，直接用min-max公式计算即可。

数据标准化之后，用户id，主播id，评价值s*这三个字段的二维表写入到hive当中，这张二维表就可以直接作为数据源来直接使用。

2 矩阵分解和als算法

矩阵分解即把一个矩阵分解成多个小矩阵的乘积。在推荐系统中，一般是会把一个大的矩阵分解成两个小矩阵的乘积。

如表1所示，在这里user指用户，item指主播。矩阵中的值代表某用户对某播主的评价（标准化后的观看时长和打赏金额之间的转化值）。为空的表示该用户对该主播之前没有交互，是需要求解预测的值。

表1

在大型应用中由于用户数和item数都非常庞大，那么矩阵就会非常大，会远远超出单机所能计算的规模。由此需要用分布式系统来处理。

User和item之间有多个关联维度（例如性别、年龄、各种风格等），我们只需要把评价矩阵R投射在这些维度上即可。设维度为k，那么可以表示为：

图1 大矩阵R拆分成两个小矩阵

一般情况下k的值会远小于m和n的值，这样达到降维的目的。k的值一般取20-100之间，不需要显示定义这些关联维度，假设他们存在即可。

分解后的两个小矩阵相乘即可填充稀疏矩阵R中的空值。

那么问题转化成找出合适的矩阵U和矩阵V，使得这两个分解矩阵相乘所得的积与初始评分矩阵R之间的差的平方最小。为了防止过拟合，引入正则化项。那么损失函数为：

上面的公式直接优化并不容易，可以u和v的二元导数并不容易计算。采用交替最小二乘法（ALS），即交替固定其中一个维度，而去优化另一个维度来优化损失函数。

首先对ui求导，可得：

令偏导数为0，即：

可得：

同理可得 vj=(UTU+λI)-1UTrj（2）

算法详细步骤如下：

初始化U，V；

（2）开始迭代，直到损失函数J的值小于设定的数或者迭代次数大于设定的次数；

①固定v，使用公式1来更新ui；

②固定u，使用公式2来更新vj；

（3）达到（2）中设定的迭代终止条件，得到的U和V即为所要求的矩阵。

分解得到的U和V矩阵相乘，即可得到用户对item的评分值。

3 在Spark中使用矩阵分解做推荐系统

对于大规模推荐系统，数据量会远远超出单机能处理的能力。一般会使用基于Spark计算引擎的分布式系统来处理推荐系统问题。

在数据预处理过程当中，已经获得一张每个用户对每个主播评价的二维表。

Spark中的机器学习库MLlib当中已经集成了ALS，使用时直接调用就可以。在训练过程当中需要设置以下四个参数：

rating：由用户-物品矩阵构成的训练集；

rank：即k，表示矩阵分解的维度，一般设置在20到100之间；

numIterations:迭代次数；

lambda：正则项的惩罚系数。

训练好的U和V两个矩阵相乘，即可得到最终的评分矩阵T。获取每个user中的评分最高的500个item，就是所推荐的结果。

接下来需要调参，最大化矩阵分解算法的推荐效果。在离线测试中，对比某一天的推荐内容和该天用户实际点击、观看、付费的节目来判断推荐效果。但是由于过去没有使用矩阵分解算法，这样不能较好地反应实际情况，只能做一个参考。

初步调完参之后，选择上线。给予10%的流量，观测推荐效果。在上线的两周内，每天调整参数，使得该算法的推荐效果接近于最优。

4 使用堆排序解决als中的笛卡儿积带来的问题

在使用Spark中的MLlib库中的ALS时，在对训练好的模型进行预测时，如果直接调用recommend-ProductsForUsers（n），给每个用户推荐最值得推荐的n个item时，不仅会极大的占用内存资源，计算时长往往会超过1个小时，远远达不到系统推荐的需求，为此我们对spark在als这一块做了优化。

读一下recommendProductsForUsers这个函数的源码，我们发现函数对user和item做了一次crossjoin（笛卡尔乘积），而在实际业务中对1000万的活跃用户数和30万的活跃主播数做一次笛卡尔乘积，会产生一张3万亿的用户对主播的评分表，这极大占用了内存，消耗了过多的计算资源。

而在实际业务中我们只需要获得的是每个用户最高评分的500个主播，并不需要保留单个用户对所有主播的评分。我们自己构造了一个函数，是用堆排序来做的。算法如下。

单个用户的userfeatures和单个itemfeatures相乘，得到单个用户对单个item的评分

如果评分数量小于500，对item加1，重复（1）的计算过程，直到满500个为止。

对这500个评分构建一个最小堆，堆顶为最小数s。

重复（1）的计算过程，继续对item做迭代（直到所有item迭代完为止），如果新的评分大于最小堆堆顶的数s，那么替换s，并对最小堆做调整，使得其满足最小堆的条件。

通过（4），最终获得单个用户在矩阵分解中评分最高的500个item，这也是最终给用户所推荐的

对每一个用户重复（1）到（5），最终获得每个用户最值得推荐的500个item。

通过上述算法，我们把内存消耗降低了90%，预测时间由原来的1个多小时减少到9分钟。

5 效果评测（与原有的算法效果比）

上线两周后,和原有的方法做一些比较。主要评价指标有 CTR（Click-Through-Rate），ATU（Average Time Per User），ARPU（Average Revenue Per User）这三项。

CTR即点击通过率，表示item的实际点击次数除以该item获得的曝光量。ATU即用户平均观看时长，指的是在一个周期内用户点击进入各个直播间观看的总时长除以进入的直播间数量。ARPU指的是在一个周期内总收入除以活跃用户数量。

下表表示基于item的协同过滤，基于user的协同过滤，热门筛选和矩阵分解这四种策略在一周内平均每天在评价指标上的表现。

表2 几种算法在各个评价维度的分值

观察可知，矩阵分解在CTR和ARPU两个指标上表现最好，尤其是在ARPU上的表现出人意料。可以提高其分配流量比例，把矩阵分解作为个性化推荐系统的主要策略之一。

6 结语

本文从数据采集、数据预处理到矩阵分解算法运用以及预测阶段算法改进，完整地实现了一套如何在大规模系统上通过矩阵分解算法做推荐系统，从而优化了CTR指标，提升了ARPU值，具有极大的实用价值。

参考文献：

[1]Zhou R,Khemmarat S,Gao L.The Impact of YouTube Recommendation System on Video Views[C].ACM SIGCOMM Conference on Internet Measurement 2010,Melbourne,Australia-November.DBLP,2010:404-410.

[2]Felfernig A,Jeran M,Ninaus G,et al.Toward the Next Generation of Recommender Systems:Applications and Research Challenges[M].Multimedia Services in Intelligent Environments.Springer International Publishing,2013:734-749.

[3]Lü L,Medo M,Chi H Y,et al.Recommender Systems[J].Physics Reports,2012,519（1）:1-49.

[4]李改,李磊.基于矩阵分解的协同过滤算法[J].计算机工程与应用,2011,47（30）:4-7.