基于k—匿名的軌跡數據隱私發布研究綜述

趙凱毅，朱麟，路士兵

摘 要：隨著移動定位技術的發展，大量移動軌跡數據使信息泄露于公開的互聯空間中，使攻擊者可以通過計算推理挖掘軌跡信息。軌跡數據發布的隱私保護是近年來網絡空間安全領域研究的熱點問題。為了防止該類軌跡數據隱私的泄露，通常采用k-匿名技術實現軌跡的隱私保護。該技術在國內外研究中取得了一定的成果。本文闡述了軌跡隱私保護的相關定義及研究方法，對國內外移動軌跡數據k-匿名隱私保護研究的成果進行了總結，并介紹了國內外有關軌跡數據k-匿名隱私保護研究的相關技術。同時對國內外的技術進行了比較，詳細敘述了國外與國內各自方法的優點，指出了研究中存在的不足與今后研究的大致方向。

關鍵詞：軌跡數據；軌跡數據發布；隱私保護；k-匿名

中圖分類號：T391 文獻標識碼：A

A Research Review on Privacy-Preserving of Trajectory Data

Publishing Based on K-Anonymity

ZHAO Kaiyi，ZHU Lin，LU Shibing

（Department of Electronics，China Maritime Police Academy，Ningbo 315801，China）

Abstract：With the development of mobile localization technology，large amounts of mobile trajectory data expose information to open cyberspace，so that hackers can dig out trajectory data by computing and reasoning.Recently，privacy-preserving of trajectory data publishing is one of the hottest topics in Internet security.In order to prevent the disclosure of trajectory data，k-anonymous privacy preserving model is widely applied，on which some research achievements have been made both at home and abroad.This paper presents some related definitions and research methods in trajectory data privacy preserving，summarizes domestic and abroad research achievements on the k-anonymous privacy preserving of mobile trajectory data，introduces and compares related technology on the k-anonymous privacy preserving of mobile trajectory data both at home and abroad，elaborates on respective advantages of each method at home and abroad，and points out the limitation in previous studies and the direction in future studies.

Keywords：trajectory data；trajectory data publishing；privacy preserving；k-anonymity

1 引言（Introduction）

隨著移動設備和定位技術的發展，移動軌跡數據的隱私保護也受到了人們的關注。軌跡數據不僅蘊含著豐富的個人、位置等顯性信息，而且還可以通過推理計算軌跡的隱性信息，挖掘移動終端設備的軌跡行為特征、行為模式和行為習慣，從而獲取設備的信息數據，導致設備對象的隱私泄露。為有效保證數據的安全性，移動軌跡數據的隱私保護成為迫切需要解決的問題。

當前，普遍采用的軌跡隱私方法是基于k-匿名模型[1，2]，它是由Gruteser等人提出的。該技術是指在相關空間領域中，給定該空間節點位置形成的軌跡。當任意一條軌跡T在任意采樣時刻ti時，當至少有k-1條軌跡在相應的采樣位置上與T泛化為同一區域時，則滿足軌跡的k-匿名。k-匿名的技術的核心思想是將敏感屬性泛化，使得單條記錄無法和其他k-1條記錄區分開，進而實現數據的隱私保護。

本文闡述了軌跡隱私保護的相關定義及的研究方法，對國內外移動軌跡數據k-匿名隱私保護研究的成果進行了總結，并介紹了國內外有關軌跡數據k-匿名隱私保護研究的相關技術。同時對國內外的技術進行了比較，詳細敘述了國外與國內各自方法的優點，指出了研究中存在的不足與今后研究的大致方向。

2 軌跡隱私保護方法（Privacy preserving methods）

軌跡數據發布中的隱私保護方法主要是假數據法、抑制法和泛化法。其中，假數據法是在原數據的基礎上，采用與原始軌跡不同的信息來抵御攻擊，同時保證數據統計屬性的真實性。該方法計算量較小，容易產生數據存儲量過大而導致數據的有效性降低，一般用于數據量不大的情況，可以體現方法的可用性；抑制法可以有條件地選擇發布的數據，對敏感數據和頻繁訪問數據則不再選擇發布，但是計算方法時間性能太大，會導致數據信息的損失量過大，一般也用于訓練計算數據量較小的軌跡集合；泛化法是通過獲取軌跡上的位置采樣點，將這些采樣點泛化為匿名區域，從而實現隱私保護。軌跡k-匿名技術就是一種基于泛化方法的隱私保護技術，可以平衡隱私保護度量和增加服務質量。endprint

3 軌跡k-匿名隱私保護技術（K-Anonymous privacy

preserving technology）

3.1 （k，δ）-匿名技術

軌跡（k，δ）-匿名的隱私保護技術最先是由國外研究者Abul等人[3]提出的。經過大量研究與分析，移動軌跡數據抽樣和定位系統存在不精確性，而Abul與其他幾位研究者正是利用這一不確定性，提出了軌跡（k，δ）-匿名的隱私保護技術。該技術在基于簇的方法基礎上，實現了基于簇的軌跡（k，δ）-匿名。

所謂（k，δ）-匿名模型，是指在不確定性閾值δ和匿名閾值k給出的情況下，當且僅當|D|≥k時，軌跡集合D滿足（k，δ）-匿名。同時D中任意兩條軌跡tr1和tr2均滿足Coloc（tr1，tr2）。如果對于每一條軌跡，在該軌跡距離δ的半徑區域內，應當至少存在與當前軌跡相似度較高的k-1條軌跡，δ越大，則說明通過聚類的組就越大，信息發布的安全性就越高，但信息損失率越高。

為了在提高信息隱私保護安全性的同時降低信息的損失率，NWA（Never Walk Alone）方法[3]將分布于同一時間段內的軌跡存儲到一個等價類中，通過聚類尋找空間距離相似的軌跡，并滿足k-匿名模型。該方法的優點可以采用歐式距離計算軌跡之間的距離。但是當數據量較多時，聚類使得當前軌跡的離群點增加，數據有效性受到影響。因此，在該問題的基礎上，W4M[4]在NWA的基礎上做了優化，采用編輯距離[5]來度量軌跡上采樣點間的距離，使軌跡上離群點的數量較之前的方法相比有了明顯的減少，降低了所舍棄數據的數量，更好且更有效地預防了攻擊者使用特定的位置信息對發布的軌跡數據隱私進行攻擊，同時保證了所發布的軌跡數據具有較高的質量。

上述的幾種方法都將整條軌跡上的所有的采樣點進行了泛化的處理，但忽視了準標識符QI的屬性與其他屬性間所存在的區別。因此，Yarovoy等人[6]針對此問題，對動態QI的屬性進行了處理，查找所有時刻內移動對象的聚集距離最小的k-1個對象，并將該k-1個對象匿名到同一匿名的區域內，更加全面地做到了在泛化處理整條軌跡上所有采樣點的同時，兼顧準標識符屬性與其他軌跡間屬性所存在的區別，提高了數據發布的服務質量。

3.2 （k，l）-匿名技術

軌跡（k，l）-匿名技術[7]與上述國外軌跡（k，δ）-匿名的隱私保護技術有所不同，該技術由RASUAR等人提出，是指在滿足軌跡的k-匿名的基礎上，同時滿足軌跡l多樣性的軌跡的集合。從構建軌跡k-匿名集的原則中我們了解到，在構建軌跡k-匿名集的同時，要使集合內的k條軌跡具有相似性，且轉化后的數據庫與原始數據庫的信息扭曲度要盡可能小，這便是所說的NP難的問題。可是，假如軌跡在集合內的相似性過高，同樣會導致隱私的泄露，因為在集合中軌跡都是相鄰且靠近的，如果每條軌跡之間的相似性過高，所有移動對象的運動方式與路徑便會很容易被攻擊者分析了解到，從而降低了隱私的保護程度。所以，在構造軌跡k-匿名集時，要盡量避免出現相似的軌跡形狀。

為了避免這一問題，文獻[8]提出了一種面向個體的、個性化擴展的l-多樣性隱私匿名模型。該模型雖然對傳統的匿名模型進行了優化，但卻只考慮到了軌跡的時間與空間屬性。基于軌跡形狀多樣性的軌跡（k，l）-匿名技術，在考慮了軌跡的時間與空間屬性的同時，還考慮到了軌跡的形狀屬性，使匿名集內的軌跡在保持相近距離與相似關聯的基礎上，依然保持了一定的形狀多樣性，避免了因高度的相似性而導致隱私泄露的可能。

軌跡（k，l）-匿名技術中所運用的SP算法是以文獻[3]中的NWA算法的框架為基礎所提出的，分為軌跡數據預處理、數據聚類、數據分組和數據（k，l）-匿名處理。數據預處理時，對所有的軌跡進行遍歷，分配并選擇時間段相等的軌跡，放置于同一個等價類中。如果某個等價類中的軌跡不足k條，為使損失的信息降低至最小，則通過貪心算法查找另一個等價類。通過重復同步化處理，將兩個等價類合并為一個新的等價類，以此類推，最后獲得一系列軌跡數不小于k的等價類。

軌跡（k，l）-匿名技術中的SP算法與NWA類似，但相比之下，SP算法將軌跡間的多樣性考慮了進去，即在相似復雜度得以保證的前提下，更有效地實現了隱私的保護。并且該算法使大量高度相似的軌跡存在于同一集合中的情況得到了避免，很好地實現了軌跡的（k，l）匿名，提升了數據的可用性。雖然該技術考慮到了軌跡的多樣性，卻未詳細考慮軌跡集合經過較大敏感區的情況，故也存在一定不足。

3.3 （k，δ，Δ）-匿名技術

通過以上幾種基于k匿名隱私保護技術的介紹，我們大致可以了解到：傳統的關于軌跡數據發布的隱私保護的研究多數都將聚類的方法運用在其中。在很多情況下，其相關算法都只注重對于每條軌跡的隱私保護，而忽略了對軌跡聚類組特征的保護。通過相關理論研究與實驗的論證，一些學者發現，在用聚類技術產生相應的軌跡數據后，對該軌跡數據進行二次聚類，可得到一系列特征，而該特征與在發布之前的原始軌跡數據所擁有的聚類組特征高度相似，從而可能導致隱私泄露。因此，為了有效地預防這種軌跡聚類的二次攻擊，福州大學吳英杰等人[9]提出了一種（k，δ，Δ）-匿名模型和基于該模型的聚類雜交隱私保護軌跡數據發布算法CH-TDP。它是在（k，δ）-匿名模型的基礎上，以（k，δ）-匿名模型為切入點，對聚類分組進行雜交，再進行組內擾亂。通過控制組間擾亂的程度，達到保護聚類組的共同特征。（k，δ，Δ）-匿名模型的目的是在抵御發布軌跡數據遭受二次聚類攻擊的前提下，保證發布軌跡數據的質量不低于質量閾值Δ。

通過了大量的仿真實驗和數據分析驗證了軌跡（k，δ，Δ）-匿名的隱私保護技術中（k，δ，Δ）-匿名模型及CH-TDP算法的有效性。實驗的相關結果證明，CH-TDP算法與（k，δ，Δ）-匿名模型不僅可以有效地抵御軌跡聚類過程中所產生的二次聚類攻擊，同時，該匿名技術還很好地保證了匿名數據的質量，確保了軌跡的相似度，控制了區域查詢結果的誤差率，在k匿名隱私保護研究方面起到了至關重要的作用，更全面地實現了移動軌跡數據的隱私保護這一根本目的。endprint

4 基于k-匿名技術的軌跡隱私保護技術的比較與

分析（Comparison and analysis of trajectory

data privacy preserving technology based on

k-anonymity）

分析了三種較為典型的基于k-匿名的軌跡隱私保護技術，分別詳細敘述了各自技術的主要原理、所用方法、重要用途，以及各自存在的優點及其所存在的一定局限性與不足。本文以表格的形式進行比較。

5 結論（Conclusion）

在當前數據隱私保護研究領域，對于軌跡數據發布的隱私保護研究很廣泛。本文中所提到的幾種軌跡k-匿名技術都是比較成功的應用案例。軌跡（k，δ）-技術模型、軌跡（k，l）-技術模型、軌跡（k，δ，Δ）-匿名技術都是在k-匿名模型的基礎上所提出來的。這些模型都有各自新穎之處，但其算法的精確性還有待改進。因此，雖然移動軌跡數據隱私保護是一個空間安全領域的研究熱點，但其技術還不夠成熟。目前，關于軌跡數據發布的隱私保護對模型和算法的研究相對較多，且有不少的學者進行了研究并提出了新的技術與算法。未來若能成功且全面地將軌跡數據隱私保護的研究成果進行實際應用，將會更好地促進信息共享和融合。

參考文獻（References）

[1] Marco Gruteser，Dirk Grunwald.Anonymous Usage of Loca-tion-Based Services through Spatial and Temporal Cloaking[C].Proceedings of the 1st International Conference on Mobile Systems，Applications and Services，San Francisco，2003：31-42.

[2] 霍崢，孟小峰.軌跡隱私保護技術研究[J].計算機學報，2011，34（10）：1820-1830.

[3] O.Abul，F.Bonchi and M.Nanni.Never walk alone：Uncertainty for anonymity in moving objects databases[C].Proceedings of the IEEE 24th International Conference on Data Engineering.IEEE，2008：376-385.

[4] O.Abul，F.Bonchi，M.Nanni.Anonymization of Moving Objects Databases by Clustering and Perturbation[J].Information Systems，2010，35（8）：884-910.

[5] CHEN L，OZSU M T，ORIA V.Robust and fast similarity search for moving object trajectories[C].Proceedings of the 2005 ACM SIGMOD international conference on Management of data，2005：491-502.

[6] Yarovoy，R.，Bonchi，F.，Lakshmanan，S..Anonymizing Moving Objects：How to Hide a MOB in a Crowd？[C].In：12th International Conference on Extending Database Technology，2009：72-83.

[7] Trujillo-R，Domingo-Ferrer J.On the privacy offered by（k，δ）anonymity[J].Information Systems，2014，38（4）：491-494.

[8] 孫丹丹，羅永龍，范國婷，等.基于軌跡形狀多樣性的隱私保護算法[J].計算機應用，2016，36（6）：1544-1551.

[9] 吳英杰，唐慶明，倪巍偉，等.基于聚類雜交的隱私保護軌跡數據發布算法[J].計算機研究與發展，2013，50（3）：578-593.

作者簡介：

趙凱毅（1997-），男，本科生.研究領域：信息安全，數據挖掘.

朱 麟（1984-），男，碩士，講師.研究領域：智能計算，數據挖掘，信息安全.

路士兵（1978-），男，碩士，副教授.研究領域：信息安全，嵌入式系統.endprint