基于密度的噪聲應(yīng)用空間聚類算法的差分隱私軌跡保護(hù)機(jī)制

劉凱， 韓益亮*， 郭凱陽， 吳日銘， 汪晶晶

(1.武警工程大學(xué)密碼工程學(xué)院， 西安 710086； 2.武警部隊(duì)密碼與信息安全保密重點(diǎn)實(shí)驗(yàn)室， 西安 710086)

隨著移動(dòng)通信設(shè)備和第五代移動(dòng)通信技術(shù)(5th generation mobile communication technology，5G)技術(shù)的快速發(fā)展，移動(dòng)用戶上傳的個(gè)人信息和服務(wù)提供商接收的用戶信息每天都在增加，在這樣的發(fā)展背景下，基于位置的服務(wù)(location-based service, LBS)也從導(dǎo)航方面的應(yīng)用逐步擴(kuò)展到社交、游戲等領(lǐng)域[1]。如今的位置服務(wù)不僅能為用戶的出行提供便利，在信息查詢、協(xié)作通信、道路監(jiān)測等方面也有廣泛應(yīng)用。例如，在車載自組網(wǎng)中，通過車輛的位置信息進(jìn)行提前預(yù)警，可以很大程度地減少車輛碰撞事故的發(fā)生[2]。對城市車輛的位置軌跡大數(shù)據(jù)進(jìn)行分析，可以準(zhǔn)確地預(yù)測交通動(dòng)態(tài)、預(yù)先采取措施緩解交通擁堵壓力、進(jìn)行道路規(guī)劃[3]。在無人機(jī)的通信網(wǎng)絡(luò)中，使用無人機(jī)的位置坐標(biāo)作為中繼選擇算法的狀態(tài)值，可以降低通信鏈路的中斷概率，保證協(xié)作通信的順利進(jìn)行[4]。用戶在請求LBS服務(wù)時(shí)需要將個(gè)人的位置信息上傳給位置服務(wù)提供商(location-based service provider，LSP)，在提交信息的過程中存在數(shù)據(jù)采集、網(wǎng)絡(luò)傳輸?shù)榷嘀仉[私泄露隱患，如果不能充分保護(hù)用戶的軌跡隱私,用戶的個(gè)人私密信息可能會(huì)隨著軌跡數(shù)據(jù)的發(fā)布而被泄露[5]。

隨著對軌跡隱私的深入研究，基于差分隱私技術(shù)的保護(hù)方法逐漸成為軌跡隱私保護(hù)的熱點(diǎn)。差分隱私概念由Dwork等[6]于2006年提出，通過添加少量高斯或指數(shù)分布的隨機(jī)噪聲來擾動(dòng)數(shù)據(jù)庫查詢的真實(shí)結(jié)果。在差分隱私的應(yīng)用場景中，往往假設(shè)攻擊者獲得了最大的背景知識，因此無須針對特定場景對攻擊者的背景知識進(jìn)行假設(shè)[7]，可以有效抵御背景知識攻擊。文獻(xiàn)[8]提出了一種基于Geohash編碼的k-匿名位置隱私保護(hù)方案，通過Geohash編碼的性質(zhì)，將用戶的真實(shí)位置泛化到一個(gè)區(qū)間區(qū)域，并通過反向檢索的方式構(gòu)造k-匿名區(qū)域集合。文獻(xiàn)[9]結(jié)合聚類的Mix-zone算法與差分隱私技術(shù)，提出一種軌跡隱私保護(hù)服務(wù)推薦模型，在聚類簇中進(jìn)行基于用戶屬性的秘密安全計(jì)算，并且根據(jù)用戶的不同隱私需求，選擇適當(dāng)?shù)碾[私預(yù)算來保護(hù)用戶的軌跡安全。文獻(xiàn)[10]為了解決背景知識攻擊對用戶軌跡隱私的影響，結(jié)合地理不可區(qū)分性的概念，使用拉普拉斯機(jī)制添加噪聲，以滿足差分隱私的需求，同時(shí)構(gòu)造數(shù)據(jù)映射函數(shù)以提高發(fā)布數(shù)據(jù)的可用性。文獻(xiàn)[11]將機(jī)器學(xué)習(xí)算法應(yīng)用到聚類分析中，使用改進(jìn)的K-means算法對軌跡進(jìn)行聚類分析，通過多序列對比增強(qiáng)聚類效果，同時(shí)建立基于機(jī)器學(xué)習(xí)的匿名化框架對用戶的時(shí)空軌跡隱私進(jìn)行保護(hù)。文獻(xiàn)[12]提出了一種基于馬爾科夫模型的差分隱私位置保護(hù)方法，利用馬爾可夫模型生成的狀態(tài)轉(zhuǎn)移概率矩陣來預(yù)測用戶的移動(dòng)位置，同時(shí)利用差分隱私技術(shù)構(gòu)建位置隱私樹，根據(jù)用戶的位置信息和檢索難度來分配隱私保護(hù)預(yù)算。

但目前的軌跡隱私保護(hù)機(jī)制大都存在以下問題。

(1)注重在空間上對單個(gè)軌跡點(diǎn)的隱私進(jìn)行保護(hù)，以達(dá)到整體軌跡的安全性，未考慮軌跡點(diǎn)在時(shí)間序列上的相關(guān)性，導(dǎo)致選取或生成的軌跡點(diǎn)可用性較差，難以抵御同質(zhì)攻擊。

(2)采用的聚類算法局限性較大，對數(shù)據(jù)類型要求較高且容易受到噪聲點(diǎn)的影響，同一個(gè)聚類簇中的數(shù)據(jù)差別較大，不利于干擾軌跡的生成。

(3)在隱私預(yù)算的選擇上考慮到了用戶的實(shí)際需要與軌跡隱私的安全性，但是忽略了隱私預(yù)算對軌跡相似性的影響。

(4)通過添加拉普拉斯噪聲來達(dá)到差分隱私保護(hù)的目的，但添加噪聲后的位置信息與用戶真實(shí)位置間的誤差分析不夠全面。

針對上述問題，現(xiàn)提出一種基于密度的噪聲應(yīng)用空間聚類(density based spatial clustering of application with noise, DBSCAN)的差分隱私軌跡保護(hù)機(jī)制。首先，利用DBSCAN[12]算法聚類生成等價(jià)簇，對任意形狀的數(shù)據(jù)集進(jìn)行聚類且排除噪聲點(diǎn)的干擾；其次，通過網(wǎng)格劃分的方法劃分用戶所在區(qū)域，根據(jù)用戶歷史活動(dòng)軌跡得到各區(qū)域的位置轉(zhuǎn)移概率，具有相似概率區(qū)域內(nèi)的用戶在時(shí)間序列上的具有相關(guān)性；最后，利用線性規(guī)劃的方法求得滿足軌跡相似性與差分隱私約束的隱私預(yù)算，確保生成的干擾軌跡具有較高的可用性。

1 預(yù)備知識

1.1 差分隱私

差分隱私模型的基本思想是在原始數(shù)據(jù)集或在數(shù)據(jù)傳輸?shù)倪^程中添加噪聲來達(dá)到保護(hù)數(shù)據(jù)隱私屬性的目的。差分隱私可大致分為兩大類[6]：中心化差分隱私和本地化差分隱私。如圖1所示，中心化差分隱私是將用戶數(shù)據(jù)集中在一個(gè)可信的中心服務(wù)器上，通過中心服務(wù)器對用戶的數(shù)據(jù)集進(jìn)行加噪處理，使其滿足差分隱私的需求，所以數(shù)據(jù)集的安全性很大程度上依賴于中心服務(wù)器的可靠性。從圖2可以看出本地化差分隱私是將數(shù)據(jù)處理的過程交由移動(dòng)端完成，依靠用戶端對敏感信息進(jìn)行保護(hù)。

定義一相鄰數(shù)據(jù)集：假設(shè)有兩個(gè)數(shù)據(jù)集D和D′,這兩個(gè)數(shù)據(jù)集中的數(shù)據(jù)只有一條不同，其余數(shù)據(jù)均相同，則稱其為相鄰數(shù)據(jù)集。

圖1 中心化差分隱私模型Fig.1 Centered differential privacy model

圖2 本地化差分隱私模型Fig.2 Localizes the differential privacy model

定義二差分隱私：若算法A是運(yùn)行在服務(wù)器上的算法，在相鄰數(shù)據(jù)集D和D′上的任意輸出結(jié)果O若滿足式(1)，則說明算法A滿足ε-差分隱私，表達(dá)式為

Pr[A(D)=O]≤eεPr[A(D′)=O]

(1)

定義三隱私保護(hù)預(yù)算：隱私保護(hù)預(yù)算ε用來調(diào)整兩個(gè)相似數(shù)據(jù)集在算法A中獲得相同輸出概率的比值，它體現(xiàn)了算法A所能提供的隱私保護(hù)強(qiáng)度。ε越小表明隱私保護(hù)強(qiáng)度越高，當(dāng)ε=0時(shí)，隱私保護(hù)強(qiáng)度最高，此時(shí)輸入任意的相鄰數(shù)據(jù)集，都將輸出相同的結(jié)果。但ε并不是越小越好，具體的數(shù)值應(yīng)當(dāng)根據(jù)用戶的實(shí)際需要合理設(shè)置，以達(dá)到安全性與可用性的平衡。

1.2 DBSCAN聚類算法

目前有很多聚類算法被應(yīng)用于軌跡隱私保護(hù)中，比如K-means算法[5,14]，基于網(wǎng)格的多分辨率聚類(statistical information grid，STING)算法[15]等。K-means算法對數(shù)據(jù)集的要求較高，僅適用于對凸樣本集進(jìn)行聚類分析；STING算法是一種基于多層次網(wǎng)格劃分的聚類方法，這種聚類方法的精度易受網(wǎng)格最底層空間的粒度影響。DBSCAN算法是一種基于密度的聚類方法，在使用DBSCAN算法進(jìn)行聚類分析前需要確定兩個(gè)參數(shù)，一個(gè)是鄰近區(qū)域的半徑(EPS)，表示以定點(diǎn)為中心點(diǎn)的圓形鄰域范圍；一個(gè)是鄰近區(qū)域內(nèi)至少包含點(diǎn)的個(gè)數(shù)(min points)。由于DBSCAN算法是基于數(shù)據(jù)推測聚類的數(shù)目，所以不需要事先確定聚類簇的數(shù)量，并且可以針對任意形狀產(chǎn)生聚類。

1.3 軌跡相似性

軌跡相似性是分析移動(dòng)對象的一個(gè)重要指標(biāo)，用來表示兩條軌跡之間的相似程度。衡量軌跡相似性的方法有很多，常用的有歐式距離[16]、動(dòng)態(tài)時(shí)間歸整(dynamic time warping, DTW)[17]、最長公共子序列(the longest common subsequence, LCSS)[18]等基于點(diǎn)距離的衡量方法。由于目前的軌跡隱私保護(hù)方法大都注重對用戶空間距離上的隱私保護(hù)，而對軌跡形狀相似性的考慮并不多，因此引入Fréchet距離作為衡量軌跡形狀相似性的方法。

假設(shè)用戶的真實(shí)運(yùn)動(dòng)軌跡為A且長度為M，產(chǎn)生的虛假軌跡為B且長度為N。兩者運(yùn)動(dòng)位置的關(guān)系可以用一個(gè)連續(xù)遞增函數(shù)F來描述。具體的表達(dá)式為

F(A,B)=infα,β,t∈[0,1]max(d{A[α(t)],

B[β(t)]})

(2)

式(2)中：t為時(shí)間變量；α(t)和β(t)為運(yùn)動(dòng)位置描述函數(shù)；A[α(t)]、B[β(t)]分別為兩條軌跡在t時(shí)刻的測量點(diǎn)；d{A[α(t)],B[β(t)]}為測量點(diǎn)之間的歐氏距離。t以一定的間隔遍歷時(shí)間區(qū)間后，得到A、B軌跡采樣對之間的歐氏距離最大值max(d{A[α(t)],B[β(t)]})即為兩條軌跡的Fréchet距離。作為一種度量軌跡相似性的方式，F(xiàn)réchet距離的大小量化了軌跡間的相似度，距離越小說明兩條軌跡越相近，反之，則說明軌跡相差較遠(yuǎn)。離散Fréchet距離是連續(xù)Fréchet距離的近似，當(dāng)軌跡上選取的采樣點(diǎn)足夠密集時(shí)，離散Fréchet距離就近似等于連續(xù)Fréchet距離，也使用離散Fréchet距離作為評價(jià)軌跡相似性的標(biāo)準(zhǔn)。

2 DP-DBS模型

提出了一種基于DBSCAN聚類算法的軌跡差分隱私保護(hù)模型(differential privacy protection model based on DBSCAN algorithm, DP-DBS)。如圖3所示，首先通過對軌跡數(shù)據(jù)聚類分析得到位置等價(jià)類，而后根據(jù)歷史位置信息計(jì)算各區(qū)域的位置轉(zhuǎn)移概率，確定隱私保護(hù)預(yù)算，找到滿足差分隱私的位置區(qū)域集合，最后在該區(qū)域中找到Fréchet距離最近的擾動(dòng)點(diǎn)集合，得到干擾軌跡。

圖3 DP-DBS模型框架Fig.3 DP-DBS model framework

2.1 聚類分析

在進(jìn)行聚類分析前，首先要進(jìn)行坐標(biāo)的平面投影處理。使用ARCGIS軟件將經(jīng)緯度坐標(biāo)轉(zhuǎn)換成笛卡爾體系下的平面坐標(biāo)，由于數(shù)據(jù)集中的數(shù)據(jù)比較密集，轉(zhuǎn)換后的坐標(biāo)集中在某個(gè)固定區(qū)間內(nèi)，為了在不影響聚類的結(jié)果的前提下減小聚類分析的計(jì)算開銷，需要先對數(shù)據(jù)進(jìn)行縮小處理，再使用DBSCAN算法進(jìn)行聚類。聚類開始時(shí)，選擇一個(gè)沒有類別的核心對象作為種子，然后找到這個(gè)對象所有密度可達(dá)的樣本集合，形成一個(gè)聚類簇，接著選擇另一個(gè)沒有類別的核心對象繼續(xù)該過程，直至所有核心對象都有類別時(shí)完成聚類過程。一個(gè)聚類簇相當(dāng)于一個(gè)等價(jià)類，用戶在等價(jià)類中選擇軌跡相似點(diǎn)，可以提高軌跡隱私的安全性。

2.2 位置轉(zhuǎn)移概率矩陣

位置轉(zhuǎn)移概率是指用戶從當(dāng)前位置轉(zhuǎn)移到另外一個(gè)位置的概率，可以從用戶移動(dòng)的歷史記錄中得到。為了模擬用戶的位置移動(dòng)相關(guān)性，通過一階馬爾可夫鏈描述用戶的真實(shí)活動(dòng)軌跡，將用戶的活動(dòng)軌跡看作是馬爾可夫過程，使用概率轉(zhuǎn)移矩陣M可以更加清晰地描述位置相關(guān)性。M是一個(gè)二維的矩陣，矩陣中的元素mij表示用戶從區(qū)域i轉(zhuǎn)移到區(qū)域j的概率，統(tǒng)計(jì)網(wǎng)格內(nèi)的歷史軌跡數(shù)據(jù)，得到位置轉(zhuǎn)移概率矩陣。

網(wǎng)格劃分的大小也與概率統(tǒng)計(jì)的結(jié)果有著很大的關(guān)系。將用戶所處地區(qū)劃分成邊長為50 m的正方形區(qū)域，如圖4所示，網(wǎng)格編號自左至右，從上到下依次增大。根據(jù)用戶所處的地理位置坐標(biāo)確定其區(qū)域編號，依托用戶的軌跡得到區(qū)域編號序列。根據(jù)序列編號序列形成一階馬爾可夫鏈，從而生成概率轉(zhuǎn)移矩陣M。

圖4 網(wǎng)格劃分示意圖Fig.4 Grid division diagram

2.3 隱私保護(hù)預(yù)算

隱私保護(hù)預(yù)算ε的大小與軌跡干擾點(diǎn)的選擇息息相關(guān)，ε越小，對隱私的保護(hù)程度要求越嚴(yán)格，生成的干擾軌跡可用性就越低；而ε變大，生成的干擾軌跡可用性會(huì)提高，但對用戶的隱私保護(hù)程度又會(huì)隨之降低。為了平衡軌跡可用性與隱私保護(hù)預(yù)算之間的關(guān)系，對二者分配不同的權(quán)重值以達(dá)到生成合理的干擾軌跡的目的。假設(shè)σ函數(shù)為平衡軌跡相似性與隱私預(yù)算的目標(biāo)函數(shù)，ω0與ω1為二者分配的權(quán)重，有

(3)

s.t.

0≤ε≤1

(4)

ω0+ω1=1

(5)

(6)

(7)

2.4 生成干擾軌跡

在確定了隱私預(yù)算的前提下，需要優(yōu)先考慮Fréchet距離對位點(diǎn)選擇的影響。將用戶的真實(shí)位置設(shè)置為核心點(diǎn)，通過DBSCAN算法進(jìn)行聚類，去除噪聲點(diǎn)的影響并縮小干擾點(diǎn)的選擇范圍。在等價(jià)類中選擇位置干擾點(diǎn)時(shí)，要根據(jù)差分隱私的定義選擇合適的位置區(qū)域。由于處在相同區(qū)域內(nèi)的用戶位置轉(zhuǎn)移概率也是相同的，因此需要計(jì)算Fréchet距離，選擇與用戶真實(shí)位置距離最小的位點(diǎn)，最后以時(shí)間序列聯(lián)結(jié)這些位點(diǎn)形成干擾軌跡。

3 實(shí)驗(yàn)分析

使用Geolife數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，該GPS軌跡數(shù)據(jù)集收集了182名用戶2007年4月—2012年8月的活動(dòng)路線，記錄了用戶廣泛的戶外活動(dòng)，如購物、觀光、徒步旅行等，一共包含17 621條軌跡信息，這些軌跡都按時(shí)間序列進(jìn)行存儲(chǔ)。

實(shí)驗(yàn)環(huán)境如下：Intel i7-7700K 3.6 GHz, 8 GB內(nèi)存，Microsoft Windows 10操作系統(tǒng)，模型算法均在Pycharm2019下實(shí)現(xiàn)。

實(shí)驗(yàn)1選取了數(shù)據(jù)集中的部分用戶數(shù)據(jù)，分別使用K-means與DBSCAN兩種方法對其進(jìn)行聚類分析。由于DBSCAN算法是基于密度的聚類算法，不需要預(yù)先設(shè)定聚類中心的個(gè)數(shù)，而K-means則需要先設(shè)定聚類中心，分別取聚類中心為10、20、30，對比數(shù)據(jù)集中的軌跡數(shù)量為500、1 000、1 500、2 000時(shí)聚類所需的時(shí)間。如圖5所示，隨著數(shù)據(jù)集的增大，兩種聚類算法所需時(shí)間均隨之增長，在選取較小的k值時(shí)，DBSCAN所需的時(shí)間要比K-means所需的時(shí)間長，但是隨著聚類中心k的增加，DBSCAN聚類算法的時(shí)間優(yōu)勢就顯現(xiàn)出來。當(dāng)k>40時(shí)，DBSCAN算法的效率就高于K-means算法，并且隨著實(shí)驗(yàn)數(shù)據(jù)的增大這種優(yōu)勢也更加明顯。

圖5 聚類效率比較圖Fig.5 Cluster efficiency comparison

實(shí)驗(yàn)2比較了豪斯多夫距離與弗朗明歇距離的運(yùn)行時(shí)間。如圖6所示，通過改變選取的軌跡點(diǎn)數(shù)量，對比二者的時(shí)間開銷，可明顯看出，使用Fréchet距離作為衡量指標(biāo)運(yùn)行時(shí)間遠(yuǎn)小于使用豪斯多夫距離所需的時(shí)間，因此選擇Fréchet距離作為衡量軌跡相似性的標(biāo)準(zhǔn)具有明顯優(yōu)勢。

實(shí)驗(yàn)3通過改變?chǔ)诺拇笮∮^察干擾軌跡與真實(shí)軌跡的Fréchet距離，由圖7可以看出，真實(shí)軌跡與干擾軌跡的Fréchet距離隨著ε的增大而減小，這是因?yàn)棣旁酱?，?shù)據(jù)集中可選擇的鄰近位置就越多，易得到在Fréchet距離上更加接近真實(shí)軌跡的位置點(diǎn)。再綜合考慮隱私預(yù)算與軌跡相似性，分別取權(quán)重(ω0,ω1)為(0.5，0.5)、(0.25，0.75)、(0.75，0.25)進(jìn)行目標(biāo)函數(shù)的計(jì)算。圖8是隱私預(yù)算分別為0.1、0.2、0.3時(shí)不同權(quán)重下目標(biāo)函數(shù)的變化，可以看出，在不同的隱私預(yù)算下，當(dāng)(ω0,ω1)的取值為(0.25，0.75)時(shí)，目標(biāo)函數(shù)的值最小，而在確定權(quán)重后，目標(biāo)函數(shù)的值隨著隱私預(yù)算的增大而增加。因此，方案可以根據(jù)用戶的實(shí)際需要，合理設(shè)置權(quán)重和隱私預(yù)算，確保生成的干擾軌跡具有較好的可用性。

圖6 運(yùn)行時(shí)間對比Fig.6 Comparison of the running time

圖7 隱私預(yù)算對軌跡相似性的影響Fig.7 The impact of the privacy budget on track similarity

圖8 隱私預(yù)算對目標(biāo)函數(shù)的影響Fig.8 The impact of privacy budget on the objective function

4 結(jié)論

針對位置隱私保護(hù)中的軌跡隱私問題，構(gòu)建了一種滿足時(shí)序性的差分隱私安全的軌跡保護(hù)模型。采用DBSCAN算法對數(shù)據(jù)集中的位置數(shù)據(jù)進(jìn)行聚類分析，并通過網(wǎng)格劃分，計(jì)算各網(wǎng)格內(nèi)用戶的位置轉(zhuǎn)移概率，使用線性回歸方法平衡隱私預(yù)算與軌跡可用性的關(guān)系，最終確定軌跡相似點(diǎn)，以時(shí)間序列連結(jié)軌跡點(diǎn)形成具有形狀相似性的干擾軌跡。仿真實(shí)驗(yàn)表明在保證隱私的前提下，方案減小了數(shù)據(jù)集中噪聲點(diǎn)的影響，同時(shí)提高聚類效率和干擾軌跡的可用性。