基于噪音前綴樹(shù)的軌跡數(shù)據(jù)發(fā)布隱私保護(hù)算法研究

石秀金，徐嘉敏，王 銳，張姝儷

（東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海201620）

0 引 言

隨著定位技術(shù)的快速發(fā)展和廣泛應(yīng)用，越來(lái)越多的軌跡數(shù)據(jù)被產(chǎn)生、發(fā)布、采集和分析。如車(chē)載定位系統(tǒng)，帶GPS的移動(dòng)設(shè)備以及位置傳感器等，這些設(shè)備在提高人們生活質(zhì)量的同時(shí)也產(chǎn)生了大量的軌跡數(shù)據(jù)，其中可能包含車(chē)輛、身份以及實(shí)時(shí)位置等諸多數(shù)據(jù)，然而這些內(nèi)容都含有個(gè)人敏感信息，直接發(fā)布會(huì)給個(gè)人隱私造成威脅。因此，對(duì)軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)具有重要的研究意義。

在軌跡數(shù)據(jù)的發(fā)布中，最簡(jiǎn)單的方式是刪除軌跡上的準(zhǔn)標(biāo)識(shí)符屬性［1］，如個(gè)人基本信息，但卻不能全面保護(hù)移動(dòng)對(duì)象的軌跡隱私。k-匿名模型［2-3］能夠在一定程度上保護(hù)軌跡隱私，但是該模型具有容易受到新型攻擊、系統(tǒng)開(kāi)銷(xiāo)大等缺陷，因此隨著數(shù)據(jù)的大量收集，這種模型并不能有效保證軌跡信息。

文獻(xiàn)［4］中證明采用差分隱私保護(hù)模型，使用合理數(shù)量的噪音保護(hù)位置數(shù)據(jù)中的敏感信息，而且還能保證數(shù)據(jù)的可用性。差分隱私方法提供了嚴(yán)格的隱私模型來(lái)保護(hù)空間信息中的敏感數(shù)據(jù)，同時(shí)能夠保證發(fā)布數(shù)據(jù)的實(shí)用性，也并不關(guān)心攻擊者擁有的背景知識(shí)，該模型向查詢或者分析結(jié)果中添加一定量的噪音來(lái)達(dá)到隱私保護(hù)的效果。差分隱私模型可以應(yīng)用于數(shù)據(jù)發(fā)布、數(shù)據(jù)挖掘、個(gè)性化推薦等諸多領(lǐng)域。

對(duì)于軌跡數(shù)據(jù)的發(fā)布，已有不少研究者考慮到用差分隱私模型來(lái)實(shí)現(xiàn)軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)。2012年，Chen等人［5］提出一種基于噪音前綴樹(shù)的交通數(shù)據(jù)發(fā)布隱私保護(hù)方式，并通過(guò)實(shí)驗(yàn)證明這種方式可以應(yīng)用于軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)研究領(lǐng)域。文獻(xiàn)［6］提出基于差分隱私保護(hù)的軌跡序列非交互式合成方式，然而這種方式局限于短距離內(nèi)的軌跡數(shù)據(jù)隱私保護(hù)，在更大規(guī)模的空間區(qū)域和實(shí)際情況中是無(wú)效的。2012年，Chen等人［7］又提出通過(guò)n-gram思想解決短距離問(wèn)題，然而這種方式導(dǎo)致了軌跡序列的丟失。

在綜合上文研究成果后，本文提出了一種基于噪音前綴樹(shù)的軌跡數(shù)據(jù)隱私保護(hù)算法。該算法分3步，可描述為：首先將軌跡數(shù)據(jù)離散化后通過(guò)聚類(lèi)分析獲得具有某些特定性質(zhì)的特征點(diǎn)（本文稱為錨點(diǎn)），對(duì)錨點(diǎn)進(jìn)行隱私保護(hù)后構(gòu)建參考系；然后基于該參考系對(duì)原始軌跡進(jìn)行校準(zhǔn)，并用校準(zhǔn)軌跡構(gòu)造噪音前綴樹(shù)；最后根據(jù)拉普拉斯機(jī)制向葉子節(jié)點(diǎn)中添加噪音，形成用于發(fā)布的數(shù)據(jù)版本。該算法在一定程度上解決了空間限制以及序列丟失等問(wèn)題。

1 問(wèn)題描述

軌跡數(shù)據(jù)是一組從實(shí)際路線中提取的位置有界和時(shí)間有序的序列，可以表示為：tj＝｛(x1，y1，t1)，(x2，y2，t2)，…， (xn，yn，tn) ｝。 其中， (xi，yi，ti)（1 ≤i≤n） 表示移動(dòng)對(duì)象在ti時(shí)刻的位置為（xi，yi） ，也稱為采樣位置或采樣點(diǎn)，ti則稱為采樣時(shí)間。若忽略具體采集到某個(gè)位置點(diǎn)的時(shí)間，而是在指定的時(shí)間段內(nèi)按照時(shí)間序列進(jìn)行排序，同時(shí)以p1表示(x1，y1)代表的位置點(diǎn)，則軌跡tj可以表示為tj＝｛p1，p2，…，pn｝。其中pi∈P，P表示一定區(qū)域內(nèi)站點(diǎn)位置的集合，｜P｜表示站點(diǎn)位置的數(shù)量且i≤｜P｜。

例如，假設(shè)p1(x1，y1)表示某小區(qū)，p2(x2，y2)表示某地鐵站，p3(x3，y3)表示某商場(chǎng)，p4(x4，y4)表示某學(xué)校，p5(x5，y5)表示某條路的第二個(gè)交叉路口，那么軌跡tj＝｛(x1，y1，t1)，(x2，y2，t2)，(x3，y3，t3)， (x1，y1，t4)｝表示：t1～t4時(shí)間段內(nèi)，車(chē)輛A從小區(qū)出發(fā)，先到達(dá)地鐵站，然后到達(dá)商場(chǎng)，最后在t6時(shí)刻回到小區(qū)。也可以表示為：在t1～t4時(shí)間段內(nèi)，tj＝｛p1，p2，p3，p1｝。

在指定時(shí)間內(nèi)，如以一周為期限，每次采樣的時(shí)長(zhǎng)為2 h，每周分別在周一和周三上午10：00～12：00進(jìn)行采樣，該車(chē)輛可能有不止一條軌跡數(shù)據(jù)產(chǎn)生，用ITq＝［tj1，tj2，…，tjk］表示該車(chē)在一周內(nèi)產(chǎn)生的軌跡數(shù)據(jù)。該周內(nèi)共產(chǎn)生的軌跡數(shù)據(jù)集為T(mén)＝［IT1，IT2，…，ITm］。 研究得到的由全部軌跡組成的一般的軌跡數(shù)據(jù)集可見(jiàn)表1。

考慮到后續(xù)的研究需要，這里關(guān)于文中涉及到的基礎(chǔ)概念理論將展開(kāi)探討論述如下。

定義1 錨點(diǎn)空間域中相對(duì)穩(wěn)定的特征位置點(diǎn)，其變化不大。如基于道路分析提取到的交叉點(diǎn)、轉(zhuǎn)折點(diǎn)，基于軌跡數(shù)據(jù)中的位置進(jìn)行聚類(lèi)分析提取到的質(zhì)心等。錨點(diǎn)用ai表示，數(shù)量上小于該數(shù)據(jù)集的位置總數(shù)｜P｜，錨點(diǎn)組成的集合稱為錨點(diǎn)集A，用來(lái)構(gòu)建參考系。

表1 軌跡數(shù)據(jù)集Tab.1 Trajectory data set

定義2 軌跡校準(zhǔn)基于由集合A構(gòu)成的參考系，校準(zhǔn)過(guò)程就是將原始軌跡tj＝［p1，p2，… ，pn］轉(zhuǎn)換為t＇j＝［a1，a2，…，am］。 其中，ai∈A， 1 ≤i≤m，m可以等于n。 稱t＇j是tj的校準(zhǔn)軌跡。

定義 3 差分隱私［4，8-10］給定數(shù)據(jù)集D和D＇，且D和D＇之間最多相差一條記錄，即｜DΔD＇｜≤1。 給定一個(gè)隱私算法A，Range（A） 表示A的取值范圍，若算法A在數(shù)據(jù)集D和D＇上任意輸出結(jié)果O（O∈Range（A））滿足下列不等式，則A滿足如下的ε-差分隱私：

其中，概率Pr［·］表示隱私的披露風(fēng)險(xiǎn)，由算法A的隨機(jī)性控制；隱私預(yù)算參數(shù)ε表示算法A所能提供的隱私保護(hù)程度。ε越大，隱私保護(hù)程度越低，反之，隱私保護(hù)程度越高。

由式（1）可以看出，差分隱私保護(hù)模型是基于2個(gè)只有一條記錄的不同數(shù)據(jù)集進(jìn)行數(shù)據(jù)失真處理的，結(jié)果是保證即使攻擊者知道大量的背景知識(shí)也無(wú)法準(zhǔn)確判斷該記錄是否在表中。

研究可知，差分隱私的組合特性［11］可分為2種，對(duì)其可做闡釋解析如下。

（1）順序組合。給定數(shù)據(jù)集D以及一組關(guān)于D的差分隱私A1（D），A2（D），…，Am（D），分別滿足ε-差分隱私，且任意2個(gè)算法的隨機(jī)過(guò)程相互獨(dú)立，則這些算法組合起來(lái)的算法滿足差分隱私。

（2）并行組合。A1（D），A2（D），…，Am（D）， 分別表示輸入集為D1，D2，…，Dm的一系列滿足ε-差分隱私算法，且任意2個(gè)算法的隨機(jī)過(guò)程相互獨(dú)立。則這些算法組合起來(lái)的算法滿足ε-差分隱私。

定義4 噪音前綴樹(shù)［12］序列數(shù)據(jù)集T的前綴樹(shù)PT是三元組PT＝（V，E，Root），其中V是標(biāo)記位置的節(jié)點(diǎn)集合，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于T中唯一的前綴；E是邊的集合，表示節(jié)點(diǎn)之間的轉(zhuǎn)換；Root∈V是PT的虛根。

定理1 拉普拉斯機(jī)制［12］拉普拉斯噪音實(shí)質(zhì)上是一組滿足拉普拉斯分布的隨機(jī)值，其原理是向原始數(shù)據(jù)及統(tǒng)計(jì)分析結(jié)果中添加服從拉普拉斯lap（b）的噪音，實(shí)現(xiàn)加入噪音后的查詢結(jié)果滿足差分隱私約束效果。文獻(xiàn)［8］提出拉普拉斯機(jī)制，則需要輸入數(shù)據(jù)集D，函數(shù)f和隱私參數(shù)α。 所添加的噪聲符合概率密度函數(shù)的拉普拉斯分布，其中λ由全局靈敏度f(wàn)和預(yù)期隱私參數(shù)α確定。

定義5 地理相似性［13］給定2條軌跡t1＝［p11，p12，……，p1n］和t2＝p21，p22，……，p2m， 地理相似性表示為：

定義6 召回率基于點(diǎn)場(chǎng)景的召回率用于衡量位置點(diǎn)的隱私保護(hù)級(jí)別，滿足如下公式：

其中，CT是基于NDBSCAN算法得到的擾動(dòng)錨點(diǎn)的集合；IST是擾動(dòng)點(diǎn)與原始位置點(diǎn)之間的距離小于初始閾值的點(diǎn)。召回率越大，則認(rèn)為數(shù)據(jù)的可用性越大。

基于軌跡場(chǎng)景的召回率用于衡量對(duì)軌跡數(shù)據(jù)的隱私保護(hù)級(jí)別，滿足如下公式：

其中，IST是被重新識(shí)別的軌跡，CT是基于Final Private Trajectory Release算法得到的發(fā)布數(shù)據(jù)集合。召回率越高，則認(rèn)為數(shù)據(jù)的實(shí)用性越大。

定義7 全局敏感性［4］對(duì)于任意一個(gè)函數(shù)f：D→Rd，函數(shù)f的全局敏感性為：

其中，D和D‘之間最多相差一條記錄；R表示所映射的實(shí)數(shù)空間；d表示函數(shù)f的查詢維度；p表示度量Δf使用的Lp距離，通常用L1來(lái)度量。

2 算法及性能分析

傳統(tǒng)基于差分隱私的軌跡數(shù)據(jù)發(fā)布算法中，基于可變長(zhǎng)度n-gram的SD算法通過(guò)噪聲合成的方法改進(jìn)軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)效率，然而n-gram模型只是簡(jiǎn)單地將所有序列切割成至少I(mǎi)max長(zhǎng)度的序列構(gòu)建樹(shù)，對(duì)長(zhǎng)距離軌跡會(huì)丟失一定的信息。本文的主要目的旨在提出一種基于差分隱私保護(hù)機(jī)制的軌跡數(shù)據(jù)發(fā)布算法以解決上述局限性。

該算法可分為2個(gè)階段，對(duì)此則分述如下。

（1）在第一階段，為了從大量的軌跡位置點(diǎn)中提取具有一定特征的錨點(diǎn)構(gòu)建參考系，本文在DBSCAN算法［14］的基礎(chǔ)上進(jìn)行改進(jìn)和豐富，提出NDBSCAN算法。NDBSCAN算法將全部數(shù)據(jù)點(diǎn)分為核心點(diǎn)（半徑r內(nèi)含有超過(guò)閾值τ的點(diǎn)）和非核心點(diǎn)。通過(guò)鄰域查詢不斷尋找當(dāng)前點(diǎn)的種子點(diǎn)，并用新種子擴(kuò)展同一類(lèi)別的集群，直到全部的種子點(diǎn)用完，得到全部的特征點(diǎn)，再為其添加拉普拉斯噪音。

（2）在第二階段，主要任務(wù)是使用上述擾動(dòng)錨點(diǎn)對(duì)原始軌跡進(jìn)行校準(zhǔn)，得到校準(zhǔn)軌跡。而后基于差分隱私框架構(gòu)造噪音前綴樹(shù)，在樹(shù)的葉子節(jié)點(diǎn)添加拉普拉斯噪音形成最終的發(fā)布版本。然而噪音的大量添加使得發(fā)布的數(shù)據(jù)實(shí)用性降低，為了添加更少的噪音，該算法通過(guò)濾波器來(lái)減少空節(jié)點(diǎn)的數(shù)量。算法的主要思想是：從虛擬根開(kāi)始，逐級(jí)分析每一層高度上的節(jié)點(diǎn)，通過(guò)估計(jì)當(dāng)前節(jié)點(diǎn)的子樹(shù)高度來(lái)分配隱私預(yù)算并計(jì)算濾波器在該節(jié)點(diǎn)的截止值。對(duì)于添加噪音后能達(dá)到截止值的非空節(jié)點(diǎn)，將其添加到前綴樹(shù)中生成最終發(fā)布版本。

這2個(gè)階段都需要添加拉普拉斯噪音。第一階段通過(guò)基于先驗(yàn)知識(shí)的閾值進(jìn)行控制；第二階段提出一種自適應(yīng)算法解決構(gòu)建前綴樹(shù)過(guò)程中的噪音計(jì)數(shù)問(wèn)題。

2.1 算法基本思想

本文算法首先是基于道路分析提取軌跡數(shù)據(jù)中的交叉點(diǎn)，轉(zhuǎn)折點(diǎn)，對(duì)軌跡數(shù)據(jù)離散化得到的位置點(diǎn)進(jìn)行基于密度的聚類(lèi)算法分析（NDBSCAN）提取軌跡關(guān)鍵點(diǎn)，由交叉點(diǎn)、轉(zhuǎn)折點(diǎn)和軌跡關(guān)鍵點(diǎn)組成特征點(diǎn)集，本文稱為錨點(diǎn)集。出于隱私性考慮，本文將對(duì)錨點(diǎn)集中的特征點(diǎn)進(jìn)行隱私保護(hù)操作，為其添加一定量的拉普拉斯噪音。在位置點(diǎn)獲得隱私保證的基礎(chǔ)上，基于擾動(dòng)錨點(diǎn)校準(zhǔn)原始軌跡。通過(guò)對(duì)原始軌跡進(jìn)行校準(zhǔn)，去除冗余位置點(diǎn)，在不影響原始軌跡大致走向的前提下縮短了長(zhǎng)度，得到校準(zhǔn)軌跡?；谛?zhǔn)軌跡構(gòu)建前綴樹(shù)，從而降低了前綴樹(shù)構(gòu)造過(guò)程中的計(jì)算量和算法復(fù)雜度。

然后，基于校準(zhǔn)軌跡構(gòu)造噪音前綴樹(shù)，該樹(shù)從根節(jié)點(diǎn)到每一個(gè)葉子節(jié)點(diǎn)的路徑表示一條軌跡數(shù)據(jù)。本文基于一種自適應(yīng)剪枝方案處理構(gòu)建前綴樹(shù)的過(guò)程中產(chǎn)生的空節(jié)點(diǎn)，以提高效率和效用。對(duì)于空節(jié)點(diǎn)，本文采取的一種解決方案是另外存儲(chǔ)，算法結(jié)束時(shí)再做統(tǒng)一處理，對(duì)于非空節(jié)點(diǎn)，為其添加拉普拉斯噪聲并計(jì)算噪音計(jì)數(shù)，對(duì)于大于閾值的節(jié)點(diǎn)，將其添加到樹(shù)中，否則將其標(biāo)記為葉子節(jié)點(diǎn)。通過(guò)自適應(yīng)剪枝方案減少了前綴樹(shù)構(gòu)建過(guò)程中的計(jì)算量，提升了算法性能。

2.2 算法描述

軌跡數(shù)據(jù)發(fā)布是從軌跡位置點(diǎn)中提取錨點(diǎn)，而后基于該錨點(diǎn)校準(zhǔn)原始軌跡后構(gòu)建噪音前綴樹(shù)生成發(fā)布版本。用于提取錨點(diǎn)的NDBSCAN算法和構(gòu)建噪音前綴樹(shù)的FPTR算法分別詳見(jiàn)如下代碼設(shè)計(jì)。

算法1 NDBSCAN算法

輸入：軌跡tj上全部位置點(diǎn)的集合P；存儲(chǔ)每個(gè)集群的結(jié)果RL；存儲(chǔ)種子點(diǎn)的隊(duì)列SD；鄰域查詢RQ的半徑r；核心點(diǎn)的閾值τ；存儲(chǔ)全部錨點(diǎn)的集合M＝｛｝；M中的一組位置點(diǎn)集Mcj；錨點(diǎn)的計(jì)數(shù)CT；錨點(diǎn)的噪音計(jì)數(shù)CT＇

輸出：擾動(dòng)錨點(diǎn)集

Construct R-Tree index overP

FOR each pointpinP，do

IFP［i］.clustered＝falseTHEN

SD.add（P）；

RL.add（P）；

whileSDis not null do

Points P′＝SD.pop（）；

Points P′＝RQ（P′，r）；

FORi＝0 to｜P′｜do

IFP′［i］.clustered＝falseand collect withP′directly

RL.add（P′［i］）；

SD.add（P′［i］）；

end

end

end

IF｜RL｜≥τTHEN

M.add（RL）；

FOR each pointP″inRLdo

P″.clustered＝true

end

end

RL.clear（）

end

FORj＝1 to｜M｜do

CT′＝｜Mcj｜+lap（σct）；

IF CT′＞γthen

CC′＝NoisyLap（σj）（CCj）

End

分析可知，NDBSCAN算法是從軌跡tj的全部位置點(diǎn)集合的某一點(diǎn)P開(kāi)始，若判斷P為核心點(diǎn)，則將與P同類(lèi)別的點(diǎn)即都?xì)w并作為P的鄰域點(diǎn)，而且將這些點(diǎn)作為種子點(diǎn)進(jìn)行下一輪考察，不斷擴(kuò)展種子點(diǎn)所在的類(lèi)直至找到完整類(lèi)。重復(fù)以上步驟直至尋找到其它類(lèi)，則算法結(jié)束。對(duì)算法獲取的錨點(diǎn)集添加拉普拉斯噪音形成擾動(dòng)錨點(diǎn)集。

算法2 Final Private Trajectory Release算法

輸入：校準(zhǔn)后的軌跡數(shù)據(jù)集CT，全部的隱私預(yù)算ε，初始閾值θ，軌跡的最大長(zhǎng)度xmax

輸出：噪音前綴樹(shù)PT

Initialize a prefix treePTwith a virtual root

FORi＝0；i＜xmax；i++do

FORj＝0；j＜｜nds｜；j++do

IFnds［j］.flagisfalse

tr（nds［j］）.height＝EstimateHeight（）；

ε［i］［j］＝PBD（tr（nds［j］）.height）；

θ［i］［j］＝Threshold（ε［i］［j］）；

nodes［pcn］＝All possible children of nds［j］；

FORk＝0 to｜pcn｜do

Count＝c（pcn［k］）；

IFNoisyCount≥θthen

NoisyCount＝c＇(pcn[k])

NoisyCount≥θthen

Add pcn［k］intoPT；

else

pcn［k］.flag＝true；

end

else

Node［empty］.push（pcn［n］）；

Node［empty＇］＝ThresholdSampling（empty＇）；

end

end

Form＝0 to｜empty＇｜do

NoisyCount＝c＇（empty＇［m］）；

IFNoisyCount≥θthen

Add empty＇［m］intoPT；

elseempty＇［m］.flag＝＆；

empty＇［m］.flag＝＆；

end

end

end

End

分析可知，F(xiàn)inalPrivateTrajectoryRelease（FPT）算法是在文獻(xiàn)［7］中提出的噪音樹(shù)構(gòu)建算法的基礎(chǔ)上加以改進(jìn)的，該算法能夠自適應(yīng)剪枝以減少噪音的添加。該算法的輸入是校準(zhǔn)軌跡數(shù)據(jù)集CT、隱私預(yù)算ε、初始閾值θ和軌跡的最大長(zhǎng)度xmax。 首先，初始化前綴樹(shù)PT并創(chuàng)建虛擬根節(jié)點(diǎn)，構(gòu)建噪音樹(shù)是找到所有序列，直到計(jì)數(shù)大于閾值而長(zhǎng)度小于xmax，迭代生成樹(shù)中每個(gè)層級(jí)的節(jié)點(diǎn)并對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行判斷：如果該節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則估計(jì)該節(jié)點(diǎn)子樹(shù)的高度并基于自適應(yīng)隱私預(yù)算分配算法計(jì)算該節(jié)點(diǎn)應(yīng)被分配的ε值。 此外，找到該節(jié)點(diǎn)的所有可能子節(jié)點(diǎn)，同時(shí)計(jì)算在數(shù)據(jù)集CT中從根節(jié)點(diǎn)到該節(jié)點(diǎn)軌跡前綴的頻率。在此過(guò)程中，為了處理大量空節(jié)點(diǎn)造成的冗余現(xiàn)象，本文提出一種自適應(yīng)剪枝方案處理空節(jié)點(diǎn)和非空節(jié)點(diǎn)的潛在子節(jié)點(diǎn)。對(duì)于計(jì)數(shù)非0的非空節(jié)點(diǎn)，通過(guò)拉普拉斯噪音添加到實(shí)數(shù)中來(lái)計(jì)算噪音計(jì)數(shù)，對(duì)于噪聲計(jì)數(shù)大于閾值的節(jié)點(diǎn)添加到噪音前綴樹(shù)中，否則該節(jié)點(diǎn)被標(biāo)記為葉節(jié)點(diǎn)；對(duì)于計(jì)數(shù)為0的空節(jié)點(diǎn)，則將其專門(mén)存儲(chǔ)起來(lái)，不會(huì)添加到噪音前綴樹(shù)中，這樣在一定程度上就減少了構(gòu)造噪音前綴樹(shù)的計(jì)算量。如果噪音前綴樹(shù)的高度達(dá)到nmax或者沒(méi)有可添加的節(jié)點(diǎn)時(shí)，遍歷過(guò)程即停止，其噪音計(jì)數(shù)無(wú)法超過(guò)閾值，或者節(jié)點(diǎn)所在高度的層級(jí)隱私預(yù)算消耗完。

2.3 算法性能分析

這里有2個(gè)連續(xù)的步驟，分別是：隱私參考系統(tǒng)和隱私軌跡發(fā)布。本文首先證明這2個(gè)連續(xù)步驟生成的發(fā)布結(jié)果分別滿足ε-差分隱私，再通過(guò)差分隱私的組成屬性證明該算法滿足ε-差分隱私。其中，εpr用于隱私參考系統(tǒng)，并且εpg用于隱私軌跡發(fā)布。

對(duì)于第一階段，又分為計(jì)數(shù)擾動(dòng)εct和質(zhì)心擾動(dòng)εcc。 在此，εpr＝εct+εcc， 計(jì)數(shù)靈敏度，即為max(NUMindividual(points))，質(zhì)心靈敏度即為max(distance(pi，pj))／2。 因此， 通過(guò)將函數(shù)的隨機(jī)噪聲添加到每個(gè)聚類(lèi)計(jì)數(shù)，將Laplace函數(shù)的隨機(jī)噪聲添加到每個(gè)聚類(lèi)質(zhì)心使得算法1滿足 (εct+εcc)-差分隱私。

對(duì)于第二階段，令lmax為原始軌跡數(shù)據(jù)集T中的最長(zhǎng)序列，因此，增加或者去除一個(gè)單獨(dú)軌跡(T＇)最多影響lmax條根到葉子節(jié)點(diǎn)的序列，記為SE(lmax)，即Δf＝lmax。 定義噪音性強(qiáng)軌跡的功能函數(shù)M(T)，那么在噪音前綴樹(shù)PT中至少有個(gè)節(jié)點(diǎn)，記為X，分配給nd∈X的隱私預(yù)算是εnd。采用拉普拉斯噪聲機(jī)制，可以表示為：

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

為了驗(yàn)證算法的隱私性和實(shí)用性，本文通過(guò)大量實(shí)驗(yàn)來(lái)評(píng)估FPT算法的性能。本文的實(shí)驗(yàn)分為2部分。第一部分：驗(yàn)證錨點(diǎn)集和發(fā)布軌跡的隱私性；第二部分：驗(yàn)證發(fā)布軌跡數(shù)據(jù)的實(shí)用性。實(shí)驗(yàn)環(huán)境為：Inter（R）Core（TM）i5-2450M CPU＠ 2.50 GHz，8 Gb內(nèi)存，Win7操作系統(tǒng)，編程環(huán)境為 MyEclipse。實(shí)驗(yàn)數(shù)據(jù)集為 Gowalla和 Brightkite上的簽到數(shù)據(jù)［11］，測(cè)試數(shù)據(jù)集由 Thomas Brinkhoff路網(wǎng)移動(dòng)節(jié)點(diǎn)數(shù)據(jù)生成器生成。

3.1 隱私性驗(yàn)證

從清洗過(guò)的數(shù)據(jù)集中分別隨機(jī)選擇8 000個(gè)軌跡，其中位置點(diǎn)的總數(shù)是252 448，最大軌跡長(zhǎng)度是192，平均軌跡長(zhǎng)度為13。 設(shè)置不同的ε＝0.01、0.1、0.5、1.0、1.5， 設(shè) 置 聚 類(lèi) 算 法 的 初 始 閾 值 為 半 徑0.01 km內(nèi)至少包含50個(gè)特征點(diǎn)。每組實(shí)驗(yàn)進(jìn)行10次，并以平均值作為該組實(shí)驗(yàn)的最終結(jié)果。

實(shí)驗(yàn)中，設(shè)置歐氏距離閾值為100 m，隱私預(yù)算ε＝0.01、0.1、0.5、1.0、1.5 時(shí)，對(duì) 2 個(gè)數(shù)據(jù)集分別基于本文算法提取的錨點(diǎn)以及發(fā)布軌跡的召回率對(duì)比如圖1所示。其中，橫坐標(biāo)表示隱私預(yù)算，縱坐標(biāo)表示召回率。

圖1 經(jīng)過(guò)本文算法處理后數(shù)據(jù)的召回率Fig.1 Data recall rate of this algorithm

圖1 表示數(shù)據(jù)集基于本文算法發(fā)布的錨點(diǎn)以及數(shù)據(jù)在給定閾值的前提下所能達(dá)到的召回率。分析圖1可知，隨著ε變大，錨點(diǎn)的召回率和發(fā)布軌跡的召回率都呈現(xiàn)增加的趨勢(shì)。這是由于ε越大，隱私保護(hù)程度越低，添加的拉普拉斯噪音越少，錨點(diǎn)和軌跡的可識(shí)別率越高，因此召回率隨之增加。反之，ε越小，隱私保護(hù)程度越高，可識(shí)別的錨點(diǎn)和軌跡越少，相應(yīng)的召回率越低。從實(shí)驗(yàn)結(jié)果來(lái)看，即使在弱隱私保護(hù)級(jí)別下，攻擊者無(wú)法重新識(shí)別的敏感位置百分比超過(guò)86%，無(wú)法重新識(shí)別的軌跡百分比超過(guò)89%，證明了本文算法的隱私性。

3.2 實(shí)用性驗(yàn)證

為了評(píng)估數(shù)據(jù)的實(shí)用性，本文基于2個(gè)數(shù)據(jù)集針對(duì)隱私保護(hù)后發(fā)布的數(shù)據(jù)進(jìn)行KNN查詢以及頻繁序列模式挖掘，并與文獻(xiàn)［7］中提出的直接構(gòu)建噪音前綴樹(shù)實(shí)現(xiàn)軌跡數(shù)據(jù)隱私保護(hù)的算法進(jìn)行對(duì)比分析。本文采用歐式距離（ED）以及實(shí)序列編輯距離（EDR）進(jìn)行計(jì)算，歐氏距離用于評(píng)估具有相同長(zhǎng)度軌跡相似性，實(shí)序列編輯距離的目的則是匹配每個(gè)可能的位置對(duì)（pi，pj）來(lái)計(jì)算使得t1和t2等效所需的最小編輯數(shù)。其中，pi∈原始軌跡數(shù)據(jù)集，pj∈校驗(yàn)軌跡數(shù)據(jù)集。 當(dāng)pi，pj匹配時(shí)，編輯距離為0，否則為1。從數(shù)據(jù)集中隨機(jī)選擇500個(gè)隨機(jī)軌跡執(zhí)行KNN查詢實(shí)驗(yàn)對(duì)比如圖2（a）、（b）所示。其中，橫坐標(biāo)表示隱私預(yù)算，縱坐標(biāo)表示頻繁模式挖掘的距離。

圖2 不同隱私保護(hù)水平下的相對(duì)誤差Fig.2 Relative error at different levels of privacy protection

從實(shí)驗(yàn)結(jié)果可以看出，一般的隱私保護(hù)機(jī)制在較強(qiáng)的隱私保護(hù)支持下，數(shù)據(jù)的實(shí)用性降低，而本文提出的數(shù)據(jù)發(fā)布算法可以在數(shù)據(jù)隱私性相同的情況下保持相對(duì)較高的數(shù)據(jù)實(shí)用性。

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

在差分隱私保護(hù)下，本文提出了隱私軌跡校準(zhǔn)和發(fā)布系統(tǒng)，解決了基于噪音前綴樹(shù)的軌跡數(shù)據(jù)發(fā)布問(wèn)題，基本上彌補(bǔ)了歷史算法中存在的距離局限性以及序列丟失等問(wèn)題。此方法通過(guò)建立噪音增強(qiáng)的前綴樹(shù)來(lái)實(shí)現(xiàn)帶有隱私保證的嘈雜校準(zhǔn)軌跡發(fā)布解決方案，可擴(kuò)展到大型地理空間領(lǐng)域，能夠有效保護(hù)軌跡數(shù)據(jù)中的個(gè)人隱私信息，提高數(shù)據(jù)的利用率。然而，當(dāng)數(shù)據(jù)集增加到一定限度后隱私預(yù)算必定會(huì)被耗盡，并且隨著數(shù)據(jù)集的增加，所添加的噪音也會(huì)加大，從而影響發(fā)布數(shù)據(jù)的實(shí)用性。因此，該算法對(duì)動(dòng)態(tài)軌跡數(shù)據(jù)發(fā)布的隱私保護(hù)仍不能完全適用。今后的研究方向?qū)⒓性谌缦?個(gè)方面：一是如何在不影響數(shù)據(jù)隱私性和實(shí)用性的前提下進(jìn)一步減小算法的計(jì)算量；二是如何在差分隱私保護(hù)下實(shí)現(xiàn)數(shù)據(jù)的增量更新。