李曉會，陳潮陽，白雨靚，張 興

(遼寧工業(yè)大學 電子與信息工程學院，遼寧 錦州 121001)

1 引 言

近年來，隨著信息爆炸、大數(shù)據(jù)技術和移動應用技術的普及，基于位置的個性化推薦成了時代的新寵，推薦系統(tǒng)的作用越來越明顯.基于位置服務(Loaction-Based Service，LBS)已經(jīng)得到了普遍的應用，在給人們帶來極大方便的同時，用戶的個人隱私很大可能會泄露，其基本形式是用戶的身份標志號、當前時刻、當前位置等數(shù)據(jù)被發(fā)送到LBS服務器，服務器將會返回興趣點的位置和移動路徑等信息給用戶.攻擊者會利用這些個人敏感信息攻擊查詢用戶，使得用戶的個人隱私遭受泄露.因此，如何既能保證推薦質量又能提高用戶隱私保護已經(jīng)成為當前研究的熱點之一.

現(xiàn)如今越來越多的學者重視隱私保護的問題，在過去的研究中，提出的大多數(shù)研究方案都是在位置服務中進行混淆，多數(shù)采用差分隱私[1，2]、k-匿名[3]、擾動[4]、泛化[5]等方法，雖然能夠產(chǎn)生一定的保護作用，但是存在很多需要解決的問題.例如Wang等人[6]提出了位置 K-匿名模型，通過K-匿名算法，生成(k-1)個匿名用戶用來混淆查詢用戶，對查詢用戶的當前位置進行保護，但K-匿名本身存在致命的缺點，不能有效評估攻擊者的背景知識，因此設計出一個全面而有效的軌跡隱私保護模型十分困難.但是差分隱私具有背景無關性，所以現(xiàn)今大部分學者利用差分隱私來解決隱私保護的問題，當然差分隱私也不是萬能的，其中最明顯的缺點就是噪聲的添加問題，現(xiàn)在大多數(shù)學者就針對這一問題進行解決，例如，侯堯等人[7]提出了后置映射的方法來降低差分隱私中噪聲的添加問題，在滿足相同的隱私級別的同時，改善其平均服務質量，但是這一方法的劣勢在于，對于不同隱私程度的保護不夠完善，雖然可以改善平均服務質量，但是會出現(xiàn)服務質量不平衡或隱私保護不針對的問題.

在本文中，提出了基于偏好感知的軌跡隱私保護服務推薦模型，該模型是由兩個算法相輔相成的.首先是基于聚類的mix-zone算法，在用戶查詢信息輸入時，對用戶的敏感信息加密，并且通過聚類的方法，保留了對于用戶群體行為的數(shù)據(jù)可用性；其次是基于差分隱私的偏好感知算法，根據(jù)用戶對不同位置的偏好劃分不同的隱私風險級別，然后根據(jù)這些級別添加不同程度的噪聲，既可以保護用戶敏感信息泄露，又可以相應的提高數(shù)據(jù)的可用性.

2 相關工作原理

本節(jié)主要闡述一些基本定義及相關概念，包括mix-zone[8，9]、聚類[10]、差分隱私、偏好感知[11，12]等.

2.1 Mix-zone

Mix-zone簡單的來說就是多個用戶集中改變假名的特定區(qū)域，其基本思想是：制定區(qū)域，將一部分制定的十字路口設定為mix-zone，并對這些區(qū)域進行加密，多個用戶進入該區(qū)域的信息不會被收集，離開時會更新用戶的標識符，從而敵手無法將每個用戶的軌跡片段一一對應.Mix-zone的具體定義如下：

定義1.匿名集在mix-zone服從k-匿名算法，滿足如下條件：

1)匿名集中至少包含k個用戶；

2)匿名集中所有的用戶都進入之后才能有用戶離開；

3)匿名集中所有的用戶在mix-zone中的時間是隨機的；

4)用戶從進入點進入和出口點離開的概率服從均勻分布.

傳統(tǒng)的mix-zone方法忽略了一個問題，就是不同的用戶在不同出入口的進入、離開的概率不是均勻分布的，所以需要確保兩個條件：在一個時間段內假名關聯(lián)到各個用戶的概率相似；不同出口的假名關聯(lián)到各個用戶的概率相似.基于上述分析，用戶可被觀察的所有屬性的相似性比較稱為關聯(lián)攻擊模式，因此對用戶屬性的相似性量化采用sim(As,As′)，其中sim(.)表示相似性.假定被指定的某一個追蹤用戶屬性為As=(a1,a2,…,am)，該用戶離開mix-zone之后表現(xiàn)出的屬性為As′=(a1′,a2′,…,am′)，若存在sim(As,As′)<λ，則這兩種屬性被認為是出自于同一個用戶的，即進出匿名域是同一用戶，使得該用戶可以被攻擊者持續(xù)追蹤.其中，可被識別的屬性數(shù)目為m，可被攻擊者使用的相似屬性最小閾值為λ.

2.2 聚類

(1)

聚類算法把數(shù)據(jù)對象集劃分成多個組或簇，簇內的對象具有很高的相似性，但與其他簇中的對象很不相似.

2.3 差分隱私

差分隱私是統(tǒng)計數(shù)據(jù)庫領域中的隱私概念，具有嚴格的隱私定義且可以抵御任意背景知識的攻擊，差分隱私保護技術通過向原始數(shù)據(jù)集的轉換或其統(tǒng)計結果添加噪聲來達到隱私保護的目的.該方法確保在任何數(shù)據(jù)集中更改任一條記錄的操作都不會影響查詢的輸出結果.此外，該模型可以抵御攻擊者掌握了除某一記錄外的所有信息的背景知識攻擊.本文使用的定義與性質如下所示:

定義2.設隨機算法A，Pr為A所有可能輸出構成的集合的概率，對于任意兩個鄰近的數(shù)據(jù)集D和D′，以及Pr的任意子集S，若算法A滿足以下不等式，則算法A滿足ε-差分隱私條件:

Pr(A(D)∈S)≤eτ×Pr(A(D′)∈S)

(2)

式中，S?Range(A)，數(shù)據(jù)庫D和D′最多有一條記錄不同.差分隱私有兩個重要的性質:

性質1.設有原始數(shù)據(jù)m、算法A，其中算法A滿足ε-差分隱私，m為算法A的輸出結果，那么對于m的任意函數(shù)y(m)，它的輸出結果均滿足ε-差分隱私.

性質2.設有兩個隱私保護算法A1和A2，隱私預算分別為ε1和ε2，其中A1滿足ε1-差分隱私，A2滿足ε2-差分隱私，且數(shù)據(jù)集不相交，那么組合算法滿足(ε1+ε2)-差分隱私.

差分隱私的主要手段是添加噪聲機制，噪聲機制主要分為兩種，分別是拉普拉斯機制[13]和指數(shù)機制，本文采用拉普拉斯機制進行噪聲的添加.推薦結果中使用Laplace機制添加噪聲，使真實輸出值產(chǎn)生概率波動，從而實現(xiàn)ε-差分隱私保護.由于Laplace噪聲服從概率分布，在相鄰數(shù)據(jù)集上分別進行相同的查詢，可能得到相同的結果.對于任意一個函數(shù)f：D→Rd，函數(shù)f的全局敏感性為Δf=maxD,D′|f(D)-f(D′)|，D和D′為相鄰數(shù)據(jù)集.d是函數(shù)輸出的維度.所以概率差異公式如下：

(3)

由以上可以得出結論：隱私參數(shù)ε越小，需要的噪聲越大，隱私保護能力就越強，但數(shù)據(jù)的可用性會大大降低，所以隱私預算ε不是越小越理想，而是需要添加適當?shù)摩?

2.4 偏好感知

偏好感知是用來解決如何有效的從移動軌跡數(shù)據(jù)中提取用戶的運動模式，進而實現(xiàn)一種軌跡匿名.本文需要構建用戶的偏好模型，主要從用戶熟悉度和位置流行度兩個方面進行.

1)熟悉度-用戶

用戶的熟悉度是指用戶中心節(jié)點的數(shù)目，往往通過對權威節(jié)點的綜合數(shù)值來計算的，計算過程如下：

(4)

2)流行度-位置

位置流行度是指權威節(jié)點的數(shù)目，通常采用對中心節(jié)點總和數(shù)值來計算，計算過程如下：

(5)

通過對用戶的熟悉度和位置的流行度進行計算，來構建用戶在位置空間上的偏好模型，對后面的PPBP算法做準備.

3 軌跡隱私保護服務推薦方法

3.1 系統(tǒng)設計思路

查詢用戶將自身真實的位置數(shù)據(jù)和身份數(shù)據(jù)等發(fā)送到推薦系統(tǒng)，以享受個性化的服務推薦，為提高系統(tǒng)的安全性，本文從兩個方面進行研究，對用戶的隱私進行雙層保護.模型的核心思想是：第1層隱私保護：當用戶需要進行推薦查詢時，用戶的真實位置和真實信息就會暴露出來，此時運用基于聚類的mix-zone算法進行隱私保護，mix-zone在路網(wǎng)中生成一個隱私保護的區(qū)域，然后對輸入查詢命令的所有用戶進行聚類，同一簇中的用戶同時進行屬性泛化，提高了相似屬性的混淆性，這既節(jié)省加密時間又增強了隱私保護；第2層保護：由于不同用戶對于不同位置的敏感程度不同，所以需要根據(jù)用戶對不同位置的偏好劃分風險等級，運用基于差分隱私的偏好感知算法，根據(jù)對不同位置的風險等級添加合適的隱私預算，在推薦結果數(shù)據(jù)中加入適當?shù)腖aplace噪聲，這種方法不僅減少了對噪聲的浪費，又提高了用戶敏感信息的隱私保護，而且還大大提高了推薦結果的質量.

3.2 設計框架

本文個性化服務推薦的隱私保護主要由位置空間匿名、偏好模型建立、隱私風險評定和位置軌跡匿名組成.

1)位置空間匿名：通過基于聚類的mix-zone算法對查詢用戶的初始位置進行匿名.

2)偏好模型建立：通過HITS算法的中心節(jié)點和權威節(jié)點找出用戶的偏好以及背景信息.

3)隱私風險評定：根據(jù)用戶對位置的不同偏好，劃分出不同的隱私風險等級，采取不同程度的Laplace保護機制.

4)位置軌跡匿名：將已經(jīng)加躁的位置組合到一起形成新的匿名軌跡.該服務推薦隱私保護框架如圖1所示.

圖1 服務推薦隱私保護框架

首先，查詢用戶在進行服務請求時，用戶當前的位置會一起被發(fā)送到系統(tǒng)中，系統(tǒng)會利用基于聚類的mix-zone算法對用戶當前真實位置進行位置空間匿名，以獲得假的位置標識符(SID).然后，應用服務器根據(jù)用戶的興趣對用戶進行個性化服務推薦，對推薦的原始軌跡K進行語義描述和行為模式提取，然后考慮用戶對語義類型的熟悉度以及位置流行度的分析計算，生成偏好模型，根據(jù)用戶在偏好模型中地理位置的偏好，生成隱私風險評級標準，并加入適當?shù)牟罘蛛[私預算ε，生成匿名軌跡K*，最后將結果返回服務器，以實現(xiàn)位置社交網(wǎng)絡的個性化軌跡隱私保護.位置空間匿名和差分隱私預算等級劃分如表1所示.

表1 位置空間匿名-差分隱私預算等級劃分表

3.3 算法的描述

算法1.

輸入：初始位置數(shù)據(jù)集SID1、SID2、…、SIDn，更新增量n

輸出：位置空間匿名標識符Alias(SID1)、Alias(SID2)、…、Alias(SIDn)

1.真實位置標識符SIDm→Alias(SIDm)

2.構建k個簇

3. 從n個位置數(shù)據(jù)集中隨機選擇k個對象作為初始的代表對象

4. 將剩下的所有對象分配到最近的代表所代表的簇

5. 隨機選擇一個非代表對象Orandom

6. 計算用Orandom代替代表對象Oj的總代價S

7. if S<0

8. Oj代替Orandom，生成一組新的k個代表對象

9.重復上述步驟，直到?jīng)]有發(fā)生更改

10.每個簇分別做下列步驟

11. RSU 集合SMZ←Φ

12. 初始化節(jié)點數(shù)目SMZ，N←0

13. 當N≤K時

14. SMZ←SMZ∪AZT；

15. N←N+n

16. 將SMZ合并到List(SMZ)

18. 選擇聚類中最大的mix-zone

19.結束

算法2.

輸入：原始軌跡K，用戶熟悉度的閾值λ，位置流行度的閾值τ，匿名的位置空間Z

輸出：匿名軌跡K*

1.定義：原始軌跡序列長度為length；

2.初始化：K*=φ，i=1，j=1；

3.when i

4. 判斷位置Li的類型C；

6.While j

17.End if

18. j=j+1；

19. End while

20. i=i+1；

21. End when

22. 返回加入不同隱私預算參數(shù)ε噪音；

23.輸出匿名軌跡K*；

24.結束

3.4 算法隱私保護效果分析

1)基于聚類的mix-zone

同構mix-zone算法可以有效地對用戶的真實位置和真實信息進行隱藏，但是mix-zone存在缺點，mix-zone在路網(wǎng)中生成一個隱私保護的區(qū)域，當用戶過多時，可被攻擊者利用屬性追蹤的方法進行攔截，泄露用戶隱私；所以在minx-zone算法的基礎上結合聚類的方法，對輸入查詢命令的所有用戶進行聚類，同一簇中的用戶同時進行屬性泛化，提高了相似屬性的混淆性，同時秘密計算的屬性處理不會泄露任何信息給參與者，這既節(jié)省加密時間又增強了隱私保護.

2)基于差分隱私的偏好感知

4 實驗數(shù)據(jù)分析

4.1 參數(shù)設置

本文算法由Python語言和My Eclipse集成開發(fā)軟件開發(fā)實現(xiàn).實驗硬件環(huán)境為 Inter(R)酷睿I5 9400CPU 2.9GHz處理器，16G內存；Linux作為操作系統(tǒng)；Hadoop為實驗平臺；spark做系統(tǒng)框架.在實驗數(shù)據(jù)方面，采用從csdn官網(wǎng)(1)https://blog.csdn.net/liangyihuai/article/details下載的GPS Trajectories with transportationmode labels數(shù)據(jù)集，該數(shù)據(jù)集包含 ID、Name、Age、Education、Date、Start Time、End time、Transportationmodes、SID、Track 等屬性，其中屬性中的敏感屬性是SID和ID，全部屬性的數(shù)據(jù)類型為數(shù)值型數(shù)據(jù).

4.2 實驗數(shù)據(jù)分析

4.2.1 基于聚類的mix-zone算法分析

本節(jié)對基于聚類的mix-zone算法與現(xiàn)有的一些相似算法進行了比較，并從隱私保護能力和算法執(zhí)行效率這兩個方面進行分析比較.參與比較的算法有AG mix-zone算法[14]、通過移動耽擱泛化查詢間隔時間的等待忍耐 mix-zone算法[15]、利用mix-zone 變形降低關聯(lián)程度的偏移 mix-zone算法[16].

1)隱私保護能力分析

如圖2所示，在用戶數(shù)目確定的條件下，除基于聚類的mix-zone算法外，隨屬性數(shù)目的增長其它對比算法信息熵都有所減少.這是因為基于聚類的mix-zone算法針對匿名域中的查詢用戶，通過定量的相似計算對多屬性進行量化來完成屬性的泛化，該方法處理的屬性數(shù)量大大超過了其他算法.其余3種算法中，AG mix-zone算法變化最小，因為它與本文算法計算方法相近，但其屬性量化范圍較小，從信息熵的變化來看，基于聚類的mix-zone算法優(yōu)勢更大.

圖2 屬性變化導致的信息熵變化曲線

2)算法執(zhí)行效率分析

如圖3所示，算法在mix-zone下執(zhí)行的成功率隨屬性變化的差異.基于聚類的mix-zone算法的執(zhí)行成功率受屬性的改變影響最小，這是因為每個算法都需要對用戶的所有屬性進行泛化，等待忍耐 mix-zone算法和偏移 mix-zone算法通過對所有屬性的直接泛化進行隱私保護的，當用戶屬性增加時，就會導致具有相似屬性的用戶消失，因此需要重新尋找具有相似屬性的用戶，導致算法執(zhí)行成功率大大降低；AG mix-zone算法采用的是量化相似用戶的相似屬性來進行隱私保護的，它只處理相似屬性，當屬性增加時，會導致用戶的相似屬性重新量化計算，降低了算法的執(zhí)行成功率；本文算法則采用對相似用戶的所有屬性進行相似性量化，進而進行隱私保護，當屬性數(shù)目增加時，只需量化計算新增屬性即可，因此算法的執(zhí)行成功率受屬性的改變影響最小.

圖3 算法執(zhí)行成功率-屬性變化

如圖4所示，在路網(wǎng)中各算法的執(zhí)行成功率都會隨著用戶數(shù)目的增長而逐漸降低，其中基于聚類的mix-zone算法的執(zhí)行成功率受用戶數(shù)量的影響最小，這是由于所有的算法都需要路網(wǎng)中有充足的用戶數(shù)目來支撐用戶屬性的泛化，所以用戶數(shù)目達不到要求時，算法無法進行；而聚類的mix-zone算法將所有用戶通過聚類分成不同屬性的簇，每個簇中采用多用戶間相似性的安全計算進行屬性的泛化，只需找到足夠的用戶數(shù)量即可，而其它3個算法在找到充足用戶數(shù)量后，還需要根據(jù)用戶的屬性情況來進行用戶間的屬性泛化，對算法執(zhí)行成功率影響較大.

圖4 算法執(zhí)行成功率-用戶數(shù)量

從上面的實驗驗證成果可以發(fā)現(xiàn)，基于聚類的mix-zone算法具有更好地隱私保護能力和算法執(zhí)行效率.

4.2.2 基于差分隱私的偏好感知算法(PPBP)分析

傳統(tǒng)的軌跡匿名方法對軌跡中的所有位置采用統(tǒng)一的隱私保護方案，即欠缺了用戶對位置偏好的考慮，又對數(shù)據(jù)的有效性產(chǎn)生了影響.表2顯示了軌跡隱私保護中ε的分類情況，第三方可信服務器針對偏好模型中不同的隱私風險評級結果，結合差分隱私算法，對不同的軌跡位置添加合適的噪聲.

表2 ε的添加分布情況

1)數(shù)據(jù)效用分析對比

通過基于差分隱私的偏好感知算法(PPBP)與現(xiàn)有的(k，?)匿名方法[17]和偏好感知隱私保護算法(PTPP)[18]在數(shù)據(jù)效用和執(zhí)行效率兩個方面的對比，來觀察PPBP算法的優(yōu)勢.首先是數(shù)據(jù)效應的對比，本文對數(shù)據(jù)效應的衡量通過軌跡隱私保護過程中的信息丟失量來表現(xiàn).信息丟失量的計算公式如下.

(6)

其中，area(zone(Ζi,tj))表示在tj時刻位置匿名空間Ζi的區(qū)域大小，刪除的位置用Lm表示，軌跡中總的位置個數(shù)為|T|.

如圖5所示，PPBP算法的信息丟失量明顯低于PTPP算法和(k，?)匿名算法，這是由于(k，?)匿名算法沒有設置用戶的偏好模型，以及忽略了隱私風險評定對軌跡隱私保護的影響，并且(k，?)匿名算法的位置匿名規(guī)則都是相同的；而PTPP算法也考慮用戶對位置的偏好以及隱私風險評級，但匿名規(guī)則的不統(tǒng)一，導致不能很好的對應風險評級標準.PPBP算法在進行軌跡隱私保護時，通過建立偏好模型以及差分隱私中背景知識自適應性，結合隱私風險評定結果，采用不同的位置匿名規(guī)則，對軌跡位置添加適當?shù)脑肼暎瑯O大的減少了信息的丟失量，可以有效的提高數(shù)據(jù)質量.

圖5 數(shù)據(jù)效應對比圖

2)執(zhí)行效率分析對比

本節(jié)對3種方法的執(zhí)行效率通過算法的運行時間來衡量.如圖6所示，當T<4時，(k，?)匿名算法的運行速度較快，主要是由于PPBP算法與PTPP算法都需要對軌跡中的位置匿名空間進行語義描述，進而構建偏好模型，在構建偏好模型的過程中浪費了大量的運行時間；而當T>4時，PPBP算法與PTPP算法的運行速度增快，主要原因是因為(k，?)匿名算法需要對匿名區(qū)域進行不斷地擴大，而PPBP算法與PTPP算法在偏好模型建立完成以后，匿名區(qū)域運行流暢，使得運行速度增快；當T>4時，PPBP算法還比PTPP算法執(zhí)行速度快，是因為PPBP算法比PTPP算法對位置匿名規(guī)則的添加速度快，極大的減少了算法的執(zhí)行時間.

圖6 執(zhí)行效率對比圖

5 結 語

本文提出的軌跡隱私保護服務推薦算法的核心思想是在傳統(tǒng)的服務推薦系統(tǒng)中加入基于聚類的mix-zone算法和基于差分隱私的偏好感知算法.通過對聚類、mix-zone、差分隱私以及偏好感知的運用與結合，設計出了一種對位置軌跡隱私保護的新算法，對用戶敏感信息泄露、推薦服務質量低以及缺乏自適應等問題進行了解決.該模型通過兩方面對隱私進行保護.首先，提出了一種隱私保護方法，切斷了用戶屬性之間的關聯(lián)性，混合區(qū)域內的用戶之間不能獲取彼此的真實信息.該方法通過聚類算法生成不同屬性的簇，各個簇中進行相似屬性的秘密安全計算，使得混合區(qū)域內離開的各個用戶的屬性無相關性.通過與現(xiàn)有相關mix-zone的算法進行比較，證明本文所提基于聚類的mix-zone算法的有效性和算法執(zhí)行效率更有優(yōu)勢.其次提出了一種基于差分隱私的偏好感知算法(PPBP)，針對位置社交網(wǎng)絡下敏感位置攻擊，通過語義描述和行為模式提取的方法進行偏好建模，根據(jù)偏好模型進行隱私風險評定，按照位置匿名規(guī)則添加對應的拉普拉斯噪聲機制，將匿名的各個位置按原始軌跡中對應的位置順序連接起來，生成新的匿名軌跡，返還給查詢用戶.本文算法不僅提高了隱私保護的安全性，又極大的減少了算法運行的時間，而且還提高了服務推薦的數(shù)據(jù)可用性.未來將繼續(xù)研究隱私保護在位置軌跡中的應用.