差分隱私模糊聚類位置保護(hù)方法

林 靜，胡德敏，王揆豪

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

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

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

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

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

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

1 差分隱私模糊聚類位置保護(hù)方法

1.1 基本定義

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

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

(1)

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

定義2全局敏感度。假設(shè)函數(shù)f:D→Rd，D是一個(gè)數(shù)據(jù)集。對于任意的兩個(gè)臨近數(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維空間中兩點(diǎn)間的真實(shí)距離，或一個(gè)矢量的長度[14]為歐氏距離，如下式所示。

(6)

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

(7)

1.2 相關(guān)技術(shù)

1.2.1 隸屬函數(shù)

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

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

(8)

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

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

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

高斯核函數(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)計(jì)算U(k+1)；

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

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

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

(15)

(16)

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

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

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

圖1 BIRCH算法流程圖

1.4 DPK-F算法

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

圖2 DPK-F模型步驟

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

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

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

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

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

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

輸出：符合差分隱私的結(jié)果集合Dres。

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

步驟2計(jì)算Ck對應(yīng)集合的誤差平方和，取最小誤差平方和φmin所對應(yīng)的簇中心點(diǎn)d作為聚類初始點(diǎn)；

d=dminφk

(17)

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

(18)

運(yùn)行目標(biāo)函數(shù)

(19)

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

(20)

(21)

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

(22)

此時(shí)，迭代終止；

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

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

(23)

(24)

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

證明設(shè)數(shù)據(jù)集D通過高斯核函數(shù)模糊聚類得到若干個(gè)不同聚類。則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 實(shí)驗(yàn)與分析

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

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

2.1 查詢準(zhǔn)確度分析

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

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

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

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

(a)

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

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

(28)

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

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

(a)

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

2.3 算法效率分析

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

圖7 算法運(yùn)行時(shí)間

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

3 結(jié)束語

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