顧貞，馬春光，宋蕾，李菊雁

（1.哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001；2.黑龍江東方學院基礎教學研究部，黑龍江哈爾濱150066；3.黑龍江大學數據科學與技術學院，黑龍江哈爾濱150080）

1 引言

近年來，隨著智能設備以及定位技術的發(fā)展，研究人員會搜集到越來越多的運動物體的軌跡數據，對其進行分析挖掘可以為人們提供方便快捷的服務。例如，在城市路網規(guī)劃中，可以合理規(guī)劃城市交通避免產生交通擁堵，進而提高人們的生活質量[1～4]。然而，軌跡數據中含有大量的個人信息，如用戶的家庭地址、單位地址、身體健康狀況等，如果直接發(fā)布位置和軌跡數據，會導致人們的隱私泄露[5]。

位置軌跡隱私保護問題主要分兩類：一類是離線模式下的位置軌跡隱私保護，由特定機構搜集軌跡數據進行分析和挖掘將有用信息提供給特定客戶的使用，這要求在軌跡數據發(fā)布前對整條軌跡進行隱私處理，如文獻[6～10]為針對離線模式下軌跡數據隱私保護方法的研究；另一類是在線位置軌跡隱私保護，如基于位置的服務，首先確定對象的實時位置，然后提供給對象相關的各類服務，如通過移動設備定位對象當前的地理位置，然后尋找其附近范圍內的餐館等查詢服務，移動對象的實時軌跡數據要上傳服務提供商，因此也面臨隱私泄露的風險，基于位置服務的軌跡隱私保護是非常有意義的，如文獻[11～16]為針對基于位置服務的軌跡隱私數據保護研究。

本文主要研究離線模式下的軌跡隱私保護技術，如圖1所示。文中對現有的軌跡數據隱私保護方法進行了總結分析，總結優(yōu)點和缺點，然后分析軌跡數據本身固有的統(tǒng)計分布特性，討論了軌跡隱私保護技術中還需要深入解決的相關問題。

2 相關概念

（1）軌跡隱私[17]：軌跡隱私是指個體運行軌跡本身含有的敏感信息（如訪問過的敏感位置），或者由運行軌跡推導出的其它個人信息（如家庭住址、工作地點、生活習慣、健康狀況等）。

（2）軌跡數據集[17]：移動對象軌跡可表示為三維空間中的一條折線，記為其中表示軌跡在時刻的位置為，為軌跡的點數，軌跡數據集是軌跡的集合，記為軌跡數據庫中軌跡的條數。

（3）軌跡k匿名集[17]：給定軌跡數據庫，發(fā)布的軌跡數據庫是的k-匿名版本，則需要滿足兩個條件。

（4）語義位置：語義位置是指真實環(huán)境中的具有語義的位置，移動對象訪問或者停留的位置，如賓館、商店、商場、醫(yī)院、銀行等。

3 軌跡隱私保護方法

3.1 基于抑制法的軌跡隱私保護

根據實際情況，有選擇的抑制發(fā)布軌跡數據中的敏感或者頻繁訪問位置[18,19]或者整條軌跡[20]，此類方法實現簡單、易導致信息丟失、數據的可用性有限。文獻[21]中提出了基于擾動的軌跡隱私保護方法，即用出現頻率最低的同類節(jié)點來代替存在隱私泄露風險的節(jié)點，從而實現對具有隱私泄露風險的節(jié)點的抑制，方法是基于數理統(tǒng)計的方法，在保持軌跡數據的內部結構和增加數據的可用性方面具有一定的優(yōu)勢。文獻[20]提出兩種基于軌跡頻率的方案對軌跡數據進行匿名處理，第一種方案是根據情況抑制整條有問題的軌跡數據或向有問題的軌跡數據集中添加假數據；第二種方案是采用特定的軌跡局部抑制法對數據進行抑制處理。抑制法將軌跡中的敏感位置信息進行隱藏不發(fā)布，方法簡單也有效，但是具有局限性：一是刪除了原始軌跡的部分信息，導致數據挖掘受到影響；二是目前都是根據已知攻擊模型選取抑制信息，當攻擊模型不確定的時候，抑制法不適用。

3.2 基于假軌跡的軌跡隱私保護

假軌跡技術這種方法的原理是通過對原始軌跡中加入一定數量的虛假軌跡使得原始軌跡數據受到干擾，降低原始軌跡泄露的概率，這種方法實現比較簡單，但是需要注意保證原軌跡數據的統(tǒng)計可用性，需要滿足虛假軌跡的移動狀態(tài)與真實軌跡相似[22]，虛假軌跡與真實軌跡之間有交叉。添加虛假軌跡的方法有隨機生成法和旋轉模式生成法。隨機生成法是指在軌跡的起點和終點之間隨機生成一條與原軌跡運行模式相似的虛假軌跡。旋轉生成法是指以真實軌跡為基礎，對原軌跡進行旋轉，例如在文獻[23]中提出通過真實軌跡的旋轉得到備選的假軌跡集，然后根據隱私模型下的參數對備選集進行篩選。文獻[24]將旋轉模式與隨機模式兩種方法結合，提出了K交叉模式方法，即通過確定虛假軌跡和真實軌跡的k個交叉點，隨機生成交叉點之間的軌跡。

文獻[25]提出的方案主要包括兩部分，真實軌跡旋轉和虛假軌跡調整，首先在用戶的真實軌跡上隨機選擇一個參考點，通過將用戶的真實軌跡旋轉不同角度，依次生成其他多條潛在虛假軌跡。由于生成的多條潛在虛假軌跡是用戶真實軌跡旋轉的產物，從而有效地保證了軌跡之間的相似性，考慮到背景信息對用戶軌跡隱私保護的影響，在軌跡旋轉的過程中，通過將選定旋轉點進行基于背景信息的偏移，該方案能夠在保證虛假軌跡與真實軌跡相似性的基礎上有效地抵御擁有背景信息的攻擊者的攻擊。假軌跡方法需要注意的問題是，若生成的假軌跡不滿足路網約束，不符合移動對象的運行模式，則假軌跡并不起到隱私保護的作用，反而造成用戶的軌跡隱私泄露，所以要求假軌跡與用戶的真實運動軌跡要盡量相似，如何模擬生成合適的假軌跡是人們一直探索的問題。

3.3 基于泛化方法的軌跡隱私保護

基于泛化方法的軌跡隱私保護最主流的方法是軌跡k匿名方法[6～9]，找相似的k條軌跡來構造匿名集合，使攻擊者在沒有其他背景知識的情況下識別用戶身份的概率不超過泛化方法主要有三個步驟。

（1）軌跡預處理

這個階段的主要任務是對所有具有相同開始和結束時間的軌跡進行分組，即將軌跡數據集中起始時間和結束時間相同的軌跡分為一個等價類。但是，由于實際應用中無法保證每條軌跡之間的采樣置位點都是同一時刻，為了增加等價類中的軌跡數量，可進行部分軌跡的同步或修剪，保證軌跡在時間上的相似。

（2）構建軌跡k匿名集

通常都采用聚類方法構造軌跡k匿名集。對每一個等價類中的軌跡聚類形成k匿名集，研究者們嘗試了不同的聚類方法，如貪婪聚類法、密度聚類、層次聚類等，在聚類過程中利用軌跡之間的距離[26～30]作為衡量軌跡之間相似性的度量，以此找出等價類中最相似的k條軌跡構成k匿名集。

（3）軌跡數據發(fā)布

經過上一步驟形成軌跡k匿名集后發(fā)布軌跡數據，文獻[6]利用每一個采樣時間點的位置均值形成代表軌跡進行發(fā)布，也可在匿名集中選擇代表性軌跡進行發(fā)布，如文獻[31,32]。

經典的軌跡k匿名隱私保護方法是文獻[6]中利用定位系統(tǒng)等設備本身具有無法精確定位的特性提出的（）匿名模型，如圖2所示，也稱為NWA（Never Walk Alone，NWA）方法，算法利用貪心聚類算法形成軌跡k匿名集，如果在第一步軌跡預處理階段構成的等價類中，軌跡位置的采樣點構成的軌跡圓柱的半徑小于提前設定的不確定性閾值，則自動構成匿名集。否則，將利用空間轉換將 k條軌跡在每個時刻的位置點平移到軌跡圓柱體內構成軌跡k匿名集，由于運動軌跡自有的不確定性使得軌跡圓柱內k條軌跡變得不可區(qū)分，達到k匿名的效果。NWA方法在構造軌跡k匿名集的過程中，計算兩條軌跡之間的距離利用歐式距離函數，要求任何兩條軌跡的起始和終止時間必須相同，并且兩個軌跡對應的采樣點必須匹配，而現實中所研究的軌跡數據很少能滿足這樣的要求。所以，文獻[33]提出W4M 方法，改進NWA方法，在軌跡聚類階段不再使用歐式距離而是利用EDR（Edit Distance on Real sequences，EDR）[34]距離函數計算兩條軌跡之間的距離，該方法能解決在軌跡數據集聚類的過程中軌跡長度不匹配的問題。

圖2 軌跡不確定模型

以上方法利用了軌跡的不確定性，對軌跡數據泛化，但是這兩種方法構造的匿名集都不是在路網約束環(huán)境下。例如，雖然兩條軌跡的距離很近，但是卻彼此不可到達。影響了后續(xù)對軌跡數據挖掘的效率，由于軌跡數據發(fā)布的最終目的是要挖掘軌跡信息為生產生活服務。因此，文獻[31]將軌跡數據集的時間和空間進行泛化，利用對數距離（Log Cost Distance）作為判斷軌跡的相似性的度量，然后隨機選擇各個匿名區(qū)域采樣位置點進行軌跡重組，最終發(fā)布隨機重組后的原子軌跡，進而提高發(fā)布軌跡數據的利用效率。泛化原子軌跡tr1、tr2、tr3的過程如圖3所示：將tr1與tr2泛化為匿名軌跡tr*，將tr3與tr*泛化為匿名區(qū)域，從圖3可以看出5個位置點匹配成功，舍棄不匹配的位置點。軌跡重構和發(fā)布如圖4所示，泛化后的各個采樣時刻的位置點進行隨機重組，發(fā)布原子軌跡數據，這有利于對軌跡數據的分析挖掘。文獻[35]針對動態(tài)軌跡數據發(fā)布問題提出了一種基于自適應聚類的動態(tài)軌跡釋放方法，可以處理實時加入的軌跡數據，文中將軌跡進行分段處理，該方法共兩步：第一步是生成軌跡中的代表區(qū)域，可以解決由于移動速度和采樣頻率不同而引起的采樣時間不對齊的問題；第二步利用提出的適應度函數對第一步中產生的代表區(qū)域進行聚類產生泛化區(qū)域，每個泛化區(qū)域至少含有個位置點，兩個泛化位置區(qū)域內的位置點之間隨機組合，這樣就使得每兩個泛化的區(qū)域之間滿足k匿名。

以上的研究方法忽略了路網限制，文獻[36]提出基于前綴樹的軌跡k匿名算法，利用前綴樹對軌跡數據進行分類，然而這個方法有兩方面問題：一是路徑推理攻擊問題，當攻擊者具有一定的背景知識，容易和稀疏路徑相關聯(lián)進行路徑推理攻擊；二是構建前綴樹需要軌跡具有相同的前綴，但是現實中卻存在很多的軌跡不滿足具有相同的前綴，這使得利用前綴樹進行匿名的結果為空集。文獻[37]提出了針對路徑推理攻擊的軌跡隱私保護方法，假設攻擊者具有公開的路網信息，文中提出了C-Tree(Cluster-Tree)方法加速聚類過程，不僅保證發(fā)布的軌跡數據滿足軌跡k匿名，并且保證軌跡匿名結果滿足路網限制。文獻[38]首次提出利用頻繁路徑模式的方法進行軌跡隱私保護，提出了在路網環(huán)境下基于頻繁路徑的隱私保護方法，將軌跡分成若干個路段，移除不頻繁路段，提出新的算法尋找最頻繁路徑，構造k匿名集，選出組中與其余軌跡相似度最高的軌跡作為每組的代表軌跡進行發(fā)布，既滿足了路網約束，也避免了路徑推理攻擊。

圖3 軌跡tr1、tr2、tr3泛化過程

圖4 軌跡重組過程

3.4 基于差分隱私的軌跡隱私保護

軌跡K匿隱私保護雖然是比較主流的方法，但是卻容易招受到攻擊。如文獻[29]提出的二次聚類攻擊，雖然文獻中也提出了針對二次聚類攻擊的改進方法匿名模型以及基于該模型的聚類雜交隱私保護軌跡數據發(fā)布方法，但是在數據的利用效率方面卻不夠理想。

近年來，出現了以差分隱私[39,40]技術為基礎的軌跡數據發(fā)布方法，差分隱私由于其嚴謹的數學形式使其能夠保證無條件隱私，即使攻擊者有部分背景知識也無法進行推斷攻擊。

文獻[41]首次提出利用差分隱私方法解決大規(guī)模的軌跡數據發(fā)布的隱私保護問題，文中利用前綴樹的方式存儲軌跡數據，且利用拉普拉斯噪聲機制將樹中除了根節(jié)點外的每個節(jié)點加入噪音數值，并且針對獨立的噪音容易產生數據不一致現象，提出了利用前綴樹自身的特點對噪音數值進行了一致性處理，該方法面對軌跡數據的計數和頻繁模式查詢。文獻[42]首次提出以空間泛化為基礎的差分隱私算法，第一步利用差分隱私的指數機制將同一時刻的距離較近的采樣點位置合并；第二步利用差分隱私的拉普拉斯機制對軌跡數據添加噪聲數值。該方法解決了當前大部分研究方法中要求軌跡必須具有相同的前綴這一要求。路網中的移動軌跡一般都具有時間相關性，如果忽略這些相關性，將會產生隱私泄露，文獻[43]針對這一問題提出了基于 “位置集合”的差分隱私保護技術，并且提出了新的函數敏感度衡量方法以及有效地位置擾亂機制，通過對位置集合內的敏感位置進行隱藏達到隱私保護的目的。當忽略了軌跡隱私保護中多個用戶位置點之間的相關性問題時，容易遭受大量的推理攻擊，文獻[44]提出了能夠保護具有相關性的多個用戶位置隱私的差分隱私方法，利用隱馬爾科夫相似度量量化兩個用戶位置的相關性，然后設計滿足差分隱私的拉布拉斯噪聲機制發(fā)布軌跡數據。文獻[45] 針對空間計數查詢，提出兩種滿足差分隱私的軌跡數據發(fā)布方法：（1）在自由空間中，基于噪音四分樹的方法，對每個區(qū)域中的移動對象計數值添加噪音，發(fā)布每個時刻的添加噪音后的數值；（2）在路網空間中，用R-樹索引路網中的路段，對路段中的移動對象計數值添加噪音后發(fā)布。當在空間中進行計數查詢時，上述兩種方法比 k-匿名模型的隱私保護度更高，如表1所示是幾種軌跡數據隱私保護方法的比較。

表1 幾種軌跡數據隱私保護方法的比較

4 聚類分析方法

4.1 基于密度的聚類

密度聚類算法假定聚類結構能通過數據樣本點分布的緊密程度確定，密集數據點被稀疏區(qū)域分割，其思想是只要一個區(qū)域中的點的密度大于某個閾值，就把它加到與之相近的聚類中，每個數據點的影響可以用一個數學函數形式化建模，稱該函數為影響函數。描述數據點在其鄰域內的影響，數據空間的整體密度可以用所有數據點的影響函數建模，然后，簇可以通過識別密度吸引點數學確定，代表性算法是Dbscan算法[46]、Optics算法[47]和Denlue[48]算法。該聚類算法可以克服基于距離聚類只能發(fā)現類圓形的聚類缺點，可以發(fā)現任何形狀的聚類，并且對噪聲數據不敏感。

4.2 基于模型的聚類方法

每個簇都可以用參數概率分布數學描述，整個數據就是這些分布的混合，其中每個單獨的分布通常稱為成員分布。因此，可以使用m個概率分布的有限混合密度模型對數據進行聚類，其中每個分布代表一個簇，需要顧及概率分布的參數，使得分布最好地擬合數據，EM（期望最大化）算法是一種流行的迭代求精算法，可以用來求得參數的估計值。

比較常用的是高斯混合模型（GMM）聚類。假設每個簇的數據都符合高斯分布，所有數據點呈現的分布就是多個高斯分布疊加之后的結果，所以用m個高斯分布密度函數的線性組合對所要分類的數據進行擬合，理論上高斯混合模型可以擬合出任意類型的分布。如圖5所示是由兩個高斯分布組成的混合分布的例子，顯然利用高斯混合分布聚成兩類比較合適。

圖5 高斯混合分布

4.3 基于頻繁模式的聚類方法

頻繁模式是頻繁出現在數據集中的模式，如子序列或子結構，通過頻繁模式挖掘可以發(fā)現數據之間有意義的關聯(lián)和相關，發(fā)現頻繁模式起著至關重要的作用，對于數據分類、聚類等數據挖掘任務有幫助。頻繁模式聚類的思想是，發(fā)現的頻繁模式也可能預示簇，基于頻繁模式的聚類非常適用于高維數據。

5 未來展望

在大數據時代將會產生大量的軌跡數據，軌跡數據以離散的時間序列形式表示，是包含時間和空間信息的采樣序列，并且軌跡數據隨著采樣間隔具有顯著的差異，因此軌跡數據隱私保護將有很多挑戰(zhàn)性的問題需要解決。

5.1 基于混合模型的軌跡聚類分析

軌跡隱私保護中經常需要對軌跡進行聚類分析，需要對軌跡進行相似性度量。目前，大多數研究都利用歐氏距離、麥哈頓距離等度量兩條軌跡的相似性，因此在計算軌跡距離時就必須考慮軌跡采樣點之間的整體性。然而，異頻采樣使得軌跡之間不是同構的，且采樣點也不服從均勻分布，因此不得不插入采樣點或者刪除采樣點使得兩條軌跡的采樣頻率一致，舍棄采樣點有可能將重要信息舍棄，使后續(xù)軌跡數據利用效率低，添加采樣點也有可能將不需要被保護的位置添加進來，從而也使后續(xù)軌跡數據利用效率降低。

軌跡數據其自身具有統(tǒng)計規(guī)律性，數據服從一定的概率分布模式，傳統(tǒng)的基于K-means聚類等方法沒有充分考慮軌跡數據自身分布不均勻的特性，因此本文第四部分介紹的基于密度的聚類、基于混合模型的聚類都可以用來研究軌跡聚類分析。它們都是基于數據分布的統(tǒng)計學特征進行聚類分析的，在對軌跡數據聚類分析時，可以克服采樣頻率不一致的困難，遵從數據本身分布的統(tǒng)計特性。

5.2 基于頻繁模式挖掘的軌跡聚類分析

差分隱私可以防御攻擊者具有任意背景知識的攻擊，但是移動對象的軌跡具有相關性。當數據存在相關性時，差分隱私并不能保證無條件隱私。文獻[49]提出當數據具有相關性的時候，差分隱私不能保證無條件隱私。大數據環(huán)境下，面對大規(guī)模的軌跡數據，攻擊者可以關聯(lián)多數據源對匿名后的軌跡數據信息進行推理攻擊。前面提到文獻[38]首次提出利用頻繁路徑模式的方法研究軌跡隱私保護，避免了路徑推理攻擊，因此利用數據的頻繁模式挖掘的方法研究軌跡數據的隱私保護問題也是值得研究的問題。

5.3 個性化隱私保護研究

當前很多研究均認為所研究的軌跡數據都具有相同的隱私需求，設立同樣的隱私保護標準，但是軌跡數據是由不同的移動個體產生的，不同的場景和移動對象可能會有不同的隱私需求，雖然已經有研究者考慮個性化隱私保護方案。如文獻[50]基于時間劃分提出一種能滿足用戶差異性需求到軌跡隱私保護算法，建立隱私保護矩陣，根據不同軌跡不同時段不同地點設定不同的隱私保護參數，實現差異隱私保護，但是關于個性化隱私保護的研究還不多。因此，基于不同隱私需求的個性化隱私保護研究也使值得研究的問題。

5.4 基于語義位置的軌跡隱私保護研究

有時候不需要整條軌跡都進行隱私保護，只是部分敏感語義位置信息需要保護。文獻[51]提出基于語義軌跡的隱私保護方法，運動軌跡中用戶訪問和停留的位置更容易暴露用戶的隱私，軌跡中用戶經過的位置可以不做隱私保護，這將會提高發(fā)布軌跡數據的可用性，所以在軌跡隱私保護問題中應該考慮軌跡數據中的語義特征和攻擊者的不同背景，合理的處理敏感位置數據和非敏感位置數據，能夠更好的平衡隱私保護力度和數據的發(fā)布質量也是值得研究的問題。

6 結束語

隨著大數據時代的到來，以及定位設備的不斷發(fā)展，軌跡數據將會越來越多，對軌跡數據進行統(tǒng)計分析，在給人們生活帶來便捷的同時，也對人們的隱私信息造成了泄露的風險。雖然研究者們不斷提出軌跡隱私保護的新方法，但是同時越來越多的攻擊模式也將會被開發(fā)出來，所以需要不斷的完善軌跡隱私保護方法。本文總結了已有軌跡隱私保護的方法，并且對其進行了分析和比較，結合軌跡數據的統(tǒng)計分布特性，對未來軌跡隱私保護的研究方向進行了討論?？傊?，雖然研究者們對軌跡隱私保護已經做了很多的研究，但是仍有很多關鍵的問題需要更深入的研究和探索。