基于信息熵抑制的軌跡隱私保護方法

汪逸飛，羅永龍，俞慶英，劉晴晴，陳 文

(1.安徽師范大學(xué) 計算機與信息學(xué)院，安徽 蕪湖 241003； 2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全安徽省重點實驗室，安徽 蕪湖 241003)(*通信作者電子郵箱wyf927@ahnu.edu.cn)

0 引言

近年來，隨著智能設(shè)備的興起和全球定位系統(tǒng)(Global Positioning System, GPS)等衛(wèi)星導(dǎo)航技術(shù)的快速發(fā)展，人們越來越多地使用定位技術(shù)、路徑推薦以及基于位置的社交網(wǎng)絡(luò)等位置服務(wù)(Location Based Service, LBS)技術(shù)，由此產(chǎn)生了大量的移動軌跡數(shù)據(jù)。一方面，這些數(shù)據(jù)有利于研究者對其分析從而挖掘出有用價值；另一方面，這些軌跡數(shù)據(jù)里包含了大量的用戶敏感信息，如果不經(jīng)任何處理直接發(fā)布，會導(dǎo)致用戶隱私的泄露。因此，數(shù)據(jù)發(fā)布者在發(fā)布數(shù)據(jù)時，既要保護用戶的隱私信息，又要最大化地保證匿名數(shù)據(jù)的可用性?，F(xiàn)如今用戶的軌跡隱私保護問題已成為了研究者和用戶重點關(guān)注的問題[1-3]。

目前，軌跡隱私保護技術(shù)主要集中于假數(shù)據(jù)法和泛化法，已取得大量研究成果[3]，但傳統(tǒng)的軌跡隱私保護法并不適用于高維軌跡數(shù)據(jù)的隱私保護。針對高維軌跡所體現(xiàn)出的高維性、稀疏性以及有序性等問題，國內(nèi)外學(xué)者提出使用抑制法能較好地解決這個問題，軌跡抑制法是指在軌跡發(fā)布前去除某些敏感或頻繁訪問的位置。Terrovitis等[4]假設(shè)攻擊者擁有部分真實軌跡，提出在軌跡發(fā)布時抑制處于敏感區(qū)域的位置，使軌跡泄露的風(fēng)險不高于用戶設(shè)置的隱私保護閾值，然而，如何找到合理的軌跡抑制位置從而減少抑制法帶來的數(shù)據(jù)損失仍然是軌跡抑制隱私保護法有待解決的一個關(guān)鍵問題； Chen等[5]基于LK(Length K-anonymity)模型尋找出所有違反模型的軌跡序列的思想，并考慮到全局抑制軌跡序列會造成較大的數(shù)據(jù)損失，進一步提出局部軌跡抑制保護算法；Komishani等[6]考慮到敏感屬性相似性攻擊問題，提出了泛化敏感屬性的隱私保護算法；趙婧等[7]基于軌跡頻率，通過對有問題的軌跡添加假數(shù)據(jù)和利用隱私關(guān)聯(lián)度和數(shù)據(jù)效用之間的關(guān)系對軌跡數(shù)據(jù)進行處理，提出了兩種軌跡抑制的隱私保護方案；Ghasemzadeh等[8]基于概率流量圖，通過全局與局部抑制對乘客流量進行隱私保護。然而，當(dāng)前采用的抑制法依然存在不足：由于隱私保護方不能確切知道攻擊者掌握的背景知識，僅通過抑制不滿足設(shè)定閾值的實例，可能會增大攻擊者識別某些敏感地區(qū)的概率；同時由于抑制操作的盲目性會造成大量的數(shù)據(jù)損失，影響高維軌跡數(shù)據(jù)的發(fā)布質(zhì)量。

針對上述問題，本文在文獻[8]的基礎(chǔ)上，針對傳統(tǒng)軌跡抑制法造成的較大數(shù)據(jù)損失的問題，提出了一種基于信息熵抑制的軌跡隱私保護算法(Trajectory Privacy-preserving algorithm based on Information Entropy, TP-IE)。本文主要工作如下：首先，對當(dāng)前數(shù)據(jù)集建立基于熵的流量圖，計算每一條路徑中時空點的熵值；然后基于每個樹節(jié)點的信息熵設(shè)計消除軌跡違反序列的花費代價函數(shù)，迭代選擇序列進行抑制操作，實現(xiàn)軌跡的匿名發(fā)布；最后，重新設(shè)計了比較抑制前后流量圖相似性的算法，提出了一個計算隱私收益的函數(shù)。通過詳細的實驗對比，證明了本文算法具有更高的應(yīng)用價值。

1 相關(guān)定義

定義1 軌跡。軌跡是指移動對象的位置信息按照時間順序排序得到的序列。通常情況下，軌跡可以表示為tr:(ID,(loc1t1→loc2t2→…→lociti))，其中ID為用戶標(biāo)識符，lociti被稱作為tr軌跡的一個時空點，表示移動對象在ti時刻的位置為loci，|tr|為軌跡的長度，即軌跡中不同時空點的個數(shù)。用T={tr1,tr2,…,trn}表示由n條軌跡數(shù)據(jù)形成的軌跡數(shù)據(jù)集。

定義2 身份鏈接攻擊[5]。身份鏈接攻擊是指攻擊者為獲取用戶的隱私信息，根據(jù)所掌握的部分用戶信息和對應(yīng)的用戶身份信息發(fā)起的攻擊。

定義3 LK模型[5]。假設(shè)L為背景知識的最大長度，即攻擊者掌握用戶軌跡序列包含的最多時空點個數(shù)，滿足LK模型的序列q需要滿足下列條件：

1)|T(q)|≥K，其中T(q)表示軌跡包含q， |T(q)|表示包含q的軌跡條數(shù)，其條數(shù)至少為K條;

2) 0<|q|≤L，|q|表示序列q包含的軌跡時空點個數(shù)，至多為L個。

定義4 違規(guī)序列[5]。假設(shè)q為軌跡數(shù)據(jù)集中的軌跡序列且長度滿足0<|q|≤L，當(dāng)且僅當(dāng)|T(q)|

定義5 最小違規(guī)序列[5]。假設(shè)q為違規(guī)序列，q的所有可能子序列都不是違規(guī)序列，則稱q為最小違規(guī)子序列(Minimal Violating Sequence, MVS)。

定義6 基于熵的流量圖?；陟氐牧髁繄D是指由一系列時空點組成的有向圖，它采用樹作為存儲結(jié)構(gòu)，可表示為三元組ET=〈G,PATH,Root(ET)〉，其中G表示該流量圖節(jié)點的集合，PATH表示該流量圖路徑的集合，Root(ET)表示流量圖的根節(jié)點。

在基于熵的流量圖中，圖的路徑集合PATH可用{Path1,Path2,…,Pathi,…,Pathn}表示，其中Pathi表示流量圖中的第i條路徑；每個節(jié)點(除了根節(jié)點)只有唯一的父親節(jié)點，對于除根節(jié)點外的任意節(jié)點d∈G，可用d=〈location,time,ent,count,children〉表示，其中l(wèi)ocation代表該節(jié)點的位置，time代表該節(jié)點的時間，ent代表該節(jié)點的時空點熵(如定義7所述)，count表示該節(jié)點的孩子節(jié)點的分支數(shù)，children代表該節(jié)點的孩子節(jié)點。

定義7 時空點熵。時空點熵是指時空點信息量的大小。對于除根節(jié)點外的任意節(jié)點d∈G，假設(shè)d的上一個節(jié)點轉(zhuǎn)移到當(dāng)前節(jié)點的概率為p，時空點熵H(d)為：

H(d)=-plgp

(1)

表1列舉了8位乘客的軌跡路徑，其中每條軌跡由一系列的時空點組成。每個時空點的形式為(lociti)，表示乘客在ti時刻的位置為loci。例如：“a1”表示在1時刻處于位置“a”，“c3”表示在3時刻處于位置“c”。

表1 原始軌跡數(shù)據(jù)集示例

根據(jù)表1中乘客的原始軌跡集，可以建立如圖1所示的乘客概率流量圖。轉(zhuǎn)移概率p(dx→dy)表示由dx移動到dy的乘客比例，如圖1所示，50%的乘客在經(jīng)過a1和b2后前往e5。

圖1 基于熵的流量圖

2 基于信息熵抑制的軌跡隱私保護方法

傳統(tǒng)的軌跡抑制法通過假設(shè)攻擊者的背景知識，抑制不滿足于設(shè)定閾值的時空點或軌跡序列以達到隱私保護的目的。文獻[5]通過假設(shè)攻擊者最大的背景知識，建立如定義3所示的LK模型，枚舉出軌跡數(shù)據(jù)中所有違反模型的違規(guī)序列，然后構(gòu)建合理的花費代價函數(shù)計算抑制違規(guī)序列的代價，局部抑制時空點以達到隱私保護的目的。文獻[8]針對乘客客流分析問題，在文獻[5]的基礎(chǔ)上，通過建立乘客流量圖重新設(shè)計消除違規(guī)序列的花費代價函數(shù)，以達到保護乘客隱私的同時最大化地保證客流分析的信息質(zhì)量的目的。然而上述方案依然存在以下問題：1)采用抑制法對違規(guī)序列處理時，沒有考慮時空點之間的轉(zhuǎn)移概率，通往下一個時空點轉(zhuǎn)移概率值較高或波動較大的時空點，對用戶的隱私威脅更加嚴(yán)重，應(yīng)當(dāng)優(yōu)先處理；2)在處理違規(guī)序列時，由于僅僅考慮了時空點數(shù)量對隱私保護的影響，導(dǎo)致限制發(fā)布的數(shù)據(jù)較多，增加了數(shù)據(jù)損失。

針對上述問題，本文基于LK模型，結(jié)合信息熵度量的思想提出了基于信息熵的軌跡抑制法。

2.1 信息熵

信息熵是1948年Shannon[9]借鑒熱力學(xué)概念，提出的衡量信息量大小(信息不確定度)的概念，解決了對信息的量化度量問題。

信息熵常常用于表示某種特定信息的出現(xiàn)概率，一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂,信息熵就越高。文獻[10]通過建立基于信息熵的無向圖來度量軌跡隱私，攻擊者對用戶軌跡隱私攻擊的主要目的是要挑選出用戶出行概率最大的軌跡：如果攻擊者認(rèn)為特定用戶每條可能的運動軌跡的概率相等，那么系統(tǒng)越混亂，攻擊者難以攻擊；如果每條可能的運動軌跡的概率差別很大，那么表示系統(tǒng)越有序，則易遭受到攻擊，因此，在基于熵流量圖里，抑制法在選取合理的抑制位置時，應(yīng)當(dāng)盡可能保留信息熵值大的樹節(jié)點，一方面可以減少信息損失，另一方面增加了抑制后數(shù)據(jù)的隱私保護性。

2.2 隱私保護算法—— TP-IE

本文提出了一種基于信息熵的軌跡抑制隱私保護算法(TP-IE)。TP-IE是基于文獻[5]提出的LK模型重新設(shè)計的隱私保護算法，其算法設(shè)計的主要思路為：首先，對軌跡數(shù)據(jù)建立了如圖1所示的基于信息熵的流量圖，利用熵值來衡量軌跡時空點的信息量；其次，基于LK模型枚舉出軌跡數(shù)據(jù)中的敏感位置點，即最小違規(guī)序列，結(jié)合信息熵建立合適的花費代價函數(shù)(定義9)，通過函數(shù)計算抑制敏感位置點的最低代價；最后，選取合理的抑制方式(局部抑制或全局抑制)對原始數(shù)據(jù)集中包含敏感點的序列進行抑制，直到軌跡數(shù)據(jù)集中的所有序列均滿足LK模型。TP-IE不同于以往的軌跡匿名方法，其優(yōu)點主要在于：1)結(jié)合信息熵值對時空點進行度量，有效地考慮到了時空點轉(zhuǎn)移概率的變化，對于某些轉(zhuǎn)移概率相差較大即熵值較低的點加以抑制，并在抑制過程中最大化保留熵值較大的點；2)TP-IE是通過求解隱私收益與數(shù)據(jù)實用性之間的關(guān)系來對軌跡數(shù)據(jù)進行抑制。在每次進行抑制的過程中，由于抑制的時空點都是利用花費代價函數(shù)計算出的最優(yōu)解，從而增加了匿名處理后的數(shù)據(jù)實用性和隱私收益。為了驗證算法的實用性，本文基于抑制前后的時空點熵的變化，設(shè)計了一個比較熵的流量圖的相似性算法來衡量經(jīng)過抑制處理后數(shù)據(jù)集的實用性。

LK模型枚舉出最小違規(guī)序列，通過抑制最小違規(guī)序列達到軌跡隱私保護的目的[5]。為了減小序列抑制帶來的信息損失，考慮到各序列q的實用價值，本文通過建立基于信息熵的流量圖重新設(shè)計了消除q的花費代價函數(shù)。

定義8 Info值。Info(d)是用來衡量時空點d在軌跡數(shù)據(jù)集以及流量圖中的信息質(zhì)量的值，Info(d)定義為：

Info(d)=(Hα(d)×α(d)+Hβ(d)×β(d))×γ(d)

(2)

其中：α(d)表示流量圖中相同節(jié)點d的數(shù)目之和，β(d)表示d在流量圖里的孩子節(jié)點分支數(shù)目之和，γ(d)表示原始數(shù)據(jù)集里含有d的路徑數(shù)之和，Hα(d)表示d在流量圖里的相同節(jié)點的時空點熵值和，Hβ(d)表示d點的孩子節(jié)點時空點熵值和。

示例1 如圖1所示，α(b2)=3因為流量圖里有3個b2的節(jié)點，β(b2)=5因為流量圖里的b2節(jié)點共有5個分支，γ(b2)=6因為原始數(shù)據(jù)集T里有6條包含b2的路徑，由式(1)可得出Hα(b2)=0.15，Hβ(b2)=0.56，則可由式(2)得出Info(b2)的值。

定義9 Score值。根據(jù)d的抑制方式，定義一種花費代價函數(shù)來計算消除d時空點的花費代價，如式(3)所示:

Score(d)=PrivGain(d)/Info(d)

(3)

其中PrivGain(d)表示消除d后MVS減少的個數(shù)。

TP-IE主要分為兩部分：第1部分在原始軌跡數(shù)據(jù)集上生成軌跡流量圖，遍歷流量圖中每個時空點，計算每個時空點的Info值，如算法1所述；第2部分獲取軌跡數(shù)據(jù)集中的最小違規(guī)序列并對最小違規(guī)序列進行時序抑制序列方式判斷，選取局部抑制或全局抑制對其抑制處理，如算法2所述。

算法1首先通過原始數(shù)據(jù)集T生成基于熵的流量圖ET；然后遍歷熵的流量圖中的每個節(jié)點，如果流量圖中存在時間、位置相同的時空點，分別計算它們的α(d)、β(d)、Hα(d)、Hβ(d)(第1)～11)行)；接著統(tǒng)計流量圖里包含時空點d的路徑數(shù)，計算出γ(d)(第12)～16)行)；根據(jù)上述值計算出每個時空節(jié)點的Info(d)，返回Info值(第17)～19)行)。

算法1 計算每個時空點的Info值—— GetInfo。

輸入 原始軌跡集T；

輸出 時空點的信息質(zhì)量Info。

1)

Generate flowgraphETfrom databaseT;

2)

for eachdinGdo

3)

α(d),β(d),γ(d),Hα(d),Hβ(d)均初始化為0;

4)

for eachd′ inGdo

5)

ifd.location==d′.location&&d.time==d′.timethen

6)

α(d)←α(d)+1;

7)

Hα(d)←Hα(d)+d′.ent;

8)

β(d)←β(d)+d′.count;

9)

Hβ(d)←Hβ(d)+d′.children.ent;

/*孩子節(jié)點的時空點熵之和*/

10)

end if

11)

end for

12)

for eachpathinPathdo

13)

ifpathcontainsdthen

//如果路徑中包含d

14)

γ(d)←γ(d)+1;

15)

end if

16)

end for

17)

Info(d)=(Hα(d)×α(d)+Hβ(d)×β(d))×γ(d);

18)

end for

19)

return Info

算法2是序列抑制階段，首先調(diào)用文獻[5]提出的MVS算法生成最小違規(guī)序列，然后根據(jù)算法1調(diào)用每個節(jié)點的Info值，由定義9建立出MVS的得分表(Score_table)(第1)～9)行)。接著，迭代選擇得分表中最高分的時空點p(第10)～11)行)，根據(jù)時空點p抑制方式的不同采取不同的操作：如果抑制方式是局部抑制，則將包含p的MVS放入到集合V′中，循環(huán)從V′中選取序列m，在軌跡數(shù)據(jù)集T中對所有包含m的實例抑制其中的時空點p(第12)～14)行)；如果抑制方式是全局抑制，則刪除軌跡數(shù)據(jù)集中的所有的時空點p(15～18行)。最后更新MVS和 Score_table中的所有時空點得分并檢查各時空點的抑制方式是否發(fā)生改變；重復(fù)上述操作，直到Score_table為空(第19)～22)行)。

如表1所示，假設(shè)K=2，L=2時，{c3 → e5,b2 → e6,e9}為表中的MVS序列集合的一部分。本文抑制目的為消除原始軌跡數(shù)據(jù)集中的所有MVS；故通過定義9算出所有MVS的得分值，降序排列。假設(shè)c3為得分值最高的時空點，則在原始軌跡數(shù)據(jù)集中尋找所有包含c3的軌跡實例，采取全局抑制或者局部抑制的方式[5]抑制時空點c3，直到原始數(shù)據(jù)集里不存在包含c3的MVS序列；迭代進行直到MVS序列集合為空集。

算法2 對MVS序列進行抑制處理—— Sequence-suppression。

輸入 原始數(shù)據(jù)集T，閾值L，K；

輸出 滿足LK模型的軌跡數(shù)據(jù)集T′。

1)

GenerateMVS(T) by MVS algorithm;

2)

GenerateInfo(T) by GetInfo algorithm;

3)

for eachdinGdo

4)

for eachpinMVS(T) do

5)

ifd.location==p.location&&d.time==p.time

6)

BuildScore_tablein descending order based on Eq.(3);

7)

end if

8)

end for

9)

end for

10)

whileScore_table≠? do

11)

select a spatio-temporal pointpwith the highest score fromScore_table;

12)

ifpis a local suppression point then

13)

V′←{m′|m′∈MVS,p∈m∧T(m′)=T(m)};

14)

Suppress the instances ofdinT(m);

15)

else

16)

V′←MVS(p);

17)

Suppress all instances ofpinT;

18)

end if

19)

Update theScore_table;

20)

MVS←MVS-V′;

21)

end while

22)

T′←the suppressedT

2.3 數(shù)據(jù)實用性比較

軌跡數(shù)據(jù)經(jīng)過匿名處理后，軌跡數(shù)目會減少，同時由于轉(zhuǎn)移概率的變化，軌跡流量圖會發(fā)生改變。文獻[8]設(shè)計了比較匿名前后流量圖變化的算法，但并未將轉(zhuǎn)移概率的變化考慮在內(nèi)。為了評測經(jīng)過抑制法處理后的軌跡數(shù)據(jù)集的數(shù)據(jù)實用性，本文在文獻[8]的基礎(chǔ)上重新設(shè)計了流量圖比較算法，其目的是為了驗證抑制前后流量圖結(jié)構(gòu)未發(fā)生明顯變化且軌跡數(shù)據(jù)挖掘性沒有明顯降低。

首先，匿名前后流量圖中的所有節(jié)點都是按照時間、地點排序，然后按次序提取G與G′中的時空點d與d′(第1)～3)行)：如果d與d′的時間、位置均相等，那么d與d′視作相同節(jié)點，并計算出它們的aSum、bSum、cSum、vSum、wSum、uSum(第5)～14)行)；如果β(d)=0，即d為流量圖里的葉子節(jié)點的值，由于β(d)為計算bSum時的分母，所以算法跳過此次除法，并使用i對β(d)=0計數(shù)(第11)～16)行)，最后在計算相似性時流量圖應(yīng)減去葉子節(jié)點的數(shù)值(第22)行)；接下來對vSum,uSum,wSum進行歸一化記作svSum、suSum、swSum(第17)～21)行)，最后第23)行返回相似性φ的值。

算法3 流量圖比較——ComFlowgraph。

輸入 軌跡流量圖ET，匿名后流量圖ET′；

輸出 匿名前后軌跡相似性φ。

1)

G←{d|d∈ET};

2)

G′←{d|d∈ET′};

3)

SelectGandG′ based on time and location;

4)

i←0;

5)

for eachd∈Gdo

6)

for eachd′∈G′ do

7)

ifd=d′ then

8)

vSum←vSum+[Hα(d′)/Hα(d)];

9)

wSum←wSum+[H?(d′)/H?(d)];

/*根節(jié)點到當(dāng)前節(jié)點的時空點熵和*/

10)

aSum←aSum+[α′(d)/α(d)];

11)

cSum←cSum+[γ′(d)/γ(d)];

12)

ifβ(d)≠0 then

13)

bSum←bSum+[β′(d)/β(d)];

14)

uSum←uSum+[Hβ(d′)/Hβ(d)];

15)

else

16)

i←i+1;

17)

end if

18)

end if

19)

vSum,uSum,wSum歸一化為svSum,suSum,swSum;

/*歸一化*/

20)

end for

21)

end for

23)

returnφ

2.4 TP-IE時間復(fù)雜度

TP-IE首先生成軌跡流量圖，計算各節(jié)點的時空點熵；然后基于LK模型生成MVS序列，計算每個時空點Score值，這部分最好情況下的時間復(fù)雜度為O(|s|2)，最壞的情況下的時間復(fù)雜度為O(|s|2|T|)，其中|s|為軌跡數(shù)據(jù)集的時空點個數(shù)，|T|為軌跡數(shù)據(jù)集路徑數(shù)；最后序列抑制階段會為每個MVS序列的消除都掃描一次數(shù)據(jù)集，所以其最好和最壞的情況下時間復(fù)雜度均為O(|s|2|T|)[5]，因此，TP-IE算法最好情況下的時間復(fù)雜度為O(|s|2)，最差情況下的時間復(fù)雜度為O(|s|2|T|)。第2部分比較流量圖相似性，時間復(fù)雜度為O(|s|2)。

2.5 TP-IE安全性分析

2.5.1 LK隱私模型有效

由于攻擊者掌握用戶的部分信息和對應(yīng)的用戶身份信息，所以攻擊者可以根據(jù)這些局部信息發(fā)起身份鏈接攻擊，進而推斷出用戶的身份。文獻[5]指出傳統(tǒng)k匿名模型針對高維軌跡數(shù)據(jù)的隱私保護需花費極大代價，因此高維軌跡隱私保護模型需要限定攻擊者的背景知識不超過L，由定義3可知，LK模型可保證用戶在受到身份鏈接攻擊時被成功識別的概率≤1/k，故LK模型有效。

2.5.2 TP-IE實用性分析

TP-IE經(jīng)過對原始流量圖進行隱私保護處理后，流量圖中節(jié)點的轉(zhuǎn)移概率會發(fā)生變化[8]。式(2)結(jié)合信息熵值測量流量圖中節(jié)點的信息質(zhì)量，式(3)定義的花費代價函數(shù)實際上是通過求出實例損失與信息質(zhì)量的最優(yōu)解來抑制時空點。經(jīng)過每一次迭代處理，信息質(zhì)量較低且在原始軌跡中實例較少的時空點得到抑制；信息質(zhì)量較大且包含實例數(shù)多的時空點得以保留，從而在提高隱私收益的同時減少了抑制法帶來的數(shù)據(jù)損失。

3 衡量標(biāo)準(zhǔn)

定義10 數(shù)據(jù)損失率(Utility Loss, UL)。數(shù)據(jù)損失率是指原始數(shù)據(jù)集經(jīng)過抑制處理后信息損失的值，記作UL。原始軌跡集的軌跡數(shù)目記作|T|,匿名后的軌跡集數(shù)目為|T′|，則數(shù)據(jù)集損失率UL計算公式為：

(4)

傳統(tǒng)抑制法用損失率來衡量信息損失，但單一的損失率只考慮到數(shù)據(jù)發(fā)布前后軌跡數(shù)目的變化，未曾考慮到抑制前后軌跡數(shù)據(jù)集信息增益的變化。本文基于文獻[10]提出的位置隱私度量方法，通過信息熵變化重新定義信息損失值。

定義11 隱私收益。隱私收益是指原始數(shù)據(jù)經(jīng)過匿名處理后增加的信息復(fù)雜度，記為HL。原始流量圖里的節(jié)點熵值和記為|V|，匿名后的流量圖節(jié)點熵值和記為|V′|，則隱私收益HL的計算公式為：

(5)

4 實驗與分析

4.1 實驗環(huán)境及數(shù)據(jù)集

實驗硬件環(huán)境為CPU為Core i5-6500 CPU 3.20 GHz處理器、8 GB內(nèi)存。本文使用C#語言在Microsoft Windows 10平臺上進行實驗?zāi)M。本文采用的是一個模擬地鐵交通運輸系統(tǒng)的數(shù)據(jù)集Metro200k[8]，擁有20萬乘客在24 h內(nèi)行駛于29個車站所形成的200 000萬條軌跡記錄，數(shù)據(jù)集大小為12 359 KB。

該數(shù)據(jù)集中每行數(shù)據(jù)包含用戶身份及一段時間內(nèi)的用戶出行軌跡，經(jīng)過對原始軌跡的處理，將原始數(shù)據(jù)轉(zhuǎn)化為時間戳形式的軌跡序列，具體格式如表1所示。

4.2 實驗結(jié)果分析

高維軌跡隱私保護一般用隱私保護度和數(shù)據(jù)損失率來評價算法效率。本節(jié)將TP-IE同文獻[5]和文獻[8]提出的算法進行比較。文獻[8]通過設(shè)置不同參數(shù)來測試算法的實用性，本文選取文獻[8]實驗效果最好的兩組參數(shù)。后文實驗圖中A、B組分別包含文獻[8]取兩組參數(shù)時的實驗效果。其中A組為wα=wβ=wγ=wδ=0.25，記作參數(shù)Ⅰ；B組參數(shù)wα=0.5，wβ=0.3，wγ=0.2，wδ=0，記作參數(shù)Ⅱ，其中wα,wβ,wγ,wδ表示不同的權(quán)值。

4.2.1 相似性

圖2展示參數(shù)k對匿名后流量圖的相似性影響。流量圖相似性變化主要取決于兩點：1)抑制軌跡時空點的數(shù)量；2)時空點熵值變化。當(dāng)k=60時，TP-IE匿名后的流量圖相似性明顯高于文獻[5]和文獻[8]提出的兩種方法。隨著k值增加，軌跡抑制法抑制處理的數(shù)據(jù)點越多，流量圖相似性降低；當(dāng)k值增加到一定值時，算法將執(zhí)行更多的全局抑制，因此相似性在逐漸達到平衡值會急劇下降。與文獻[5]與文獻[8]相比，由于時空點熵值較大的點保留更多，數(shù)據(jù)集的實用性也會更大。如圖2所示，TP-IE在相同的匿名參數(shù)取值下相似性始終比另外兩種方式高，所提方法在相似性度量上比文獻[5]提出的方法提高了約27%, 比文獻[8]方法提高了約22%。由此可以說明TP-IE使得抑制處理后的流量圖相似性優(yōu)于文獻[8]和文獻[5]提出的兩種方法。

圖2 k對匿名后流量圖的相似性影響(L=3)

4.2.2 數(shù)據(jù)損失率

圖3展示了參數(shù)k對數(shù)據(jù)損失的影響情況。數(shù)據(jù)損失主要受到抑制時空點數(shù)量變化的影響。隨著k值增大，抑制的時空點越多，原始數(shù)據(jù)集的數(shù)據(jù)損失率越大。對比三個不同算法發(fā)現(xiàn)：隨著k值增大，TP-IE的數(shù)據(jù)損失率始終最低，當(dāng)k值增長到一定程度時，本文算法的數(shù)據(jù)損失率趨于穩(wěn)定，但文獻[5]與文獻[8]仍有較大的增長。經(jīng)過計算可得，在相同匿名參數(shù)的影響下，TP-IE比文獻[5]算法在數(shù)據(jù)損失量上降低了約25%，比文獻[8]算法降低了約21%。因此可以得出結(jié)論本文提出的算法可以最大化地減小抑制法帶來的數(shù)據(jù)損失。

圖3 k對數(shù)據(jù)損失的影響(L=3)

4.2.3 隱私收益

本文通過匿名前后的熵值變化來計算算法帶來的隱私收益。圖4展示了k值對于隱私收益的影響，可以看出文獻[5]與文獻[8]算法在k值較小時隱私收益均高于本文算法，這是由于當(dāng)k值較小時，匿名算法執(zhí)行的更多是局部抑制，文獻[8]與文獻[5]算法在隱私需求較低、數(shù)據(jù)損失較小的情況下，能帶來更高的隱私收益；然而，隨著k值逐漸增大，隱私需求提升時，匿名算法更多的執(zhí)行全局抑制。TP-IE在執(zhí)行抑制的過程中實則消除了流量圖中熵值較低的點，保留了熵值較大的點，同時由于軌跡數(shù)據(jù)集中實例數(shù)量較低和轉(zhuǎn)移概率較小的點得以抑制，實際上增大了原先熵值較低的時空點，因此，TP-IE匿名后的流量圖的隱私收益會呈現(xiàn)出較大的增長；而文獻[5]與文獻[8]算法隨著k值的增大，數(shù)據(jù)損失會越來越大，在抑制的過程中將會舍棄大量熵值較高的時空點，降低了原始軌跡的數(shù)據(jù)實用性，也使得隱私收益出現(xiàn)明顯下降。經(jīng)過計算可以得出在相同匿名參數(shù)取值下，TP-IE在隱私收益上比文獻[5]算法提高了約21%，比文獻[8]算法提高了約11%。因此，當(dāng)k值持續(xù)增長時，本文方法會帶來更高的隱私收益，在實用性上明顯高于其余二者。

圖4 k值對于隱私收益的影響(L=3)

5 結(jié)語

本文基于LK模型提出了一種基于信息熵抑制的軌跡隱私保護方法，對原始軌跡集建立基于信息熵的流量圖，根據(jù)圖節(jié)點的熵值大小局部抑制違反模型的時空點,進而實現(xiàn)抑制敏感點的同時最大化保留軌跡數(shù)據(jù)實用性的目的。在仿真數(shù)據(jù)集上的實驗表明，本文方法在匿名前后流量圖的相似性、數(shù)據(jù)損失率以及隱私收益三個方面均優(yōu)于文獻[5]與文獻[8]提出的算法，證明了TP-IE的有效性和實用性。本文算法前提是假設(shè)攻擊者的背景知識長度不超過L,然而現(xiàn)實生活中攻擊者的背景知識大部分是未知的，如何在不知曉攻擊者背景知識的條件下達到保護用戶隱私的目的是下一階段主要研究的問題。