随着移动设备的发展，最新一代的移动设备允许用户连接到地理社交网络服务中，让用户分享他们在访问特定地点时的亲身体验。用户分享的位置隐私数据常常被用于分析、统计和挖掘。这些有价值的隐私数据受到互联网等领域研究者的关注，特别是在位置推荐领域。然而，当前面临的挑战是如何保护用户的位置数据的同时保证位置推荐的准确度。直接向不可信推荐系统发布用户历史访问位置会导致严重的位置隐私泄露问题。

用户签到的历史位置可以揭示个人出行或生活方式等敏感细节。目前，位置推荐算法有协同过滤技术^[1]、序列技术^[2]等。协同过滤技术也可与其他信息相结合^[3]，例如用户与社交朋友地理坐标之间的联系。由于社交朋友更容易分享共同的兴趣，因此社交链接信息被广泛用于测量用户之间的相似性，结合协同过滤技术可以提高位置推荐的精度。目前研究工作从用户的签到位置序列中提取序列模式，利用全局或个人马尔可夫模型分别挖掘用户运动的全局行为和个体模式信息，并根据过去的位置序列预测用户可能感兴趣的位置。而 $n$ -阶马尔可夫模型^[4]通过统计用户访问每个地点的频次，然后计算每个位置被访问的概率作为转移概率矩阵，并在转移概率矩阵上使用马尔可夫链生成位置推荐结果。虽然马尔可夫模型在位置推荐中应用很广泛，但在计算地点访问频次以及求概率时都有可能泄露用户的隐私，如果直接发布马尔可夫模型容易泄露敏感信息。

现有的几种技术部分解决了位置隐私泄露问题。第一种位置隐私保护方法是 $k$ -匿名^[5]。 $k$ -匿名技术确保每个发布的位置必须与其他 $k - 1$ 位置不可区分。如 $k$ -匿名的扩展模型 $LK$ -匿名隐私保护方法^[6]，在公开的轨迹数据库中 $LK$ -匿名隐私保护要求每一个位置序列的最大长度L至少与K条记录不可区分。虽然这种类型的转换既快又简单，但极易受背景知识攻击。第二种方法是差分隐私保护。针对 $k$ -匿名易受背景知识的攻击者攻击，Dwork等^[7]提出差分隐私保护模型，差分隐私是一种通过向查询或分析结果中适当添加噪声来达到隐私保护效果的方法，并且严格定义量化评估的方法。因此攻击者不能以偶然的概率得知某个个体的信息是否包括在数据集中，保护了用户的位置隐私，同时仍然可以利用关于数据的噪声统计结果来进行数据挖掘。Kellaris等^[8]提出了分组与平滑算法(Grouping and Smoothing,GS)，一种通过细粒度分组和平滑平均预处理计数的方法，通过初步扰动的形式，降低了敏感度，使得GS算法能够通过较低的拉普拉斯噪声注入实现 $\varepsilon $ -差分隐私。对于发布高维度数据集问题，Day等^[9]提出一种基于敏感度控制的差分隐私数据集统计信息发布方法(Differential Privacy Sensitivity,DPSS)。鲜征征等^[10]提出差分隐私与协同过滤结合的算法(Differential Privacy Singular and Output,DPSAOut++)来保护用户隐私，最后向用户推荐其感兴趣的项目。

针对位置推荐中隐私保护的问题，本文提出基于自适应权重的 $n$ -马尔可夫链的差分隐私位置推荐算法模型。该模型不仅可以防止任意背景知识攻击者的攻击，还在保护用户位置隐私的同时保证了位置推荐的准确度。相对于已有的研究，算法模型分配的隐私预算更加合理，同时向用户提供个性化的位置推荐，提高了位置推荐的精度。最后，在两个公开数据集上进行实验，相比GS算法、DPSS算法和DPSAOut++算法，从推荐结果方面，本文提出的差分隐私位置推荐模型表现出了更好的实验效果。

1 相关工作 1.1 差分隐私位置推荐

近年来，研究者对位置推荐算法进行了大量研究。基于协同过滤的思想，Noulas等^[11]通过提取用户信息中地理位置的类型、时间戳、用户移动方向等特征结合监督学习模型向用户推荐下一时刻可能感兴趣的地点。文献[12]通过考虑地理和时间属性对用户访问下一地点的影响，提出一种混合的矩阵分解方法，以实现受欢迎地点的推荐。Lu等^[13]揭示了用户对地点访问的决策依赖于多个因素，因此设计了一个综合考虑各种因素的推荐结果的地点推荐框架。这些方法主要分析用户与地理位置之间的关系，缺乏对语义信息以及用户本身偏好的考虑。

在为用户提供推荐服务的同时，可能会出现用户隐私泄露的情况。因此，位置推荐系统需要保护用户个人隐私的同时，向用户提供个性化推荐服务。文献[14-15]利用 $\varepsilon $ -差分隐私将随机噪声添加到用户的签到位置的统计数据中，并且只向位置推荐系统发布这些噪声统计数据。GS和DPSS算法虽然可以处理在高度敏感的数据上发布大量统计数据的问题，但是对于一些具有大量统计数据值小的结果，例如，用户位置签入转移计数，它们添加的噪声严重降低了数据的可用性。

在差分隐私位置推荐算法研究中，Liu等^[16]将差分隐私结合协同过滤推荐技术，实验表明在没有严重损失推荐准确率的情况下可以向用户提供个性化推荐，但算法未能考虑到潜在因子模型。Li等^[17]针对用户兴趣点的推荐，将原始位置序列数据转为二部图,然后提取二部图中的关联矩阵，通过向矩阵元素中添加噪声以满足 $\varepsilon $ -差分隐私保证。虽然保护了用户的位置数据隐私，但算法向用户推荐的是粗粒度的位置区域，不是具体的位置地点。文献[18]基于不同用户的位置信息特征，提出一种个性化的位置推荐，将用户的特征分为隐私保护信息和非隐私保护信息两类，使得一部分具有隐私泄露风险的用户信息得到保护，而不具风险的信息则主要用于提高推荐的准确率。

差分隐私位置推荐研究的难点在于位置域维度高，数据稀疏，精准、个性化推荐难度大，虽然保护了用户隐私，但是导致最后向用户推荐位置的效果不佳。本文基于马尔可夫模型，提出基于差分隐私的自适应权重 $n$ -阶马尔可夫链位置推荐算法。算法对所有用户原位置计算转移计数矩阵，针对算法中矩阵维度大、稀疏的问题，本文采用奇异值分解(Singular Value Decomposition, SVD)矩阵分解的方法分解转移计数矩阵，然后利用差分隐私向分解后的矩阵添加拉普拉斯噪声，保护用户的隐私，最后结合自适应权重 $n$ -阶马尔可夫链位置推荐算法向用户提供个性化的推荐。

1.2 理论基础 1.2.1 马尔可夫链

转移概率：假设数据集 $D = \{ {S_1}, \cdots ,{S_M}\} $ 为所有用户历史签到位置序列， $L$ 为位置域集合，用户 $u$ 按时间签到的位置序列为 ${S_u} = ({l_1} \to \cdots \to {l_{n - 1}} \to {l_n})$ ，其中 ${l_i} \in L$ ， ${l_i} \to {l_j}$ 表示用户 $u$ 从 ${l_i}$ 转移到下一个位置 ${l_j}$ 。用 ${T_C}({l_i} \to {l_j})$ 表示所有用户从 ${l_i}$ 转移到 ${l_j}$ 的计数，则 ${l_i} \to {l_j}$ 对应的转移概率如式(1)所示。

${T_P}_{ij}({l_i} \to {l_j}) = \frac{{{T_C}({l_i} \to {l_j})}}{{\displaystyle \sum\nolimits_{j = 1}^{|L|} {{T_C}({l_i} \to {l_j})} }}$

(1)

自适应权重 $n$ -阶马尔可夫链：给定用户 $u$ 的位置序列 ${S_u}$ ， $n$ -阶马尔可夫链定义为用户 $u$ 在依次访问 ${l_1}, \cdots ,{l_n}$ 后，访问下一个目标位置 ${l_j}$ 的概率，用式(2)表示，其中 ${w_i}$ 是权重系数。

${P_r}({l_j}|{S_u}) = \sum\nolimits_{i = 1}^n {{w_i}{T_P}_{ij}({l_i} \to {l_j})} \propto \sum\nolimits_{i = 1}^n {{w_i}{T_C}_{ij}({l_i} \to {l_j})} $

(2)

1.2.2 差分隐私定义

差分隐私是一种概率隐私模型，假设在只相差1条记录的2个数据集中，使用差分隐私保护的方法分析这2个数据集的结果不会有明显的差别，即从2个数据集中获得相同结果的概率相似。因此，即使攻击者拥有背景知识，也无法判断某条记录是否在数据集里，即不能以任何方式侵犯个人隐私。

$\varepsilon $ -差分隐私：对于至多只相差1条记录的2个数据集 ${D_1}$ 和 ${D_2}$ ，即 $|{D_1}\Delta {D_2}| = 1$ ， $M$ 为一随机化算法， $R(M)$ 表示算法 $M$ 的所有可能的输出构成的集合， $S$ 是 $R(M)$ 的任一子集。若算法 $M$ 提供 $\varepsilon $ -差分隐私保护，则对于所有的 $S \in R(M)$ ，有

$P[M({D_1}) \in S] \leqslant {{\rm{e}}^{\varepsilon}}P[M({D_2}) \in S]$

(3)

概率 $P[E]$ 表示事件 $E$ 的披露风险，由算法 $M$ 的随机性所控制， $\varepsilon $ 是由数据拥有者视隐私保护程度所指定的参数，也称为隐私预算，隐私保护程度越高， $\varepsilon $ 的取值越小。这一定义表示为，对算法 $M$ 的任一可能输出而言，无论函数的输入是 ${D_1}$ 还是 ${D_2}$ ，得到这一输出的概率相差很小。

1.2.3 差分隐私的实现机制

差分隐私保护需要对转移计数添加噪声来实现，常用的一种实现噪声添加技术是拉普拉斯机制，而噪声大小与全局敏感度有关。

全局敏感度：对于函数 $f:D \to {{{R}}^d}$ ，输入为数据集 $D$ ，输出 ${{{R}}^d}$ 为任一 $d$ 维实数向量，数据集 ${D_1}$ 和 ${D_2}$ 之间至多相差一条记录， $f$ 的全局敏感度定义为

$\Delta f = {\max _{{D_1},{D_2}}}||f({D_1}) - f({D_2})|{|_1}$

(4)

其中， $||f({D_1}) - f({D_2})|{|_1}$ 表示 $f({D_1})$ 和 $f({D_2})$ 之间的1-阶范数距离。

拉普拉斯机制：对于数据集 $D$ 上的任一函数 $f: D \to {{{R}}^d}$ ，如果算法 $M$ 的输出结果满足式(5)， ${L_a}\left(\dfrac{{\Delta f}}{\varepsilon }\right)$ 是拉普拉斯分布函数产生的随机噪声，则 $M$ 满足 $\varepsilon $ -差分隐私保护。

$M(D) = f(D) + {L_a}\left(\frac{{\Delta f}}{\varepsilon }\right)$

(5)

2 算法框架描述及分析

本文提出的差分隐私保护位置推荐算法框架DPLORE分为差分隐私保护模块和位置推荐模块。对原始用户位置签到数据计算其转移计数，然后向统计数据提供差分隐私保护。将已受保护的噪声转移计数作为位置推荐系统输入，利用自适应权重 $n$ -阶马尔可夫链算法向用户推荐其感兴趣的位置。在最后的位置推荐实验结果中，算法能够在不失准确率和召回率的情况下保护用户的位置隐私。

2.1 算法框架描述

计算满足差分隐私的转移计数矩阵算法过程为：

算法1 计算差分隐私转移计数矩阵

输入：数据集用户的数量 $m$ ，位置数量 $|L|$ ，所有用户签到位置序列 ${S_1},{S_2}, \cdots ,{S_m}$

输入：隐私预算 ${\varepsilon _1},{\varepsilon _2},{\varepsilon _3}$

输出：噪声转移计数矩阵

1: T_C[|L|][|L|]=0

2: for $i = 1$ to $m$ do

3:　　for $j = 1$ to $|{S_i}| - 1$ do

4:　　　 ${l_{i,j}} = {S_i}[j]$

5:　　　 ${l_{i,j + 1}} = {S_i}[j + 1]$

6:　　　　 T_C[l_i,j][l_i,j+1]+=1

7:　　end for

8: end for

9: U_|L|×r′ ${{\varSigma}}$ _r×r′V ^T_r×|L|=SVD(T_C[|L|][|L|])

10: ${ U}'_{|L|\times r} $ =U_|L|×r+L_a(1/ε₁)

11: ${{\varSigma}}_{r\times r}'$ = ${{\varSigma}} $ _r×r+L_a(1/ε₂)

12: V ^T′_r×|L|=V ^T_r×|L|+L_a(1/ε₃)

13: ${ T}'_C $ [|L|][|L|]= ${ U}'_{|L|\times r}{{\varSigma}}_{r\times r}'$ V ^T_r×|L|

14: return ${ T}'_C$ [|L|][|L|]

算法2将算法1输出的噪声转移计数矩阵用于自适应权重的 $n$ -阶马尔可夫链模型向用户返回推荐结果，具体步骤为：

算法2 自适应权重的 $n$ -阶马尔可夫链推荐算法

输入：用户 $u$ 的位置序列 ${S_u} = ({l_1}, \cdots ,{l_m})$ ，噪声转移计数矩阵T_C^’[|L|][|L|]，位置域集合 $L$ ，衰减率参数 $\alpha $

输出：推荐位置得分前 $k$ 高的位置集合 ${T_{kl}}$

1: ${T_{kl}} = \phi $

2: ${L_s} = \phi $

3: for $i = 1$ to $|L|$ do

4:　　 $s = 0$

5:　　if $L[i] \notin {S_u}$ then

6:　　　for $j = 1$ to $|{S_u}|$ do

7:　　　 ${l_n} = L[i]$

8:　　　 ${l_u} = {S_u}[j]$

9:　　　 ${t_p} = {T_P}[{l_u}][{l_n}]$

10:　　　 $w = {2^{ - \alpha (|{S_u}| - j)}} \times {t_p}$

11:　　　 $s = s + w$

12:　　end for

13:　end if

14:　 ${L_s}[{l_n}] = s$

15: end for

16: 返回 ${L_s}$ 中得分前 $k$ 高的位置集合 ${T_{kl}}$

2.2 算法实现细节

算法1首先初始化一个 $|L| \times |L|$ 的转移计数矩阵用来保存用户的签到位置序列中的位置转移计数。然后遍历每个用户的位置序列，位置 ${l_i} \to {l_j}$ 为一次位置转移，累加保存到对应下标的转移计数中。因为得到的转移计数矩阵维度大，而且稀疏，添加拉普拉斯噪声量过大，导致数据可用性低。因此使用SVD方法对矩阵进行分解降维，最后分配不同的隐私预算，向分解后的低维矩阵U_|L|×r、 ${{\varSigma}} $ _r×r、V ^T_r×|L|元素添加拉普拉斯噪声。

算法2根据噪声转移计数矩阵，计算转移概率T_P，结合用户 $u$ 的历史位置序列信息向用户推荐得分前 $k$ 高的新位置。首先，对于用户下一个可能感兴趣位置 ${l_n}$ 的选择与用户的签到历史位置相关， ${t_p}$ 为用户从位置 ${l_u}$ 访问 ${l_n}$ 的概率，即 ${l_u} \to {l_n}$ 的转移概率为 ${t_p}$ ，因为每一个历史位置对 ${l_n}$ 的选择影响大小不同，即 ${l_u} \to {l_n}$ 的概率值的相关系数不是每次相等的，实际情况中，最后几次的历史访问位置与下一个感兴趣位置点的相关系数更大，因此需要对其分配更大的权重系数，以提高推荐效果的精度。算法中自适应权重为 ${2^{ - \alpha (|{S_u}| - j)}}$ ，其中 $\alpha $ 为衰减率参数。算法最后向用户返回得分前 $k$ 高的新位置。

3 实验结果分析 3.1 实验设置

本文提出的算法使用Python实现，本节中所有实验的硬件环境为Intel(R) Core(TM)i7 2.70 GHz，内存为8 GB。采用2个不同规模的公开数据集，分别是Foursquare、Brightkite来验证算法的有效性。首先对原始数据进行预处理，过滤地点在数据集中出现少于5次的数据，过滤数据集中用户签到位置数量少于10次的用户，以及用户在同一时间连续在同一位置进行签到的异常数据，最后保留的数据集的基本统计信息如表1所示。

3.2 实验结果评估指标

一般来说，位置推荐算法通过计算每个候选位置对目标用户的得分，并将得分最高的前 $k$ 个位置作为推荐结果返回给目标用户。为了评估位置推荐的效果，重要的是找出目标用户在测试数据集中实际访问了多少位置。因此，本文利用准确率和召回率作为评价差分隐私保护的位置推荐算法的效用，其值越大，表明结果越好。

准确率的定义为，给出目标用户的得分前 $k$ 高的位置推荐结果与对于用户测试位置数据的交集数量与 $k$ 的比值。用式(6)表示，其中 ${S_r}$ 为推荐的结果集合， ${S_t}$ 为目标用户的测试数据集合。

$ p = \frac{{|{S_r} \cap {S_t}|}}{k} $

(6)

召回率的定义为，给出目标用户的得分前 $k$ 高的位置推荐结果与对于用户测试位置数据的交集数量与目标用户测试数据的位置域的比值。用式(7)表示，其中 ${S_r}$ 为推荐的结果集合， ${S_t}$ 为目标用户的测试数据集合。

$ r = \frac{{|{S_r} \cap {S_t}|}}{{|{S_t}|}} $

(7)

3.3 结果分析

在实验中，每个数据集将依据用户签入时间顺序划分为训练集和测试集，一半具有较早时间戳的签入数据作为训练集，另一半签入数据作为测试集。在向用户推荐的位置数 $k$ 对实验结果的影响中，实验参数设置方面，将 $k$ 设在2到22的区间范围。默认情况下，总隐私预算 $\varepsilon $ 为0.1，其中 $\varepsilon = {\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3}$ ， ${\varepsilon _1}:{\varepsilon _2}:{\varepsilon _3} = 2:1:2$ ，衰减率参数 $\alpha $ 为0.5，实验对比GS算法、DPSS算法和DPSAOut++算法，GS算法是一种通过细粒度分组和平滑平均预处理计数降低敏感度来实现 $\varepsilon $ -差分隐私的方法。DPSS是一种敏感度可控的差分隐私高维度数据集统计信息发布方法。DPSAOut++是SVD++算法结合差分隐私，对输出结果进行扰动的隐私保护算法。对比实验结果如下。

图1是本文提出的算法DPLORE与3种不同算法在两个不同的数据集，不同的位置推荐数 $k$ 下的准确率和召回率的结果。可以看出，在2个不同的数据集下，随着 $k$ 的增加，4个算法的准确率都在降低，而召回率都在提高。一般来说，通过为用户返回更多的位置，它总是能够发现用户希望访问的更多位置。然而，由于这些位置的访问概率较低，额外推荐的位置不太可能被用户喜欢。但本文提出的算法DPLORE准确率和召回率在大多数情况下优于其他3个对比算法。

图2是2个数据集在不同的隐私预算下，本文提出的算法DPLORE与3种不同算法的准确率和召回率的对比实验结果。实验中位置推荐数 $k$ 设为10，随着隐私预算的增加，4个算法的准确率和召回率都在提高，因为隐私预算越大，数据隐私保护的力度越小，总添加的噪声越小，所以准确率和召回率越高。本文的算法在不失准确率和召回率的情况下提供了更好的差分隐私保护。

图3描述了衰减率参数 $\alpha $ 的取值对算法准确率和召回率的影响。当参数 $\alpha $ 在0.25到1.0之间时，本文提出的算法结果变化相对稳定，可以在这个区间选择一个合适的值，而不是找到最优值来避免算法过度拟合，使得算法推荐结果的准确率和召回率在可接受的范围。而当参数 $\alpha $ 不在这个区间时，算法的准确率和召回率明显降低。这是因为， $\alpha $ 值大，算法过度地认为最近访问的地点就是用户感兴趣的地点，低估了过去访问地点会影响用户下一个感兴趣点的选择。然而， $\alpha $ 值小容易对所有历史访问的地点进行同等的看待，最终影响推荐的结果。

4 结论

本文提出基于差分隐私的位置推荐算法DPLORE，目的是为了提高位置推荐的准确率和召回率的同时保护用户的位置隐私。本文的算法通过改进噪声的添加方式，在同等隐私预算下，向分解后的转移计数矩阵添加的噪声量更少，在推荐算法模块中，使用改进的自适应权重的 $n$ -阶马尔可夫链模型，在Foursquare、Brightkite数据集上的实验结果表明，该算法能够在保护用户位置隐私的同时，仍然保证位置推荐的准确率和召回率。下一步尝试将本文的算法应用在交通轨迹数据领域，为其他领域的数据提供差分隐私保护机制，以保护数据隐私等问题。