基于密文的去中心化兴趣点推荐研究
2021-11-15张亚男张益凡
张亚男 刘 安 彭 佳 张益凡
(苏州大学计算机科学与技术学院 江苏 苏州 215006)
0 引 言
随着移动设备的大量普及，全球定位系统(GPS)信息的获取变得非常容易。工业界利用这些定位数据推动基于位置的社交网络(LBSNs)的发展。一些经典的LBSNs网站如Foursquare和Gowalla鼓励用户分享所在位置的相关信息，从而收集丰富的用户签到数据，并利用这些数据为用户提供兴趣点推荐服务。兴趣点推荐旨在为用户找到未被访问和感兴趣的地点，它以其在面向服务领域的巨大商机吸引了众多研究者的关注，尤其是在基于位置的服务领域。目前已有大量模型被创建用来学习用户在选择兴趣点时的偏好[1-2]。
Cheng等[3]和Yang等[4]提出的矩阵分解模型是最经典的推荐模型，它根据用户-兴趣点交互矩阵学习用户和兴趣点的潜在因子向量，并利用向量的相似性推测用户和兴趣点的相关性。许多研究者通过结合一些辅助信息来改善矩阵分解推荐模型，如社会关系[5]、空间信息[6-7]、时间信息[8]、属性信息[9]等。这些模型的成功证明了矩阵分解在推荐性能上的优越性。然而，这些基于矩阵分解的算法在集中训练过程中有两个主要缺点：(1) 计算成本高。所有用户的信息都被收集到特定的集中式服务器中，导致该服务器需要同时处理大量的签到数据，意味着服务器的计算能力必须满足高要求。(2) 隐私风险大。不是每个人都想让别人知道他做了什么，例如一个自卑的肥胖者不愿意把他经常去健身房的消息告诉别人。因此，将用户的私有数据提交给一个集中式服务器，向服务器公开他们的偏好，或者依赖服务器保护他们的数据不被泄露，这样的行为可能不符合用户的意愿。
对于上述集中式服务器存在的计算压力问题，最有效的方法是保持用户数据的分散性，实现分布式推荐系统。这类模型[10-12]可以利用分布式设备来分担集中服务器的计算任务，从而解决传统矩阵分解的集中计算问题。然而，分布式计算导致隐私风险问题也转移到了各分布式服务器上，如果分布式服务器忽视信息保护，用户的隐私仍然可能泄露。在上述分布式模型中，Chen等[12]考虑了对用户数据的保护，该模型将每个用户数据始终保持在自己的终端上，每个终端相当于一个分布式服务器，训练推荐模型时，各终端通过交互梯度来完成矩阵分解。虽然传输梯度看似保护了用户的原始数据，但这些梯度计算式包含了大量的隐私信息，模型无法保证他人不能根据梯度反推出这些信息。此外，梯度本身反映了用户的一些信息，例如潜在因子的变化幅度，这些信息可能会被他人利用。该问题类似于发送一组特定数字的平均值，虽然保证了其他人不会知道这些数字，但依然泄露了这些数字的分布特征且可能被他人利用。
针对上述集中式服务器存在的隐私风险问题，一些研究者提出使用加噪或加密策略来保护用户隐私。加噪就是向数据中加入合适的噪声让数据变得有一定误差但仍具有实验价值，而加密是通过加密密钥让明文变成密文且只有拥有解密密钥的用户才能从密文中获取明文。Sweeney等[13]提出用k-匿名算法对所有收集数据加噪，Berlioz等[14]结合差分隐私算法引入拉普拉斯噪声生成安全性更高的加噪数据，Erkin等[15]利用同态加密机制设计基于密文的推荐算法。然而，加噪会造成数据的精度损失；而加密则因为密文计算的复杂性造成巨大的计算开销，特别是在集中式服务器上。
基于上述研究在改进传统矩阵分解模型上的不足，本文提出了一种基于密文的去中心化矩阵分解模型，以较小的计算压力实现隐私保护的兴趣点推荐。如图1所示，去中心化过程就是把用户数据始终保持在各自的终端，每台终端完成各自用户的偏好学习。去中心化之后，为了加快各终端的计算速度，该模型定义了不同层次的朋友来表示用户之间的兴趣相似度，并采用随机游走的方式选择部分朋友进行协同学习。同时，为了保护用户的隐私并保证不降低数据精度，该模型对所有用户的交互数据进行加密，并设计了一种基于密文的矩阵分解算法。Paillier加密具有同态加密的性质因此被选作为本文模型的加密算法。在性能优化方面，本文模型从“用户是否可能访问该兴趣点”的角度为每个用户设定了个人兴趣点集合，从而改善加密算法时间性能。
图1 中心化及去中心化矩阵分解模型的数据分布
综上所述，本文的贡献如下：(1) 提出将分布式系统与训练加密相结合的兴趣点推荐研究。(2) 提出了有效的隐私保护推荐算法CDMF。通过第三方密钥生成器提供的公钥，CDMF的整个协同学习过程都在密文上进行，保证用户数据只被用户自己所知。(3) CDMF通过定义每个用户的个人兴趣点集合来提高基于密文的去中心化推荐算法的性能。(4) 通过两个真实数据集上的大量实验证明， CDMF模型在保护隐私的同时，还比传统矩阵分解模型有更高的精确率和召回率。
1 相关工作
1.1 基于矩阵分解的兴趣点推荐
矩阵分解[4,7,16]是通过将用户-兴趣点交互矩阵RM×N分解为两个低维矩阵，即用户潜在因子矩阵P和兴趣点潜在因子矩阵Q，来学习用户和兴趣点的属性。矩阵分解公式如下：
RM×N=PM×K×QK×N
(1)
R中的元素rij表示用户i在兴趣点j上的签到次数，pik和qkj分别表示用户i和兴趣点j对第k(k∈[1,K])维属性的偏好。为了获得P和Q，矩阵分解使用最小二乘法优化损失函数：
(2)
式中：pi为用户i的潜在因子；qj为兴趣点j的潜在因子。另外，为了避免训练结果的过拟合，函数中加入了正则化参数λ和μ。
许多研究人员致力于基于矩阵分解的兴趣点推荐。Ye等[17]提出的模型证明了用户越接近某个兴趣点，他们就越有可能在该点签到，因此其提出在矩阵分解模型中加入地理影响来学习用户偏好。Lian等[6]使用加权矩阵分解来加权用户签到信息：比起未签到过的地点，已签到地点更能反映用户的偏好，因此为其设置更高的权重。Zhao等[18]提出了一个多层次矩阵分解模型，该模型将加权矩阵分解和层次结构结合起来，并将具有地理位置相关性的用户和兴趣点划分在同一层。然而，由于它们都需要集中式服务器来收集用户数据，这些工作不可避免地存在计算压力大和隐私泄露风险高问题。
1.2 隐私保护推荐系统
隐私安全是众多推荐系统研究的热点。随着大数据时代到来，信息泄露越发严重，导致基于隐私保护的推荐被广泛重视，其中对数据加噪或加密是保护隐私的主要方法。
在一系列加噪方法中，差分隐私方法保密性极高，其噪声服从拉普拉斯分布，已经通过严格的数学推导证明其数据保护性。Balu等[19]提出了一个差分隐私矩阵分解模型，它使用一致的扰动噪声保护所有用户的签到数据。Meng等[20]指出为个人敏感及不敏感数据分配不同的噪声，可保护用户的隐私免受不可信朋友的攻击。虽然这些方法保护了用户的数据，但是通过加噪改变数据会对推荐精度产生负面影响。
在一系列加密方法中，同态加密是其中最高效最安全的一种。同态性表示对明文采用某种计算操作可以转化为对密文采用其他种计算操作。所以在同态加密中，模型不需要解密数据也可以实现算法。Erkin等[15]提出了一种结合同态加密和数据打包技术的隐私保护推荐方法。Zheng等[21]结合保序加密技术来保护用户发出请求的位置。虽然这些方法能够保护数据且不影响推荐效果，但加密计算复杂性非常高。本文使用同态加密方法来保护用户隐私，同时为了缓解加密带来的计算压力，改进性地为用户建立个人兴趣点集合。
2 预处理
(3)
式中：M和N分别是用户总数和兴趣点总数。
2.1 朋 友
如果两个用户i和j被判断为相似的用户即他们有相似的兴趣点偏好，那么模型认为这两个用户是朋友。友谊是可传递的，即如果用户j和l也是朋友，那么用户l就是用户i的二级朋友，以此类推，用户l的朋友就是用户i的三级朋友。本文定义二级及以上的朋友都是间接朋友。
在判断相似用户之前，首先观察Foursquare数据集上的用户-兴趣点签到数据。如图2所示，实验随机选取五个城市的用户，统计这些用户在当前城市和其他城市签到的次数，其中：“市内”标签表示本地用户在本城市的签到次数，“市外”标签表示本地用户在其他城市的签到次数。
图2 五个不同城市的用户签到数据
由此可知，用户通常活跃在所属城市内，少数情况下会涉足其他城市。该发现表明：用户的偏好受地理位置的影响很大，用户之间距离越接近，他们的偏好可能越相似。因此，CDMF假定在同一个城市的用户有相似的偏好，并且彼此是朋友。在训练CDMF时，用户只需与具有相似偏好的朋友或间接朋友进行协同学习。
设G=
2.2 随机游走
随机游走是一个由连续随机步组成的随机过程。任意两个连续随机步之间的关系被定义为：
(4)
式中：si是服从任何随机分布的随机步。这表明下一状态WC仅依赖于当前状态WC-1和从当前状态到下一状态的随机步SC[22]。
(5)
(6)
为了避免无止境地选择间接用户，规定用户只可以与第d(d≤D)级朋友交互数据。
2.3 Paillier加密
Paillier加密属于公钥加密。公钥加密体系由公钥Kpub、私钥Kpri和Aead算法三部分组成。假设有这样一个任务，发送方需要向接收方发送数据且保证不暴露数据。为了达到这个目的，通常由接收方根据Aead算法生成Kpub和Kpri，并将Kpub发送给发送方。发送方使用Aead算法和公钥Kpub加密数据并发送密文，接收方然后使用Aead算法和私钥Kpri解密数据，这样可以保证数据安全。算法1简要介绍了Paillier加密的算法Aead，包括生成密钥、加密和解密三个步骤。
算法1Paillier公钥加密
密钥生成：
1.随机选取两个大素数p和q，其中： gcd(pq,(p-1)(q-1))=1；
2.n=pq,λ=lcm(p-1)(q-1)；
5.则公钥为(n,g)，密钥为(λ,μ) ；
加密:
7.计算密文c=E(m,r)=gm·rnmodn2；
解密:
8.计算明文m=D(c)=L(cλmodn2)·μmodn。
Paillier加密具有同态加密的加法同态性质。同态加密满足要求：在密文上操作f1运算之后获得的值等于在明文上操作f2运算后的值的密文。Paillier加密的同态性质如下：
E(m1)·E(m2)=E(m1+m2)
(7)
(E(m1))n=E(n·m1)
(8)
式中：E(·)表示加密算法；m1和m2表示明文；n表示任意明文。
由于Paillier算法可以将明文计算转换为密文计算，具有绝对的安全性，因此本文选择Paillier算法作为模型的加密算法。
3 基于密文的去中心化兴趣点推荐
矩阵分解通过协同学习所有用户的签到数据来提取用户属性(潜在因子)，用户之间潜在因子的相似性反映了用户偏好的相似性。因此，在去中心化模型中，单个用户仅凭自身的签到数据无法完成矩阵分解，用户需要进行必要的数据交互。考虑到只有相似用户的偏好才能对用户的选择具有启发作用，CDMF提出用户只需要与具有相似偏好的朋友或者间接用户交互数据。
3.1 去中心化矩阵分解
用户潜在因子表示用户的个人属性，与其他用户数据无关。兴趣点潜在因子表示兴趣点的属性，是由所有用户共同判定。换言之，对于每个用户，他的用户潜在因子不需要协同学习，但兴趣点潜在因子需要。通过细化兴趣点的属性判定者，模型将用户i终端上兴趣点j的潜在因子划分为两个部分：
(9)
基于式(2)所示的传统矩阵分解的损失函数，去中心化模型的损失函数为：
(10)
式中：α、β、γ是正则化参数。加入正则化可以防止训练过拟合。接下来，模型可以用梯度下降法更新每个变量：
(11)
(12)
(13)
3.2 基于密文的分布式矩阵分解
为了保护传输数据，CDMF在上述去中心化模型中引入了Paillier算法来加密公有梯度，并设计算法让上述整个训练过程在密文上实现。
在模型训练之前，本文需先定义Pailliar加密的同态乘法实现过程。假定用户i想要根据密文E(A)和E(B)得到E(A·B)，则：
(1)i：生成两个随机数r1和r2；
(2)i：E(A-r1)=E(A)·E(-r1),E(B-r2)=E(B)·E(-r2)；
(3)i：将E(A-r1),E(B-r2)发送给可信第三方；
(4)V：私钥解密E(A-r1),E(B-r2)，获取A-r1,B-r2；
(5)V：计算密文E((A-r1)·(B-r2))，并发回给i。
因此，用户i可以得到：
E(A·B)=E((A-r1)·(B-r2))·(E(A))r2·
(E(B))r1·E(-r1·r2)
(14)
为了书写方便，同态乘法被定义如下：
E(A·B)=f(E(A),E(B),r1,r2)
(15)
以此类推，可以得到：
E(A·B·C)=f(E(A·B),E(C),r1,r2)
(16)
结合Pailliar加密的同态性质和间接实现的同态乘法，用户可以利用本地数据获得梯度的密文如下：
(17)
(18)
(19)
获取梯度密文后，用户首先更新本地潜在因子，接下来随机选择D×H个朋友/间接朋友(在邻接图中共走D步，每步选H个朋友)发送公有梯度的密文，之后接收者更新他们的公有兴趣点潜在因子。
CDMF伪代码如算法2所示。其中Si,i′是二元指示函数，如果i和i′是朋友，Si,i′为1，否则为0。
算法2CDMF模型算法
输入：用户-兴趣点交互矩阵R，正则化系数α、β、γ，学习率θ，最大朋友量H，随机游走最大步长D，最大迭代次数T，密钥长度Lp。
输出：每位用户i的潜在因子密文E(pi)，公有兴趣点潜在因子密文E(Qi,public)，私有兴趣点潜在因子密文E(Qi,private)。
1.假定每个用户已经获得公钥Kpub
2.fori=1 toMdo
3.初始化pi、Qi,public、Qi,private
4.利用Kpub加密得到E(pi),E(Qi,public),E(Qi,private)
5.fort=1 toTdo
6.forrijinRdo
16.returnE(pi)、E(Qi,public)、E(Qi,private)
3.3 优化时间性能
图2表明了用户的签到具有地理聚集性，用户通常在他们的居住地和公司附近移动，意味着他们在越远的兴趣点签到的概率越低。因此，CDMF提出为每个用户建立个人兴趣点集合。以用户已有签到点的中心作为用户的地理长居地，那么他的个人兴趣点集合是其长居地附近的前O个邻近点。在模型训练过程中，只有当兴趣点属于个人兴趣点集合，用户才会更新它的潜在因子，通过减少更新计算从而加速模型收敛。实验部分分析了O的大小设定。
3.4 安全性分析
直观上来看，该模型安全的原因有两方面：(1) 用户没有私钥，所以用户无法解密接收到的密文，Paillier密码体系的安全性保证了用户无法从密文中获取任何隐私信息；(2) 可信第三方拥有私钥，但是其接收到的数据是用户用随机数处理过的数据。因此，只要用户不和第三方互通有无，隐私就不会被暴露。
接下来，本文对模型训练的所有参与方进行具体的安全性分析，包括每位用户和可信第三方，考虑每个参与方是否能从接收的数据中获取隐私信息。
(1) 用户。每次更新中，用户得到公有梯度的密文。基于Paillier加密的语义安全性，除非用户使用穷举法对其进行暴力破解，否则无法解密该梯度。然而由于计算量太大，穷举法几乎是不可能的。所以用户方无法获取隐私信息。
(2) 可信第三方。第三方持有私钥，在交互过程中，第三方接收的数据包括E(A-r1)、E(B-r2)。因此，尽管可以解密数据，但未知且不断变化的随机数r1和r2使得第三方无法得到公有梯度A和B。
基于以上讨论，可以得出结论：模型在隐私保护方面是安全的。
3.5 复杂度分析
因为CDMF是分布式模型，所以本文从计算时间复杂度和通信时间复杂度两个方面来分析模型复杂度。在分析前，需要知道加密算法的时间复杂度与密钥长度Lp密切相关。
计算时间复杂度主要源于算法2中7-12行的梯度获取与潜在因子更新。一次训练中，梯度获取的时间复杂度是Lp×K，而潜在因子更新是(Lp×K)×min(D×|Ci|,D×H)，其中K表示潜在因子维度，|Ci|表示用户i所处城市的用户数。因此，所有用户迭代一轮的计算时间复杂度是|R|×(Lp×K)×min(D×|Ci|,D×H)。考虑到K、D、H非常小，所以计算时间复杂度基本与|R|×Lp成线性关系。采用个人兴趣点集合可以通过减少潜在因子更新次数来提升模型的时间性能。
通信时间复杂度取决于如下两个部分：(1) 用户之间的通信；(2) 用户与可信第三方之间的通信。接下来本文以一轮迭代为单位分析这两部分的通信时间复杂度。对于第一部分，用户需要与min(D×|Ci|,D×H)位朋友交换梯度密文，每个梯度密文包含Lp×K个字节。因此，一轮迭代中用户之间的通信时间复杂度是|R|×(Lp×K)×min(D×|Ci|,D×H)。对于第二部分，用户需要将Lp×K字节的密文传递给可信第三方共21+2×min(D×|Ci|,D×H)次，因此用户和可信第三方之间的通信时间复杂度为|R|×(Lp×K)×min(D×|Ci|,D×H)。总的来看，模型的通信时间复杂度为|R|×(Lp×K)×min(D×|Ci|,D×H)，它与|R|×Lp也基本呈线性关系。
根据上述分析，模型除了因密文长度所引起的必要时间复杂度外，没有产生额外的时间复杂度代价。
4 实 验
本文主要通过一些对比实验来评估当前模型的有效性，并分析部分参数的设定对模型效果的影响。此外该部分还研究了模型的时间性能，用以评估模型的有效性。
4.1 数据集
Foursquare和Gowalla是两个经典的基于位置的推荐模型数据集[23]，它们收集于真实世界。本文利用这两个数据集对模型进行评估，首先从每个国家随机选取两个城市的签到数据，然后排除过于活跃/不活跃的用户、兴趣点。预处理之后数据集的相关信息如表1所示。实验按照9 ∶1的比例划分训练集和测试集。
表1 数据集
4.2 评估指标
针对每个用户，模型对其未参观过的兴趣点进行评分，并根据评分对这些兴趣点排序。模型的推荐性能体现在从排名前k位的兴趣点中找到用户测试集中兴趣点的能力。在topk兴趣点推荐[8,17]中，这种能力通常可以由两个广泛使用的指标来衡量，即精确率P@k和召回率R@k。前一个指标反映了在topk推荐中用户实际访问了的比例，后一个指标反映了用户访问过的兴趣点出现在topk推荐中的比例。如果用Ri表示对用户i的topk推荐兴趣点集，用Vi表示i的已访问兴趣点集，评估指标计算方法如下：
(20)
(21)
4.3 比较方法
本文评估了CDMF的性能，并将其与包括MF、BPR、DMF和CDMF的变体等方法进行了比较。比较方法没有选用近两年的基于矩阵分解的先进推荐方法，例如结合用户社交信息[4]、属性信息[9]或深度学习[24]的矩阵分解方法，因为这些方法都使用了除交互矩阵的额外信息或者附加工具作为辅助。考虑到把这些模型与本文方法进行比较不够公平，本文只选择经典模型如MF、BPR等进行比较。几种对比模型的介绍如下：
MF[16]：矩阵分解模型。一种经典的集中式方法，它将用户-兴趣点交互矩阵转化为两个潜在因子的乘积，并使用最小二乘法计算损失函数。
BPR[25]：贝叶斯个性化排名模型。与传统的矩阵分解相比，BPR也将用户-兴趣点交互矩阵分解为两个潜在因子，但它的目的是减少成对排名的损失。
DMF[12]：分布式矩阵分解模型。比起传统的矩阵分解，它保持用户数据在自身的客户端，并通过在邻居之间传输梯度以进行潜在因子更新。
LCDMF(Local CDMF)：CDMF的变体。比起CDMF，该模型中用户不再相互交互，只在自己的客户端根据个人的签到数据学习潜在因子。该特例会在正则化系数β很大时产生。
GCDMF(Global CDMF)：CDMF的另一个变体。比起CDMF，该模型中用户不再保留私有兴趣点潜在因子更新维度，它将整个兴趣点潜在因子维度传递给朋友，保证每个人都会得到相似的兴趣点潜在因子。该特例会在正则化系数γ很大时产生。
4.4 超参数设定
实验预设了一些参数来控制模型训练的复杂性：学习率θ=0.1；正则化系数α=β=γ=0.1；用户的最大朋友数H=2，随机游走的最大步长D=4，用于平衡模型计算量和推荐精确率。此外，实验还设置兴趣点推荐数量k∈{5,10}，潜在因子的维度K∈{5,10,15}，后续实验结果会展示这些参数选择不同值产生的影响。
4.5 比较结果
对于每一个模型，实验都试图获得它们的最佳效果用于比较。分布式模型DMF、CDMF及其变体获取每个城市效果的平均值。表2展示了在不同数据集中不同方法的精确率和召回率。
表2 各模型在不同数据集和潜在因子维度下的实验结果
1) 当潜在因子的维度K变大时，所有模型的性能都有了改善。原因是K表示从兴趣点中划分出的属性个数，其越大，模型学到的属性信息就越多。
2) LCDMF的性能最差，因为每个用户只能根据自己的签到数据学习偏好。这个现象说明了协同学习在推荐中的重要性。
3) BPR比MF表现更好，因为个性化排名比最小二乘法更适合推荐系统的损失计算，推荐需要的是相对排名不是绝对分值。实验表明，当K=15时，BPR甚至是效果最好的。由此可见，BPR对MF的改进效果是明显的。
4) DMF的实验结果优于MF，因为DMF从个人和大众的角度学习了兴趣点潜在因子，获得了更个性化的推荐模型。此外，因为其协同学习的主要对象是邻居，避免了来自无关或负相关用户的信息干扰。
5) GCDMF的性能优于MF。该模型与MF相似，都协同地学习了公有兴趣点潜在因子。不同点在于，它通过引入朋友概念和个人兴趣点集合概念提前剔除了一些噪声数据。
6) CDMF始终优于DMF和GCDMF。与DMF相比，CDMF引入了个人兴趣点集合。用户具有很强的地理依赖性，所以对于用户具有相似偏好程度的两个兴趣点，虽然矩阵分解方法对它们打分相似，但距离用户更近的那个兴趣点其实对用户的吸引力更高。这种情况下，引入个人兴趣点集合排除距离较远的兴趣点，可以帮助用户去除一些虽然感兴趣但不会去的兴趣点噪声数据。与GCDMF相比，除了对兴趣点的公有偏好外，用户还在各自的客户端提取了对兴趣点的私有偏好，从而获取了个性化兴趣点潜在因子，促进个性化偏好学习。
4.6 参数分析
不同的参数设定对模型有不同的影响。本节分析了两个代表性的参数对模型的影响，分别为随机游走最大步长D和最大迭代次数T。
随机游走最大步长D，决定了每次更新时用户要与多少朋友进行数据交互，D的大小直接影响模型的时间复杂度。此处设置潜在因子维度K=5并进行实验。图3展示了在Foursquare和Gowalla数据集上模型的精确率和召回率随着D增加产生的变化。从结果来看，随着D的增加，模型的精确率也在不断提高，当D超过3时，精确率趋于稳定，这意味着模型可以设置D=3或D=4，以获得精确率和时间复杂度之间的平衡。
图3 随机游走最大步长D对模型CDMF的影响
最大迭代次数T，用于控制模型的训练次数。在Foursquare和Gowalla数据集上的实验结果如图4所示。可以看出，在模型收敛之前，T越大，模型损失越小，迭代了约175次后模型达到收敛，之后增加T模型损失基本不变。所以模型可以设置T≈180,降低模型时间复杂度。
图4 最大迭代次数T对模型CDMF的影响
参数分析实验中，Gowalla数据集的实验结果总是更好一些。这可能是因为选取的这部分Gowalla数据集具有更高的城市密度，导致用户与兴趣点之间的相关性更大，学习潜在因子也就更容易些。
4.7 时间损失分析
加密算法因为其计算复杂度太高，在许多应用中受到限制。为了提高加密算法的时间性能，CDMF提出了个人兴趣点集合，并在Foursquare数据集上进行了时间性能测试，如图5所示。
(a) 时间损失 (b) 精确率图5 个人兴趣点集合对模型时间性能和精确率的影响
如图5(a)所示，实验提取了三个不同城市的用户集，它们分别包含50、200和400个用户，在这三个数据集上观察模型的时间性能随着个人兴趣点集合增大产生的变化。横坐标表示个人兴趣点集合的数量，纵坐标表示每个用户的收敛时间。实验表明，当个人兴趣点数大于200时，用户数越少，每个用户需要的收敛时间就越多。原因是随着用户数量的减少，用户的平均等待时间占总时间的比重增加。当个人兴趣点数小于200时，用户数几乎不影响收敛速度。这是因为当个人兴趣点数较少时，梯度更新较快，使得用户的等待时间足够小。当用户数量保持不变时，个人兴趣点数越多，每个用户的收敛时间就越长，说明缩小个人兴趣点集合有助于加速模型收敛。
图5(b)显示了个人兴趣点数的设置对推荐精确率的影响。实验表明，随着个人兴趣点数量的增加，不同数据集的推荐精确率也随之提高。但当个人兴趣点数超过300时，推荐精确率开始下降。这是因为当个人兴趣点集过小时，许多用户感兴趣的兴趣点可能会被错误地排除掉，而过多时又会产生更多的噪声。另外，随着个人兴趣点集合的减小，大城市的推荐精确率下降得比小城市快。这与不同城市拥有不同的兴趣点密度有关，兴趣点密度越大的城市，相同的地理范围内兴趣点数就越多。通常大城市比起小城市具有更高的兴趣点密度，同等活动范围内大城市的用户可以到达更多的兴趣点，因此其个人兴趣点集合应该更大。这两个实验表明，模型可以将个人兴趣点集合长度设置在100到300之间以平衡模型精确性和时间性能。
5 结 语
本文提出了一种基于密文的去中心化矩阵分解推荐算法CDMF。为了将集中式服务器的计算压力分散到每个用户的终端，模型将用户的数据保存在各自的终端，并使用随机游走的方法选择交互用户。为了保护交互数据，模型利用Paillier加密算法来加密数据。此外，CDMF还提出个人兴趣点集合概念来加快收敛速度。在保证隐私的前提下，CDMF相比传统矩阵分解其精确率和召回率分别提升约1百分点和9百分点。该模型还具有普遍适用性，在其他如网站服务、音乐等项目推荐中也适用，因为模型只是矩阵分解方法的变体。
