本算法整理自知乎上的回答@nick lee。应用领域:“网易云音乐歌单个性化推荐”、“豆瓣电台音乐推荐”等。
这种算法是在NetFlix(没错,就是用大数据捧火《纸牌屋》的那家公司)的推荐算法竞赛中获奖的算法,最早被应用于电影推荐中,在实际应用中比现在排名第一的 @邰原朗所介绍的算法误差(RMSE)会小不少,效率更高。下面仅利用基础的矩阵知识来介绍下这种算法。
该算法的思想是:每个用户(user)都有自己的偏好,比如A喜欢带有小清新的、吉他伴奏的、王菲等元素(latent factor),如果一首歌(item)带有这些元素,那么就将这首歌推荐给该用户,也就是用元素去连接用户和音乐。每个人对不同的元素偏好不同,而每首歌包含的元素也不一样。
我们希望能找到这样两个矩阵:
(1)潜在因子-用户矩阵Q,表示不同的用户对于不用元素的偏好程度,1代表很喜欢,0代表不喜欢。比如图1这样:
图1
(2)潜在因子-音乐矩阵P,表示每种音乐含有各种元素的成分,比如图2中,音乐A是一个偏小清新的音乐,含有小清新这个Latent Factor的成分是0.9,重口味的成分是0.1,优雅的成分是0.2……
图2
利用这两个矩阵,我们能得出张三对音乐A的喜欢程度是:张三对小清新的偏好*音乐A含有小清新的成分+对重口味的偏好*音乐A含有重口味的成分+对优雅的偏好*音乐A含有优雅的成分+……即:0.6*0.9+0.8*0.1+0.1*0.2+0.1*0.4+0.7*0=0.69
每个用户对每首歌都这样计算可以得到不同用户对不同歌曲的评分矩阵
,如图3所示。(注,这里的破浪线表示的是估计的评分,接下来我们还会用到不带波浪线的R表示实际的评分):
图3
因此我们对张三推荐四首歌中得分最高的B,对李四推荐得分最高的C,王五推荐B。如果用矩阵表示即为:
下面问题来了,这个潜在因子(latent factor)是怎么得到的呢?
由于面对海量的让用户自己给音乐分类并告诉我们自己的偏好系数显然是不现实的,事实上我们能获得的数据只有用户行为数据。我们沿用 @邰原朗的量化标准:单曲循环=5, 分享=4, 收藏=3, 主动播放=2 , 听完=1, 跳过=-2 , 拉黑=-5,在分析时能获得的实际评分矩阵R,也就是输入矩阵大概是这个样子(图4):
图4
推荐系统的目标就是预测出空白对应位置的分值。推荐系统基于这样一个假设:用户对项目的打分越高,表明用户越喜欢。因此,预测出用户对未评分项目的评分后,根据分值大小排序,把分值高的项目推荐给用户。这是个非常稀疏的矩阵,因为大部分用户只听过全部音乐中很少一部分。如何利用这个矩阵去找潜在因子呢?这里主要应用到的是矩阵的UV分解,如图5所示。
图5
矩阵分解的想法来自于矩阵补全,就是依据一个矩阵给定的部分数据,把缺失的值补全。一般假设原始矩阵是低秩的,我们可以从给定的值来还原这个矩阵。由于直接求解低秩矩阵从算法以及参数的复杂度来说效率很低,因此常用的方法是直接把原始矩阵分解成两个子矩阵相乘。例如将图5所示的评分矩阵分解为两个低维度的矩阵,用Q和P两个矩阵的乘积去估计实际的评分矩阵,而且我们希望估计的评分矩阵和实际的评分矩阵不要相差太多,也就是求解下面的目标函数:
这里涉及到最优化理论,在实际应用中,往往还要在后面加上2范数的罚项,然后利用梯度下降法就可以求得这P,Q两个矩阵的估计值。例如我们上面给出的那个例子可以分解成为这样两个矩阵(图6):
图6
这两个矩阵相乘就可以得到估计的得分矩阵(图7):
图7
将用户已经听过的音乐剔除后,选择分数最高音乐的推荐给用户即可(红体字)。在这个例子里面用户7和用户8有强的相似性(图8):
图8
从推荐的结果来看,正好推荐的是对方评分较高的音乐(图9):
图9
从前面的介绍可以知道,Latent Factor推荐算法关键点在于评分矩阵的UV分解,求得P/Q两个矩阵。MADlib的lmf_igd_run函数能够实现这个功能。
lmf_igd_run( rel_output,
rel_source,
col_row,
col_column,
col_value,
row_dim,
column_dim,
max_rank,
stepsize,
scale_factor,
num_iterations,
tolerance
)
(1)rel_output
TEXT类型,接收输出的表名。输出的因子矩阵U和V是扁平格式。
RESULT AS (
matrix_u DOUBLE PRECISION[],
matrix_v DOUBLE PRECISION[],
rmse DOUBLE PRECISION
);
行i对应的特征是matrix_u[i:i][1:r],列j对应的特征是matrix_v[j:j][1:r]。
(2)rel_source
TEXT类型,包含输入数据的表名。输入矩阵的格式如下:
{TABLE|VIEW} input_table (
row INTEGER,
col INTEGER,
value DOUBLE PRECISION
)
输入包含一个描述稀疏矩阵的表,数据被指定为(row, column, value)。输入矩阵的行列值大于等于1,不应该有NULL值。
(3)col_row
TEXT类型,包含行号的列名。
(4)col_column
TEXT类型,包含列号的列名。
(5)col_value
DOUBLE PRECISION(FLOAT8)类型,(row, col)位置对应的值。
(6)row_dim(可选)
INTEGER类型,缺省为:“SELECT max(col_row) FROM rel_source”,矩阵中的行数。
(7)column_dim(可选)
INTEGER类型,缺省为:“SELECT max(col_col) FROM rel_source”,矩阵中的列数。
(8)max_rank
INTEGER类型,缺省为20,期望逼近阶。
(9)stepsize(可选)
DOUBLE PRECISION(FLOAT8)类型,缺省值为0.01。超参数,决定梯度步长。
(10)scale_factor(可选)
DOUBLE PRECISION(FLOAT8)类型,缺省值为0.1。超参数,决定初始因子标度。
(11)num_iterations(可选)
INTEGER类型,缺省值为10。不收敛时最大的迭代次数。
(12)tolerance(可选)
DOUBLE PRECISION(FLOAT8)类型,缺省值为0.0001,收敛误差。
用lmf_igd_run函数分解图4所示的矩阵,并生成相应的推荐矩阵。
(1)建立索引表
从前面的解释可以看到,推荐矩阵的行列下标分别表示用户和音乐作品。然而在业务系统中,userid和musicid很可能不是按从0到N的规则顺序生成的,因此需要建立矩阵下标值与业务表ID之间的映射关系,这里使用HAWQ的BIGSERIAL自增数据类型对应推荐矩阵的索引下标。
-- 用户索引表
drop table if exists tbl_idx_user;
create table tbl_idx_user (user_idx bigserial, userid varchar(10));
-- 音乐索引表
drop table if exists tbl_idx_music;
create table tbl_idx_music (music_idx bigserial, musicid varchar(10));
(2)建立用户行为表
drop table if exists lmf_data;
create table lmf_data (
row int,
col int,
val float8
);
-- 用户表
insert into tbl_idx_user (userid)
values ('u1'),('u2'),('u3'),('u4'),('u5'),('u6'),('u7'),('u8'),('u9'),('u10');
-- 音乐表
insert into tbl_idx_music (musicid)
values ('m1'),('m2'),('m3'),('m4'),('m5'),('m6'),('m7'),('m8'),('m9'),('m10'),('m11'),('m12'),('m13'),('m14'),('m15');
-- 用户行为表
insert into lmf_data values (1, 1, 5), (1, 6, -5), (1, 9, 5), (1, 11, 3), (1, 12, 1), (1, 13, 5);
insert into lmf_data values (2, 4, 3), (2, 9, 3), (2, 13, 4);
insert into lmf_data values (3, 3, 1), (3, 5, 2), (3, 6, -5), (3, 7, 4), (3, 11, -2), (3, 12, -2), (3, 13, -2);
insert into lmf_data values (4, 2, 4), (4, 3, 4), (4, 4, 3), (4, 7, -2), (4, 9, -5), (4, 12, 3);
insert into lmf_data values (6, 2, 5), (6, 3, -5), (6, 5, -5), (6, 7, 4), (6, 8, 3), (6, 11, 4);
insert into lmf_data values (7, 3, 4), (7, 6, 3), (7, 9, 4);
insert into lmf_data values (8, 2, -2), (8, 6, 5), (8, 11, 4), (8, 12, 4), (8, 13, -2);
insert into lmf_data values (9, 2, -2), (9, 6, 5), (9, 8, 5), (9, 11, 4), (9, 13, -2);
在生成原始数据时对图4的例子做了适当的修改。用户表中u5和u10用户没有给任何作品打分,而音乐表中的m10、m14、m15无评分。我们希望看到的结果是,除了与打分行为相关的用户和作品以外,也能为u5、u10推荐作品,并可能将m10、m14、m15推荐给用户。
drop table if exists lmf_model;
select madlib.lmf_igd_run( 'lmf_model',
'lmf_data',
'row',
'col',
'val',
11,
16,
7,
0.1,
1,
10,
1e-9
);
说明:
执行结果的控制台输出如下:
NOTICE: Matrix lmf_data to be factorized: 11 x 16
NOTICE: CREATE TABLE will create implicit sequence "lmf_model_id_seq" for serial column "lmf_model.id"
CONTEXT: SQL statement "
CREATE TABLE lmf_model (
id SERIAL,
matrix_u DOUBLE PRECISION[],
matrix_v DOUBLE PRECISION[],
rmse DOUBLE PRECISION)"
PL/pgSQL function "lmf_igd_run" line 49 during exception cleanup
NOTICE:
Finished low-rank matrix factorization using incremental gradient
DETAIL:
* table : lmf_data (row, col, val)
Results:
* RMSE = 0.0032755443518
Output:
* view : SELECT * FROM lmf_model WHERE id = 1
lmf_igd_run
-------------
1
(1 row)
Time: 2477.339 ms
可以看到,误差值为0.0033,分解用时2秒多。
从上一步的输出看到,lmf_igd_run()函数返回的模型ID是1,需要用它作为查询条件。
select array_dims(matrix_u) as u_dims, array_dims(matrix_v) as v_dims
from lmf_model
where id = 1;
结果:
u_dims | v_dims
-------------+-------------
[1:11][1:7] | [1:16][1:7]
(1 row)
Time: 158.163 ms
结果表中包含分解成的两个矩阵,U(用户潜在因子)矩阵11行7列,V(音乐潜在因子)矩阵16行7列。
select matrix_u, matrix_v from lmf_model where id = 1;
结果:
matrix_u | {{1.54648885311,1.63203242967,1.19529757016,1.03141840085,0.844437687891,0.0769111939022,0.645542689815},{0.757818584934,0.716903440182,1.19021031149,0.578927767269,0.954646881167,0.219129157675,0.70922183389},{1.33531138374,1.30363952312,0.0919517138103,-0.142114607359,-0.668429861574,0.279744342425,-1.47956275838},{0.190393941069,-0.0157012997592,-1.59761714858,0.303397793911,2.15476796766,0.741260761563,0.702753056216},{0.123468743637,0.843539815862,0.668331681751,0.429033627734,0.144201364834,0.402088313829,0.240613154601},{-1.73675064226,1.72484359814,0.990104966913,0.646877613553,0.905835307162,-0.707346214017,-0.36038050429},{0.622993679823,-0.00543774810147,0.163193819662,0.91213474814,-0.598496246148,1.78565072923,1.34895433137},{-1.18926160921,0.17719838284,0.478695134653,-1.14668758686,-0.352168758657,1.26421385298,1.10551649305},{-1.15853595317,-0.119913407821,1.07440704269,-0.686910624669,-0.297405263117,1.79703846266,0.535631232667},{0.831467553042,0.979984433856,0.130160186905,0.453018658794,0.0628163618967,0.0531226526946,0.00863399589434},{0.195625970606,0.171808642801,0.60626720218,0.761990434024,0.90873805061,0.63927074708,0.453554459848}}
matrix_v | {{0.91664850933,0.295100137999,0.649386785896,0.740600691525,1.04761610381,0.3951938048,0.998669662318},{-0.211657274194,1.23775531428,-0.0990159936749,1.50500061334,1.62828521114,-0.345089550207,0.277028536078},{1.48907962612,-0.244764864271,-1.11798478253,0.172149124925,0.212554639601,1.4013240539,0.535152168373},{0.182228641514,0.710136204482,0.199561470359,0.952762531103,1.08504062754,0.273794511904,0.662804958119},{1.83870481391,-0.377896107431,0.177281723558,-0.027566718438,-0.621172199773,0.841672155605,0.427967335391},{-1.4208947449,-1.52877812059,-0.279978617646,-0.438163656333,-0.506157691773,1.30685274721,1.25037856931},{0.293946423431,1.64459334677,0.642146247552,0.446804095655,0.000142813943154,-0.505397837783,-1.08734103352},{-1.00316820867,0.533775424924,1.38128161314,-0.29340575407,0.0619412924369,1.21026893492,0.112172980617},{0.928571674012,0.917879383969,1.81854196905,0.783856521179,-1.48198191488,0.510083892664,0.457647107996},{0.307900905609,0.227393480018,0.079794999212,0.0367207694799,0.755868535955,0.623352447525,0.124734496698},{-0.936350840061,1.00012249484,1.20991171631,0.0803342204453,0.39871563714,0.646403662259,1.39754259822},{-0.495918823256,0.358190982574,0.13668876922,-0.475142499674,0.759641070407,1.34038757262,1.18405353287},{0.889504598477,-0.0854584870533,0.411028314388,1.22217493352,1.48080784437,-0.445754117769,1.23355880197},{0.658764299937,0.689042912796,0.878053414635,0.757899995893,0.478946132585,0.446365167852,0.523622296751},{0.226923980284,0.493002902251,0.0254670833237,0.218542233109,0.719660140574,0.841996903066,0.750140952412},{0.695838811807,0.0145157109946,0.92957209982,0.420896829572,0.364341121167,0.229911166709,0.85705531016}}
Time: 89.038 ms
MADlib的矩阵相乘函数是matrix_mult,支持稠密和稀疏两种矩阵表示。
稠密矩阵需要指定矩阵对应的表名、row和val列:
select madlib.matrix_mult('mat_a', 'row=row_id, val=row_vec',
'mat_b', 'row=row_id, val=vector, trans=true',
'mat_r');
稀疏矩阵需要指定矩阵对应的表名、row、col和val列:
select madlib.matrix_mult('mat_a_sparse', 'row=rownum, col=col_num, val=entry',
'mat_b_sparse', 'row=row_id, col=col_id, val=val, trans=true',
'matrix_r');
‘trans=true’表示在相乘前该矩阵先进行转置。需要将lmf_igd_run函数输出的矩阵装载到表中。如果使用稠密形式,需要将二维矩阵转为一维矩阵。array_unnest_2d_to_1d是madlib 1.11版本的新增的函数,用于将二维数组展开为一维数组。1.10版本并无次函数,但可以创建一个UDF实现,具体参见“HAWQ + MADlib 玩转数据挖掘之(二)——矩阵”
如果使用稀疏形式,只要二维矩阵的行、列、值插入表中即可,这里使用稀疏方式。
-- 建立用户稀疏矩阵表
drop table if exists mat_a_sparse;
create table mat_a_sparse as
select d1,d2,matrix_u[d1][d2] val from
(select matrix_u,
generate_series(1,array_upper(matrix_u,1)) d1,
generate_series(1,array_upper(matrix_u,2)) d2
from lmf_model) t;
-- 建立音乐稀疏矩阵表
drop table if exists mat_b_sparse;
create table mat_b_sparse as
select d1,d2,matrix_v[d1][d2] val from
(select matrix_v,
generate_series(1,array_upper(matrix_v,1)) d1,
generate_series(1,array_upper(matrix_v,2)) d2
from lmf_model) t;
-- 执行矩阵相乘
drop table if exists matrix_r;
select madlib.matrix_mult('mat_a_sparse', 'row=d1, col=d2, val=val',
'mat_b_sparse', 'row=d1, col=d2, val=val, trans=true',
'matrix_r');
结果:
matrix_mult
-------------
(matrix_r)
(1 row)
Time: 5785.798 ms
这两个矩阵相(11 x 3与16 x 3)乘用时将近6秒。生成的结果表是稠密形式的11 x 16矩阵,这就是我们需要的推荐矩阵。为了方便与原始的索引表关联,将结果表转为稀疏表示。
drop table if exists matrix_r_sparse;
select madlib.matrix_sparsify('matrix_r', 'row=d1, val=val',
'matrix_r_sparse', 'col=d2, val=val');
结果:
matrix_sparsify
-------------------
(matrix_r_sparse)
(1 row)
Time: 2252.413 ms
最后与原始的索引表关联,过滤掉用户已经已经听过的音乐,选择分数最高音乐的推荐。
select t2.userid,t3.musicid,t1.val
from (select d1,d2,val,row_number() over (partition by d1 order by val desc) rn
from matrix_r_sparse t1
where not exists (select 1 from lmf_data t2 where t1.d1 = t2.row and t1.d2 = t2.col)) t1,
tbl_idx_user t2, tbl_idx_music t3
where t1.rn = 1 and t2.user_idx= t1.d1 and t3.music_idx = t1.d2
order by t2.user_idx;
结果:
userid | musicid | val
--------+---------+------------------
u1 | m7 | 4.46508576767804
u2 | m1 | 3.45259331270197
u3 | m14 | 1.21085044974838
u4 | m15 | 2.87854763370041
u5 | m12 | 3.07991997971589
u6 | m9 | 2.8073075471921
u7 | m8 | 5.70400322091688
u8 | m8 | 4.229015803831
u9 | m12 | 4.14559001844873
u10 | m8 | 2.16407771238165
(10 rows)
Time: 743.415 ms
这就是为每个用户推荐的音乐作品。可以看到,用户u5、u10分别推荐了m12和m8,m14和m15也推荐给了用户。