張青云 張 興 李萬(wàn)杰 李 帥 李曉會(huì)

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

0 引 言

目前，基于位置的社交網(wǎng)絡(luò)(Location-Based Social Networks,LBSN)應(yīng)用非常廣泛，典型的LBSN有美團(tuán)、街旁、大眾點(diǎn)評(píng)網(wǎng)等。這些社交網(wǎng)站為用戶(hù)提供興趣點(diǎn)(Point of Interests,POI)的簽到、評(píng)論以及分享功能，這些功能積累的大量數(shù)據(jù)可作為興趣點(diǎn)推薦的基礎(chǔ)數(shù)據(jù)。興趣點(diǎn)推薦服務(wù)是基于用戶(hù)偏好和地理位置的一種社交網(wǎng)絡(luò)服務(wù)類(lèi)型，主要是向用戶(hù)推薦滿(mǎn)足自身偏好并且從未去過(guò)的位置。在互聯(lián)網(wǎng)的快速發(fā)展中，興趣點(diǎn)推薦服務(wù)可以讓用戶(hù)更加方便地在網(wǎng)絡(luò)上與朋友分享信息、推薦信息，但與此同時(shí)也存在弊端。用戶(hù)需要暴露隱私信息來(lái)接受推薦服務(wù)，會(huì)帶來(lái)隱私泄露的風(fēng)險(xiǎn)，例如：觀察用戶(hù)每天的出行路線，可以大致推測(cè)出用戶(hù)的家庭住址以及公司地址；將用戶(hù)的歷史訪問(wèn)興趣點(diǎn)進(jìn)行分類(lèi)統(tǒng)計(jì)，能夠大致得出用戶(hù)的個(gè)人喜好以及經(jīng)濟(jì)情況。所以用戶(hù)可能會(huì)因?yàn)殡[私問(wèn)題不愿意接受這樣的推薦服務(wù)，因此亟需設(shè)計(jì)出一種算法來(lái)解決這個(gè)問(wèn)題。傳統(tǒng)的興趣點(diǎn)推薦算法首先收集用戶(hù)的行為記錄，然后使用協(xié)同過(guò)濾推薦算法發(fā)現(xiàn)用戶(hù)的偏好并為用戶(hù)尋找偏好相似的其他用戶(hù)，最后結(jié)合偏好相似用戶(hù)的歷史行為記錄、好友行為記錄和用戶(hù)地理位置等因素，將新的興趣點(diǎn)推薦給有需求的用戶(hù)。

如今，興趣點(diǎn)推薦系統(tǒng)引起了大量學(xué)者的關(guān)注，他們對(duì)其進(jìn)行了深入地研究并提出了很多改進(jìn)算法。Park等[1]根據(jù)用戶(hù)對(duì)各類(lèi)餐廳的喜好程度，運(yùn)用貝葉斯分析方法構(gòu)建數(shù)學(xué)模型，將用戶(hù)可能感興趣的餐廳反饋給用戶(hù)。Nunes等[2]提出了一種基于位置的推薦方法，主要通過(guò)位置感知技術(shù)和構(gòu)建高斯模型進(jìn)行推薦。Zhang等[3-4]提出了興趣點(diǎn)推薦系統(tǒng)需要考慮的幾點(diǎn)因素：地理位置、好友信息、用戶(hù)偏好以及時(shí)空關(guān)系，詳細(xì)地列舉了影響興趣點(diǎn)推薦的幾個(gè)方面。曹玖新等[5]將社交網(wǎng)絡(luò)圖和簽到軌跡圖結(jié)合起來(lái)，計(jì)算每條路徑的關(guān)聯(lián)度，為用戶(hù)推薦興趣點(diǎn)。Jeh等[6]結(jié)合Page Rank算法，提出了兩種改進(jìn)的位置推薦算法：基于好友關(guān)系的標(biāo)簽涂色算法和基于位置-好友關(guān)系的標(biāo)簽涂色算法。Yang等[7]結(jié)合時(shí)間和空間因素提出了一種改進(jìn)的興趣點(diǎn)推薦算法。

上述文獻(xiàn)提出的算法雖然能從不同角度滿(mǎn)足興趣點(diǎn)推薦系統(tǒng)的要求，但是并沒(méi)有考慮到用戶(hù)的隱私泄漏問(wèn)題。為了在保護(hù)用戶(hù)隱私信息的同時(shí)不影響推薦效果，本文對(duì)傳統(tǒng)興趣點(diǎn)推薦算法進(jìn)行改進(jìn)，在其基礎(chǔ)上添加差分隱私保護(hù)機(jī)制，以此來(lái)防止攻擊者的惡意攻擊。

1 基本工作原理

1.1 傳統(tǒng)興趣點(diǎn)推薦算法工作原理

傳統(tǒng)的興趣點(diǎn)推薦算法主要使用協(xié)同過(guò)濾推薦算法來(lái)實(shí)現(xiàn)推薦功能。該算法可分為兩大類(lèi)，分別是基于用戶(hù)的協(xié)同過(guò)濾推薦算法和基于項(xiàng)目的協(xié)同過(guò)濾推薦算法。下面簡(jiǎn)單地介紹這兩類(lèi)推薦算法的原理：

基于用戶(hù)的協(xié)同過(guò)濾推薦算法：首先根據(jù)收集到的用戶(hù)信息來(lái)計(jì)算用戶(hù)之間的相似度，找到與當(dāng)前目標(biāo)用戶(hù)相似度高的所有用戶(hù)集合，然后再收集這個(gè)集合中的用戶(hù)對(duì)其他興趣點(diǎn)的評(píng)分，通過(guò)對(duì)不同興趣點(diǎn)的評(píng)分等級(jí)來(lái)推測(cè)出目標(biāo)用戶(hù)對(duì)該興趣點(diǎn)的喜好程度，從而實(shí)現(xiàn)推薦功能。

基于興趣點(diǎn)的協(xié)同過(guò)濾推薦算法：首先根據(jù)目標(biāo)用戶(hù)對(duì)興趣點(diǎn)的喜好程度找到與之相似的興趣點(diǎn)集合，然后根據(jù)用戶(hù)的偏好和興趣點(diǎn)集合中的項(xiàng)目進(jìn)行相似度排序，將相似度高的興趣點(diǎn)推薦給目標(biāo)用戶(hù)。

1.2 差分隱私相關(guān)概念

自2006年差分隱私發(fā)表以來(lái)，在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域產(chǎn)生了巨大的影響。Dwork[8]將差分隱私定義為一種類(lèi)似數(shù)據(jù)加密的方法。在這種定義下，對(duì)于數(shù)據(jù)集的計(jì)算結(jié)果而言，單個(gè)記錄是否在數(shù)據(jù)集中對(duì)結(jié)果造成的影響可以忽略不計(jì)。因此，攻擊者不能計(jì)算出某條記錄是否在該數(shù)據(jù)集中。本文使用的定義、定理與性質(zhì)[8]如下所示：

定義1存在一個(gè)含有n條記錄的數(shù)據(jù)集D，記為D=(x1,x2,…,xn)，xi是一條記錄，取值均在Rd范圍內(nèi)，向量xi的d個(gè)元素分別對(duì)應(yīng)每個(gè)記錄的d個(gè)屬性。定義隱私保護(hù)算法A的取值范圍為Range(A)，若算法滿(mǎn)足以下不等式，則算法A滿(mǎn)足ε-差分隱私條件：

P(A(D)∈S)≤eεP(A(D′)∈S)

(1)

式中：S?Range(A)，數(shù)據(jù)庫(kù)D和D′至多相差一條記錄，數(shù)據(jù)庫(kù)中的每條記錄都對(duì)應(yīng)一個(gè)個(gè)體。差分隱私有兩個(gè)重要的性質(zhì)：

性質(zhì)1若原始數(shù)據(jù)v是算法A的輸出結(jié)果，算法A滿(mǎn)足ε-差分隱私，那么關(guān)于v的任意函數(shù)g(v)的輸出結(jié)果均滿(mǎn)足ε-差分隱私。

性質(zhì)2對(duì)原始數(shù)據(jù)v使用兩個(gè)隱私保護(hù)算法A1和A2，其中，A1滿(mǎn)足ε1-差分隱私，A2滿(mǎn)足ε2-差分隱私，那么v的隱私保護(hù)參數(shù)至多為ε1+ε2。

定理1令D和D′為兩個(gè)至多相差一條記錄的數(shù)據(jù)庫(kù)，F(xiàn)表示向數(shù)據(jù)庫(kù)請(qǐng)求的查詢(xún)函數(shù)，那么查詢(xún)算法F的敏感度ΔF表示為:

(2)

通俗而言，可以把算法敏感度ΔF理解成隨機(jī)增加或者刪除一條記錄對(duì)整個(gè)數(shù)據(jù)集查詢(xún)結(jié)果的最壞影響。

定理2如果變量x的概率密度分布函數(shù)Pr[x|μ,λ]滿(mǎn)足:

(3)

則稱(chēng)x服從拉普拉斯分布。其中參數(shù)μ和λ分別表示變量x的期望值和尺度參數(shù)。參數(shù)λ由算法敏感度ΔF和隱私保護(hù)參數(shù)ε共同決定，表示為λ=ΔF/ε。

對(duì)于數(shù)據(jù)集D而言，如果查詢(xún)數(shù)據(jù)為數(shù)值型，則使用拉普拉斯機(jī)制對(duì)查詢(xún)結(jié)果進(jìn)行加噪處理；反之，如果查詢(xún)數(shù)據(jù)為非數(shù)值型，則使用指數(shù)機(jī)制來(lái)處理查詢(xún)結(jié)果。

文獻(xiàn)[9]提出了指數(shù)機(jī)制的概念。指數(shù)機(jī)制常被用于分類(lèi)算法中多個(gè)分類(lèi)值的選擇問(wèn)題。打分函數(shù)mark(D,r)(r∈D)的設(shè)計(jì)是指數(shù)機(jī)制的核心部分，其中r表示隨機(jī)在值域D中選取的輸出結(jié)果。

定理3如果F:D→Rd是一個(gè)k維的查詢(xún)函數(shù)，ΔF是該查詢(xún)函數(shù)的敏感度，那么加入拉普拉斯噪聲的查詢(xún)函數(shù)表示為F(D)+Lapk(ΔF/ε)，滿(mǎn)足ε-差分隱私。其中Lapk(ΔF/ε)表示加入的拉普拉斯噪聲，由此得出加入的噪聲大小與查詢(xún)函數(shù)的敏感度成正比，與隱私參數(shù)ε的大小成反比。隱私參數(shù)ε越小，需要加入的噪聲就越大，隱私保護(hù)程度就越高，但同時(shí)會(huì)降低數(shù)據(jù)的可用性，因此并不是隱私參數(shù)ε越小越理想。

2 地理位置隱私保護(hù)算法設(shè)計(jì)

2.1 設(shè)計(jì)思路

在推薦服務(wù)中，興趣點(diǎn)的推薦服務(wù)是一個(gè)重要的研究方向。在設(shè)計(jì)推薦算法時(shí)，不僅要有準(zhǔn)確的推薦結(jié)果，還要同時(shí)考慮到用戶(hù)的隱私泄露問(wèn)題。文中提出的基于差分隱私保護(hù)的興趣點(diǎn)推薦算法就是在傳統(tǒng)的興趣點(diǎn)推薦算法中加入地理位置隱私保護(hù)算法，以此達(dá)到預(yù)期目的。地理位置隱私保護(hù)算法首先根據(jù)數(shù)據(jù)集中各項(xiàng)記錄的相互關(guān)系建立位置搜索樹(shù)，然后遍歷位置搜索樹(shù)并運(yùn)用指數(shù)機(jī)制挑選出經(jīng)常訪問(wèn)的k項(xiàng)紀(jì)錄，最后對(duì)這k項(xiàng)記錄添加拉普拉斯噪聲并發(fā)布加噪后的位置搜索樹(shù)。地理位置隱私保護(hù)算法設(shè)計(jì)框圖如圖1所示。

圖1 地理位置隱私保護(hù)算法設(shè)計(jì)框圖

現(xiàn)有的位置隱私保護(hù)方法大多都是通過(guò)匿名化、位置信息隨機(jī)化和位置信息模糊化等[10]方法達(dá)到隱私保護(hù)的效果。當(dāng)用戶(hù)向服務(wù)器位置服務(wù)組件發(fā)送一個(gè)當(dāng)前位置信息來(lái)請(qǐng)求服務(wù)時(shí)，盡管發(fā)送的實(shí)時(shí)地理位置是經(jīng)過(guò)處理的，但是對(duì)其簽到所在的興趣點(diǎn)信息卻沒(méi)有進(jìn)行保護(hù)。攻擊者以及用于數(shù)據(jù)分析和數(shù)據(jù)挖掘的信息收集器仍然可以通過(guò)獲取該興趣點(diǎn)的相關(guān)信息獲得用戶(hù)的實(shí)時(shí)地理位置，所以對(duì)于當(dāng)前位置隱私保護(hù)的程度是遠(yuǎn)遠(yuǎn)不夠的。因此，本文在原始興趣點(diǎn)推薦的基礎(chǔ)上加入了一種嚴(yán)謹(jǐn)?shù)幕诓罘蛛[私保護(hù)機(jī)制的地理位置隱私保護(hù)算法。

在數(shù)據(jù)集D的頻繁模式挖掘中，應(yīng)該在挖掘top-k頻繁模式之前采用指數(shù)機(jī)制挑選出數(shù)據(jù)集D中所有訪問(wèn)頻率大于min-count的k個(gè)頻繁模式，然后采用拉普拉斯噪音機(jī)制擾動(dòng)挖掘結(jié)果，向挖掘結(jié)果中添加適當(dāng)噪聲，以此保護(hù)top-k模式的訪問(wèn)頻率不被泄露。本文就top-k頻繁模式挖掘問(wèn)題，引入了位置搜索樹(shù)(LQ-Tree)結(jié)構(gòu)，文中定義關(guān)于位置數(shù)據(jù)庫(kù)D的LQ-Tree為L(zhǎng)QTD。

基于差分隱私保護(hù)機(jī)制的地理位置隱私保護(hù)算法(D-LPP)首先通過(guò)建立完整的位置搜索樹(shù)LQTD來(lái)表示數(shù)據(jù)集中的位置數(shù)據(jù)，然后在LQTD上選取所有訪問(wèn)頻率大于min-count的k個(gè)頻繁模式記錄，對(duì)選取的數(shù)據(jù)進(jìn)行加噪處理，最后返回并發(fā)布加噪后的位置搜索樹(shù)NLQTD。如算法1所示。

算法1D-LPP算法

《國(guó)家中長(zhǎng)期教育改革和發(fā)展規(guī)劃綱要(2010—2020年)》明確提出要?jiǎng)?chuàng)新人事管理方式，引導(dǎo)教師潛心教學(xué)科研，改善教師工作和生活條件，關(guān)心教師身心健康。因此教育行政管理部門(mén)和學(xué)校應(yīng)充分發(fā)揮廣大教師在參與學(xué)校校務(wù)監(jiān)督、民主管理中的作用，滿(mǎn)足廣大教師合法表達(dá)利益、對(duì)學(xué)校事務(wù)知情監(jiān)督的訴求，努力構(gòu)建和諧的校園。

輸入：位置數(shù)據(jù)集D、k、min-count、差分隱私參數(shù)ε

輸出：加噪后的位置搜索樹(shù)NLQTD

1) 將數(shù)據(jù)集D中的所有元素構(gòu)建成一個(gè)完整的位置搜索樹(shù)LQTD。

2) 遍歷LQTD，得到所以滿(mǎn)足訪問(wèn)頻率大于min-count的頻繁模式記錄，將該集合記為A。

3) 運(yùn)用指數(shù)機(jī)制挑選出k個(gè)滿(mǎn)足條件的頻繁模式記錄，將這些記錄表示為bi，由bi構(gòu)成的集合稱(chēng)為集合B。

4) 對(duì)集合B中的k個(gè)頻繁模式記錄bi的訪問(wèn)頻率添加拉普拉斯噪聲，將該集合記為E。

5) 將集合E與LQTD結(jié)合，輸出添加噪聲后的位置搜索樹(shù)NLQTD。

2.2 建立位置搜索樹(shù)

通過(guò)用戶(hù)L一個(gè)月內(nèi)的歷史行為記錄，篩選出用戶(hù)經(jīng)常訪問(wèn)的k個(gè)興趣點(diǎn)，構(gòu)建用戶(hù)的位置數(shù)據(jù)庫(kù)D，并根據(jù)數(shù)據(jù)庫(kù)D構(gòu)建一個(gè)位置搜索樹(shù)。圖2表示的是用戶(hù)L一個(gè)月內(nèi)經(jīng)常訪問(wèn)的5個(gè)興趣點(diǎn)。

圖2 位置數(shù)據(jù)

對(duì)地圖上的每個(gè)位置進(jìn)行編號(hào)，根據(jù)圖2的位置數(shù)據(jù)構(gòu)建位置對(duì)應(yīng)關(guān)系表，如表1所示。

表1 位置對(duì)應(yīng)關(guān)系

表2 位置數(shù)據(jù)庫(kù)

根據(jù)表2的位置數(shù)據(jù)庫(kù)，建立如圖3所示的LQTD，其中包含了位置數(shù)據(jù)庫(kù)D中的所有頻繁模式。

圖3 位置搜索樹(shù)

2.3 基于指數(shù)機(jī)制挑選頻繁模式

得到算法1中的集合A后，使用指數(shù)機(jī)制挑選出經(jīng)常訪問(wèn)的k項(xiàng)記錄。指數(shù)機(jī)制不僅能夠篩選出包含用戶(hù)隱私信息大于min-count的位置，而且在每次篩選的時(shí)候能夠合理地控制隱私泄露情況。

通過(guò)指數(shù)機(jī)制在A中選取k個(gè)滿(mǎn)足下式的頻繁模式ai，構(gòu)成集合B：

(4)

式中：Pr(ai)表示每個(gè)興趣點(diǎn)被選中的概率；ai·weight表示ai頻繁模式的權(quán)重。如算法2所示。

算法2Select-Patterns(A,ε1)算法

輸入：集合A，隱私參數(shù)ε1。

輸出：挑選出的k個(gè)頻繁模式構(gòu)成的集合B。

1)n←|A|

/*n表示集合A中的元素個(gè)數(shù) */

2) fori=1 toNdo

3)ai·mark←mark(A,ai)

/* 模式的打分函數(shù) */

/* 打分函數(shù)的全局敏感度 */

/* 計(jì)算每個(gè)模式ai的權(quán)重 */

6) end for

7)L←[a1·weight…an·weight]

/* 將權(quán)重存入鏈表L中 */

8) fori=1 tokdo

/* 頻繁模式ai被選中的概率 */

10) Randomly selectai∈L；

/* 從鏈表L中隨機(jī)選擇模式ai*/

11) InsetaiintoB；

/* 把模式ai插入到集合B中 */

12) end

其中，打分函數(shù)設(shè)置為:

mark(A,ai)=Pr(ai)

(5)

式中：Pr(ai)表示ai模式的訪問(wèn)頻率。

2.4 添加拉普拉斯噪聲

算法2只是選擇出k個(gè)頻繁模式，但并沒(méi)有對(duì)這k個(gè)模式的真實(shí)訪問(wèn)頻率起到保護(hù)的效果，如果直接輸出會(huì)泄露用戶(hù)的興趣點(diǎn)訪問(wèn)頻率。于是在輸出頻繁模式及訪問(wèn)頻率之前，應(yīng)該對(duì)這k個(gè)頻繁模式進(jìn)行加噪保護(hù)，以此來(lái)保護(hù)用戶(hù)的位置隱私。如算法3所示。

算法3Add-Noise(B,ε2)算法

輸入：查詢(xún)函數(shù)F、集合B、隱私預(yù)算ε2。

輸出：添加拉普拉斯噪聲后的k個(gè)頻繁模式集合。

1)k←|B|

/*k表示集合B中的元素個(gè)數(shù) */

/* 對(duì)模式bi添加拉普拉斯噪聲*/

3) returnB

在步驟2中添加的噪聲服從拉普拉斯分布，分布函數(shù)為：

(6)

式中：x表示興趣點(diǎn)的訪問(wèn)頻率。

2 實(shí)驗(yàn)與結(jié)果分析

用于算法實(shí)驗(yàn)測(cè)試的數(shù)據(jù)來(lái)源于Foursquare網(wǎng)站，該網(wǎng)站包括從2010年3月到2011年12月的所有數(shù)據(jù)，其中包含18 293個(gè)用戶(hù)的基本信息、43 186個(gè)興趣點(diǎn)信息以及用戶(hù)簽到所產(chǎn)生的1 903 909次簽到數(shù)據(jù)。

3.1 數(shù)據(jù)效用性分析

為驗(yàn)證加入差分隱私保護(hù)的興趣點(diǎn)推薦算法所產(chǎn)生的數(shù)據(jù)的完整性和安全性，分別取 50、100和200個(gè)興趣點(diǎn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。在實(shí)驗(yàn)中，設(shè)定一個(gè)訪問(wèn)頻率l，當(dāng)興趣點(diǎn)的訪問(wèn)頻率高于l時(shí)，將該興趣點(diǎn)稱(chēng)為敏感位置；反之，則稱(chēng)為非敏感位置。根據(jù)實(shí)驗(yàn)結(jié)果，統(tǒng)計(jì)出不同模式下的敏感位置數(shù)量，如表3所示。

表3 不同模式下的敏感位置數(shù)量

圖4表示不同模式下，兩種推薦算法所產(chǎn)生的敏感位置的數(shù)量對(duì)比折線圖。

圖4 兩種推薦算法的Recall對(duì)比圖

由圖4可以看出，經(jīng)過(guò)差分隱私保護(hù)的興趣點(diǎn)推薦算法產(chǎn)生的敏感位置個(gè)數(shù)明顯增加，當(dāng)取50個(gè)興趣點(diǎn)進(jìn)行試驗(yàn)時(shí)，敏感位置由7個(gè)增加到了12個(gè)；取100個(gè)興趣點(diǎn)時(shí)，敏感位置由11個(gè)增加到了25個(gè)；取200個(gè)興趣點(diǎn)時(shí)，敏感位置由13個(gè)增加到了37個(gè)。

由實(shí)驗(yàn)結(jié)果得出，使用差分隱私保護(hù)機(jī)制對(duì)這些實(shí)驗(yàn)數(shù)據(jù)進(jìn)行加噪處理時(shí)，加入的拉普拉斯噪聲會(huì)使實(shí)驗(yàn)數(shù)據(jù)的訪問(wèn)頻率增大，因此更多實(shí)驗(yàn)數(shù)據(jù)的訪問(wèn)頻率會(huì)達(dá)到敏感位置的訪問(wèn)頻率閾值，從而使得非敏感位置變成了敏感位置，增加了攻擊者的攻擊難度，更好地保護(hù)了用戶(hù)的真實(shí)位置信息。由此可見(jiàn)，加入差分隱私保護(hù)機(jī)制的興趣點(diǎn)推薦算法不僅能夠保證數(shù)據(jù)的安全性，而且還維持了數(shù)據(jù)的完整性。

3.2 結(jié)果分析

實(shí)驗(yàn)通過(guò)召回率R和準(zhǔn)確率P[12]這兩個(gè)指標(biāo)來(lái)評(píng)估該算法推薦效果的好壞。召回率是指推薦算法返回的被標(biāo)記并加噪的興趣點(diǎn)數(shù)量比上所有被標(biāo)記的興趣點(diǎn)數(shù)量，準(zhǔn)確率是指推薦算法返回的被標(biāo)記并加噪的興趣點(diǎn)數(shù)量比上所有被加噪的興趣點(diǎn)數(shù)量。令集合A表示所有被標(biāo)記過(guò)的興趣點(diǎn)集合，集合B表示算法返回的加噪后的興趣點(diǎn)集合，根據(jù)上述定義，得出召回率與準(zhǔn)確率的公式為：

(7)

(8)

實(shí)驗(yàn)計(jì)算中k表示推薦算法待返回的興趣點(diǎn)個(gè)數(shù)，k的取值是不斷變化的。在k的所有取值情況下(k=5，10，20，50)，將召回率和準(zhǔn)確率作為評(píng)價(jià)算法好壞的指標(biāo)，比較加入差分隱私保護(hù)算法后的興趣點(diǎn)推薦算法與傳統(tǒng)的興趣點(diǎn)推薦算法的性能差異。

圖5表示在k取值變化的情況下，傳統(tǒng)的興趣點(diǎn)推薦算法和加入差分隱私保護(hù)的興趣點(diǎn)推薦算法的召回率對(duì)比圖。

圖5 兩種推薦算法的Recall對(duì)比圖

圖6表示在k取值變化的情況下，傳統(tǒng)的興趣點(diǎn)推薦算法和加入差分隱私保護(hù)的興趣點(diǎn)推薦算法的準(zhǔn)確率對(duì)比圖。

圖6 兩種推薦算法的Precision對(duì)比圖

對(duì)圖5和圖6進(jìn)行分析，可以得出無(wú)論是召回率還是準(zhǔn)確率，差分隱私保護(hù)算法的加入都沒(méi)有對(duì)推薦算法產(chǎn)生非常大的影響。傳統(tǒng)的興趣點(diǎn)推薦算法和加入差分隱私保護(hù)的興趣點(diǎn)推薦算法的有效性總體一致，加入差分隱私保護(hù)的推薦算法從召回率和準(zhǔn)確率這兩個(gè)指標(biāo)上看至少不會(huì)比傳統(tǒng)的推薦算法差太多。

實(shí)驗(yàn)結(jié)果印證了我們對(duì)差分隱私保護(hù)的興趣點(diǎn)推薦算法優(yōu)越性的理論分析，使用該算法，不僅能保護(hù)用戶(hù)的位置隱私信息，還能保證良好的推薦效果。

4 結(jié) 語(yǔ)

本文提出的基于差分隱私保護(hù)的興趣點(diǎn)推薦算法的核心思想是在傳統(tǒng)的推薦算法中加入差分隱私保護(hù)算法。通過(guò)對(duì)差分隱私定義、定理以及性質(zhì)的理解，本文提出了一種全新的地理位置隱私保護(hù)算法。該算法首先根據(jù)數(shù)據(jù)集中各項(xiàng)記錄的相互關(guān)系建立位置搜索樹(shù)，方便接下來(lái)實(shí)驗(yàn)中的查找、加噪和發(fā)布處理；然后運(yùn)用指數(shù)機(jī)制挑選出經(jīng)常訪問(wèn)的k項(xiàng)記錄；最后對(duì)這k項(xiàng)記錄添加拉普拉斯噪聲并發(fā)布加噪后的位置搜索樹(shù)。該地理位置隱私保護(hù)算法與傳統(tǒng)的位置隱私算法相比，運(yùn)用了差分隱私保護(hù)機(jī)制，采用了樹(shù)的結(jié)構(gòu)來(lái)表示位置數(shù)據(jù)。對(duì)位置記錄進(jìn)行加噪處理時(shí)，加噪擾動(dòng)的對(duì)象是節(jié)點(diǎn)中的所有位置記錄，而不是對(duì)單獨(dú)的位置記錄進(jìn)行加噪處理，這樣設(shè)計(jì)算法不僅能減少加噪次數(shù)，使記錄具有較高的可用性，還能保持記錄之間的關(guān)聯(lián)，提高算法的運(yùn)行效率。

對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析可知，加入差分隱私保護(hù)機(jī)制的興趣點(diǎn)推薦算法仍具有良好的性能。在實(shí)驗(yàn)過(guò)程中，該算法具有較高的數(shù)據(jù)可用性和安全性，能在很大程度上減少添加的噪聲量，從而達(dá)到既能保護(hù)用戶(hù)的隱私信息又具有良好推薦效果的目的。