基于位置推薦中的隱私保護方法研究

張海濤，汪佩佩

(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.