一種改進的差分隱私聚類位置保護方法

林 靜，胡德敏，王揆豪

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

0 引言

在信息化時代，移動終端的位置服務應用廣泛，如簽到、導航、線路跟蹤等功能。為了增加搜索功能以最大限度地提高效益，基于位置服務（Location Based Service，LBS）提供商收集了大量用戶定位信息，以形成用戶的軌跡數據，對這些數據進行分析優化從而給出興趣點推薦、位置共享服務等［1］?；谖恢玫臄祿l布便捷了人們生活，但是也存在個人隱私信息泄露的風險［2］。

1 相關工作

傳統的位置保護方法有抑制法、數據加密法、泛化法、數據擾動法［3］等。

抑制法是一種基于先驗知識，通過抑制敏感背景信息來保護用戶隱私的方法［4］。然而，在需要刪除太多數據的情況下，信息會大量丟失，導致數據查詢服務質量下降。

數據加密法是利用加密技術對數據信息加密，以保護數據隱私［3］。雖然加密后真實數據很難泄露，但嚴重破壞了數據可用性且耗時較長。

泛化法由點到面地將數據點或整個位置軌跡進行轉換，以達到保護用戶位置隱私的目的［5］。由于泛化法需要加入很多輔助數據，會拉低算法的運行效率，且數據冗余過多。

為了給真實數據增加噪點、擾亂其真實性，一般采用數據擾動法，但這種方法通常是將偽造的位置數據來代替原有數據集中的真實位置數據［6］。如Feng 等［7］提出Vurtual Avatar 軌跡隱私保護方案，用擾動的數據點對真實的位置點進行干擾。計算量小、實現簡單是假數據法的優點，但是添加過多假數據會導致查詢結果不可靠。

差分隱私保護方法不需要攻擊者的背景知識，對于只差一條信息記錄的兩個數據集，查詢他們的概率是非常接近的。即使攻擊者知道除了某個記錄外的所有敏感特性，也無法推定該記錄中的任何重要信息，這降低了隱私泄露的風險。文獻［8］提出通過將拉普拉斯噪聲添加到實際位置來保護差分隱私的方法，但不能很好地適用于移動環境，噪聲的疊加會影響數據的可用性以及查詢結果的真實性；文獻［9］將差分隱私與K-means 算法相結合，在拉普拉斯噪聲添加到該組中心點獲得干擾數據之前，通過合并位置點產生泛化效應，從而達到保護位置隱私目的。但該方法在位置點范圍規模較大、離散程度高的情況下適用性不好；針對上述問題，文獻［10］提出了UG 網格劃分法，將空間數據集劃分為多個大小相同的網格，并向其加入拉普拉斯噪聲。但對于分布不均的數據集來說，網格大小相同，對應每個網格密度值就差別過大，加入噪聲后虛擬位置點并不能很好地代表真實位置點；文獻［11］提出基于差分隱私的混合位置保護方法，該方法將隨機噪聲添加到離散點，使用K-means 將噪聲添加到非離散點泛化后的中心點。但在離散點直接添加噪聲會導致噪音數據過多，誤差變大。對于非離散點使用K-means 方法聚類，選取不同的初始聚類中心會對結果產生較大影響，若存在異常點也會導致均值偏離嚴重，數據的可用性降低［12］。

現有的差分隱私位置保護方法存在一些問題：①如何在保障使用者隱私的同時減少噪音影響所導致的錯誤；②位置點數據集過大，如果采用聚類的方法則存在離散點敏感，盲目選擇初始中心點會導致聚類結果不理想等問題。由于位置點之間的相關性，對每個真實位置獨立添加噪聲會導致噪音疊加，直接保護全部的數據集又會大大降低數據的可用性［13］。所以，合理設計隱私保護機制至關重要。

本文基于DPk-means 算法提出DPK-MO 算法，引入鄰接密度和最小誤差平方和來判定初始中心點，并始終選取樣本誤差平方和最小的點作為中心再聚類，減少了由于隨機選取初始聚類中心點而對后期結果產生的誤差。為避免聚類后離散值對聚類有效性的影響，再對聚類后的集群剔除離散點，合并密度小的聚類集，最后合理加入符合差分隱私的拉普拉斯噪聲來得到虛擬位置從而減少隱私消耗，在保護用戶隱私的前提下減少噪聲數據帶來的誤差。

2 改進方法

2.1 基本定義

定義1差分隱私。給定一個算法K，若對于任意的兄弟數據集T1和T2，T1、T2里面只相差一個記錄，則任意的輸出S∈Range(k)滿足［14］：

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

定義2全局敏感度。假設有函數f：D→Rd，Df：D→Rd，D 是一個數據集，輸入為一個數據集，輸出為一個dd 維向量。對于任意兩個臨近的數據集DD 和D′D′，有：

‖表示曼哈頓距離，也可以是1-范數，定義為：

稱為函數ff 的全局敏感度［15］。

定義3噪音機制。差分隱私中，拉普拉斯機制將根據拉普拉斯分布添加噪聲擾動數據［16］。設噪聲方差為，其中Q 為查詢函數：

若為輸出結果變化的最大值，那么概率密度分布如下：

定義4歐氏距離。歐幾里得距離：n 維空間中兩點之間的真實距離或者一個矢量的自然長度如下［17］：

定義5誤差平方和。樣本x 與樣本總平均值的偏差平方和是用來衡量樣本離散程度的重要指標，計算公式如下：

2.2 相關技術

2.2.1 Greedy DBSCAN 算法

Greedy DBSCAN 算法采用貪心算法思路保證每個步驟得到局部最優解，主要步驟如下：

（1）確定點p 半徑ε 后聚類。

其中，pk_nearest(i)表示與點pi最近的k 個點；d（）表示點間的歐氏距離，k 值在二維空間聚類中一般取4，其他情況可取數據集（n 為數據樣本總數，表示向下取整）；

（2）鄰域查詢。

（3）剔除離散噪聲。

（4）合并含有公共點的簇。

2.2.2 K-means++算法

K-means++是一種改進的K-means 算法，克服了初始聚類中心點的選取對于聚類結果的影響并改進分類結果的最終誤差［19］。中心節點選擇的思路是聚類中心點兩兩之間的相互距離盡可能地遠。

K-means++聚類算法選擇k 個聚類中心步驟如下：

（2）計算樣本與現有的聚類中心點間的最短距離（即與距離最近的聚類中心點的歐式距離），該距離用D（x）表示。計算每一樣本被選為下一個中心點的概率，新的聚類中心則為概率最高的樣本點。

（3）重復步驟（2），直到選擇了k 個聚類中心。

（4）劃分每個樣本Xi到距離其最近的聚類中心簇中。

2.2.3 拉普拉斯加噪

其中，Pi是類中的樣本數。

輸入隱私預算ε和聚類中心J，產生噪聲，滿足概率Pr（j（x，y），λ），其中Pr（j（x，y），λ）計算如下：

然后添加噪聲，在聚類中心J 中加入噪聲來擾亂攻擊者，通過判斷聚類中心在真實位置點的左/右方向，合理使用“+”/“-”運算。噪聲添加公式如下：

為中心點加入與密度呈正相關的噪音數據如圖1 所示（彩圖掃OSID 碼可見，下同）。

Fig.1 Adding Laplace noise data to the data set圖1 數據集加入拉普拉斯噪音數據

2.3 DPK-MO 算法

基于差分隱私的K-means 聚類算法（DPK-means）由于對離群點敏感，對初始中心點盲目選擇，往往劃分結果［21］不理想。為了降低初始中心點選取對聚類結果產生的影響，本文提出DPK-MO 算法。

DPK-MO 算法步驟如下：①選取初始中心點；②聚類后去離散值；③合并聚類集加噪。DPK-means 算法采用隨機選取初始中心點聚類，導致選取不同初始聚類中心對結果產生較大影響，若存在異常點也會導致均值嚴重偏離，數據的可用性降低。DPK-MO 算法引入鄰接密度和誤差平方和兩個標準來判定初始中心點，并始終選取樣本誤差平方和最小的點作為中心再聚類，減少了由于隨機選取初始聚類中心點而對后期結果產生的誤差。為避免聚類后的離散值引發與真實位置點偏離嚴重、數據可用性降低的問題，對聚類后的位置群剔除離散點。最后判斷密度閾值，合并聚類集，加入拉普拉斯噪聲得到虛擬位置，從而減少隱私消耗。

DPK-MO 算法步驟如下：

輸入：數據對象集D。

輸出：聚類結果集合Dres。

（1）使用Greedy DBSCAN 算法在數據集上運行得到初始化的中心點集C 以及個數k。

（2）計算C 中各中心點對應集合中的誤差平方和φ(Ck,Xk)，取最小誤差平方和φmin所對應的簇中心點Ck作為聚類初始點。

（3）以Ck為初始中心點，k 為目標集合數，執行Kmeans++算法。

（4）判斷φ(Ck,Xk)'與φmin的大小，如果φ(Ck,Xk)'小于φmin則對應的簇Dk不動，如果φ(Ck,Xk)'大于φmin，數據集D=D-Dk，再循環執行步驟（2）-（4），直到超過指定執行次數最大值。

（5）最終得到最優聚類集D’。

（6）對于用戶位置點聚類集D’，計算聚類簇位置點密度參數ui（i=1，2，…，n，位置點密度參數為聚類簇內位置點總數）。

（7）計算異常點最大數Nnum=ui*0.05。

（8）判斷每個類中的元素數目是否小于Nnum。如果小于Nnum則進行合并操作。

（10）將S(i,j)最小的兩個類別合并成為一個新的類，該類的聚類中心位置為：

式（14）中的ni和nj表示這兩類樣本的個數，新的聚類中心可以看作是這兩類樣本的加權和。如果其中一個類包含樣本數過多，則合成的新的類中心位置將更傾向于它。

（11）在新的聚類中心Cnew中加入噪聲，輸出差分隱私保護擾動后的數據集Dres。

算法流程如圖2 所示。

Fig.2 Algorithm flow圖2 算法流程

3 實驗結果與分析

本文使用Python 編程語言進行仿真實驗，分別從結果誤差、數據可用性兩個方面對比DPK-means 算法、DPKmeans++算法和本文提出的DPK-MO 算法進行分析，采用Geo-life 數據集進行數據預處理得到二維位置數據集。單機環境為：Inter（R）Core（TM）i7 CPU 3.7 GHz，8GB 內存，Window 10 64 位操作系統。

3.1 實驗結果誤差

采用實驗前后K-means 聚類質心距離Dis 來衡量實驗結果誤差。實驗前后質心變化越小，證明位置保護前后數據集劃分的范圍相差越小，越能反映真實數據。DPK-MO算法使用之前，對初始真實點位進行K-means 聚類，聚類后的質心用Ck表示。使用DPK-MO 算法后，對加噪后的數據點再進行K-means 聚類，聚類后的質心用Ck'表示。計算實驗先后質心歐式距離差Disk，距離越小代表位置保護前后數據相似性越高，可用性越大；反之，代表算法前后數據相似性不高，誤差較大，可用性較低，具體效果如圖3 所示。從圖3 可以看出，在隱私系數一定的條件下，改進后的算法誤差較經典的DPK-means 算法減少了近13%，隱私保護效果更好。

3.2 實驗數據可用性分析

分別對原始數據集進行DPK-means 算法、DPkmeans++算法聚類，結果都設為W，采用本文提出的DPKMO 算法所得結果設為W'。采用評價指標F-measure 評價DPK-MO 算法的可用性。F-measure 表示聚類結果與原始數據集的相似度，相似性越高，結果越接近1。設數據樣本集總數為n，用Wi表示W 中的任一簇，用W'i表示W'中的任一簇，定義ni記錄Wi和W'i中有多少相同的簇，定義P1表示ni占W 全部簇的比例，P2表示ni占W'全部簇的比例，則Fmeasure 為：

Fig.3 Error comparison of algorithm results圖3 算法結果誤差對比

Fig.4 Data availability comparison of algorithm F-measure圖4 算法F-measure 數據可用性對比

通過圖4 可以看出，本文提出的DPK-MO 算法在滿足ε 差分隱私要求的前提下能夠有效保護用戶的位置隱私。與經典DPK-means 算法相比，F-measure 值提高了近30%，表明在相同隱私預算ε 下數據可用性更高。

4 結語

針對現有的差分隱私K-means 算法中初始聚類中心點對結果的影響，為提高數據可用性，本文提出一種新的基于差分隱私的DPK-MO 算法。算法引入鄰接密度和最小誤差平方和來判定初始中心點，始終選取樣本誤差平方和最小的點作為中心再聚類，剔除離散點，合并聚類集，最后合理加入符合差分隱私的拉普拉斯噪聲，提升了聚類結果的準確性，在保護用戶隱私信息的同時提高了數據的可用性。后續計劃引入分布式系統來提升算法效率，進一步探索DPK-MO 算法在其它方面的應用。