賈俊杰，秦海濤

(西北師范大學(xué)計算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

1 引言

無線定位技術(shù)的不斷發(fā)展和移動智能終端設(shè)備的不斷普及，使得基于位置的服務(wù)LBS(Location-Based Services)[1]成為了一個新興產(chǎn)業(yè)。移動對象在獲得多樣化位置服務(wù)的同時也面臨著諸多隱私信息暴露的風(fēng)險。例如，移動對象為獲得更好的位置服務(wù)需要向位置服務(wù)器發(fā)送自身的精確位置信息，這些位置信息將會被位置服務(wù)器以日志的形式記錄下來，一旦攻擊者以某種方式獲得移動對象的軌跡數(shù)據(jù)，對其進(jìn)行分析便可從中推斷出與移動對象相關(guān)的隱私信息，例如工作單位、收入情況和興趣愛好等。攻擊者進(jìn)一步通過其他關(guān)聯(lián)信息還可能獲得移動對象的社交關(guān)系，這就為移動對象的安全造成了極大的隱患。

近年來，為解決移動對象的軌跡隱私保護(hù)問題，已有許多方法被相繼提出。其中，軌跡K-匿名技術(shù)[1]的使用最為廣泛。軌跡K-匿名技術(shù)采用K-匿名原理[2,3]，將軌跡信息與移動對象之間1∶1的關(guān)系轉(zhuǎn)換為1∶K的關(guān)系，從而達(dá)到保護(hù)移動對象隱私信息的目的[4]。Gruteser等[5]最先將K-匿名技術(shù)應(yīng)用于位置隱私保護(hù)服務(wù)中，用一個包含至少K-1個移動對象的匿名區(qū)域代替移動對象的精確位置發(fā)送給位置服務(wù)器，使得攻擊者從匿名數(shù)據(jù)集中識別出真實移動對象的概率不大于1/K。該方法在一定程度上保護(hù)了移動對象的隱私信息，但不能滿足移動對象的個性化隱私需求。針對此問題，文獻(xiàn)[6]提出一種個性化隱私保護(hù)軌跡發(fā)布算法。該算法采用貪心聚類的等價類劃分思想對含有不同隱私需求的軌跡集合進(jìn)行個性化處理，在一定條件下滿足了移動對象的個性化隱私需求，但卻忽略了二次聚類攻擊依然會導(dǎo)致移動對象隱私信息泄露的問題。因此，文獻(xiàn)[7]提出了一種基于聚類雜交的隱私保護(hù)軌跡數(shù)據(jù)發(fā)布算法。該算法采用聚類雜交策略，對聚類分組后先進(jìn)行組間雜交，再進(jìn)行組內(nèi)擾亂，從而達(dá)到預(yù)防二次聚類攻擊的目的。但是，因軌跡進(jìn)行聚類雜交時存在一定的隨機(jī)性，會產(chǎn)生一些隨機(jī)軌跡，攻擊者通過已掌握的背景知識，便可以從匿名集中輕易識別出這些軌跡。針對文獻(xiàn)[7]的問題，文獻(xiàn)[8]提出一種基于移動對象真實軌跡的虛假軌跡生成方法。該方法采用聚類，選擇出具有相同行為模式的軌跡構(gòu)建虛假軌跡，解決軌跡隨機(jī)性問題，并通過構(gòu)建馬爾科夫模型減小背景知識對軌跡隱私的影響。文獻(xiàn)[8]方法在一定程度上解決了軌跡隨機(jī)性問題以及減小背景知識對隱私保護(hù)的影響，但卻不能對移動對象的動態(tài)移動軌跡進(jìn)行隱私保護(hù)。

現(xiàn)有的動態(tài)軌跡匿名算法大多從移動對象的單個軌跡出發(fā)進(jìn)行軌跡隱私保護(hù)，在尋找最優(yōu)解的過程中容易陷入局部最優(yōu)。而且在進(jìn)行軌跡匿名時大多采用隨機(jī)方法來生成虛假軌跡，使得生成的虛假軌跡具有一定的隨機(jī)性。針對此問題，基于遺傳算法GA(Genetic Algorithm)具有搜索全局最優(yōu)解的特性，本文提出基于遺傳算法的動態(tài)軌跡匿名算法，利用遺傳算法對當(dāng)前時間段內(nèi)的歷史軌跡建立軌跡行為模式，通過該模式對移動對象進(jìn)行軌跡預(yù)測，根據(jù)軌跡K-匿名技術(shù)對預(yù)測軌跡進(jìn)行虛假軌跡生成，以達(dá)到匿名的效果。在軌跡預(yù)測階段，根據(jù)預(yù)測軌跡實時更新軌跡行為模式，提高軌跡預(yù)測的準(zhǔn)確性，在一定程度上避免了隨機(jī)軌跡的出現(xiàn)，在對移動對象軌跡隱私保護(hù)的同時保證匿名數(shù)據(jù)的發(fā)布質(zhì)量。

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

2.1 軌跡

由于軌跡數(shù)據(jù)在時間、空間上的特殊性，所以對移動對象軌跡數(shù)據(jù)進(jìn)行軌跡預(yù)測或者隱私保護(hù)，大多是在時空模型上進(jìn)行的。通過對移動對象的軌跡數(shù)據(jù)進(jìn)行分析、挖掘，從而對移動對象周期性規(guī)律或?qū)崟r運行軌跡進(jìn)行預(yù)測以獲得移動對象的相關(guān)個體信息[9,10]。

一般情況下，移動對象的軌跡T可以表示為T={(x1,y1,t1)，(x2,y2,t2),…,(xn,yn,tn)}，其中,(xn,yn,tn)表示在tn時刻移動對象的地理信息(xn,yn)。而移動對象的軌跡又可以分為靜態(tài)軌跡和動態(tài)軌跡。

(1)靜態(tài)軌跡是指移動對象已經(jīng)停止運行后，收集到的軌跡數(shù)據(jù)，即移動對象的歷史軌跡。一般由第三方服務(wù)器或者移動對象通過收集、篩選后發(fā)布給相關(guān)研究機(jī)構(gòu)。

(2)動態(tài)軌跡是指移動對象正在運行且不斷增加新的位置序列的增量更新軌跡。一般是由移動對象通過移動終端設(shè)備向第三方服務(wù)器實時提供自身的位置信息，并獲得相應(yīng)的位置服務(wù)過程中發(fā)布的。

2.2 軌跡K-匿名

現(xiàn)有的軌跡K-匿名技術(shù)[1]采用K-匿名原理[2,3]，將移動對象與軌跡之間的1∶1關(guān)系轉(zhuǎn)換為一條軌跡信息與多個移動對象之間的1∶K關(guān)系。經(jīng)軌跡K-匿名處理后的匿名數(shù)據(jù)表，每個匿名組中每條軌跡與其他至少K-1條軌跡不可區(qū)分，從而降低移動對象隱私泄露的概率，提高數(shù)據(jù)安全性。

2.3 遺傳算法

軌跡數(shù)據(jù)是一種多特性、多變量共存的數(shù)據(jù)，因此對軌跡數(shù)據(jù)進(jìn)行隱私保護(hù)時需要在多個變量中尋求一個最優(yōu)解，而通用性強(qiáng)、魯棒性高的遺傳算法正好可以解決軌跡匿名尋求多變量最優(yōu)解這一問題[11]。遺傳算法是通過模擬自然界中生物的遺傳進(jìn)化過程并采用適者生存思想來搜索最優(yōu)解的算法[11]。算法搜索全局最優(yōu)解的過程是一個不斷迭代的過程，每一次迭代相當(dāng)于生物進(jìn)化中的一次循環(huán)，直到滿足算法的終止條件為止。但是，遺傳算法在其搜索過程中采用隨機(jī)搜索方法，因此通過遺傳算法得出的搜索結(jié)果存在一定的不確定性。通過一些相應(yīng)的改進(jìn)方法，可以有效地改善遺傳算法的局限性，在可控范圍的代價之內(nèi)取得最優(yōu)解[11]。

在遺傳算法中，問題的每一個有效解被稱為一條“染色體”，染色體的具體形式是一個使用特定編碼方式生成的編碼序列，編碼序列中的每一個編碼單元稱為“基因”。在本文中，遺傳算法的染色體就是移動對象的軌跡，基因則是移動對象軌跡中的位置點。

3 動態(tài)軌跡隱私保護(hù)

3.1 軌跡行為模式

移動對象的習(xí)慣性軌跡運動模式具有群體特征[12]，通過對移動對象的歷史軌跡數(shù)據(jù)進(jìn)行分析和挖掘便可從中獲得移動對象的軌跡行為模式，這種模式在一定程度上反映了移動對象在當(dāng)前時間段的出行規(guī)律。例如，通過提取Thomas Brinkhoffs生成器[13]模擬生成的某移動對象在一個月內(nèi)的軌跡數(shù)據(jù)，提取字段包括：移動對象ID、日期、軌跡起止時間、軌跡數(shù)據(jù)和語義數(shù)據(jù)，得到該移動對象的歷史軌跡數(shù)據(jù)，如表1所示。

Table 1 Example of trajectory data of moving object 表1 移動對象軌跡數(shù)據(jù)示例

在對移動對象的歷史軌跡數(shù)據(jù)進(jìn)行軌跡行為模式構(gòu)建時，為使得模式盡可能符合軌跡群體的特征，降低冗余數(shù)據(jù)對模式的影響，需要先對歷史軌跡數(shù)據(jù)進(jìn)行預(yù)處理。

(1)數(shù)據(jù)預(yù)處理。

為了建立遺傳算法的初始種群，首先，從移動對象的歷史信息中選擇某一段時間內(nèi)的軌跡；其次，利用混合編碼方式[14]將所選歷史軌跡進(jìn)行編碼。例如表1中移動對象1在時間段0821～0825(起始時間ti=01:00，結(jié)束時間tn=07:00)的一條軌跡T={(3,4),(2,2),(4,3),(5,4),(3,1),(5,6)}，由于位置屬性是整數(shù)，采用混合編碼后得到軌跡編碼序列F=(1,2,3,4,5,6)。

(2)軌跡行為模式構(gòu)建。

在本文中，利用遺傳算法尋找全局最優(yōu)解的特性，對移動對象的軌跡行為模式進(jìn)行構(gòu)建時，首先將某一固定時間段內(nèi)的歷史軌跡信息作為初始種群；其次從歷史軌跡中選擇出滿足適應(yīng)度策略的最優(yōu)相似軌跡進(jìn)行選擇、交叉、變異操作，迭代此過程直到選擇出軌跡片段重復(fù)率最大的n條軌跡(n≥1)，這n條軌跡在一定程度上反映了移動對象在該歷史時間段內(nèi)的出行規(guī)律，即軌跡行為模式。令Ti表示第i條軌跡，Tij表示第i條軌跡中第j個位置。軌跡行為模式構(gòu)建過程如下所示：

(1)將移動對象固定歷史時間段內(nèi)的軌跡數(shù)據(jù)進(jìn)行編碼作為染色體，生成初始種群，其中基因表示軌跡中的位置點。

(2)適應(yīng)度策略。在本文中，若軌跡Tr和軌跡Ts的軌跡片段重復(fù)的概率大于閾值τ，則認(rèn)為軌跡Tr和Ts相似，這樣的相似軌跡即為所選擇個體。

(3)選擇。通過輪盤賭方式選擇群體中滿足適應(yīng)策略的父代個體。

(4)交叉。利用交叉算子形成新的子代個體，并按照適應(yīng)度策略進(jìn)行篩選。

(5)變異。利用變異算子形成新的子代個體，并按照適應(yīng)度策略進(jìn)行篩選。

(6)重復(fù)(3)～(5)，直到收斂得到最優(yōu)個體，即代表移動對象行為規(guī)律的軌跡。

例如，根據(jù)表1，設(shè)定重復(fù)概率閾值τ≤3，利用算法得到最終軌跡T1={(3,4),(2,2),(4,3),(5,4),(3,1),(5,6)}，T2={(3,2),(4,1),(2,3),(1,4),(2,1),(5,2)}，T3={(2,2),(5,2),(1,3),(4,3),(5,4),(5,1)}，T4={(1,4),(3,2),(4,1),(3,1),(5,1),(4,2)}，T5={(5,1),(1,4),(2,3),(1,4),(5,1),(2,6)}，進(jìn)行軌跡網(wǎng)構(gòu)建后得到如圖1所示的軌跡網(wǎng)狀結(jié)構(gòu)，該軌跡網(wǎng)表示固定時間段內(nèi)的所有頻繁軌跡片段(邊)，除了起止時間，軌跡片段之間不考慮時序。

Figure 1 network圖1 軌跡網(wǎng)

為了得到移動對象軌跡行為模式，通過位置點所體現(xiàn)的語義信息，將圖1轉(zhuǎn)換為軌跡語義[15]網(wǎng)絡(luò)，如圖2所示，各位置點對應(yīng)的語義在移動對象軌跡(如表1所示)中出現(xiàn)的頻數(shù)如表2所示。

Figure 2 Trajectory semantic network圖2 軌跡語義網(wǎng)絡(luò)

Table 2 Semantic frequency table

設(shè)定軌跡語義頻數(shù)閾值3≤ρ≤5，得到移動對象在當(dāng)前時間段內(nèi)的軌跡語義網(wǎng)絡(luò)如圖3所示。

Figure 3 Trajectory semantic network (3≤ρ≤5)圖3 軌跡語義網(wǎng)絡(luò)(3≤ρ≤5)

根據(jù)圖3得到移動對象在該時間段內(nèi)的軌跡行為模式為(超市，醫(yī)院，工作單位，星巴克，加油站，醫(yī)院，超市，家)，“超市”和“家”分別為起止時間移動對象的位置語義，則圖1中的軌跡為該軌跡行為模式所蘊(yùn)含的軌跡。假設(shè)軌跡T1，T2，T3為移動對象在某一時間段內(nèi)的3條軌跡，則可以把它們按時序歸為一個軌跡組TRi，軌跡行為模式構(gòu)建如算法1所示。

算法1移動對象軌跡行為模式構(gòu)建(Modeal_Tra)

輸入：移動對象歷史軌跡數(shù)據(jù)D={T1,T2,…,Tn}。

輸出：移動對象軌跡行為模式T。

1.按時間順序?qū)進(jìn)行分組，得到m個軌跡組Dt={TR1,TR2,TR3,…,TRm};

2.T=?;

3.for(i=1 tom)

4.{

5. 初始化第i個軌跡組TRi：Initialize(TRi);

6. 根據(jù)遺傳算法選擇TRi中滿足適應(yīng)度策略的父代軌跡組TR′i：Fitness(TR′i);

7. 當(dāng)存在不滿足適應(yīng)度策略的軌跡TRi-TR′i時

8. {進(jìn)行交叉、變異：GA-operation(TRi-TR′i);

9. 選擇滿足適應(yīng)度策略的子代：Fitness(TR″i);

10. 將父代與子代合并，即TR′i+ =TR″i;}

11. 從TR′i中選擇出一條最優(yōu)個體T′i作為該軌跡組TRi的行為模式;

12.T+=T′i;

13.}

14.返回T。

3.2 動態(tài)軌跡預(yù)測

移動對象的動態(tài)軌跡是依賴于當(dāng)前軌跡或位置點而實時變化的，對下一時段軌跡進(jìn)行預(yù)測具有一定的現(xiàn)實意義。針對預(yù)測出的下一時段軌跡中的敏感信息進(jìn)行有效保護(hù)可避免移動對象的隱私泄露，而軌跡的敏感信息一般蘊(yùn)含在軌跡的語義信息中。

軌跡預(yù)測過程就是根據(jù)當(dāng)前移動對象已走的軌跡語義信息，去預(yù)測下一時段軌跡語義，利用下一時段軌跡語義可預(yù)測出軌跡行為模式中所蘊(yùn)含的軌跡。再將新增的預(yù)測軌跡加入歷史軌跡中，重新利用遺傳算法更新軌跡行為模式。文獻(xiàn)[8,16]將歷史軌跡信息作為背景知識，缺少對背景知識的動態(tài)更新。本文算法通過實時動態(tài)更新軌跡行為模式，不斷地充實背景知識，可提高軌跡預(yù)測的準(zhǔn)確性。

假設(shè)移動對象1某時間段的軌跡行為模式如圖3所示，其所蘊(yùn)含的軌跡如圖1所示，該時間段移動對象已走軌跡為{(2,2),(4,3),(5,4),(3,1)}，根據(jù)軌跡模式可以預(yù)測移動對象下一時段軌跡語義為(工作單位，醫(yī)院，超市)，根據(jù)圖1可知該軌跡語義所蘊(yùn)含的軌跡為T1={(3,1)，(4,1)，(2,3)，(4,3)，(5,1)}，T2={(3,1)，(5,4)，(4,3)，(2,2)}，T3={(3,1)，(5,1)，(4,3)，(2,3)，(4,1)}，移動對象的預(yù)測軌跡如圖4所示。

Figure 4 Trajectory prediction圖4 軌跡預(yù)測

對移動對象的動態(tài)軌跡進(jìn)行預(yù)測時，一般會采用均方根誤差RMSE判定移動對象真實軌跡點與預(yù)測軌跡點之間的誤差[9]，如式(1)所示：

(1)

其中，(xi,yi)為移動對象的真實位置，(x′i,y′i)為移動對象的預(yù)測位置，k表示軌跡中的位置點個數(shù)。

3.3 隱私保護(hù)

軌跡隱私是一種特殊的個體隱私，是指移動對象運行的軌跡本身就包含有敏感信息或者由軌跡信息可推導(dǎo)出與移動對象相關(guān)的個體隱私[1]。假設(shè)移動對象軌跡行為模式發(fā)生泄漏，攻擊者結(jié)合背景知識可對其接下來的行為軌跡進(jìn)行預(yù)測，進(jìn)而可能推斷移動對象軌跡隱私。因此，要保證預(yù)測軌跡中的敏感位置不被泄露，進(jìn)而保證軌跡模式中的敏感語義信息不被泄露。

表1中移動對象位置點(4,3)和(4,1)對應(yīng)的語義信息為醫(yī)院，攻擊者一旦獲得該信息后，通過事先獲知移動對象有不舒服的表現(xiàn)，便可大概率推斷出該移動對象生病的信息，因此，“醫(yī)院”作為敏感信息需要對其所蘊(yùn)含的敏感位置所處的軌跡進(jìn)行隱匿。

本文在對移動對象的動態(tài)軌跡進(jìn)行隱私保護(hù)時，根據(jù)預(yù)測軌跡間的最大距離為帶寬，按照軌跡K-匿名的方式從該帶寬內(nèi)選擇K條軌跡，使得預(yù)測軌跡被識別出的概率不大于1/K，以達(dá)到隱匿真實動態(tài)軌跡的目的。

軌跡間的距離如式(2)所示：

(2)

其中，(xi,yi)為移動對象的坐標(biāo)點，t1,t2表示對應(yīng)時刻，Dis為位置點間的距離。

如圖5所示，假設(shè)K=3,根據(jù)軌跡行為模式，在一定帶寬內(nèi)選擇K-1=2條軌跡，形成軌跡3-匿名組。

Figure 5 Trajectory 3-anonymous圖5 軌跡3-匿名

4 基于遺傳算法的動態(tài)軌跡匿名算法

4.1 算法描述

為防止移動對象動態(tài)運行軌跡泄露導(dǎo)致的自身隱私泄露問題，本文提出基于遺傳算法的動態(tài)軌跡匿名算法，隨著移動對象的動態(tài)移動，將預(yù)測軌跡實時加入初始軌跡種群，反復(fù)執(zhí)行下面3個步驟：

(1)以移動對象的真實歷史軌跡信息為基礎(chǔ)，通過遺傳算法從歷史軌跡信息中選擇出移動對象的軌跡行為模式；

(2)通過軌跡行為模式預(yù)測當(dāng)前移動對象的下一時段軌跡，將預(yù)測軌跡加入初始種群；

(3)對預(yù)測出的軌跡利用軌跡K-匿名技術(shù)隱匿軌跡，以達(dá)到隱匿移動對象實時位置或?qū)崟r運行軌跡的目的。

算法2移動對象的動態(tài)軌跡匿名(Hidden_Tra)算法

輸入：歷史軌跡數(shù)據(jù)集D={T1,T2,…,Tn},動態(tài)更新的軌跡數(shù)據(jù)Tg。

輸出：滿足軌跡K-匿名的軌跡數(shù)據(jù)D′。

1.D′←?;

2.將Tg加入到D中；

3.調(diào)用Modeal_Tra(D)返回軌跡行為模式T;

4.if(T包含敏感信息)

5. 根據(jù)遺傳算法從D中選擇出與T相似的K-1條軌跡并將T加入到D′中;

6.else不進(jìn)行隱匿，即D′ =D;

7.endif

8.返回D′。

4.2 準(zhǔn)確性度量

為檢測本文算法的性能，結(jié)合軌跡相似度[17]和匹配查詢結(jié)果來對預(yù)測軌跡進(jìn)行準(zhǔn)確性和隱匿效果的評價。軌跡相似度主要衡量移動對象的真實軌跡與預(yù)測軌跡之間的差異性，用于算法中軌跡預(yù)測階段。匹配查詢結(jié)果主要衡量移動對象的真實軌跡從匿名集中被識別出的概率，用于軌跡匿名階段。

定義1(軌跡相似度) 預(yù)測軌跡T′內(nèi)的任意位置點s，計算與s對應(yīng)的真實軌跡T內(nèi)的位置點的距離Dis，若Dis<φ(φ為軌跡相似距離閾值)且該2條軌跡的軌跡片段重復(fù)的概率大于閾值τ，則稱預(yù)測軌跡T′與真實軌跡T相似。

定義2(匹配查詢結(jié)果) 匿名表內(nèi)任一軌跡記錄Ts，計算Ts到真實軌跡T的軌跡距離Dis，若Dis大于相似距離閾值ξ，并且重合位置點個數(shù)小于給定閾值，則認(rèn)為該匿名軌跡存在隱私泄露。

由于本文采用先對移動對象的軌跡進(jìn)行預(yù)測，然后再對預(yù)測的軌跡進(jìn)行隱私保護(hù)的策略，所以需要結(jié)合軌跡相似度和匹配查詢結(jié)果來對軌跡匿名的不同階段進(jìn)行數(shù)據(jù)評價。

5 實驗結(jié)果與分析

本節(jié)將從軌跡命中率、軌跡誤差率、隱私保護(hù)有效性、軌跡相似度和匿名數(shù)據(jù)質(zhì)量幾個角度出發(fā)，對本文算法進(jìn)行驗證。通過軌跡命中率和軌跡誤差率來評測本文算法預(yù)測軌跡的有效性。隱私保護(hù)有效性和軌跡相似度用來評測經(jīng)過本文算法進(jìn)行軌跡隱匿后的移動對象隱私信息泄露的概率。匿名數(shù)據(jù)質(zhì)量用來衡量發(fā)布的匿名數(shù)據(jù)的有效性。

5.1 實驗數(shù)據(jù)與環(huán)境

實驗采用的數(shù)據(jù)由Thomas Brinkhoffs生成器[13]模擬德國奧爾登堡地圖生成。本文選取50 km×50 km區(qū)域內(nèi)1 000個時間片內(nèi)的10 000條軌跡構(gòu)成實驗數(shù)據(jù)集，其軌跡中相鄰軌跡點間的時間差為20 min。表3為實驗數(shù)據(jù)集參數(shù)。

實驗環(huán)境為Intel i5 3.4 GHz，4 GB內(nèi)存，Windows 64位操作系統(tǒng)，算法由eclipse 8.1和Matlab 2016a編寫。

Table 3 Experimental parameter setting表3 實驗參數(shù)設(shè)置

5.2 軌跡命中率

軌跡命中率指通過算法預(yù)測出的預(yù)測軌跡與移動對象真實運行軌跡匹配度達(dá)到一定閾值的次數(shù)。作為衡量一個軌跡預(yù)測算法準(zhǔn)確性的標(biāo)準(zhǔn)，通常命中率越高，則表示該軌跡預(yù)測算法準(zhǔn)確性越好。在本文中，選擇相同時間段內(nèi)具有相同背景信息的3 500條軌跡作為初始軌跡數(shù)據(jù)集，選擇文獻(xiàn)[9,10]中的算法作為參考，并與本文算法做對比實驗。實驗結(jié)果如圖6所示。

Figure 6 Trajectory hit rate圖6 軌跡命中率

如圖6所示，隨著軌跡數(shù)目的不斷增加，3種算法對移動對象的真實軌跡運行的命中率也呈現(xiàn)出不同的變化效果。在軌跡數(shù)目為0～1000時，本文的軌跡預(yù)測算法的軌跡命中率相比于其它2種算法的更高，這是因為本文算法是以移動對象的歷史運行軌跡為基礎(chǔ)，并結(jié)合遺傳算法尋找全局最優(yōu)解的特性可以較為快速地從軌跡數(shù)據(jù)集中預(yù)測出移動對象將要到達(dá)的軌跡位置點。但是，在起始區(qū)間內(nèi)，由于起始區(qū)間內(nèi)的軌跡數(shù)目較少，軌跡預(yù)測時的初始種群就會比較小，所以本文算法相比于文獻(xiàn)[9,10]中的算法的軌跡命中率就低一些。軌跡數(shù)目達(dá)到一定值時，移動對象歷史軌跡之間的關(guān)聯(lián)性也在逐漸增加，軌跡命中率也會出現(xiàn)一個短暫的下降趨勢。隨著軌跡數(shù)目逐漸增加，本文算法會結(jié)合移動對象軌跡之間的關(guān)聯(lián)性，調(diào)整歷史軌跡劃分規(guī)則，從而提高預(yù)測軌跡命中真實運行軌跡的概率。

5.3 軌跡相似度

軌跡相似度主要是用來評判移動對象真實運行軌跡與算法生成的軌跡之間的差異性。為驗證不同算法在相同條件下的移動對象預(yù)測軌跡、通過算法生成的匿名軌跡與真實運行軌跡之間的相似度，將本文算法與文獻(xiàn)[9，10，16]中的算法進(jìn)行對比。

首先，將從預(yù)測軌跡與移動對象真實運行軌跡這個角度出發(fā)，驗證不同軌跡預(yù)測算法在相同時間段內(nèi)預(yù)測軌跡之間的差異性，結(jié)果如圖7所示。

Figure 7 Similarity of predicted trajectory圖7 預(yù)測軌跡相似度

從圖7中可以看出，相比于其他3種算法，本文算法預(yù)測出的預(yù)測軌跡與移動對象真實運行軌跡的相似度較高。這是因為本文算法采用了遺傳算法尋找全局最優(yōu)解的特性，可以快速從移動對象歷史軌跡數(shù)據(jù)集中得到軌跡行為模式，從而預(yù)測出當(dāng)前時間段內(nèi)移動對象將要到達(dá)的位置點，并根據(jù)移動對象實時新增的軌跡位置點動態(tài)更新移動對象的軌跡行為模式，進(jìn)一步提高預(yù)測軌跡與移動對象真實運行軌跡之間的相似性。而文獻(xiàn)[9,10,16]中的算法卻沒有考慮移動對象實時新增位置點這一因素對預(yù)測軌跡的影響，從而使得預(yù)測出的預(yù)測軌跡與移動對象真實運行軌跡之間的相似性較低。

將本文算法與文獻(xiàn)[8,16]中的算法進(jìn)行實驗對比，在設(shè)定相同軌跡數(shù)目、長度和隱私需求的情況下，評測不同算法生成的匿名軌跡與真實運行軌跡之間的相似度，結(jié)果如圖8所示。

Figure 8 Similarity between anonymous trajectory and real trajectory圖8 匿名軌跡與真實軌跡相似度

如圖8所示，比較不同算法在相同匿名條件下生成的匿名軌跡與真實軌跡之間的相似性，本文算法在起始階段生成的匿名軌跡與移動對象真實軌跡相似性較低，這是因為在軌跡數(shù)目為200～800時，軌跡數(shù)目較少，遺傳算法進(jìn)行匿名軌跡構(gòu)建時的初始種群較小，因此本文算法的相似性較小，但隨著軌跡數(shù)目的不斷增加，初始種群不斷增大，相似性也逐漸上升。而當(dāng)軌跡數(shù)目達(dá)到一定閾值時，本文算法相比于其他幾種算法呈現(xiàn)出一定的優(yōu)勢，這是因為文獻(xiàn)[8,16]中的算法大多先對移動對象的歷史軌跡進(jìn)行聚類，然后進(jìn)行匿名軌跡構(gòu)建，沒有考慮對歷史軌跡信息的實時更新。

5.4 軌跡數(shù)據(jù)質(zhì)量

在軌跡數(shù)據(jù)發(fā)布中，既要保護(hù)移動對象的隱私信息不被泄露，又要保證通過算法匿名后的匿名數(shù)據(jù)集具有一定的可用性。根據(jù)這一特性，本文在對匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量進(jìn)行評估時分為軌跡隱私泄露概率和匿名數(shù)據(jù)質(zhì)量2部分，在評測軌跡數(shù)據(jù)質(zhì)量優(yōu)劣時，本文選擇文獻(xiàn)[16,18]中的算法來做對比實驗。

(1)軌跡隱私泄露。

通過軌跡隱私泄露概率對不同算法生成的匿名軌跡進(jìn)行驗證，實驗結(jié)果如圖9所示。

Figure 9 Disclosure probability of trajectory privacy圖9 軌跡隱私泄露概率

如圖9所示，在K值相同且具有相同背景知識的軌跡匿名數(shù)據(jù)集上的實驗結(jié)果中，本文算法相較于其它2種算法的軌跡隱私泄露概率較低。這是由于本文算法在進(jìn)行軌跡隱匿時，依據(jù)移動對象軌跡行為模式，提前對移動對象的動態(tài)軌跡進(jìn)行了預(yù)測，同時充分考慮了移動對象軌跡動態(tài)更新位置點這一因素對生成匿名軌跡的影響，提高了對預(yù)測軌跡匿名的具體指向，使得生成的匿名軌跡概化程度更好，降低了移動對象軌跡隱私泄露的風(fēng)險。

(2)匿名數(shù)據(jù)質(zhì)量。

對軌跡數(shù)據(jù)進(jìn)行匿名后的匿名數(shù)據(jù)集可用性越高，則證明該匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量越好[1]。為評估不同算法生成的匿名數(shù)據(jù)集的可用性，隨機(jī)選擇匿名數(shù)據(jù)集中的N條軌跡，在設(shè)定同一K值的前提下，比較其匿名數(shù)據(jù)集的可用性。實驗結(jié)果如圖10所示。

Figure 10 Anonymous data quality圖10 匿名數(shù)據(jù)質(zhì)量

如圖10所示，在同一匿名條件下，隨著軌跡數(shù)目的不斷增加，經(jīng)過匿名后的匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量也在逐漸提高，相比于文獻(xiàn)[16,18]中的算法，本文算法的匿名數(shù)據(jù)質(zhì)量相對較高，這是因為文獻(xiàn)[16,18]中的算法是以移動對象的歷史軌跡信息為基礎(chǔ)，沒有考慮移動對象的軌跡動態(tài)更新這一因素對數(shù)據(jù)質(zhì)量的影響。而本文算法在進(jìn)行匿名軌跡構(gòu)建時，充分考慮了動態(tài)軌跡實時更新這一因素對數(shù)據(jù)質(zhì)量的影響，并結(jié)合與其相關(guān)的軌跡語義信息，進(jìn)行軌跡K-匿名，這樣既保護(hù)了移動對象的軌跡隱私信息，又保證了匿名數(shù)據(jù)集具有較高的可用性。

6 結(jié)束語

針對現(xiàn)有的動態(tài)軌跡隱私保護(hù)算法在對移動對象的動態(tài)軌跡進(jìn)行隱私保護(hù)時，大多采用先對移動對象的歷史軌跡進(jìn)行聚類，而后進(jìn)行軌跡隱匿，但沒有考慮實時增加的新位置或者新軌跡對動態(tài)軌跡的影響問題，本文提出了一種基于遺傳算法的動態(tài)軌跡匿名算法。該算法利用遺傳算法對移動對象的軌跡行為模式進(jìn)行構(gòu)建，以該行為模式為基礎(chǔ)，對移動對象的動態(tài)軌跡進(jìn)行預(yù)測，通過軌跡K-匿名技術(shù)生成匿名軌跡對預(yù)測軌跡進(jìn)行隱匿，從而達(dá)到保護(hù)移動對象動態(tài)軌跡隱私信息的目的。該算法在一定程度上解決了移動對象動態(tài)軌跡隱私泄露的問題，但因遺傳算法中初始種群選擇這一因素的影響，依然會導(dǎo)致本文算法在算法效率上有所欠缺，這將是下一步亟待解決的問題。