林 靜，胡德敏，王揆豪

(上海理工大學 光電信息與計算機工程學院，上海 200093)

在信息化時代，移動終端的位置服務廣為人知，簽到、導航、線路跟蹤等功能也存在于大量軟件中。為了增加搜索功能以便最大限度地提高效益，LBS(Location Based Service)[1]服務提供商收集大量用戶定位信息，形成用戶軌跡數(shù)據(jù)，并對這些數(shù)據(jù)進行分析優(yōu)化，從而給出興趣點推薦及位置共享服務等?；谖恢玫臄?shù)據(jù)發(fā)布雖然增加了日常生活的便捷性，但也增加了個人隱私信息被泄露的風險[2]。

目前國內(nèi)外應用在LBS背景下的位置隱私保護方法可分為4類：抑制法(Suppression)、加密法(Cryptography)、泛化法(Generalization)和擾動法(Confusion)。抑制法[3]是一種基于先驗知識，通過抑制敏感背景信息來保護用戶隱私的方法。但在需要刪除太多數(shù)據(jù)的情況下，這種方法會丟失大量數(shù)據(jù)，導致數(shù)據(jù)查詢服務質量低下。數(shù)據(jù)加密法[4]采用某種加密協(xié)議來實現(xiàn)身份和位置的保護，但是其實現(xiàn)過程需要較大的計算量，且匿名過程延時較長，實際應用效果不佳。泛化法[5]通過將數(shù)據(jù)點或數(shù)據(jù)軌跡由點到面進行轉換，以此來保護用戶位置隱私。由于泛化法需要加入很多輔助數(shù)據(jù)，導致算法運行效率降低且數(shù)據(jù)冗余過多。為了給真實數(shù)據(jù)增加噪點并擾亂其真實性，一般采用數(shù)據(jù)擾動法[6]。該方法用偽造的位置數(shù)據(jù)來替代原有數(shù)據(jù)集中真實的位置數(shù)據(jù)，例如文獻[7]提出的Virtual Avatar軌跡隱私保護方案，就是用擾動的數(shù)據(jù)點對真實的位置數(shù)據(jù)進行干擾，但是添加過多假數(shù)據(jù)會導致查詢請求結果不可靠。

差分隱私是在數(shù)據(jù)擾動法的基礎上提出的，主要是通過給位置點加噪聲擾動來保護真實的位置信息，具有嚴格的推理過程和數(shù)學證明，常被應用于位置隱私保護中。目前對于位置點加噪主要分為兩種方式：一是直接對此位置點加上滿足差分隱私的噪聲，但該方法會造成隱私預算過大、冗余過多，影響數(shù)據(jù)的真實性；二是對數(shù)據(jù)轉化后再添加噪聲，又可進一步分為網(wǎng)格劃分法和聚類法。網(wǎng)格劃分法是自頂向下逐步細分網(wǎng)格，尋找最優(yōu)劃分是算法的關鍵，但對于分布不均的數(shù)據(jù)集來說，網(wǎng)格大小相同，對應每個網(wǎng)格密度值的差別過大，加入噪聲后，擾動位置點并不能有效代表真實位置點。

基于聚類的數(shù)據(jù)加噪是近些年來相關工作中主流的研究方法，本文通過聚類與差分隱私相結合的方法來研究位置隱私保護。文獻[8]通過將拉普拉斯噪聲添加到實際的位置來保護用戶隱私，但這并不適用于移動環(huán)境，噪聲的疊加會影響數(shù)據(jù)的可用性以及查詢結果的真實性。文獻[9]將差分隱私與K-means算法相結合，添加拉普拉斯噪聲到該組的中心點，在獲得干擾數(shù)據(jù)點之前，通過合并位置點產(chǎn)生泛化效應，從而達到保護位置隱私的效果。然而，該方法對于初始中心點和初始值k的設置較為敏感，對k值的選取會對結果產(chǎn)生一定的影響。文獻[10]提出了基于差分隱私的混合位置保護方法，該方法將隨機噪聲添加到離散點，使用K-means算法將噪聲添加到非離散點泛化后的中心點，但對離散點直接添加噪聲會導致噪音數(shù)據(jù)過多，增大誤差；對于非離散點使用K-means算法聚類，選取不同初始聚類中心也會對結果產(chǎn)生較大影響。若存在異常點，會導致均值偏離，從而降低數(shù)據(jù)的可用性。

常見的差分隱私聚類位置保護方法對離散點敏感，且會盲目選擇初始值，導致結果不理想。此外，隱私疊加、隱私預算消耗過大也會降低數(shù)據(jù)的可用性。為了在滿足差分隱私的條件下，最大化查詢結果的精確性并提高算法效率，本文設計提出了一種差分隱私模糊聚類位置保護方法(Differential Privacy Kernel Fuzzy Clustering Location Protection Method，DPK-F)，將差分隱私與模糊C均值聚類算法(Fuzzy C-Means Clustering，F(xiàn)CM)相結合，同時使用BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法確定初始值，使得每一個輸入數(shù)據(jù)以隸屬程度來選擇類別。通過高斯核函數(shù)將數(shù)據(jù)點映射到特征空間，降低計算負載。隨后，選取最終聚類集合的質心點，加入滿足差分隱私的拉普拉斯噪聲，得到每個位置集合的擾動位置，并使用擾動位置進行查詢。實驗結果表明，該方法可以在保護用戶的位置隱私前提下，降低查詢誤差，提升算法效率。

1 差分隱私模糊聚類位置保護方法

1.1 基本定義

定義1差分隱私。給定一個算法K，若對于任意的數(shù)據(jù)集T1和T2，T1和T2里面只相差一個記錄，δ為一個比較小的常數(shù)，輸出S∈Range(K)滿足

Pr{K(T1)∈S}≤eε×Pr{K[T2]∈S}+δ

(1)

則該算法符合ε-差分隱私[11]。

定義2全局敏感度。假設函數(shù)f:D→Rd，D是一個數(shù)據(jù)集。對于任意的兩個臨近數(shù)據(jù)集D和D′，有

GSf=maxD，D′‖f(D)-f(D′)‖

(2)

其中，GSf為函數(shù)f的全局敏感度[12]；‖·‖表示曼哈頓距離，定義如式(3)所示。

‖x‖=|x1|+|x2|+…+|xn|

(3)

ΔQ=maxD，D′‖D-D′‖=1‖f(D)-f(D′)‖

(4)

概率密度分布如式(5)所示，λ為偏移量。

(5)

定義4歐氏距離。n維空間中兩點間的真實距離，或一個矢量的長度[14]為歐氏距離，如下式所示。

(6)

定義5誤差平方和。樣本x與樣本總平均值的偏差平方和是衡量樣本離散程度的重要指標，如式(7)[15]所示。

(7)

1.2 相關技術

1.2.1 隸屬函數(shù)

隸屬函數(shù)是衡量一個對象x屬于某個集合A的程度的函數(shù)，通常被記做μA(x)。它的范圍就是屬于集合A的所有值，取值范圍為[0，1]。當值為1時，代表x完全屬于集合A；當值為0時，就表示x完全不屬于該集合。因此，一個對象的隸屬函數(shù)就定義了一個模糊的集合。對于對象x1，x2，…，xn，模糊集合A可表示成式(8)。

A={(μA(xi)，xi)|xi∈x}

(8)

將每個聚類結果看作是一個模糊集合，每個數(shù)據(jù)點所對應集合的隸屬度在[0，1]區(qū)間內(nèi)。

1.2.2 核函數(shù)模糊C均值聚類

基于高斯核函數(shù)改進的模糊C均值聚類算法(Kernel Fuzzy C-Means Clustering，KFCM)是指通過一個核函數(shù)將原始空間中的點直接映射至一個特征空間中。考慮到無法用一個線性函數(shù)對原始空間中的點進行劃分，于是將其經(jīng)過變換放到一個高維空間中，并在這個高維空間中尋找到一個線性函數(shù)與之相對應，使之更容易對原始數(shù)據(jù)進行劃分[16]。本文選取基于核函數(shù)的模糊聚類算法，在提升算法精度的同時，使擾動位置用戶查詢可以更好地代表真實用戶的需求，縮短了查詢時間。

高斯核函數(shù)模糊聚類算法中，設X∈Rs，定義從X到特征空間H的映射為

φ:X→H:φ(x)=y

(9)

(10)

(11)

式中，K(vi，xj)是高斯徑向基函數(shù)[18]，其形式如式(12)所示。

(12)

利用拉格朗日的極值必要條件，求出聚類中心V和隸屬度矩陣U。

(13)

(14)

算法步驟如下：

步驟1FCM算法初始化隸屬度矩陣U；

步驟2用式(13)計算U(k+1)；

步驟3根據(jù)式(14)計算V(k+1)，令k=k+1；

步驟4重復步驟2和步驟3，直到滿足如式(15)所示的條件，或存在i(1≤i≤c)，使得式(16)成立，則可終止。

‖U(k)-U(k-1)‖<ε

(15)

(16)

1.3 確定聚類初始點和聚類數(shù)

對位置點進行隱私保護時，需要在不暴露用戶真實位置的前提下，得到盡可能準確的查詢結果。本文先對用戶位置點聚類，然后選取聚類后具有代表性的點，加入滿足差分隱私的拉普拉斯噪聲得到擾動位置點，并使用擾動位置代替真實位置查詢。但聚類算法普遍存在對初始點敏感且容易陷入局部最優(yōu)解的問題。為了讓初始化選取更加科學，實現(xiàn)更準確的聚類效果，本文采取BIRCH算法初步分類數(shù)據(jù)。

BIRCH利用層次方法的平衡迭代規(guī)約和聚類，只需要單遍掃描數(shù)據(jù)集就可以開始進行聚類。該算法使用了一個類似B+樹的樹結構來協(xié)助迅速聚類。該樹結構與平衡B+樹相似，故將其稱為聚類特征樹。這棵樹的每一個節(jié)點均包含若干個聚類特征，樹中的每一個節(jié)點都可以對應一個簇，子節(jié)點所對應的簇也就是父節(jié)點對應簇的子簇。BIRCH算法流程如圖1所示。

圖1 BIRCH算法流程圖

1.4 DPK-F算法

本文采用擾動位置代替真實位置進行LBS查詢，在查詢過程中需要對用戶真實位置進行保護。通常采用聚類的方法先將真實位置點聚類，選出具有代表的點進行位置查詢，若攻擊者有足夠多的背景知識，就會輕易推斷出用戶的隱私信息。所以本文將差分隱私與核函數(shù)模糊聚類相結合，提出一種差分隱私模糊聚類位置保護方法(DPK-F)。此方法不僅能夠保護有效用戶位置隱私，也提高了算法的效率。算法模型步驟如圖2所示。

圖2 DPK-F模型步驟

DPK-F算法分為3個環(huán)節(jié)：

(1)采用BIRCH算法將數(shù)據(jù)集初始化，得到聚類數(shù)，判斷初始點；

(2)運行KFCM算法對數(shù)據(jù)集進行聚類；

(3)取簇質心點，加入符合差分隱私的拉普拉斯噪聲。

DPK-F算法的具體步驟如下：

輸入：數(shù)據(jù)對象集D。

輸出：符合差分隱私的結果集合Dres。

步驟1在數(shù)據(jù)對象集D上運行算法BIRCH，算法參數(shù)都取默認值，得到聚類個數(shù)k和各集合Ck；

步驟2計算Ck對應集合的誤差平方和，取最小誤差平方和φmin所對應的簇中心點d作為聚類初始點；

d=dminφk

(17)

步驟3設定徑向基函數(shù)的參數(shù)σ、聚類個數(shù)k、模糊指數(shù)m(一般取[1.5，2.5])以及收斂精度ε(此處取0.000 01)，令迭代次數(shù)為0，用FCM算法初始化隸屬度矩陣U，并運行KFCM算法聚類徑向基函數(shù)

(18)

運行目標函數(shù)

(19)

其中，聚類中心V、隸屬度矩陣U分別如下所示

(20)

(21)

當‖U(k)-U(k-1)‖<ε或存在i(1≤i≤c)使得

(22)

此時，迭代終止；

步驟4得到最優(yōu)聚類集D′；

M(Ci)=f(Ci)+Y，i=1，…，k

(23)

(24)

步驟6輸出差分隱私保護的擾動后數(shù)據(jù)集Dres。

證明設數(shù)據(jù)集D通過高斯核函數(shù)模糊聚類得到若干個不同聚類。則D=C1∪C2∪C3∪…∪Cn，D′=C′1∪C′2∪C′3∪…∪C′n，由式(1)和式(2)可知

(25)

(26)

由式(25)除以式(26)得

(27)

只需，|f(C1)-f(C′1)|≤max(C1，C′1)，|f(C1)-f(C′1)|=Δf1，即滿足(ε1，δ)-差分隱私。

同理，由并行組合定理可知，算法DPK-F滿足差分隱私要求。

算法流程如圖3所示。

圖3 DPK-F算法流程圖

2 實驗與分析

本文基于用戶獲取LBS服務的響應時間以及查詢結果的準確性和誤差等方面來衡量隱私保護效果。本文分別在Gowalla位置簽到數(shù)據(jù)集以及虛擬用戶位置數(shù)據(jù)集(Data)上進行實驗。其中，Gowalla位置簽到數(shù)據(jù)集包含了用戶ID、經(jīng)緯度、簽到地點ID等重要信息。通過提取用戶簽到經(jīng)緯度作為位置點數(shù)據(jù)，并以地點ID作為請求的查詢位置來進行實驗分析。通過與經(jīng)典差分隱私K-means保護算法和文獻[11]提出的混合K-means保護算法進行指標對比來驗證本文所用方法的性能。

本文使用Python編程語言進行仿真實驗，使用Thomas Brinkhoff路網(wǎng)數(shù)模擬器生成1 000個模擬數(shù)據(jù)，將其組成一組模擬用戶位置查詢數(shù)據(jù)集。單機環(huán)境為Inter(R)Core(TM)i7 CPU 3.7 GHz，8 GB內(nèi)存，Windows 10 64位操作系統(tǒng)。

2.1 查詢準確度分析

實驗查詢結果的準確性使用聚類評價指標輪廓系數(shù)、準確率來分析，本文采用差分隱私與聚類方法結合，目的是為了聚類真實位置點，選取足夠代表用戶查詢位置的擾動位置點進行查詢。因此，聚類效果可以有效反應出查詢的準確性。實驗分別對比了DPK-means、混合DPK-means算法在Iris、Wine、Gowalla和模擬數(shù)據(jù)集Data上的效果。

通過圖4可以看出，與其他經(jīng)典算法相比，本文提出的DPK-F算法在Iris、Wine、Gowalla和模擬數(shù)據(jù)集Data上的輪廓系數(shù)更接近于1。這表明在相同隱私預算條件下，本文所提方法的聚類性能更好，虛擬值能更好地代表真實值，準確度更高。

圖4 輪廓系數(shù)對比

通過圖5可以看出，隱私預算ε越接近1，準確率越高。在相同隱私預算ε下，與其他算法相比，本文提出的DPK-F算法在Iris、Wine、Gowalla和模擬數(shù)據(jù)集Data上的聚類準確率大于90%，優(yōu)于其他算法。實驗結果表明DPK-F算法分類結果更精確，查詢準確性更高。

(a)

2.2 數(shù)據(jù)可用性分析

本文采用相對誤差來衡量實驗的數(shù)據(jù)可用性，其計算式為

(28)

式中，A(s)表示真實查詢結果；QM(s)代表經(jīng)過位置隱私保護算法后運行的查詢結果；p=0.001×|D|；D為數(shù)據(jù)集樣本數(shù)。相對誤差可有效反映出算法的查詢誤差，避免由于匿名區(qū)域大小差別過大，或噪聲添加差別過大而導致的查詢精度下降問題。相對誤差越小，表示查詢結果越接近真實結果，數(shù)據(jù)可用性越好；反之，相對誤差越大，表明查詢結果越偏離真實結果，數(shù)據(jù)可用性低。實驗分別對比了DPK-means、混合DPK-means算法在Gowalla和虛擬數(shù)據(jù)集Data上的效果。

圖6給出了DPK-F算法與DPK-means、混合DPK-means在不同數(shù)據(jù)集中改變隱私預算時的相對誤差變化情況。

(a)

從圖6可以看出，實驗誤差隨隱私預算ε的增大而減小。在同一隱私預算下，與DPK-means、混合DPK-means算法相比，DPK-F算法誤差更小，數(shù)據(jù)可用性更高。

2.3 算法效率分析

本文在Gowalla數(shù)據(jù)集和虛擬數(shù)據(jù)集Data中進行算法效率分析實驗。取隱私預算ε=1.0，對比DPK-means、混合DPK-means和DPK-F這3種算法的運行時間，如圖7所示。

圖7 算法運行時間

從圖中可以看出，DPK-means算法與DPK-F算法運行時間相差不大。根據(jù)圖6可知，同一隱私參數(shù)下，與其他算法相比，DPK-F算法降低了查詢結果誤差，提升了查詢精確度。與此同時，DPK-F算法較混合DPK-means算法的運行時間縮短了近1/4，在保護位置隱私的前提條件下，降低了查詢時間。

3 結束語

為了在保護隱私的條件下獲取高精度位置查詢，并提升算法效率，本文提出了一種差分隱私模糊聚類位置保護方法(DPK-F)。該方法將差分隱私與改進的模糊C均值聚類算法相結合，使用BIRCH算法確定初始值，引入高斯核函數(shù)將原始空間中的點映射到特征空間，選取最終聚類集合的質心點加入符合差分隱私的拉普拉斯噪聲來得到每個位置集合的擾動位置點，并使用擾動位置進行查詢。實驗結果表明，該方法可以降低查詢誤差，提升算法效率。在今后的研究中，計劃引入分布式系統(tǒng)來進一步提升算法效率，并探索DPK-F算法在其它方面的應用。