融合聚類與差分隱私的位置隱私方法研究

張偉媛　湯文兵　陳彥杰

摘 要：移動計算設備的快速發(fā)展導致了基于位置的服務（LBS）得到了各領域的應用，但同時給用戶隱私安全帶來威脅。針對用戶位置信息上傳共享第三方的問題，提出了融合聚類與差分隱私的位置保護方案。首先，根據(jù)位置信息的密集程度將周邊位置點進行排序劃分，采用k-means聚類對其進行泛化處理；在滿足地理不可區(qū)分性的前提下通過平面拉普拉斯機制對簇中心進行加噪，得到每個位置點的擾動位置，進而保護位置隱私。實驗結果證明，在保障位置隱私安全的前提下，本文算法具有更高的數(shù)據(jù)利用率。

關鍵詞：差分隱私；k-means聚類；位置隱私；基于位置的服務

中圖分類號：TP309.2? 文獻標識碼：A? 文章編號：1673-260X（2023）11-0001-05

1 引言

傳感器和移動設備的快速發(fā)展在市場上為用戶提供了廣泛的選擇，便利了用戶的生活。然而，這些設備的處理和存儲能力會導致用戶一些隱私信息的泄漏。例如使用基于位置的服務LBS會獲取用戶的位置信息[1]。用戶將準確的位置信息上傳到LBS以獲得相應的服務，但上傳未經(jīng)處理的位置數(shù)據(jù)將直接導致用戶隱私信息泄露。訂外賣、外出交通或與其他用戶會面，必須將他們的位置發(fā)布到LBS服務器，這些被收集的位置信息將有可能會暴露有關用戶的一些基本信息，利用這些信息，廣告商可以推送廣告，犯罪分子也可能進行犯罪活動[2]。用戶一些敏感位置信息的泄露可能對其造成大量損失，保護用戶的信息安全，建立安全有效的模型已經(jīng)成為當前研究的重點。

關于LBS隱私保護方案國內外已經(jīng)有大量研究成果[3-6]。Song等人提出了一種基于雙線性配對理論和k-匿名性的改進隱私保護方案，根據(jù)位置信息選擇最佳假位置，從而實現(xiàn)隱私保護[7]。隨后，Zhang等人提出了一種新的基于地理語義的位置隱私保護方法，同時滿足k-匿名性，其中使用最大和最小距離多中心聚類算法構建候選集，并根據(jù)其語義相似性生成虛擬位置結果集[8]。然而l-多樣性和k-匿名的概念受到數(shù)據(jù)分布和背景知識攻擊的極大限制，因此隱私保護的程度無法得到很好的保證。除上述方法外，LBS隱私保護結構主要包括位置樹結構、馬爾可夫模型和聚類。位置樹的主要思想是根據(jù)一定的規(guī)則構造樹結構，引用前綴樹和差分隱私來保護軌跡數(shù)據(jù)隱私，樹的節(jié)點用于存儲軌跡段[9]。馬爾可夫模型主要用于模擬用戶實際位置之間的時間相關性，并根據(jù)每個位置的轉移概率預測下一個可能的位置[10]。聚類可以展現(xiàn)用戶在一定時間內的活動規(guī)則，去除訪問頻率較低的位置，因此具有很高的靈活性。Tareqd等人提出了一種基于密度網(wǎng)格的在線數(shù)據(jù)流聚類方法，采用基于網(wǎng)格的方法來減少距離函數(shù)的調用次數(shù)，從而提高聚類質量[11]。Sabarish等人提出了一種基于圖形的軌跡數(shù)據(jù)表示模型，使用基于邊和頂點的測量方法計算軌跡之間的相似度，并基于路徑對相似軌跡進行聚類和識別從而對位置隱私提供了隱私保障[12]。

為了最大化查詢結果的準確性，提高算法的效率，在滿足差分隱私的條件下本文提出一種融合聚類與差分隱私的位置隱私算法。將差分隱私與k-means聚類算法相結合，選取聚類集合的質心點，使用平面拉普拉斯機制對其進行處理得到擾動位置，并使用擾動位置代替原始位置進行查詢。本文的貢獻有兩個方面。

（1）本文結合k-means聚類和差分隱私提出了可以有效保護用戶位置隱私的機制。

（2）使用真實數(shù)據(jù)集測試所提出方案的效率和有效性，驗證本文提出的算法優(yōu)于其他算法，數(shù)據(jù)可用性得到了較好的提高。

2 定義及相關概念

2.1 差分隱私

2.1.1 差分隱私定義

2.1.2 隱私保護預算

參數(shù)ε稱為隱私預算。如公式（1）所示，較小的ε會使算法M生成的查詢結果的概率分布在一對相鄰的數(shù)據(jù)集上越相似，攻擊者更難判斷數(shù)據(jù)集中是否存在某個元素。隱私保護的程度會更高。因此，ε的值通常要與具體的要求結合，以完成結果的隱私性和利用率之間的平衡。

2.1.3 敏感度

2.2 地理不可區(qū)分性

差分隱私通常用于數(shù)據(jù)聚合問題中的隱私保護，使攻擊者無法確定元素是否屬于某個數(shù)據(jù)集。考慮到某一地理空間中特定位置數(shù)據(jù)點的隱私保護，引用地理不可區(qū)分的機制，此機制擴展差分隱私到地理位置數(shù)據(jù)，并將差分隱私中相鄰數(shù)據(jù)集的概念轉換為兩個地理上接近的位置。當兩個相鄰位置彼此靠近時，它們生成相同查詢位置的概率相似。因此，攻擊者無法根據(jù)用戶提交的查詢位置來確定用戶的真實位置。具體定義如下：

其中，參數(shù)ε是單位距離的隱私預算，εr代表半徑為r的任意圓內的隱私預算。從公式（3）中可以看出，εr越小，同一輸出位置的概率分布越相似，攻擊者就越難判斷用戶的真實位置，隱私保護程度越高。同樣，通過在真實位置點上添加拉普拉斯噪聲來實現(xiàn)地理上的不可辨性，用戶的真實位置被保護在一個半徑為r的圓內。

2.3 實現(xiàn)機制

2.4 k-means聚類

3 算法設計

針對位置隱私保護機制數(shù)據(jù)利用率低問題，本文將k-means聚類加入差分隱私位置保護機制中。該機制能夠很好地保護單個位置的隱私，并通過k-means算法和差分隱私性使擾動位置與真實位置相似，從而提高位置數(shù)據(jù)的可用性。其基本思想如下，對于每個位置點，將距離小于r的興趣點劃入該位置所在的聚類簇。該算法使用聚類中心點來代表一定距離內的用戶活動區(qū)域，區(qū)域內的其他位置點被移除，以避免位置冗余。最后，為了進一步保護用戶的隱私，原始位置被質心所取代[14]。

3.1 位置點預處理模塊

3.2 位置數(shù)據(jù)聚類模塊

3.3 算法安全性分析

4 實例分析

4.1 實驗設置

實驗所用硬件環(huán)境為11th Gen Intel（R） Core（TM） i5 2.40GHz，16GB內存，使用python編程語言實現(xiàn)，操作系統(tǒng)平臺為Windows10。使用的數(shù)據(jù)集為Gowalla，一個收集位置數(shù)據(jù)的社交網(wǎng)絡，允許用戶通過簽到來分享他們的位置。該數(shù)據(jù)集使用公共API收集信息，具有196591個站點和950327個域，并在2009年2月至2010年10月時間范圍內收集了用戶的6442890次簽到。

4.2 實驗分析

本文采用MSE衡量數(shù)據(jù)可用性，對比了單純使用差分隱私算法的數(shù)據(jù)可用性，分析了隱私預算ε對數(shù)據(jù)利用率的影響，其中誤差越低，代表數(shù)據(jù)可用性越高，隱私預算ε對算法誤差的影響分析如圖1所示。

根據(jù)拉普拉斯概率密度函數(shù)推斷，隱私保護程度隨ε的增加而降低，該實驗結果也反映了這一理論。而且從實驗結果中不難看出本文算法的隱私保護程度較好于傳統(tǒng)的差分隱私算法，這是由于k-means聚類生成了一個質心，所有位置都被一個唯一的質心替換，因此本文的隱私保護程度更好，數(shù)據(jù)可用性更高。

圖2則分析了待保護位置的數(shù)量N對隱私保護程度的影響，從實驗結果中可以看出隱私保護程度隨著待保護位置數(shù)量N的減少而增加。N越大，隱私保護程度越差。同樣，對比傳統(tǒng)的差分隱私方法，可以看出本文算法的數(shù)據(jù)可用性更高。

5 總結

本文針對位置數(shù)據(jù)中的隱私問題提出了一種新的解決方案，設計了一個融合k-means聚類與差分隱私的算法來干擾用戶的位置數(shù)據(jù)。通過理論分析與實驗證明，本文算法能夠在有效保護用戶數(shù)據(jù)安全性的同時提高數(shù)據(jù)的利用率。

參考文獻：

〔1〕姜海洋，曾劍秋，韓可，等.5G環(huán)境下移動用戶位置隱私保護方法研究[J].北京理工大學學報，2021， 41（01）：84-92.

〔2〕楊洋，王汝傳.增強現(xiàn)實中基于位置安全性的LBS位置隱私保護方法[J].計算機應用，2020，40（05）：1364-1368.

〔3〕XIONG J B， REN J， CHEN L， et al. Enhancing privacy and availability for data clustering in intelligent electrical service of IoT， IEEE Internet of Things Journal， 2019， 6（02）：1530-1540.

〔4〕XIONG J B， MA R， CHEN L， et al. A personalized privacy protection framework for mobile crowdsensing in IIoT， IEEE Transactions on Industrial Informatics， 2020， 16（06）：4231-4241.

〔5〕HE J S， Du J H， ZHU N F. Research on k-anonymity Algorithm for Personalized Quasi-identifier Attributes [J]. Information network security， 2020， 20（10）：19-26.

〔6〕LIU Q， YU J， HAN J， et al. Differentially private and utility-aware publication of trajectory data[J]. Expert Systems with Applications， 2021， 180（07）：115120.

〔7〕SONG C， ZHANG YD， WANG L， et al. Research on k-anonymity privacy protection scheme based on bilinear pairings [J]. The Journal of China Universities of Posts and Telecommunications， 2018， 25（05）：12-19.

〔8〕ZHANG Y B， ZHANG Q Y， LI Z Y， et al. A k-anonymous Location Privacy Protection Method of Dummy Based on Geographical Semantics [J]. International Journal of Network Security， 2019， 21（06）：937-946.

〔9〕ZHAO X， PI D， CHEN J. Novel trajectory privacy-preserving method based on prefix tree using differential privacy [J]. Knowledge-Based Systems， 2020， 198（05）：105940.

〔10〕YUAN T A， MMK A， MAR A， et al. A privacy preserving location service for cloud-of-things system-Science Direct [J]. Journal of Parallel and Distributed Computing， 2019， 123： 215-222.

〔11〕TAREQ M， SUNDARARAJAN E A， MOHD M， et al. Online clustering of evolving data streams using a density grid-based method.IEEE Access 2020， 8， 166472-166490.

〔12〕SABARISH BA， KARTHI R， KUMAR T G. Graph Similarity-based Hierarchical Clustering of Trajectory Data [J]. Procedia Computer Science， 2020， 171：32-41.

〔13〕SINAGA K P， YANG M S. Unsupervised K-means clustering algorithm[J]. IEEE access， 2020， 8： 80716-80727.

〔14〕任曉宇.基于差分隱私的位置隱私保護技術研究[D].山西師范大學，2021.