一種基于聚類的交通軌跡差分隱私保護數據發布方法

趙書鵬

（廣東工業大學計算機學院，廣州510006）

0 引言

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

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

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

Hua等人[3]提出了一種K-means和指數機制結合的位置泛化方法。Li等人[4]擴展了這一方法，它首先用K-means離散每個時間戳n條軌跡的每個點并視作最優劃分方式，再設計距離計算公式提取候選劃分方式，通過指數機制選取該時間戳的聚類方式，以簇心作為該類點的映射位置。但由于K-means受初始值和離群點的影響，導致聚類結果不穩定且需要預設定簇的數量，因此會對軌跡點映射的準確性造成影響。

我們提出了一種新的基于聚類的交通軌跡差分隱私保護數據發布方法，結合AP聚類與歐氏幾何的豪斯多夫距離進行軌跡點的區域劃分和泛化映射，不需要提前定義聚類個數，更好地適應每個時間戳不同的軌跡點稀疏情況。

1 相關工作

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

差分隱私[1]作為一種頗受關注的隱私保護技術，能夠防止擁有任意背景知識的攻擊者的攻擊并提供有力的保護。其基本方法是對原始數據、原始數據的轉換過程或者是對統計結果添加噪聲實現隱私保護，并且對隱私保護的水平進行了嚴格的數學證明。目前，在軌跡序列數據發布中，差分隱私算法也被廣泛應用。但由于軌跡數據普遍是高維且稀疏的，因此怎樣聚合軌跡數據是目前主要的研究方向。我們根據不同的聚合方式將差分隱私保護軌跡數據發布的研究內容主要分為三類：基于樹形結構的模型、基于網格結構的模型以及基于聚類的模型。

Chen等人[10]首先提出了一種基于樹型結構的差分隱私保護軌跡數據發布模型SeqPT，該模型利用混合粒度的前綴樹存儲所有子序列的噪聲計數，并發布差分隱私軌跡數據。Chen等人[11]用可變長度的NGram模型存儲變長子序列，并將子序列與生成的軌跡進行組合。Khalil等人[12]提出了一種新的模型SafePath，該模型利用一種變高度、變度的分類樹來降低生成空節點的概率，提高匹配位置和時間標簽的速度。Li等人[13]對SafePath進行了擴展，通過一種增量的隱私分配機制和一種新的不需要分類樹的前綴樹結構來提高其有效性和效率。

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

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

2 理論基礎

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

AP聚類算法又稱吸引子傳播算法，是基于數據點間的“信息傳遞”的一種聚類算法。AP聚類算法的基本思想是將全部樣本映射成網絡的節點，再通過網絡中各邊的消息傳遞計算出個樣本的聚類中心。聚類過程中，有吸引度（responsibility）和歸屬度（avail?ability）兩類消息在各節點間傳遞。AP聚類算法通過迭代來不斷更新每個節點的吸引度和歸屬度，直到產生m個高質量的Exemplar（相當于質心），并將其余的數據節點分配到相應的聚類中。

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

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

迭代公式：

其中：

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

迭代公式：

其中：

2.1 差分隱私

相鄰數據集：對兩個數據集D1、D2，如果存在一條軌跡T，使得D1=D2∪T或D2=D1∪T，則D1、D2互為相鄰數據集。

差分隱私是一種概率隱私保護模型，對兩個相鄰數據集，經過差分隱私保護模型處理后，發布的兩個數據集的不存在明顯差異，即無法識別出數據集中的單條軌跡。因此，可以防止具有額外背景知識的攻擊者的攻擊，保護用戶個人隱私。

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

則隨機算法A滿足ε-差分隱私。其中，隱私預算參數ε控制隱私保護的級別，ε越小，隱私保護級別越高。

敏感度：對函數f:D1→Rm，輸入為數據集D1，輸出為m維向量。則f的敏感度為：

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

拉普拉斯機制是目前常用于對數值型數據實現差分隱私保護的方法，添加噪聲的大小依賴于其敏感度。

拉普拉斯機制：對函數f:D→Rm，令表示添加的噪聲，該噪聲由平均值為0，由規模參數為

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

為了應對復雜的算法模型，我們可以設置具體的組合算法，來保證模型滿足差分隱私保護。

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

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

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

后處理免疫性：對滿足差分隱私保護的算法輸出的結果進行二次處理，不會影響數據的隱私性。

3 算法框架和描述分析

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

3.1 軌跡點聚合模塊

算法1軌跡泛化整合

輸入：原始軌跡集D，時間域Dt，候選劃分方式數量φ，隱私預算ε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）//隨機從D中選取

11.ReturnD1

算法1在每個時間戳下，先提取軌跡集D在該時間戳下所有軌跡點，使用AP聚類算法，對軌跡點進行聚類劃分。再結合文獻[4]中φSubOptimal方法，基于AP算法聚類劃分與豪斯多夫距離，計算得出φ個最優的候選劃分方式φAreas。然后使用指數機制對劃分方式進行選取，期間，需要設計指數機制的得分函數。

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

則對任意一中劃分方式pi，我們可以得到得分函數為：

使用設計的指數機制選擇該時間戳下的軌跡點劃分結果，再以每個劃分區域的簇心作為該區域點的映射位置，對數據集所有軌跡點進行映射，完成泛化操作。此外，為了達到與原軌跡相同的軌跡種類，需要隨機選取|D|-|D1|條原軌跡加入到D1數據集中。

3.2 軌跡生成發布模塊

算法2噪聲添加與后處理

輸入：映射數據集D1，每條軌跡的真實計數{tc1,tc2,...,tcN}，隱私預算ε1

輸出：發布的軌跡數據集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'

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

然后計算得：

該后處理方法使軌跡更加符合真實情況。最后再按照對應的計數比作為軌跡生成的概率，生成與原軌跡相同數量的數據集D'，完成軌跡集D'的發布。

4 實驗結果分析

4.1 實驗設置

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

表1 數據集的基本統計信息

4.2 結果評估指標

4.2.1 計數查詢誤差

在對軌跡數據集進行統計分析時，數據分析人員通常會對一個區域內的人員情況進行統計查詢。我們規定，計數查詢方法Q（D）：在地圖上任取一點為圓心，以半徑為r作圓，計算數據集D中經過該圓的軌跡數。則查詢相對誤差為：

其中b為原軌跡集中軌跡數目的0.1%。為了防止概率性誤差，評估時會進行100次實驗，結果取平均值。

4.2.2 豪斯多夫距離

豪斯多夫距離是在度量空間中任意兩個集合之間定義的一種距離，是一種常用的歐氏幾何度量方式。我們用豪斯多夫距離作為數據集有效性的評價指標之一。

其中：

豪斯多夫距離越小，說明兩個數據集越相似。

4.2.3 結果分析

基于T-Drive數據集，我們在不同的隱私預算下，對比文獻[4]提出的模型進行實驗，分析評估指標的差異。由于對比文獻[4]提出的模型是基于K-means算法的，聚類數量需要提前設定，因此我們分別對聚類數為10，20，30，…，100的模型進行了實驗。

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

圖1 同一隱私預算下計數查詢誤差結果對比

圖2 同一隱私預算下豪斯多夫距離結果對比

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

圖3 不同隱私預算下計數查詢誤差結果對比

圖4 不同隱私預算下豪斯多夫距離結果對比

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

5 結語

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