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

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

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

0 引言

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

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

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

1 相關(guān)定義

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

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

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

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

2) 0<|q|≤L，|q|表示序列q包含的軌跡時(shí)空點(diǎn)個(gè)數(shù)，至多為L(zhǎng)個(gè)。

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

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

定義6 基于熵的流量圖。基于熵的流量圖是指由一系列時(shí)空點(diǎn)組成的有向圖，它采用樹(shù)作為存儲(chǔ)結(jié)構(gòu)，可表示為三元組ET=〈G,PATH,Root(ET)〉，其中G表示該流量圖節(jié)點(diǎn)的集合，PATH表示該流量圖路徑的集合，Root(ET)表示流量圖的根節(jié)點(diǎn)。

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

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

H(d)=-plgp

(1)

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

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

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

圖1 基于熵的流量圖

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

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

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

2.1 信息熵

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

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

2.2 隱私保護(hù)算法—— TP-IE

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

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

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

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

(2)

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

示例1 如圖1所示，α(b2)=3因?yàn)榱髁繄D里有3個(gè)b2的節(jié)點(diǎn)，β(b2)=5因?yàn)榱髁繄D里的b2節(jié)點(diǎn)共有5個(gè)分支，γ(b2)=6因?yàn)樵紨?shù)據(jù)集T里有6條包含b2的路徑，由式(1)可得出Hα(b2)=0.15，Hβ(b2)=0.56，則可由式(2)得出Info(b2)的值。

定義9 Score值。根據(jù)d的抑制方式，定義一種花費(fèi)代價(jià)函數(shù)來(lái)計(jì)算消除d時(shí)空點(diǎn)的花費(fèi)代價(jià)，如式(3)所示:

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

(3)

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

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

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

算法1 計(jì)算每個(gè)時(shí)空點(diǎn)的Info值—— GetInfo。

輸入 原始軌跡集T；

輸出 時(shí)空點(diǎn)的信息質(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é)點(diǎn)的時(shí)空點(diǎn)熵之和*/

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

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

算法2 對(duì)MVS序列進(jìn)行抑制處理—— Sequence-suppression。

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

輸出 滿(mǎn)足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í)用性比較

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

首先，匿名前后流量圖中的所有節(jié)點(diǎn)都是按照時(shí)間、地點(diǎn)排序，然后按次序提取G與G′中的時(shí)空點(diǎn)d與d′(第1)～3)行)：如果d與d′的時(shí)間、位置均相等，那么d與d′視作相同節(jié)點(diǎn)，并計(jì)算出它們的aSum、bSum、cSum、vSum、wSum、uSum(第5)～14)行)；如果β(d)=0，即d為流量圖里的葉子節(jié)點(diǎn)的值，由于β(d)為計(jì)算bSum時(shí)的分母，所以算法跳過(guò)此次除法，并使用i對(duì)β(d)=0計(jì)數(shù)(第11)～16)行)，最后在計(jì)算相似性時(shí)流量圖應(yīng)減去葉子節(jié)點(diǎn)的數(shù)值(第22)行)；接下來(lái)對(duì)vSum,uSum,wSum進(jìn)行歸一化記作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é)點(diǎn)到當(dāng)前節(jié)點(diǎn)的時(shí)空點(diǎn)熵和*/

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時(shí)間復(fù)雜度

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

2.5 TP-IE安全性分析

2.5.1 LK隱私模型有效

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

2.5.2 TP-IE實(shí)用性分析

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

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

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

(4)

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

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

(5)

4 實(shí)驗(yàn)與分析

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

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

高維軌跡隱私保護(hù)一般用隱私保護(hù)度和數(shù)據(jù)損失率來(lái)評(píng)價(jià)算法效率。本節(jié)將TP-IE同文獻(xiàn)[5]和文獻(xiàn)[8]提出的算法進(jìn)行比較。文獻(xiàn)[8]通過(guò)設(shè)置不同參數(shù)來(lái)測(cè)試算法的實(shí)用性，本文選取文獻(xiàn)[8]實(shí)驗(yàn)效果最好的兩組參數(shù)。后文實(shí)驗(yàn)圖中A、B組分別包含文獻(xiàn)[8]取兩組參數(shù)時(shí)的實(shí)驗(yàn)效果。其中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對(duì)匿名后流量圖的相似性影響。流量圖相似性變化主要取決于兩點(diǎn)：1)抑制軌跡時(shí)空點(diǎn)的數(shù)量；2)時(shí)空點(diǎn)熵值變化。當(dāng)k=60時(shí)，TP-IE匿名后的流量圖相似性明顯高于文獻(xiàn)[5]和文獻(xiàn)[8]提出的兩種方法。隨著k值增加，軌跡抑制法抑制處理的數(shù)據(jù)點(diǎn)越多，流量圖相似性降低；當(dāng)k值增加到一定值時(shí)，算法將執(zhí)行更多的全局抑制，因此相似性在逐漸達(dá)到平衡值會(huì)急劇下降。與文獻(xiàn)[5]與文獻(xiàn)[8]相比，由于時(shí)空點(diǎn)熵值較大的點(diǎn)保留更多，數(shù)據(jù)集的實(shí)用性也會(huì)更大。如圖2所示，TP-IE在相同的匿名參數(shù)取值下相似性始終比另外兩種方式高，所提方法在相似性度量上比文獻(xiàn)[5]提出的方法提高了約27%, 比文獻(xiàn)[8]方法提高了約22%。由此可以說(shuō)明TP-IE使得抑制處理后的流量圖相似性?xún)?yōu)于文獻(xiàn)[8]和文獻(xiàn)[5]提出的兩種方法。

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

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

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

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

4.2.3 隱私收益

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

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

5 結(jié)語(yǔ)

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