1 引言

随着信息技术的不断发展, 人类走入信息过载时代, 越来越多的系统引入标签作为其信息表示方式, 标签推荐技术取得快速发展.《连线》杂志创始人Kevin Kelly^[1]指出, 信息组织方式进化经历了3个阶段, 从文件通过文件夹的组织形式存储在台式机中, 到网页以链接的方式形成网络, 再到数据流借助标签构成云.以标签来组织信息具有历史必然性, 标签既可用于描述和组织信息, 又可用于信息检索, 此外还具有语义性.随着标签服务的成功, 越来越多的系统为用户提供标签服务, 标签是用户标记物品和发现物品最自然的方式, 用户可用标签标记图片、视频、音乐、文档等各类数据^[2].目前标签广泛应用于网站系统^[3], Delicious、CiteULike、Last.fm以及Meetup等系统都允许用户为其内容标注标签.然而, 目前系统主要利用标签对信息资源进行分类、组织、检索, 标签推荐技术也大多采用热门标签、常用标签、PersonalRank等^[3]简单、成熟的方法, 推荐效果有待进一步提高.

标签成为信息组织方式, 提供标签服务的系统不断涌现, 如微博允许用户用标签标识自身特征, 用于描述用户相关信息, 构成二维标签信息〈用户, 标签〉(注:本文所提到的数据维度是指数据中对象类型的个数); 数据管理器用标签标识数据, 通过标签直接定位数据, 解决文件夹式不断双击查找数据的问题, 也构成二维标签信息〈数据, 标签〉; 标签网站系统(如Delicious, Last.fm, MovieLens等)允许用户对网站内容进行标注, 获得特定用户对特定内容的标签信息, 构成三维标签信息〈用户, 物品, 标签〉; 基于活动的应用系统(如Meetup, Plancast)中, 包含活动、群体、用户、活动内容、活动地点等多维信息, 其中, 用户、群体、活动内容等都可被标签标记, 构成多维标签信息〈用户, 事件, 地点, 群体, 标签, 等〉.标签数据维度从二维到多维不断扩展, 随着数据信息量的增多, 对用户进行精准标签推荐的难度也不断增大, 现有标签推荐系统大多采用成熟、简单的推荐模型^[3], 难以体现不同类型对象的特征信息差异.目前研究或者针对单一网络结构建模, 不区分数据不同维度信息, 将数据中不同类型对象看作同一对象, 或者针对某一特定维度网络综合考虑多个维度的信息进行标签推荐, 缺乏同时考虑多维度信息且适用于不同维度数据的标签推荐模型.

本文研究一种基于异构网络(heterogeneous network)维度可扩展的标签推荐模型HnMTR(heterogeneous networks tag recommendation in multi-dimension), 该模型可同时适用于不同维度标签数据对用户进行标签推荐, 实验结果表明, 该模型不仅可以适用于不同维度的数据, 而且推荐结果也优于现有流行算法.本文的主要贡献包括以下几个方面.

(1) 在标签推荐应用中, 首先提出先进行异构网络同空间映射, 再进行推荐的思想.综合考虑各个类型顶点特征后, 将顶点进行同空间映射, 使该模型适用于具有不同顶点类型数量的标签系统, 具有良好的可扩展性.

(2) 在标签推荐应用中, 构建面向多标签系统维度可扩展的标签推荐模型.以往模型或者仅考虑部分标签数据信息构建不区分顶点和边类型的同构网络(homogeneous network)模型进行推荐, 或者仅基于某一特定类型的标签系统数据构建异构网络模型, 其模型只适用于特定类型的标签系统.HnMTR模型可适用于多种标签系统, 且综合考虑数据多维度信息.

(3) 在标签推荐应用中, 构建多维度标签数据对象的同空间映射模型.该模型在充分考虑不同顶点特征的前提下, 将标签系统中不同类型顶点和边映射到同一空间, 使网络中任意两个顶点可以比较, 任意两条边的权重可以比较.

(4) 对标签推荐模型和顶点同空间映射模型参数进行最优化学习.针对文中提出的异构网络同空间映射模型和标签推荐模型, 分别提出参数优化算法, 对模型中的关键参数进行学习, 设定最优模型参数值.

2 相关工作

本文研究标签推荐模型, 首先对已有标签推荐研究进行分析总结; 其次, 本文充分借鉴网络嵌入(network embedding)技术已有研究成果, 并基于该技术实现异构网络模型顶点和边同空间映射.此外, 基于元路径建模是数据挖掘领域进行异构网络分析的另一类方法, 很多研究人员将该方法用于相似性计算、链接预测等问题, 本文也将简要介绍其相关研究成果.

2.1 面向互联网系统的标签推荐技术

随着互联网标签系统的不断涌现, 标签推荐技术引起研究人员的广泛关注.德国卡塞尔大学Jäschke等人^[4]最先通过量化研究方法对标签推荐结果进行评估, 并提出基于协同过滤和基于图模型两种标签推荐算法, 该研究对标签推荐算法进行初步尝试.美国明尼苏达大学Vig等人^[5]基于MoiveLens数据集, 通过分析用户的标签标注行为对电影和标签的评分进行预测, 并向用户推荐标签, 该研究采用协同过滤相关推荐算法, 并未构建图模型, 精确度有待提高.美国宾夕法尼亚州立大学Song等人^[6]将带标签文档通过三元组(Words, Documents, Tags)表示成二部图, 并提出高效率算法进行实时推荐, 该研究主要专注算法实时特性, 难以扩展到多维度标签数据.上海复旦大学Yang等人^[7]基于微博用户标签数据, 针对微博标签数据稀疏性、个人喜好优先等特点, 提出先聚类、再通过社会化信息扩展、最后去除语义重复的标签推荐算法, 该算法仅适用于微博数据, 可扩展性有待增强.新加坡南阳理工大学Tuan-Anh等人^[8]以基于活动的社会网络(event-based social network)为研究对象, 提出用于进行用户个性化推荐的图模型, 构建有多种顶点类型的异构网络, 并利用该模型为群体推荐标签.该模型引入太多不同顶点类型, 未进行顶点同空间映射, 直接基于多参数马尔可夫链(multivariate Markov chain)建模, 需学习过多参数, 给模型计算带来很大负担.清华大学Wei等研究人员^[9]针对社会化标签系统, 构建异构图模型, 针对(用户, 物品, 标签)三维数据进行标签推荐.他们还引入社会网络、标签语义、物品内容等附加信息以提高推荐准确度, 是目前针对三维标签数据的最优算法, 但该算法难以满足其他维度标签数据的推荐需求.针对以往标签推荐算法可扩展性和准确度无法同时兼顾的问题, 本文首先对异构网络进行同空间映射, 减少异构顶点类型, 降低需学习参数数量.在充分考虑异构顶点信息的前提下, 增强算法可扩展性并取得较好的推荐结果.

2.2 异构网络信息挖掘技术

网络嵌入研究是由网络中协同过滤和连接预测等应用需求驱动而产生的特征嵌入技术分支研究^[10].该研究通常将实际应用问题转化为采用代数方法的实体嵌入(entity embedding)问题.美国NEC实验室Zhu等人^[11]提出对网络连接矩阵和文档词频同时进行因数分解对网页进行分类; 美国哥伦比亚大学Shaw等人^[12]提出一个保持网络结构特征的嵌入框架, 该框架将网络映射到一个低维度的欧几里德空间.此外, 美国纽约州立大学石溪分校的研究人员提出DeepWalk^[13], 通过有界随机游走模型学习网络空间的隐含信息.以上方法都仅考虑了同构网络信息, 无法对异构网络的多种顶点和边的信息进行有效挖掘.引入异构网络信息最直接的方法是构建异构网络不同顶点和边类型的多个邻接矩阵, 再分别对每个邻接矩阵用已有方法进行张量分解^[14], 这样做需维护大量矩阵信息, 无法将算法扩展到大规模网络数据.中国科学院自动化研究所Yuan等人^[15]提出一个非线性嵌入模型, 该模型采用受限玻尔兹曼机(restricted Boltzman machines)对多种边的类型进行分析, 但其并未充分利用原数据所有异构信息, 且受限玻尔兹曼机在需大量学习参数设定时效率低下.美国伊利诺伊大学香槟分校Chang等人^[16]提出基于深度学习模型的异构网络嵌入方法, 该方法将多种顶点和边的信息映射到同一信息空间, 使异构网络中任意两顶点可比较.本文主要借鉴该模型的异构网络信息嵌入思想, 对异构网络信息进行同空间映射.

基于元路径的方法是解决异构网络相关问题的另一有效途径, 元路径是指异构网络中链接对象关系的组合^[17], 不同组合表达不同语义.北京邮电大学Shi等人^[18]针对传统异构网络建模方法难以精确度量顶点间语义信息的问题, 提出引入异构网络边和元路径权重的方法, 从而能够精确地描述路径语义, 最终构建基于语义路径的推荐模型SemRec.该研究团队已发表多篇基于元路径进行异构网络信息挖掘的科研论文^{[17, 19]}, 将该方法在文献检索、移动通话等领域的应用进行探索.美国印第安纳大学Liu等人^[20]引入PRF(pseudo relevance feedback)算法进行科研人员文献推荐.美国伊利诺大学芝加哥分校Zhang等人^[21]基于多在线社交网络场景, 提出内部社交元路径和外部社交元路径概念, 构建异构网络模型, 对社交网络进行连接预测.此外, 美国乔治亚理工学院Zhou等人^[22]和香港大学Wan等人^[23]对元路径在异构网络聚类和分类中的应用进行深入探索.由于基于元路径的方法复杂度往往较高, 研究者们大多借助分布式架构进行并行计算, 本文主要借鉴网络嵌入的相关方法.

总之, 已有研究通常针对某一特定标签系统数据建模, 难以直接应用到其他系统, 可扩展性受到制约.其次, 基于异构网络进行信息挖掘技术不断受到研究人员关注, 主要采用基于元路径和信息嵌入两种挖掘方法.根据调研结果, 还未有学者将信息嵌入挖掘方法应用到标签推荐中, 本文将充分借鉴该方法构建具有良好可扩展性的标签推荐模型.

3 标签推荐模型

本节主要介绍维度可扩展标签推荐模型, 可为多种标签系统提供标签推荐服务.其基本思想是:首先构建异构网络模型描述标签数据多维信息; 其次对异构网络中除标签以外的异构顶点和边基于同空间映射模型进行计算, 使不同类型的顶点和边可进行量化比较, 将原异构网络多维度信息映射到由标签顶点和普通顶点构成的二维网络中; 最终基于该二维网络引入多参数马尔可夫链构建标签推荐模型, 并对模型参数进行最优化学习.本节首先介绍模型基本表示方法, 其次介绍异构网络同空间映射模型, 最后介绍基于映射后网络的标签推荐模型.

3.1 模型基本表示

异构网络^[8]是指一个网络的顶点和边至少有一项存在两种或以上的类型, 即顶点有多种类型或边有多种类型或二者都有多种类型.由于本文针对标签系统进行建模, 对标签进行特殊处理, 将标签系统数据抽象成无向图G=(T, ET, V, EV), 其中, T={t₁, t₂, …, t_|T|}表示标签集合, V={v₁, v₂, …, v_|T|}表示图中其他类型顶点集合, ET表示图中边的两个顶点至少有一个为标签顶点的边集合, EV表示图中除ET以外边的集合.边e_ij(∀i, j∈{1, …, |V|+|T|})∈ EV∪ET当且仅当顶点v_i和v_j之间存在无向边, 边的权重根据实际数据语义进行定义(在本文中, 向量是列向量且用小写加粗字母表示, 如x和y; 矩阵用大写加粗字母表示, 如X和Y.用大写字母表示集合, 如V和E; 用|·|表示集合的大小, 空集用∅表示).

此外, 无向图G通过两个映射函数与对象类型集合O和关系类型集合R相关联, 分别表示为f_v:V→O和f_e:E→R.每个顶点v_i∈V∪T都对应某个特定的对象类型f_v(v_i)∈O.同理, 每条边e_ij∈EV∪ET都对应某种特定的关系类型f_e(e_ij)∈R, 每条边的关系类型通过两个顶点的类型确定.

定义 1(异构网络维度).对于一个异构网络, 其对象类型集合为O, 其顶点有|O|种类型, 则称该异构网络为|O|维异构网络.另外, 可以构建|O|维异构网络的标签数据集, 称为|O|维标签数据.

网络的异构性通过集合O和R的大小体现, 如果|O|=|R|=1, 此时为同构网络; 否则为异构网络.每个顶点都属于特定类型V_m(m∈[1, |O|]), 不同类型的顶点满足V₁∪V₂∪...∪V_|O|=V, V_m∩V_n=∅(m, n∈[1, |O|]), E_mn则表示类型m的顶点与类型n的顶点间边的集合; 每种类型的顶点由一个d_m维特征向量进行描述, 即对于v∈V_m, 其特征向量x ∈R^d_m顶点间关系用对称矩阵A∈R^|V|x|V|表示, 如果e_ij∈E, 则A_ij为1, 否则为–1.

3.2 基于网络嵌入技术的异构网络同空间映射模型

异构网络的顶点和边有多种类型, 每种类型顶点具有不同特征, 不同类型顶点间相似性难以度量, 本节的工作是学习映射函数, 将不同空间的数据映射到同一维空间, 这样可以方便计算顶点间相似性^[16].首先需选取顶点特征构建其特征向量, 所选特征应反映顶点独特性质, 如用户特征可选用其购买商品数量、消费总金额、标注标签数量等等.特征向量包含信息越多, 越能清晰地描述顶点属性, 映射结果信息量越大, 计算复杂度越高.第m种类型的转换矩阵用U_m∈ R^d_m×r表示.对于第m种顶点类型某个顶点特征向量x_m, 则有:

${{\mathit{\boldsymbol{\tilde x}}}_m} = \mathit{\boldsymbol{U}}_m^T{\mathit{\boldsymbol{x}}_m}$

(1)

这样, 将所有顶点的特征向量映射到r维空间.第m种类型顶点i表示为v_mi, 其特征向量为x_mi.顶点间余弦相似度可以如式(2) 所示, 相似度越大, 两顶点越相似.

$s({\mathit{\boldsymbol{x}}_{mi}},{\mathit{\boldsymbol{x}}_{nj}}) = {{\mathit{\boldsymbol{\tilde x}}}_{mi}}^T{{\mathit{\boldsymbol{\tilde x}}}_{nj}} = {(\mathit{\boldsymbol{U}}_m^T{\mathit{\boldsymbol{x}}_{mi}})^T}\mathit{\boldsymbol{U}}_n^T{\mathit{\boldsymbol{x}}_{nj}} = {\mathit{\boldsymbol{x}}_{mi}}^T{\mathit{\boldsymbol{U}}_m}\mathit{\boldsymbol{U}}_n^T{\mathit{\boldsymbol{x}}_{nj}}$

(2)

其中, ${\mathit{\boldsymbol{U}}_m}\mathit{\boldsymbol{U}}_n^T \in {R^{{d_m} \times {d_n}}}.$

异构网络中顶点与其他顶点通过显式或隐式方式关联, 这些关联信息在网络中通过异构边体现.映射模型基本假设为:若两个顶点相连, 则二者相似度应高于不相连的两个顶点.对于两个顶点特征向量x_mi和x_nj, 为对边的信息进行形式化表示, 设计一个成对判定函数, 如式(3) 所示.

$d({\mathit{\boldsymbol{x}}_{mi}},{\mathit{\boldsymbol{x}}_{nj}})\left\{ {\begin{array}{*{20}{c}} { > 0({\mathit{\boldsymbol{A}}_{ij}} = 1)}\\ { < 0({\mathit{\boldsymbol{A}}_{ij}} = - 1)} \end{array}} \right\}$

(3)

所有v_mi, v_nj∈V, t_mn是与顶点类型相关的偏好值^[16].令:

$d({\mathit{\boldsymbol{x}}_{mi}},{\mathit{\boldsymbol{x}}_{nj}}) = s({\mathit{\boldsymbol{x}}_{mi}},{\mathit{\boldsymbol{x}}_{nj}}) - {t_{mn}}$

(4)

这样, 本文采用由网络连接关系引导的二元逻辑回归函数进行参数U的学习^[16], 损失函数表示为

$L({\mathit{\boldsymbol{x}}_{mi}},{\mathit{\boldsymbol{x}}_{nj}}) = \log (1 + {{\rm{e}}^{ - {\mathit{\boldsymbol{A}}_{ij}}d({\mathit{\boldsymbol{x}}_{mi}},{\mathit{\boldsymbol{x}}_{nj}})}})$

(5)

以上损失函数基于Sigmoid函数, 目标为最大化连通顶点与不连通顶点间相似度差异, 但上式对Sigmoid函数先取倒数再取对数, 故目标函数为求其最小值.目标函数形式化为

$f(\mathit{\boldsymbol{U}}) = {\min _{{\mathit{\boldsymbol{U}}_1},...,{\mathit{\boldsymbol{U}}_{|O|}}}}\left( {\sum\limits_{m \in [1,|O|]} {\sum\limits_{n \in [1,|O|]} {\frac{{{\beta _{mn}}}}{{{N_{mn}}}}\sum\limits_{{v_{mi}} \in {V_m},{v_{nj}} \in {V_n}} {L({\mathit{\boldsymbol{x}}_{mi}},{\mathit{\boldsymbol{x}}_{nj}})} } } + \gamma \sum\limits_{m \in [1,|O|]} {\left\| {{\mathit{\boldsymbol{U}}_m}} \right\|_F^2} } \right)$

(6)

N_mn表示连接顶点类型m和顶点类型n的边的数量.β是平衡参数, 用来权衡不同类型边的重要性, γ是用来进行偏置方差^[24]折中的偏好参数, 这些偏好参数都可以通过学习来设定或者设置为固定值.在本文中, 为简化计算, 都设置为固定值.在上式中, ║·║_F是弗罗贝尼乌斯范数(Frobenius norm).该目标函数可采用坐标下降法进行计算, 在计算某个U_m时, 设定其他变量为固定值, 计算过程如下:

${\min _{{\mathit{\boldsymbol{U}}_m}}}\left( {\sum\limits_{n \in [1,|O|]} {\frac{{{\beta _{mn}}}}{{{N_{mn}}}}\sum\limits_{{v_{mi}} \in {V_m},{v_{nj}} \in {V_n}} {\log (1 + {{\rm{e}}^{ - {\mathit{\boldsymbol{A}}_{ij}}{\mathit{\boldsymbol{x}}_{mi}}^T{\mathit{\boldsymbol{U}}_m}{\mathit{\boldsymbol{U}}_n}^T{\mathit{\boldsymbol{x}}_{nj}}}})} } + \gamma \left\| {{\mathit{\boldsymbol{U}}_m}} \right\|_F^2} \right)$

(7)

下降幅度则可以通过(8) 计算, 同维映射算法具体过程如算法1所示.由于已有研究^[16]证明参数趋于收敛, 假设该算法经过n次迭代趋于收敛, 则其时间复杂度为O(nN).

$\frac{{\partial ( \cdot )}}{{\partial {\mathit{\boldsymbol{U}}_m}}} = \sum\limits_{n \in [1,|O|]} {\frac{{{\beta _{mn}}}}{{{N_{mn}}}}} \sum\limits_{{v_{mi}} \in {V_m},{v_{nj}} \in {V_n}} {\frac{{ - {\mathit{\boldsymbol{A}}_{ij}}{\mathit{\boldsymbol{x}}_{mi}}{\mathit{\boldsymbol{x}}_{nj}}^T{\mathit{\boldsymbol{U}}_n}}}{{1 + {{\rm{e}}^{{\mathit{\boldsymbol{A}}_{ij}}{\mathit{\boldsymbol{x}}_{mi}}^T{\mathit{\boldsymbol{U}}_m}\mathit{\boldsymbol{U}}_n^T{\mathit{\boldsymbol{x}}_{nj}}}}}}} + 2\gamma {\mathit{\boldsymbol{U}}_m}$

(8)

通过以上同维映射, 集合V中任意顶点v_i的特征都可用r维向量$\mathit{\boldsymbol{r}}_i^T$表示.此时, 顶点v_i和v_j间边的权重可定义为

${w_{ij}} = s(\widetilde {{\mathit{\boldsymbol{x}}_i}},\widetilde {{\mathit{\boldsymbol{x}}_j}})$

(9)

经过以上处理, 对除标签顶点外的顶点及其边进行了同一维度映射, 边的权重也进行了统一度量.

算法 1.同空间映射模型参数学习算法.

输入:顶点初始特征矩阵X={x₁, x₂, ..., x_N}, 坐标下降参数γ, 平衡参数β, 映射到维度r;

输出:学习后的参数U.

1.    t=0;

2.   初始化U⁽⁰⁾ ;

3.     while f(U) 未收敛  do

4.      For维度m from 1 to N do

5.      固定其他维度的参数;

6.      按式(8) 所示计算∂(·)/(∂U_m)=0时的U_m;

7.      更新U_m^(t);

8.       t=t+1;

3.3 基于多参数马尔可夫链的标签推荐模型

标签推荐的目的是为被标记对象推荐最能描述其功能和所属范畴的标签, 如在微博数据中, 被标记对象为用户; 在文件管理系统数据中, 被标记对象为数据; 在社交音乐网站数据中, 被标记对象为音乐; 在基于活动的社会网络数据中, 被标记对象为群体或用户.推荐的标签应该综合考虑数据中各个与其相关的维度信息, 标签与标记对象在越多的维度相关度高, 则其评分越高.

3.3.1 模型描述

通过上一节计算, 异构网络G=(T, ET, V, EV)的顶点V和边EV映射到同一空间, 此时, 顶点集合用V′表示, 边集合用EV′表示, 由V′和EV′构成的网络为同构网络.此时, 网络表示为G′=(T, ET, V′, EV′).由于模型的目的是进行标签推荐, 在同维映射过程中并未对标签顶点及其相关边进行处理.此时, 网络中顶点有两种类型:标签顶点和普通顶点; 网络中边也有两种类型.带标签边et和普通边ev.ET中边的权重为标签标记次数, 而EV′中边的权重为通过同空间映射后顶点间关系的权重, 网络邻接矩阵B中的元素值为对应边的权重.

定义 2(状态转移矩阵).状态转移矩阵P是将引入标签顶点后网络G′的邻接矩阵B的列进行归一化处理后的矩阵.网络的邻接矩阵表示如下:

$\mathit{\boldsymbol{B = }}\left[ {\begin{array}{*{20}{c}} 0 & {{\mathit{\boldsymbol{B}}_{TV}}}\\ {{\mathit{\boldsymbol{B}}_{VT}}} & {{\mathit{\boldsymbol{B}}_{VV}}} \end{array}} \right]$

(10)

经过归一化的矩阵P可表示为

$\mathit{\boldsymbol{P = }}\left[ {\begin{array}{*{20}{c}} 0 & {{\mathit{\boldsymbol{B}}_{TV}}\mathit{\boldsymbol{D}}_V^{ - 1}}\\ {{\mathit{\boldsymbol{B}}_{VT}}\mathit{\boldsymbol{D}}_T^{ - 1}} & {{\mathit{\boldsymbol{B}}_{VV}}\mathit{\boldsymbol{D}}_V^{ - 1}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 0 & {{\mathit{\boldsymbol{P}}_{TV}}}\\ {{\mathit{\boldsymbol{P}}_{VT}}} & {{\mathit{\boldsymbol{P}}_{VV}}} \end{array}} \right]$

(11)

其中, D_V^-1和D_T^-1为两个对角矩阵, 二者的第i个元素计算如下:

$\mathit{\boldsymbol{D}}_T^{ - 1}(i,i) = \frac{1}{{\sum\nolimits_{M \in \{ T,V\} } {\sum\nolimits_{k = 1}^M {{\mathit{\boldsymbol{B}}_{MT}}(k,i)} } }},\mathit{\boldsymbol{D}}_V^{ - 1}(i,i) = \frac{1}{{\sum\nolimits_{M \in \{ T,V\} } {\sum\nolimits_{k = 1}^M {{\mathit{\boldsymbol{B}}_{MV}}(k,i)} } }}$

(12)

定义 3(查询向量).给定一个标记对象及其与标签推荐相关的顶点集合S, 查询向量q∈R^|V|定义如下:

${\mathit{\boldsymbol{q}}_i} = \left\{ {\begin{array}{*{20}{c}} {{\omega _i}(v \in S)}\\ {0(v \notin S)} \end{array}} \right\}$

(13)

其中, ω_i > 0且Σω_i=1, 令ω^T={ω₁, ω₂, ..., ω_|S|}表示查询向量的非零值向量.开始时, 首先将ω_i设置为$\sqrt {\sum\nolimits_{k = 1}^r {{\mathit{\boldsymbol{r}}_{ik}}^2} } ,$再对q中所有的非零值进行归一化处理, 得到ω_i的初始值.

可重启随机游走模型(random walk with restart)被广泛应用于基于图的推荐模型中, 其基本思想是将推荐问题转化为图顶点相似性计算问题.在异构网络中, 该模型的缺陷是对网络中顶点和边仅仅看作是一种类型, 无法区分异构网络中顶点和边的不同类型^[8].在标签推荐系统中, 也有研究将该模型应用到异构网络中, 证明参数最终趋于收敛^[9], 但其方法并未将异构网络不同维度顶点和边进行同空间映射, 其推荐模型仅适用于具有三维标签数据.本文为了对标签顶点和普通顶点进行区分, 引入多参数马尔可夫链进行建模, 顶点的状态转移函数用公式(14)、公式(15) 表示.

${\mathit{\boldsymbol{t}}^{(t + 1)}} = {\alpha _{VT}}{\mathit{\boldsymbol{P}}_{VT}}{\mathit{\boldsymbol{v}}^{(t)}}$

(14)

${\mathit{\boldsymbol{v}}^{(t + 1)}} = {\alpha _{TV}}{\mathit{\boldsymbol{P}}_{TV}}{\mathit{\boldsymbol{t}}^{(t)}} + {\alpha _{VV}}{\mathit{\boldsymbol{P}}_{VV}}{\mathit{\boldsymbol{v}}^{(t)}} + (1 - {\alpha _{TV}} - {\alpha _{VV}})\mathit{\boldsymbol{q}}$

(15)

从上两式可以看出, 在该模型中, 参数α_VT, α_TV, α_VV和查询向量q直接决定推荐结果.接下来对模型参数进行优化学习, 令a^T={α_VT, α_TV, α_VV}.初始时, t⁽⁰⁾ 和v⁽⁰⁾ 均设置为{0}.

3.3.2 模型参数优化

本文采用BPR(Bayesian personalized ranking)优化框架来构建目标函数^[8].在标签推荐应用场景中, 给定标记对象, 已被标记的标签集合表示为PT, 其余标签集合表示为NT, 则有T=PT∪NT.对于上式中α_VT, α_TV, α_VV参数, 则应满足PT中标签排序比NT中标签排序靠前, 即PT中标签比NT中标签有更大概率被标记到该对象上.采用AUC(area under the roc curve)目标函数对该语义进行建模, 假设总共有m个实例, 则目标函数可表示为

${\max _{\mathit{\boldsymbol{w}},\mathit{\boldsymbol{\alpha }}}}f(\mathit{\boldsymbol{w}},\mathit{\boldsymbol{\alpha }}) = \sum\nolimits_{k = 1}^m {{f_k}(\mathit{\boldsymbol{w}},\mathit{\boldsymbol{\alpha }})} = \sum\nolimits_{k = 1}^m {\frac{{\sum\nolimits_{i \in P{T_k}} {\sum\nolimits_{j \in N{T_k}} {\prod {(\mathit{\boldsymbol{t}}(i) - \mathit{\boldsymbol{t}}(j))} } } }}{{|P{T_k}||N{T_k}|}}} $

(16)

其中, NT_k=T–PT_kΠ(·)为指示函数, t(i)表示通过式(14)、式(15) 得到的标签i的推荐评分, 如果t(i)–t(j) > 0, 则为1, 否则, 为0.指示函数一般定义为不可微的Sigmoid函数σ(x; θ)=1/(1+e^–θx), 其中, 参数θ控制误差, 并通过实验设定.将该函数的对数形式代入式(16), 可得:

${\max _{\mathit{\boldsymbol{w}},\mathit{\boldsymbol{\alpha }}}}f(\mathit{\boldsymbol{w}},\mathit{\boldsymbol{\alpha }}) = \sum\nolimits_{k = 1}^m {\frac{{\sum\nolimits_{i \in P{T_k}} {\sum\nolimits_{j \in N{T_k}} {\ln \sigma (\mathit{\boldsymbol{t}}(i) - \mathit{\boldsymbol{t}}(j))} } }}{{|P{T_k}||N{T_k}|}}} $

(17)

本文采用随机梯度下降法(SGD)计算式(17) 中使目标函数最大化的参数α, 在每一步中, 偏导求解算法按照式(18) 所示梯度进行下降, 其中lr决定了下降梯度的大小.

$\mathit{\boldsymbol{\omega }} \leftarrow \mathit{\boldsymbol{\omega }} + lr\frac{{\partial {f_k}(\mathit{\boldsymbol{\omega }},\mathit{\boldsymbol{\alpha }})}}{{\partial \mathit{\boldsymbol{\omega }}}},\mathit{\boldsymbol{\alpha }} \leftarrow \mathit{\boldsymbol{\alpha }} + lr\frac{{\partial {f_k}(\mathit{\boldsymbol{\omega }},\mathit{\boldsymbol{\alpha }})}}{{\partial \mathit{\boldsymbol{\alpha }}}}$

(18)

接下来计算函数偏导数, 方法如下:

$\frac{{\partial {f_k}(\mathit{\boldsymbol{\omega }},\mathit{\boldsymbol{\alpha }})}}{{\partial \mathit{\boldsymbol{\omega }}}} = \frac{{\sum\nolimits_{i \in P{T_k}} {\sum\nolimits_{j \in N{T_k}} {\frac{{\partial \ln \sigma ({\delta _{ij}})}}{{\partial {\delta _{ij}}}}} } \left( {\frac{{\partial \mathit{\boldsymbol{t}}(i)}}{{\partial \mathit{\boldsymbol{\omega }}}} - \frac{{\partial \mathit{\boldsymbol{t}}(j)}}{{\partial \mathit{\boldsymbol{\omega }}}}} \right)}}{{|P{T_k}||N{T_k}|}},\frac{{\partial {f_k}(\mathit{\boldsymbol{\omega }},\mathit{\boldsymbol{\alpha }})}}{{\partial \mathit{\boldsymbol{\alpha }}}} = \frac{{\sum\nolimits_{i \in P{T_k}} {\sum\nolimits_{j \in N{T_k}} {\frac{{\partial \ln \sigma ({\delta _{ij}})}}{{\partial {\delta _{ij}}}}\left( {\frac{{\partial \mathit{\boldsymbol{t}}(i)}}{{\partial \mathit{\boldsymbol{\alpha }}}} - \frac{{\partial \mathit{\boldsymbol{t}}(j)}}{{\partial \mathit{\boldsymbol{\alpha }}}}} \right)} } }}{{|P{T_k}||N{T_k}|}}$

(19)

在式(19) 中, δ_ij=t(i)–t(j), 由于其为Sigmoid函数, 则有∂lnσ(δ_ij)/(∂δ_ij)=θ(1–σ(δ_ij)), 而θ又可以与参数lr合并, 故可表示为∂lnσ(δ_ij)/(∂δ_ij)=1–σ(δ_ij).最后需计算式(14) 和式(15) 的偏导数, 由q定义可知, ∂q/(∂ω_i)∈R^|V|, 且ω_i对应的值为1, 其余值为0, 计算可得:

$\frac{{\partial \mathit{\boldsymbol{t}}}}{{\partial \mathit{\boldsymbol{\omega }}}} = {\alpha _{VT}}{\mathit{\boldsymbol{P}}_{VT}}\frac{{\partial v}}{{\partial \mathit{\boldsymbol{\omega }}}}$

(20)

$\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial \mathit{\boldsymbol{\omega }}}} = {\alpha _{TV}}{\mathit{\boldsymbol{P}}_{TV}}\frac{{\partial \mathit{\boldsymbol{t}}}}{{\partial \mathit{\boldsymbol{\omega }}}} + {\alpha _{VV}}{\mathit{\boldsymbol{P}}_{VV}}\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial \mathit{\boldsymbol{\omega }}}} + (1 - {\alpha _{TV}} - {\alpha _{VV}})\frac{{\partial \mathit{\boldsymbol{q}}}}{{\partial \mathit{\boldsymbol{\omega }}}}$

(21)

$\left\{ {\begin{array}{*{20}{c}} {\frac{{\partial \mathit{\boldsymbol{t}}}}{{\partial {\alpha _{VT}}}} = {\mathit{\boldsymbol{P}}_{VT}}\mathit{\boldsymbol{v + }}{\alpha _{VT}}{\mathit{\boldsymbol{P}}_{VT}}\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{VT}}}}}\\ {\frac{{\partial \mathit{\boldsymbol{t}}}}{{\partial {\alpha _{TV}}}} = {\alpha _{VT}}{\mathit{\boldsymbol{P}}_{VT}}\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{VT}}}}}\\ {\frac{{\partial \mathit{\boldsymbol{t}}}}{{\partial {\alpha _{VV}}}} = {\alpha _{VT}}{\mathit{\boldsymbol{P}}_{VT}}\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{VT}}}}} \end{array}} \right\}$

(22)

$\left\{ {\begin{array}{*{20}{c}} {\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{VT}}}} = {\alpha _{VT}}{\mathit{\boldsymbol{P}}_{TV}}\frac{{\partial \mathit{\boldsymbol{t}}}}{{\partial {\alpha _{VT}}}} + {\alpha _{VV}}{\mathit{\boldsymbol{P}}_{VV}}\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{VT}}}}}\\ {\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{TV}}}} = {\mathit{\boldsymbol{P}}_{TV}}\mathit{\boldsymbol{t + }}{\alpha _{TV}}{\mathit{\boldsymbol{P}}_{TV}}\frac{{\partial \mathit{\boldsymbol{t}}}}{{\partial {\alpha _{TV}}}} + {\alpha _{VV}}{\mathit{\boldsymbol{P}}_{VT}}\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{TV}}}} - \mathit{\boldsymbol{q}}}\\ {\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{VV}}}} = {\alpha _{TV}}{\mathit{\boldsymbol{P}}_{TV}}\frac{{\partial \mathit{\boldsymbol{t}}}}{{\partial {\alpha _{VV}}}} + {\mathit{\boldsymbol{P}}_{VV}}\mathit{\boldsymbol{v + }}{\alpha _{VV}}{\mathit{\boldsymbol{P}}_{VV}}\frac{{\partial \mathit{\boldsymbol{v}}}}{{\partial {\alpha _{VV}}}} - \mathit{\boldsymbol{q}}} \end{array}} \right\}$

(23)

通过式(20) 和式(21) 可以计算参数w_i(i∈[1, |S|])的微分, 通过式(22) 和式(23) 可以计算参数a_VT, α_TV, α_VV的微分.通过以上过程可以得到优化后的参数ω和α.模型的参数优化过程可表示为算法2.由于已有研究^[8]证明模型参数趋于收敛, 假设该算法经过n次迭代趋于收敛, 则其时间复杂度为O(nm), 推荐模型时间复杂度与参数学习算法2时间复杂度一致.接下来, 将对算法的结果与目前流行算法进行实验对比.

算法 2.标签推荐模型参数学习算法.

输入:m个实例, 下降梯度参数lr;

输出:学习后的参数ω和α.

1.    t=0;

2.   初始化ω⁽⁰⁾ 和α⁽⁰⁾ ;

3.    while f(ω, α) 未收敛  do

4.   对m个实例进行随机洗牌;

5.    Foreach实例k do

6.   按式(14)、式(15) 所示迭代计算向量t和v;

7.   根据式(20)、式(21) 计算∂t/∂w和∂v/∂ω;

8.   更新ω^(t+1) ←ω^(t)+lr(∂f_k(ω^(t), α^(t)))/∂w^(t);

9.   根据式(22)、式(23) 计算∂t/∂a和∂v/∂α;

10.   更新α^(t+1) ←α^(t)+lr(∂f_k(ω^(t), α^(t)))/∂a^(t);

11.    t=t+1;

4 实验与评估

本节首先进行评估指标和实验设计的介绍, 然后进行实验结果的阐述与评估.

4.1 评估指标 4.1.1 准确率

准确率定义为在推荐的Top-K标签集合中, 真正标记在数据上的标签数与推荐集合标签总数的百分比, 其定义如下所示.其中, D表示测试数据集合, R(d)是推荐给数据d的标签集合, T(d)是数据d真实拥有的标签集合.

$P@K = \frac{{\sum\nolimits_{d \in D} {|R(d) \cap T(d)|} }}{{\sum\nolimits_{d \in D} {R(d)} }}$

(24)

4.1.2 召回率

召回率定义为在推荐的Top-K标签集合中, 真正标记在数据上的标签数与数据的真实标签数的百分比, 其定义如下所示.

$R@K = \frac{{\sum\nolimits_{d \in D} {|R(d) \cap T(d)|} }}{{\sum\nolimits_{d \in D} {T(d)} }}$

(25)

4.1.3 平均准确率(mean average precision)

平均准确率(MAP)用来衡量Top-K标签集合的平均准确度, 它用来评测推荐的平均质量, 其定义如下.其中, rel(k)是一个指示函数, 如果第k个标签与真实标签匹配, 则其值为1;否则, 为0.P(k)是前k个标签的匹配比率.

$MAP@K = \frac{{\sum\nolimits_{d \in D} {\sum\nolimits_{k = 1}^K {(P(k) \times rel(k))} /|R(d) \cap T(d)|} }}{{|D|}}$

(26)

4.2 实验设计

本文分别基于二维、三维和五维标签数据对推荐模型进行实验验证, 其中, 二维数据采用豆瓣读书数据^[25], 三维数据采用Delicious数据^[26], 五维数据采用Meetup数据^[8].不同维度数据对比算法设置如下.

豆瓣数据集

(1) TF-IDF.基于信息检索领域的加权技术, 采用统计方法评估标签重要程度.在二维数据集中, 标签权重随其在同一标记对象上被标记次数的增多而增大, 随其被不同标记对象所标记次数的增多而减小.

(2) CF.协同过滤算法, 用到该数据集〈图书, 标签〉二维信息.在标签推荐应用中, 图书间相似度计算的基本思想是:两图书拥有的共同标签数越多, 则二者越相近.用两图书共同标签数除以两图书标签集合大小乘积计算相似度.为了获得较好的推荐结果, 对热门标签评分进行惩罚.

(3) RWR.可重启随机游走算法, 其基于图模型, 根据标签和图书的标记关系构建网络.其基本思想是赋予要推荐的图书较高权重, 并以此顶点为出发点进行随机游走, 以一定概率走到当前顶点的邻居顶点, 以一定概率重新回到出发顶点.最后, 顶点权重分布趋于收敛, 该权重即为标签排序权重.

Delicious数据集

(1) CF.协同过滤算法, 在本数据集中采用〈网页, 标签〉二维数据信息.计算方法与豆瓣数据集基本相同.

(2) RWR.可重启随机游走算法, 在三维数据集中, 该算法不区分顶点和边的不同类型, 将整个网络看作同构网络.其基本思想是赋予被推荐标签的用户和物品较高权重, 并以此二顶点为出发点进行随机游走, 以一定概率走到当前顶点的邻居顶点, 以一定概率重新回到出发顶点.最后, 顶点权重分布趋于收敛, 该权重即为标签排序权重.

(3) OptRank^[9].该算法为目前三维数据标签推荐最优算法, 其基于RWR算法, 引入异构网络信息, 对顶点评分状态转移函数的参数进行学习.

Meetup数据集

(1) CF.协同过滤算法, 在本数据集中采用〈用户, 标签〉二维数据信息.计算方法与豆瓣数据集基本相同.

(2) RWR.在本数据集中基于用户和标签关系图, 用到〈用户, 标签〉二维数据信息, 若用户被某标签标记, 则将二者相连.对于需进行标签推荐的用户, 初始时其权重为1, 其余用户权重为0, 构成查询向量进行求解, 该算法属于基于同构网络方法.

(3) full_RWR.基于RWR进行改进, 在整个网络上运行RWR算法, 不区分不同类型的顶点和边, 是基于同构网络的算法.

(4) HeteRS^[8].适用于基于活动的社会网络数据, 是目前的最优算法.该算法构建异构网络模型, 对每种类型的顶点分别进行建模, 并基于多参数马尔可夫链对参数进行学习.

4.3 实验结果

本节描述针对3种不同标签数据集的实验结果, 并对结果进行量化分析和解释, 对各种算法优劣进行比较.由于TF-IDF和CF算法不是基于图的算法, 运行时间与基于图的算法不处于同一数量级, 不具有可比性, 故运行时间仅对基于图的算法进行比较.

4.3.1 二维异构网络实验结果

实验将豆瓣数据集随机分为8份, 其中1份作为测试集, 其余作为训练集.最终训练集记录有23 378条, 包含3 315本图书信息和6 879个标签信息; 测试集记录数为2 892条, 包含2 012本图书信息.该数据集包含〈图书, 标签〉二维信息, 故无需对信息进行同空间映射, 直接采用推荐模型进行标签推荐.

HnMTR算法与其他3种算法的对比结果如图 1所示, 对准确率、召回率、平均准确率和运行时间4个指标进行评测.由结果可知, HnMTR算法在4个指标上优于其他非基于图的算法70%以上, 总体上优于RWR算法.在二维数据集中, 不进行异构网络同空间映射.HnMTR算法与RWR算法的区别在于:HnMTR算法引入多参数马尔可夫链进行状态转换建模, 并对参数进行学习; 而RWR基于单参数马尔可夫链建模.可见, 多参数马尔可夫链可以更精确地描述顶点的状态转换, 提高推荐结果质量.

从图 1(b)可以发现, 当K=2时, HnMTR算法的召回率与RWR算法相当, 这可能是由于RWR算法在该数据集上的召回率有较好表现.在K=5和K=10时, 以及后续在其他数据集上的实验发现, HnMTR算法的召回率优于RWR算法.在K=5时, HnMTR算法在准确率、召回率和平均准确率上优于CF算法分别为82.58%、73.76%和165.79%;优于RWR算法分别为22.28%、17.79%和9.22%.故HnMTR算法在二维数据集上通过引入多参数马尔可夫链进行建模而提高了算法的精度和效率.

在K=2时, 无论是推荐的准确度还是MAP, RWR和HnMTR基于图模型的算法推荐质量要远远高于TF-IDF和CF算法.对用户而言, 往往仅关注前几个推荐的标签, 所以K较小时的推荐质量更重要.基于图模型的算法虽然运算时间较长, 但推荐结果质量得到大幅提高.此外, RWR和HnMTR都是基于图模型的算法, 由于HnMTR基于多参数马尔可夫链, 参数增多使计算时邻接矩阵规模减小, 进行权重迭代时参数收敛更快, 故运行效率高于RWR, 图 1(d)所示为两种算法运行74个训练实例时间的对比情况(由于部分算法运行时间较长, 本文均采用运行74个训练实例结果进行对比).

4.3.2 三维异构网络实验结果

实验用Delicious数据集, 将数据随机分为8份, 其中1份作为测试集, 其余作为训练集.最终训练集记录有136 883条, 包含9 220个用户, 83 422个网页和35 934个标签; 测试集记录数为17 119条.对于Delicious数据, 包含〈用户, 网页, 标签〉3个维度信息, 需对 < 用户, 网页 > 两种类型顶点进行同空间映射, 使顶点间边的权重可在同一空间进行比较.本实验中, 用户特征信息表示为(访问网页数, 标记标签数), 网页特征信息表示为(访问该网页用户数, 被标记标签数), 被标记顶点类型为网页.将两个特征向量映射到维空间, 由于参数决定顶点间关系的重要程度, 本例中只有〈用户, 网页〉一种类型关系, 无〈用户, 用户〉和〈网页, 网页〉类型的边, 故通过多次实验获取参数, 在训练用户顶点转换向量时, 设置为1;在训练网页顶点转换向量时, 设置为0.01.转换向量的学习结果见表 1.

HnMTR算法与其他3种算法的对比结果如图 2所示, 分别对准确率、召回率、MAP和运行时间4个指标进行评测.从图中可以看出, 不论是准确率、召回率还是MAP指标, HnMTR算法总体上都优于其他算法.如图 2(a)所示, HnMTR算法的准确率比CF算法提高14%以上, 比RWR算法提高11%以上.K值越小, HnMTR算法比其他算法的优势越明显, 因为随着K值的增加, 推荐标签个数大于网页实际标签个数, 准确率整体下降.结果说明, 顶点进行同空间映射后, 各个顶点间关系可直接进行量化比较, 使各个边的权重与实际重要程度更符合, 从而取得更好的推荐结果.HnMTR算法与OptRank算法的结果相当, 而在现实推荐中, 用户更看重K较小时推荐的标签, 而当K=2和K=5时, HnMTR算法的结果优于OptRank算法, 故HnMTR算法的准确率优于目前最先进的算法OptRank.从图 2(b)可以发现, HnMTR算法的召回率优于CF算法68%以上, 优于RWR算法19%以上, 优于OptRank算法1%以上.这说明, HnMTR算法的推荐结果覆盖率高于其他算法, 引入多参数马尔可夫链进行建模后, 对参数的学习更加细化, 使查询向量的设置更加合理, 顶点状态转化概率更加符合实际, 提升了推荐结果召回率.图 2(c)展示了不同算法平均准确率的对比情况, 从图中可以发现, 不论K是否大于实际标签个数, HnMTR算法的平均准确率均高于其他算法, 这说明, 该算法推荐标签的平均质量高于其他算法.图 2(d)展示了算法运行时间, 从图中可以看出, RWR和OptRank算法由于需要维护计算全部顶点和边的状态转移矩阵, 参数收敛较慢, 计算时间较长; HnMTR算法由于对数据进行同空间映射, 网络中有两种类型顶点, 且采用多参数马尔可夫链进行建模, 每个状态转移函数对应状态转移矩阵相对较小, 参数收敛迅速, 大大提高了运行效率.

4.3.3 五维异构网络实验结果

实验用Meetup数据集, 该数据集包含纽约和加利福尼亚两个地点数据, 本文选择纽约市数据进行研究.数据集中包含群体(group)标签和用户(user)标签两种, 本文选择用户作为标记对象进行实验.最终实验数据训练集包含32 443个用户, 15 514个标签, 9 551个事件, 398个群体; 测试集包含2 999个用户.

该数据集包含〈用户, 活动, 群体, 标签, 地点〉5种顶点类型, 故称其为五维异构网络.需要对〈用户, 活动, 群体, 地点〉4个顶点类型进行同空间映射.本文用(参加群体数, 标记标签数, 参与活动数)特征信息标识用户, 用(地点, 时间, 参与群体)特征信息标识活动, 用(成员数量, 举办活动数)特征信息标识群体, 用(举办活动数)特征信息标识地点.将以上特征向量映射到二维空间, 4类顶点信息包含6个顶点对元组, 故设置参数学习方法与三维异构网络一致, 本数据集的结果分别为3×2维、3×2维、2×2维和1×2维矩阵.HnMTR算法与其他4种算法的对比结果如图 3所示.

从图 3可以看出, HnMTR算法的准确率、召回率和平均准确率优于目前最先进的HeteRS算法21%、18%和43%以上.特别地, 在平均准确率评测算法的平均推荐质量方面, HnMTR算法的平均推荐质量比HeteRS的优势更加明显, 因为HnMTR算法经过顶点同空间映射后, 不同类型顶点间的关系可进行量化比较, 在迭代计算顶点权重时, 不同类型顶点的权重更能表征其在整个网络中的实际权重; 而不进行同空间映射的模型在顶点权重迭代计算时, 无法准确比较不同类型顶点权重间的关系.full_RWR算法的推荐质量优于RWR算法, 由于full_ RWR算法虽无法对不同顶点类型进行区分, 也无法度量其权重, 但其引入了不同类型顶点间的关联信息, 从而其推荐质量优于传统的RWR算法.故引入更多数据信息, 可提高推荐质量.图 3(d)对各种基于图模型算法的运行时间进行了比较.发现full_RWR算法最耗时, 由于该算法将所有数据信息维护在一个邻接矩阵中, 每次查询和状态更新都需对整个矩阵进行更新; 且其状态转换方程基于单参数马尔可夫链, 参数收敛较慢.RWR算法由于比full_RWR算法维护较少的数据信息, 其速度较快但推荐质量下降.HeteRS算法基于多参数马尔可夫链, 状态转移邻接矩阵规模较小, 参数收敛较快, 其运行时间小于full_RWR算法.但其需要维护大量的异构顶点信息, 对不同类型的顶点采用不同的状态转换方程计算权重, 权重数值差异较大且需要学习较多参数, 故运行时间大于HnMTR算法.HnMTR算法的运行时间最短, 由于其对异构顶点信息进行了同空间映射, 仅需要学习较少的参数且权重数值可比较, 参数收敛速度快于RWR算法, 故该算法效率较高.

4.3.4 结果分析

HnMTR模型的精确度之所以优于以往模型, 主要包含以下两方面原因.

(1) 通过同空间映射模型在同一维度全面考虑异构网络不同类型顶点信息.

将异构网络不同类型顶点特征信息通过同空间映射方式引入推荐顶点排序过程, 直接影响了模型中不同顶点状态转移的概率, 从而提高了模型精度.

以Delicious数据集为例, 网络中存在3种类型顶点(用户, 网页, 标签), 用户顶点与网页顶点间的权重是用户为该网页打标签的个数, 用户顶点与标签顶点间的权重为标注该标签的次数, 网页顶点与标签顶点间的权重为被该标签标注的次数.用户104、网页26496和标签“photograpy”3个顶点, 权重分别为8, 1, 23, 则在进行状态转移计算时, 不同类型顶点间的权重缺乏可比性, 转移函数系数差异较大.基于第4.3.2节中顶点特征进行顶点同空间映射, 经过参数学习后, 其权重分别为0.2 683 499, 0.0 887 831, 0.6 739 876, 则将其映射到同一度量空间且权重可比较, 状态转移函数计算误差减小, 提高了推荐精度.

(2) 采用多参数马尔可夫链进行标签推荐建模.

多参数马尔可夫链比单参数马尔可夫链可更精确地描述不同类型顶点间的状态转移, 且由于本文针对标签推荐应用建模, 对标签类型顶点进行特殊处理, 凸显其重要性.故能提高标签推荐精度.

以HnMTR模型与OptRank模型在豆瓣数据集运行为例, 网络中存在两种类型顶点(图书, 标签), 图书与标签之间的权重为图书被标注此标签的次数.存在图书《罪责》、《简爱》和标签“外国文学”3个顶点, 经过同空间映射后权重为${w_{{v_1}t}} = 0.7564688,{w_{{v_1}{v_2}}} = 0.8733234,$在OptRank模型中, 顶点状态转移函数为v^(t+1) =(1–α)(P_VVv^(t)+P_VTt(t))+αq, 学习后α值为0.4 447 323, 然而在HnMTR模型中, 顶点状态转移函数为v^(t+1) =α_TVP_TVt^(t)+α_VVP_VVv^(t)+ (1–α_TV–α_VV)q, 学习后α_TV=0.4987676, α_VV=0.1003541.可以看到, 两个参数在进行网络中顶点权重迭代时, 不同类型的顶点, 状态转移概率有所不同, 比单一参数模型可描述更多的数据特征, 更贴近真实世界状态转移机制, 故精度更高.

另一方面, 采用多参数马尔可夫链建模的模型(HnMTR和HeteRS)计算效率总体上高于采用单参数马尔可夫链的模型(RWR和OptRank), 这是由于状态转移函数参数增多, 每个函数进行矩阵相乘时所需搜索的矩阵规模缩小, 效率提高.此外, HnMTR模型的运行效率比未进行顶点同空间映射的模型HeteRS要高, 这是因为经过同空间映射后, 计算所需邻接矩阵数值范围得到有效控制, 多次相乘后数值差异相对较小, 使得计算效率有所提高.

5 总结与展望

本文提出一种基于异构网络的可适用于多种标签数据的标签推荐模型, 该模型的优势在于既能全面包含异构网络不同顶点和边的信息, 又可适用于不同类型不同维度的异构网络.本文将算法应用到具有不同顶点类型数量(本文称其为维度)的标签数据, 并将应用该模型的推荐结果与当前主流算法进行对比, 对比算法包括目前商用最经典的算法、基于同构网络的最优算法及其改进算法和针对特定顶点类型种类的基于异构网络算法.本模型的推荐准确率、召回率和平均准确率指标均优于商用经典算法和基于同构网络的推荐算法, 在绝大多数情况下优于基于异构网络的推荐算法, 从总体上达到较好的推荐结果.此外, 基于本模型的推荐算法运行效率也比其他基于网络模型的推荐算法要高.未来, 一方面将进一步对模型其他参数进行学习, 使模型计算结果更加准确; 另一方面对算法基于数据中心集群进行并行设计, 进一步提高运行效率, 争取获得实时的推荐结果.