基于关系图邻接矩阵逼近的推荐系统

引用本文

朱振峰, 高红格, 赵耀. 基于关系图邻接矩阵逼近的推荐系统[J]. 北京交通大学学报, 2017,41(2): 1-7.
ZHU Zhenfeng, GAO Hongge, ZHAO Yao. Graph adjacency matrix approximation based recommendation system[J]. JOURNAL OF BEIJING JIAOTONG UNIVERSITY, 2017,41(2): 1-7.
Doi:10.11860/j.issn.1673-0291.2017.02.001 复制到剪切板

Permissions

基于关系图邻接矩阵逼近的推荐系统

朱振峰, 高红格, 赵耀

北京交通大学 a.计算机与信息技术学院,b. 北京市现代信息科学与网络技术重点实验室,北京 100044

第一作者:朱振峰(1974—),男,黑龙江鸡西人,教授,博士. 研究方向为计算机视觉、机器学习、图像/视频分析与理解等. email:zhfzhu@bjtu.edu.cn.

收稿日期: 2016-09-12

基金: 国家自然科学基金(61572068,61532005); 教育部新世纪优秀人才支持计划项目(NCET-13-0661); 中央高校基本科研业务费专项资金(2015JBM039)

摘要

在基于关系图约束的推荐方法中,引入用户图(项目图)约束的目的是保持原始的高维用户表征空间(高维项目表征空间)与低维的隐性用户表征空间(隐性项目表征空间)之间用户关系(项目关系)的一致性.不同于传统的基于关系图Laplacian矩阵的一致性约束,本文提出一种基于关系图邻接矩阵逼近的推荐模型,从相似性空间一致性角度进行约束,在保持高维表征空间与低维隐性空间的一致性关系的同时,可以一定程度上避免局部过拟合问题.在EachMovie与MovieLens数据集上的实验结果验证了本文算法的有效性.

关键词: 推荐系统; 协同过滤; 因子分解; 图模型; 梯度下降法

中图分类号:TP181 文献标志码:A 文章编号:1673-0291(2017)02-0001-07

Graph adjacency matrix approximation based recommendation system

ZHU Zhenfeng, GAO Hongge, ZHAO Yao

a. School of Computer and Information Technology, b.Beijing Key Laboratory of Advanced Information Science and Network Technology, Beijing Jiaotong University, Beijing 100044,China

Fund:National Natural Science Foundation of China(61572068,61532005); Program for the New Century Excellent Talents in Universities of China(NCET-13-0661); Fundamental Research Funds for the Central Universities(2015JBM039)

Abstract

In graph based recommendation methods, the goal of the graph constraint is to preserve the consistency of user relationships (item relationships) between high dimensional user representation space (item representation space) and low dimensional latent user representation space. Instead of applying the traditional Laplacian matrix based consistency constraint, a graph adjacency matrix approximation based recommendation model is proposed. In essence,the matrix approximation plays a role of directly imposing a consistency constraint on the different similarity metric spaces. Thus, not only the consistency of the user relationships (the item relationships) from different representation spaces can be well preserved, but also, the local over-fitting problem can be avoided to some extent. Experimental results on EachMovie and MovieLens datasets show the effectiveness of the proposed method.

Keyword: recommender system; collaborative filtering; matrix factorization; graph model; gradient descent method

文章图片

网络技术的发展给用户带来了大量信息, 但同时也产生了信息过载^[1], 为解决这一问题, 研究人员提出了搜索引擎、推荐系统^[2]等方法.其中, 推荐系统在帮助用户发现有效信息的同时, 也使得信息更精准地推送给指定用户, 因此得到了广泛关注和长足发展.其中较为典型的应用如电商网站Amazon^[3]的书籍推荐系统, 以及网易的云音乐推荐系统等.

经过多年研究和发展, 现有推荐技术主要包括基于内容^[4]协同过滤^{[5, 6, 7]}和混合式推荐等方法.其中, 应用最广泛且最成功的是协同过滤推荐, 它通过整合用户的历史行为信息来发现用户间或项目间的关系, 再根据这些关系将未知项目推荐给活跃用户.同时, 协同过滤推荐又分为基于内存^[8]和基于模型的推荐算法, 后者也是目前推荐领域的研究重点, 其中经典的算法包括图模型和矩阵因子分解等.

基于矩阵因子分解的方法最早可追溯到由文献[9]提出的基于奇异值分解的推荐模型, 通过矩阵分解降低原始数据维度, 减少了计算量和内存占用, 但同时面临过拟合问题.文献[10, 11]提出规范化矩阵分解模型, 通过加入惩罚项, 提高了推荐准确率.由于预测评分中存在负值.文献[12]提出了非负矩阵分解方法, 将特征矩阵限制为非负矩阵, 增强了推荐内容的可解释性.

在矩阵因子分解的基础上, 研究表明:通过引入关系图约束, 可以保持高维表征空间与低维隐性空间之间用户(项目)关系的一致性, 从而改善推荐性能.文献[13]提出了融合项目关系图的非负矩阵分解算法, 揭示了隐含语义并保持了固有几何结构, 提高了推荐性能.文献[14]提出了一种基于交互式图传递模型的方法, 在评分信息空间中通过图模型交互传递用户关系和项目关系, 实现用户关系和项目关系的有效融合; 而不同于GNMF(Graph Regularized Non-negative Matrix Factorization)中的非负约束.文献[15]采用了正交约束, 达到了消除低维隐性表征空间的信息冗余的目的.

上述方法中为保持关系一致性, 图约束均以与关系图邻接矩阵对应的Laplacian矩阵的二次型的形式予以体现.但不足之处在于, 它只考虑了局部关系的一致性, 易于导致过拟合问题, 因而影响推荐性能.据此, 本文作者提出了基于关系图邻接矩阵逼近的模型, 不仅更好地保持了空间一致性关系, 而且一定程度上避免局部过拟合.本质上, 基于Laplacian矩阵关系图约束方法是以保持表征空间的一致性为出发点间接约束了高维显性空间向量和低维隐性表征空间的一致性, 而本文方法则以保持相似性空间的一致性为出发点, 利用关系图邻接矩阵的逼近直接对表征空间的一致性进行约束, 从而使推荐精确性得到进一步提升.

1 相关工作

1.1 符号介绍

令 $X = [x_{ij}] \in R^{Μ \times Ν} 表示 M 个用户对 N$ 个项目的偏好评分矩阵, 简称为用户-项目矩阵, $x_{ij}$ 表示第 $i$ 个用户对第 $j$ 个项目的评分, 其值为0到5的整数, 且 $x_{ij} = 0$ 表示未评分; $x_{i \cdot} = [x_{i 1}, ..., x_{iN}]$ 与 $x_{\cdot j} = [x_{1 j}, ..., x_{Mj}]$ 分别为评分矩阵X的第 $i$ 行与第 $j$ 列, 分别表示第 $i$ 个用户描述向量和第 $j$ 个项目描述向量.

此外, 对于由n个节点构成的无向图 $G = (V^{G}, E^{G})$ , $V^{G} = {\{v_{i}\}}_{i = 1}^{n}$ 表示图中节点的集合, $E^{G} = {\{e_{ij}^{G}\}}_{i, j = 1}^{n}$ 表示边的集合, 其中边 $e_{ij}^{G} = (v_{i}, v_{j})$ 表示节点对 $(v_{i}, v_{j})$ 的关系, 边的权重用 $w_{ij} \in [0, 1]$ 表示, 权重矩阵表示为 $W = [w_{ij}]_{i, j = 1}^{n}$ .令Tr(· )表示矩阵的迹, $‖ X ‖_{F}$ 表示矩阵X的F-范数, 且有 $‖ X ‖_{F} = \sqrt[]{\sum_{i, j} x_{ij}^{2}}$ ; 另外, Laplacian矩阵定义为 $L = D - W$ , 其中 $D = diag [d_{1}, ..., d_{n}]$ 为对角矩阵, $d_{i} = \sum_{j}^{=} w_{ij}$ .

1.2 基于图模型约束的协同滤波

矩阵因子分解将稀疏且高维的评分矩阵分解为两个低维隐性表征矩阵, 进而可用重构的低维矩阵预测用户对项目的评分.研究表明:若引入关系图约束, 可以有效保持高维显性表征空间与低维隐性表征空间用户结构关系(项目结构关系)的一致性, 从而可提高推荐性能.

1.2.1 基于用户图的图传递模型

关系图是反映用户之间或者项目之间关系的图, 而对某一项目表现出相同兴趣度的用户很可能在其他项目上也有相似的兴趣度, 因此, 引入关系图可以保持原始评分矩阵中的结构, 给出更精准的推荐.以基于用户图的模型^[14]为例, 根据原始评分矩阵抽取出的用户评分向量, 构建用户关系图 $W^{u} = [w_{ij}^{u}]_{i, j = 1}^{n}$ , 将用户的近邻关系作为约束加入到表征传统的矩阵分解模型中, 得到基于用户图的图传递模型为

$\begin{array}{l} \min ψ (\overset{\land}{X}) = μ \overset{M}{\sum_{i = 1}} ‖ x_{i \cdot} - {\overset{\land}{x}}_{i \cdot} ‖_{F}^{2} + \\ \overset{M}{\sum_{i, j = 1}} w_{ij}^{u} = \frac{{\overset{\land}{x}}_{i \cdot}}{\sqrt[]{d_{i}^{u}}} - \frac{{\overset{\land}{x}}_{j \cdot}}{\sqrt[]{d_{j}^{u}}} =_{F}^{2} (1) \end{array}$

式中: $μ > 0$ 为平衡因子; $d_{i}^{u} = \overset{M}{\sum_{j = 1}} w_{ij}^{u}$ ; ${\overset{\land}{x}}_{i \cdot}$ 表示经图传递后第 $i 个用户对 N$ 个项目的初始评分 $x_{i \cdot}$ 的预测.整理可得

$\min ψ (\overset{\land}{X}) = Tr ({\overset{\land}{X}}^{T} {\overset{\land}{L}}^{u} \overset{\land}{X}) + μ ‖ \overset{\land}{X} - X ‖_{F}^{2} (2)$

式中: ${\overset{\land}{L}}^{u} = (D^{u})^{- 1 / 2} L^{u} (D^{u})^{- \frac{1}{2}}$ 表示归一化的Laplacian矩阵.

通过对式(2)优化求解, 得到

$\overset{\land}{X} = μ {[I - {(D^{u})}^{- 1 / 2} W^{u} {(D^{u})}^{- 1 / 2}]}^{- 1} X (3)$

基于上述预测矩阵 $\overset{\land}{X}$ , 可对用户进行Top-N推荐.

1.2.2 基于规范化图的非负矩阵分解

现有的NMF方法^[7]是在欧氏空间实现对原始评分矩阵的低秩拟合, 不能很好地保持数据信息的固有几何结构, 据此, 文献[13]提出了基于规范化图的非负矩阵分解方法(GNMF), 基于局部不变性假设, 构建数据节点间的近邻关系图, 保持了数据信息固有的几何结构.本质上, GNMF整合了NMF和Laplacian特征映射的特点, 其模型为

$\begin{array}{l} \min ψ (U, V) = \overset{M}{\sum_{i = 1}} \overset{N}{\sum_{j = 1}} {(x_{ij} - \overset{k}{\sum_{p = 1}} u_{ip} v_{jp})}^{2} + \\ λ \overset{N}{\sum_{i, j = 1}} w_{ij}^{v} ‖ v_{i \cdot} - v_{j \cdot} ‖_{F}^{2} \\ s.t. u_{ip} \geq 0, v_{jp} \geq 0 (4) \end{array}$

式中: $U = [u_{ij}] \in R^{M \times k}$ 与 $V = [v_{ij}] \in R^{N \times k}$ 分别为低维的隐性用户空间及隐性项目空间的用户与项目表征矩阵; $λ$ 是平衡系数; $k$ 是低维空间的维度, 且有 $k ≪ M$ 及 $k ≪ N$ .

推导可得

$\begin{array}{l} \min ψ (U, V) = ‖ X - \overset{\land}{X} ‖_{F}^{2} + λ Tr (V^{T} L^{v} V) \\ s.t. u_{ip} \geq 0, v_{jp} \geq 0 (5) \end{array}$

式中: $\overset{\land}{X} = U V^{T}$ 为评分预测矩阵; $L^{v} = D^{v} - W^{v}$ .由于式(5)中的目标函数为非凸函数, 固可采用交替迭代更新法, 分别求得U和V, 从而得到预测矩阵 $\overset{\land}{X}$ .

1.2.3 应用半监督多标签学习的推荐模型

引入关系图可以显著提高推荐性能, 但同时也存在信息单一的问题.为此, 文献[16]提出了一种基于用户图和项目图联合图传递的半监督多标签学习算法(Semi-supervised Multi-label Learning by Solving a Sylvester Equation, SMSE), 并应用于推荐系统中.该联合图传递模型为

$\begin{array}{l} \min ψ (\overset{\land}{X}) = \overset{M}{\sum_{i = 1}} ‖ {\overset{\land}{x}}_{i \cdot} - x_{i \cdot} ‖_{F}^{2} + \\ \frac{1}{2} (α^{u} \overset{M}{\sum_{i, j = 1}} w_{ij}^{u} = \frac{x_{i \cdot}}{\sqrt[]{d_{i}^{u}}} - \frac{x_{j \cdot}}{\sqrt[]{d_{j}^{u}}} =_{F}^{2} + \\ α^{v} \overset{N}{\sum_{i, j = 1}} w_{ij}^{v} = \frac{x_{\cdot i}}{\sqrt[]{d_{i}^{v}}} - \frac{x_{\cdot j}}{\sqrt[]{d_{j}^{v}}} =_{F}^{2}) (6) \end{array}$

式中: $α^{u} 和 α^{v}$ 分别是用户项和项目项的平衡因子, 且 $d_{i}^{u} = \overset{M}{\sum_{j = 1}} w_{ij}^{u}$ , $d_{i}^{v} = \overset{N}{\sum_{i = 1}} w_{ij}^{v}$ .

进一步, 令 $\frac{\partial ψ (\overset{\land}{X})}{\partial \overset{\land}{X}} = 0$ 可有

$(α^{u} {\overset{\land}{L}}^{u} + I) X + α^{v} X {\overset{\land}{L}}^{v} = \overset{\land}{X} (7)$

式中: ${\overset{\land}{L}}^{u} = I - {(D^{u})}^{- 1 / 2} W^{u} {(D^{u})}^{- 1 / 2}$ ; ${\overset{\land}{L}}^{v} = I - {(D^{v})}^{- 1 / 2} W^{v} {(D^{v})}^{- 1 / 2}$ 分别表示归一化的Laplacian矩阵.即可由式(7)可得出预测评分矩阵.

1.2.4 基于图约束的矩阵分解模型

不同于文献[13]提出的GNMF模型中的非负约束, 文献[15]提出了一种基于正交约束的图规范化因子分解模型(Orthogonal Graph-Regularized Matrix Factorization, OGRMF).采用正交约束的目的是消除低维隐性表征空间的信息冗余.OGRMF模型的具体形式为

$\begin{array}{l} \min ψ (U, V) = \overset{M}{\sum_{i = 1}} \overset{N}{\sum_{j = 1}} {(x_{ij} - \overset{k}{\sum_{k = 1}} u_{ik} v_{jk})}^{2} + \\ α [\overset{M}{\sum_{i, j = 1}} w_{ij}^{u} ‖ u_{i \cdot} - u_{j \cdot} ‖_{F}^{2} + \overset{N}{\sum_{i, j = 1}} w_{ij}^{v} ‖ v_{i \cdot} - v_{j \cdot} ‖_{F}^{2}] \\ s.t. U^{T} U = I, V^{T} V = I (8) \end{array}$

式中: $α$ 是平衡因子.对于式(8), 文献[15]中提出了一种对偶收缩法对U和V进行求解, 从而得到预测评分矩阵 $\overset{\land}{X} = U V^{T} .$

2 基于关系图邻接矩阵逼近的算法

前述介绍的基于图模型约束的推荐方法中, 引入用户图(项目图)约束的目的是保持原始的高维用户表征空间(高维项目表征空间)与低维的隐性用户表征空间(隐性项目表征空间)之间用户关系(项目关系)的一致性.为保持关系的一致性, 用户图或项目图约束均以与关系图邻接矩阵对应的Laplacian矩阵的二次型的形式予以体现.但利用Laplacian矩阵的二次型进行一致性约束的不足之处在于, 它只考虑了局部关系的一致性, 易于导致过拟合问题, 因而影响推荐性能.

2.1 基于关系图邻接矩阵逼近的推荐框架

不同于基于关系图Laplacian矩阵的一致性约束, 本文提出了一种基于关系图邻接矩阵逼近(Graph Adjacency Matrix Approximation, GAMA)的方法更好地保持高维显性空间与低维隐性空间的一致性关系, 同时在一定程度上可避免上述的局部过拟合.

图1所示为本文提出的基于关系图邻接矩阵逼近的推荐框架.其中, $m \in [1, \dots, N],$ 对于已有评分矩阵X, 分别在高维显性用户表征空间(项目表征空间)与低维的隐性用户表征空间(隐性项目表征空间)构建用户关系图邻接矩阵 $W^{u} = [w_{ij}^{u}] \in R^{M \times M}$ (项目关系图邻接矩阵 $W^{v} = [w_{ij}^{v}] \in R^{N \times N}$ )与 ${\overset{\land}{W}}^{u} = [{\overset{\land}{w}}_{ij}^{u}] \in R^{M \times M}$ ( ${\overset{\land}{W}}^{v} = [{\overset{\land}{w}}_{ij}^{v}] \in R^{N \times N}$ ).进一步, 为保持在高维显性空间与低维隐性空间用户关系(项目关系)的一致性, 分别针对 $W^{u}$ 与 ${\overset{\land}{W}}^{u}$ 及 $W^{v}$ 与 ${\overset{\land}{W}}^{v}$ 施加某种逼近约束 $g (W^{u}, {\overset{\land}{W}}^{u})$ 及 $g (W^{v}, {\overset{\land}{W}}^{v})$ ; 最后, 利用形成的评分预测矩阵 $\overset{\land}{X} = U V^{T}$ 实现Top-N推荐.

	Figure Option View Download New Window
	图1 基于关系图邻接矩阵逼近的推荐框架Fig.1 Graph adjacency matrix approximation based recommendation framework

2.2 基于关系图邻接矩阵逼近的模型

本文提出的基于关系图邻接矩阵逼近的推荐模型可形成如下最小化问题

$\begin{array}{l} \min ψ (U, V, {\overset{\land}{W}}^{u}, {\overset{\land}{W}}^{v}) = \\ ‖ X - U V^{T} ‖_{F}^{2} + α^{u} g (W^{u}, {\overset{\land}{W}}^{u}) + α^{v} g (W^{v}, {\overset{\land}{W}}^{v}) (9) \end{array}$

为在低维的隐性用户表征空间(隐性项目表征空间)构建用户关系图邻接矩阵 ${\overset{\land}{W}}^{u} \in R^{M \times M}$ (项目关系图邻接矩阵 ${\overset{\land}{W}}^{v} \in R^{N \times N}$ ), 本文采用线性方式, 即有 ${\overset{\land}{w}}_{ij}^{u} = u_{i \cdot} \cdot {u^{T}}_{j \cdot}$ 和 ${\overset{\land}{w}}_{ij}^{v} = v_{i \cdot} \cdot {v^{T}}_{j \cdot}$ .此外, 为简化模型, 对于逼近函数 $g (A, B)$ 本文直接采用F-范数, 即有 $g (A, B) = ‖ βA - B ‖_{F}^{2}$ , 其中 $β$ 为量纲平衡系数.本质上, $g (W^{u}, {\overset{\land}{W}}^{u})$ 及 $g (W^{v}, {\overset{\land}{W}}^{v})$ 是从相似性空间一致性的角度对各自的关系图进行了约束.

式(9)可转化为

$\begin{array}{l} \min ψ (U, V) = \\ \overset{M}{\sum_{i = 1}} \overset{N}{\sum_{j = 1}} {(x_{ij} - u_{i \cdot} {v^{T}}_{j \cdot})}^{2} + \\ α^{u} \overset{M}{\sum_{i, j = 1}} {(β \cdot w_{ij}^{u} - u_{i \cdot} {u^{T}}_{j \cdot})}^{2} + \\ α^{v} \overset{N}{\sum_{i, j = 1}} {(β \cdot w_{ij}^{v} - v_{\cdot i} {v^{T}}_{\cdot j})}^{2} + \\ λ (\overset{M}{\sum_{i = 1}} ‖ u_{i \cdot} ‖_{F}^{2} + \overset{N}{\sum_{j = 1}} ‖ v_{\cdot j} ‖_{F}^{2}) (10) \end{array}$

其中, $λ$ 为惩罚项系数.

2.3 模型求解

对于由式(10)给出的针对 $ψ (U, V)$ 的最小化问题, 由于其对于变量U、V为非联合凸函数, 为此本文采用交替迭代的梯度下降法(Gradient Descend)进行求解.具体来说, 把目标函数 $ψ (U, V)$ 分别对U和V求导可得

$\begin{array}{l} \frac{\partial}{\partial U} ψ (U, V) = - 2 (X - U V^{T}) V - \\ 4 α^{u} (β \cdot W^{u} - U U^{T}) U + 2 λU (11) \\ \frac{\partial}{\partial V} ψ (U, V) = - 2 (X^{T} - V U^{T}) U - \\ 4 α^{v} (β \cdot W^{v} - V V^{T}) V + 2 λV (12) \end{array}$

令 $E = X - U V^{T}$ 表示利用U和V对原始评分矩阵X进行重构的误差矩阵, $E = [e_{ij}] \in R^{M \times N}$ .这样, 对于 $u_{i \cdot}$ 与 $v_{j \cdot}$ 则有如下更新公式

$\begin{array}{l} u_{i \cdot} + γ \cdot [e_{ij} {v^{T}}_{\cdot j} + α^{u} (β \cdot w_{ii}^{u} - \\ u_{i \cdot} {u^{T}}_{i \cdot}) u_{i \cdot} - λ u_{i \cdot}] \to u_{i \cdot} (13) \\ v_{j \cdot} + γ \cdot [e_{ij} {u^{T}}_{i \cdot} + α^{v} (β \cdot w_{jj}^{v} - \\ v_{j \cdot} {v^{T}}_{j \cdot}) v_{j \cdot} - λ v_{j \cdot}] \to v_{j \cdot} (14) \end{array}$

式中, γ 为表示学习率的常数.具体优化求解过程如表1所示.

表1 算法1 Tab.1 Algorithm No.1

算法1. 针对隐性因子U和V的优化求解
1)输入:初始评分矩阵X, 学习率γ , 迭代次数Iter; 2)初始化: $U^{(0)}$ 和 $V^{(0)}$ 3)for $t$ =1: $Iter$ 4) for $i = 1 : M$ 5) for $j = 1 : N$ 6) 计算预测误差矩阵E; 7) 根据式(13)更新用户特征向量 $u_{i \cdot}$ ; 8) 根据式(14)更新项目特征向量 $v_{j \cdot}$ ; 9) end for 10) end for 11)end for 12)输出 $U = U^{(Iter)}$ 和 $V = V^{(Iter)}$

表1 算法1 Tab.1 Algorithm No.1

3 实验结果与分析

3.1 数据集说明及评价标准

3.1.1 数据集说明

本文采用两个公开的真实数据集来演示所述模型的推荐效果:MovieLens和EachMovie, 这也是研究协同过滤推荐算法常用的数据库.其中, MovieLens数据集收录了943个用户对1 682部电影的10万条评分信息, EachMovie数据集收录了74 424个用户对1 682部电影的260万条评分信息.为避免冷启动的影响, 两个数据集中均舍弃了被评分少于5次的电影, 特别地, 对于EachMovie数据集, 抽取了1 000个用户的评分数据进行实验.数据集的细节描述信息见表2.

表2 数据集描述 Tab.2 Descriptions of the datasets

实验中, 对数据集进行随机划分, 按照9∶ 1的比例把用户随机划分为训练集和测试集, 对于测试集中的每个用户, 将该用户已评分的记录划分为观测集和隐藏集, 观测集用来推荐隐藏集中的对象, 通过比较可以检验推荐效果.

3.1.2 评价标准及参数设置

为了评价各推荐模型的效果, 采用常用的F1评价指标

$F 1 = \frac{2 PR}{P + R} (15)$

其中, R与P分别表示召回率与准确率.F1值综合反映了召回率与准确率评估指标.显然, F1值越大, 推荐效果越好.

实验中, 对于EachMovie与MovieLens数据集, 由式(13)和式(14)给出的学习率分别设置为 $γ = 0.015 和 γ = 0.004 .$ 其他参数设置由实验确定.

3.2 推荐性能比较与分析

为验证本文算法性能, 实验中, 本文与其他一些相关的因子分解或引入关系图的推荐方法进行了性能比较, 这些方法包括:正规化矩阵分解RMF、非负矩阵分解NMF、基于图约束的非负矩阵分解GNMF、基于项目图的传递模型IG^[14](Item Graph)、基于用户图传递模型UG^[14](User Graph)、项目近邻法IN^[14](Item Neighbor)、用户近邻法UN^[14](User Neighbor)、基于用户-项目联合图的传递模型UIG^[14](User-Item united Graph)、以及基于用户图-项目图交替传递模型UIIG^[14](Interactive User-Item Graph)等, 每种方法的细节描述信息见表3.

表3 方法描述 Tab.3 Descriptions of related methods

表4列出了各方法在两个数据集上的F1性能比较.可以观察到, 利用用户信息的方法(如UN, UG)明显优于利用项目信息的方法(如IN, IG); 而综合利用两类信息的方法(如UIG, UIIG)又显著优于分别利用两类信息的方法; 此外, 利用了关系图辅助信息的方法表现更优.与此同时, 在EachMovie数据集上, 本文提出的GAMA方法比已有方法中最优的UIIG方法仍高出了1.52%; 而在MovieLens数据集上, 本文提出的方法相较于已有方法中最优的RMF方法也高出了0.31%.

表4 不同算法的F1性能比较 Tab.4 Performance comparisons based on F1%

3.3 模型参数影响

本文提出的基于关系图邻接矩阵逼近的推荐模型中, 涉及的参数包括:低维隐性表征空间维度k, 量纲平衡系数β , 以及平衡因子α ^u和α ^v, 见式(10).为减少参数选择的复杂性, 在实验中, 本文设置α ^u = α ^v.

图2、图3分别是在MovieLens与EachMovie数据集上低维表征维度 $k$ 与F1值的关系曲线.可以看出, 对于MovieLens数据集, 当 $k$ 为30时取得最佳性能, 随后F1值则下降并趋于平稳; 而对于EachMovie数据集, 达到最佳性能时 $k$ 为110, 其后则趋于平稳.

	Figure Option View Download New Window
	图2 维数k对MovieLens数据集上的性能影响Fig.2 Effect of parameter $k$ on MovieLens dataset

	Figure Option View Download New Window
	图3 维数k对EachMovie数据集上的性能影响Fig.3 Effect of parameter $k$ in EachMovie dataset

对于平衡因子 $α^{u} (α^{v}),$ 图4与图5分别给出了在EachMovie与MovieLens数据集上其对F1值的作用曲线.可以看出, 平衡因子对应的最优值分别为 $α^{u} (α^{v}) = 0.006, α^{u} (α^{v}) = 0.002 .$

	Figure Option View Download New Window
	图4 参数α ^u(α ^v)对EachMovie数据库的性能影响Fig.4 Effect of parameter $α^{u} (α^{v})$ on EachMovie dataset

	Figure Option View Download New Window
	图5 参数α ^u(α ^v)对MovieLens数据集上的性能影响Fig.5 Effect of parameter $α^{u} (α^{v})$ on MovieLens dataset

此外, 对于量纲平衡系数 $β,$ 从图6与图7中可以看出, 其对推荐性能还是有一定的影响.这也说明, 在由式(10)给出的推荐模型中引入量纲平衡系数的必要性.

	Figure Option View Download New Window
	图6 参数β 对EachMovie数据集上的性能影响Fig.6 Effect of parameter $β$ on EachMovie dataset

	Figure Option View Download New Window
	图7 参数β 对MovieLens数据集上的性能影响Fig.7 Effect of $β$ on MovieLens dataset

3.4 算法收敛性分析

实验中采用MAE(Mean Absolute Error)值对算法的收敛性进行了分析.如图8所示, 对于EachMovie和MovieLens数据库, 算法在经过大约10次迭代后均达到收敛状态.这表明:由算法1给出的交替迭代求解能够保证算法的收敛.

	Figure Option View Download New Window
	图8 收敛性分析Fig.8 Convergence analysis

4 结论

1)为保持关系的一致性, 用户图或项目图约束均以与关系图邻接矩阵对应的Laplacian矩阵的二次型的形式予以体现.但利用Laplacian矩阵的二次型进行一致性约束的不足之处在于, 它只考虑了局部关系的一致性, 易于导致过拟合问题, 因而影响推荐性能.

2)不同于基于关系图Laplacian矩阵的一致性约束, 本文作者提出一种基于关系图邻接矩阵逼近的方法, 从相似性空间上更好地保持上述高维显性空间与低维隐性空间的一致性关系.同时, 在一定程度上可避免上述的局部过拟合问题.

The authors have declared that no competing interests exist.

参考文献

文献列表

[1]	MAES P. Agents that reduce work and information overload[J]. Communications of the ACM, 1994, 37(7): 30-40. [本文引用:1]
[2]	HILL W, STEAD L, ROSENSTEIN M, et al. Recommending and evaluating choices in a virtual community of use[C]. The SIGCHI Conference on Human Factors in Computing Systems, 1995: 194-201. [本文引用:1]
[3]	LINDEN G, SMITH B, YORK J. Amazon. com recommendations: item-to-item collaborative filtering[J]. IEEE Internet Computing, 2003, 7(1): 76-80. [本文引用:1]
[4]	PAZZANI M J, BILLSUS D. Content-based recommendation systems[M]. Berlin: Springer Press, 2007: 325-341. [本文引用:1]
[5]	ADOMAVICIUS G, TUZHILIN A. Towards the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6): 734-749. [本文引用:1]
[6]	MARLIN B. Collaborative filtering: a machine learning perspective[D]. Toronto: University of Toronto, 2004. [本文引用:1]
[7]	CREMONESI P, KOREN Y, TURRIN R. Performance of recommender algorithms on Top-N recommendation tasks[C]. ACM Conference on Recommender Systems, 2010: 39-46. [本文引用:2]
[8]	SARWAR B, KARYPIS B, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms[C]. 10th International Conference on World Wide Web, 2001: 285-295. [本文引用:1]
[9]	SARWAR B, KARYPIS G, KONSTAN J, et al. Application of dimensionality reduction in recommender system-a case study[R]. Minneapolis: Minnesota Univ Minneapolis Dept of Computer Science, 2000. [本文引用:1]
[10]	GORRELL G, WEBB B. Generalized hebbian algorithm for incremental latent semantic analysis[C]. The Interspeech, 2005: 86-93. [本文引用:1]
[11]	GORRELL G. Generalized hebbian algorithm for incremental singular value decomposition in natural language processing[C]. The Conference of the European Chapter of the Association for Computational Linguistics, 2006: 97-104. [本文引用:1]
[12]	LEE D D, SEUNG H S. Algorithms for non-negative matrix factorization[C]. Advances in Neural Information Processing Systems, 2001: 556-562. [本文引用:1]
[13]	CAI D, HE X, HAN J, et al. Graph regularized non-negative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560. [本文引用:3]
[14]	辛沛露, 朱振峰, 赵耀. 基于交互式图传递模型的Top-N推荐[J]. 信号处理, 2012, 28(10): 1386-1393. XIN Peilu, ZHU Zhenfeng, ZHAO Yao. Interactive graph propagation model for Top-N recommendation[J]. Signal Processing, 2012, 28(10): 1386-1393. (in Chinese) [本文引用:8]
[15]	ZHU Z, XIN P, WEI S, et al. Orthogonal graph-regularized matrix factorization and its application for recommendation[C]. IEEE International Conference on Multimedia and Expo, 2013: 1-6. [本文引用:3]
[16]	CHEN G, SONG Y, WANG F, et al. Semi-supervised multi-label learning by solving a sylvester equation[C]. SIAM International Conference on Data Mining, 2008: 410-419. [本文引用:1]

1994

0.0

... 网络技术的发展给用户带来了大量信息,但同时也产生了信息过载^[1],为解决这一问题,研究人员提出了搜索引擎、推荐系统^[2]等方法 ...

1995

0.0

... 网络技术的发展给用户带来了大量信息,但同时也产生了信息过载^[1],为解决这一问题,研究人员提出了搜索引擎、推荐系统^[2]等方法 ...

2003

0.0

... 其中较为典型的应用如电商网站Amazon^[3]的书籍推荐系统,以及网易的云音乐推荐系统等 ...

2007

0.0

... 经过多年研究和发展,现有推荐技术主要包括基于内容^[4]协同过滤^[5,6,7]和混合式推荐等方法 ...

2005

0.0

... 经过多年研究和发展,现有推荐技术主要包括基于内容^[4]协同过滤^[5,6,7]和混合式推荐等方法 ...

2004

0.0

... 经过多年研究和发展,现有推荐技术主要包括基于内容^[4]协同过滤^[5,6,7]和混合式推荐等方法 ...

2010

0.0

... 经过多年研究和发展,现有推荐技术主要包括基于内容^[4]协同过滤^[5,6,7]和混合式推荐等方法 ...

... 现有的NMF方法^[7]是在欧氏空间实现对原始评分矩阵的低秩拟合,不能很好地保持数据信息的固有几何结构,据此,文献[13]提出了基于规范化图的非负矩阵分解方法(GNMF),基于局部不变性假设,构建数据节点间的近邻关系图,保持了数据信息固有的几何结构 ...

2001

0.0

... 同时,协同过滤推荐又分为基于内存^[8]和基于模型的推荐算法,后者也是目前推荐领域的研究重点,其中经典的算法包括图模型和矩阵因子分解等 ...

2000

0.0

... 基于矩阵因子分解的方法最早可追溯到由文献[9]提出的基于奇异值分解的推荐模型,通过矩阵分解降低原始数据维度,减少了计算量和内存占用,但同时面临过拟合问题 ...

2005

0.0

... 文献[10,11]提出规范化矩阵分解模型,通过加入惩罚项,提高了推荐准确率 ...

2006

0.0

... 文献[10,11]提出规范化矩阵分解模型,通过加入惩罚项,提高了推荐准确率 ...

2001

0.0

... 文献[12]提出了非负矩阵分解方法,将特征矩阵限制为非负矩阵,增强了推荐内容的可解释性 ...

2011

0.0

... 文献[13]提出了融合项目关系图的非负矩阵分解算法,揭示了隐含语义并保持了固有几何结构,提高了推荐性能 ...

... 不同于文献[13]提出的GNMF模型中的非负约束,文献[15]提出了一种基于正交约束的图规范化因子分解模型(Orthogonal Graph-Regularized Matrix Factorization, OGRMF) ...

2012

0.0

辛沛露, 朱振峰, 赵耀. 基于交互式图传递模型的Top-N推荐[J]. 信号处理, 2012, 28(10): 1386-1393.

XIN

Peilu

, ZHU

Zhenfeng

, ZHAO

Yao

. Interactive graph propagation model for Top-N recommendation[J]. Signal Processing, 2012, 28(10): 1386-1393. (in Chinese)

摘　要：本文提出了一种基于交互式图传递模型的Top-N推荐方法。在‘用户-项目’评分信息空间中通过图模型交互传递用户关系和项目关系,实现用户关系和项目关系的有效融合。针对用户和项目描述空间的相似性度量问题,本文提出了一种鲁棒的组合相似性度量方法,以平衡原始评分信息和经传递得到的预测分值信息间之间的不对称性。最后,通过融合从用户图与项目图视角得到的活跃用户对每个项目的预测分值,形成其对项目评价分值更加可靠的预测。在MovieLens和EachMovie两个数据库上的实验结果表明,同基于用户图模型与项目图模型的协同滤波推荐方法相比,本文提出的方案取得了更好的推荐性能。

... 文献[14]提出了一种基于交互式图传递模型的方法,在评分信息空间中通过图模型交互传递用户关系和项目关系,实现用户关系和项目关系的有效融合 ...

... 以基于用户图的模型^[14]为例,根据原始评分矩阵抽取出的用户评分向量,构建用户关系图 Wu=[wiju]i,j=1n,将用户的近邻关系作为约束加入到表征传统的矩阵分解模型中,得到基于用户图的图传递模型为 ...

... 2 推荐性能比较与分析为验证本文算法性能,实验中,本文与其他一些相关的因子分解或引入关系图的推荐方法进行了性能比较,这些方法包括:正规化矩阵分解RMF、非负矩阵分解NMF、基于图约束的非负矩阵分解GNMF、基于项目图的传递模型IG^[14](Item Graph)、基于用户图传递模型UG^[14](User Graph)、项目近邻法IN^[14](Item Neighbor)、用户近邻法UN^[14](User Neighbor)、基于用户-项目联合图的传递模型UIG^[14](User-Item united Graph)、以及基于用户图-项目图交替传递模型UIIG^[14](Interactive User-Item Graph)等,每种方法的细节描述信息见表3 ...

2013

0.0

... 文献[15]采用了正交约束,达到了消除低维隐性表征空间的信息冗余的目的 ...

... 不同于文献[13]提出的GNMF模型中的非负约束,文献[15]提出了一种基于正交约束的图规范化因子分解模型(Orthogonal Graph-Regularized Matrix Factorization, OGRMF) ...

... 对于式(8),文献[15]中提出了一种对偶收缩法对U和V进行求解,从而得到预测评分矩阵 X∧=UVT ...

2008

0.0

... 为此,文献[16]提出了一种基于用户图和项目图联合图传递的半监督多标签学习算法(Semi-supervised Multi-label Learning by Solving a Sylvester Equation,SMSE),并应用于推荐系统中 ...