基于时间权重因子的隐私保护推荐算法

王永，王利，冉珣，肖玲

（重庆邮电大学电子商务与现代物流重点实验室，重庆 400065）

随着网络中数据的爆炸式增长，用户有效获取有用信息的难度日益增加.推荐算法结合用户的历史数据准确挖掘用户的真实意图，提供精准的个性化推荐服务［1］，能帮助用户更快获得有用的信息.然而，个性化推荐需要利用大量个人信息，存在隐私泄露风险［2-3］.因此，设计考虑隐私保护的推荐算法是非常必要的.

近年来，将差分隐私技术应用到推荐领域取得了良好的进展，其中一类典型的处理方式是将隐私保护技术与邻居型协同过滤算法相结合.Zhu等人［4］运用指数机制对邻居选择过程进行扰动，减小攻击者推测用户和项目相似性的概率，防止攻击者通过邻居信息推测用户评分数据.Yang 等［5］针对用户上下文兴趣建模时的隐私保护问题，在计算用户平均分和相似度时进行差分隐私保护，并利用聚类算法解决数据稀疏问题.Mcsherry等人［6］将推荐算法分为学习阶段和预测阶段，在学习阶段引入噪声实现对项目相似度矩阵的保护.Yang 等人［7］根据用户隐私需求特点，将用户隐私需求分为3 种不同层次，在计算相似度时，对不同层次隐私需求的用户采用不同强度的拉普拉斯噪声进行扰动，实现个性化差分隐私保护.此类基于邻居选择的隐私保护推荐算法具有良好的可解释性以及推荐性能.然而，该类算法存在高维数据稀疏性问题及可拓展性问题.在历史数据较少时，推荐质量不高.

基于矩阵因式分解的推荐算法是另一类主流推荐算法，具有准确度高、拓展性好、灵活度高等特点.通过将高维稀疏矩阵分解为两个低维特征矩阵，能有效解决数据稀疏性问题，具有良好的应用前景.针对该类算法，Zhang 等人［8］根据用户自身的特点，设计了一种特殊的评分数据采样机制，实现个性化差分隐私保护.鲜征征等人［9］致力于将SVD++模型与差分隐私机制相结合，分别从梯度扰动、目标函数扰动、输出结果扰动提出基于差分隐私机制和SVD++结合的模型.郑剑等［10］提出一种融合标签相似度的差分隐私矩阵分解推荐模型，可以同时保护标签数据和用户评分.为减少噪声的引入，Zhang 等人［11］设计一种新的目标函数扰动方式，并通过联合学习得到差分隐私分解矩阵.

然而，现有的隐私保护推荐算法大多是基于静态数据进行设计的.现实中，用户兴趣是一个动态变化的过程［12-13］.用户兴趣变化导致评分数据的重要程度变化，进而使隐私需求相应发生变化.上述算法对推荐系统进行隐私保护时忽略隐私需求的变化，容易引入不必要的噪声，降低数据效用，进而导致推荐质量降低.为解决上述问题，本文从用户兴趣漂移的行为数据出发，将时间因素作为度量隐私保护程度的关键点，提出一种基于时间权重因子的隐私保护推荐算法.设计时间权重因子刻画数据对用户的重要性，对不同时间段的数据根据其重要性进行不同强度的隐私保护.所提出的算法旨在充分保障用户隐私安全的条件下，有效提升数据的有效性，进而提升推荐质量.

1 预备知识

1.1 概率矩阵分解

概率矩阵分解（Probability Matrix Factorization，PMF）算法作为推荐系统的主流算法之一，在稀疏度高的评分矩阵中表现出良好的推荐精确度［14］.相关评分矩阵R的条件分布如下：

式中：ui、vj分别为K维的用户因子向量和项目因子向量；Iij为指示函数，当用户i评论过项目j时，Iij=1，否则Iij=0；N(Ri，j|μ)是服从高斯分布的概率密度函数，其均值为μ，方差为

当U、V均为μ=0的高斯球面先验分布时，U、V的概率密度函数分布分别为：

对式（2）的后验分布取对数进行分析，计算公式如下：

式中：C为常量值.求解以式（3）为目标函数的最大化问题，就能训练出用户因子矩阵U和项目因子矩阵V，然后根据U和V进行预测评分，并根据预测结果为用户提供推荐服务.以上问题可以转换为求解如下最小化问题：

式中：λu＞0，λv＞0 为正则化参数；‖ · ‖2为欧几里得范数；rij表示用户i对项目j的评分；每个用户因子向量ui∈U满足

1.2 差分隐私

差分隐私是当前主流的隐私保护技术，本文所涉及的重要相关概念如下：

定义1ε-差分隐私［15］：D和D′为相差一条记录的邻居数据集.给定随机算法A，当A在数据集D和D′上的任意输出结果O[O∈Range(A)]满足式（5），则称算法A满足ε-差分隐私.

式中：Pr [·]表示事件发生的概率；ε为隐私预算.

定义2ρ-个性化差分隐私［16］：设随机算法A：D→Range(A)，并且用户-项目评分的隐私预算矩阵ρ=[εij]N×M.如果算法满足式（6），称随机算法A满足ρ-个性化差分隐私.

式中：εij表示rij的个性化隐私预算.

2 应用场景

本研究的应用场景为集中式推荐系统，采用PMF 算法为推荐模型.系统被认为是可靠和可信赖的，这类系统通过收集并利用用户评分数据进行模型训练，为用户提供个性化推荐服务.然而，用户评分不仅直接反映其兴趣偏好，还隐含用户的性别、年龄、收入水平等信息，用户的评分信息如果被他人获取，则个人隐私泄露风险增加.因此，推荐系统应当着力于保障系统中用户评分信息的安全.

文献［11］表明，一个具有隐私保护的推荐系统应该确保攻击者不能学习用户因子矩阵U和项目因子矩阵V，否则，系统任何评分数据都可以由两个因子矩阵内积UT·V推导出来.为了抵御这种攻击，推荐系统需要保密储存U，只发布V.此外，发布V有助于解决项目评分数据不足问题.例如，不同的推荐系统，拥有相似的项目集，但用户群不同.通过与其他推荐系统共享V，推荐者可以使用本地用户信息进一步训练V.这样，推荐系统就可以利用多个来自其他系统的数据进行模型训练，有效实现信息共享，缓解信息不足的问题，改进推荐系统的性能.

然而，项目因子矩阵V包含用户信息，直接发布真实的V依然会带来隐私问题.假设攻击者拥有除用户评分rab之外的其他所有用户的评分数据和真实的V.攻击者想要获得rab.可以采用以下两种典型的攻击方式：

1）相似性攻击［4］：项目因子矩阵揭示了项目评分之间的相似性，可以帮助攻击者预测用户信息.攻击者通过做一些关于未知评分rab的假设及观察vb和vi，i∈{x|x∈I}之间相似性的变化，推断出实际的rab.

2）重构攻击［17］：根据真实项目因子矩阵V，攻击者只需要求解如下问题就能够得到用户a的信息ua：

为了抵御这两种攻击方式，对推荐系统进行如下处理：首先，推荐系统训练不加扰动的推荐模型，得到U并将其保密储存.随后，将用户因子矩阵U作为常数，训练满足差分隐私的推荐模型得到并发布扰动后的项目因子矩阵扰动后的可以防止攻击者通过获取任意两个项目因子之间的精确距离，能够对相似性进行有效保护.也可以防止攻击者获得准确的项目因子矩阵以抵御重构攻击.此外，其他推荐系统仍然可以利用训练自己的模型，提高推荐质量.

综上所述，在本文方案中，为保护用户的评分信息，用户因子矩阵U和项目因子矩阵V均需要进行保护.其中，U通过在可信系统内部以保密储存的方式进行保护，V通过引入差分隐私以添加噪声的方式进行保护.

3 基于时间权重因子的隐私保护推荐算法

当前大多数隐私保护推荐算法对评分数据进行隐私保护时没有考虑时间的影响，将所有时间段的评分数据视为同等重要程度.然而，时间因素对推荐系统有着重要的影响，且具有很好的研究价值.费洪晓等［18］运用时间窗口调整用户兴趣漂移带来的影响；Pan等［19］提出时间距离越近的信息在推荐时更加受重视；Jiang 等［20］将时间权重信息应用到用户评分数上，削弱用户过去兴趣，突出现在的兴趣；兰燕等［21］认为用户具有兴趣漂移的特性，即用户兴趣是变化的，且信息的影响力随时间阶段性衰减；Chen等［22］认为发生在不同时间的信息对表示用户当前兴趣的贡献值是不一样的，并引入4 种遗忘曲线以更好地把握用户近期的兴趣.上述研究表明，用户兴趣偏好会随着时间变化，发生时间不同的评分数据对用户重要程度存在差异，近期数据更能反映用户当下的兴趣偏好，更为重要.对所有时间段的数据采用相同程度的隐私保护，容易引入不必要的噪声，降低推荐算法的性能.因此，有必要考虑时间的影响，对不同时间段的评分数据施加不同强度的隐私保护.从而达到在保障用户隐私安全的前提下，不降低数据的有效性，提升推荐的准确度.

为了论述方便，相关符号说明如表1所示.

表1 符号说明Tab.1 Description of symbol

本文设计了基于时间权重因子的隐私保护推荐方案，总体步骤如下：

步骤1根据3.1 节的算法1 计算时间权重因子和评分的隐私预算；

步骤2利用步骤1得到的隐私预算，根据3.2节的算法2对评分数据进行抽样，得到抽样数据集Ds；

步骤3利用抽样数据集Ds，根据3.3 节的算法3，生成具有差分隐私保护作用的PMF模型.

本文方案对应的整体框架如图1所示.

图1 方案框架Fig.1 The framework of the proposed scheme

3.1 考虑时间权重因子的隐私预算

时间对兴趣点具有深远和广泛的影响.首先用户兴趣会因自身成长、阶段性角色的转变等而发生变化.其次，项目本身也具有时效性，如项目的流行性、生命周期等.兴趣点的改变导致评分数据对推荐系统的重要程度存在差异.因此，引入时间权重因子用于调节信息价值在时间变化中的衰减情况.时间权重因子的设计主要考虑两个因素：评分重要性的半衰期T0［23］，即评分从发布到其重要性减半所需要的时间；评分重要性的保持期T1［21］，即评分重要性基本维持不变的时长.根据以上两个概念，构建时间权重因子F(tij)为：

式中：tnow为计算推荐结果的时间；tij为评分rij发生的时间；floor（）为阶梯函数.权重因子F(tij)随(tnow-tij)的增大而减小，表示评分发生的时间越长，用户兴趣越可能发生改变，重要程度越小.

时间权重因子表示评分的重要程度.时间权重因子越大，评分重要程度越高，应采用较高的隐私保护强度.当时间权重因子低于所设置的阈值时，表明评分信息的重要程度下降，应降低其隐私保护强度以减少噪声的引入.通过该方式对评分数据进行隐私保护更加符合实际情况，能够有效提升推荐的准确性.针对每个评分，采用如下隐私预算分配公式：

式中：ε为统一隐私预算；εij表示评分rij的隐私预算；AVG（F（t））表示时间权重因子阈值.限制隐私预算范围为：

隐私预算描述了隐私保护的强弱程度，隐私预算越小，相应的隐私保护强度越高.

基于上述分析，设计考虑时间权重因子的隐私预算分配算法如算法1所示.

3.2 评分数据抽样

数据中每个评分的隐私预算存在差异，为了根据评分的隐私预算进行不同强度的隐私保护，采用随机抽样算法对评分数据进行抽样.随机抽样算法定义如下：

给定数据集RN×M、算法1 的输出ρ=[εij]N×M和.以式（10）所定义的概率π(rij，)对R中的评分数据进行随机抽样.

其中rij∈R.未被抽中的评分，将其评分值设为0.

结合隐私预算的随机抽样算法如算法2所示.

在随机抽样算法中，评分数据被分为两个两部分：①算法未抽中的评分数据.当评分数据的隐私预算低于所设定阈值时，有一定概率不被抽中.未被抽中的数据被设置为0，直接不参与推荐流程，能够最大限度保护这些数据.②算法抽中的评分数据Ds.被抽中的数据Ds将作为输入项，用于3.3节的模型训练中，实现具有隐私保护的个性化推荐.

3.3 基于隐私保护的概率矩阵分解模型

为了实现PMF 模型与隐私保护的结合，采用对目标函数添加扰动的方式.扰动后的目标函数如下：

在模型训练中，首先，用交替最小二乘法求解式（4）所示的不加扰动的PMF目标函数.

1）固定U，对式（4）的vj求偏导∂E(U，V)∕∂vj=0，得到求解vj的公式：

2）固定V，对式（4）的ui求偏导∂E(U，V)∕∂ui=0，得到求解ui的公式：

迭代上述过程，直到收敛，得到用户因子矩阵U.随后，将U作为常数，代入式（11），求解扰动后的PMF 目标函数，即对式（11）的求偏导∂E(U，V)∕=0，得到求解的公式：

迭代上述过程至收敛，得到扰动后的项目因子矩阵.

上述求解过程如算法3所示.

为了防止攻击者通过发布的信息来预测用户偏好，将用户因子矩阵U进行保密储存，只发布扰动后的项目因子矩阵.推荐系统利用自身保密存储的用户因子矩阵U和发布的项目因子矩阵，可以预测用户对项目的评分，并据此提供个性化推荐服务.

4 算法分析

4.1 安全性分析

引理1［8］对概率矩阵分解模型的目标函数添加扰动的方式如下：

引理2［8］令R表示评分数据集，ρ表示用户隐私预算矩阵.抽样算法RS(R，ρ，t)以式（13）所示的概率π(rij，t) 对原始数据集R进行随机抽样.将RS(R，ρ，t)抽样后的数据作为输入集，训练任意满足t-差分隐私的推荐模型，则所得的模型满足ρ-个性化差分隐私.

式中：t是一个可调整的值.

定理1本文提出的基于时间权重因子的隐私保护推荐方案满足ρ-个性化差分隐私.

证明本文方案包括算法1、算法2、算法3，分别对这3种算法进行分析，证明本文方案的安全性.

根据随机抽样算法式（10），对π(rpq，)分情况进行讨论：

证毕

4.2 复杂度分析

在本文算法中，算法1 是对原始评分矩阵进行遍历，时间复杂度为O(NM).类似地，算法2 时间复杂度为O(NM).算法3 时间开销与其梯度下降更新公式相关，其时间复杂度为O(ωN)或O(ωM).则本文算法的整体时间复杂度为O[N(M+ω)]或者O[M(N+ω)].同理，算法1 和算法2 的空间复杂度均为O(NM)；算法3 的空间复杂度为O(NK)或者O(KM).由于K＜＜(M或N)，故算法的整体空间复杂度近似于O(NM).综上所述，本文算法的时间和空间复杂度均与数据数量呈正线性关系，应用于大规模数据运算时复杂度不会显著增加.

5 实验结果及分析

实验采用推荐系统领域常用的Movielens-100k、Movielens-1M、Epinions、Movielens-10M、Amazon-Books 5 个数据集对算法性能进行分析.Movielens-10M、Amazon-Books 数据集用于测试算法在大规模数据集上的性能.数据集包含的统计信息如表2所示.

表2 数据集的统计信息Tab.2 Statistics for the dataset

实验的训练集与测试集比例为4∶1，评价指标为均方根误差（RMSE）.实验中默认参数设置为：隐因子维度K=5，迭代次数ω=50，正则化参数λu=λv=1.为保证结果的有效性，对每个算法进行5 次实验，取均值作为实验结果.所有实验均基于Python实现，使用PC 机执行，操作系统为Windows 10 64b，CPU 是Intel®CoreTMi7-9700 CPU @ 3.00GHz，RMA是16-GB.

实验主要检验3 个问题：①时间权重因子对算法准确性的影响；②本文算法预测的准确性；③算法的效率.

5.1 时间权重因子对算法准确性的影响

信息重要性衰减曲线如图2 所示.横轴表示距离评分的时间，纵轴表示信息重要程度随时间的衰减情况.

图2 信息重要性衰减曲线Fig.2 Information importance decay curve

由式（8）可知，在时间权重因子曲线中，信息重要性的衰减程度与参数T0与T1相关.本文算法在进行隐私保护时结合了时间权重因子.为实现算法的最佳性能，需要首先确定最优的时间权重因子参数.本节实验T1分别取20、25、30.为方便对比，本节实验只呈现算法中引入时间权重因子的结果.实验统一隐私预算ε=0.1.实验结果如图3所示.

图3 时间参数的影响Fig.3 Influence of time parameters

由图3 可知，在Movielens、Epinions 与Amazon-Books数据集上，算法的准确性由于时间权重因子参数不同存在差异.在图3（a）的Movielens-100K 数据集中，当T1=20 时，算法的RMSE 整体更低，预测准确性更高，且当T0为2 时预测精确度最好.此时，算法对T1的改变比较敏感，对T0的改变不敏感.图3（b）中，RMSE的变化情况与图3（a）类似，在0.913 62～0.913 82 内波动，在T1=20、T0=6 时推荐效果最优.由图3（c）（d）可知，T1=20、T0=4 时算法性能最好.图4（e）中，RMSE 在T1值不同时差异较大，但在T1值相同时波动较小，在T1=20、T0=2时取得最优结果.上述结果差异主要是由于对于相同时间段发生的评分，其时间权重因子会随着参数变化而变化，进而隐私保护强度水平不同，最终改变算法的预测准确性.

5.2 算法性能对比

为验证模型的有效性，将本文算法与其他4 种基于矩阵分解的隐私保护算法进行比较.涉及的对比算法有：①基于随机梯度扰乱的矩阵分解（Private Stochastic Gradient Perturbation，PSGD）算法［24］.将差分隐私与矩阵因式分解推荐相结合的典型算法，采用随机梯度下降法更新因子矩阵，在每次迭代过程中加入拉普拉斯噪声.②基于一般差分隐私保护的概率矩阵分解（Differentially Private Probabilistic Matrix Factorization，DP-PMF）算法［8］.未引入时间权重因子，通过目标扰动法对PMF 的目标函数进行扰动.③基于个性化差分隐私保护的概率矩阵分解（Personalized Differentially Private Probabilistic Matrix Factorization，PDP-PMF）算法［8］.将用户分为不同隐私关注人群并以此划分隐私预算，根据评分项的隐私预算对原始数据进行随机抽样，并对抽样后的数据采用一般的差分隐私保护方案.④基于交替最小二乘法输出加扰的矩阵分解（Private Alternating Least Squares，PALS）算法［25］.将差分隐私与矩阵因式分解相结合，采用交替最小二乘法更新因子矩阵，并对输出进行扰动.为合理地进行比较，算法②和算法④均只对项目因子矩阵进行扰动.根据5.1节实验结果确定T0和T1，在Movielens-100k、Movielends-1M、Movielens-10M、Epinions、Amazon-Books 数据集上，测试所有算法在不同隐私预算下的RMSE.结果如图4所示.

图4 呈现了不同数据集上所有算法的性能表现.整体上看，随着ε增加，除本文算法外的其他算法预测精确度提升.这体现出差分隐私的性质，隐私预算越大，数据可用性越强，精度越高.而本文算法对ε的变化并不敏感.本文算法具有这种特性，主要是由于本文算法根据式（9）分配隐私预算时结合了时间权重因子的影响，对单个评分项进行了个性化的隐私保护，ε的增加主要降低部分近期评分隐私保护强度，平均隐私预算变化较小，导致算法的整体性能波动较小.

图4 不同算法性能对比Fig.4 Performance for different algorithm

在不同数据集中，本文算法性能表现均优于其他算法.以图4（b）为例，本文算法RMSE 在隐私预算ε=1 时比其他算法中性能最优的算法（PSGD）低0.084.并且，本文算法对隐私不敏感的这种特性使得算法在高隐私保护水平下，准确性优势更加明显.例如，在ε=0.1 时，本文算法的RMSE 比PSGD 算法低0.58.

此外，本文算法在大规模、更稠密的数据集上有更好的效果.例如，在ε=0.1 时，本文算法的RMSE由Movielens-1M 算法的0.975 2 下降到Movielens-10M 算法的0.876 8.其他算法的准确性在相同条件下也有增长，比如PSGD 算法的RMSE 由Movielens-1M 数据集的1.490 下降到Movielens-10M 数据集的1.293.但是，由于其他算法忽略了时间因素的影响，容易引入过量的噪声，在大规模数据集上，效果仍然不如本文算法.如在Amazon-Books 数据集上，当ε=0.1 时，本文算法的RMSE 比性能最好的算法（PALS）低0.138.如上所述，本文算法在Movielens-10M 以及Amazon-Books 数据集上的表现验证了其应用于大规模数据集上的潜力.

5.3 效率对比

为了分析本文算法的效率，对本文算法与PALS、PSGD、DP-PMF、PDP-PMF 算法进行分析，从理论和实验两个方面分析时间和计算开销.

理论上.由4.2 节可知，本文算法的时间复杂度为O[N(M+ω)]或者O[M(N+ω)]，算法的时间复杂度与用户和项目数量乘积NM成正比.PSGD、PALS 与DP-PMF 算法按照统一的隐私预算添加噪声，无须在原算法增加额外步骤，故两个算法时间复杂度均为O(NM).PDP-PMF 算法在DP-PMF 的基础上增加了用户隐私预算分配和评分采样两个步骤，增加的计算复杂度为NM，故算法的时间复杂度仍为O(NM).理论分析表明，尽管本文算法增加了时间复杂度O(Nω)或者O(Mω)，但与其他算法仍然在同一数量范围O(kNM)内，k为常数.

从训练时间和预测时间进行实验分析.训练时间指算法模型训练完成耗费的时间，可以在用户使用系统前完成；预测时间指系统推荐预测某个用户评分耗费的时间，也是用户等待的时间.实验开销对比如表3 所示.随着数据规模的增加，所有算法耗费的时间均增多.整体上看，本文算法的时间比PALS和PSGD 要少，主要是因为PALS 和PSGD 算法均对数据进行了预处理，计算了每个用户和项目的均值.在大规模数据集上，这种预处理会随着用户和项目数量增大耗费更多时间.此外，PALS比PSGD耗费时间多是由于PALS采用交替最小二乘法进行优化，增加了对矩阵的求逆步骤.PDP-PMF 和DP-PMF 不需要对数据进行预处理，两个算法的时间整体上均少于PALS 和PSGD 算法.此外，由于PDP-PMF 算法增加了两个步骤，耗费时间比DP-PMF 多.而本文算法由于增加了时间权重因子计算步骤和隐私预算分配，本文算法的时间整体上多于PDP-PMF 和DPPMF.

表3 实验开销对比Tab.3 Comparison of experimental costs

在相同数据集上，与其他算法相比，尽管本文算法增加了计算时间，但整体计算开销差距并不大.例如，在Movielens-10M 数据集上，本文算法预测时间比DP-PMF 算法多19.92 ms；训练时间为8 100.90 s，比PSGD的2 200.80 s增加约3.6倍.说明尽管本文算法比其他算法耗费的时间更多，但仍然处于同样的数量级别.在Movielens-100K 数据集上，本文算法的训练时间为10.86 s，预测时间为3.96 ms.而在Amazon-Books 数据集上的训练时间为36 395.39 s，预测时间为202.67 ms.说明算法数据的增加更多的是增加模型训练的时间，而对用户偏好的预测时间影响不大.

6 结论

本文算法的核心思想是从用户兴趣漂移角度出发，解决现有隐私保护推荐算法忽略时间的影响导致推荐质量下降的问题.通过构建时间权重因子来衡量信息的重要性，并根据重要性对不同时间段的评分数据采用不同强度隐私保护.对推荐系统进行隐私保护时，这种方式能够减少不必要噪声的引入.此外，分别从理论和实践上证明算法可行性.首先从理论角度证明本文算法的安全性，随后，通过实验表明，本文算法即使在较强的隐私预算下也能保证良好的预测精度，并且其推荐结果的准确度也比经典的差分隐私推荐算法更高，具有良好的应用前景.