DPLORE：一种差分隐私保护位置推荐算法

杨达森

（广东工业大学 计算机学院，广东 广州510006）

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

用户签到的历史位置可以揭示个人出行或生活方式等敏感细节。目前，位置推荐算法有协同过滤技术[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算法能够通过较低的拉普拉斯噪声注入实现ε-差分隐私。对于发布高维度数据集问题，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]利用ε-差分隐私将随机噪声添加到用户的签到位置的统计数据中，并且只向位置推荐系统发布这些噪声统计数据。GS和DPSS算法虽然可以处理在高度敏感的数据上发布大量统计数据的问题，但是对于一些具有大量统计数据值小的结果，例如，用户位置签入转移计数，它们添加的噪声严重降低了数据的可用性。

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

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

1.2 理论基础

1.2.1 马尔可夫链

2 算法框架描述及分析

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

2.1 算法框架描述

2.2 算法实现细节

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

3 实验结果分析

3.1 实验设置

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

表1 数据集的基本统计信息Table 1 Basic statistics of dataset

3.2 实验结果评估指标

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

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

3.3 结果分析

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

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

图1 不同k 下的准确率和召回率Fig.1 Precision and recall under different k

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

图2 不同隐私预算ε 下的准确率和召回率Fig.2 Precision and recall under different ε

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

图3 衰减率α 对准确率和召回率的影响Fig.3 Effect of decay rate αon precision and recall

4 结论

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