基于密度的噪聲應用空間聚類算法的差分隱私軌跡保護機制

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

(1.武警工程大學密碼工程學院， 西安 710086； 2.武警部隊密碼與信息安全保密重點實驗室， 西安 710086)

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

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

但目前的軌跡隱私保護機制大都存在以下問題。

(1)注重在空間上對單個軌跡點的隱私進行保護，以達到整體軌跡的安全性，未考慮軌跡點在時間序列上的相關性，導致選取或生成的軌跡點可用性較差，難以抵御同質攻擊。

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

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

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

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

1 預備知識

1.1 差分隱私

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

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

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

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

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

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

(1)

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

1.2 DBSCAN聚類算法

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

1.3 軌跡相似性

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

假設用戶的真實運動軌跡為A且長度為M，產生的虛假軌跡為B且長度為N。兩者運動位置的關系可以用一個連續遞增函數F來描述。具體的表達式為

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

B[β(t)]})

(2)

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

2 DP-DBS模型

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

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

2.1 聚類分析

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

2.2 位置轉移概率矩陣

位置轉移概率是指用戶從當前位置轉移到另外一個位置的概率，可以從用戶移動的歷史記錄中得到。為了模擬用戶的位置移動相關性，通過一階馬爾可夫鏈描述用戶的真實活動軌跡，將用戶的活動軌跡看作是馬爾可夫過程，使用概率轉移矩陣M可以更加清晰地描述位置相關性。M是一個二維的矩陣，矩陣中的元素mij表示用戶從區域i轉移到區域j的概率，統計網格內的歷史軌跡數據，得到位置轉移概率矩陣。

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

圖4 網格劃分示意圖Fig.4 Grid division diagram

2.3 隱私保護預算

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

(3)

s.t.

0≤ε≤1

(4)

ω0+ω1=1

(5)

(6)

(7)

2.4 生成干擾軌跡

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

3 實驗分析

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

實驗環境如下：Intel i7-7700K 3.6 GHz, 8 GB內存，Microsoft Windows 10操作系統，模型算法均在Pycharm2019下實現。

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

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

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

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

圖6 運行時間對比Fig.6 Comparison of the running time

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

圖8 隱私預算對目標函數的影響Fig.8 The impact of privacy budget on the objective function

4 結論

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