0 引言

随着互联网的飞速发展，人们在互联网平台上的活动越来越频繁，信息推荐在网络中发挥的作用也越来越重要。在电子商务领域，商品推荐根据客户的注册信息、商品信息以及客户对商品的反馈信息等分析客户的偏好，模拟销售人员向其提供商品购买建议，从而提高电子商务交易量。在社交网络领域，好友推荐系统能够为用户建立复杂的人际关系网络图谱，向用户推荐可能认识的好友或群体，扩展用户的交际圈，最终提高用户对于社交平台的满意度。在网络媒体领域，由于新闻资讯数量呈爆炸式增长，广大读者受到了信息过载问题的困扰，新闻推荐通过分析读者的行为记录(浏览、分享、点赞、评论等)，识别读者的兴趣点，向他们推荐其感兴趣的内容，在读者目的不明确的情况下，大大提高了其信息获取的效率，缓解了信息过载问题。

基于k近邻的推荐算法^[1-3]是一种常用的推荐模型，可以分为基于用户近邻的推荐算法和基于项目近邻的推荐算法。基于用户近邻的推荐算法主要分为以下步骤：根据用户的特征计算两两用户之间的相似度；针对目标用户，找到与之最相似的用户近邻集合；在估计目标用户对某一项目的评分时，利用近邻集合中用户对该项目的评分，通过相似度加权，来预测目标用户的评分。

基于项目近邻的推荐算法与基于用户近邻的推荐算法原理大致相同，区别在于基于项目近邻的推荐算法通过计算项目之间的相似度来完成预测和推荐。两种方法的适用场合不同，在实际应用中，需要结合具体的场景进行选择。在一些系统中，项目的数量较为稳定且远远小于用户的数量，此时计算项目之间的相似度更节省时间，适合采用基于项目近邻的推荐算法。但是还有一些系统，如新闻推荐系统和微博推荐系统，项目的更新速度要远远高于系统中用户的更新速度，且数量也要远远超过用户的数量，此时适合选择基于用户近邻的推荐算法。因此需要具体问题具体分析，根据系统的实际需要选取合适的推荐算法。

k近邻推荐算法的关键在于评分特征提取和相似度计算。基础算法将原始高维稀疏的评分作为用户和项目的特征，采用余弦相似度进行计算，最后根据相似度最高的k个近邻进行评分预测和推荐。这种方法存在空间消耗大、相似度计算不精确、相似近邻选取效率低等缺点。近年来，国内外学者针对上述关键点进行了不同的改进。在特征提取方面，文献[4-6]分别采用主成分分析(Principle Component Analysis, PCA)和奇异值分解(Singular Value Decomposition, SVD)对数据进行降维，提高相似度计算速度和相似近邻选取效率，但是PCA降维方法假设评分数据之间是线性的，而实际中的数据可能是非线性的。在相似度计算方面，经典的相似度计算方法有余弦相似度、皮尔森相关系数和修正的余弦相似度等^[7]，后续工作大都在这些基础上改进，文献[8]对相似度加权方法进行改进，文献[9]对项目属性相似度和评分相似度进行动态组合，文献[10]引入Tanimoto系数进行相似度计算，这些改进能够提高评分预测的准确率，但都是在原始评分特征上进行的，特征降维以后，这些相似度计算方法便不再适用。另外，上述方法没有考虑评分冷启动问题(在评分数据过于稀疏或没有评分数据时，无法进行准确推荐)，且在推荐过程中仍然需要大量的相似度计算，不能真正提高推荐效率。

针对上述问题，本文融合了评分数据、用户属性数据和项目类别数据，采用堆叠降噪自编码(Stack Denoising Auto-encoder, SDA)神经网络对上述数据进行非线性降维，引入精确欧氏局部敏感哈希(Exact Euclidean Local-Sensitive Hash, E²LSH)快速检索算法进行相似近邻检索，并改进了相似度计算方法，在保证推荐效率的前提下，缓解了评分冷启动问题。

1 相关理论 1.1 堆叠降噪自编码网络

降噪自编码器(Denoising Auto-Encoder, DAE)是由Vincent等^[11]提出的一种由输入层、隐藏层和输出层组成的三层神经网络，输出层是对输入层的重构，输入层到隐藏层是编码器，隐藏层到输出层是解码器。DAE向输入层数据中加噪，在学习过程中去噪，这样能够消除干扰特征提取的噪声，学习到的特征更具有代表性。SDA是一种特殊的深度神经网络^[12]，其网络结构可认为是对称的，前半部分从输入层到中间层逐层编码，后半部分从中间层到输出层逐层解码，因此通常网络层数为2L+1，如图 1所示。

SDA的第l层隐层到下一层和第2L－l+1层隐层到下一层构成一对编解码器，编码函数和解码函数分别如式(1) 和式(2) 所示：

$ {\mathit{\boldsymbol{h}}_{l + 1}} = {f_l}({\mathit{\boldsymbol{W}}_l}{\mathit{\boldsymbol{h}}_l} + {\mathit{\boldsymbol{b}}_l}) $

(1)

$ {\mathit{\boldsymbol{h}}_{2(L{\rm{ + 1)}} - l}} = {g_l}({\mathit{\boldsymbol{W}}_{2L - l + 1}}{\mathit{\boldsymbol{h}}_{2L - l{\rm{ + }}1}} + {\mathit{\boldsymbol{b}}_{2L - l{\rm{ + }}1}}) $

(2)

其中: f(·)和g(·)分别为编码器和解码器函数，通常采用sigmoid函数，其自变量为网络参数W和b。W_l是第l层与上一层之间的权重，W_l和W_2L－l+1互为转置，由编码器和解码器共享，称为一对捆绑权重^[12]。h_l和h_2L－l+1分别是编码器和解码器的输入向量，b_l和b_2L－l+1是偏置向量。

SDA的训练过程分为预训练和微调两个阶段。预训练将每一对编码器和解码器都当作一个DAE进行训练，通过随机梯度下降法最小化单个DAE的损失函数，如式(3) 所示，得到预训练参数。微调阶段利用预训练参数作为网络的初始化参数，通过后向传播算法最小化损失函数，如式(4) 所示，得到最终的网络参数。在这种深度神经网络结构下，在预训练阶段，每一个DAE可以看作是一种无监督的预训练过程，依次进行。由于当前DAE的输入是前面DAE的隐层值，因此，只有当前面的DAE训练好后，才能开始当前DAE的训练。具体的训练步骤将在第2章中详细阐述。

$ \begin{array}{l} {\rm{ }}C({\mathit{\boldsymbol{h}}_l}, {\mathit{\boldsymbol{h}}_{2(L + 1) - l}}) = - {\mathit{\boldsymbol{h}}_l}\ln ({\mathit{\boldsymbol{h}}_{2(L + 1) - l}}) + \\(1 - {\mathit{\boldsymbol{h}}_l})\ln (1 - {\mathit{\boldsymbol{h}}_{2(L + 1) - l}}) \end{array} $

(3)

$ C(\mathit{\boldsymbol{x}}, \mathit{\boldsymbol{x'}}) = \mathit{\boldsymbol{x}}\ln (\mathit{\boldsymbol{x'}}) + (1 - \mathit{\boldsymbol{x}})\ln (1 - \mathit{\boldsymbol{x'}}) $

(4)

$ \mathit{\pmb{x}}' = {g_1} \circ \cdots \circ {g_L} \circ {f_L} \circ \cdots \circ {f_1}(\mathit{\pmb{x}}'') $

(5)

其中:C(h_l, h_2(L+1)－l)是预训练阶段的损失函数，C(x, x′)是微调阶段的损失函数，x″是加噪后的输入，h_l是网络第l层的数据，当l=0时，h_l分和h_2(L+1)－l分别为整个网络的输入x和输出x′。

1.2 精确欧氏局部敏感哈希算法

局部敏感哈希(Local-Sensitive Hash, LSH)算法是一种近似近邻搜索策略^[13]，能够得到近似却高效的候选结果，这往往比低效精确的策略更具实际意义。LSH的基本思想是以较大的碰撞概率保证空间中的相似点哈希到同一个哈希桶中，同时过滤掉不相似的点以减少相似性计算，从而快速检索到相似近邻。E²LSH是对LSH的一种改进^[14]，通过基于p稳态分布的LSH函数对数据进行哈希表示，使相似的数据哈希到同一个桶中的概率更高。

位置敏感哈希函数族是LSH算法的基础，是根据一组由点域S到数集域U的映射函数定义的，用E={e:S → U}表示。随机选取哈希函数族E中的一个，对于数据点t, v∈R^d，如果满足下列条件，则E即为位置敏感哈希函数族。

若‖t－v‖ < d₁，则P[e(t)=e(v)]>P₁；

若‖t－v‖>d₂，则P[e(t)=e(v)] < P₂。

其中，P[·]表示t和v的哈希值取等时的概率，0 < d₁ < d₂，0 < P₂ < P₁ < 1。上述条件表示随着数据点之间距离的增大，其碰撞概率减小，即数据点哈希到同一桶中的概率减小。

与LSH不同的是E²LSH采用基于p稳态分布的哈希函数族。假定一个实数集R上的分布D，对于任意n个实数γ₁, γ₂, …, γ_n与D的一组独立同分布随机变量X₁, X₂, …, X_n，如果存在p≥0，使得$\sum\limits_{i = 1}^n {{\gamma _i}{X_i}} $和${(\sum\limits_{i = 1}^n {{{\left| {{\gamma _i}} \right|}^p}} )^{1/p}}$ X同分布，其中随机变量X服从D分布，则称D为p稳态分布。基于p稳态分布的哈希函数族中每个函数的表达形式如(6) 式所示：

$ {e_{a, b}}(\mathit{\boldsymbol{v}}) = \left\lfloor {\mathit{\boldsymbol{a}} \cdot \mathit{\boldsymbol{v}} + b/w} \right\rfloor $

(6)

其中:a是从R上的p稳态分布中随机取样构成的d维向量，b是从[0, w]上的均匀分布中随机取样得到的随机数，$\left\lfloor \cdot \right\rfloor $表示向下取整。函数e将d维向量v映射成一个整数，作为该向量的哈希值。由p稳态分布的定义可知，向量v在a方向上的投影av与‖av‖_pX同分布，X服从p稳态分布。哈希函数e_{a, b}(v)的几何意义如图 2所示，a方向上的实线以w为间隔进行分割，将投影a·v+b所处的间隔作为向量v的哈希值。

E²LSH为了提高相似点碰撞概率的同时，降低不相似点的碰撞概率，拼接k个哈希函数得到哈希函数族Φ={φ:S→T^k}，其中φ(v)=(e₁(v), e₂(v), …, e_k(v))。由于随机选取哈希函数使得单一哈希表精度不够^[15]，所以随机均匀选取Φ中的L个函数φ₁(v), φ₂(v), …, φ_L(v)，构造L个哈希表对数据进行处理，将数据存储在L个哈希表中的不同桶中。E²LSH通过主次哈希函数e′₁和e′₂对进一步降维后的数据进行处理，形成索引键。具体计算方法分别如式(7) 和式(8) 所示：

$ {e'_1}({t_1}, {t_2}, \cdots, {t_k}) = ((\sum\limits_{i = 1}^k {{m_i}{t_i}} )\bmod prime)\bmod N $

(7)

$ {e'_2}({t_1}, {t_2}, \cdots, {t_k}) = (\sum\limits_{i = 1}^k {{{m'}_i}} {t_i})\bmod prime $

(8)

其中：m_i和m′_i为随机整数，prime为大素数，通常取2³²-5。主哈希函数为哈希表中每个点建立唯一整数值索引Value，结合主次哈希函数为每个哈希桶建立索引键(Value, Index)，其中Index由次哈希函数确定。

2 基于数据降维和E²LSH的k近邻推荐算法

本章首先给出基于数据降维和E²LSH的k近邻推荐算法基本流程，然后对其中的关键技术逐一进行详细阐述。

2.1 基本流程

本文方法的基本流程如图 3所示，对基础k近邻推荐算法进行了改进，主要包括数据降维、相似近邻检索和评分预测三部分。

1) 数据降维。通过SDA神经网络对评分数据和用户/项目标签数据融合后所形成的高维稀疏向量进行非线性降维，得到低维稠密的用户/项目特征向量。

2) 相似近邻检索。利用精准欧氏局部敏感哈希算法为降维后的数据构建索引，通过检索得到目标用户或项目的近似近邻集合。

3) 评分预测。计算目标用户或项目与相似近邻之间的相似度，利用相似近邻的评分记录，通过相似度加权来预测未知评分。

2.2 基于神经网络的数据降维

在计算用户或项目之间的相似度时，若采用原始评分作为特征，随着推荐系统中用户数和项目数的不断增多，特征维度将急剧增加，从而降低运算效率，甚至造成维数灾难，因此对评分数据进行降维十分必要。传统的PCA和SVD降维是一种线性模型，而推荐系统中的数据可能是非线性的，因此本文引入自编码神经网络作为一种非线性降维方法。自编码神经网络有深层和浅层之分，前者能够拟合更复杂的函数，降维后得到的特征更具有代表性^[16]。所以本文采用深层网络——SDA对评分数据和标签数据进行非线性降维。训练步骤如下：

1) 确定SDA的网络结构，设置输入层维数、隐藏层个数、各隐藏层维数以及各层的加噪比例。然后融合评分数据和用户/项目标签数据，对数据加噪后以向量的形式作为SDA的输入。

2) 训练第一层DAE，即图 4(a)中输入层N维，隐层N₁维的DAE，利用式(1) 和式(2) 计算网络的输出值，通过随机梯度下降法最小化损失函数，如式(3) 所示。

3) 将第一层DAE的隐层数据作为第二层DAE的输入，按照步骤2) 中的方法训练第二层DAE。以此类推，训练多层DAE。

4) 将多层DAE展开成深度网络的结构，分为编码和解码两部分，如图 4(b)所示。利用步骤2)、3) 中得到的权值对深度网络进行参数初始化。

5) 将输入数据作为深度网络的整体输入，通过经典的后向传播算法对网络参数进行微调，如图 4(c)所示。将编码部分最后一个隐层的值保留(即维度为N₃的隐藏层的值)，作为输入数据的特征编码。

2.3 基于E²LSH的相似近邻选择

针对传统的基于余弦相似度来计算近邻用户的方法存在计算量大、耗时长的缺点，本文采用E²LSH算法实现相似近邻的快速检索。在进行用户/项目的相似近邻检索时，以用户为例，根据索引键搜索目标用户u的特征向量所在的L个哈希桶，将这些桶中用户的并集作为目标用户的近似近邻集。具体实现方法如下：

1) 初始化函数φ(v)=(e₁(v), e₂(v), …, e_k(v))，φ(v)将用户特征向量v哈希成k个整数，连成一个k维向量。其中，e(·)由式(6) 给出，不同的e_i(·)和e_j(·)彼此随机独立产生。

2) 随机独立的选取L个φ(·)函数，为每个用户生成L个k维哈希向量，对应L个哈希表。

3) 根据式(7) 和式(8)，计算用户特征向量的主哈希值e′₁(φ(v))和次哈希值e′₂(φ(v))，得到用户特征向量在L个哈希表中的索引键(Value, Index)，每个索引键对应表中一个哈希桶，如图 5所示。将索引键相同的用户存入哈希表中的同一个桶中。

图 5中，每个用户的特征向量对应高维空间的一个点，根据索引键(Value, Index)将该点分别存入L个哈希表中的其中一个桶。按照此法将所有数据点存入哈希桶，同一个桶中的点索引键相同，从而完成索引构建。

4) 在对目标用户进行检索时，根据目标用户的索引键，找到该用户所在的L个哈希桶。将这些桶中的所有用户取出，去掉重复的用户，剩下的即为目标用户的相似近邻。

2.4 相似度计算

本文在余弦相似度的基础上，为了消除差异较大的相似近邻对后续预测评分计算的干扰，对相似度计算公式进行改进，以项目相似度计算为例，改进前后的具体计算方法分别如式(8) 和式(9) 所示：

$ sim(\mathit{\boldsymbol{\alpha }}, \mathit{\boldsymbol{\beta }}) = \frac{{\sum\limits_{i = 1}^q {{\alpha _i}{\beta _i}} }}{{\sqrt {\sum\limits_{i = 1}^q {\alpha _i^2} } \sqrt {\sum\limits_{i = 1}^q {\beta _i^2} } }} $

(8)

$ sim(\mathit{\pmb{\alpha}}, \mathit{\pmb{\beta}} ) = \left\{ {\begin{array}{*{20}{c}} {\frac{{\sum\limits_{i = 1}^q {{\alpha _i}{\beta _i}} }}{{\sqrt {\sum\limits_{i = 1}^q {\alpha _i^2} } \sqrt {\sum\limits_{i = 1}^q {\beta _i^2} } }}, sim(\mathit{\pmb{\alpha}}, \mathit{\pmb{\beta}} ) > 0}\\ {{\rm{ }}0, sim(\mathit{\pmb{\alpha}}, \mathit{\pmb{\beta}} ) \le 0{\rm{ }}} \end{array}} \right. $

(9)

其中:α和β分别表示两个项目的特征向量，sim(α, β)表示两个项目之间的相似度，q表示特征维度的大小，α_i和β_i分别表示特征向量的第i个元素，当sim(α, β)>0时，说明两个项目较为相似，否则说明二者差别较大。当某一项目与目标项目差别较大时，该项目对目标项目的评分预测贡献意义不大，因此本文将它们的相似度置为0，从而减小异类项目对评分预测的干扰。类似地，在计算用户a与用户b之间的相似度时，在消除不同用户平均评分不同的差异的同时，也排除异类用户对目标用户评分预测的干扰。

2.5 评分预测

在利用E²LSH得到用户/项目的相似近邻后，需要根据相似近邻的评分来预测未知评分。评分预测分为基于用户的评分预测和基于项目的评分预测，计算公式分别如式(10)、(11) 所示。对于基于用户的方法，由于每个用户的评分习惯不同，例如有的用户习惯评分较高，有的用户则习惯评分较低，因此在评分预测在用户的评分均值的基础上进行。基于项目的评分预测是利用同一用户已评价过的项目来预测未评价过的项目，因此不存在这个问题，可直接通过相似度加权进行评分预测。

$ {r'_{a, i}} = {\bar r_a} + \frac{{\sum\limits_{b = 1}^k {sim(a, neigh{{(a)}_b})} ({r_{neigh{{(a)}_b}, i}} - {{\bar r}_{neigh{{(a)}_b}}})}}{{\sum\limits_{b = 1}^k {sim(a, neigh{{(a)}_b})} }} $

(10)

$ {r'_{a, i}} = \frac{{\sum\limits_{b = 1}^k {sim(i, neigh{{(i)}_b}) \times {r_{a, neigh{{(i)}_b}}}} }}{{\sum\limits_{b = 1}^k {sim(i, neigh{{(i)}_b})} }} $

(11)

其中:r′表示预测评分，$\bar r$表示平均评分记录，sim(·)表示相似度，neigh(·)_b表示对象的第b个相似近邻。如果式(10) 中r_{neigh(a)b, i}未知，即目标用户a的相似近邻neigh(a)_b没有评价过目标项目i，或者式(11) 中r_{a, neigh(i)b}未知，即目标用户a没有评价过目标项目i的近邻项目neigh(i)_b，则利用1.2节中SDA网络的输出值对该评分记录进行填补。

3 实验结果及分析 3.1 实验数据

本文使用MovieLens100K数据集，该数据集包含943名用户对1682个项目的100000条真实评分记录，同时包含用户和项目的属性信息。本文设计了热启动和冷启动两种场景：在热启动场景下，将数据集分为两部分，80%用作训练集，20%用作测试集；在冷启动场景下，训练集和测试集都为原始数据集的20%。实验采用5折交叉验证的平均值作为最终结果。

3.2 评价指标

评分预测的准确率通常采用均方根误差(Root Mean Square Error, RMSE)计算，误差越小表示评分预测越准确。230对于测试集Test中的用户u和项目i，定义为：

$ RMSE=\sqrt{\sum\limits_{u,i\in Test}{{{({{r}_{u,i}}-{{{{r}'}}_{u,i}})}^{2}}/\left| Test \right|}} $

(12)

其中，r_{u, i}是用户对项目的实际评分，r′_{u, i}是推荐算法计算出的预测评分，|Test|表示测试数据集中评分数据的数量。

3.3 实验设置与结果分析 3.3.1 实验参数设置

本文结合SDA降维和E²LSH近邻检索技术，改进了相似度计算方法，分别实现了基于用户的k近邻推荐和基于项目的k近邻推荐，对比实验包括传统的协同过滤推荐^[8]和其他基于数据降维的推荐^{[4, 6]}(基于PCA和基于SVD的推荐)。经过大量实验测试，在保证各算法相对公平的条件下，各算法参数设置如下：降维后的特征维度大小统一设置为25，DAE实验中，加噪程度为0.2，梯度下降的学习率为0.8，迭代次数为15。SDA隐藏层设置为三层，节点数分别为300, 25, 25，三层的加噪程度分别为0.2, 0.3, 0.3，梯度下降的学习率为0.8，迭代次数为15。E²LSH算法参考文献[14]进行参数设置，哈希表的个数L设置为20，因为该值过小导致检索精度不够，该值过大导致空间浪费且检索精度并不会显著提高。g(v)中哈希函数h(v)的个数k取5，h(v)中w值取经验值4。

3.3.2 实验结果分析

图 6显示了相似度计算方法对不同算法的影响，其中受相似度计算影响较大的两种算法为基于SVD降维的项目近邻推荐(记为SVD-ICF)和基于PCA降维的项目近邻推荐方法(记为PCA-ICF)。采用原始数据、DAE降维和SDA降维后的数据以及文献[14]的方法计算得到的近邻相似度都大于0，因而不受影响。这是由于采用线性降维方法在提取特征时，特征向量的元素出现负值，导致计算相似近邻时不够稳定和准确，这种情况可以通过本文所提出的相似度计算方法进行弥补，通过消除相似度过低的近邻对评分预测的干扰，仅考虑相似度更高的近邻，性能得到较大提升。

图 7(a)(b)两图分别显示了在热启动和冷启动场景下，基于项目的不同推荐算法的准确率对比。在热启动场景下，各算法RMSE相差不大，改进相似度后的线性降维算法PCA-ICF和SVD-ICF的RMSE最小，文献[14]的方法(LSH-ICF)、非线性降维算法DAE-ICF、本文方法与基本的ICF算法相当，本文方法略好。在冷启动场景下，算法的预测准确率较于热启动有所下降，降维后比降维前的算法准确率高，本文方法较其他算法提升较为明显，这是由于本文算法融入了项目的类别信息。

类似的，图 8(a)、(b)分别显示了在热启动和冷启动场景下，基于用户的各种推荐算法的准确率对比。在热启动场景下，各算法准确率差异不大。在冷启动条件下，文献[14]的方法(LSH-UCF)准确率略高于基于SVD降维的方法(SVD-UCF)，基非线性降维算法的准确率明显高于其他基于线性降维的算法，由于本文方法结合用户的属性信息，故在冷启动场景下准确率最高。

图 9显示了不同推荐算法的平均运行时间对比。图中对比了三种有代表性的推荐算法在平均运行时间上的差异。ICF利用高维稀疏的原始评分数据进行推荐，平均运行时间最长；其次是PCA-CF，利用降维后的数据进行推荐，缩短了平均运行时间；平均运行时间最短的是本文方法和文献[14]的方法(LSH-ICF)，两种方法利用E²LSH检索到相似近邻后，仅需计算目标与近邻之间的相似度，无需计算所有用户或项目两两之间的相似度，从而提高了算法效率。与LSH-ICF相比，本文方法在冷启动场景下的准确率更高，RMSE指标平均降低了约7.2%。

4 结语

本文提出一种基于SDA数据降维与E²LSH的信息推荐方法，该方法将高维稀疏的用户-项目评分数据与用户属性、项目类别数据融合后作为SDA深度神经网络的输入，通过迭代训练得到低维稠密的用户特征和项目特征。然后利用E²LSH算法对降维后的用户或项目特征构建索引，通过检索得到目标用户或目标项目的相似近邻。最后根据目标用户或项目与相似近邻之间的相似度，通过相似度加权来预测用户对项目的评分。实验结果表明，本文提出的数据降维方法能够较好的提取原始评分数据中的有效信息，在降低数据维度的同时提高评分预测准确度，尤其是在冷启动场景下优势较为明显。另外，本文结合E²LSH检索算法能够快速找到目标的相似近邻，运行效率较高。但是本文仅考虑了推荐准确率和运行效率，实际中推荐性能还受到推荐结果新颖度和覆盖率的影响。通常情况下，准确率提高会导致新颖度和覆盖率下降，因此，如何利用多策略推荐方法，在保证准确率的同时提高新颖度和覆盖率是推荐算法的一个难点，也是未来研究工作的一个重点。