林 靜，胡德敏，王揆豪

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

0 引言

在信息化時(shí)代，移動(dòng)終端的位置服務(wù)應(yīng)用廣泛，如簽到、導(dǎo)航、線(xiàn)路跟蹤等功能。為了增加搜索功能以最大限度地提高效益，基于位置服務(wù)（Location Based Service，LBS）提供商收集了大量用戶(hù)定位信息，以形成用戶(hù)的軌跡數(shù)據(jù)，對(duì)這些數(shù)據(jù)進(jìn)行分析優(yōu)化從而給出興趣點(diǎn)推薦、位置共享服務(wù)等［1］?；谖恢玫臄?shù)據(jù)發(fā)布便捷了人們生活，但是也存在個(gè)人隱私信息泄露的風(fēng)險(xiǎn)［2］。

1 相關(guān)工作

傳統(tǒng)的位置保護(hù)方法有抑制法、數(shù)據(jù)加密法、泛化法、數(shù)據(jù)擾動(dòng)法［3］等。

抑制法是一種基于先驗(yàn)知識(shí)，通過(guò)抑制敏感背景信息來(lái)保護(hù)用戶(hù)隱私的方法［4］。然而，在需要?jiǎng)h除太多數(shù)據(jù)的情況下，信息會(huì)大量丟失，導(dǎo)致數(shù)據(jù)查詢(xún)服務(wù)質(zhì)量下降。

數(shù)據(jù)加密法是利用加密技術(shù)對(duì)數(shù)據(jù)信息加密，以保護(hù)數(shù)據(jù)隱私［3］。雖然加密后真實(shí)數(shù)據(jù)很難泄露，但嚴(yán)重破壞了數(shù)據(jù)可用性且耗時(shí)較長(zhǎng)。

泛化法由點(diǎn)到面地將數(shù)據(jù)點(diǎn)或整個(gè)位置軌跡進(jìn)行轉(zhuǎn)換，以達(dá)到保護(hù)用戶(hù)位置隱私的目的［5］。由于泛化法需要加入很多輔助數(shù)據(jù)，會(huì)拉低算法的運(yùn)行效率，且數(shù)據(jù)冗余過(guò)多。

為了給真實(shí)數(shù)據(jù)增加噪點(diǎn)、擾亂其真實(shí)性，一般采用數(shù)據(jù)擾動(dòng)法，但這種方法通常是將偽造的位置數(shù)據(jù)來(lái)代替原有數(shù)據(jù)集中的真實(shí)位置數(shù)據(jù)［6］。如Feng 等［7］提出Vurtual Avatar 軌跡隱私保護(hù)方案，用擾動(dòng)的數(shù)據(jù)點(diǎn)對(duì)真實(shí)的位置點(diǎn)進(jìn)行干擾。計(jì)算量小、實(shí)現(xiàn)簡(jiǎn)單是假數(shù)據(jù)法的優(yōu)點(diǎn)，但是添加過(guò)多假數(shù)據(jù)會(huì)導(dǎo)致查詢(xún)結(jié)果不可靠。

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

現(xiàn)有的差分隱私位置保護(hù)方法存在一些問(wèn)題：①如何在保障使用者隱私的同時(shí)減少噪音影響所導(dǎo)致的錯(cuò)誤；②位置點(diǎn)數(shù)據(jù)集過(guò)大，如果采用聚類(lèi)的方法則存在離散點(diǎn)敏感，盲目選擇初始中心點(diǎn)會(huì)導(dǎo)致聚類(lèi)結(jié)果不理想等問(wèn)題。由于位置點(diǎn)之間的相關(guān)性，對(duì)每個(gè)真實(shí)位置獨(dú)立添加噪聲會(huì)導(dǎo)致噪音疊加，直接保護(hù)全部的數(shù)據(jù)集又會(huì)大大降低數(shù)據(jù)的可用性［13］。所以，合理設(shè)計(jì)隱私保護(hù)機(jī)制至關(guān)重要。

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

2 改進(jìn)方法

2.1 基本定義

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

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

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

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

稱(chēng)為函數(shù)ff 的全局敏感度［15］。

定義3噪音機(jī)制。差分隱私中，拉普拉斯機(jī)制將根據(jù)拉普拉斯分布添加噪聲擾動(dòng)數(shù)據(jù)［16］。設(shè)噪聲方差為，其中Q 為查詢(xún)函數(shù)：

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

定義4歐氏距離。歐幾里得距離：n 維空間中兩點(diǎn)之間的真實(shí)距離或者一個(gè)矢量的自然長(zhǎng)度如下［17］：

定義5誤差平方和。樣本x 與樣本總平均值的偏差平方和是用來(lái)衡量樣本離散程度的重要指標(biāo)，計(jì)算公式如下：

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

2.2.1 Greedy DBSCAN 算法

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

（1）確定點(diǎn)p 半徑ε 后聚類(lèi)。

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

（2）鄰域查詢(xún)。

（3）剔除離散噪聲。

（4）合并含有公共點(diǎn)的簇。

2.2.2 K-means++算法

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

K-means++聚類(lèi)算法選擇k 個(gè)聚類(lèi)中心步驟如下：

（2）計(jì)算樣本與現(xiàn)有的聚類(lèi)中心點(diǎn)間的最短距離（即與距離最近的聚類(lèi)中心點(diǎn)的歐式距離），該距離用D（x）表示。計(jì)算每一樣本被選為下一個(gè)中心點(diǎn)的概率，新的聚類(lèi)中心則為概率最高的樣本點(diǎn)。

（3）重復(fù)步驟（2），直到選擇了k 個(gè)聚類(lèi)中心。

（4）劃分每個(gè)樣本Xi到距離其最近的聚類(lèi)中心簇中。

2.2.3 拉普拉斯加噪

其中，Pi是類(lèi)中的樣本數(shù)。

輸入隱私預(yù)算ε和聚類(lèi)中心J，產(chǎn)生噪聲，滿(mǎn)足概率Pr（j（x，y），λ），其中Pr（j（x，y），λ）計(jì)算如下：

然后添加噪聲，在聚類(lèi)中心J 中加入噪聲來(lái)擾亂攻擊者，通過(guò)判斷聚類(lèi)中心在真實(shí)位置點(diǎn)的左/右方向，合理使用“+”/“-”運(yùn)算。噪聲添加公式如下：

為中心點(diǎn)加入與密度呈正相關(guān)的噪音數(shù)據(jù)如圖1 所示（彩圖掃OSID 碼可見(jiàn)，下同）。

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

2.3 DPK-MO 算法

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

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

DPK-MO 算法步驟如下：

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

輸出：聚類(lèi)結(jié)果集合Dres。

（1）使用Greedy DBSCAN 算法在數(shù)據(jù)集上運(yùn)行得到初始化的中心點(diǎn)集C 以及個(gè)數(shù)k。

（2）計(jì)算C 中各中心點(diǎn)對(duì)應(yīng)集合中的誤差平方和φ(Ck,Xk)，取最小誤差平方和φmin所對(duì)應(yīng)的簇中心點(diǎn)Ck作為聚類(lèi)初始點(diǎn)。

（3）以Ck為初始中心點(diǎn)，k 為目標(biāo)集合數(shù)，執(zhí)行Kmeans++算法。

（4）判斷φ(Ck,Xk)'與φmin的大小，如果φ(Ck,Xk)'小于φmin則對(duì)應(yīng)的簇Dk不動(dòng)，如果φ(Ck,Xk)'大于φmin，數(shù)據(jù)集D=D-Dk，再循環(huán)執(zhí)行步驟（2）-（4），直到超過(guò)指定執(zhí)行次數(shù)最大值。

（5）最終得到最優(yōu)聚類(lèi)集D’。

（6）對(duì)于用戶(hù)位置點(diǎn)聚類(lèi)集D’，計(jì)算聚類(lèi)簇位置點(diǎn)密度參數(shù)ui（i=1，2，…，n，位置點(diǎn)密度參數(shù)為聚類(lèi)簇內(nèi)位置點(diǎn)總數(shù)）。

（7）計(jì)算異常點(diǎn)最大數(shù)Nnum=ui*0.05。

（8）判斷每個(gè)類(lèi)中的元素?cái)?shù)目是否小于Nnum。如果小于Nnum則進(jìn)行合并操作。

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

式（14）中的ni和nj表示這兩類(lèi)樣本的個(gè)數(shù)，新的聚類(lèi)中心可以看作是這兩類(lèi)樣本的加權(quán)和。如果其中一個(gè)類(lèi)包含樣本數(shù)過(guò)多，則合成的新的類(lèi)中心位置將更傾向于它。

（11）在新的聚類(lèi)中心Cnew中加入噪聲，輸出差分隱私保護(hù)擾動(dòng)后的數(shù)據(jù)集Dres。

算法流程如圖2 所示。

Fig.2 Algorithm flow圖2 算法流程

3 實(shí)驗(yàn)結(jié)果與分析

本文使用Python 編程語(yǔ)言進(jìn)行仿真實(shí)驗(yàn)，分別從結(jié)果誤差、數(shù)據(jù)可用性?xún)蓚€(gè)方面對(duì)比DPK-means 算法、DPKmeans++算法和本文提出的DPK-MO 算法進(jìn)行分析，采用Geo-life 數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理得到二維位置數(shù)據(jù)集。單機(jī)環(huán)境為：Inter（R）Core（TM）i7 CPU 3.7 GHz，8GB 內(nèi)存，Window 10 64 位操作系統(tǒng)。

3.1 實(shí)驗(yàn)結(jié)果誤差

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

3.2 實(shí)驗(yàn)數(shù)據(jù)可用性分析

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

Fig.3 Error comparison of algorithm results圖3 算法結(jié)果誤差對(duì)比

Fig.4 Data availability comparison of algorithm F-measure圖4 算法F-measure 數(shù)據(jù)可用性對(duì)比

通過(guò)圖4 可以看出，本文提出的DPK-MO 算法在滿(mǎn)足ε 差分隱私要求的前提下能夠有效保護(hù)用戶(hù)的位置隱私。與經(jīng)典DPK-means 算法相比，F(xiàn)-measure 值提高了近30%，表明在相同隱私預(yù)算ε 下數(shù)據(jù)可用性更高。

4 結(jié)語(yǔ)

針對(duì)現(xiàn)有的差分隱私K-means 算法中初始聚類(lèi)中心點(diǎn)對(duì)結(jié)果的影響，為提高數(shù)據(jù)可用性，本文提出一種新的基于差分隱私的DPK-MO 算法。算法引入鄰接密度和最小誤差平方和來(lái)判定初始中心點(diǎn)，始終選取樣本誤差平方和最小的點(diǎn)作為中心再聚類(lèi)，剔除離散點(diǎn)，合并聚類(lèi)集，最后合理加入符合差分隱私的拉普拉斯噪聲，提升了聚類(lèi)結(jié)果的準(zhǔn)確性，在保護(hù)用戶(hù)隱私信息的同時(shí)提高了數(shù)據(jù)的可用性。后續(xù)計(jì)劃引入分布式系統(tǒng)來(lái)提升算法效率，進(jìn)一步探索DPK-MO 算法在其它方面的應(yīng)用。