0 概述

目前, 推荐算法可分为基于内容^[1-2]和协同过滤^[3-4]2种类型。基于内容的推荐算法给用户推荐已购物品相似度较大的物品, 但仅考虑到物品内容在一维空间中的相似度, 导致推荐效果较差。协同过滤推荐算法是目前主流的推荐算法, 如k近邻算法和随机游走算法^[5-7]，但无法适用于用户历史记录较少的情况, 即无法解决数据稀疏性问题, 对没有历史记录的用户更加难以推荐, 且在数据集规模较大时, 计算开销大。

针对上述问题, 本文提出一种自适应混合协同过滤推荐(Adaptive Hybrid Collaborative Filtering recommendation, AHCF)算法。运用基于张量的相似度计算物品间的相似度, 以目标用户为起点, 通过多步路径跳转找到候选物品, 使用贝叶斯概率计算评分得到物品排名, 从而得到物品推荐结果。

1 相关工作

个性化物品推荐是推荐系统的核心问题。物品推荐算法可分为基于内容的推荐算法和协同过滤推荐算法。协同过滤推荐算法主要通过考察用户对物品的购买记录、评论信息和标签信息等内容来计算用户与用户之间及物品与物品之间的相似度, 从而更好地为用户推荐相关商品^[8]。然而, 用户之间或者物品之间相似性依赖历史记录。当一个系统刚开始启动时, 协同过滤算法存在稀疏性问题, 因此结合协同过滤推荐算法与基于内容的推荐算法被提出。一种方法是分别用多种推荐方法得到推荐结果, 再采用某种算法将其混合。如投票机制^[9-10]。一种方法是以某种推荐策略为框架混合另外的推荐策略, 如在协同过滤推荐的框架内混合基于内容的推荐^[11]。然而, 上述混合方式都不能缓解系统稀疏性的问题。

基于内容的推荐算法是将物品表示成词向量, 并度量物品间的相似度, 给用户推荐最可能感兴趣的物品。然而一维向量表示方法忽略了内容各个属性间的关联关系。例如, 在电影数据集上, 导演詹姆斯·卡梅隆总和科幻性电影联系在一起, 当一部电影由詹姆斯·卡梅隆导演, 即使没有指明其类型, 但如果有关联关系, 仍可以推断这是一部科幻电影。而这种关联关系不能通过一维相似度计算。张量分解是一种特征抽取方法。文献[8]对用户物品标签三元组构造张量, 使用tucker分解求解得到用户的抽象表示, 核心张量蕴含了各属性间的关联, 且考虑了物品与标签的共现关系。因此可利用张量分解来挖掘内容之间的内部关系。

协同推荐方法通常考虑建立一个由用户和物品构成的二部图^{[3, 12]}, 并在此二部图上进行用户与物品之间的相似度计算。文献[13]提出经典SimRank算法, 其基本思想是“跟相似物品相关的物品也是相似的”, 它定义了节点间相似度度量方法, 然后用迭代方法求得最终所有节点的相似度。文献[5]提出3种基于随机游走的评分算法, 分别计算从一个用户出发经过三步或五步游走后得到的物品排名信息。对于加入标签信息的三部图上的协同过滤算法也有大量的研究。比如文献[14]将二部图上的基于传播模型的推荐算法拓展到三部图中, 定义一个简单的线性叠加来结合用户与物品、物品与标签二部图的传播, 该集成方法能够提供更准确、多样和新奇的推荐。文献[15]提出基于标签的物品推荐算法, 通过先降维再融合, 将用户、物品和标签的三维关系划分为3个二维关系, 最后再将这些关系进行融合。然而, 基于图结构的协同过滤算法的缺点在于数据量较大时对内存的要求较高且时间效率较差，如SimRank、随机游走^[6]等都需要足够的内存空间和计算资源以处理大量节点的邻接矩阵。使用抽样的方法能够解决效率问题^[5], 但抽样会导致推荐质量的下降。文献[16]提出一种从目标用户出发的三步路径法, 使用贝叶斯范式计算候选物品评分, 降低了计算开销。本文将该方法拓展到三部图上, 其有较好的推荐性能。

2 自适应混合协同推荐算法

问题定义如下:用户集合U={u₁, u₂, …, u_m}, 物品集合I={i₁, i₂, …, i_n}(每个物品都具有特定属性)和标签集合T={t₁, t₂, …, t_k}构成三部图, 如图 1所示, 其多元关系包括:用户打标签的行为, 用户对物品的购买记录以及物品被标签标注的行为。推荐任务是基于三部图上的多元信息为每个用户个性化推荐可能感兴趣的物品。自适应混合协同推荐模型框架如图 2所示。

2.1 自适应调整的加权混合模型

协同过滤方法对于评论和购买记录较少的不活跃用户以及刚进入系统的新物品推荐效果较差。为此, 引入基于内容的物品相关性计算来自适应地缓解冷启动问题。自适应主要指算法能根据目标用户的活跃度和推荐物品的新鲜度来自动调节基于内容的推荐在混合模型中的权重。用户的活跃度和物品的新鲜度定义如下:

定义1   (用户u的活跃度)一个用户u的活跃度反映了用户的活跃程度, 历史记录越多, 活跃度越高, 其定义为:

$\eta (u) = \frac{2}{{1 + {{\rm{e}}^{ - {N_r}(u)/\alpha }}}} - 1$

(1)

其中, N_r(u)表示用户u的物品历史记录个数, α是一个调节参数, 用于调整用户记录数对活跃度的影响程度。

定义2   (物品i的新鲜度)一件物品i的新鲜度反映了该物品受用户的关注程度, 它被购买记录越多, 新鲜度越低, 其定义为:

$\varphi (i) = 2 - \frac{2}{{1 + {{\rm{e}}^{ - {N_r}(i)/\beta }}}}$

(2)

其中, N_r(i)表示物品i的被交易记录个数, β也是一个调节参数, 用于调整物品被交易记录数对物品新鲜度的影响程度, 其由数据集确定。

对一个物品i而言, 将其推荐给用户u的得分可计算如下:

$r(u,i) = \omega (u,i) \cdot {r_t}(u,i) + (1/\omega (u,i)) \cdot {r_c}(u,i)$

(3)

其中, r_t(u, i)为基于内容的推荐将物品i推荐给用户u的推荐得分, r_c(u, i)为协同推荐将物品i推荐给用户u的推荐得分, ω(u, i)是混合基于内容的推荐算法的自适应权重。

ω(u, i)主要考虑用户的活跃度和物品的新鲜度以及它们的组合关系对权重值的影响。随着用户的活跃度提高或者物品新鲜度的降低, 基于内容的推荐评分所占权重ω(u, i)的分数逐渐降低, 其计算公式如下:

$\omega (u,i) = \frac{{\gamma \cdot \varphi (i)}}{{\eta (u)}}$

(4)

其中, γ是一个调整因子, 本文设为1。

2.2 基于张量的内容推荐分析

在混合模型中, 基于内容的关联度推荐是对协同过滤方法的重要补充, 因此挖掘物品的内容信息十分关键。文献[8]方法仅基于词向量空间模型, 把所有关键词映射到一个向量空间, 且每一个物品可以表示成i_i={w_1i, w_2i, …, w_ni}, 那么物品i_i与i_j的相似度可以用余弦相似度来度量。但这种一维空间上的词向量表达不仅浪费空间, 且无法解析和发现物品本身的不同特征之间的关系。本文使用一种基于张量分解的方法来对物品之间的相似性进行计算, 将物品中包含的多维共现信息表示成张量, 然后用张量分解方法提取物品的抽象特征。具体来说, 首先将物品表示成一个N阶张量 X ∈ ℝ^{I₁×I₂×… ×I_N}, 每一维表示一个属性。例如电影可以有类型、导演、演员等多个属性的表示。I_i表示属性i的所有取值的集合大小。张量 X 与矩阵 U ∈ ℝ^J×I_i的mode-i乘法用 X ×_i U 表示, 且结果是一个I₁×I₂×…×I_i－1×J×I_i+1×… ×I_N大小的张量。本文使用Tucker分解方法^[17]将物品张量 X 分解成一个与原张量维度相同的核心张量 ϑ ∈ ℝ^{J₁×J₂×… ×J_N}和每个维度上的因子矩阵 A ⁽ⁱ⁾∈ ℝ^I_i×J_i进行mode-i矩阵乘法近似表达, 即:

$\mathit{\boldsymbol{X}} \approx \mathit{\boldsymbol{\vartheta }}{ \times _1}{\mathit{\boldsymbol{A}}^{(1)}}{ \times _2}{\mathit{\boldsymbol{A}}^{(2)}} \times \cdots { \times _N}{\mathit{\boldsymbol{A}}^{(N)}}$

(5)

核心张量是一个和原张量维度一样但是每一维上的特征小得多的张量, 它代表了各个属性的隐式因子间的关系, 每个维度上的因子矩阵 A ⁽ⁱ⁾代表该属性上的特征与隐式因子间的关系。例如, 电影网络可以表示成1个4阶张量, X ∈ ℝ^{I₁×I₂×I₃×I₄}, 其中每个维度分别表示电影、导演、演员、类型。经过Tucker分解后, 核心张量是一个d×d×d×d的张量, 且d是比较小的常数, 而每一个因子矩阵是d×I_n大小的矩阵, 表示张量在某一个属性维度上的子空间。假设 A ⁽¹⁾代表了电影子空间因子矩阵, 那么用 ϑ ×₁ A ⁽¹⁾来表示所有电影的特征张量, 它是一个I₁×d×d×d大小的张量, 每一个电影可以用d×d×d的特征张量表示。假设有电影 T₁和 T₂, 那么 T₁和 T₂的相似度为:

$sim\left( {{\mathit{\boldsymbol{T}}_1},{\mathit{\boldsymbol{T}}_2}} \right) = \frac{{\sum\limits_{i,j,k} {t_{ijk}^1} \cdot t_{ijk}^2}}{{\left\| {{\mathit{\boldsymbol{T}}_1}} \right\|\left\| {{\mathit{\boldsymbol{T}}_2}} \right\|}}$

(6)

其中, t_ijk表示张量中第(i, j, k)个元素, 从而可以计算出所有物品之间的相似度。

2.3 三部图上的短路径枚举算法

本文数据集有用户、物品以及标签3种实体, 且3种实体间有不同的关系连接。为解决协同推荐方法的效率随着用户及物品规模的增长而降低的问题，本文采用一种短路径枚举叠加方法。该方法以目标用户为起点, 通过多步路径跳转找到候选物品, 使用贝叶斯概率计算评分得到物品排名从而进行推荐, 大幅提高了基于图模型的推荐算法效率且保证了推荐质量。三部图模型涉及的关系较多, 每个用户的邻居节点包括物品和标签, 用户之间的连接可以通过物品或者标签, 也可以同时通过一个物品标签对。因此, 本节将讨论并比较包含多类型关系的三部图之上的2种短路径枚举方法。图 3所示为三部图上的多种短路径枚举法的拓展图模型。

从图 3(a)可以看出, 由目标用户出发, 根据该用户的邻接节点, 包括选择过的物品和打过的标签, 并找到共享这些物品或标签的用户, 再将这些用户的所有邻接物品找出来。对于每一条路径上的目标物品, 用贝塔分布来计算他们的评分, 对于目标物品相同的路径, 叠加该目标物品的得分。物品的评分是该物品的正面评分的概率。假设物品v的正面概率θ_v的分布服从贝塔分布, 即θ_v~Beta(a, b), 那么$\frac{a}{{a + b}}$即为所有物品正面概率的平均值, 而对于某一个物品v来说, 它的正面率又与其本身的正面评分与负面评分相关, 假设该物品正面和负面评分的分别个数有| R_v⁺ |和| R_v ^－|, 并且为避免该物品没有评分的情况, 调整该物品的正面率如式(7)所示。

${p_v} = \frac{{a + \left| {R_v^ + } \right| + 1}}{{a + b + \left| {R_v^ + } \right| + \left| {R_v^ - } \right| + 1}}$

(7)

通过上述方法, 可以统计图信息, 根据候选物品的路径评分叠加得出所有待推荐物品的得分。对于用户u的从物品v出发到用户w再到物品x一条路径ρ(u, v, w, x), 其得分为:S_{ρ(u, v, w, x)}=P_x。对于经过标签的路径同理可求。

分享共同物品或者共同标签的用户数量实际上是很普遍的, 将他们选取为路径中的节点无法判断用户与目标用户是真的兴趣相投还是只是因为偶然性。因此, 考虑一种共享物品标签对的路径方法, 从而提出第2种高维扩展方法。如图 3(b)所示, 将路径中的第1步到达节点更改为物品与标签二元组, 可以认为共享物品和标签的二元组信息的用户是更相似的, 这种物品与标签共现的信息很大程度上去除了大量偶然相关用户, 提高推荐物品的相关性。这种情况下第2个节点的评分与基本扩展类似, 从而该条路径的评分是终点物品的评分。假设用户u通过 < i_k, t_i > 二元组找到用户v, 计算用户v的历史物品i_l的得分为:S_{ρ(u, < ik, ti > , v, il)}=P_il。

图 4描述了短路径枚举方法的示意图, A 代表用户与物品标签的邻接矩阵, 对于用户与物品(标签)有交互的点设置为1, 没有交互的设置为0, A ^T代表 A 的转置，P 是用户与物品的交互矩阵，矩阵相乘之后即为最终的预测矩阵 R 。

2.4 算法描述

本文算法伪代码具体如下：

输入  物品的内容信息, 用户物品评分矩阵 M , 用户物品邻接矩阵 A

输出  所有用户的推荐结果r

//生成基于内容的推荐评分矩阵

1.构造物品的内容张量T;

2.ϑ×₁A⁽¹⁾×₂A⁽²⁾×…×_NA^(N)= Tucker(T);

3.item=ϑ×₁A⁽¹⁾;

4.itemSimMatrix=calSimMatrix(item);

5.canMatrixByCon=calCanList(itemSimMatrix, M);

//生成短路径枚举法推荐评分矩阵

6.itemScore = cal(M);

7.P = construct(M, itemScore);

8.canMatrixBySP=A×A^T×P;

//自适应混合, 输出推荐结果r

9.for j=1 to m do

10.calculate users’ activeness;

11.for k=1 to n do

12.calculate items’ freshness;

13.calculate w(j, k);

14.for i=1 to m do

15.for j=1 to n do

16.if M(i, j) = 0

17. r(i, j)=w(i, j)×canMatrixByCon(i, j)+(1/w(i, j))×canMatrixBySP(i, j);

具体步骤描述如下:

步骤1  根据物品的内容构造张量, 例如根据电影名称、导演、演员、类型构造一个四维张量, Tucker分解后得到电影的低维稠密向量表示, 第4行和第5行与传统基于内容的推荐类似, 通过构造物品相似度矩阵, 生成预测结果。

步骤2  使用基于短路径枚举的方法生成预测结果。具体来说, 利用统计学方法为每个物品计算评分, 并使用图 4计算最终的预测矩阵。

步骤3  将前2个步骤的结果自适应混合。第9行~第13行计算所有用户的活跃度和所有物品的新鲜度以及对应的权重。对于每一个用户, 遍历其所有未交互的物品, 根据权重计算自适应评分, 生成最终推荐结果。

3 实验结果与分析 3.1 实验设置 3.1.1 数据集描述

本文分别在Movielens、doubanbook这2个真实数据集上进行实验, 前者为公开数据集, 后者爬取自豆瓣读书。表 1所示为2个数据集的相关信息描述。另外，对于基于内容的属性选取部分, Movielens数据集中选取的属性是电影名称、导演、演员和类型, doubanbook选取的属性是书籍名称、作者、类别、关键词。

本文使用留出法进行评估, 数据集中每个用户抽取80%的记录作为训练集, 其余作为测试集。

3.1.2 评价指标

本文使用的评价指标包括:Top-N结果的准确率P_N以及平均准确率均值(MAP)。

${P_N} = \frac{{\left| {L_u^N \cap T_u^ + } \right|}}{N}$

(8)

其中, L_u^N代表用户u的Top-N顺序推荐列表, T_u⁺代表用户u测试集中正面评价物品集, N代表推荐数目。

$MAP = \frac{1}{N}\sum\limits_{i = 1}^N {\frac{{\sum\limits_{j = 1}^{{m_i}} p (j) \times rel(j)}}{{\left| {T_i^ + } \right|}}} $

(9)

其中, N代表用户的数量, p(j)是截止排名从1~j的准确率, rel(j)是一个指数函数, m_i是用户i的推荐列表总数。

3.2 基于张量的内容对比

在基于内容的推荐部分, 将本文提出的基于张量的内容推荐与传统的基于词向量的内容推荐(RSV)进行比较。如表 2和表 3所示, 本文算法在2个数据集上准确率分别平均提升19.12%和34.4%，平均准确率均值分别提升91.5%和49.2%。其中, MAP是用户数量为10的平均准确率均值。该结果验证了基于张量挖掘内容相似度的算法的有效性。

3.3 短路径方法与以往方法的对比

在基于短路径的推荐算法的性能评估部分, 本文提出的2种短路径枚举算法(SP1和SP2)基于用户与物品以及标签的交互, 与基于协同过滤的方法相似, 因此将SP1和SP2与经典UserKNN和随机游走(RW)算法进行对比。UserKNN^[18]是一个标准的基于用户k近邻的协同过滤算法。本文实验将k设置为3。随机游走算法通过构造用户、物品和标签的邻接矩阵, 并根据典型的随机游走的原理实现推荐。SP1和SP2是分别是2.3节中提出的2种短路径枚举算法。

表 4和图 5分别给出4种方法在推荐数为10的准确率和运行时间开销对比。从表 4可以看出，本文提出的2种短路径枚举算法在2个数据集上准确率都明显优于UserKNN和RW。其中, SP1算法在2个数据集上较UserKNN提升了225.2%和118.8%, SP2算法在2个数据集上有提升但效果不明显。SP1效果要好于SP2, 这是因为SP1找到的路径列表其实是包含SP2包含的路径列表, 它的统计信息更能反映用户的偏好, 但显然需要更多的时间开销。图 5给出4种算法在时间性能上的比较。可以看出，SP1和SP2的时间性能优势明显, 在Movielens中SP1和SP2时间优化最高, 较UserKNN和RM分别达到了9.53倍、13.09倍和21.89倍、29.17倍。UserKNN由于对于每个用户都需要遍历整个数据集的用户计算相似度花费大量时间, RW由于需要在大规模矩阵中多次迭代计算产生了大量的时间消耗，SP1和SP2用3个矩阵相乘得到最后的预测评分矩阵。

3.4 混合模型

由于在3.3节的实验结果表明了基于短路径枚举算法第一种模型性能优势明显, 因此本文使用第1种短路径枚举模型作为混合模型中的协同过滤部分。

3.4.1 α和β对准确率的影响

表 6和表 7给出在Movielens上不同稀疏度数据集中设置不同的α和β准确率的变化。在表 6中, 抽取总数据集中20%的记录作为训练集, 此时用户和物品的平均记录数分别为100和20, 可以看出，当α和β设置为100和20时, 准确率达到最高。在表 7中, 抽取总数据集80%的记录作为训练集, 此时用户和物品的平均记录数约为300和60, 可以看出，当α和β设置为300和60时, 精确度达到最高。因此, 在混合计算之前, 首先判断当前数据集的用户与物品的平均记录数, 将α和β分别设置为对应值。同理，doubanbook也根据上述方法设置。

3.4.2 结果分析

本文对比了3种混合算法, 分别是CBCF、AHCF-basic和AHCF。

CBCF是一个经典的混合推荐算法^[19], 其目的是解决数据稀疏性问题，该算法利用基于内容的预测来构造伪评分矩阵, 并在伪评分矩阵上进行基于用户的协同推荐。

AHCF-basic即AHCF的简化版, 其不考虑用户的活跃度和物品的新鲜度, 只是简单地将基于内容评分和基于短路径枚举方法的得分等权加和。

AHCF是本文提出的自适应混合模型, 即考虑用户活跃度和物品新鲜度并且自适应调整2种方法比重的算法。

表 8和表 9反映了2个数据集上3种混合方法的精确率比较。可以看出, 2个数据集上AHCF算法准确率较高。在Movielens中, AHCF较CBCF和AHCF-basic在P₁上提升幅度最大, 分别提升21.4%和30.8%。在doubanbook中, AHCF较CBCF和AHCF-basic在P₉提升最多, 可达28.6%和63.6%。

为验证AHCF处理数据稀疏性问题，本文依次随机选择原始数据集中每个用户的10%、20%、30%、50%、80%的记录作为训练集, 剩余部分作为测试集，选择CBCF, AHCF-basic和AHCF进行比较，且用户数量为10。图 6展示了2个数据集上3种算法的准确率对比结果。可以发现, AHCF在数据稀疏性不断变化的过程中始终处于领先位置。这是因为当数据集较稀疏时, 用户和物品的记录都很少, 使用短路径枚举的方法无法获得足够的统计信息。同时，需要增大基于内容的评分比重, 用于修正短路径枚举方法带来的偏差。CBCF由于使用了内容预测的方法来填补了评分矩阵, 一定程度上也缓解了稀疏性问题。然而这种填补方法很有可能偏离用户的真正兴趣。同时固定权值的AHCF-basic进一步验证了AHCF的合理性和有效性。

4 结束语

本文提出一种动态自适应混合协同推荐算法。该算法结合基于内容的推荐方法, 通过基于张量的相似度计量方法来计算物品间相似度, 在此基础上, 采用短路径叠加方法大幅提高了算法的效率。在2个真实数据集上的实验结果表明, 该方法不仅推荐准确率较高, 而且能够节省计算开销。