一種基于聚類的交通軌跡差分隱私保護(hù)數(shù)據(jù)發(fā)布方法

趙書鵬

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州510006）

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，越來(lái)越多的設(shè)備能夠收集和分析用戶個(gè)人的移動(dòng)信息，并為用戶提供定位、導(dǎo)航、興趣點(diǎn)推薦等服務(wù)。導(dǎo)航應(yīng)用程序可以根據(jù)用戶當(dāng)前的位置和目的地為其規(guī)劃最快的移動(dòng)路線，交通攝像頭可以識(shí)別車輛車牌等特征信息并跟蹤其位置。通過(guò)與第三方公司合作進(jìn)行數(shù)據(jù)分析，企業(yè)和政府可以將這些信息應(yīng)用到各種交通場(chǎng)景中。

但是，上述設(shè)備收集的位置信息可能包含個(gè)人隱私。例如，帶有全球定位系統(tǒng)（GPS）的智能手機(jī)可能會(huì)記錄敏感位置，例如家庭和工作地點(diǎn)。這些信息一旦泄露，個(gè)人的生命財(cái)產(chǎn)安全可能受到威脅。目前，數(shù)據(jù)的收集方往往只采用傳統(tǒng)的k匿名、空間位置掩蓋等方法來(lái)保護(hù)隱私數(shù)據(jù)。然而，這些方法都不能抵抗背景知識(shí)和再識(shí)別攻擊。例如，攻擊者可以通過(guò)一個(gè)人的性別、家庭和工作位置來(lái)識(shí)別出他的所有軌跡位置信息。因此，對(duì)于軌跡數(shù)據(jù)的發(fā)布，只采用傳統(tǒng)的匿名方法是不夠的。

差分隱私[1]是由Dwork于2006年提出的一種嚴(yán)格定義的隱私保護(hù)模型，能夠概率地對(duì)查詢或分析結(jié)果添加噪聲，保護(hù)數(shù)據(jù)庫(kù)中單條記錄不被泄露。因其能夠量化評(píng)估結(jié)果，在交通軌跡數(shù)據(jù)發(fā)布領(lǐng)域受到越來(lái)越多的關(guān)注。由于軌跡信息通常是二維甚至高維的，直接添加噪聲容易使數(shù)據(jù)誤差過(guò)大[2]，因此研究人員通常會(huì)先對(duì)高維軌跡進(jìn)行泛化操作。常用的泛化方法一般為采用網(wǎng)格模型或樹形結(jié)構(gòu)進(jìn)行映射。此外，隨著機(jī)器學(xué)習(xí)相關(guān)研究的深入，與差分隱私保護(hù)算法結(jié)合的研究也取得了一定的進(jìn)展。

Hua等人[3]提出了一種K-means和指數(shù)機(jī)制結(jié)合的位置泛化方法。Li等人[4]擴(kuò)展了這一方法，它首先用K-means離散每個(gè)時(shí)間戳n條軌跡的每個(gè)點(diǎn)并視作最優(yōu)劃分方式，再設(shè)計(jì)距離計(jì)算公式提取候選劃分方式，通過(guò)指數(shù)機(jī)制選取該時(shí)間戳的聚類方式，以簇心作為該類點(diǎn)的映射位置。但由于K-means受初始值和離群點(diǎn)的影響，導(dǎo)致聚類結(jié)果不穩(wěn)定且需要預(yù)設(shè)定簇的數(shù)量，因此會(huì)對(duì)軌跡點(diǎn)映射的準(zhǔn)確性造成影響。

我們提出了一種新的基于聚類的交通軌跡差分隱私保護(hù)數(shù)據(jù)發(fā)布方法，結(jié)合AP聚類與歐氏幾何的豪斯多夫距離進(jìn)行軌跡點(diǎn)的區(qū)域劃分和泛化映射，不需要提前定義聚類個(gè)數(shù)，更好地適應(yīng)每個(gè)時(shí)間戳不同的軌跡點(diǎn)稀疏情況。

1 相關(guān)工作

早期大多數(shù)軌跡數(shù)據(jù)發(fā)布方法大都基于k-匿名[5]，如果一個(gè)數(shù)據(jù)集滿足k-匿名，那么該數(shù)據(jù)集中至少有k條記錄具有相同的屬性值。Nergiz等人[6]首先將k-匿名應(yīng)用于軌跡數(shù)據(jù)集，在廣義時(shí)空下抑制單個(gè)軌跡點(diǎn)或整條軌跡。Abul等人[7]提出了一種廣義的k-匿名方法，即在一定地理距離范圍內(nèi)的點(diǎn)可以被認(rèn)為是在相同的位置，并應(yīng)用到軌跡集中[8]。Chen等人[9]對(duì)身份鏈接攻擊和屬性鏈接攻擊進(jìn)行了研究，首先提出了一種基于（K,C）L-privacy的支持局部和全局抑制的匿名化框架。雖然k-匿名方法被廣泛應(yīng)用，但k-匿名容易受到同質(zhì)性攻擊和背景知識(shí)攻擊，也不能量化隱私泄露的概率。因此，它們不能為發(fā)布軌跡數(shù)據(jù)提供足夠的隱私保護(hù)。

差分隱私[1]作為一種頗受關(guān)注的隱私保護(hù)技術(shù)，能夠防止擁有任意背景知識(shí)的攻擊者的攻擊并提供有力的保護(hù)。其基本方法是對(duì)原始數(shù)據(jù)、原始數(shù)據(jù)的轉(zhuǎn)換過(guò)程或者是對(duì)統(tǒng)計(jì)結(jié)果添加噪聲實(shí)現(xiàn)隱私保護(hù)，并且對(duì)隱私保護(hù)的水平進(jìn)行了嚴(yán)格的數(shù)學(xué)證明。目前，在軌跡序列數(shù)據(jù)發(fā)布中，差分隱私算法也被廣泛應(yīng)用。但由于軌跡數(shù)據(jù)普遍是高維且稀疏的，因此怎樣聚合軌跡數(shù)據(jù)是目前主要的研究方向。我們根據(jù)不同的聚合方式將差分隱私保護(hù)軌跡數(shù)據(jù)發(fā)布的研究?jī)?nèi)容主要分為三類：基于樹形結(jié)構(gòu)的模型、基于網(wǎng)格結(jié)構(gòu)的模型以及基于聚類的模型。

Chen等人[10]首先提出了一種基于樹型結(jié)構(gòu)的差分隱私保護(hù)軌跡數(shù)據(jù)發(fā)布模型SeqPT，該模型利用混合粒度的前綴樹存儲(chǔ)所有子序列的噪聲計(jì)數(shù)，并發(fā)布差分隱私軌跡數(shù)據(jù)。Chen等人[11]用可變長(zhǎng)度的NGram模型存儲(chǔ)變長(zhǎng)子序列，并將子序列與生成的軌跡進(jìn)行組合。Khalil等人[12]提出了一種新的模型SafePath，該模型利用一種變高度、變度的分類樹來(lái)降低生成空節(jié)點(diǎn)的概率，提高匹配位置和時(shí)間標(biāo)簽的速度。Li等人[13]對(duì)SafePath進(jìn)行了擴(kuò)展，通過(guò)一種增量的隱私分配機(jī)制和一種新的不需要分類樹的前綴樹結(jié)構(gòu)來(lái)提高其有效性和效率。

由于軌跡數(shù)據(jù)固有的順序性和高維性，前綴樹在處理具有時(shí)間屬性的軌跡數(shù)據(jù)時(shí)存在效率低、可用性低等問(wèn)題。Mir等人[14]提出了滿足不同隱私保護(hù)出行路線的WHERE[15]模型，命名為DP-WHERE。首先將軌跡點(diǎn)映射到均勻網(wǎng)格中，然后構(gòu)建home position、movement length、work position、call times概率分布，生成新的軌跡。He等人[16]提出了一種分級(jí)參考系統(tǒng)DPT，該系統(tǒng)可以識(shí)別具有不同粒度的原始軌跡，并將其映射到具有相應(yīng)粒度的參考系統(tǒng)中。Gursoy等人[17]提出了一種兩層的自適應(yīng)網(wǎng)格，通過(guò)第一層均勻網(wǎng)格內(nèi)軌跡點(diǎn)的密度來(lái)計(jì)算推出第二層子網(wǎng)格的劃分大小，以此生成的網(wǎng)格來(lái)對(duì)軌跡點(diǎn)進(jìn)行映射。Ghane等人[18]以移動(dòng)速度與對(duì)象最小停留時(shí)間為參數(shù)設(shè)計(jì)生成了一種均勻的網(wǎng)格結(jié)構(gòu)來(lái)映射軌跡。

隨著機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)相關(guān)研究的發(fā)展，現(xiàn)在越來(lái)越多的研究關(guān)注機(jī)器學(xué)習(xí)與差分隱私的融合技術(shù)。傅彥銘等人[19]提出了一種差分隱私保護(hù)Kmeans++聚類算法，在初始化選取中心點(diǎn)和迭代求均值中心點(diǎn)的過(guò)程中分別添加拉普拉斯噪聲以滿足差分隱私保護(hù)。胡闖等人[20]提出了一種新的基于差分隱私的DPk-means-up聚類算法來(lái)確定最佳K值的選擇。黃保華等人[21]提出了一種結(jié)合三分法和等差數(shù)列的隱私預(yù)算分配方案，保證使用對(duì)K-means每次迭代更新質(zhì)心的過(guò)程中引入的噪聲不會(huì)引起質(zhì)心變形。Hua等人[3]提出了一種利用K-means聚合點(diǎn)和指數(shù)機(jī)制提取點(diǎn)的位置泛化方法。文獻(xiàn)[4]擴(kuò)展了這一工作，它首先用K-means離散每個(gè)時(shí)間戳n條軌跡的每個(gè)點(diǎn)并視作最優(yōu)劃分方式，再設(shè)計(jì)距離計(jì)算公式提取候選劃分方式，通過(guò)指數(shù)機(jī)制選取該時(shí)間戳的聚類方式，以簇心作為該類點(diǎn)的映射位置。但由于此類算法需要預(yù)設(shè)簇的數(shù)量，受初始值和離群點(diǎn)的影響，導(dǎo)致聚類結(jié)果不穩(wěn)定，因此會(huì)對(duì)軌跡點(diǎn)聚合的準(zhǔn)確性造成影響。

2 理論基礎(chǔ)

2.1 AP聚類算法（Affinity Propagation Clustering Algorithm）

AP聚類算法又稱吸引子傳播算法，是基于數(shù)據(jù)點(diǎn)間的“信息傳遞”的一種聚類算法。AP聚類算法的基本思想是將全部樣本映射成網(wǎng)絡(luò)的節(jié)點(diǎn)，再通過(guò)網(wǎng)絡(luò)中各邊的消息傳遞計(jì)算出個(gè)樣本的聚類中心。聚類過(guò)程中，有吸引度（responsibility）和歸屬度（avail?ability）兩類消息在各節(jié)點(diǎn)間傳遞。AP聚類算法通過(guò)迭代來(lái)不斷更新每個(gè)節(jié)點(diǎn)的吸引度和歸屬度，直到產(chǎn)生m個(gè)高質(zhì)量的Exemplar（相當(dāng)于質(zhì)心），并將其余的數(shù)據(jù)節(jié)點(diǎn)分配到相應(yīng)的聚類中。

設(shè)數(shù)據(jù)樣本集為{x1,x2,…，xn}，S為描述各軌跡點(diǎn)之間相似度的矩陣，當(dāng)且僅當(dāng)xi與xj的相似性程度要大于其與xk的相似性，S(i,j)>S(i,k)。

吸引信息矩陣R：r(i,k)描述了數(shù)據(jù)對(duì)象k適合作為數(shù)據(jù)對(duì)象i的聚類中心的程度，表示的是從i到k的消息。

迭代公式：

其中：

歸屬信息矩陣A：a()i,k描述了數(shù)據(jù)對(duì)象i選擇數(shù)據(jù)對(duì)象k作為其據(jù)聚類中心的適合程度，表示從k到i的消息。

迭代公式：

其中：

2.1 差分隱私

相鄰數(shù)據(jù)集：對(duì)兩個(gè)數(shù)據(jù)集D1、D2，如果存在一條軌跡T，使得D1=D2∪T或D2=D1∪T，則D1、D2互為相鄰數(shù)據(jù)集。

差分隱私是一種概率隱私保護(hù)模型，對(duì)兩個(gè)相鄰數(shù)據(jù)集，經(jīng)過(guò)差分隱私保護(hù)模型處理后，發(fā)布的兩個(gè)數(shù)據(jù)集的不存在明顯差異，即無(wú)法識(shí)別出數(shù)據(jù)集中的單條軌跡。因此，可以防止具有額外背景知識(shí)的攻擊者的攻擊，保護(hù)用戶個(gè)人隱私。

ε-差分隱私：對(duì)相鄰數(shù)據(jù)集D1、D2，一種隨機(jī)算法A，Range(A)表示算法A所有可能的輸出集合，S是Range(A)任一子集，即S?Range(A)。若對(duì)于所有的S，都有：

則隨機(jī)算法A滿足ε-差分隱私。其中，隱私預(yù)算參數(shù)ε控制隱私保護(hù)的級(jí)別，ε越小，隱私保護(hù)級(jí)別越高。

敏感度：對(duì)函數(shù)f:D1→Rm，輸入為數(shù)據(jù)集D1，輸出為m維向量。則f的敏感度為：

其中，D1、D2互為相鄰數(shù)據(jù)集，||.||表示L1范式。

拉普拉斯機(jī)制是目前常用于對(duì)數(shù)值型數(shù)據(jù)實(shí)現(xiàn)差分隱私保護(hù)的方法，添加噪聲的大小依賴于其敏感度。

拉普拉斯機(jī)制：對(duì)函數(shù)f:D→Rm，令表示添加的噪聲，該噪聲由平均值為0，由規(guī)模參數(shù)為

指數(shù)機(jī)制：設(shè)一得分函數(shù)q(D,R)，輸入為數(shù)據(jù)集D，輸出為一實(shí)體集R，若對(duì)一隨機(jī)算法A的任一輸出r∈R，與e(εq(D,r))/(2?q)成正比，則稱隨機(jī)算法A滿足ε-差分隱私。

為了應(yīng)對(duì)復(fù)雜的算法模型，我們可以設(shè)置具體的組合算法，來(lái)保證模型滿足差分隱私保護(hù)。

組合屬性：設(shè)A1，A2，…，An為n個(gè)隨機(jī)算法，對(duì)每個(gè)i∈[1,n]，Ai滿足εi-差分隱私。則有：

順 序 組 合：A1（D）,A2（D）,…,An（D）輸 出 滿 足-差分隱私。

平行組合：在D的不相交子集上應(yīng)用每個(gè)算法，滿足max(εi)-差分隱私。

后處理免疫性：對(duì)滿足差分隱私保護(hù)的算法輸出的結(jié)果進(jìn)行二次處理，不會(huì)影響數(shù)據(jù)的隱私性。

3 算法框架和描述分析

本文提出的滿足差分隱私保護(hù)的交通軌跡數(shù)據(jù)發(fā)布方法分為兩個(gè)部分，軌跡點(diǎn)聚合泛化模塊與軌跡生成發(fā)布模塊。對(duì)原始軌跡集中每個(gè)時(shí)間戳的軌跡點(diǎn)使用AP聚類算法進(jìn)行聚合，基于聚合結(jié)果，匹配選擇豪斯多夫距離最短的φ種聚合方式作為候選劃分方式，設(shè)計(jì)得分函數(shù)并使用指數(shù)機(jī)制選擇最佳劃分方式，再對(duì)聚合后的軌跡集合并泛化，對(duì)軌跡計(jì)數(shù)添加噪聲，最后經(jīng)后處理后生成發(fā)布軌跡數(shù)據(jù)集。該模型的創(chuàng)新之處在于，使用了AP聚類算法進(jìn)行軌跡聚合，不需要指定最終聚類的劃分個(gè)數(shù)，減少參數(shù)的干擾；將AP聚類與歐氏幾何平面的豪斯多夫距離進(jìn)行結(jié)合，更好地增強(qiáng)發(fā)布數(shù)據(jù)集的數(shù)據(jù)可用性。實(shí)驗(yàn)結(jié)果證明，該模型發(fā)布的軌跡數(shù)據(jù)集能夠在滿足差分隱私保護(hù)的同時(shí)，具有較高的數(shù)據(jù)可用性。

3.1 軌跡點(diǎn)聚合模塊

算法1軌跡泛化整合

輸入：原始軌跡集D，時(shí)間域Dt，候選劃分方式數(shù)量φ，隱私預(yù)算ε1

輸出：聚合后的軌跡集D1

1.Map=[]

2.For each timestamptiinDt:

3.Dti=[T[ti]forTinD]

4.apArea=AP（ti_points）//AP聚類

5.φAreas=φSubOptimal（apArea,hausdorffDis）

6.areaSelect=EM（φAreas,ε1）

7.Map[ti]=areaSelect

8.D1=map（Map,D）

9.While|D|-|D1|>0:

10.D1.add（Trajectory）//隨機(jī)從D中選取

11.ReturnD1

算法1在每個(gè)時(shí)間戳下，先提取軌跡集D在該時(shí)間戳下所有軌跡點(diǎn)，使用AP聚類算法，對(duì)軌跡點(diǎn)進(jìn)行聚類劃分。再結(jié)合文獻(xiàn)[4]中φSubOptimal方法，基于AP算法聚類劃分與豪斯多夫距離，計(jì)算得出φ個(gè)最優(yōu)的候選劃分方式φAreas。然后使用指數(shù)機(jī)制對(duì)劃分方式進(jìn)行選取，期間，需要設(shè)計(jì)指數(shù)機(jī)制的得分函數(shù)。

設(shè)每一種劃分方式為p，AP算法得出的劃分方式為p'，根據(jù)文獻(xiàn)[4]中基于豪斯多夫距離設(shè)計(jì)的平均距離算法MeanDist，我們可以得到可靠性U的函數(shù)：

則對(duì)任意一中劃分方式pi，我們可以得到得分函數(shù)為：

使用設(shè)計(jì)的指數(shù)機(jī)制選擇該時(shí)間戳下的軌跡點(diǎn)劃分結(jié)果，再以每個(gè)劃分區(qū)域的簇心作為該區(qū)域點(diǎn)的映射位置，對(duì)數(shù)據(jù)集所有軌跡點(diǎn)進(jìn)行映射，完成泛化操作。此外，為了達(dá)到與原軌跡相同的軌跡種類，需要隨機(jī)選取|D|-|D1|條原軌跡加入到D1數(shù)據(jù)集中。

3.2 軌跡生成發(fā)布模塊

算法2噪聲添加與后處理

輸入：映射數(shù)據(jù)集D1，每條軌跡的真實(shí)計(jì)數(shù){tc1,tc2,...,tcN}，隱私預(yù)算ε1

輸出：發(fā)布的軌跡數(shù)據(jù)集D'

2.ForiinN:

3.nci=tci+lap（ε2,Δf）

4.NC={nc1,nc2,…,ncN}

5.SortNCand getS=

7.S'=

8.Forifrom 1 toN:

9.nci'=S'[i]

10.D2={（Ti',nci'）|i=1,…,N}

11.D'=[forifrom 1 toN:randomly choose

12.Tbased onP（nci'/sum（S'））]

13.ReturnD'

軌跡生成發(fā)布模塊分為噪聲添加與后處理兩個(gè)子模塊。前半部分（1-3行）是噪聲添加子模塊，先計(jì)算出敏感度，由敏感度定義可知，這里的敏感度為1，然后根據(jù)隱私預(yù)算ε2，對(duì)不同軌跡的計(jì)數(shù)添加拉普拉斯噪聲。后半部分（4-10行）為后處理子模塊。為了更直觀地進(jìn)行后處理，我們以圖的形式來(lái)映射生成的軌跡集，不同的節(jié)點(diǎn)表示不同時(shí)間戳的軌跡點(diǎn)位置。由實(shí)際經(jīng)驗(yàn)可知，對(duì)于相鄰的節(jié)點(diǎn)，時(shí)間戳小的節(jié)點(diǎn)計(jì)數(shù)一定大于時(shí)間戳大的；且如果對(duì)兩個(gè)節(jié)點(diǎn)p、g，p的真實(shí)計(jì)數(shù)大于q，那么p的噪聲計(jì)數(shù)也應(yīng)大于q。因此，我們基于文獻(xiàn)[4]，設(shè)計(jì)了一種后處理方法：我們令mean[i,j]表示S的一條子軌跡Sij的平均數(shù)：

然后計(jì)算得：

該后處理方法使軌跡更加符合真實(shí)情況。最后再按照對(duì)應(yīng)的計(jì)數(shù)比作為軌跡生成的概率，生成與原軌跡相同數(shù)量的數(shù)據(jù)集D'，完成軌跡集D'的發(fā)布。

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

4.1 實(shí)驗(yàn)設(shè)置

本文提出的算法基于Python實(shí)現(xiàn)，本節(jié)中所有實(shí)驗(yàn)的運(yùn)行環(huán)境為雙核Intel Core i5 3.1 GHz，內(nèi)存為8 GB。采用微軟提供的公開數(shù)據(jù)集T-Drive[24]，內(nèi)含北京10357輛出租車一周的出行軌跡。我們提取了其中850條軌跡，每條軌跡包含32個(gè)時(shí)間戳。詳情如表1所示。作為對(duì)比，我們同樣實(shí)現(xiàn)了文獻(xiàn)[4]中的模型，通過(guò)設(shè)置不同的隱私預(yù)算、聚類數(shù)量，對(duì)比說(shuō)明本文提出算法的先進(jìn)性。

表1 數(shù)據(jù)集的基本統(tǒng)計(jì)信息

4.2 結(jié)果評(píng)估指標(biāo)

4.2.1 計(jì)數(shù)查詢誤差

在對(duì)軌跡數(shù)據(jù)集進(jìn)行統(tǒng)計(jì)分析時(shí)，數(shù)據(jù)分析人員通常會(huì)對(duì)一個(gè)區(qū)域內(nèi)的人員情況進(jìn)行統(tǒng)計(jì)查詢。我們規(guī)定，計(jì)數(shù)查詢方法Q（D）：在地圖上任取一點(diǎn)為圓心，以半徑為r作圓，計(jì)算數(shù)據(jù)集D中經(jīng)過(guò)該圓的軌跡數(shù)。則查詢相對(duì)誤差為：

其中b為原軌跡集中軌跡數(shù)目的0.1%。為了防止概率性誤差，評(píng)估時(shí)會(huì)進(jìn)行100次實(shí)驗(yàn)，結(jié)果取平均值。

4.2.2 豪斯多夫距離

豪斯多夫距離是在度量空間中任意兩個(gè)集合之間定義的一種距離，是一種常用的歐氏幾何度量方式。我們用豪斯多夫距離作為數(shù)據(jù)集有效性的評(píng)價(jià)指標(biāo)之一。

其中：

豪斯多夫距離越小，說(shuō)明兩個(gè)數(shù)據(jù)集越相似。

4.2.3 結(jié)果分析

基于T-Drive數(shù)據(jù)集，我們?cè)诓煌碾[私預(yù)算下，對(duì)比文獻(xiàn)[4]提出的模型進(jìn)行實(shí)驗(yàn)，分析評(píng)估指標(biāo)的差異。由于對(duì)比文獻(xiàn)[4]提出的模型是基于K-means算法的，聚類數(shù)量需要提前設(shè)定，因此我們分別對(duì)聚類數(shù)為10，20，30，…，100的模型進(jìn)行了實(shí)驗(yàn)。

圖1、圖2分別為隱私預(yù)算為1下，本文提出的方法與文獻(xiàn)[4]提出的模型（聚類K值分別為10,20,30,…,100）計(jì)數(shù)查詢誤差的對(duì)比圖與豪斯多夫距離的對(duì)比圖。由圖1可以看出，我們提出的方法具有更低的計(jì)數(shù)查詢誤差，說(shuō)明在位置準(zhǔn)確度上，我們的方法能更好地?cái)M合原始軌跡的稀疏性，更大地保存數(shù)據(jù)信息。由圖2可以看出，我們提出的方法對(duì)比大部分K值下的文獻(xiàn)[4]模型結(jié)果，具有更低的豪斯多夫距離，得到的數(shù)據(jù)集可用性較高。

圖1 同一隱私預(yù)算下計(jì)數(shù)查詢誤差結(jié)果對(duì)比

圖2 同一隱私預(yù)算下豪斯多夫距離結(jié)果對(duì)比

圖3、圖4分別為不同隱私預(yù)算下，本文提出的方法與文獻(xiàn)[4]提出的模型（劃分?jǐn)?shù)分別為10、70、100）計(jì)數(shù)查詢誤差的對(duì)比圖與豪斯多夫距離的對(duì)比圖。由圖3可以看出，不同隱私預(yù)算下，我們提出的方法依然具有最佳的計(jì)數(shù)查詢誤差。由圖4可以看出，我們提出的方法也接近文獻(xiàn)[4]模型的最佳豪斯多夫距離。且從兩個(gè)圖中都可看出，隨著差分隱私預(yù)算的增加，計(jì)數(shù)查詢誤差與豪斯多夫距離都越來(lái)越低，效果越來(lái)越好，符合差分隱私的定義。

圖3 不同隱私預(yù)算下計(jì)數(shù)查詢誤差結(jié)果對(duì)比

圖4 不同隱私預(yù)算下豪斯多夫距離結(jié)果對(duì)比

綜上，由于我們提出的方法可以不需要提前指定軌跡點(diǎn)劃分區(qū)域數(shù)量，且將AP算法與豪斯多夫距離計(jì)算相結(jié)合，能夠不受數(shù)據(jù)集稀疏、范圍的變化影響，能更好地對(duì)軌跡點(diǎn)進(jìn)行聚合泛化，發(fā)布具有更好數(shù)據(jù)可用性且滿足差分隱私保護(hù)的數(shù)據(jù)集。

5 結(jié)語(yǔ)

本文提出的基于聚類的交通軌跡差分隱私保護(hù)數(shù)據(jù)發(fā)布方法，目的是為了提高發(fā)布數(shù)據(jù)的可用性同時(shí)保證用戶的隱私。本文的算法通過(guò)改變每個(gè)時(shí)間戳軌跡點(diǎn)聚合的方式，使用AP聚類算法進(jìn)行軌跡點(diǎn)聚合，基于聚類結(jié)果結(jié)合豪斯多夫距離計(jì)算生成候選劃分方式，設(shè)計(jì)新的指數(shù)機(jī)制進(jìn)行選取。對(duì)比常用的K-means聚類方法，我們提出的方法不需要事先指定聚類的數(shù)量，聚類的結(jié)果不會(huì)變化，也更適用于稀疏的軌跡集。在T-Drive數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果也表明，該方法能夠在保護(hù)發(fā)布軌跡數(shù)據(jù)集隱私的同時(shí)，極大保留數(shù)據(jù)集的可用性。下一步將拓展差分隱私算法在軌跡數(shù)據(jù)發(fā)布領(lǐng)域與新興領(lǐng)域的結(jié)合，嘗試結(jié)合使用神經(jīng)網(wǎng)絡(luò)相關(guān)算法，以提高數(shù)據(jù)可用性。