基于指數(shù)機(jī)制的軌跡差分隱私保護(hù)方法

焦薈聰，劉文菊，王賾

天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300384

0 引言

基于位置的服務(wù)近年來不斷地出現(xiàn)在各個(gè)社交軟件中，隨著大數(shù)據(jù)時(shí)代的到來，多種軟件帶有全球定位系統(tǒng)（global positioning system，GPS），便于數(shù)據(jù)提供商收集用戶信息進(jìn)行數(shù)據(jù)分析和數(shù)據(jù)挖掘，以便為用戶提供更優(yōu)質(zhì)的服務(wù)。連續(xù)的基于位置的服務(wù)（location-based service，LBS）簽到形成一系列帶有時(shí)間屬性的軌跡數(shù)據(jù)，這些軌跡信息攜帶很多可通過相關(guān)性及某些屬性信息帶來推斷攻擊的信息，造成用戶敏感信息隱私泄露，帶來很大的安全隱患。為了達(dá)到保護(hù)隱私軌跡數(shù)據(jù)的目的，相比于僅對(duì)單個(gè)位置點(diǎn)進(jìn)行保護(hù)，對(duì)整條軌跡進(jìn)行保護(hù)才是當(dāng)下更重要的問題。目前針對(duì)軌跡的隱私保護(hù)方法可以大致分為3類：泛化（匿名區(qū)域）、抑制（抑制敏感位置）、擾動(dòng)（差分隱私，生成假位置）。參考文獻(xiàn)[1]通過保護(hù)停留點(diǎn)，使用k匿名算法構(gòu)建匿名區(qū)域的方式保護(hù)了敏感信息，同時(shí)降低了整個(gè)軌跡暴露的概率。參考文獻(xiàn)[2]提出基于k-means++的軌跡(k, l,δ)-匿名算法，能有效抵抗軌跡相似性攻擊?？臻g匿名技術(shù)具有較高的隱私保護(hù)水平，部署簡(jiǎn)單，計(jì)算開銷較小，但是要以犧牲服務(wù)質(zhì)量為代價(jià)。參考文獻(xiàn)[3]依據(jù)語(yǔ)義位置流行度、用戶設(shè)定的敏感語(yǔ)義位置類型及語(yǔ)義安全閾值對(duì)軌跡停留位置進(jìn)行空間匿名，構(gòu)建語(yǔ)義安全匿名區(qū)域，防止語(yǔ)義推斷攻擊。參考文獻(xiàn)[4]以局部抑制代替全局抑制的方式實(shí)現(xiàn)軌跡數(shù)據(jù)的隱私保護(hù)，降低數(shù)據(jù)損失率并提高軌跡數(shù)據(jù)的可用性。參考文獻(xiàn)[5]通過離散度控制假位置的分布情況，生成語(yǔ)義安全且分布稀疏的匿名集。然而，這些方法雖然可以保護(hù)數(shù)據(jù)的隱私，但它們都需要特殊的攻擊假設(shè)和背景知識(shí)，而且無(wú)法提供一種有效且嚴(yán)格的方法來證明其隱私保護(hù)水平。

2008 年Dwork C[6]提出了一種更加嚴(yán)格的可證明隱私定義，即差分隱私保護(hù)方法。差分隱私由于其嚴(yán)格的可證明的安全性被廣泛應(yīng)用于數(shù)據(jù)隱私保護(hù)領(lǐng)域，目前逐漸成為主流的位置隱私保護(hù)方法。它主要有3個(gè)優(yōu)點(diǎn)：一是用戶的隱私泄露風(fēng)險(xiǎn)與攻擊者掌握的背景知識(shí)量無(wú)關(guān)；二是它基于嚴(yán)格的數(shù)學(xué)證明，提供的隱私保護(hù)水平可以定量分析；三是隱私保護(hù)需要添加的噪聲大小可以通過調(diào)整差分隱私預(yù)算來控制，不會(huì)隨著數(shù)據(jù)集的變化而變化。參考文獻(xiàn)[7]綜合考慮軌跡上位置點(diǎn)的分布規(guī)律，利用希爾伯特曲線的性質(zhì)對(duì)空間上的位置點(diǎn)進(jìn)行降維映射，對(duì)空間點(diǎn)離散模式進(jìn)行研究，提出了一種空間劃分方法，劃分后的區(qū)域全部使用其區(qū)域中心點(diǎn)來替換，對(duì)聚合后的軌跡進(jìn)行發(fā)布，但是未考慮語(yǔ)義位置對(duì)聚類產(chǎn)生的語(yǔ)義推斷攻擊。參考文獻(xiàn)[8]利用最小描述長(zhǎng)度（minimum description length, MDL）算法對(duì)整條軌跡進(jìn)行精簡(jiǎn)處理，利用前綴樹存儲(chǔ)軌跡段信息，對(duì)軌跡段計(jì)數(shù)進(jìn)行差分隱私保護(hù)。但是由于前綴樹結(jié)構(gòu)假設(shè)數(shù)據(jù)有很多相同的前綴，而實(shí)際軌跡中位置點(diǎn)大多是分散的，因此該方法并不理想。參考文獻(xiàn)[9]根據(jù)空間稀疏性以及最大運(yùn)行速度提出兩種空間攻擊模型，以用戶最大運(yùn)行速度為約束提出了一種有效的一致性處理方法，使用四叉樹對(duì)空間進(jìn)行數(shù)據(jù)索引以及使用R樹對(duì)路網(wǎng)進(jìn)行數(shù)據(jù)索引發(fā)布。參考文獻(xiàn)[10]提出了隱式位置的概念，建立了推演泄露模式的模型，通過位置替換和抑制對(duì)敏感位置進(jìn)行匿名，同時(shí)考慮了用戶行為模式和軌跡特征提出了兩種約束模型。基于此，為了避免軌跡發(fā)布過程中語(yǔ)義信息帶來的隱私泄露，同時(shí)提高軌跡發(fā)布的可用性，本文將位置空間屬性和位置語(yǔ)義特征屬性相結(jié)合，提出一種基于指數(shù)機(jī)制的軌跡差分隱私保護(hù)方法。

1 相關(guān)定義

1.1 語(yǔ)義軌跡數(shù)據(jù)庫(kù)

語(yǔ)義是具有坐標(biāo)位置的一個(gè)很重要的屬性，本文通過高德地圖公開的應(yīng)用程序接口（application program interface，API）獲取每一個(gè)位置的地理標(biāo)簽及語(yǔ)義類別編碼，將語(yǔ)義分為如圖1所示的3個(gè)類別，以餐飲服務(wù)為例，餐飲服務(wù)屬于大類，餐飲服務(wù)包括快餐廳，快餐廳包含肯德基、麥當(dāng)勞等具體快餐品牌。本文共有23個(gè)大類、800多個(gè)小類。語(yǔ)義軌跡數(shù)據(jù)代表空間中一個(gè)移動(dòng)對(duì)象的運(yùn)行軌跡，包含多個(gè)時(shí)空位置點(diǎn)。單個(gè)位置的數(shù)據(jù)結(jié)構(gòu)l={userid, lon, lat, time, sen_type, sen_typecode}，其中userid代表用戶ID，lon代表經(jīng)度，lat代表緯度，time代表時(shí)間，sen_type代表語(yǔ)義類型，sen_typecode代表語(yǔ)義類型編碼。語(yǔ)義時(shí)空軌跡數(shù)據(jù)庫(kù)是由|D|條語(yǔ)義軌跡構(gòu)成的數(shù)據(jù)集，D={T1,T2,…,Tn}。

圖1 語(yǔ)義分類

1.2 語(yǔ)義位置敏感度

信息熵的概念起源于香農(nóng)信息論[11]，是一種可應(yīng)用在很多領(lǐng)域的隱私度量方法，熵值越大，說明該位置的不確定性越高[12]，基本計(jì)算式如式（1）所示：

設(shè)sloc是一個(gè)語(yǔ)義位置，用戶ui對(duì)位置sloc的訪問總次數(shù)記為ni，對(duì)所有位置的訪問總次數(shù)記為N。因此，用戶ui對(duì)位置sloc訪問總次數(shù)占所有位置被訪問總次數(shù)的比例可表示為式（2）：

根據(jù)式（1）可以計(jì)算出位置信息熵，如式（3）所示：

不同于傳統(tǒng)概念中針對(duì)所有用戶進(jìn)行計(jì)算，本文根據(jù)不同用戶需求，設(shè)計(jì)語(yǔ)義位置敏感度計(jì)算式，如式（4）所示：

Sen(ui.sloc)的值越大，該位置對(duì)于當(dāng)前用戶越重要，隱私保護(hù)水平越高。

1.3 差分隱私

定義1差分隱私[12-13]給定隨機(jī)算法M及相鄰數(shù)據(jù)集D1和D2，其中D1和D2相差1條數(shù)據(jù)。對(duì)于算法M在數(shù)據(jù)集D1和D2上的任意輸出O，若滿足式（5），則稱隨機(jī)算法M滿足ε-差分隱私。

其中，Pr[·]由隨機(jī)算法M控制，表示隱私被披露的風(fēng)險(xiǎn)。ε是一個(gè)可以調(diào)節(jié)的參數(shù)，稱為隱私預(yù)算，它決定隱私保護(hù)的程度和發(fā)布數(shù)據(jù)集的精度，ε越接近0，算法M在D1和D2上輸出相同結(jié)果的概率越接近1，隱私保護(hù)程度越高，相應(yīng)的發(fā)布數(shù)據(jù)集的精度也就越低，可用性越低。

定義2全局敏感度。對(duì)于任意一個(gè)查詢函數(shù)f:D→Rd，D表示數(shù)據(jù)集，R表示所映射的實(shí)數(shù)空間，d表示函數(shù)f的查詢維度，該函數(shù)作用于數(shù)據(jù)集D后返回一個(gè)d維向量，其全局敏感度如式（6）所示：

其中，D1和D2是任意兩個(gè)相鄰數(shù)據(jù)集。

定義3指數(shù)機(jī)制。給定數(shù)據(jù)集D及隨機(jī)算法M，M的輸出為實(shí)體對(duì)象r，用u(D,r)表示打分函數(shù)，用來評(píng)估輸出值r的優(yōu)劣程度，Δf表示打分函數(shù)的全局敏感度，如果M以正比于P的概率從R中選擇并輸出r，那么M滿足ε-差分隱私，如式（7）所示：

1.4 停留區(qū)域

GPS愈來愈精確。在海量的軌跡數(shù)據(jù)中，每條軌跡位置點(diǎn)擁有很大的體量，但并非所有位置點(diǎn)都是有意義的，用戶頻繁且長(zhǎng)時(shí)間停留的區(qū)域容易暴露用戶的行為模式[14]，只有能代表用戶行為模式的位置點(diǎn)具有代表性。本文利用已有文獻(xiàn)中提出的興趣區(qū)域的概念，設(shè)置時(shí)間閾值和距離閾值，將用戶長(zhǎng)時(shí)間停留的相近位置點(diǎn)集合定義為停留區(qū)域，對(duì)停留區(qū)域包含的實(shí)際位置點(diǎn)進(jìn)行隱私保護(hù)。

1.5 基于語(yǔ)義背景知識(shí)的攻擊

一個(gè)位置，除了地理上的形狀還有一些語(yǔ)義信息（如學(xué)校、醫(yī)院、電影院等），這些語(yǔ)義信息依賴于這個(gè)位置上的實(shí)體。攻擊者將地理空間信息和語(yǔ)義信息相結(jié)合，可以有效推測(cè)出用戶的位置?；谖恢谜Z(yǔ)義背景知識(shí)的攻擊中最常見的是語(yǔ)義推斷攻擊[15]，當(dāng)發(fā)布的軌跡數(shù)據(jù)集中包含大量的用戶敏感語(yǔ)義位置時(shí)，攻擊者就可以根據(jù)此語(yǔ)義進(jìn)一步推測(cè)出用戶的其他敏感信息。例如，用戶A的簡(jiǎn)單軌跡記錄示例見表1。用戶A一個(gè)月的軌跡記錄中頻繁出現(xiàn)某小區(qū)到某醫(yī)院的軌跡，攻擊者結(jié)合地理信息等其他公開信息可以推測(cè)出該用戶的家庭地址，并知曉該用戶是患者或者職業(yè)是醫(yī)生；再結(jié)合軌跡中的時(shí)間信息，前往醫(yī)院的時(shí)間符合上下班的規(guī)律，可以初步推斷用戶A是一名在職醫(yī)生；再通過其他信息得知用戶A的家庭信息、個(gè)人愛好等，進(jìn)而竊取用戶敏感信息。

表1 用戶A的簡(jiǎn)單軌跡記錄示例

2 基于指數(shù)機(jī)制的軌跡差分隱私保護(hù)方法

差分隱私的指數(shù)機(jī)制是面向非數(shù)值性數(shù)據(jù)的一種隱私保護(hù)機(jī)制。指數(shù)機(jī)制以一定的概率值返回一個(gè)數(shù)值，從而實(shí)現(xiàn)差分隱私，概率值由打分函數(shù)確定。筆者基于此提出一種基于位置空間屬性和位置語(yǔ)義的軌跡隱私保護(hù)方法，并根據(jù)指數(shù)機(jī)制特性進(jìn)行設(shè)計(jì)，減少位置語(yǔ)義信息帶來的隱私泄露問題。

為了抵抗語(yǔ)義推斷攻擊，本文通過抑制發(fā)布和差分隱私技術(shù)相結(jié)合來設(shè)計(jì)算法。指數(shù)機(jī)制核心概念是設(shè)計(jì)打分函數(shù)，對(duì)于數(shù)據(jù)集合中的語(yǔ)義位置來說，對(duì)每個(gè)位置進(jìn)行打分，打分越高的位置輸出概率越高，同時(shí)加入差分隱私技術(shù)的隨機(jī)化來達(dá)到隱私保護(hù)的目的。本文設(shè)計(jì)打分函數(shù)，使用戶位置敏感度較低的位置分?jǐn)?shù)高，這樣在隨機(jī)輸出時(shí)，敏感語(yǔ)義位置大概率不被發(fā)布，同時(shí)結(jié)合地理位置屬性保持空間特征，保護(hù)用戶隱私。

2.1 設(shè)計(jì)思路

本文提出一種基于指數(shù)機(jī)制的軌跡差分隱私保護(hù)方法，主要設(shè)計(jì)思路如下。

● 根據(jù)停留區(qū)域挖掘算法得到整條軌跡中的停留區(qū)域集合，即需保護(hù)隱私的軌跡位置區(qū)域。

● 根據(jù)改進(jìn)的MDL算法計(jì)算待保護(hù)區(qū)域中包含所有位置點(diǎn)的軌跡特征保持度，根據(jù)語(yǔ)義位置敏感度計(jì)算待保護(hù)區(qū)域中包含所有位置點(diǎn)的語(yǔ)義隱私度。

● 結(jié)合語(yǔ)義隱私度和位置軌跡特征保持度設(shè)計(jì)打分函數(shù)，利用指數(shù)機(jī)制將待保護(hù)區(qū)域內(nèi)位置點(diǎn)進(jìn)行隨機(jī)輸出，刪除其他位置點(diǎn)，發(fā)布隱私保護(hù)后的軌跡。

2.2 算法設(shè)計(jì)

基于指數(shù)機(jī)制的軌跡差分隱私保護(hù)方法框架如圖2所示，其中核心部分在于指數(shù)機(jī)制打分函數(shù)設(shè)計(jì)。

圖2 基于指數(shù)機(jī)制的軌跡差分隱私保護(hù)方法框架

（1）停留區(qū)域挖掘

假設(shè)某條軌跡T={L1，L2，L3，…，Ln},其中Li代表一個(gè)位置點(diǎn)，該位置點(diǎn)攜帶語(yǔ)義屬性及地理屬性經(jīng)緯度信息。設(shè)置時(shí)間閾值ΔT和距離閾值ΔS。從軌跡第一個(gè)位置點(diǎn)開始，將該位置點(diǎn)記作start，并將其加入停留區(qū)域area，向后計(jì)算下一個(gè)位置點(diǎn)與該位置點(diǎn)的時(shí)間差Δt。如果Δt大于時(shí)間閾值，則計(jì)算兩點(diǎn)之間的距離差Δs（使用真實(shí)經(jīng)緯度距離計(jì)算實(shí)際位置距離）；如果Δs小于距離閾值，則將該位置點(diǎn)加入停留區(qū)域area，繼續(xù)遍歷下一個(gè)位置點(diǎn)，直至到達(dá)該條軌跡最后一個(gè)位置點(diǎn)，形成一個(gè)以start位置點(diǎn)為基礎(chǔ)點(diǎn)的停留區(qū)域area。接著遍歷除已形成的停留區(qū)域外的第一個(gè)位置點(diǎn)，將其作為start繼續(xù)挖掘停留區(qū)域，直至整個(gè)軌跡的停留區(qū)域全部形成。

（2）軌跡特征保持度計(jì)算

根據(jù)MDL算法計(jì)算待保護(hù)區(qū)域中包含所有位置點(diǎn)的軌跡特征保持程度權(quán)重值。在將MDL算法應(yīng)用于軌跡數(shù)據(jù)時(shí)，D是運(yùn)動(dòng)物體的軌跡數(shù)據(jù)集，H是運(yùn)動(dòng)物體軌跡的軌跡分割。本文方法中對(duì)停留區(qū)域和前后兩個(gè)位置點(diǎn)構(gòu)成的局部軌跡進(jìn)行軌跡特征保持，可利用MDL算法精確度高的特點(diǎn)，計(jì)算每個(gè)位置點(diǎn)的軌跡特征保持度。單個(gè)停留區(qū)域示意如圖3所示，該停留區(qū)域中n個(gè)位置點(diǎn)和前后兩個(gè)位置點(diǎn)構(gòu)成局部特征區(qū)域，根據(jù)實(shí)際坐標(biāo)計(jì)算出這n個(gè)位置點(diǎn)分別與前后兩個(gè)位置點(diǎn)的位置幾何權(quán)重，將平均值作為該位置的軌跡特征保持度。

對(duì)于停留區(qū)域內(nèi)的位置點(diǎn)ci，有式（8）所示關(guān)系：

某位置點(diǎn)的模型精度值等于該位置點(diǎn)與前后兩個(gè)端點(diǎn)的歐氏距離的平均值，如式（9）所示：

本文分兩部分計(jì)算模型復(fù)雜度。取該位置點(diǎn)與區(qū)域外鄰近的兩個(gè)位置點(diǎn)（圖3中s點(diǎn)和e點(diǎn)）分別計(jì)算復(fù)雜度值，根據(jù)MDL算法的定義求出垂直距離和角距離，計(jì)算后求平均值，如式（10）～式（13）所示：

圖3 單個(gè)停留區(qū)域示意

其中，W為總描述長(zhǎng)度，將每個(gè)位置點(diǎn)的W作為軌跡特征保持度輸出。

（3）語(yǔ)義隱私度計(jì)算

為了防止語(yǔ)義推斷攻擊，將位置語(yǔ)義屬性作為保護(hù)區(qū)域內(nèi)位置點(diǎn)的隱私度量。原始軌跡數(shù)據(jù)集中不包括語(yǔ)義屬性，為了保證方案的真實(shí)性，使用高德地圖的API，根據(jù)位置點(diǎn)對(duì)應(yīng)實(shí)際地圖上的經(jīng)緯度坐標(biāo)進(jìn)行語(yǔ)義爬取，采取距離該位置點(diǎn)最近的語(yǔ)義地點(diǎn)標(biāo)簽定義語(yǔ)義屬性，保證整個(gè)爬取過程距離范圍在200 m以內(nèi)。高德地圖將語(yǔ)義分為三大類別，據(jù)此對(duì)位置點(diǎn)語(yǔ)義屬性進(jìn)行語(yǔ)義編碼。挖掘到停留區(qū)域時(shí)，對(duì)包含的所有位置點(diǎn)提取語(yǔ)義屬性，根據(jù)式（4），基于位置熵的概念計(jì)算每個(gè)語(yǔ)義位置的語(yǔ)義敏感度，并將其作為語(yǔ)義特征權(quán)重，得出每個(gè)位置點(diǎn)的語(yǔ)義隱私度。語(yǔ)義隱私度的值越大，代表語(yǔ)義位置隱私需求越高。

（4）指數(shù)機(jī)制打分函數(shù)設(shè)計(jì)

差分隱私的指數(shù)機(jī)制關(guān)鍵在于打分函數(shù)的設(shè)計(jì)，打分函數(shù)設(shè)計(jì)的目的是可以以較大的概率輸出泄露用戶隱私概率最小的位置語(yǔ)義，同時(shí)最大限度保持軌跡特征變化，以保證隱私。本文打分函數(shù)如式（14）所示：

其中，D是興趣區(qū)域集合，r是想要輸出的抽樣的語(yǔ)義位置點(diǎn)。以正比于p(D,r)的概率將n種結(jié)果隨機(jī)輸出，如式（15）所示：

其中，ε是隱私預(yù)算，Δf是打分函數(shù)的全局敏感度，對(duì)興趣區(qū)域執(zhí)行隱私保護(hù)算法，輸出隱私泄露最小的語(yǔ)義位置，刪除其他語(yǔ)義位置。本文將所提方法命名為Index_DP算法，算法偽代碼如下。

算法1Index_DP算法

輸入：原始軌跡T={L1,L2,…,Ln}，軌跡長(zhǎng)度N，距離閾值ΔS，時(shí)間閾值ΔT

輸出：隱私保護(hù)后的軌跡T1

1：fori=1;i＜N；i++ do

2： if Δt(Li,Li+1)＜ΔTand Δs(Li,Li+1)＞ΔSthen

3： 將Li,Li+1加入停留區(qū)域A

4： 對(duì)于A={Lj,Lj+1,…,Lj+n}

5： ifLj+n!=Lnthen

6： 將A加入鄰近位置，形成帶邊界區(qū)域E

7：g=MDL(A,E)

8： s=-p×np.log2(p)

9： 設(shè)計(jì)打分函數(shù)score=1-sen_w/2geo_w

10： out=index_mechanism(A,pr)

11： end if

12： end if

13：end for

14：end

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

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

本文的實(shí)驗(yàn)環(huán)境為Windows 10版本操作系統(tǒng)，編程語(yǔ)言使用Python，采用的數(shù)據(jù)集是真實(shí)用戶軌跡采樣Geolife數(shù)據(jù)集。Geolife數(shù)據(jù)集是微軟亞洲研究院項(xiàng)目組歷時(shí)5年多收集的182位用戶的GPS軌跡數(shù)據(jù)集，GPS軌跡由一系列時(shí)間戳點(diǎn)表示，每個(gè)點(diǎn)包含緯度、經(jīng)度和時(shí)間信息。該數(shù)據(jù)集包含17 621條軌跡，經(jīng)過初步篩選，最短軌跡包含300個(gè)攜帶語(yǔ)義屬性的位置點(diǎn)，最長(zhǎng)軌跡包含2 000個(gè)軌跡點(diǎn)。在原始軌跡數(shù)據(jù)集上，通過高德地圖API爬取每個(gè)位置點(diǎn)在地圖上對(duì)應(yīng)的語(yǔ)義信息，將語(yǔ)義類型編碼作為不同語(yǔ)義的象征，并添加到軌跡每個(gè)位置點(diǎn)的屬性當(dāng)中，作為軌跡隱私保護(hù)的一個(gè)屬性。

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

（1）數(shù)據(jù)可用性

本文采用動(dòng)態(tài)時(shí)間彎曲（dynamic time warping，DTW）[14,16]距離來衡量隱私保護(hù)前后軌跡的失真度。DTW是一個(gè)動(dòng)態(tài)迭代的過程，原始軌跡T1={L1,L2,L3,…,Lm}和處理后的可發(fā)布軌跡T2={C1,C2,C3,…,Cn}的長(zhǎng)度分別為m和n，則兩條軌跡之間的DTW距離計(jì)算式如式（16）所示：

（2）隱私保護(hù)度

使用差分隱私中的指數(shù)機(jī)制對(duì)軌跡進(jìn)行隱私保護(hù)，分析不同的隱私預(yù)算對(duì)軌跡可用性的影響來衡量差分隱私方法的隱私保護(hù)度。從差分隱私指數(shù)機(jī)制的定義可以得出，隱私預(yù)算與可用性成正比，與隱私保護(hù)成反比。

3.3 實(shí)驗(yàn)結(jié)果

為了分析算法效果，將本文提出的Index_DP算法分別與參考文獻(xiàn)[17]提出的ANoise算法以及參考文獻(xiàn)[18]提出的GNoise算法進(jìn)行對(duì)比。

（1）不同參數(shù)設(shè)定下算法性能對(duì)比

分析在不同的時(shí)間閾值及不同的距離閾值下，Index_DP算法對(duì)數(shù)據(jù)可用性產(chǎn)生的影響。首先分析在時(shí)間閾值固定的情況下，距離閾值不同時(shí)軌跡的失真度變化趨勢(shì)。時(shí)間閾值為10 min時(shí)，距離閾值分別為200 m、400 m、800 m時(shí)的失真度變化趨勢(shì)如圖4所示。隨著距離閾值的增大，軌跡失真度增加，這是由于在停留區(qū)域挖掘過程中，距離范圍越大，停留區(qū)域中包含的軌跡位置點(diǎn)越多，保護(hù)的隱私區(qū)域越大，導(dǎo)致處理之后的軌跡長(zhǎng)度越短，與原始軌跡差異性越大。

圖4 時(shí)間閾值為10 min時(shí)，距離閾值分別為200 m、400 m、800 m時(shí)的失真度變化趨勢(shì)

分析在距離閾值固定的情況下，時(shí)間閾值不同時(shí)軌跡的失真度變化趨勢(shì)。距離閾值為400 m時(shí)，時(shí)間閾值分別為5 min、10 min、15 min時(shí)3種算法的失真度變化趨勢(shì)如圖5所示。隨著時(shí)間閾值的增大，軌跡失真度降低，這是由于搜索的時(shí)間越短，保護(hù)的隱私區(qū)域越小，處理后軌跡失真度越低。

圖5 距離閾值為400 m時(shí)，時(shí)間閾值分別為5 min、10 min、15 min時(shí)3種算法的失真度變化趨勢(shì)

（2）不同閾值下算法性能對(duì)比

選取距離閾值為400 m，分別取時(shí)間閾值為5 min、10 min、15 min和20 min，在軌跡數(shù)據(jù)集中隨意抽取10條軌跡計(jì)算出4個(gè)時(shí)間閾值下的軌跡失真度后取平均值，3種算法分別進(jìn)行實(shí)驗(yàn)得出結(jié)果如圖6所示。圖6中橫軸對(duì)應(yīng)的是本文實(shí)驗(yàn)中選取的4個(gè)時(shí)間閾值，縱軸對(duì)應(yīng)的是軌跡失真度，失真度的值越高，代表軌跡的可用性越差。由圖6中可以看出，Index_DP算法在不同時(shí)間閾值下的平均失真度均小于其他兩種算法。隨著時(shí)間閾值的增大，3種算法的失真度都大致呈現(xiàn)減小趨勢(shì)，符合停留區(qū)域挖掘算法的閾值影響。在時(shí)間閾值為5 min時(shí)，Index_DP算法失真度為0.0158；ANoise算法失真度為0.0608，比Index_DP算法高0.045；GNoise算法采用純加噪聲的方法使其失真度最高達(dá)到0.209。由此可見Index_DP算法在對(duì)軌跡進(jìn)行隱私保護(hù)后，軌跡的信息損失遠(yuǎn)低于GNoise算法和ANoise算法，大大提高了軌跡可用性。

圖6 距離閾值為400 m，時(shí)間閾值分別為5 min、10 min、15 min和20 min時(shí)3種算法的失真度變化趨勢(shì)

時(shí)間閾值為10 min，距離閾值分別為200 m、300 m、500 m和700 m時(shí)3種算法的失真度變化趨勢(shì)如圖7所示。由圖7可知，在距離閾值變化下Index_DP算法在對(duì)軌跡進(jìn)行隱私保護(hù)后軌跡的信息損失仍然最小，且遠(yuǎn)低于GNoise算法和ANoise算法。隨著時(shí)間閾值和距離閾值的不斷變化，Index_DP算法的平均失真度并未產(chǎn)生較大波動(dòng)，均小于0.05，而ANoise算法的失真度基本為0.05以上。由實(shí)驗(yàn)可知，Index_DP算法不僅大大提高了軌跡可用性，且具有很好的延展性，在當(dāng)前大數(shù)據(jù)情況下，軌跡長(zhǎng)度越來越長(zhǎng)，軌跡數(shù)量越來越多，本文算法仍有良好的普適性。

圖7 時(shí)間閾值為10 min，距離閾值分別為200 m、300 m、500 m和700 m時(shí)3種算法的失真度變化趨勢(shì)

（3）不同隱私保護(hù)度下算法性能對(duì)比

差分隱私的隱私保護(hù)程度與隱私預(yù)算ε有關(guān)，分析不同的ε取值對(duì)平均失真度的影響。由于本文方法設(shè)計(jì)目的是在越來越長(zhǎng)的軌跡趨勢(shì)下保護(hù)軌跡隱私，且每個(gè)用戶軌跡長(zhǎng)度各有不同，本文將用戶軌跡大致分為3組進(jìn)行對(duì)比試驗(yàn)，分別為500～1 000 m、1 000～1 500 m以及1 500～2 000 m。在本文數(shù)據(jù)集中，軌跡長(zhǎng)度在1 000～1 500 m的軌跡數(shù)量最多，軌跡長(zhǎng)度在500 m以下的軌跡較少，因此不考慮該部分軌跡。由表2可以看出，不同的軌跡長(zhǎng)度在軌跡失真度上的變化沒有逐漸增大，1 500～2 000 m分段的軌跡失真度小于500～1 000 m的軌跡失真度，說明Index_DP算法可以適用在更長(zhǎng)的軌跡上，具有很好的延展性。

由表2可以看出，隨著隱私預(yù)算ε增大，數(shù)據(jù)失真度逐漸降低，這是由Index_DP算法設(shè)計(jì)的打分函數(shù)的目標(biāo)及指數(shù)機(jī)制的性質(zhì)決定的。ε越大，選擇出期望結(jié)果的可能性也越大，軌跡保持更好。打分函數(shù)設(shè)計(jì)的目的首先是保證語(yǔ)義位置的隱私，其次是盡可能地保持軌跡特征，軌跡保持得更好的情況下也會(huì)更大概率地泄露敏感位置，隱私預(yù)算與可用性成正比，與隱私保護(hù)成反比，這個(gè)結(jié)果符合差分隱私指數(shù)機(jī)制的規(guī)律。由表2可以看到大部分的軌跡受隱私預(yù)算影響不大，這是因?yàn)樵谠摍C(jī)制中加入的語(yǔ)義屬性對(duì)打分函數(shù)進(jìn)行了一部分約束，本文主要目的是在保護(hù)隱私的情況下盡可能提高軌跡可用性，因此為了同時(shí)兼顧語(yǔ)義安全和保持軌跡特征，犧牲了一部分可用性。

表2 不同隱私預(yù)算下的失真度分析

4 結(jié)束語(yǔ)

本文提出了一種基于指數(shù)機(jī)制的軌跡差分隱私保護(hù)方法。此方法針對(duì)軌跡位置隱私保護(hù)中往往忽略位置點(diǎn)的語(yǔ)義屬性帶來的隱私泄露問題，在對(duì)軌跡進(jìn)行保護(hù)時(shí)不僅考慮其隱私保護(hù)，也要保證軌跡本身的特征盡可能不發(fā)生較大的改變，保證隱私保護(hù)后軌跡的可用性。根據(jù)語(yǔ)義時(shí)空軌跡本身的特性，使用差分隱私方法中的指數(shù)機(jī)制，對(duì)停留區(qū)域中具有不同隱私水平的位置點(diǎn)進(jìn)行概率隨機(jī)化選擇輸出，由此對(duì)軌跡進(jìn)行隱私保護(hù)?；谕Ａ魠^(qū)域的概念，考慮位置點(diǎn)地理幾何特征的同時(shí)，為了防止語(yǔ)義推斷攻擊在原始數(shù)據(jù)集上融入位置語(yǔ)義屬性，使用指數(shù)機(jī)制在保證隱私條件下對(duì)區(qū)域內(nèi)語(yǔ)義位置進(jìn)行抽樣選擇。在真實(shí)數(shù)據(jù)集上進(jìn)行的多次仿真實(shí)驗(yàn)證明了Index_DP算法具有良好的延展性和普適性，在軌跡保護(hù)中有效地提高了數(shù)據(jù)可用性。由于本文使用了比較復(fù)雜的數(shù)學(xué)模型，下一階段將考慮如何降低算法的運(yùn)行時(shí)間，提高運(yùn)行效率。