一種軌跡隱私保護(hù)服務(wù)推薦模型研究

李曉會(huì)，陳潮陽(yáng)，白雨靚，張 興

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

1 引 言

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

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

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

2 相關(guān)工作原理

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

2.1 Mix-zone

Mix-zone簡(jiǎn)單的來(lái)說(shuō)就是多個(gè)用戶集中改變假名的特定區(qū)域，其基本思想是：制定區(qū)域，將一部分制定的十字路口設(shè)定為mix-zone，并對(duì)這些區(qū)域進(jìn)行加密，多個(gè)用戶進(jìn)入該區(qū)域的信息不會(huì)被收集，離開(kāi)時(shí)會(huì)更新用戶的標(biāo)識(shí)符，從而敵手無(wú)法將每個(gè)用戶的軌跡片段一一對(duì)應(yīng).Mix-zone的具體定義如下：

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

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

2)匿名集中所有的用戶都進(jìn)入之后才能有用戶離開(kāi)；

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

4)用戶從進(jìn)入點(diǎn)進(jìn)入和出口點(diǎn)離開(kāi)的概率服從均勻分布.

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

2.2 聚類

(1)

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

2.3 差分隱私

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

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

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

(2)

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

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

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

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

(3)

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

2.4 偏好感知

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

1)熟悉度-用戶

用戶的熟悉度是指用戶中心節(jié)點(diǎn)的數(shù)目，往往通過(guò)對(duì)權(quán)威節(jié)點(diǎn)的綜合數(shù)值來(lái)計(jì)算的，計(jì)算過(guò)程如下：

(4)

2)流行度-位置

位置流行度是指權(quán)威節(jié)點(diǎn)的數(shù)目，通常采用對(duì)中心節(jié)點(diǎn)總和數(shù)值來(lái)計(jì)算，計(jì)算過(guò)程如下：

(5)

通過(guò)對(duì)用戶的熟悉度和位置的流行度進(jìn)行計(jì)算，來(lái)構(gòu)建用戶在位置空間上的偏好模型，對(duì)后面的PPBP算法做準(zhǔn)備.

3 軌跡隱私保護(hù)服務(wù)推薦方法

3.1 系統(tǒng)設(shè)計(jì)思路

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

3.2 設(shè)計(jì)框架

本文個(gè)性化服務(wù)推薦的隱私保護(hù)主要由位置空間匿名、偏好模型建立、隱私風(fēng)險(xiǎn)評(píng)定和位置軌跡匿名組成.

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

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

3)隱私風(fēng)險(xiǎn)評(píng)定：根據(jù)用戶對(duì)位置的不同偏好，劃分出不同的隱私風(fēng)險(xiǎn)等級(jí)，采取不同程度的Laplace保護(hù)機(jī)制.

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

圖1 服務(wù)推薦隱私保護(hù)框架

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

表1 位置空間匿名-差分隱私預(yù)算等級(jí)劃分表

3.3 算法的描述

算法1.

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

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

1.真實(shí)位置標(biāo)識(shí)符SIDm→Alias(SIDm)

2.構(gòu)建k個(gè)簇

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

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

5. 隨機(jī)選擇一個(gè)非代表對(duì)象Orandom

6. 計(jì)算用Orandom代替代表對(duì)象Oj的總代價(jià)S

7. if S<0

8. Oj代替Orandom，生成一組新的k個(gè)代表對(duì)象

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

10.每個(gè)簇分別做下列步驟

11. RSU 集合SMZ←Φ

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

13. 當(dāng)N≤K時(shí)

14. SMZ←SMZ∪AZT；

15. N←N+n

16. 將SMZ合并到List(SMZ)

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

19.結(jié)束

算法2.

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

輸出：匿名軌跡K*

1.定義：原始軌跡序列長(zhǎng)度為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. 返回加入不同隱私預(yù)算參數(shù)ε噪音；

23.輸出匿名軌跡K*；

24.結(jié)束

3.4 算法隱私保護(hù)效果分析

1)基于聚類的mix-zone

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

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

4 實(shí)驗(yàn)數(shù)據(jù)分析

4.1 參數(shù)設(shè)置

本文算法由Python語(yǔ)言和My Eclipse集成開(kāi)發(fā)軟件開(kāi)發(fā)實(shí)現(xiàn).實(shí)驗(yàn)硬件環(huán)境為 Inter(R)酷睿I5 9400CPU 2.9GHz處理器，16G內(nèi)存；Linux作為操作系統(tǒng)；Hadoop為實(shí)驗(yàn)平臺(tái)；spark做系統(tǒng)框架.在實(shí)驗(yàn)數(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í)驗(yàn)數(shù)據(jù)分析

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

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

1)隱私保護(hù)能力分析

如圖2所示，在用戶數(shù)目確定的條件下，除基于聚類的mix-zone算法外，隨屬性數(shù)目的增長(zhǎng)其它對(duì)比算法信息熵都有所減少.這是因?yàn)榛诰垲惖膍ix-zone算法針對(duì)匿名域中的查詢用戶，通過(guò)定量的相似計(jì)算對(duì)多屬性進(jìn)行量化來(lái)完成屬性的泛化，該方法處理的屬性數(shù)量大大超過(guò)了其他算法.其余3種算法中，AG mix-zone算法變化最小，因?yàn)樗c本文算法計(jì)算方法相近，但其屬性量化范圍較小，從信息熵的變化來(lái)看，基于聚類的mix-zone算法優(yōu)勢(shì)更大.

圖2 屬性變化導(dǎo)致的信息熵變化曲線

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

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

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

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

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

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

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

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

表2 ε的添加分布情況

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

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

(6)

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

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

圖5 數(shù)據(jù)效應(yīng)對(duì)比圖

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

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

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

5 結(jié) 語(yǔ)

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