奇异值分解简称SVD(singular value decomposition),可以理解为:将一个比较复杂的矩阵用更小更简单的三个子矩阵的相乘来表示,这三个小矩阵描述了大矩阵重要的特性。SVD的用处有很多,比如:LSA(隐性语义分析)、推荐系统、数据降维、信号处理与统计等。
任何矩阵都可以使用SVD进行分解,对于一个MxN(M>=N)的矩阵M,存在以下的SVD分解:
∑是一个对角矩阵,其中的元素值就是奇异值,并且按照从大到小的顺序排列。
在很多情况下,前10%甚至更少的奇异值的平方就占全部奇异值平方的90%以上了,因此可以用前k个奇异值来近似描述矩阵:
而k的取值是由下面的公式决定:
其中percentage称为“奇异值平方和占比的阈值”,一般取90%,k是一个远小于m和n的值,这样也就达到了降维的目的。
MADlib的SVD函数可以对稠密矩阵和稀疏矩阵进行奇异值因式分解,并且还提供了一个稀疏矩阵的本地高性能实现函数。
(1)语法
svd( source_table,
output_table_prefix,
row_id,
k,
n_iterations,
result_summary_table
);
(2)参数
source_table:TEXT类型,源表名(稠密矩阵)。表含有一个row_id列标识每一行,从数字1开始。其它列包含矩阵的数据。可以使用两种稠密格式的任何一个,例如下面示例的2x2矩阵。
格式一:
row_id col1 col2
row1 1 1 0
row2 2 0 1
格式二:
row_id row_vec
row1 1 {1, 0}
row2 2 {0, 1}
output_table_prefix:TEXT类型,输出表的前缀。
row_id:TEXT类型,每行的ID。
k:INTEGER类型,计算的奇异值的个数。
n_iterations(可选):INTEGER类型,运行的迭代次数,必须在[k, 列维度]范围内,k是奇异值的个数。
result_summary_table(可选):TEXT类型,存储结果摘要表名。
表示为稀疏格式的矩阵使用此函数。为了高效计算,在奇异值分解操作之前,输入矩阵会被转换为稠密矩阵。
(1)语法
svd_sparse( source_table,
output_table_prefix,
row_id,
col_id,
value,
row_dim,
col_dim,
k,
n_iterations,
result_summary_table
);
(2)参数
source_table:TEXT类型,源表名(稀疏矩阵)。稀疏矩阵使用行列下标指示矩阵的每个非零条目,非常适合含有很多零元素的矩阵。如下面所示的4x7矩阵,除去零值只有6行。矩阵的维度由行、列的最大值推导出来。需要注意最后一行,即使是0也要包含这一行,因为它标识了矩阵的维度,并暗示了第4行与第7列全是0。
row_id | col_id | value
-------+--------+-------
1 | 1 | 9
1 | 5 | 6
1 | 6 | 6
2 | 1 | 8
3 | 1 | 3
3 | 2 | 9
4 | 7 | 0
(6 rows)
output_table_prefix:TEXT类型,输出表的前缀。
row_id:TEXT类型,包含行下标的列名。
col_id:TEXT类型,包含列下标的列名。
value:TEXT类型,包含值的列名。
row_dim:INTEGER类型,矩阵的行数。
col_dim:INTEGER类型,矩阵的列数。
k:INTEGER类型,计算的奇异值的个数。
n_iterations(可选):INTEGER类型,运行的迭代次数,必须在[k, 列维度]范围内,k是奇异值的个数。
result_summary_table(可选):TEXT类型,存储结果摘要表名。
此函数在计算SVD时使用本地稀疏表示,能够更高效地计算稀疏矩阵,适合高度稀疏的矩阵。
(1)语法
svd_sparse_native( source_table,
output_table_prefix,
row_id,
col_id,
value,
row_dim,
col_dim,
k,
n_iterations,
result_summary_table
);
(2)参数
参数含义与svd_sparse函数相同。
SVD函数的输出是以下三个表:
左右奇异值向量表的格式为:
row_idINTEGER类型。每个特征值对应的ID。
row_vecFLOAT8[]类型。该row_id对应的特征向量元素,数组大小为k。
由于只有对角线元素是非零的,奇异值表采用稀疏表格式:
row_idINTEGER类型,第i个奇异值为i。
col_idINTEGER类型,第i个奇异值为i(与row_id相同)。
valueFLOAT8类型,奇异值。
其中的row_id和col_id都是从1开始。
结果摘要表名有以下列:
rows_usedINTEGER类型,SVD计算使用的行数。
exec_timeFLOAT8类型,计算SVD使用的总时间。
iterINTEGER类型,迭代运行次数。
recon_errorFLOAT8类型,这组正交基的质量得分(如近似精度)。计算公式为:
relative_recon_errorFLOAT8类型,相对质量分数。计算公式为:
select madlib.svd();
-- 用法
select madlib.svd('usage');
-- 示例
select madlib.svd('example');
用稀疏SVD函数解决上一篇介绍的音乐作品推荐问题。(参见“HAWQ + MADlib 玩转数据挖掘之(四)——低秩矩阵分解实现推荐算法”)
(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 source_data;
create table source_data (
userid varchar(10),
musicid varchar(10),
val float8
);
(3)建立用户行为矩阵表
drop table if exists svd_data;
create table svd_data (
row_id int,
col_id int,
val float8
);
(1)生成用户行为业务表数据
insert into source_data values
('u1', 'm1', 5), ('u1', 'm6', -5),
('u2', 'm4', 3),
('u3', 'm3', 1), ('u3', 'm5', 2), ('u3', 'm7', 4),
('u4', 'm2', 4), ('u4', 'm3', 4), ('u4', 'm4', 3), ('u4', 'm7', -2),
('u5', 'm2', 5), ('u5', 'm3', -5), ('u5', 'm5', -5), ('u5', 'm7', 4), ('u5', 'm8', 3),
('u6', 'm3', 4), ('u6', 'm6', 3),
('u7', 'm2', -2), ('u7', 'm6', 5),
('u8', 'm2', -2), ('u8', 'm6', 5), ('u8', 'm8', 5),
('u9', 'm3', 1), ('u9', 'm5', 2), ('u9', 'm7', 4) ;
(2)从业务表生成索引表数据
-- 用户表
insert into tbl_idx_user (userid)
select distinct userid from source_data order by userid;
-- 音乐表
insert into tbl_idx_music (musicid)
select distinct musicid from source_data order by musicid;
(3)从业务表生成矩阵表数据
insert into svd_data
select t1.user_idx, t2.music_idx, t3.val
from tbl_idx_user t1, tbl_idx_music t2, source_data t3
where t1.userid = t3.userid and t2.musicid = t3.musicid;
之所以要用用户业务表作为数据源,是因为矩阵中包含所有有过打分行为的用户和被打过分的作品,但不包括没有任何打分行为相关的用户和作品。如果包含五行为记录的用户或作品,会在计算余弦相似度时出现除零错误或噪声数据。
drop table if exists svd_u, svd_v, svd_s, svd_summary cascade;
select madlib.svd_sparse_native( 'svd_data', -- input table
'svd', -- output table prefix
'row_id', -- column name with row index
'col_id', -- column name with column index
'val', -- matrix cell value
9, -- number of rows in matrix
8, -- number of columns in matrix
7, -- number of singular values to compute
NULL, -- Use default number of iterations
'svd_summary' -- Result summary table
);
说明:
select array_dims(row_vec) from svd_u;
select * from svd_s order by row_id, col_id;
select array_dims(row_vec) from svd_v;
select * from svd_summary;
输出如下:
dm=# select array_dims(row_vec) from svd_u;
array_dims
------------
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
(9 rows)
dm=# select * from svd_s order by row_id, col_id;
row_id | col_id | value
--------+--------+------------------
1 | 1 | 10.6650887159422
2 | 2 | 10.0400685494281
3 | 3 | 7.26197376834847
4 | 4 | 6.52278928434469
5 | 5 | 5.11307075598296
6 | 6 | 3.14838515537081
7 | 7 | 2.67251694708376
7 | 7 |
(8 rows)
dm=# select array_dims(row_vec) from svd_v;
array_dims
------------
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
[1:7]
(8 rows)
dm=# select * from svd_summary;
rows_used | exec_time (ms) | iter | recon_error | relative_recon_error
-----------+----------------+------+----------------+----------------------
9 | 6122.36 | 8 | 0.116171249851 | 0.0523917951113
(1 row)
可以看到,结果U、V矩阵的维度分别是9 x 7和8 x 7,奇异值是一个7 x 7的对角矩阵。
让我们按公式3计算一下奇异值的比值,验证k设置为6、7时近似程度。需要将奇异值个数设置成与列数相同,执行SVD,再计算比值。
-- k=8
drop table if exists svd8_u, svd8_v, svd8_s, svd8_summary cascade;
select madlib.svd_sparse_native( 'svd_data', -- input table
'svd8', -- output table prefix
'row_id', -- column name with row index
'col_id', -- column name with column index
'val', -- matrix cell value
9, -- number of rows in matrix
8, -- number of columns in matrix
8, -- number of singular values to compute
NULL, -- Use default number of iterations
'svd8_summary' -- Result summary table
);
-- k=6
drop table if exists svd6_u, svd6_v, svd6_s, svd6_summary cascade;
select madlib.svd_sparse_native( 'svd_data', -- input table
'svd6', -- output table prefix
'row_id', -- column name with row index
'col_id', -- column name with column index
'val', -- matrix cell value
9, -- number of rows in matrix
8, -- number of columns in matrix
6, -- number of singular values to compute
NULL, -- Use default number of iterations
'svd6_summary' -- Result summary table
);
对比近似度:
select * from svd6_summary;
select * from svd_summary;
select * from svd8_summary;
select s1/s3, s2/s3
from (select sum(value*value) s1 from svd6_s) t1,
(select sum(value*value) s2 from svd_s) t2,
(select sum(value*value) s3 from svd8_s) t3;
结果如下:
dm=# select * from svd6_summary;
t3;
rows_used | exec_time (ms) | iter | recon_error | relative_recon_error
-----------+----------------+------+----------------+----------------------
9 | 3051.51 | 8 | 0.335700790666 | 0.151396899541
(1 row)
dm=# select * from svd_summary;
rows_used | exec_time (ms) | iter | recon_error | relative_recon_error
-----------+----------------+------+----------------+----------------------
9 | 6122.36 | 8 | 0.116171249851 | 0.0523917951113
(1 row)
dm=# select * from svd8_summary;
rows_used | exec_time (ms) | iter | recon_error | relative_recon_error
-----------+----------------+------+-------------------+----------------------
9 | 4182.38 | 8 | 1.52006310774e-15 | 6.85529638348e-16
(1 row)
dm=# select s1/s3, s2/s3
dm-# from (select sum(value*value) s1 from svd6_s) t1,
dm-# (select sum(value*value) s2 from svd_s) t2,
dm-# (select sum(value*value) s3 from svd8_s) t3;
?column? | ?column?
-------------------+-------------------
0.977078978809393 | 0.997255099805013
(1 row)
可以看到,随着k值的增加,误差越来越小。在本示例中,奇异值个数为6、7的近似度分别为97.7%和99.7%。后面的计算都使用k=7的结果矩阵。
(1)定义计算余弦相似度函数
余弦相似度计算公式为:
madlib.cosine_similarity()函数返回两个向量的余弦相似度。
(2)定义基于用户的协同过滤函数
create or replace function fn_user_cf(user_idx int)
returns table(r2 int, s float8, col_id int, val float8, musicid varchar(10)) as
$func$
select r2, s, col_id, val, musicid
from (select r2,s,col_id,val,row_number() over (partition by col_id order by col_id) rn
from (select r2,s,col_id,val
from (select r2,s
from (select r2,s,row_number() over (order by s desc) rn
from (select t1.row_id r1, t2.row_id r2, abs(madlib.cosine_similarity(v1, v2)) s
from (select row_id, row_vec v1 from svd_u where row_id = $1) t1,
(select row_id, row_vec v2 from svd_u) t2
where t1.row_id <> t2.row_id) t) t
where rn <=5 and s < 1) t1, svd_data t2
where t1.r2=t2.row_id and t2.val >=3) t
where col_id not in (select col_id from svd_data where row_id = $1)) t1,
tbl_idx_music t2
where t1.rn = 1 and t1.col_id = t2.music_idx
order by t1.s desc, t1.val desc limit 5;
$func$
language sql;
说明:
select t1.row_id r1, t2.row_id r2, abs(madlib.cosine_similarity(v1, v2)) s
from (select row_id, row_vec v1 from svd_u where row_id = $1) t1,
(select row_id, row_vec v2 from svd_u) t2
where t1.row_id <> t2.row_id
最内层查询调用madlib.cosine_similarity函数返回指定用户与其他用户的余弦相似度。
select r2,s,row_number() over (order by s desc) rn from ...
外面一层查询按相似度倒序取得排名。
select r2,s from ... where rn <=5 and s < 1
外面一层查询取得最相近的5个用户,同时排除相似度为1的用户,因为相似度为1说明两个用户的作品评分一模一样,而推荐的应该是用户没有打过分的作品。
select r2,s,col_id,val from ... where t1.r2=t2.row_id and t2.val >=3
外面一层查询取得相似用户打分在3及其以上的作品索引ID。
select r2,s,col_id,val,row_number() over (partition by col_id order by col_id) rn from ... where col_id not in (select col_id from svd_data where row_id = $1)
外面一层查询取得作品索引ID的排名,目的是去重,避免相同的作品推荐多次,并且过滤掉被推荐用户已经打过分的作品。
select r2, s, col_id, val, musicid ... where t1.rn = 1 and t1.col_id = t2.music_idx order by t1.s desc, t1.val desc limit 5;
最外层查询关联作品索引表取得作品业务主键,并按相似度和打分推荐前5个作品。
(3)定义接收用户业务ID的函数
create or replace function fn_user_recommendation(i_userid varchar(10))
returns table (r2 int, s float8, col_id int, val float8, musicid varchar(10)) as
$func$
declare
v_rec record;
v_user_idx int:=0;
begin
select user_idx into v_user_idx from tbl_idx_user where userid=i_userid;
for v_rec in (select * from fn_user_cf(v_user_idx)) loop
r2:=v_rec.r2;
s:=v_rec.s;
col_id:=v_rec.col_id;
val :=v_rec.val;
musicid:=v_rec.musicid;
return next;
end loop;
return;
end;
$func$
language plpgsql;
通常输入的用户ID是业务系统的ID,而不是索引下标,因此定义一个接收业务系统的ID函数,内部调用fn_user_cf函数生成推荐。
(4)测试推荐结果
select * from fn_user_recommendation('u1');
select * from fn_user_recommendation('u3');
select * from fn_user_recommendation('u9');
推荐结果如图1所示。可以看到,因为u3和u9的评分完全相同,相似度为1,所以为他们生成的推荐也完全相同。
图1
(1)定义基于物品的协同过滤函数
create or replace function fn_item_cf(user_idx int)
returns table(r2 int, s float8, musicid varchar(10)) as
$func$
select t1.r2, t1.s, t2.musicid
from (select t1.r2,t1.s,row_number() over (partition by r2 order by s desc) rn
from (select t1.*, row_number() over (partition by r1 order by s desc) rn
from (select t1.row_id r1, t2.row_id r2, abs(madlib.cosine_similarity(v1, v2)) s
from (select row_id, row_vec v1
from svd_v
where row_id in (select col_id from svd_data where row_id=$1)) t1,
(select row_id, row_vec v2
from svd_v
where row_id not in (select col_id from svd_data where row_id=$1)) t2
where t1.row_id <> t2.row_id) t1) t1
where rn <=3) t1, tbl_idx_music t2
where rn = 1 and t1.r2 = t2.music_idx
order by s desc;
$func$
language sql;
说明:
select t1.row_id r1, t2.row_id r2, abs(madlib.cosine_similarity(v1, v2)) s
from (select row_id, row_vec v1
from svd_v
where row_id in (select col_id from svd_data where row_id=$1)) t1,
(select row_id, row_vec v2
from svd_v
where row_id not in (select col_id from svd_data where row_id=$1)) t2
where t1.row_id <> t2.row_id
最内层查询调用madlib.cosine_similarity函数返回指定用户打过分的作品与没打过分的作品的相似度。
select t1.*, row_number() over (partition by r1 order by s desc) rn ...
外面一层查询按相似度倒序取得排名。
select t1.r2,t1.s,row_number() over (partition by r2 order by s desc) rn from ... where rn <=3
外面一层查询取得与每个打分作品相似度排前三的作品,并以作品索引ID分区,按相似度倒序取得排名,目的是去重,避免相同的作品推荐多次。
select t1.r2, t1.s, t2.musicid from ... where rn = 1 and t1.r2 = t2.music_idx order by s desc
最外层查询关联作品索引表取得作品业务主键并推荐。
(2)定义接收用户业务ID的函数
create or replace function fn_item_recommendation(i_userid varchar(10))
returns table (r2 int, s float8, musicid varchar(10)) as
$func$
declare
v_rec record;
v_user_idx int:=0;
begin
select user_idx into v_user_idx from tbl_idx_user where userid=i_userid;
for v_rec in (select * from fn_item_cf(v_user_idx)) loop
r2:=v_rec.r2;
s:=v_rec.s;
musicid:=v_rec.musicid;
return next;
end loop;
return;
end;
$func$
language plpgsql;
通常输入的用户ID是业务系统的ID,而不是索引下标,因此定义一个接收业务系统的ID函数,内部调用fn_item_cf函数生成推荐。
(3)测试推荐结果
select * from fn_item_recommendation('u1');
select * from fn_item_recommendation('u3');
select * from fn_item_recommendation('u9');
推荐结果如图2所示。可以看到,因为u3和u9的评分作品完全相同,相似度为1,所以按作品相似度为他们生成的推荐也完全相同。
图2
假设一个新用户u10的评分向量为'{0,4,5,3,0,0,-2,0}',要利用已有的奇异值矩阵找出该用户的相似用户。
(1)添加业务数据
insert into source_data values ('u10', 'm2', 4), ('u10', 'm3', 5), ('u10', 'm4', 3), ('u10', 'm7', -2);
insert into tbl_idx_user (userid)
select distinct userid
from source_data
where userid not in (select userid from tbl_idx_user)
order by userid;
(2)确认从评分向量计算svd_u向量的公式
u10[1:8] x svd_v[8:7] x svd_s[7:7]^-1
(3)生成u10用户的向量表和数据
drop table if exists mat_u10;
create table mat_u10(row_id int, row_vec float8[]);
insert into mat_u10 values (1, '{0,4,5,3,0,0,-2,0}');
(4)根据计算公式,先将前两个矩阵相乘
drop table if exists mat_r_10;
select madlib.matrix_mult('mat_u10', 'row=row_id, val=row_vec',
'svd_v', 'row=row_id, val=row_vec',
'mat_r_10');
(5)根据公式,求奇异值矩阵的逆矩阵
drop table if exists svd_s_10;
create table svd_s_10 as select row_id, col_id,1/value val from svd_s where value is not null;
(6)根据公式,将(3)、(4)两步的结果矩阵相乘
注意(3)的结果mat_r_10是一个稠密矩阵,(4)的结果svd_s_10是一个稀疏矩阵。
drop table if exists matrix_r_10;
select madlib.matrix_mult('mat_r_10', 'row=row_id, val=row_vec',
'svd_s_10', 'row=row_id, col=col_id, val=val',
'matrix_r_10');
(7)查询与u10相似的用户
select t1.row_id r1, t2.row_id r2, abs(madlib.cosine_similarity(v1, v2)) s
from (select row_id, row_vec v1 from matrix_r_10 where row_id = 1) t1,
(select row_id, row_vec v2 from svd_u) t2
order by s desc;
结果如图3所示。
图3
可以看到,u10与u4的相似度高达99%,从原始的评分向量可以得到验证:
u4:'{0,4,4,3,0,0,-2,0}'
u10:'{0,4,5,3,0,0,-2,0}'
(8)将结果向量插入svd_u矩阵
insert into svd_u
select user_idx, row_vec from matrix_r_10, tbl_idx_user
where userid = 'u10';
如果需要给用户行为表中没有的用户做推荐,或者推荐用户行为表没有的物品,如何进行归一化处理?