基于差分隱私保護的興趣點推薦算法設計

張青云 張 興 李萬杰 李 帥 李曉會

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

0 引 言

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

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

上述文獻提出的算法雖然能從不同角度滿足興趣點推薦系統的要求，但是并沒有考慮到用戶的隱私泄漏問題。為了在保護用戶隱私信息的同時不影響推薦效果，本文對傳統興趣點推薦算法進行改進，在其基礎上添加差分隱私保護機制，以此來防止攻擊者的惡意攻擊。

1 基本工作原理

1.1 傳統興趣點推薦算法工作原理

傳統的興趣點推薦算法主要使用協同過濾推薦算法來實現推薦功能。該算法可分為兩大類，分別是基于用戶的協同過濾推薦算法和基于項目的協同過濾推薦算法。下面簡單地介紹這兩類推薦算法的原理：

基于用戶的協同過濾推薦算法：首先根據收集到的用戶信息來計算用戶之間的相似度，找到與當前目標用戶相似度高的所有用戶集合，然后再收集這個集合中的用戶對其他興趣點的評分，通過對不同興趣點的評分等級來推測出目標用戶對該興趣點的喜好程度，從而實現推薦功能。

基于興趣點的協同過濾推薦算法：首先根據目標用戶對興趣點的喜好程度找到與之相似的興趣點集合，然后根據用戶的偏好和興趣點集合中的項目進行相似度排序，將相似度高的興趣點推薦給目標用戶。

1.2 差分隱私相關概念

自2006年差分隱私發表以來，在機器學習和數據挖掘領域產生了巨大的影響。Dwork[8]將差分隱私定義為一種類似數據加密的方法。在這種定義下，對于數據集的計算結果而言，單個記錄是否在數據集中對結果造成的影響可以忽略不計。因此，攻擊者不能計算出某條記錄是否在該數據集中。本文使用的定義、定理與性質[8]如下所示：

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

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

(1)

式中：S?Range(A)，數據庫D和D′至多相差一條記錄，數據庫中的每條記錄都對應一個個體。差分隱私有兩個重要的性質：

性質1若原始數據v是算法A的輸出結果，算法A滿足ε-差分隱私，那么關于v的任意函數g(v)的輸出結果均滿足ε-差分隱私。

性質2對原始數據v使用兩個隱私保護算法A1和A2，其中，A1滿足ε1-差分隱私，A2滿足ε2-差分隱私，那么v的隱私保護參數至多為ε1+ε2。

定理1令D和D′為兩個至多相差一條記錄的數據庫，F表示向數據庫請求的查詢函數，那么查詢算法F的敏感度ΔF表示為:

(2)

通俗而言，可以把算法敏感度ΔF理解成隨機增加或者刪除一條記錄對整個數據集查詢結果的最壞影響。

定理2如果變量x的概率密度分布函數Pr[x|μ,λ]滿足:

(3)

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

對于數據集D而言，如果查詢數據為數值型，則使用拉普拉斯機制對查詢結果進行加噪處理；反之，如果查詢數據為非數值型，則使用指數機制來處理查詢結果。

文獻[9]提出了指數機制的概念。指數機制常被用于分類算法中多個分類值的選擇問題。打分函數mark(D,r)(r∈D)的設計是指數機制的核心部分，其中r表示隨機在值域D中選取的輸出結果。

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

2 地理位置隱私保護算法設計

2.1 設計思路

在推薦服務中，興趣點的推薦服務是一個重要的研究方向。在設計推薦算法時，不僅要有準確的推薦結果，還要同時考慮到用戶的隱私泄露問題。文中提出的基于差分隱私保護的興趣點推薦算法就是在傳統的興趣點推薦算法中加入地理位置隱私保護算法，以此達到預期目的。地理位置隱私保護算法首先根據數據集中各項記錄的相互關系建立位置搜索樹，然后遍歷位置搜索樹并運用指數機制挑選出經常訪問的k項紀錄，最后對這k項記錄添加拉普拉斯噪聲并發布加噪后的位置搜索樹。地理位置隱私保護算法設計框圖如圖1所示。

圖1 地理位置隱私保護算法設計框圖

現有的位置隱私保護方法大多都是通過匿名化、位置信息隨機化和位置信息模糊化等[10]方法達到隱私保護的效果。當用戶向服務器位置服務組件發送一個當前位置信息來請求服務時，盡管發送的實時地理位置是經過處理的，但是對其簽到所在的興趣點信息卻沒有進行保護。攻擊者以及用于數據分析和數據挖掘的信息收集器仍然可以通過獲取該興趣點的相關信息獲得用戶的實時地理位置，所以對于當前位置隱私保護的程度是遠遠不夠的。因此，本文在原始興趣點推薦的基礎上加入了一種嚴謹的基于差分隱私保護機制的地理位置隱私保護算法。

在數據集D的頻繁模式挖掘中，應該在挖掘top-k頻繁模式之前采用指數機制挑選出數據集D中所有訪問頻率大于min-count的k個頻繁模式，然后采用拉普拉斯噪音機制擾動挖掘結果，向挖掘結果中添加適當噪聲，以此保護top-k模式的訪問頻率不被泄露。本文就top-k頻繁模式挖掘問題，引入了位置搜索樹(LQ-Tree)結構，文中定義關于位置數據庫D的LQ-Tree為LQTD。

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

算法1D-LPP算法

《國家中長期教育改革和發展規劃綱要(2010—2020年)》明確提出要創新人事管理方式，引導教師潛心教學科研，改善教師工作和生活條件，關心教師身心健康。因此教育行政管理部門和學校應充分發揮廣大教師在參與學校校務監督、民主管理中的作用，滿足廣大教師合法表達利益、對學校事務知情監督的訴求，努力構建和諧的校園。

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

輸出：加噪后的位置搜索樹NLQTD

1) 將數據集D中的所有元素構建成一個完整的位置搜索樹LQTD。

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

3) 運用指數機制挑選出k個滿足條件的頻繁模式記錄，將這些記錄表示為bi，由bi構成的集合稱為集合B。

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

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

2.2 建立位置搜索樹

通過用戶L一個月內的歷史行為記錄，篩選出用戶經常訪問的k個興趣點，構建用戶的位置數據庫D，并根據數據庫D構建一個位置搜索樹。圖2表示的是用戶L一個月內經常訪問的5個興趣點。

圖2 位置數據

對地圖上的每個位置進行編號，根據圖2的位置數據構建位置對應關系表，如表1所示。

表1 位置對應關系

表2 位置數據庫

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

圖3 位置搜索樹

2.3 基于指數機制挑選頻繁模式

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

通過指數機制在A中選取k個滿足下式的頻繁模式ai，構成集合B：

(4)

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

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

輸入：集合A，隱私參數ε1。

輸出：挑選出的k個頻繁模式構成的集合B。

1)n←|A|

/*n表示集合A中的元素個數 */

2) fori=1 toNdo

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

/* 模式的打分函數 */

/* 打分函數的全局敏感度 */

/* 計算每個模式ai的權重 */

6) end for

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

/* 將權重存入鏈表L中 */

8) fori=1 tokdo

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

10) Randomly selectai∈L；

/* 從鏈表L中隨機選擇模式ai*/

11) InsetaiintoB；

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

12) end

其中，打分函數設置為:

mark(A,ai)=Pr(ai)

(5)

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

2.4 添加拉普拉斯噪聲

算法2只是選擇出k個頻繁模式，但并沒有對這k個模式的真實訪問頻率起到保護的效果，如果直接輸出會泄露用戶的興趣點訪問頻率。于是在輸出頻繁模式及訪問頻率之前，應該對這k個頻繁模式進行加噪保護，以此來保護用戶的位置隱私。如算法3所示。

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

輸入：查詢函數F、集合B、隱私預算ε2。

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

1)k←|B|

/*k表示集合B中的元素個數 */

/* 對模式bi添加拉普拉斯噪聲*/

3) returnB

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

(6)

式中：x表示興趣點的訪問頻率。

2 實驗與結果分析

用于算法實驗測試的數據來源于Foursquare網站，該網站包括從2010年3月到2011年12月的所有數據，其中包含18 293個用戶的基本信息、43 186個興趣點信息以及用戶簽到所產生的1 903 909次簽到數據。

3.1 數據效用性分析

為驗證加入差分隱私保護的興趣點推薦算法所產生的數據的完整性和安全性，分別取 50、100和200個興趣點數據進行實驗。在實驗中，設定一個訪問頻率l，當興趣點的訪問頻率高于l時，將該興趣點稱為敏感位置；反之，則稱為非敏感位置。根據實驗結果，統計出不同模式下的敏感位置數量，如表3所示。

表3 不同模式下的敏感位置數量

圖4表示不同模式下，兩種推薦算法所產生的敏感位置的數量對比折線圖。

圖4 兩種推薦算法的Recall對比圖

由圖4可以看出，經過差分隱私保護的興趣點推薦算法產生的敏感位置個數明顯增加，當取50個興趣點進行試驗時，敏感位置由7個增加到了12個；取100個興趣點時，敏感位置由11個增加到了25個；取200個興趣點時，敏感位置由13個增加到了37個。

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

3.2 結果分析

實驗通過召回率R和準確率P[12]這兩個指標來評估該算法推薦效果的好壞。召回率是指推薦算法返回的被標記并加噪的興趣點數量比上所有被標記的興趣點數量，準確率是指推薦算法返回的被標記并加噪的興趣點數量比上所有被加噪的興趣點數量。令集合A表示所有被標記過的興趣點集合，集合B表示算法返回的加噪后的興趣點集合，根據上述定義，得出召回率與準確率的公式為：

(7)

(8)

實驗計算中k表示推薦算法待返回的興趣點個數，k的取值是不斷變化的。在k的所有取值情況下(k=5，10，20，50)，將召回率和準確率作為評價算法好壞的指標，比較加入差分隱私保護算法后的興趣點推薦算法與傳統的興趣點推薦算法的性能差異。

圖5表示在k取值變化的情況下，傳統的興趣點推薦算法和加入差分隱私保護的興趣點推薦算法的召回率對比圖。

圖5 兩種推薦算法的Recall對比圖

圖6表示在k取值變化的情況下，傳統的興趣點推薦算法和加入差分隱私保護的興趣點推薦算法的準確率對比圖。

圖6 兩種推薦算法的Precision對比圖

對圖5和圖6進行分析，可以得出無論是召回率還是準確率，差分隱私保護算法的加入都沒有對推薦算法產生非常大的影響。傳統的興趣點推薦算法和加入差分隱私保護的興趣點推薦算法的有效性總體一致，加入差分隱私保護的推薦算法從召回率和準確率這兩個指標上看至少不會比傳統的推薦算法差太多。

實驗結果印證了我們對差分隱私保護的興趣點推薦算法優越性的理論分析，使用該算法，不僅能保護用戶的位置隱私信息，還能保證良好的推薦效果。

4 結 語

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

對實驗結果進行對比分析可知，加入差分隱私保護機制的興趣點推薦算法仍具有良好的性能。在實驗過程中，該算法具有較高的數據可用性和安全性，能在很大程度上減少添加的噪聲量，從而達到既能保護用戶的隱私信息又具有良好推薦效果的目的。