基于語(yǔ)義位置保護(hù)的軌跡隱私保護(hù)的k-CS算法

霍 崢，崔洪雷，賀 萍

(1.河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，石家莊 050061； 2.浙江大學(xué)寧波理工學(xué)院 商學(xué)院，浙江 寧波 315100)(*通信作者電子郵箱huozheng@heuet.edu.cn)

0 引言

近年來(lái)，隨著智能移動(dòng)手機(jī)和定位技術(shù)的發(fā)展，越來(lái)越多的位置數(shù)據(jù)被收集、存儲(chǔ)、挖掘和分析。軌跡數(shù)據(jù)挖掘[1]和語(yǔ)義軌跡抽取[2]已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域一個(gè)重要的研究方向。許多學(xué)者意識(shí)到對(duì)位置數(shù)據(jù)的分析和挖掘會(huì)導(dǎo)致移動(dòng)對(duì)象的個(gè)人隱私泄露。近年來(lái)，學(xué)者們對(duì)軌跡數(shù)據(jù)的隱私保護(hù)技術(shù)進(jìn)行了研究，這些研究主要可分為擾動(dòng)法[3]、抑制法[4]和k-匿名方法[5-8]。近年來(lái)，出現(xiàn)了以差分隱私技術(shù)為基礎(chǔ)的軌跡數(shù)據(jù)發(fā)布方法[9]，它能夠保證無(wú)條件隱私，即對(duì)指定的統(tǒng)計(jì)信息進(jìn)行分析，無(wú)法得到任何一個(gè)個(gè)體的信息。然而，差分隱私的主要問(wèn)題在于其靈活性不足，僅能在有限的統(tǒng)計(jì)信息上進(jìn)行隱私保護(hù)。而傳統(tǒng)的k-匿名技術(shù)通過(guò)將k條軌跡上相應(yīng)的采樣位置匿名在同一區(qū)域中達(dá)到隱私保護(hù)的效果，實(shí)現(xiàn)簡(jiǎn)單，且應(yīng)用環(huán)境靈活。在數(shù)據(jù)隱私保護(hù)技術(shù)中，隱私保護(hù)度和數(shù)據(jù)可用性是一對(duì)矛盾。隱私保護(hù)度越高，必然會(huì)造成數(shù)據(jù)可用性的下降；如果需要較高的數(shù)據(jù)可用性，必然以犧牲隱私保護(hù)度來(lái)?yè)Q取。文獻(xiàn)[7]提出了一種利用軌跡數(shù)據(jù)不確定性進(jìn)行軌跡聚類的隱私保護(hù)算法，將移動(dòng)對(duì)象軌跡上的各個(gè)采樣位置都進(jìn)行匿名處理，隱私處理后的數(shù)據(jù)可用性較低。文獻(xiàn)[5]第一次在自由空間中提出：并不是軌跡上每一個(gè)采樣位置都有必要進(jìn)行隱私保護(hù)。例如：行進(jìn)時(shí)所在的道路等位置信息不是移動(dòng)對(duì)象真正訪問(wèn)的位置，并不會(huì)暴露用戶的隱私，不必要的匿名會(huì)給軌跡數(shù)據(jù)造成嚴(yán)重的信息丟失，導(dǎo)致數(shù)據(jù)不可用。例如，在利用軌跡數(shù)據(jù)進(jìn)行交通流量信息分析時(shí)，道路上的數(shù)據(jù)如果不會(huì)暴露用戶隱私而不加以匿名處理，其數(shù)據(jù)可用性更高，分析結(jié)果更加精確。而用戶運(yùn)行軌跡中真正能夠暴露隱私的是用戶訪問(wèn)過(guò)的地圖上的語(yǔ)義位置，例如酒吧、醫(yī)院、賓館等。也就是說(shuō)，攻擊者更容易通過(guò)語(yǔ)義位置獲取用戶隱私。若僅對(duì)語(yǔ)義位置進(jìn)行隱私保護(hù)，則能極大地提高數(shù)據(jù)的可用性。

筆者注意到，語(yǔ)義軌跡上某些重要的停留位置需要進(jìn)行隱私保護(hù)處理，而其余位置并不需要隱私保護(hù)處理。采用上述思路能夠減少需匿名的采樣位置數(shù)量，從而提高軌跡數(shù)據(jù)的可用性。針對(duì)上述問(wèn)題，本文提出一種路網(wǎng)空間中基于語(yǔ)義軌跡的軌跡隱私保護(hù)技術(shù)。具體來(lái)說(shuō)，本文的主要貢獻(xiàn)如下：

1)本文提出一種基于語(yǔ)義軌跡的軌跡隱私保護(hù)方法，在隱私保護(hù)過(guò)程中，僅僅對(duì)軌跡上的語(yǔ)義位置進(jìn)行匿名處理，對(duì)一般的位置不作隱私保護(hù)，能夠提高數(shù)據(jù)可用性。

2)本文提將路網(wǎng)環(huán)境中基于語(yǔ)義位置的軌跡隱私保護(hù)問(wèn)題定義為一個(gè)k-CS(k-Connected Sub-graph)匿名問(wèn)題，且證明了該問(wèn)題是一個(gè)NP(Non-deterministic Polynomial)難問(wèn)題。

3)提出了一種基于圖上頂點(diǎn)聚類的近似算法，得到地圖上語(yǔ)義位置的k-CS匿名區(qū)域，并通過(guò)算法將軌跡上的停留位置進(jìn)行匿名處理，保護(hù)停留位置的隱私。

4)在真實(shí)數(shù)據(jù)集上對(duì)k-CS匿名算法的數(shù)據(jù)可用性、查詢誤差率和運(yùn)行時(shí)間進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文提出的方法比傳統(tǒng)k-匿名方法的數(shù)據(jù)可用性高20%左右。

1 預(yù)備知識(shí)

下面介紹本文算法的預(yù)備知識(shí)。

1.1 系統(tǒng)結(jié)構(gòu)

在軌跡數(shù)據(jù)隱私保護(hù)技術(shù)中，使用圖1所示的系統(tǒng)架構(gòu)。該架構(gòu)包括客戶端、軌跡數(shù)據(jù)庫(kù)、隱私保護(hù)服務(wù)器三個(gè)組件?？蛻舳藢⒆约旱奈恢脭?shù)據(jù)發(fā)送給數(shù)據(jù)采集方，隱私保護(hù)服務(wù)器負(fù)責(zé)將收集到的軌跡數(shù)據(jù)進(jìn)行語(yǔ)義位置提取、地圖匿名區(qū)域生成及軌跡匿名處理。匿名后的數(shù)據(jù)形成可發(fā)布軌跡數(shù)據(jù)，可供其他應(yīng)用程序進(jìn)行挖掘或統(tǒng)計(jì)。

圖1 軌跡數(shù)據(jù)隱私保護(hù)系統(tǒng)結(jié)構(gòu)

1.2 相關(guān)定義

定義1 語(yǔ)義軌跡。語(yǔ)義軌跡T是一系列帶有注釋的停留位置和移動(dòng)位置的序列，通常用如下元組表示：(軌跡標(biāo)示符，移動(dòng)對(duì)象標(biāo)示符，注釋，軌跡上重要位置，語(yǔ)義停留位置，軌跡片段)。

語(yǔ)義軌跡和原始軌跡數(shù)據(jù)不同，它將原始軌跡上的采樣位置語(yǔ)義化為移動(dòng)對(duì)象訪問(wèn)的位置及訪問(wèn)時(shí)間等重要信息。原始軌跡是指從位置采集設(shè)備上收集到的位置及采樣時(shí)間，位置信息是用經(jīng)緯度表示的。在語(yǔ)義軌跡的信息中，本文的算法主要關(guān)注軌跡上重要位置和語(yǔ)義停留位置，本文將其統(tǒng)稱為語(yǔ)義位置。

定義2 路網(wǎng)。路網(wǎng)G=(V,E,W)是一個(gè)無(wú)向圖，其中V是所有興趣位置(Points of Interests, POI)的集合，集合中的元素表示為vi；E是邊的集合，當(dāng)且僅當(dāng)兩個(gè)頂點(diǎn)vi和vj之間有一條不包含任何頂點(diǎn)的路段時(shí)，兩者之間有一條邊(vi,vj)；W表示邊權(quán)的集合，元素wij表示頂點(diǎn)vi到頂點(diǎn)vj的距離，即邊(vi,vj)的長(zhǎng)度。

1.3 攻擊模式

針對(duì)語(yǔ)義軌跡主要有以下兩種攻擊模式。

第1種 語(yǔ)義位置攻擊。在路網(wǎng)環(huán)境中，并不是軌跡上的任意采樣位置都是攻擊者感興趣的，僅有那些用戶真正訪問(wèn)過(guò)的語(yǔ)義位置才是攻擊者重點(diǎn)攻擊的對(duì)象，例如，如果某個(gè)移動(dòng)對(duì)象訪問(wèn)了醫(yī)院，攻擊者可能推導(dǎo)出該用戶患了某種疾病，然而，如果用戶僅僅是從醫(yī)院門(mén)口經(jīng)過(guò)，并不能得出上述結(jié)論，此為語(yǔ)義位置攻擊。

第2種 最大運(yùn)行速度攻擊。最大運(yùn)行速度攻擊最早是在文獻(xiàn)[10]中提出的。在路網(wǎng)環(huán)境中，最大運(yùn)行速度攻擊的效果更具威脅性。假設(shè)圖2(a)中灰色區(qū)域?yàn)橐苿?dòng)對(duì)象在ti時(shí)刻的匿名區(qū)域，圖2(a)中的圓角矩形表示在假如移動(dòng)對(duì)象在ti到下一個(gè)時(shí)刻ti+1之間可能運(yùn)行到的最大運(yùn)行區(qū)域(Maximum Moving Boundary, MMB)。道路一般有限速(環(huán)路一般不超過(guò)80 km/h，普通道路一般不超過(guò)60 km/h)，移動(dòng)對(duì)象的最大運(yùn)行速度用vmax來(lái)表示，則ti時(shí)刻的最大運(yùn)行邊界可由式vmax×(ti+1-ti)計(jì)算得出，那么攻擊者可以推導(dǎo)出在ti+1時(shí)刻，移動(dòng)對(duì)象肯定處于被Zi的最大運(yùn)行邊界覆蓋的區(qū)域中，導(dǎo)致Zi+1時(shí)刻的匿名區(qū)域中的大部分區(qū)域變?yōu)椴豢蛇_(dá)的，隱私保護(hù)度降低。

圖2 最大運(yùn)行速度攻擊

2 基于語(yǔ)義軌跡的隱私保護(hù)算法

算法主要由3個(gè)步驟構(gòu)成：

第1步 從原始軌跡數(shù)據(jù)上抽取出重要位置和停留位置，即原始軌跡語(yǔ)義化；

第2步 根據(jù)路網(wǎng)數(shù)據(jù)和語(yǔ)義軌跡數(shù)據(jù)，將地圖上的POI進(jìn)行k-CS匿名，即將k個(gè)地圖上的POI組成一個(gè)匿名區(qū)域；

第3步 將語(yǔ)義軌跡進(jìn)行匿名，即，將語(yǔ)義位置由相應(yīng)的地圖匿名區(qū)域取代，而經(jīng)過(guò)位置可不作處理。

2.1 語(yǔ)義位置抽取

原始軌跡中的采樣位置只是經(jīng)緯度，并不包含語(yǔ)義信息。作者認(rèn)為，假如不對(duì)原始軌跡中的采樣位置加以區(qū)分，進(jìn)行同樣的匿名處理，勢(shì)必會(huì)造成數(shù)據(jù)可用性的嚴(yán)重下降。本節(jié)主要講述如何從原始數(shù)據(jù)中抽取重要位置或停留位置。所謂停留位置，是指移動(dòng)對(duì)象真正訪問(wèn)過(guò)的位置。與移動(dòng)對(duì)象僅經(jīng)過(guò)未訪問(wèn)的位置不同，停留位置包含了更多的語(yǔ)義信息。若移動(dòng)對(duì)象訪問(wèn)了某個(gè)專科醫(yī)院，可以推斷該用戶患了何種類型的疾??；如果移動(dòng)對(duì)象的軌跡上有對(duì)應(yīng)于該專科醫(yī)院的采樣位置，但用戶并未在此處停留，則無(wú)法推導(dǎo)出用戶訪問(wèn)過(guò)該位置的結(jié)論，即前述語(yǔ)義位置攻擊。

軌跡上停留位置抽取方法有兩種：一種是基于停留時(shí)間的抽取方法；一種基于采樣位置密度的抽取方法。第1種方法是為了識(shí)別軌跡上速度為0的停留，這時(shí)需設(shè)置一個(gè)時(shí)間閾值tht，但凡兩個(gè)連續(xù)采樣位置的時(shí)間間隔大于tht,則認(rèn)為該采樣位置發(fā)生了停留。第2種基于采樣密度的方法主要是為了識(shí)別速度不為0的游覽型訪問(wèn)，比如，在公園中游覽等，此時(shí)，移動(dòng)對(duì)象的速度并不為0，但是游覽速度較慢，因此，位置的采樣密度較大。

經(jīng)過(guò)語(yǔ)義位置抽取過(guò)程，原始軌跡Ti可以轉(zhuǎn)換為語(yǔ)義位置和停留時(shí)間的序列，即，Ti={(L1,td1),(L2,td2),…,(Ln,tdn)}。其中：Li表示語(yǔ)義位置，tdi表示在相應(yīng)位置的停留時(shí)間。

2.2 地圖匿名區(qū)域生成

抽取出的軌跡停留位置是地圖上的POI是一個(gè)經(jīng)緯度，可由反向地址解析器解釋得到確切的地址信息，此處不再贅述。

經(jīng)由停留位置抽取之后，路網(wǎng)數(shù)據(jù)G=(V,E)中的頂點(diǎn)和邊都已生成。其中，V中包含的頂點(diǎn)除了路網(wǎng)數(shù)據(jù)中的POI之外，還有從軌跡停留位置中抽取出來(lái)的POI，并將抽取出的POI放置在距離其最近的一條路段上，作為一個(gè)頂點(diǎn)。

文獻(xiàn)[5]采用了語(yǔ)義和自由空間歐氏距離的混合距離對(duì)空間中存在的POI進(jìn)行聚類，生成包含k個(gè)頂點(diǎn)的匿名區(qū)域。而在路網(wǎng)空間中，不能簡(jiǎn)單地用距離對(duì)POI進(jìn)行聚類，這樣會(huì)產(chǎn)生某些匿名區(qū)域中POI不可達(dá)的問(wèn)題，導(dǎo)致隱私保護(hù)度下降，具體如圖3所示。

圖3 不連通的4-匿名區(qū)域

圖3展示了一個(gè)4-匿名區(qū)域Ci，其中包含了v1,v2,v3,v4四個(gè)頂點(diǎn)，另有e1,e2,e3,e4四條邊與該匿名區(qū)域連通。按照匿名模型的定義，一旦達(dá)到4-匿名，意味著隱私泄露的概率為1/4，即，攻擊者無(wú)法識(shí)別移動(dòng)對(duì)象處于v1,v2,v3,v4中哪個(gè)位置。然而，圖3所示的例子有路網(wǎng)信息作為背景知識(shí)，4-匿名無(wú)法達(dá)到應(yīng)有的隱私保護(hù)度。若有軌跡Ti從道路e1進(jìn)入匿名區(qū)域中的某個(gè)語(yǔ)義位置并停留一段時(shí)間，則將該停留位置用匿名區(qū)域Ci取代進(jìn)行匿名。然而，攻擊者可能發(fā)現(xiàn)移動(dòng)對(duì)象只能處在v1或v2位置上,不可能處于v3或v4，因?yàn)槁窂絜1沒(méi)有路徑連通到v1和v2。同理，從路徑e2,e3,e4進(jìn)入匿名區(qū)域Ci的軌跡，均無(wú)法達(dá)到4-匿名的效果，只能保證隱私泄露的概率不大于1/2。

為了避免上述問(wèn)題的發(fā)生，需要重新設(shè)計(jì)地圖匿名算法，避免僅用距離衡量哪些POI應(yīng)該處于同一個(gè)匿名區(qū)域中。匿名算法中需要滿足下述3個(gè)要求：1)每個(gè)匿名區(qū)域中包含至少k個(gè)語(yǔ)義位置；2)匿名區(qū)域中的k個(gè)匿名位置須構(gòu)成一個(gè)連通子圖；3)由于數(shù)據(jù)可用性需求，匿名區(qū)域面積越小越好。本文將滿足上述3個(gè)條件的問(wèn)題定義為k-CS匿名問(wèn)題。該問(wèn)題的形式化定義如下。

定義3k-CS匿名問(wèn)題。給定路網(wǎng)數(shù)據(jù)G=(V,E,W)，k-CS匿名問(wèn)題需要找到滿足下述條件的匿名區(qū)域：

1)圖G=(V,E,W)最多可劃分為m=?n/k」個(gè)子圖(n為圖G中頂點(diǎn)個(gè)數(shù))：G1=(V1,E1,W1)，G2=(V2,E2,W2),…,Gi=(Vi,Ei,Wi);每個(gè)子圖中至少包含k個(gè)頂點(diǎn)，每個(gè)子圖即為一個(gè)匿名區(qū)域；

2)V1∩V2∩…∩Vm=?;

3)V1∪V2∪…∪Vm?V;

4)連通子圖Vi的區(qū)域面積最小。

然而，在圖中計(jì)算不規(guī)則多邊形的面積并非一個(gè)簡(jiǎn)單工作，本文采用路網(wǎng)距離之和來(lái)取代匿名區(qū)域面積。所謂路網(wǎng)距離是指：如果頂點(diǎn)vi和頂點(diǎn)vj之間有一條通路，則頂點(diǎn)vi到頂點(diǎn)vj的路網(wǎng)距離就是兩點(diǎn)之間的最短距離。如果vi和vj不連通，則其路徑長(zhǎng)度為+∞。

文獻(xiàn)[11]中，已經(jīng)證明了圖上的k-way劃分是NP-hard問(wèn)題，下面證明本文提出的k-CS匿名問(wèn)題也是NP-hard問(wèn)題。

定理1k-CS匿名問(wèn)題是NP-hard問(wèn)題。

證畢。

本文提出了一種近似算法求解k-CS匿名問(wèn)題，算法以聚類算法k-medoids為基礎(chǔ)，區(qū)別在于：一般的k-medoids聚類是在自由空間中進(jìn)行的，以歐氏距離為基礎(chǔ)；而在路網(wǎng)空間中，距離的衡量公式都會(huì)發(fā)生改變。如圖4所示，如果按照歐氏距離的定義進(jìn)行聚類，會(huì)產(chǎn)生圖4(a)的聚類效果，顯然，v2,v3,v4,v5構(gòu)成的匿名區(qū)域是一個(gè)不連通的子圖，會(huì)產(chǎn)生前述的隱私泄露問(wèn)題。盡管圖4(b)中的匿名區(qū)域C2面積大于圖4(a)中的匿名區(qū)域C1，但是由v2,v4,v5,v6構(gòu)成的子圖是一個(gè)連通子圖，不會(huì)造成前述隱私泄露問(wèn)題，因此，本文采用路網(wǎng)距離進(jìn)行聚類。

圖4 不同距離的聚類結(jié)果

算法1k-CS匿名區(qū)域生成(G(V,E,W),k)。

輸入：路網(wǎng)數(shù)據(jù)G，隱私保護(hù)參數(shù)k。

輸出：匿名區(qū)域C1,C2,…,Cm。

FOR 圖G中的每個(gè)連通分量Gi

任選Gi中的一個(gè)頂點(diǎn)vi作為聚類中心；

按照距離相遠(yuǎn)的原則選擇?ni/k」個(gè)聚類中心；

FOR 每個(gè)聚類中心vi

WHILE |Cj|

Cj← 距離質(zhì)心路網(wǎng)距離最近的頂點(diǎn)；

|Cj|++;

END WHILE

FOR 每個(gè)簇Cj

計(jì)算Pscore← 各個(gè)頂點(diǎn)到質(zhì)心的距離之和;

按順序每個(gè)頂點(diǎn)vm作為聚類中心;

重新計(jì)算Pscore;

選擇Pscore最小的那個(gè)簇的頂點(diǎn)為聚類中心;

重復(fù)上述步驟，直到簇不變化為止。

END FOR

END FOR

RETURNC1,C2,…,Cp

算法1展示了生成k-CS匿名區(qū)域的過(guò)程。為了減小計(jì)算代價(jià)，算法將連通子圖匿名區(qū)域面積最小用路網(wǎng)距離之和最小取代。算法對(duì)圖G中的每個(gè)連通分量作處理，每個(gè)連通分量各自選取?ni/k」個(gè)聚類中心，其中ni表示第i個(gè)連通分量中頂點(diǎn)的個(gè)數(shù)。當(dāng)每個(gè)簇中的頂點(diǎn)個(gè)數(shù)小于k時(shí)，將距離簇質(zhì)心最近的頂點(diǎn)加入到簇Cj中，然后重新計(jì)算簇的質(zhì)心，并使簇中的頂點(diǎn)數(shù)增加1，質(zhì)心的選擇是聚類效果的關(guān)鍵。當(dāng)簇中只有一個(gè)頂點(diǎn)時(shí)，該頂點(diǎn)就是該簇的質(zhì)心；當(dāng)簇中頂點(diǎn)數(shù)多于2個(gè)時(shí)，選擇距離簇中其他各個(gè)頂點(diǎn)距離之和最小的作為簇的質(zhì)心。然后再加入其他的頂點(diǎn)到當(dāng)前簇中，直到簇中包含k個(gè)頂點(diǎn)為止。對(duì)于每個(gè)簇Cj，按照順序依次選擇一個(gè)頂點(diǎn)作為質(zhì)心，計(jì)算該簇的得分Pscore，即，每個(gè)頂點(diǎn)到簇中心的路網(wǎng)距離之和。哪個(gè)頂點(diǎn)作為質(zhì)心得到的Pscore最小，就用哪個(gè)頂點(diǎn)作質(zhì)心，重新調(diào)整簇。重復(fù)這些步驟，直到簇不再變化為止。輸出由頂點(diǎn)構(gòu)成的簇C1,C2,…,Cp，每個(gè)簇為一個(gè)匿名區(qū)域。下面證明用算法1得到的匿名區(qū)域中，每個(gè)子圖都是一個(gè)包含的k個(gè)頂點(diǎn)的連通子圖。

定理2 用算法1得到的每個(gè)匿名區(qū)域都是包含k個(gè)頂點(diǎn)的連通子圖。

證明 算法1將距離質(zhì)心路網(wǎng)距離最小的頂點(diǎn)加入到簇中。假定簇Cj中質(zhì)心為vi，那么距離vi路網(wǎng)距離最近的頂點(diǎn)vj一定被加入到Cj中。根據(jù)Dijskra算法，距離vi的路網(wǎng)距離次近的頂點(diǎn)分為兩種情況：

第1種vj有一條直接路徑到達(dá)vi路網(wǎng)距離最近；

第2種vj經(jīng)過(guò)另外一個(gè)中間節(jié)點(diǎn)vm到達(dá)vi的距離最近。

第1種情況vj和vi連通的，因?yàn)閮蓚€(gè)頂點(diǎn)之間有一條直接路徑。第2種情況下，vm到vi的距離比vj到vi的距離更近，因此，vm必定先于vj加入到以vi為質(zhì)心的簇中，vj通過(guò)vm和vi連通。依此類推，Cj中有k個(gè)頂點(diǎn)時(shí)，子圖也是連通的。

證畢。

2.3 軌跡匿名處理

得到匿名區(qū)域C1，C2,…，Cp之后，將采集到的軌跡數(shù)據(jù)進(jìn)行匿名處理。匿名處理的過(guò)程就是將收集到的軌跡數(shù)據(jù)中的采樣位置分為停留位置和經(jīng)過(guò)位置。如前所述，停留位置攜帶的敏感信息更多，能夠真正反映移動(dòng)對(duì)象的隱私信息，因此，需要對(duì)軌跡上的停留位置進(jìn)行匿名處理。此外，軌跡匿名處理后的數(shù)據(jù)還應(yīng)抵御最大運(yùn)行速度攻擊。具體如算法2所示。

算法2 軌跡匿名處理。

輸入：匿名區(qū)域C1,C2,…,Cp，原始軌跡數(shù)據(jù)庫(kù)D。

FORD中的每條軌跡Ti

轉(zhuǎn)換為語(yǔ)義位置序列Ti={(L1,td1), (L2,td2),…,(Ln,tdn)}

將停留位置Ti由地圖上的匿名區(qū)域Ci替換；

計(jì)算MMB(Ci)和MMB(Ci+1);

IFMMB(Ci)不能夠完全覆蓋Ci+1，延長(zhǎng)tdi，使得MMB(Ci)完全覆蓋Ci+1

END IF

END FOR

2.4 算法分析

算法1和算法2能夠保證語(yǔ)義軌跡上的停留位置被匿名在一個(gè)包含有k個(gè)POI的匿名區(qū)域中，因此，移動(dòng)對(duì)象在停留位置隱私泄露的概率至多為1/k。軌跡數(shù)據(jù)的匿名處理對(duì)數(shù)據(jù)造成了一定的可用性丟失，信息丟失主要是由兩方面造成的：一方面是由停留位置匿名導(dǎo)致的，從一個(gè)采樣位置泛化為一個(gè)面積，導(dǎo)致精度下降；另一方面是由停留時(shí)間tdi的延長(zhǎng)導(dǎo)致的，致使某個(gè)時(shí)刻移動(dòng)對(duì)象所處位置不精確。

針對(duì)第一方面的信息丟失(Information Loss, IL)，通常采用文獻(xiàn)[12]提出的標(biāo)準(zhǔn)進(jìn)行衡量，即：將一個(gè)點(diǎn)泛化為一個(gè)區(qū)域后，移動(dòng)對(duì)象被識(shí)別概率降低了多少，如式(1)所示：

(1)

其中：n表示移動(dòng)對(duì)象數(shù)據(jù)庫(kù)中軌跡的條數(shù)，k表示一條軌跡上的語(yǔ)義位置數(shù)目。只有語(yǔ)義位置才需要被匿名區(qū)域取代，因此，停留位置會(huì)造成信息的丟失。

此外，空間范圍查詢的誤差率也是衡量信息丟失的重要標(biāo)準(zhǔn)，它能夠衡量上述兩方面的信息丟失。所謂空間范圍計(jì)數(shù)查詢是指：查詢某個(gè)時(shí)間段內(nèi)某個(gè)空間區(qū)域中的移動(dòng)對(duì)象數(shù)目。在對(duì)語(yǔ)義軌跡進(jìn)行匿名之后，空間范圍計(jì)數(shù)查詢必然產(chǎn)生一定的誤差，該誤差用error表示，可由式(2)計(jì)算：

(2)

其中，Q(D)表示在原始軌跡數(shù)據(jù)上進(jìn)行空間范圍計(jì)數(shù)查詢時(shí)得到的值；Q(D*)表示在隱私保護(hù)處理后的數(shù)據(jù)上，進(jìn)行空間范圍計(jì)數(shù)查詢時(shí)得到的值。本文主要衡量?jī)煞N空間范圍計(jì)數(shù)查詢：一種是PSI(Possibly Sometimes Inside)查詢；一種是DAI(Definitely Always Inside)查詢。

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用北京市路網(wǎng)數(shù)據(jù)以及Geolife的真實(shí)數(shù)據(jù)進(jìn)行。北京市路網(wǎng)數(shù)據(jù)中包括了17萬(wàn)個(gè)路網(wǎng)頂點(diǎn)及43萬(wàn)余條邊。軌跡數(shù)據(jù)Geolife采集了155個(gè)志愿者在北京市的8 000多條軌跡，該數(shù)據(jù)集中大約包含230萬(wàn)條采樣位置信息，采樣位置主要分布在北京市五環(huán)區(qū)域內(nèi)。數(shù)據(jù)分布如圖5所示。

圖5 數(shù)據(jù)分布

本實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境為Intel i5 3.30 GHz處理器、8 GB內(nèi)存、Windows 7操作系統(tǒng)。根據(jù)前述的停留位置抽取算法，將時(shí)間閾值設(shè)為20 min，共抽取近8萬(wàn)個(gè)停留位置。實(shí)驗(yàn)對(duì)算法的信息丟失率、范圍查詢相對(duì)誤差及算法的運(yùn)行時(shí)間進(jìn)行了測(cè)試。對(duì)比算法是軌跡隱私保護(hù)的經(jīng)典算法(k,δ)-anonymity算法，它是在自由空間中通過(guò)軌跡聚類進(jìn)行隱私保護(hù)的一種算法，其中，δ是給定的匿名區(qū)域半徑，在本實(shí)驗(yàn)中，δ的取值與文獻(xiàn)[7]中的取值相同，即從1 000到4 000，每次增長(zhǎng)1 000，實(shí)驗(yàn)中展示的結(jié)果是在不同δ值上的平均值。

3.1 信息丟失率

本節(jié)主要展示k-CS算法和(k,δ)-anonymity算法在數(shù)據(jù)可用性上的對(duì)比結(jié)果，其中，信息丟失率由式(1)計(jì)算得出。實(shí)驗(yàn)驗(yàn)證了在不同隱私參數(shù)k的取值下，信息丟失率的變化情況，如圖6所示。兩個(gè)算法的信息丟失率隨著k的增加逐漸增大，當(dāng)隱私參數(shù)k取值到12時(shí)，k-CS算法的信息丟失率為40%左右，而(k,δ)-anonymity算法的信息丟失率接近80%，這是由于(k,δ)-anonymity算法將軌跡上的各個(gè)采樣位置都進(jìn)行了泛化，造成了較大的信息丟失。而k-CS算法只對(duì)軌跡上的語(yǔ)義位置進(jìn)行泛化，因此，信息丟失率較小。

圖6 兩種算法信息丟失率對(duì)比

3.2 查詢誤差率

查詢誤差率實(shí)驗(yàn)主要評(píng)估在軌跡數(shù)據(jù)集D*與原始數(shù)據(jù)集D上執(zhí)行空間范圍查詢的誤差率，該標(biāo)準(zhǔn)是隱私保護(hù)算法常用的衡量標(biāo)準(zhǔn)之一。查詢誤差率的計(jì)算由式(2)計(jì)算得出。實(shí)驗(yàn)結(jié)果如圖7所示。由于DAI查詢比PSI查詢的選擇性更強(qiáng)，所以在圖7(b)中，兩個(gè)算法得查詢誤差率均高于圖7(a)中的算法查詢誤差率。(k,δ)-anonymity算法的查詢誤差率明顯高于k-CS算法，而k-CS算法的查詢誤差率在兩種查詢上均低于20%，顯示出良好的數(shù)據(jù)可用性。

3.3 運(yùn)行時(shí)間

本實(shí)驗(yàn)驗(yàn)證了算法的運(yùn)行時(shí)間。k-CS算法的運(yùn)行時(shí)間僅計(jì)算了聚類所需。兩個(gè)算法的運(yùn)行時(shí)間都隨著隱私保護(hù)參數(shù)k的取值增大而減少?？梢钥闯鰇-CS算法的運(yùn)行時(shí)間優(yōu)于(k,δ)-anonymity算法，但是兩種算法的運(yùn)行時(shí)間都在百秒級(jí)別，并不適合在實(shí)時(shí)環(huán)境中使用。由于本文所提出的算法主要用在離線軌跡數(shù)據(jù)處理之上，算法運(yùn)行時(shí)間可以滿足要求。

圖7 兩種算法查詢誤差率對(duì)比

圖8 兩種算法的運(yùn)行時(shí)間對(duì)比

4 結(jié)語(yǔ)

本文提出一種路網(wǎng)環(huán)境中基于語(yǔ)義位置的隱私保護(hù)方法。該方法的最大貢獻(xiàn)在于，僅對(duì)軌跡上停留的語(yǔ)義位置進(jìn)行匿名，信息丟失率較低。本文首先提出路網(wǎng)環(huán)境中針對(duì)軌跡數(shù)據(jù)的兩種攻擊模型，將隱私保護(hù)問(wèn)題定義為k-CS匿名問(wèn)題，并證明了該問(wèn)題是一個(gè)NP-hard問(wèn)題。隨后提出一種基于圖中頂點(diǎn)聚類的近似算法，將圖中的頂點(diǎn)進(jìn)行聚類。最后實(shí)驗(yàn)驗(yàn)證了該算法的數(shù)據(jù)可用性和算法效率。后續(xù)工作包括繼續(xù)優(yōu)化圖上的聚類算法，提高其精確度及運(yùn)行效率。

References)

[1] ZHENG Y. Trajectory data mining: an overview [J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): 1-41.

[2] PARENT C, SPACCAPICTRA S, RENSO C, et al. Semantic trajectories modeling and analysis [J]. ACM Computing Surveys, 2013, 45(4): 42.

[3] DAI J, HUA L. A method for the trajectory privacy protection based on the segmented fake trajectory under road networks [C]// Proceedings of the 2nd International Conference on Information Science and Control Engineering. Piscataway, NJ: IEEE, 2015: 13-17.

[4] 趙婧,張淵,李興華,等.基于軌跡頻率抑制的軌跡隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(10):2096-2106.(ZHAO J, ZHANG Y, LI X H, et al. A trajectory privacy protection approach via trajectory frequency suppression [J]. Chinese Journal of Computers, 2014, 37(10): 2096-2196.)

[5] HUO Z, MENG X, HU H, et al. You can walk alone: trajectory privacy-preserving through significant stays protection [C]// Proceedings of the 17th International Conference on Database Systems for Advanced Applications. Berlin: Springer, 2012: 351-366.

[6] CAI Z F, YANG H X, SHUANH W, et al. A clustering-based privacy-preserving method for uncertain trajectory data [C]// Proceedings of the 2014 International Conference on Trust, Security and Privacy in Computing and Communications. Piscataway, NJ: IEEE, 2014: 1-8.

[7] ABUL O. BONCHI F. NANNI M. Anonymization of moving objects databases by clustering and perturbation [J]. Information Systems, 2010, 35(8): 884-910.

[8] 霍崢,孟小峰,黃毅.PrivateCheckIn:一種移動(dòng)社交網(wǎng)絡(luò)中的軌跡隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2013:36(4):716-726.(HUO Z, MENG X F, HUANG Y. PrivateCheckIn: trajectory privacy-preserving for check-in services in MSNS [J]. Chinese Journal of Computers, 2013, 36(4): 716-726.)

[9] HUA J, GAO Y, ZHONG S. Differentially private publication of general time-serial trajectory data [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2015: 549-557.

[10] PAN X, XU J, MENG X. Protecting location privacy against location-dependent attacks in mobile services [J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(8): 1506-1519.

[11] CHOI T Y. A linear-time heuristic algorithm fork-way network partitioning [J]. Journal of the Korea Safety Management and Science, 2004, 7(8): 1183-1194.

[12] YAROVOY R, BONCHI F, LAKSHMANAN L, et al. Anonymizing moving objects: how to hide a MOB in a crowd? [C] // Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. New York: ACM, 2009: 72-83.

[13] CHEN R, LI H, QIN K A, et al. Private spatial data aggregation in local setting [C]// Proceedings of the 32nd IEEE International Conference on Data Engineering. Piscataway, NJ: IEEE, 2016: 289-300.

[14] SU S, TANG P, CHENG X, et al. Differentially private multi-party high-dimensional data publishing [C]// Proceedings of the 2016 International Conference on Data Engineering. Piscataway, NJ: IEEE, 2016: 205-216.

[15] QIN Z, YANG Y, YU T, et al. Heavy hitter estimation over set-valued data with local differential privacy [C]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 192-203.

[16] 孟小峰,張嘯劍.大數(shù)據(jù)隱私管理[J].計(jì)算機(jī)研究與發(fā)展,2016,52(2):265-281.(MENG X F, ZHANG X J. Big data privacy management [J]. Journal of Computer Research and Development, 2016, 52(2): 265-281.)

This work is partially supported by the National Natural Science Foundation of China (61502279), the Natural Science Foundation of Hebei Province (F2015207009), the Scientific Research Projects in Colleges and Universities in Hebei Province (BJ2016019, QN2016179), the Soft Science Project of Ningbo City (2016A10066).

HUOZheng, born in 1982, Ph. D., lecturer. Her research interests include privacy-preserving, mobile object database.

CUIHonglei, born in 1976, Ph. D., lecturer. Her research interests include economic data applications under big data environment.

HEPing, born in 1982, Ph. D., lecturer. Her research interests include wireless sensor network, graph optimization algorithm.