基于二部图的推荐方法中, 随机游走算法应用较广。文献[6]中建立用户-项目二部图随机游走方法(Bipartite Graph Projection and Ranking, BGPR), 并根据用户与关联项目的情况, 在项目间随机游走、排序并进行推荐, 解决了数据稀疏和冷启动的问题; 但该算法中用户与项目之间的边为对称边, 不能体现用户兴趣。文献[7]利用资源分配原理, 对用户关联的项目个数和项目被用户关联的个数进行权重的二次分配, 建立体现用户和项目特征的不对称用户-项目二部图, 提高推荐的准确性; 但这种方法也仅仅考虑到了用户和项目的关联关系, 没有考虑到其他信息。文献[8]将用户对项目的评分信息加入到二部图中, 建立更加体现用户兴趣的不对称用户-项目二部图随机游走方法(Bipartite Graph Projection and Ranking based on User Interest, IN-BGPR), 进一步提高算法的准确性。文献[9]在二部图中加入对用户行为的分析, 通过用户行为的分析, 产生相似用户的条件, 根据条件进一步改进用户-项目二部图推荐算法, 在提高推荐结果准确性的同时提高了算法效率。

在二部图推荐算法中有大量用户、项目以外的信息没有得到充分分析, 有学者^[10,11]提出建立用户-项目-标签三部图推荐算法(Tripartite Graph Projection and Ranking, TGPR), 利用物质扩散过程计算相似用户, 再根据相似用户进行项目推荐, 在电影推荐和社交网络好友推荐中得到应用。但由于用户信息、标签等信息过于稀疏, 该算法存在大量缺失信息。文献[12]利用张量分解的模型表示信息, 不仅表示三部图的信息, 还可以表示三部图中丢失元素的信息, 该方法改善了推荐结果的召回率和准确率。文献[13]利用标签进行主题分布计算, 通过主题分布细化的用户分类, 可以更精确地计算用户间相似度, 提高推荐结果的相似度。文献[14]通过引入标签和资源的热门惩罚机制, 对用户-标签-资源三元关系的初始张量进行重新定义, 该方法在社交网络环境下可以有效提高推荐的准确性。

以上方法通过物质扩散或加入标签信息优化图推荐方法, 推荐结果有一定程度上的改善。但目前的图推荐方法主要分析用户与项目、项目与类别之间的关系, 缺少用户之间、用户与类别之间关系的深层分析。针对以上问题, 本文提出一种结合条件型游走的四部图推荐方法:

(1) 构建两个二部图, 第一部分为用户-项目二部图, 在这-部分放弃传统的二部图随机游走方法, 定义用户-项目二部图上的游走条件, 提出基于条件型游走的用户间推荐度计算方法; 第二部分为项目-类别二部图, 在这一部分采用随机游走的方法;

(2) 通过用户-项目-类别三部图映射用户-类别二部图, 进一步提出类别-用户-项目-类别四部图的个性化项推荐算法。在MovieLens数据集上通过平均准确率、平均绝对偏差、平均召回率、平均覆盖率这4种指标对该方法进行验证, 实验结果表明, 基于条件型游走的四部图推荐方法改善了推荐结果。

传统的三部图主要选择用户与评分项目, 以及评分项目与类别的关系, 建立用户-项目-类别三部图$D(U,I,G,{{E}_{1}},{{E}_{2}})$, 其中, $U=({{u}_{1}},{{u}_{2}},{{u}_{3}}\text{,}\cdot \cdot \cdot ,{{u}_{m}})$表示用户节点, $I=\left\{ {{i}_{1}},{{i}_{2}},{{i}_{3}},\cdot \cdot \cdot ,{{i}_{n}} \right\}$表示项目节点, $G=\{{{g}_{1}},{{g}_{2}},{{g}_{3}},\cdot \cdot \cdot ,{{g}_{r}}\}$是项目类别节点, E₁表示用户节点到项目节点的边集合, E₂表示项目节点到项目类别节点的边集合。采用随机游走的方式在三部图上进行游走, 三部图及游走方式如图1所示。

图1中, 将三部图划分为用户-项目二部图S₁、项目-类别二部图S₂。S₁中用户集U_i以概率P_i随机游走到项目I_i, 在S₂中再随机游走到G_i; 将G_i包含的I_i进行排序, 推荐给目标用户集U_i。在S₁、S₂的部分仅考虑用户与项目之间的选择关系、项目与类别之间的隶属关系, 没考虑到用户对项目的评分、项目的度关联关系, 也忽略了用户和类别之间的关联关系。在用户-项目边上加入评分信息作为权重, 如图2所示。由于用户对项目评分的高低不同、项目评分对用户之间的关系影响、项目自身的度、类别的度等都体现了不同的用户兴趣和偏好。

因此, 本文在用户-项目的二部图S₁中加入游走条件, 使用户对项目的游走不再是随机的, 而是根据假设条件进行有目的游走; 通过项目-类别二部图S₂从项目随机游走到类别; 再通过用户-项目二部图S₁和项目-类别二部图S₂, 建立用户-类别二部图S₃, S₃通过类别体现用户兴趣。最后, 结合用户-项目关系、项目-类别关系以及用户-类别的关系建立类别-用户-项目-类别四部图并进行项目推荐。

基于图模型的随机游走是一种无规则的任意游走方式, 用户训练出最佳重启动概率后随机选择下一步要游走的项目。由于每一次游走重启动概率相同, 游走在固定尺度上具有相同的结构, 每次游走的方向也是任意的。在用户-项目间的二部图上游走时采用一种条件型游走策略^[15], 即满足某种条件才向某一方向运动, 每一步的游走不是随机的, 而是确定和唯一的。这种游走方式目标更明确, 游走效率更高。游走条件的原理体现的是用户兴趣和项目的影响力。本文定义的游走条件有两个:

(1) 项目的度越小, 越能体现对应用户的兴趣偏好;

(2) 高评分的项目更能体现用户兴趣。

在用户-项目二部图部分根据以上两个条件进行游走。

如图1的S₁部分所示, 假设目标用户集U_i的已评分项目集为$I=\left\{ {{i}_{1}},{{i}_{2}},{{i}_{3}},\cdot \cdot \cdot ,{{i}_{n}} \right\}$,根据条件1和条件2, 计算下一目标游走概率P_i如公式(1)所示。

${{P}_{i}}=\frac{{{C}_{i}}}{{{D}_{i}}},i\in N$ (1)

其中, C_i为目标用户对项目i的评分, D_i为项目I_i的度, P_i为游走概率, 即为优先策略选择依据, P_i的值越大, 被下一步游走选择的概率越大。

按照P_i的值由大到小对集合I中所有项目进行排序, 值最大的P_i为下一步游走的目标项目。若出现两个项目的P_i值相同, 则以度优先规则, 游走到D_i值最大的项目; 若D_i值也相同, 则认为两个项目条件相同, 随机游走到任意项目。

如图2的S₁部分所示, 若选择U₁用户为目标用户, U₁的已评分项目集为$\left\{ {{I}_{1}}\mathrm{,}{{I}_{2}}\mathrm{,}{{I}_{3}} \right\}$, 根据公式(1)计算${{I}_{1}}\mathrm{,}{{I}_{2}}\mathrm{,}{{I}_{3}}$的P_i分别为: P₁=3/1, P₂=4/3, P₃=1/3。P₁值最大, 则下一次U₁用户游走的项目为I₁。

建立基于条件游走的四部图推荐方法(Quadripartite Graph Based on Conditional Walk, CWQG), 如图2所示, S₁部分计算P_i, 训练游走次数, 游走结束后, 产生项目集${I}'=\left\{ {{{{I}'}}_{1}},{{{{I}'}}_{2}},{{{{I}'}}_{3}}\cdot \cdot \cdot ,{{{{I}'}}_{n}} \right\}$, ${I}'$∈$I${Invalid MML},, 是在用户产生行为的集合中根据条件随机游走产生的项目集。为更好地计算用户兴趣, 根据图2和游走项目集${I}'$计算目标用户集U_i与类别的关系, 建立用户-类别二部图S₃。

从目标用户集U_i出发, 到G_i有连通边记为1, 无连通边记为0, 同时将三部图重新映射为用户-类别二部图S₃, 如图3所示。

图3为对称二部图, 结合图2更新图3中边权重, 用户经过项目${I}'$到类别的度W(g)计算方法如公式(2)所示。

$\mathrm{W(}g\mathrm{)}=\mathop{\sum }^{}{{e}_{ig}}$ (2)

e_ig的取值如公式(3)所示。

${{e}_{ig}}=\left\{ \begin{align} & 1,\ \ \ ig\in {{E}_{2}} \\ & 0,\ \ \ ig\notin {{E}_{2}} \\ \end{align} \right.$ (3)

其中, 从目标用户集U_i到项目集${{{I}'}_{i}}$再到类别集G_i节点存在连通的边, e_ig为1; 反之, e_ig为0。

根据图2和图3更新后的加权用户-类别二部图如图4所示。结合图2和图4, 建立基于条件游走的四部图, 如图5所示。

对目标用户集U_i到类别G_i的W(g)进行排序, 取Top-N类别为用户最感兴趣的类别集合Gin。根据Gin集合, 在S₂中产生目标用户候选项目集I₀。

由于各类别包含的候选项目个数不同, 类别的度越大, 说明包括用户感兴趣的项目数量较多。所以依据推荐步长和类别包含的项目数量比例, 产生最终推荐项目集${{I}_{f}}$的方法如公式(4)所示。

${{I}_{f}}=\frac{W({{G}_{i}})}{\mathop{\sum }_{1}^{N}W({{G}_{i}})},N\in Top-N$ (4)

其中, W(G_i)为目标用户映射的每一类别的度。

目标用户对推荐项目的预测评分如公式(5)所示。

${{P}_{u,j}}=\overline{{{R}_{u}}}+\frac{\sum\nolimits_{j=1}^{n}{sim(i,j)\cdot ({{R}_{u,j}}-\overline{{{R}_{u}}})}}{\sum\nolimits_{j=1}^{n}{\left| sim(i,j) \right|}}$ (5)

其中, $\overline{{{R}_{u}}}$为用户u所有评分的平均值, n为前n个最近邻。当R_u,j = 0时, 令${{R}_{u,j}}-\overline{{{R}_{u}}}$= 0。$sim(i,j)$为i和j项目的相似度, 计算步骤如下:

(1) 在S₁中计算项目之间的相似度, 如公式(6)所示。

${{\sigma }_{ij}}=\frac{1}{deg(j)}\sum\nolimits_{\text{u}\in \text{U}}{\frac{{{r}_{ui}}{{r}_{uj}}}{deg(u)}}$ (6)

其中, $deg(j)$表示项目j的度即项目j的连边个数, r_ui表示用户u对项目i的评分, U表示项目i与项目j的共同用户集合, $deg(u)$表示用户u的度即用户u的连边数。

(2) 在S₂中计算项目之间的相似度, 如公式(7)所示。

${{\rho }_{ij}}=\sum\nolimits_{u\in U}{\frac{{{r}_{ui}}{{r}_{uj}}}{deg(j)deg(u)}}$ (7)

其中, $deg(j)$表示项目j所有连边的边权之和(边权即评分), $deg(u)$表示用户u的所有边权之和, r_ui表示用户u对项目i的评分。

(3) 用参数λ调整i、j项目的相似度, 调整方法如公式(8)所示。

$Sim(i,j)=\lambda \ {{\rho }_{ij}}+(1-\lambda ){{\sigma }_{ij}}$ (8)

经过以上分析, 基于条件游走的四部图推荐方法描述如下:

输入: 用户集合U, 项目集合I, 项目类别集合G, 边集合E₁和E₂;

输出: 目标用户u游走到项目j的概率排序。

①构建用户-项目-类别三部图$G(U,I,G\text{,}{{E}_{1}},{{E}_{2}})$。

②在用户-项目-类别三部图中,对于用户-项目二部图S₁, 加入评分作为权重, 同时根据公式(1)计算用户集U_i游走到项目I_i的概率P_i。

③根据步骤②的规则训练S₁中游走的最佳重启动次数。

④重复步骤②和步骤③, 得到用户-类别加权二部图, 图中权重为用户经过项目到类别的累计次数和。

⑤建立类别-用户-项目-类别四部图, 统计类别-用户二部图中权重, 并按权重值从大到小进行排序。

⑥根据步骤⑤的结果, 取Top-N类别, 结合S₂产生Top-N类别对应的项目候选集I_o。

⑦根据推荐步长和公式(4)产生推荐项目集I_f 。

⑧根据公式(5)-公式(8)计算推荐项目预测评分。

实验采用MovieLens^[16]100k数据集, 该数据集由GroupLens研究组收集和整理, 包含943名用户对1 682部电影的100 000多个评分, 评分取值为1-5, 每个用户至少有20个评分。使用5折交叉验证法对提出的改进算法进行验证。

实验通过二部图随机游走算法(BGPR)、加权二部图随机游走算法(IN-BGPR)、三部图随机游走算法(TGPR)与本文提出的条件型游走四部图算法(CWQG)进行对比, 同时采用平均准确率(Precision)、平均绝对偏差(Mean Absolute Error, MAE)、平均召回率(Recall)以及平均覆盖率(Coverage)^[10,17]对4种算法的实验结果进行对比评价。

(1) 平均准确率表示对于目标用户给定的推荐列表中, 在测试集上出现的物品个数占推荐列表大小的比例, 准确率依赖于推荐列表的长度, 且值越大推荐效果越好, 计算方法如公式(9)所示。

$Precision=\frac{\mathop{\sum }_{u\in U}\left| L(u)\bigcap T(u) \right|}{\mathop{\sum }_{u\in U}\left| L(u) \right|}$ (9)

其中, L(u)为用户u的推荐列表, T(u)为用户u推荐列表中出现在测试集中的物品。

(2) 通过计算预测评分与实际评分差值的绝对值可以衡量预测评分的准确性, MAE值越大, 表明误差越大, 推荐精度越低; 反之, MAE值越小, 表明误差越小, 推荐精度越高, 计算方法如公式(10)所示。

$MAE=\frac{\mathop{\sum }_{i\in T(u)}|{{R}_{ui}}-{{P}_{ui}}|}{|T(u)|}$ (10)

其中, R_ui表示用户u对项目i的实际评分, P_ui表示用户u对项目i的预测评分, T(u)表示测试集中用户u评分的项目集合。

(3) 平均召回率表示对于目标用户给定的推荐列表中, 在测试集上出现的物品个数占测试集大小的比例, 召回率也依赖推荐列表的长度, 且值越大推荐精度越准确, 计算方法如公式(11)所示。

$Recall=\frac{\mathop{\sum }_{u\in U}\left| L(u)\bigcap T(u) \right|}{\mathop{\sum }_{u\in U}\left| T(u) \right|}$ (11)

其中, L(u)为用户u的推荐列表, T(u)为用户u推荐列表中出现在测试集中的物品。

(4) 平均覆盖率表示最终的推荐列表占总物品集合的比例, 反应了算法发现长尾的能力, 覆盖率值越大说明算法越能将长尾推荐给用户, 计算方法如公式(12)所示。

$Coverage=\frac{\left| {{U}_{u\in U}}T(u) \right|}{\left| I \right|}$ (12)

其中, U为用户集, I为物品集, T(u)为给每个用户推荐一个长度为N的物品列表。

由于本文的CWQG算法以及对比算法TGPR算法需要训练公式(6)中的加权参数λ, 故设置参数λ从0到1以0.1为间隔, 分别在Precision、MAE、Recall及Coverage指标下进行训练, 不同λ参数对应的4种指标值如图6所示。

由图6可以看出, 当λ取值为0.5时, Precision、Recall及Coverage的值达到最佳效果, MAE在0.5-0.6之间已经趋于平稳。故取加权参数λ的值取0.5。

在算法描述的步骤③中, 需要训练用户-项目二部图游走的最佳重启动次数, 实验中的最佳重启动次数如图7所示。

由图7可以看出, Precision、Recall及Coverage三种指标都显示重启动次数为600时达到最佳效果, MAE在300之前较低, 400-600趋于平稳, 600以后明显上升, 故重启动次数选取为600次。

4种算法在数据集上, 根据推荐步长的推荐效果如图8所示。由Precision指标可以看出, CWQG算法准确率最高。说明采用条件型的二部图游走方法较普通的二部图随机游走方法能更准确地定位用户兴趣; 同时加入类别-用户关系的四部图推荐方法较三部图推荐方法增加了用户兴趣的维度, 也更好地体现了用户兴趣。但随着推荐步长的增加, CWQG的准确率逐步降低, 笔者分析是由于数据稀疏造成的, 因为推荐步长越大, 数据稀疏度就越大。

由MAE指标可以看出, CWQG算法的MAE最低。随着步长的增加MAE略有升高, 但变化不大, 而另外三种算法, 在推荐步长由20变化到40时MAE有较大升高。说明CWQG算法在MAE上的稳定性最好, 适用于不同步长的推荐系统。

由Recall指标可以看出, CWQG算法的Recall最高, 且随着推荐步长的增加逐步提高。另外三种算法在推荐步长为40-60时, Recall无明显提高, 在推荐步长80-100时三部图推荐算法才有明显提高。说明CWQG算法在小步长推荐上有明显优势, 同时也适用于不同步长的推荐系统。

由Coverage指标可以看出, CWQG算法的Coverage最高, 且明显高于其他三种算法, 推荐步长越长, 推荐的长尾能力越强。长尾能力是用户个性化需求的体现, 说明CWQG中游走条件的定义及类别-用户的关系映射能够更好地体现用户的个性化需求。

综上, 本文提出的基于条件型游走的四部图推荐方法(CWQG)在提高推荐准确率和命中率的同时提高了推荐的覆盖率, 使推荐更多样化, 避免了给不同用户推荐相同商品的单一推荐模式, 是一种更加个性化的推荐方法。