基于差分隱私的混合位置隱私保護

徐啟元 陳珍萍 付保川 許馨尹 邵雪蓮

(蘇州科技大學電子與信息工程學院 江蘇 蘇州 215009)

0 引 言

隨著智能終端的廣泛應用，智能手機、平板等設備已經成為人們生活中的必須品，用戶使用全球定位系統(Global Position System，GPS)和通信運營商的定位服務也在日益精確，基于位置的服務(Location-Based Services，LBS)得到越來越廣泛的應用，用戶可以通過這些LBS應用搜索附近的所有餐廳、距離自己最近的電影院等[1]。然而，LBS的廣泛應用也帶來了一系列問題，其中一個重要問題就是用戶位置信息存在被泄露的風險[2]。近些年來，關于位置隱私保護的研究非常活躍，取得了很多研究成果。

文獻[3]采用模糊策略對位置進行模糊化處理，雖然可以保護位置隱私，但影響了感知數據的服務質量，降低了數據可用性。文獻[4]采用假名替換，即把用戶真實身份用預先設定的假名替代，從而隱藏了用戶真實身份，但若攻擊者掌握了替代規律，也可能挖掘出用戶的真實信息。文獻[5-6]通過K-匿名方法來保護位置隱私，將K個用戶位置組成一個匿名集，使得攻擊者即使獲得了每個用戶的具體位置，仍無法從K個用戶中確定真正的查詢請求用戶，從而在一定程度上達到了保護用戶位置隱私的目的。然而，K的增加可能會使隱形區域最大化，由于是在服務器端處理開銷，導致響應時間延遲。因此，隱形區域的最大化可能會降低LBS應用程序提供查詢服務的質量。文獻[7]提出了地理l-多樣性原則，要求用戶位置信息不能被l個位置集所識別，防止由于用戶間相距過近而被攻擊者推導出用戶所處區域的大致位置。

上述方法都是在假定對手沒有用戶背景信息的基礎上進行的研究，因而當對手擁有用戶的背景信息時，上述方法很可能將用戶的信息泄露，例如在利用k-means聚類算法進行位置泛化時，簡單地通過歐幾里得函數計算每個距離當前用戶位置最近的聚類中心很容易遭到數據攻擊進而泄露位置信息。文獻[8]提出一種將k-means聚類算法與差分隱私保護技術相結合的方法，差分隱私是一種具有完全獨立于攻擊者背景信息的強隱私保護技術，使得該方法具有較強的隱私保護能力。但是在仿真實驗過程中，這種差分隱私k-means隱私保護方法的聚類結果可用性較低，本文針對這一問題并結合LBS的自身特點提出一種基于差分隱私的k-means混合位置隱私保護方法。

用戶先將位置發送到可信匿名服務器，通過對用戶位置的人流密度參數進行分析將用戶位置點分成離散位置點和非離散位置點。對于離散點我們采用基于差分隱私的單獨加噪技術進行隱私保護；對于非離散點，選取其中人流密度較大的點作為初始聚類中心點，通過改進的k-means聚類算法來實現位置數據的泛化處理，并在泛化過程中使用差分隱私技術對可能泄露的發布數據進行加噪，最終將算法收斂后的聚類中心點和離散點位置集發送給LBS服務器來獲取位置服務。仿真實驗證明算法能夠在相同隱私性的條件下提高數據的可用性。

1 位置隱私保護模型

1.1 差分隱私技術

差分隱私技術是文獻[9]提出的，是一種與背景知識無關的強隱私保護模型。文獻[10]在此基礎上提出位置差分隱私，其定義如下：

定義1ε-位置差分隱私:對于2個位置數據集D和D′，假定兩者最多只有一條位置信息不同，即兩者的線性相異距離|D-D′|≤1，M為隨機查詢函數，并具有差分隱私保護，Rang(M)代表M的取值范圍，若D和D′在查詢函數M下得到的任意位置L(L?Rang(M))滿足下式，則查詢函數M滿足ε-位置差分隱私[10]。

Pr[M(D)∈L]≤Pr[M(D′)∈L]eε

(1)

式中:Pr[·]表示位置信息被泄露的概率，由算法M的隨機性控制；參數ε為隱私保護預算，ε越小隱私保護程度越高。

全局敏感度是差分隱私保護算法的一個重要度量指標。它的大小只與函數f本身有關，與數據集大小無關。全局敏感度的定義如下。

定義2全局敏感度[11]:對于任意函數f:D→Rd，f的全局敏感度定義為:

(2)

差分隱私保護的實現機制主要有拉普拉斯機制[12]和指數機制[13]，其中拉普拉斯機制多用于數值型數據，指數機制一般用于非數值型數據。本文采用拉普拉斯加噪機制。

定義3拉普拉斯機制:給定位置數據集D，對任意函數f:D→Rd，其敏感度為Δf，若函數f輸出結果滿足：

M(DM)=f(DM)+Lap(b)

(3)

1.2 位置隱私保護

標準差分隱私被證明可以應用于有多用戶位置的信息發布，但并不適用單個用戶位置。文獻[14]提出一種滿足差分隱私的地理不可區分性理論，它通過向用戶的真實位置添加平面拉普拉斯噪聲生成干擾位置，這種滿足差分隱私的加噪方式即使被有背景信息的對手觀察到，也不能以較高準確率判斷出真實位置。

對于用戶位置x=(s,t)，其中s和t分別為位置的二維坐標，給定隱私保護預算ε，若添加噪聲后生成位置x′的概率P(x)(x′)滿足：

(4)

則稱該加噪保護機制滿足ε-位置差分隱私。

從式(4)可以看出，在隱私預算ε一定且d(x,x′)>0時，概率P(x)(x′)隨著x′到x的距離增大而減小，取值只與x′到x的距離d(x,x′)有關。為簡化起見，可將該概率轉化為極坐標形式，具體為：

(5)

式中:r表示x′到x的距離，θ為x′在極坐標下與極軸的夾角。同樣可將式(5)分解到半徑R和角度Θ上，以得到如下概率分布函數：

(6)

(7)

2 混合位置隱私保護方法

現有差分隱私k-means算法在進行位置數據的隱私保護時，少量的離群點會導致算法輸出結果產生較大的偏差，且對初始中心點較為敏感，導致其具有較低的位置數據可用性。本文提出一種混合位置隱私保護方法，在k-means算法進行初始中心點選擇時，根據不同地理空間區域人流密度的不同，將一些離群用戶從用戶集合中剔除，以減少因為離群點對聚類穩定性的干擾。然后將初始中心點分配到人流較集中的區域而不是隨機選取，使初始中心點距離最終輸出的中心點位置較接近，減少算法的迭代次數，提高了聚類結果的穩定性和LBS服務的可用性。對于離群用戶點進行單獨加噪方法來對其進行位置隱私保護。本文所提方法根據不同用戶周圍人流密度的不同，采取的混合隱私保護方法可以提高聚類的穩定性，同時也對離群位置點進行了很好的隱私保護。

2.1 離群點的判定

對于用戶位置數據集X={x1,x2,…,xn}，任一用戶位置點xi為中心、半徑為Rm的區域稱為點xi的鄰域，領域內的用戶數ui稱為點xi基于Rm的人流密度。對包含有n個用戶的數據集X={x1,x2,…,xn}，取用戶間的平均距離為半徑Rm，則Rm可為：

(8)

ui=|Ni|Ni={xj|d(xi,xj)≤Rm}

(9)

ui值可以反映位置xi周圍點的稀疏程度。

離群點是指與其他點有明顯不同的數據點，一般可分為全局離群點、情境離群點、集體離群點[15-16]，鑒于本文主要面對的是數值型數據的保護，不涉及具體情境或者群組，因此只考慮全局離群點，即位置數據集X={x1,x2,…,xn}中與其余點差別均很大的數據點。對于離群點的判定，由文獻[17]數據集中X的稀有類由至多5%的數據點組成，因而數據集中離群點數目nD不超過n×0.05，可表示為nD=└n×0.05┘ 。對于位置數據集X={x1,x2,…,xn}的nD個離群點的判定，可通過式(9)計算得到的每個位置點xi處的人流密度參數ui，取密度參數最小的nD個點作為位置隱私保護中的離群點。

2.2 離群點隱私保護方法

在本文所提混合位置隱私保護中，對于離群點采用單獨加噪的方法來進行隱私保護。具體如算法1所示。

算法1離群點隱私保護

輸入：用戶位置數據集X={x1,x2,…,xn}(xi=(st,ti)，隱私預算ε；

輸出：加噪離群點集D′，非離群點集X2。

2) 由式(9)計算每個位置點xi處的人流密度參數ui(i=1,2,…,n)；

確定位置極坐標表的隨機噪聲ri和θi，其中θi為[0,2π)間均勻分布隨機數，νi為[0,1)間均勻分布的隨機數，而Cε(νi)為概率密度函數Pε,r(νi)在[0,νi]上的積分函數，滿足：

用以表示隨機半徑ri落在0到νi上的累積概率。

5) 按照：

2.3 混合k-means隱私保護方法

算法2混合k-means隱私保護

輸出：差分隱私保護的位置數據集X′=D′∪C″。

確定位置極坐標表的隨機噪聲ri和θi，νi為[0,1)間均勻分布的隨機數，而Cε(νi)為概率密度函數Dε,r(νi)在[0,νi]上的積分函數，按照：

8) 輸出通過差分隱私保護的位置數據集X′=D′∪C″。

這時離散點的位置由單獨加噪后的位置代替，非離散點的原始位置由加噪后的聚類中心點代替。

3 仿真結果與分析

為驗證本文所提混合位置隱私保護方法的有效性，在MATLAB仿真平臺上進行算法的數值仿真。數值仿真主要關注目標為用戶在獲取LBS服務的過程中位置數據的安全性和可用性，以及改進算法在聚類過程中的聚類效果。

3.1 參數設置

本實驗在MATLAB環境中在2×2的空間隨機生成n=80個二維數據點來模擬用戶位置，也即有用戶xi=(si,ti)(i=1,2,…,n)，si∈(0,2),ti∈(0,2)。聚類簇數通過文獻[18]給出的評價指標誤差平方和(Sum of the Squared Errors，SSE)來確定，通過計算不同k值下的SSE觀察到當k取3為其最佳聚類數，因此取k=3，對算法運行10次取平均值作為輸出的結果進行比較分析。

3.2 聚類誤差分析

下面進行本文所提混合位置隱私保護方法、基于差分隱私的k-means算法以及位置單獨加噪方法的聚類誤差Error的分析。分別記E1、E2、E3為本文所提差分隱私k-means混合隱私保護方法、單獨加噪和傳統差分隱私k-means方法運行結果的偏移誤差，即每個位置點的原始位置與輸出的加噪后的查詢位置點之間的誤差。

圖1 本文算法的聚類輸出結果，其中ε=2

圖2 不同隱私預算ε下對算法誤差的影響

通過圖2可以看出，在隱私預算ε較小的時候，三種加噪方法的輸出距離原始數據誤差均過大；隨著隱私預算ε的不斷增加，誤差先是急劇減小，然后下降幅度逐漸減少并趨于穩定。因而在實際應用過程中，可以取趨于穩定后并且ε較小的值作為隱私預算。通過比較三種不同的加噪方式發現，在相同的隱私預算ε下本文提出的混合位置隱私保護算法的誤差比另外兩種算法的誤差較小。

3.3 數據可用性分析

(10)

圖3 不同隱私預算ε下的F-measure運行結果

通過圖3可以看出，本文提出的基于差分隱私的混合k-means聚類算法滿足ε差分隱私的要求，能夠有效地保護用戶的位置隱私，并且與差分隱私k-means算法相比，F-measure值有了較大提升，這說明本文提出的算法在相同隱私預算ε下具有更高的數據可用性。

4 結 語

對于傳統使用k-means進行數據泛化可能導致位置數據泄露的問題，本文提出了一種結合LBS數據特點的差分隱私混合k-means位置隱私保護算法。通過使用密度參數來選擇聚類的初始中心點，對中心點和聚類過程中可能泄露用戶隱私的數據添加滿足差分隱私的Laplace噪聲，并將離散點提取出來單獨加噪減少來增加聚類可用性。實驗結果表明，改進后的算法減少了聚類中簇的迭代次數，提高了聚類中心精度，并且在添加相同噪聲的情況下提高了位置數據的可用性。下一步將根據用戶對查詢結果的反饋，根據不同用戶對數據的隱私需求程度不同添加不同的噪聲等級，從而給用戶更好的LBS體驗和滿足用戶的安全性要求。