Matrix Factorization Recommendation Algorithm for Differential Privacy Protection

矩阵分解是隐语义推荐模型的典型算法，它将用户和项目均映射到相同的d维隐因子空间中^[17]。将用户u对应的隐因子向量表示为${{{P}}_u} \in {\mathbb{R}^d}$，将由所有用户的隐因子向量构成的矩阵表示为${{P}}$；将项目i的隐因子向量表示为${{{Q}}_i} \in {\mathbb{R}^d}$，将所有项目的隐因子向量构成的矩阵表示为${{Q}}$；则矩阵分解算法就是求解满足式(1)的最佳${{P}}$和${{Q}}$：

式中，r_ui为用户评分矩阵${{r}}$中用户u对项目i的评分；${\cal{K}}$为观测到的评分数据对应的用户−项目对$\left( {u,i} \right)$集合。假设${{r}}$中包含的用户数为m，项目数为n，则有${{r}} \in {\mathbb{R}^{m \times n}},{{Q}} \in {\mathbb{R}^{n \times d}},{{P}} \in {\mathbb{R}^{m \times d}}$，其中$d \ll m,n$。

差分隐私(differential privacy, DP)是一种新型隐私保护框架，通过添加可控的噪声到数据的统计结果中，保证隐私不被泄露且数据具有可用性。

定义1　差分隐私(DP)^[6]：对于任意的邻近数据集D和$ D' $至多相差一条数据，且随机算法A所有可能的输出$O \subseteq {\rm{Range}}\left( A \right)$，当且仅当满足不等式(2)时，A满足ε-差分隐私：

式中，ε为隐私预算，当ε值越小时，隐私保护的需求水平越高。

指数机制^[18]是一种实现差分隐私保护的技术手段，其定义如下。

定义2　指数机制：设随机算法M的输入为数据集D，输出为$\omega \in \varOmega $。函数$Q\left( {D,\omega } \right) \to \mathbb{R}$为$\omega $的可用性函数。若算法M以正比于${\rm{exp}}\left( {\varepsilon Q\left( {D,\omega } \right)}/ \varDelta \right)$的概率从$\varOmega $中选择并输出$\omega $，则算法M提供ε-差分隐私保护，称算法M为指数机制。其中，$\varDelta $为可用性函数$Q\left( {D,\omega } \right)$的阻尼因子，也称$Q\left( {D,\omega } \right)$的敏感度，表示单个数据的差异对$Q\left( {D,\omega } \right)$造成的最大影响。假设$ D' $与D为邻近数据集，$\varDelta $满足不等式：

文献[16]针对模型拟合问题设计了增强指数机制，与指数机制相比，增强指数机制的应用限于可用性函数，具有特定形式：

式中，D是包含了n个元组的数据集；${\cal{T}}$是任意元组t的取值范围；$q\left( {t,\omega } \right)$为元组拟合函数，表示模型对D中单个元组t的拟合程度；$h\left( \omega \right)$是独立于数据集D的函数。基于此可用性函数，增强指数机制的定义如下。

定义3　增强指数机制(enhanced exponential mechanism, EEM)：设随机算法M的输入为数据集D，输出为$\omega \in \varOmega $。算法M以正比于${\rm{exp}}\left( {\varepsilon f\left( {D,\omega } \right)}/ \varDelta \right)$的概率从$\varOmega $中选择并输出$\omega $，其中$f\left( {D,\omega } \right)$满足式(4)且$\varDelta $满足不等式：

那么算法M提供ε-差分隐私保护，称算法M为增强指数机制。

从式(5)可知增强指数机制与标准指数机制之间的区别是前者的阻尼因子$\varDelta $考虑了$q(t,\omega )$和$q\left( {t,\omega '} \right)$之间的最大差异，这比较适合候选解集合中解之间变化程度比较小的情况，原因是此时$\max\limits_{t \in {\cal{T}},\omega ,\omega ' \in \varOmega } q $$ (t,\omega ) - q\left( {t,\omega '} \right)$可能取得较小值。本文提出的隐私保护方案将利用这一特点改善算法效用。

本文算法围绕推荐系统的评分矩阵分解展开，将隐因子矩阵${{P}}$和${{Q}}$的求解过程转化为两个交替进行的优化过程。在优化过程中使用遗传算法求解，并在求解过程中引入增强指数机制，进而使矩阵分解过程满足差分隐私保护。本文算法的总体流程如下：

1)为提高评分预测准确性，对用户评分矩阵r进行预处理，即设边界参数为B，将评分转化到$\left[ { - B,B} \right]$的范围，得到新的用户评分矩阵${{R}}$。然后，对矩阵${{R}}$进行隐因子分解，即：

式中，R_ui为R中用户u对项目i的真实评分。隐因子分解的目标是找到使预测评分与真实评分误差平方和最小的${{P}}$和${{Q}}$矩阵。

2) 将式(6)的目标问题转换成两类特征求解任务：1)求解用户的隐因子向量；2)求解项目的隐因子向量。即在求解${{{P}}_u}$时，将矩阵${{Q}}$看作常数，构建目标函数：

式中，$q\left( {t,{{{P}}_u}} \right) = - {\left( {{R_{ui}} - {{P}}_u^{\rm{T}}{{{Q}}_i}} \right)^2}$是针对单个元组$t = $$ \left( {{{{Q}}_{{i}}},{R_{ui}}} \right)$的元组拟合函数，它表征在单个评分上的预测效果；${{{Q}}_i} = \left( {{Q_{i1}},{Q_{i2}}, \cdots ,{Q_{id}}} \right)$表示项目i的隐因子向量；${D_u} = \left\{ {\left( {{{{Q}}_i},{R_{ui}}} \right)|i \in {I_u}} \right\}$是关于用户u的二元组集合，I_u为用户u评价过的项目集合。为保障评分预测的准确性，对隐因子${{{Q}}_i}$设置上下界：$\left| {{Q_{ik}}} \right| \leqslant 1$，$k \in \left\{ {1,2, \cdots ,d} \right\}$。

同理，在求解${{{Q}}_i}$时，保持${{P}}$矩阵不变，构建目标函数：

式中，$q\left( {t,{{{Q}}_i}} \right) = - {\left( {{R_{ui}} - {{P}}_u^{\rm{T}}{{{Q}}_i}} \right)^2}$；$t = \left( {{{{P}}_u},{R_{ui}}} \right)$；${{{P}}_u} = $$ \left( {P_{u1}},{P_{u2}},\cdots ,{P_{ud}} \right)$为用户u的隐因子向量；${D_i} = $$ \left\{ {\left( {{{{P}}_u},{R_{ui}}} \right)|u \in {U_i}} \right\}$是关于项目i的二元组集合, ${U_i}$为评价过项目i的用户集合。对隐因子${{{P}}_u}$设置上下界：$\left| {{P_{uk}}} \right| \leqslant 1$，$k \in \left\{ {1,2, \cdots \cdots ,d} \right\}$。

3)首先保持矩阵Q不变，使用2.2节设计的隐私遗传算法(APrivGene)为每个用户求解式(7)所示的优化问题，得到对应的用户隐因子，更新矩阵P。然后，保持矩阵P不变，同样使用2.2节设计的隐私遗传算法为每个项目求解式(8)所示的优化问题，得到对应的项目隐因子，更新矩阵Q。交替重复上述过程，持续优化P和Q矩阵，直至达到最大迭代次数T。

上述隐私遗传矩阵分解算法的伪代码如算法1所示，其中改进的隐私遗传算法APriveGene将在2.2节中进行详细说明。

算法1　隐私遗传矩阵分解算法(PGMF)

输入：用户评分矩阵r，用户集合Users，项目集合Items，迭代次数T；

输出：P, Q；

r矩阵做预处理得同型矩阵R，建立优化问题如式(6)；

for t = 1 to T

　　for u in Users

　　构建目标函数$f_Q^u$；

　　${D_u} = \left\{ {\left( {{{{Q}}_i},{R_{ui}}} \right)|i \in {I_u}} \right\}$ //获取用户二元组集；

　　${{{P}}_u} = {\rm{APrivGene}} \left( {{D_u},f_Q^u} \right)$ //求解用户隐因子；

　　end for

　　for i in Items

　　构建子目标函数$f_{{P}}^i$；

　　${D_i} = \left\{ {\left( {{{{P}}_u},{R_{ui}}} \right)|u \in {U_i}} \right\}$ //获取项目二元组集；

　　${{{Q}}_{{i}}} = {\rm{APrivGene}} \left( {{D_i},f_{{P}}^i} \right)$ //求解项目隐因子；

　　end for

end for

return P, Q

本算法对文献[16]中的隐私遗传算法进行了改良，提出调整的隐私遗传算法(adjusted private genetic algorithm, APrivGene)。使用APrivGene算法对式(7)和式(8)所示的优化问题进行求解，在选择阶段引入增强指数机制，实施对矩阵分解过程的隐私保护。按照执行顺序、从初始化、选择和变异3个方面介绍APrivGene算法。

初始化阶段：设置包括ε在内的各个控制参数。然后，随机生成l个d维的向量作为初始候选解集$\varOmega $，计算$\varOmega $中每个解的目标函数值$f\left( {D,{{\omega }}} \right)$作为遗传算法的适应度值。

选择阶段：以$f\left( {D,{{\omega }}} \right)$为可用性函数，使用$\varepsilon /{\rm{2}}TG$作为选择操作的隐私预算，应用增强指数机制EEM以正比于${\rm{exp}}\left( {\varepsilon f\left( {D,{{\omega }}} \right)/{\rm{2}}TG\varDelta } \right)$的概率从$\varOmega $中挑选出${{\omega }}$。为了有效减轻选择阶段引入的扰动，只选出单个个体进行后续操作，之后将$\varOmega $置空，准备接纳新解。

变异阶段：为避免交叉操作造成敏感度过大，只使用了变异操作。为了改善寻优效率，采用全局搜索效率较高的柯西变异算子生成变异扰动，即从标准柯西分布$C\left( {0,1} \right)$中生成随机扰动。然后，以寻找重要程度最高的隐因子为目的，让变异操作对各个隐因子进行变化，且每次只在一个维度k上搜索。由于用户或项目对某隐因子的偏好可分为正负两类，对单个隐因子的扰动对应地被设计为正负两个方向。对每个维度进行上述变异，每次变异生成两个新解，加入$\varOmega $，最后形成新的候选解集。

生成新集合之后，为逐步减小搜索范围提高寻优效率，使用衰减因子$\beta $缩减变异步长$\eta $。然后，返回选择环节，进入下一轮循环。当达到最大迭代次数G时，使用EEM方式选出最终解${{{\omega }}^{*}}$。

上述改进的隐私遗传算法的伪代码如算法2所示。

算法2　改进的隐私遗传算法(APrivGene)

输入：$D$，即二元组集合${D_u}$或${D_i}$；$f$，即目标函数$f_Q^u$或$f_P^i$；

输出：隐因子向量${{{\omega }}^{*}} = \left( {{\omega _1},{\omega _2}, \cdots ,{\omega _d}} \right)$；

初始化算法中的控制参数：设置隐因子个数d，隐私预算ε，变异步长$\eta $，衰减因子$\beta < 1$，最大迭代次数G，候选解集$\varOmega $的大小l；

随机生成初始候选解集$\varOmega $

for g = 1 to G − 1 do

　对每个${{\omega }} \in \varOmega $，计算$f\left( {D,{{\omega }}} \right)$

　${{\omega }} = {\rm{EEM}}_f^e\left( D \right)$ //使用增强指数机制选择个体；

　将$\varOmega $置空；

　for k = 1 to d do

　　$x = C\left( {0,1} \right)$ //按标准柯西分布抽取随机噪声；

　　${{{v}}_1} = \left( {{\omega _1},{\omega _2}, \cdots ,{\omega _k} + \eta x, \cdots, {\omega _d}} \right)$//正方向变异；

　　${{{v}}_2} = \left( {{\omega _1},{\omega _2}, \cdots ,{\omega _k} - \eta x, \cdots, {\omega _d}} \right)$//负方向变异；

　　$\varOmega = \varOmega \cup \left\{ {{{{v}}_1},{{{v}}_2}} \right\}$

　end for

$\eta = \eta \beta$；

end for

对每个${{\omega }} \in \varOmega $，计算$f\left( {D,{{\omega }}} \right)$；

${{{\omega }}^{*}} = {\rm{EEM}}_f^e\left( D \right)$；

return ${{{\omega }}^{*}}$

在算法2中，为了发挥增强指数机制的作用，在每次迭代中需要根据当前候选解，求解增强指数机制中的阻尼因子。求解过程如2.3节所示。

在求解隐因子向量时，根据候选集合中个体的适应值$f\left( {D,\omega } \right)$和隐私预算ε，EEM将按照如下的概率输出用户隐因子向量和项目隐因子向量：

数据集${D_u}$或${D_i}$中的元组t有d+1个属性，其中预处理后的评分数据${R_{ui}}$在$\left[ { - B,B} \right]$之间，$\left| {{P_{uk}}} \right| \leqslant 1$和$\left| {{Q_{ik}}} \right| \leqslant 1$，$k \in \left\{ {1,2, \cdots ,d} \right\}$，所以元组t的取值范围${\cal{T}} = \left[ { - B,B} \right] \times {\left[ { - 1,1} \right]^d}$。设${\varDelta _{{P_u}}}$为求解用户隐因子向量时的阻尼因子，${\varDelta _{{Q_i}}}$为求解项目隐因子向量时的阻尼因子，则根据增强指数机制的定义可得：

为了求解${\varDelta _{Pu}}$，需要分别求解${\varDelta _1}$和${\varDelta _2}$。对于${\varDelta _1}$有：

由于$ \mathop {\min }\limits_{\left( {{R_{ui}},{Q_i}} \right) \in {\cal{T}}} {\left( {{R_{ui}} - {{P}}_u^{\rm{T}}{{{Q}}_i}} \right)^2} = 0$，所以：

对于$ {\Delta _2}$有：

因为

所以，

综合${\varDelta _1}$和${\varDelta _2}$的上界，得到求解用户隐因子向量时，阻尼因子应满足的条件为：

同理可得求解项目隐因子向量时阻尼因子${\varDelta _{{Q_i}}}$应满足的条件为：

观察${\varDelta _{{P_u}}}$和${\varDelta _{{Q_i}}}$应满足的条件，可以发现${\varDelta _2}$衡量的是候选解集中各隐因子向量之间的差异。在多数情况下${\varDelta _{\rm{1}}} > {\varDelta _{\rm{2}}}$，这是因为随着APrivGene的迭代，$q\left( {t,{{{P}}_u}} \right) - q\left( {t,{{P_{u}}^\prime}} \right)$或$q\left( {t,{{{Q}}_i}} \right) - q\left( {t,{{Q_{i}}^\prime}} \right)$的值会逐渐减小，但${\varDelta _1}$的值并不会受到APrivGene迭代的影响。所以，随着APrivGene迭代次数增加，阻尼因子会减小，增强指数机制可以选择出更精确的解，从而有效保证算法的效用。

定理1 算法1满足ε-差分隐私。

证明：令$D$为数据集${D_u}$或${D_i}$，$ D' $与D为其邻近数据集，t和$ t' $分别表示D与$ D' $中相异的元组；令${{\omega }}$为隐因子向量${{{P}}_u}$或${{{Q}}_i}$，在应用APrivGene求解${{\omega }}$时，设EEM的隐私预算$\varepsilon ' = \varepsilon /2TG$，$T$表示算法1(PGMF)中外循环的次数，$G$表示算法2(APrivGene)中的最大迭代次数。令$\varDelta $为EEM的阻尼因子${\varDelta _{{P_u}}}$或${\varDelta _{{Q_i}}}$，根据2.3节中式(9)和式(10)，考虑以下两种情况：

当$ \varDelta \geqslant {\varDelta _1}$时：

当$ \varDelta \geqslant {\varDelta _2}$时：

综上，由于$ \varDelta \geqslant {\rm{min}}\left\{ {{\varDelta _1},{\varDelta _2}} \right\}$，总有：

故应用APrivGene算法求解隐因子向量时，其每一轮迭代均满足$\varepsilon /2TG$-差分隐私。由差分隐私保护的序列组合性质可得，更新每个用户或项目的隐因子向量时算法满足$\varepsilon /2T$-差分隐私，算法1满足$\varepsilon $-差分隐私。

本文算法将矩阵分解的求解转换为对两个优化问题的求解，这样处理有两点优势：

1)更好地体现个性化的思想。因为直接求解 式(6)可能忽视单个个体的推荐质量。转化为式(7)和式(8)所示的问题后，可以为每个用户或每个项目分别设计其专属的考虑隐私保护的隐因子值，更好地体现个性化的推荐思想，利于提升推荐精度。

2)提升算法效率和效用。直接对原问题应用遗传算法求解，解的维度将是$d \times \left( {m + n} \right)$，而推荐系统中的用户数m和项目数n通常都很庞大。采用遗传算法在高维空间中寻优，将会导致效率非常低。同时，原问题关于P，Q是非凸的，也会导致算法收敛速度慢。过慢的收敛速度，会导致迭代轮次增加。由于需要在每轮迭代中添加隐私保护的噪音，会导致噪声增大，从而使解的质量下降甚至不可用。本算法将原问题分解为两个优化问题，使得各个子问题都是凸问题，且解的维度是隐因子个数d，它远小于m和n，极大地提高了求解的效率，也利于提高解的效用。

APrivGene算法是PrivGene算法的改进算法。PrivGene算法并没有对变异操作进行专门的设计，它所采用的随机变异方式，将导致解的搜索效率不高，影响最终解的质量。APrivGene算法在变异操作中，对选择的个体沿着解的各个维度，从正反两个方向使用标准柯西分布生成随机扰动进行变异，具有如下优势：

1)有助于EEM选出更好的解。EEM的特点是，当候选解之间的变动程度不大时，其敏感度将取得较小值从而减轻选择过程的扰动。单维度变异所生成的新解之间只存在一个隐因子上的差异，此时式(9)和式(10)中对于${\varDelta _{Pu}}$和${\varDelta _{Qi}}$通常有${\varDelta _{\rm{1}}} > {\varDelta _{\rm{2}}}$。随着算法逐渐收敛，${\varDelta _{\rm{2}}}$的取值将更小，增强指数机制的阻尼因子减小，使得选中优质解的概率提高。

2)有助于提高解的搜素效率并减少扰动。矩阵分解中用户和项目共享相同的隐因子，但不同的用户或项目对不同的隐因子会有不同程度的关注，单维度变异将有利于快速找到相对重要的隐因子。用户或项目对隐因子只有正向或负向两类偏好，变异算子在隐因子的正负方向上同时进行搜索，而非随机搜索，符合实际情况。该做法有效提升了解的搜索效率，同时控制了候选解之间的变动程度，减轻选择过程受到的扰动。

3)标准柯西分布${\rm{C}}\left( {0,1} \right)$由于有较高的两翼概率特性，具有较好的全局搜索能力，能帮助算法在迭代的初期保持一定程度的多样性。设置了衰减因子$\beta $在每次迭代时对步长$\eta $进行缩减，利于在迭代后期增强指数机制实现更优的选择。因为随着迭代进行，式(9)和式(10)中${\varDelta _{Pu}}$和${\varDelta _{Qi}}$的值${\varDelta _{\rm{2}}}$会逐渐减小，但${\varDelta _1}$的值并不会受到影响，这样增强指数机制的阻尼因子会减小，使选择过程受到更少的扰动，做出更优的选择。

采用两个常用数据集Movielens100K和YahooMusic进行实验，按8∶2的比例随机划分为训练集和测试集。两个数据集的统计属性如表1所示。

除本文算法外，还对其他一些类似算法进行了对比实验。实验中涉及到的算法及其描述如表2所示。

本文取10次实验的平均值作为最终结果。采用均方根误差(RMSE)度量算法的性能：

式中，T为有效预测项目的个数；${r_{ui}}$为用户u对项目i的真实评分；${\hat r_{ui}}$为用户u对项目i的预测评分。RMSE越小则推荐精度越高。

采用文献[14]中的预处理方式，将评分区间转换为[−1,1]，设置隐因子变量域为[−1,1]。在APrivGene中，最大迭代轮次为23，候选集大小为85，柯西变异算子的步长为0.2，步长的衰减率为0.95。对比算法的参数设置均遵循相应文献中的最优参数设置。

为了保证有效的隐私保护，实验中将隐私预算ε设置为较小范围，即$\varepsilon \in \left[ {{\rm{0}}{\rm{.1,1}}} \right]$。图1和图2分别给出了本算法与其他对比算法在Movielens100K和YahooMusic两个数据集上的RMSE测试结果。其中，将不考虑隐私保护的ALSBase算法的实验结果作为对比基线。从整体上看，随着ε的增大，各个算法的RMSE均逐渐减小，表明随着隐私保护水平的下降，推荐准确性增加。各算法在Movielens100K数据集上的推荐准确性均高于YahooMusic数据集，主要原因是YahooMusic数据集具有更高的稀疏性。

在图1中，随着ε的变化，PGMF在Movielens100K数据集上的RMSE为：$0.995 \leqslant $$ {\rm{RMSE}} \leqslant 1.308$，低于其他的隐私保护算法。同样的趋势也存在于YahooMusic数据集的测试中。在图2中，PGMF的RMSE总是低于其他对比算法，其RMSE值的范围为$1.290 \leqslant {\rm{RMSE}} \leqslant 1.670$，比其他隐私保护算法平均低0.2左右，显示出了更好的准确性。在两个数据集上，PGMF与不考虑任何隐私保护的ALSBase算法的RMSE差距是最小的，同样证明了PGMF具有更好的推荐准确性。

在本实验中，DPALS算法的推荐准确性比DPSGD算法要高。因为在不考虑隐私保护的情况下，ALS的性能比SGD要好，这种优越性在考虑差分隐私的情形下同样存在。但是，这两种方法都是基于传统优化方式的算法，当隐私预算ε越小，DPSGD和DPALS所引入的噪声就越大，导致求解出的隐因子向量与最优解之间差距过大，推荐准确度降低。在图1中，$\varepsilon = 0.1$时，DPALS与DPSGD的RMSE都超过了2.1，而PGMF的RMSE只有1.3；在图2中，$\varepsilon = 0.1$时，DPALS与DPSGD的RMSE都超过了2.3，而PGMF的RMSE只有1.67。比较结果说明在隐私保护要求较高时，PGMF的优势更为明显。

DPSGDInput算法是文献[13]中表现最优的算法，直接对评分数据添加噪音。它不需要在矩阵分解过程中分配隐私预算，在较低隐私保护需求下具有良好的推荐准确性。当ε=1时，其RMSE值在Movielens100K与YahooMusic数据集上分别为1.06和1.44，是除PGMF算法以外最低的。但是，这种直接对数据集加噪音的方式在高隐私保护需求下会引入过大的噪声。从图1和图2中可以看出，在ε<0.5时，该算法的推荐RMSE值显著增加，其推荐准确性比DPALSObj算法和PGMF更差。

DPALSObj算法通过对目标函数进行扰动而实现隐私保护。它的推荐精度在高隐私保护条件下，即$\varepsilon \in \left[ {0.1,0.5} \right]$时，优于除PGMF之外的其他隐私保护算法。这种方法对隐私预算的大小比较敏感，在高隐私保护需求下相对于PGMF仍然引入了过大的噪声，即便在其表现更为突出的YahooMusic数据集上，其RMSE仍然明显比PGMF高。

PGMF的性能优于其他算法的主要原因是采用了独特的进化方式限制了候选解集的方差，又借助增强指数机制改善了解的选择过程。所以，即使在很小的隐私预算条件下，求解出的隐因子向量都不会偏离最优解太远，实现了更高的推荐准确度。

本文针对推荐系统中的隐私问题提出了一种满足差分隐私保护的矩阵分解算法。该算法将矩阵分解问题转化为两个交替进行的优化问题。在遗传算法的选择操作中采用了增强指数机制使得整个矩阵因子分解的过程满足差分隐私保护。基于搜索重要隐因子的思想，设计了遗传算法的变异操作，从正反两个方向变异隐因子，不仅提高了算法的效率而且有效增强了解的性能。在两个标准数据集上的实验结果表明本文算法能更好地平衡隐私性和推荐的准确性，尤其在隐私保护需求较高的条件下，仍然可以取得良好的推荐效果，具有很好的应用潜力。