基于位置推荐中的隐私保护方法研究

张海涛，汪佩佩

(1.南京邮电大学 地理与生物信息学院，江苏 南京 210023; 2.南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

近年来，随着人们从海量信息中找到自己所需要位置信息的需求日益强烈，位置推荐系统得到了广泛的应用[1-3]。基于位置的推荐系统主要是利用用户向服务器发送位置服务请求以及用户所在的地理位置来为用户提供个性化的服务。推荐系统结合用户的兴趣偏好与地理位置，对服务的内容进行分析，最终返回用户所需要的服务信息[4]。在位置推荐系统中，服务器为给用户提供个性化服务，会储存记录大量用户的评价及推荐信息，并从中挖掘出隐藏的、有用的信息，从而为请求用户返回有效的推荐结果[5]。但是，这些位置推荐服务，会对用户的隐私构成一定的威胁。

位置推荐系统当前面临着基于敏感位置和位置独立性的隐私推理攻击。敏感位置推理攻击是指攻击者结合推荐结果中的敏感位置数据及相关的背景知识，推断出用户的偏好信息[6-7]和社会属性。位置独立性推理是指攻击者结合推荐结果中的独立性位置数据和收集到的其他用户信息，获取用户隐私信息。截止目前，已有大量的研究指出，位置推荐系统在为用户提供服务时会造成用户隐私的泄露。因此，位置推荐过程中的隐私保护成为当前研究的热点。

针对位置推荐中的隐私保护问题，国内外学者已提出了很多解决方法。文献[8-9]中提出通过匿名的方法来对用户的位置隐私进行保护。文献[10-11]中提出了基于差分隐私保护的位置隐私保护机制。此外，Shao等[12]提出了一种属性加密方案。文献[13-14]提出了一种以密码学为基础的方案。Zhu等[15]基于移动端APP流行度以及用户的隐私需求设计了个性化的具有隐私感知功能的智能APP推荐系统。

但是，上述方法均不能对推荐结果中的敏感位置数据和独立性位置数据做出有效处理。基于此，文中提出了一种基于敏感位置和独立性位置推理攻击的隐私保护方法。

1 基于位置推荐的隐私攻击

1.1 基本定义

定义1(位置)：将位置定义为S={p1,p2,…,pn}，其中pn表示位置点的特征值。

定义2(敏感位置)：对于位置S，如果其任意特征值p(p∈S)具有敏感属性，那么S就是敏感位置。

定义3(基于敏感位置的推理攻击)：如果推荐系统返回给用户的推荐线路R(u1)={S1,S2,…,Sn}满足Sn∈R且Sn为敏感位置，则该推荐结果会使用户受到基于敏感位置的推理攻击。

定义5(基于位置独立性的推理攻击)：如果推荐系统返回给用户的推荐线路R(u1)={S1,S2,…,Sn}满足Sn∈R且F(Sn)=1，则该推荐结果会使用户受到基于位置独立性的推理攻击。

1.2 推理攻击步骤

基于敏感位置的推理攻击的主要步骤如下：

(1)基于用户提出的位置请求服务，服务器给用户返回推荐列表LR={R1,R2,…,Rn}。

(2)对所有Rn(Rn∈LR)，利用定义2进行敏感位置检测。

(3)将敏感位置进行标注，作为对用户隐私进行攻击的依据。

(4)输出含敏感位置数据的推荐列表。

基于位置独立性的推理攻击的主要步骤如下：

(1)服务器返回满足用户需求的推荐列表LR。

(2)利用定义4对LR中的所有Rn进行位置独立性检测。

(3)将独立性位置进行标注，作为对用户隐私进行攻击的依据。

(4)输出含独立性位置数据的推荐列表。

2 感知隐私推理攻击的位置推荐算法

2.1 系统架构

为应对基于敏感位置和位置独立性的隐私推理攻击，设计了基于隐私保护服务器的推荐系统架构。整个系统架构主要由用户、应用服务器、隐私保护服务器三部分组成。推荐及隐私保护过程如下：

(1)用户发送位置服务请求给应用服务器，应用服务器结合请求用户和其他用户的位置信息，找到相似度最高的用户信息，以此为基础生成推荐列表，并将其发送给隐私保护服务器。

(2)隐私保护服务器收到推荐列表后，会对列表中的数据进行隐私检测，然后将处理后的数据返回给应用服务器。

(3)应用服务器将推荐结果返回给用户[16]。

2.2 算法实现

根据2.1中提到的系统架构，文中设计的两种隐私保护算法的流程描述如下：

(1)用户提出位置服务请求。

(2)应用服务器接收用户请求信息，计算用户相似度，生成推荐列表。

(3)对推荐列表中的数据进行敏感位置检测，若包含敏感位置数据则隐藏。

(4)对推荐结果中的数据进行独立性位置检测，如果包含独立性位置数据则进行步骤5，否则进行步骤6。

(5)删除独立性位置数据。

(6)判断推荐结果数量是否满足用户需求，满足则输出推荐结果，不满足则重复步骤2～6。

算法实现的伪代码如下所述：

算法：RL:Privacy Protection(ML,Count,Req)

输入：移动终端位置(ML)、所需位置推荐数(Count)及位置请求(Req)

输出：推荐列表(RL)

数据库：用户位置数据(DB)、敏感位置数据(SD)、独立性位置数据(UD)

1.InsertML,Req into DB

2.While(RR.Count=Count and RR not contain SD and RR not contained)

3.{

4.RL=Reco()

5.If RL contain SD

6.RS()

7.else if RL contain SD

8.RU()

9.else return RL

10.}

函数Reco()

1.M=ALS.train(D,ε)

2.for eachε'

3.{

4.if ALS.train(D,ε')优于M

5.M=ALS.train(D,ε')

6.}

7.returnM

函数RS()

1.for eachr∈RL

2.{

3.ifrcontain SD

4.RL remover

5.}

6.return RL

函数RU()

1. for eachr∈RL

2.{

3.ifrcontain UD

4.RL remover

5.}

6.return RL

算法中第1行是将移动终端位置及位置请求信息导入到数据库中；第2行是一个循环推荐过程，当推荐结果的数量满足用户的需求时，已删除敏感位置数据和独立性位置数据，就退出循环；第4行是对移动终端的请求进行位置推荐；第5～6行是隐藏敏感位置数据；第7～8行是删除独立性位置数据;第9～10行是返回推荐结果给用户。

函数Reco()主要是找到与请求用户相似度较高的用户信息。

函数RS()、RU()分别检测推荐结果中有无敏感位置数据和独立性位置数据。如果有，则将数据删除，然后将推荐结果返回给用户。

2.3 实例分析

下面结合一个例子，介绍算法的基本实现过程。用户甲在图1中的位置提出了景点推荐的请求，其提供的自身喜好程度由高到低排序依次为：电影院(9分)、商场(7分)、美食(5分)。

图1 地图信息

数据库中已有的用户信息如表1所示。

表1 数据库用户信息

(1)根据用户的位置服务请求，将用户与其他用户进行相似度计算，得到的相似度最高的3位用户序号依次为2，4，5。

(2)将相似度最高的3位用户2，4，5的路线作为推荐结果进行隐私检测，检测结果如下：

路线A→B→H→E中不包含敏感位置和独立性位置；

路线A→B→H→E→C中不包含敏感位置，但是包含独立性位置；

路线K→B→I→J中不包含独立性位置，但是包含敏感位置。

(3)删除推荐结果中用户4，5推荐的线路，递补相似度较高的用户6推荐的线路，并进行隐私安全检测，检测结果正常。

(4)将线路A→B→H→E与A→B→H推荐给用户甲。

3 实验结果与分析

实验数据主要由位置数据、样本数据、评分数据组成。位置数据由400个网格组成，样本数据包含了发出服务请求的用户信息，评分数据包含了数据库中所有用户的信息。通过对评分数据进行统计，得到数据库中的用户数为4 382，有评分的网格数为385，用户对网格的平均评分为5分(评分等级为1～10)，各评分等级网格数会随着生成的实验数据的不同而有所变化。

实验1：对比分析基于敏感位置的隐私检测算法对推荐结果的影响。

该实验将基于敏感位置的隐私检测算法与位置推荐算法相结合，依次选取敏感等级G=6，7，8，9，10时生成的数据进行实验(当G=6时，实验会对隐私等级大于等于6的推荐结果中的位置数据进行隐私保护)。将所得实验结果与正常推荐所得结果进行比较，对比结果如图2～4所示。

由图2可以看出，进行隐私保护时，敏感位置数会随着隐私等级的升高而减少。不进行隐私保护时，敏感位置数不受隐私等级的影响，数量一直为0。由图3可以看出，进行隐私保护时，推荐给用户的位置数会随着隐私等级的升高而增加，而不进行隐私保护时，推荐给用户的位置数不受隐私等级变化的影响，并且一直高于进行隐私保护时系统推荐给用户的位置数量。由图4可以看出，进行隐私保护时对推荐结果的平均检测时间始终高于未进行隐私保护时的平均检测时间，但是差值不大。结果表明：基于敏感位置的隐私保护方法能有效找到推荐结果中的敏感位置数据，并且检测到的敏感位置数、推荐给用户的位置数以及平均推荐用时均随敏感等级的增加呈线性变化，而不是指数型变化，变化范围波动不大;提出的算法具有代价小、速度快、可用性强的优点，对用户的隐私保护具有一定的意义。

图2 进行隐私保护与不进行隐私保护检测到的敏感位置平均数对比

图3 进行隐私保护与不进行隐私保护推荐给用户的位置平均数对比

图4 进行隐私保护与不进行隐私保护的平均检测时间对比

原因分析：进行隐私保护时，隐私保护服务器会对推荐结果中的数据进行敏感位置的检测。在敏感范围内，随着等级的升高，算法可检测的范围会变小，检测到的敏感位置数就会降低，能推荐给用户的位置数就随之升高。而未进行隐私保护时，应用服务器不会将生成的推荐列表发送给隐私保护服务器进行隐私检测，而是将生成的推荐列表直接返回给用户。因此，不管隐私等级如何变化，推荐结果中检测到的敏感位置数都是0，推荐给用户的位置数也一直保持不变，并且始终高于进行隐私保护时推荐给用户的位置数。

实验2：对比分析基于位置独立性的隐私检测算法对推荐结果的影响。

该实验将基于位置独立性的隐私检测算法与位置推荐算法相结合，依次选取5组数据进行实验(实验数据与敏感等级无关)。表2是基于位置独立性的检测结果。

表2 基于位置独立性的检测结果

进行独立性检测的推荐结果与正常推荐结果的对比如下：

(1)进行独立性检测的推荐和正常推荐中推荐系统返回位置的平均数量均是26。

(2)进行独立性检测的推荐中检测到的具有独立性位置的平均数是3，而正常推荐中没有检测到独立性位置数据。

结果分析：由独立性检测结果对比可以看出，在正常的推荐结果中，具有独立性特征的数据所占的比重达到了0.116。这样的推荐结果会造成用户隐私的泄露。因此，对推荐结果进行独立性位置检测有很大的必要性；在性能方面，包含独立性检测的位置推荐与正常的位置推荐耗时平均相差143 ms，差值很小，可以忽略不计。实验结果表明：文中提出的算法不仅能有效降低用户隐私泄露的风险，而且不会对生成推荐列表的时间带来太大的影响，具有较高的可用性。

4 结束语

位置推荐系统中用户位置数据的泄露严重影响着用户的隐私安全，而现有的基于位置推荐中的隐私保护方法不能有效应对基于敏感位置和位置独立性的推理攻击。为此，文中设计了一种基于敏感位置和独立性位置的隐私保护方法。通过实验对比分析正常推荐结果和进行敏感位置及独立性位置检测后的推荐结果。结果表明，该方法不会对生成推荐列表的时间带来太大的影响，并且能实现敏感位置数据和独立性位置数据的快速隐藏，具有较高的可用性。

参考文献：

[1] 涂金龙.基于tag的个性化推荐技术研究[D].重庆：重庆大学,2013.

[2] 蔺 川.基于LBS移动终端信息推荐系统的研究与实现[D].北京：北京交通大学,2016.

[3] 孙冬婷.协同过滤推荐系统中的冷启动问题研究[D].长沙：国防科学技术大学,2010.

[4] MCNEE S M,RIEDL J,KONSTAN J A.Making recommendations better:an analytic model for human-recommender interaction[C]/Extended abstracts on human factors in computing systems.Montréal,Québec,Canada:ACM,2006:1103-1108.

[5] 王付强,彭甫镕,丁小焕,等.基于位置的非对称相似性度量的协同过滤推荐算法[J].计算机应用,2016,36(1):171-174.

[6] 付达杰,张小波.基于用户兴趣与隐私保护的网络信息资源个性化推荐技术[J].景德镇高专学报,2015,30(6):42-45.

[7] 李 青,尹四清.结合用户偏好和相似性的网络结构推荐算法[J].计算机工程与设计,2016,37(3):814-818.

[8] GAO Sheng,MA Jianfeng,SHI Weisong,et al.TrPF:A trajectory privacy-preserving framework for participatory sensing[J].IEEE Transactions on Information Forensics and Security,2013,8(6):874-887.

[9] NIU Ben,LI Qinghua,ZHU Xiaoyan,et al.Enhanceing privacy through caching in location-based services[C]//Proceedings of the IEEE conference on computer communications.Kowloon,Hong Kong,China:IEEE,2015:1017-1025.

[10] XIAO Yonghui,XIONG Li.Protecting locations with differential privacy under temporal correlations[C]//Proceedings of the 22nd ACM SIGSAC conference on computer and communications security.Denver,Colorado,USA:ACM,2015:1298-1309.

[11] TO H,GHINITA G,SHAHABI C.A framework for protecting worker location privacy in spatial crowd-sourcing[J].Proceedings of the VLDB Endowment,2014,7(10):919-930.

[12] SHAO Jun,LU Rongxing,LIN Xiaodong.FINE:A fine-grained privacy-preserving location-based services framework for mobiles devices[C]//Proceedings of the IEEE conference on computer communications.Toronto,ON,Canada:IEEE,2014:244-252.

[13] SAMANTHULA B K,CEN Lei,JIANG Wei,et al.Privacy-preserving and efficient friend recommendation in online social networks[J].Transactions on Data Privacy,2015,8(2):141-171.

[14] GONG Yanmin,GUO Yuanxiong,FANG Yuguang.A privacy-preserving task recommendation framework for mobile crowdsourcing[C]//Proceedings of the IEEE global communications conference.Austin,TX,USA:IEEE,2014:588-593.

[15] ZHU Hengshu,XIONG Hui,GE Yong,et al.Mobile app recommendations with security and privacy awareness[C]//Proceedings of the 20th SIGKDD international conference on knowledge discovery and data mining.New York,NY,USA:ACM,2014:951-960.

[16] 鞠 娜.移动互联网的大数据处理关键技术[J].信息与电脑,2015(23):38.