基于社交上下文和神经网络的增量推荐算法

邹 锋

(广州商学院 信息技术与工程学院，广东 广州 511363)

0 引 言

经典的协同过滤推荐系统通常使用k-近邻(k-nearest neighbor，k-NN)技术[1]寻找和目标用户(或项目)最相似的top-k用户(或项目)，然后为目标用户推荐其近邻用户偏爱的项目。矩阵分解[2]是一种推荐系统的经典方法，大数据情况下矩阵运算的效率较低。基于内存的推荐系统又分为基于用户的推荐方式和基于项目的推荐方式[3]，基于项目的推荐方式比基于用户推荐方式的准确率高，前者倾向于向用户推荐相似的项目，而这会引起严重的“马太效应”[4]。

为了在保证高推荐准确率的前提下，降低推荐项目的马太效应，许多学者设计了改进算法以提高推荐结果的多样性、新颖性以及推荐列表满意度。文献[5]需要迭代地寻找推荐列表的帕累托最优解，虽然实现了理想的指标，但是其计算效率较低。与文献[5]属于同一类型的算法还有：基于多目标粒子群的系统[6]、基于布谷鸟搜索的系统[7]和基于狮群优化算法的系统[8]等。另一方面，通过结合成熟的聚类技术来提高推荐的多样性也是一种有效手段，文献[9]设计了基于模拟退火的聚类技术对项目进行精准的分类处理，通过模拟退火的优化技术保证了聚类结果的多样性，由此提高推荐结果的多样性。与文献[9]属于同一类型的算法还有：基于去中心化聚类的推荐系统[10]、基于增量回归模型的推荐系统[11]、基于关联规则和聚类处理的推荐系统[12]等。上述推荐系统均能够有效提高推荐效果，但计算时间较长，每当数据发生较大变动均需要重新训练全部数据集，无法满足推荐系统的实时性需求。

词嵌入模型在许多应用领域中表现出良好的性能，如词嵌入在文本情感分类方面的应用[13]。神经网络语言模型(neural network language model，NNLM)是一种性能突出的词嵌入方法，能够精确地根据上下文预测出当前词。本文将用户个人档案、显式反馈信息和隐式反馈信息作为上下文，利用NNLM预测特定上下文偏爱的项目列表。将NNLM运用于推荐系统需要解决两个难题：首先，需要建模NNLM的上下文结构，本文设计了层次用户档案模型，并提出相应的快速相似性度量方法；再者，神经网络的训练计算量较大，为此本文设计了一种增量学习技术，加快神经网络的训练速度。

1 建立词嵌入的上下文

1.1 建立用户档案序列

每个用户表示为一个项目集和一个评分集，通过以下步骤为每个用户建立一个上下文序列：

步骤1 分析用户评分项目的信息，将这些边际信息补充到用户的个人档案内。

为每个项目关联一个函数e，其返回值是该项目相关的元素集，表示为函数e:I×R→I×Tk，k为每个项目相关的元素数量，T表示元素。

步骤2 将项目集转化为元组形式。

步骤3 将整型符号排列成序列。

序列生成函数f视为上述3个函数的级联组合，表示为f=s∘t∘e。例如：电影《让子弹飞》的ID为1，用户u对它评分5分。使用函数e获取该电影的类型信息，发现电影ID=1有两个类型：类型=7,10，函数e的输出为元组(1, {{剧情, 5},{探险, 5}})。使用函数t获得这些元组的符号序列，然后将电影类型转换成ID形式，产生新的元组(1, {75, 105})。最终，仅需要分析用户u评分的项目元组，即(75,105)。

1.2 提取用户间相同子序列

不同用户的档案序列之间可能存在大量重复的元素，因此从n个给定的序列中提取出最长的相同子序列∑=(σ1,…,σs)。设序列α的子序列为β，β由α的元素[1, |β|]构成。采用动态规划求解该问题，如算法1所示，该算法逐渐填充(m+1)×(n+1)矩阵的元素，m和n分别为序列x和序列y的长度，其计算式为

(1)

式中：L[m,n]记录了两个序列间的最大相同子序列长度。原序列的时间复杂度和空间复杂度为O(mn)，提取子序列后的空间复杂度降至O(m)或者O(n)。根据两个序列的最长相同子序列评价两个用户的相似性。

算法1：基于序列的相似性度量算法(SSM)。

输入：序列x, 序列y。

输出：L[m,n]

(1)L[0…m, 0…n]=0；

(2)fori={1…m} do

(3) forj= {1…n} do

(4) ifxi==yithen

(5)L{i,j} =L[i-1,j-1]+1；

(6) else

(7)L[i,j]=max(L[i,j-1],L[i-1,j])；

(8) endif

(9) endfor

(10)endfor

为了运用SSM算法度量推荐系统的相似性，提出了基于SSM的上下文正则化算法，如算法2所示。算法2对算法1进行了两点修改：引入变换函数f和匹配阈值δ。其中，δ越高说明相似用户的差异越大，该阈值根据具体应用场景设定；变换函数则为1.1小节介绍的f函数。

算法2：推荐系统的SSM计算算法。

输入：用户u, 用户v, 变换函数f，阈值δ

输出：L[m,n]

(1) (x,y)←(f(u),f(v))

(2)L[0…m, 0…n]←0；

(3)fori={1…m} do

(4) forj={1…n} do

(5) ifmatch(xi，yi,δ) then

(6)L{i,j} =L[i-1,j-1]+1；

(7) else

(8)L[i,j]=max(L[i,j-1],L[i-1,j])；

(9) endif

(10) endfor

(11)endfor

1.3 相似性归一化处理

SSM相似性的范围为[0, min(|f(u),f(v)|)]，但协同过滤系统的相似性指标取值范围一般为[-1, 1]或[0, 1]。通过式(3)的归一化技术处理SSM相似性值

simf,δ(u,v)=SSM(u,v,f,δ)

(2)

(3)

SSM算法的计算成本较高，在推荐之前离线计算SSM相似性，推荐系统可以透明地利用这些相似性值。

2 Top-N推荐系统

2.1 Top-N推荐系统的模型

假设u为用户集U中的一个用户，推荐系统的目标是从项目集I中选出推荐给u的列表。协同过滤推荐系统利用用户-项目的交互数据，如评分、评论和浏览时间等。将用户u对项目i的评分设为rui，未评分的情况rui记为0。Iu表示用户u评分的项目集，Ui表示对项目i评分的用户集。Top-N推荐的目标是为用户提供N个项目的列表。

2.2 基于内存的推荐系统

协同过滤技术依赖相似的用户集或项目集，常用k-近邻(k-NN)技术寻找和目标用户(或项目)最相似的top-k用户(或项目)。基于用户(或项目)推荐系统的输出定义为

(4)

(5)

式中：s表示用户(或项目)之间的相似性，即第1小节的SSM，rui和ruj分别表示用户u对项目i和j的评分。

3 基于词嵌入的推荐系统模型

3.1 词嵌入表示

prod2vec[14]是一种基于项目嵌入的产品推荐模型，该模型利用了矩阵分解技术，无法运用于基于内存的推荐系统。本文设计了新的词嵌入推荐系统，同一个用户评分的项目之间具有一定的相关性，而对同一个项目评分的用户之间也存在一定的共性。下文以基于项目的协同过滤系统为例，基于用户的推荐系统与之相似。本文将连续词袋模型(CBOW)[14]和协同过滤top-N推荐系统结合，将推荐系统项目作为CBOW的词，用户个人档案(以及显式、隐式反馈信息)作为CBOW的上下文，CBOW根据上下文预测其偏好的词。利用CBOW模型主要出于两点考虑：①其计算效率较高，高于Skip-gram等模型；②推荐系统存在稀疏性问题和冷启动问题，CBOW模型对输入上下文平均化处理，产生平滑的概率估计，能够缓解评分信息不足的情况。

图1所示是本文推荐系统的神经网络结构。网络隐层学习训练样本集，每个训练样本是一个目标项目和上下文数据，上下文是对该项目评分的用户相关信息。每个用户的训练样本数量设为|Iu|，输入层由上下文向量{x1,…,xi,xi+1,…,x|Iu|}组成。

图1 嵌入协同过滤系统的主要结构

隐层神经元数量设为d，隐层采用线性激活函数。输入层和隐层间的连接权重表示为矩阵W∈|I|×d，矩阵每一行vj表示项目j第d维的输入向量。项目i的隐层输出设为hi，hi的计算式为

(6)

输出层的神经元数量为|I|，输出层采用softmax激活函数。隐层和输出层间的权重设为W′∈d×|I|，权重每一列v′i是项目i的d维输出向量。输出层的输入为v′iTh，输出值y是目标上下文的后验分布。采用softmax激活函数计算后验分布的概率，softmax激活函数的计算式为

(7)

通过最小化以下的损失函数来训练神经网络

(8)

(9)

3.2 正则化处理

单隐层网络中失活正则比L2正则的效果好，因此采用失活处理解决过拟合问题。在训练阶段，运用失活机制，随机失活一定数量的单元，失活概率为p。因为本文主要学习矩阵W的权重，因此在测试阶段无需正则处理。

3.3 推荐系统的实现方法

(1)失活机制在推荐系统的实现

原CBOW模型的输入是文本语料库，输出是词向量，窗口参数w控制上下文的词数量。本文建立一个上下文文档表示每个用户的信息，为了将全部用户的信息作为上下文，窗口w设为wmax来覆盖全部的用户信息。因为将全部用户档案的平均值作为输入，所以无需考虑档案的顺序。

本文修改超参数w，在输入层增加失活处理。如果w小于用户档案序列的最大长度，那么系统将一部分信息作为上下文，将其它信息失活。该w参数和失活率p成比例关系。

(2)推荐系统的相似性度量

使用式(3)计算用户(或项目)间的相似性，采用k-NN寻找用户(或项目)的近邻。本文采用NN-descent[15]代替传统的k-NN算法，NN-descent的计算效率远高于经典的k-NN算法。

3.4 神经网络的增量训练方法

推荐系统首先使用后向传播技术随机初始化矩阵W和W′，学习这两个矩阵的参数。这不是凸优化问题，因此通过梯度下降法寻找其局部最优解。实际应用中数据连续不断地发生变化，随时可能加入新的评分信息、新的用户或者新的项目，本文设计了增量的系统更新方法，从而避免重新训练神经网络。当加入新项目的时候，在W中增加行，在W′中增加列，随机初始化新加入的行和列，因为矩阵内其它的向量接近局部最优解，所以系统的收敛速度较快。

4 实验与结果分析

实验的硬件环境为：Intel 酷睿i7 9700 K，CPU主频为3.6 GHz，8个核心，16 GB内存。软件环境为：Window 10操作系统，基于Python编程实现推荐算法的算法。

4.1 实验方法

(1)实验数据集和预处理

采用从GroupLens网站获取的MovieLens数据集进行实验验证，Movielens_20M数据集由20 000 263个评分构成，评分范围从0.5星到5星。为了支持半星的评分，本文将项目的ID乘以100，评分值乘以10，例如：用户u对项目1的评分为3.5星，那么语句预处理的结果为1×100+3.5×10=135。表1所示是实验数据集的基本信息，随机划分80%的子数据集作为训练集，剩下的20%作为测试集，分别独立划分5次，完成5折交叉验证。推荐列表的数量设为5，即top-5推荐系统。

表1 实验数据集的基本信息

(2)性能评价指标

本文考虑了多个指标全面地评价推荐系统多个方面的性能。

1)排列质量和推荐准确率

采用4个指标评价推荐系统的推荐准确率，分别为归一化折损累计增益nDCG[16]、精度P[16]、召回率R[15]和平均精度均值MAP[16]。nDCG用来衡量排序质量，精度P和召回率R分别用来衡量推荐项目的命中率和查全率。

2)新颖性：

EPC(expected popularity complement)[17]：定义为期望的新出现推荐项目数量。

EPD(expected profile distance)[17]：推荐项目和用户偏爱项目间的距离。

3)多样性：

α-nDCG[18]：多样性感知的排列指标。

EILD(expected intra-list diversity)[18]：期望的列表内多样性。

4.2 神经网络超参数的选取

通过5折交叉验证训练本文神经网络模型，训练以最大化nDCG为目标，每组实验完成100次迭代。因为w是本文网络的关键超参数，通过试错法调节w，将神经网络对Movielens_20M数据集进行实验，结果如图2所示。图中显示随着w值的升高，每次迭代所需的时间升高，且nDCG收敛曲线的质量也提高，当w=50之后，nDCG收敛曲线质量的提升幅度较小，但处理时间升高明显，所以选取w=50为最佳参数。

图2 神经网络w参数的实验

最终获得神经网络对于Movielens_20M数据集的最佳超参数值，见表2。

表2 神经网络超参数设置

4.3 SSM相似性验证实验

本文提出了新的SSM相似性度量指标，一方面该指标的计算效率较快，另一方面该指标的精度也较好。采用经典基于内存的协同过滤推荐算法和不同的相似性度量指标集成为不同的推荐系统，采用每个推荐系统独立地完成实验。本文SSM的参数δ设为5和10，将两种参数的指标分别简记为SSM1和SSM2，γ参数统一设为10。选择3个常用相似性度量指标和本文方法比较，分别为余弦相似性Cosine、Jaccard相关性和JMSD[19]。

图3所示是每个相似性度量指标对推荐系统的影响实验结果。图中可见余弦相似性和Jaccard的效果十分接近，且明显好于JMSD指标。本文指标受所选取参数的影响较大，总体而言，SSM2的效果好于SSM1，且略好于Cosine指标和Jaccard指标，Cosine指标和Jaccard指标均为广义的距离度量方法，难以对推荐系统所需的细节信息做深度开发，因此在推荐系统的应用效果差于本文的相似性度量方法。SSM2引入了匹配阈值δ，δ越高说明相似用户的差异越大，由于Movielens_20M数据集的数据量较大，δ=10的效果好于δ=5。本文将选用SSM2作为相似度度量方法。

图3 SSM相似性实验

4.4 推荐系统的性能

测试本文推荐系统在静态完全训练下的推荐性能。将本文推荐系统与下面的算法进行比较，评估各算法的性能：

SocialMF[20]：结合用户之间的信任关系，学习用户和项目的潜在特征向量，是一种基于矩阵分解的方法。

SocialSVD[21]：根据人际关系中的六度分隔理论计算用户之间信任度，填充用户信任矩阵，是一种基于奇异值分解的方法。

MIF[22]：根据互信息评价相似性，是一种基于内存的协同过滤推荐算法。

RNNN[23]：通过循环神经网络根据过去的交互信息预测用户未来的偏好项目，是一种基于会话相似性的协同过滤算法。

TIUII[24]：通过分析隐式反馈信息建立信任模型，并且设计了信任传播机制，是一种基于内存的协同过滤推荐算法。

图4所示是各个推荐系统对于Movielens_20M数据集的实验结果。MIF和RNNN均实现了较好的排列质量和推荐准确率，本文算法略高于这两个算法。SocialMF和SocialSVD是两个以分析社交关系为核心的推荐系统，由于Movielens_20M数据集中包含的社交关系极少，所以这两个算法并未获得理想的效果。观察新颖性实验结果和多样性实验结果，本文算法的新颖性和多样性均实现了显著的提高，将图4和图3比较，可以发现本文词嵌入模型有效地提高了基于内存推荐系统的新颖性和多样性。

图4 静态推荐系统实验

4.5 增量推荐实验

支持增量地更新神经网络模型是本文算法的一个特色，因此通过实验评估本文增量推荐系统的性能。将数据集随机划分为4个大小相等的分区，首先对第1个分区进行完全训练，并且对模型进行验证实验。然后将第2个分区和第1个分区结合，进行重新训练(重新训练的迭代次数为400次)，该模型的测试结果记为“重新训练”模型；另外以第1个分区训练的网络为基础，采用增量训练技术训练第2个分区的模型，分别对增量学习20次、40次、60次迭代的网络进行了测试实验。第3个分区、第4个分区采用和第2个分区相似的方式完成增量训练实验，结果如图5所示。

图5 增量推荐实验

图5中可看出，随着训练数据分区的增加，系统的性能逐渐提高；随着迭代次数的增加，神经网络的性能也明显提高。比较不同迭代次数的nDCG值，可发现增量训练的模型在40次迭代已经和重新训练的模型十分接近，而重新训练需要300次迭代，因此本文的增量训练方法能够节约巨大的时间开销。

5 结束语

本文在离线预处理阶段，将用户的个人档案、显式反馈信息和隐式反馈信息建模为序列格式的上下文，并设计了基于序列的相似性度量方法。将用户个人档案、显式反馈信息和隐式反馈信息作为上下文，利用NNLM预测特定上下文偏爱的项目列表。本文的增量训练能够通过较少的迭代次数即可达到局部最优解，在牺牲少量推荐性能的情况下，大幅度地降低了训练时间，能够较好地解决用户和项目变化剧烈的推荐问题。本文系统目前仅考虑了基本的反馈信息，未来将重点研究时域信息、社交关系信息等和本文推荐系统的集成方法。