[[375214]]

軌跡隱私是一種特殊的個(gè)人隱私，指用戶的運(yùn)行軌跡本身含有的敏感信息（如用戶去過(guò)的一些敏感區(qū)域等），或者可以通過(guò)運(yùn)行軌跡推導(dǎo)出其他的個(gè)人信息（如用戶的家庭住址、工作地點(diǎn)、健康狀況、生活習(xí)慣等）。因此，軌跡隱私保護(hù)既要保證軌跡本身的敏感信息不泄露，又要防止攻擊者通過(guò)軌跡推導(dǎo)出其他的個(gè)人信息。

01 軌跡隱私的度量

在軌跡數(shù)據(jù)的發(fā)布過(guò)程中，發(fā)布的數(shù)據(jù)為了方便研究者研究利用，在進(jìn)行隱私保護(hù)時(shí)需要具有較高的數(shù)據(jù)可用性。針對(duì)位置隱私保護(hù)，保護(hù)技術(shù)既要保護(hù)用戶的隱私安全，又要保證用戶能夠享受到較高的服務(wù)質(zhì)量。

針對(duì)軌跡隱私的保護(hù)程度，一般可用3個(gè)指標(biāo)來(lái)對(duì)其進(jìn)行度量：軌跡上點(diǎn)與點(diǎn)之間的關(guān)聯(lián)性、軌跡中數(shù)據(jù)點(diǎn)的精確性、軌跡的隱私泄露概率。

軌跡是指某個(gè)用戶在一天內(nèi)的位置和時(shí)間關(guān)聯(lián)排序的一組序列。一條軌跡可以表示為Ti={(xi1,yi1,ti1),(xi2,yi2,t2i),…,(xji,yji,tji),…,(xni,yni,tni)}。其中，Ti表示第i個(gè)用戶的軌跡，(xji,yji,tji)(1≤j≤n)表示此移動(dòng)的用戶在tj時(shí)刻所在的位置為(xji,yji)，tj為采樣時(shí)刻。基站或服務(wù)器將用戶在一天內(nèi)所有的數(shù)據(jù)收集起來(lái)，然后將位置數(shù)據(jù)根據(jù)時(shí)間串聯(lián)起來(lái)就是此用戶的軌跡。軌跡數(shù)據(jù)蘊(yùn)含了豐富的時(shí)空信息，對(duì)軌跡的分析和挖掘可以支持許多移動(dòng)應(yīng)用。例如：研究者通過(guò)分析人們的日常軌跡可以研究人類的行為模式；政府機(jī)構(gòu)可以利用用戶的移動(dòng)GPS軌跡數(shù)據(jù)可以分析基礎(chǔ)交通設(shè)施的建設(shè)情況。由此可知，用戶的軌跡數(shù)據(jù)對(duì)社會(huì)的發(fā)展提供了許多信息，同樣也會(huì)帶來(lái)隱私安全問(wèn)題。

軌跡隱私與位置隱私最大的不同是軌跡包含時(shí)間和位置的關(guān)聯(lián)信息，很容易通過(guò)一個(gè)信息來(lái)推測(cè)出其他的信息。在傳統(tǒng)的軌跡隱私度量方法中，大都用時(shí)間和空間兩者進(jìn)行分析度量，之后加入了軌跡形狀來(lái)對(duì)軌跡進(jìn)行度量，其更能準(zhǔn)確地衡量出兩條軌跡之間的相似性。

在定義軌跡相似性的度量標(biāo)準(zhǔn)時(shí)，需要從兩方面進(jìn)行考慮。如圖1所示，有3條軌跡，每條軌跡都具有5個(gè)數(shù)據(jù)點(diǎn)，每個(gè)數(shù)據(jù)點(diǎn)都是在同一采樣時(shí)間上通過(guò)采樣得到的，假設(shè)每個(gè)采樣時(shí)刻的3個(gè)數(shù)據(jù)點(diǎn)的x軸坐標(biāo)相同，只有y軸坐標(biāo)不同。通過(guò)計(jì)算對(duì)應(yīng)的5個(gè)數(shù)據(jù)點(diǎn)之間的歐氏距離，最后得出軌跡2和軌跡3到軌跡1的距離相等，但是從圖中可以觀察看出，軌跡2與軌跡1的形狀完全相同，而軌跡3與軌跡1不同，所以軌跡2與軌跡1的相似性明顯強(qiáng)于軌跡3與軌跡1的相似性。所以，在進(jìn)行軌跡相似性度量時(shí)，要從兩個(gè)方面著手。

圖1  軌跡相似性對(duì)比

軌跡形狀距離：給定兩條軌跡Ti={(x1i,y1i,t1i),(xi2,y2i,t2i),…,(xni,yni,tni)}和Tj={(x1j,y1j,t1j),(x2j,y2j,t2j),…,(xnj,ynj,tnj)}，則兩條軌跡之間的形狀距離如下所示：

軌跡位置距離：針對(duì)定義6.1中給定的兩條軌跡，它們之間的位置距離如下所示：

基于上述兩種距離形式的定義，將它們進(jìn)行加權(quán)合并，即可得到兩條軌跡的軌跡距離。

軌跡距離：軌跡距離的定義如下所示：

這里，α∈[0,1]為軌跡形狀距離和軌跡位置距離兩者的一個(gè)權(quán)重，一般取值為α=0.5。

02 軌跡隱私保護(hù)場(chǎng)景

目前，關(guān)于軌跡隱私保護(hù)的研究工作主要解決下述兩種應(yīng)用場(chǎng)景中的隱私問(wèn)題。

1. 數(shù)據(jù)發(fā)布中的軌跡隱私保護(hù)

軌跡數(shù)據(jù)本身蘊(yùn)含了豐富的時(shí)空信息，對(duì)軌跡數(shù)據(jù)的分析和挖掘結(jié)果可以支持多種移動(dòng)應(yīng)用，因此，許多政府及科研機(jī)構(gòu)都加大了對(duì)軌跡數(shù)據(jù)的研究力度。例如：美國(guó)政府利用移動(dòng)用戶的GPS軌跡數(shù)據(jù)分析基礎(chǔ)交通設(shè)施的建設(shè)情況，進(jìn)而為是否更新和優(yōu)化交通設(shè)施提供依據(jù)；社會(huì)學(xué)的研究者們通過(guò)分析人們的日常軌跡來(lái)研究人類的行為模式；某些公司通過(guò)分析雇員的上下班軌跡來(lái)提高雇員的工作效率等。然而，假如惡意攻擊者在未經(jīng)授權(quán)的情況下，計(jì)算推理獲取與軌跡相關(guān)的其他個(gè)人信息，則用戶的個(gè)人隱私會(huì)通過(guò)其軌跡完全暴露。數(shù)據(jù)發(fā)布中的軌跡隱私泄露情況大致可分為以下兩類。

① 軌跡上敏感或頻繁訪問(wèn)位置的泄露導(dǎo)致移動(dòng)對(duì)象的隱私泄露。軌跡上的敏感或頻繁訪問(wèn)的位置很可能暴露其個(gè)人興趣愛好、健康狀況、政治傾向等個(gè)人隱私，如某人在某個(gè)時(shí)間段內(nèi)頻繁訪問(wèn)醫(yī)院或診所，攻擊者可以由此推斷出這個(gè)人近期患上了某種疾病。

② 移動(dòng)對(duì)象的軌跡與外部知識(shí)的關(guān)聯(lián)導(dǎo)致隱私泄露。例如，某人每天早上在固定的時(shí)間段從地點(diǎn)A出發(fā)到地點(diǎn)B，每天下午在固定的時(shí)間段從地點(diǎn)B出發(fā)到地點(diǎn)A，通過(guò)挖掘分析，攻擊者很容易做出判斷：A是某人的家庭住址，B是其工作單位。通過(guò)查找A所在區(qū)域和B所在區(qū)域的郵編、電話簿等公開內(nèi)容，很容易確定某人的身份、姓名、工作地點(diǎn)、家庭住址等信息。因此，某人的個(gè)人隱私通過(guò)其運(yùn)行軌跡被完全泄露。

在軌跡數(shù)據(jù)發(fā)布中，最簡(jiǎn)單的隱私保護(hù)方法是刪除每條軌跡的準(zhǔn)標(biāo)志屬性，即QI屬性。然而，單純地將QI屬性移除并不能保護(hù)移動(dòng)對(duì)象的軌跡隱私，攻擊者通過(guò)將背景知識(shí)（如受攻擊者的博客、談話記錄或其他外部信息等）與特定用戶相匹配，亦可推導(dǎo)出個(gè)體的隱私信息。

例如，在刪除了QI屬性的數(shù)據(jù)中，攻擊者發(fā)現(xiàn)某個(gè)移動(dòng)對(duì)象在某個(gè)時(shí)刻ti訪問(wèn)了地點(diǎn)L1和L2，在攻擊者已知的背景知識(shí)中，小王曾在時(shí)刻ti左右分別訪問(wèn)過(guò)這兩個(gè)位置，如果小王是在ti時(shí)刻唯一分別訪問(wèn)過(guò)L1和L2的移動(dòng)對(duì)象，那么攻擊者就可以斷定該軌跡屬于小王，繼而可從軌跡中發(fā)現(xiàn)小王訪問(wèn)過(guò)的其他位置?？梢?，簡(jiǎn)單地刪除移動(dòng)對(duì)象的QI屬性并不能起到隱私保護(hù)的目的。

2. 位置服務(wù)中的軌跡隱私保護(hù)

用戶在獲取LBS服務(wù)時(shí)，需要提供自己的位置信息，為了保護(hù)移動(dòng)對(duì)象的位置隱私，出現(xiàn)了位置隱私保護(hù)技術(shù)。然而，保護(hù)了移動(dòng)對(duì)象的位置隱私并不代表能保護(hù)移動(dòng)對(duì)象的實(shí)時(shí)運(yùn)行軌跡隱私，攻擊者極有可能通過(guò)其他手段獲得移動(dòng)對(duì)象的實(shí)時(shí)運(yùn)行軌跡。例如，利用位置k-匿名模型對(duì)發(fā)出連續(xù)查詢的用戶進(jìn)行位置隱私保護(hù)時(shí)，移動(dòng)對(duì)象的匿名框的位置和大小會(huì)產(chǎn)生連續(xù)更新。如果將移動(dòng)對(duì)象發(fā)出LBS請(qǐng)求時(shí)各個(gè)時(shí)刻的匿名框連接起來(lái)，就可以得到移動(dòng)對(duì)象大致的運(yùn)行路線。這是由于移動(dòng)對(duì)象在查詢過(guò)程中生成的匿名框包含了不同移動(dòng)對(duì)象的信息，單純地延長(zhǎng)匿名框的有效時(shí)間會(huì)導(dǎo)致服務(wù)質(zhì)量下降。雖然，目前已有針對(duì)連續(xù)查詢的位置隱私保護(hù)技術(shù)，但是，其查詢有效期處于秒級(jí)，無(wú)法滿足軌跡隱私保護(hù)的需求。因此，在LBS中也需要軌跡隱私保護(hù)技術(shù)。

在上述兩種場(chǎng)景中，軌跡隱私保護(hù)需要解決以下幾個(gè)關(guān)鍵問(wèn)題：

① 保護(hù)軌跡上的敏感／頻繁訪問(wèn)位置信息不泄露；

② 保護(hù)個(gè)體和軌跡之間的關(guān)聯(lián)關(guān)系不泄露，即保證個(gè)體無(wú)法與某條軌跡相匹配；

③ 防止由移動(dòng)對(duì)象的相關(guān)參數(shù)限制（如最大速度、路網(wǎng)等）而泄露移動(dòng)對(duì)象軌跡隱私的問(wèn)題發(fā)生。

03 軌跡隱私保護(hù)技術(shù)分類

軌跡隱私保護(hù)技術(shù)大致可以分為3類。

（1）基于假數(shù)據(jù)的軌跡隱私保護(hù)技術(shù)

該技術(shù)通過(guò)添加假軌跡對(duì)原始數(shù)據(jù)進(jìn)行干擾，同時(shí)又要保證被干擾的軌跡數(shù)據(jù)的某些統(tǒng)計(jì)屬性不發(fā)生嚴(yán)重失真?；诩贁?shù)據(jù)的軌跡隱私保護(hù)技術(shù)主要是在原始數(shù)據(jù)的基礎(chǔ)上添加假數(shù)據(jù)，進(jìn)而對(duì)原始軌跡數(shù)據(jù)進(jìn)行干擾，同時(shí)又不會(huì)使原始軌跡數(shù)據(jù)失真。例如，在表1中有3個(gè)移動(dòng)對(duì)象O1、O2、O3，表中數(shù)據(jù)分別對(duì)應(yīng)它們?cè)跁r(shí)刻t1、t2、t3中的數(shù)據(jù)點(diǎn)，每個(gè)對(duì)象可根據(jù)時(shí)間關(guān)聯(lián)形成一條軌跡。

表1  原始數(shù)據(jù)

利用假數(shù)據(jù)法對(duì)表1中的數(shù)據(jù)進(jìn)行干擾之后，形成了6條軌跡，如表2所示，在此6條軌跡中，I1、I2、I3是O1、O2、O3的假名。由此可將每條真實(shí)軌跡被泄露的風(fēng)險(xiǎn)降至0.5。

表2  用假數(shù)據(jù)法干擾后的數(shù)據(jù)

針對(duì)假數(shù)據(jù)方法，假軌跡的數(shù)量越多，被泄露的風(fēng)險(xiǎn)就越低，但是這會(huì)對(duì)原始數(shù)據(jù)產(chǎn)生較大的影響。假軌跡的產(chǎn)生在空間關(guān)系中增加了復(fù)雜性，會(huì)產(chǎn)生許多交叉點(diǎn)，因易于混淆而可降低風(fēng)險(xiǎn)。在運(yùn)行模式中，假軌跡的運(yùn)行模式與原始軌跡相似，也會(huì)對(duì)攻擊者的攻擊造成一定的影響。此類方法較簡(jiǎn)單且計(jì)算量小，但易造成存儲(chǔ)量的擴(kuò)大，使數(shù)據(jù)可用性降低。

（2）基于泛化法的軌跡隱私保護(hù)技術(shù)

該技術(shù)是指將軌跡上所有的采樣點(diǎn)都泛化為對(duì)應(yīng)的匿名區(qū)域，以達(dá)到隱私保護(hù)的目的?；诜夯ǖ能壽E隱私保護(hù)技術(shù)針對(duì)所有軌跡中的每一個(gè)點(diǎn)進(jìn)行泛化，并將它們泛化成數(shù)據(jù)點(diǎn)對(duì)應(yīng)的匿名區(qū)，從而達(dá)到隱私保護(hù)的目的。在泛化的保護(hù)技術(shù)中，最常用的是軌跡k-匿名保護(hù)技術(shù)，其主要的保護(hù)技術(shù)是將其需要保護(hù)的核心屬性進(jìn)行泛化，使其無(wú)法與其他k-1條記錄區(qū)分開。針對(duì)表1中的軌跡數(shù)據(jù)，將其中的3條軌跡進(jìn)行軌跡泛化匿名，即針對(duì)每個(gè)采樣時(shí)刻的點(diǎn)，將數(shù)據(jù)點(diǎn)泛化為匿名區(qū)，如表3所示。

表3  軌跡6-匿名

在進(jìn)行匿名時(shí)依然通過(guò)假名進(jìn)行發(fā)布，同時(shí)也須對(duì)3個(gè)匿名時(shí)刻中的數(shù)據(jù)點(diǎn)進(jìn)行匿名泛化。此方法可以保證數(shù)據(jù)均為真實(shí)數(shù)據(jù)，但是由于計(jì)算開銷比較大，因此需要考慮性能的問(wèn)題。

（3）基于抑制法的軌跡隱私保護(hù)技術(shù)

該技術(shù)根據(jù)具體情況有條件地發(fā)布軌跡數(shù)據(jù)，不發(fā)布軌跡上的某些敏感位置或頻繁訪問(wèn)的位置以實(shí)現(xiàn)隱私保護(hù)。表4所示為表2進(jìn)行抑制發(fā)布后的數(shù)據(jù)。

表4  抑制法進(jìn)行軌跡匿名

抑制法較其他方法來(lái)說(shuō)簡(jiǎn)單有效，在攻擊者具有一定背景知識(shí)的前提下亦可進(jìn)行軌跡保護(hù)，效率也比較高。但在不能確切地了解攻擊者具有的背景知識(shí)時(shí)，這種方法就不再適用了。另一方面，此方法雖然限制了敏感數(shù)據(jù)的發(fā)布且實(shí)現(xiàn)過(guò)程簡(jiǎn)單，但是信息丟失量過(guò)大。

總之，基于假數(shù)據(jù)的軌跡隱私保護(hù)技術(shù)簡(jiǎn)單、計(jì)算量小，但易造成假數(shù)據(jù)的存儲(chǔ)量大及數(shù)據(jù)可用性降低等問(wèn)題；基于泛化法的軌跡隱私保護(hù)技術(shù)可以保證數(shù)據(jù)的真實(shí)性，但計(jì)算開銷較大；基于抑制法的軌跡隱私保護(hù)技術(shù)可限制發(fā)布某些敏感數(shù)據(jù)，實(shí)現(xiàn)也簡(jiǎn)單，但信息丟失量較大。目前，基于泛化法的軌跡k-匿名技術(shù)在隱私保護(hù)度和數(shù)據(jù)可用性上取得了較好的平衡，是目前軌跡隱私保護(hù)使用的主流方法。

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

原始的軌跡數(shù)據(jù)與用戶的各類隱私信息緊密相關(guān)，如果不對(duì)收集到的軌跡數(shù)據(jù)做任何處理就發(fā)布，惡意攻擊者就可以通過(guò)對(duì)軌跡數(shù)據(jù)進(jìn)行挖掘分析，獲得用戶的家庭住址、興趣愛好、行為模式等敏感信息。因此，離線軌跡數(shù)據(jù)發(fā)布必須遵循“數(shù)據(jù)采集、隱私保護(hù)處理、軌跡發(fā)布”的原則。

軌跡發(fā)布后，不論是商業(yè)機(jī)構(gòu)還是科研單位，都希望能夠從保護(hù)后的軌跡中分析出可用的信息。因此，軌跡隱私保護(hù)處理的目標(biāo)是：既要能防止惡意攻擊者從處理后的軌跡中推測(cè)出用戶的敏感信息，也要確保處理后的軌跡仍然具有較高的完整性和數(shù)據(jù)可用性。

目前，離線軌跡發(fā)布中的隱私保護(hù)方法，如軌跡聚類、假軌跡等，都僅把軌跡數(shù)據(jù)看作歐式空間中具有時(shí)間屬性的位置點(diǎn)序列，只考慮到了軌跡的時(shí)間和空間屬性，卻忽視了軌跡上各個(gè)采樣點(diǎn)在實(shí)際環(huán)境中對(duì)應(yīng)的位置信息，即軌跡的語(yǔ)義屬性。

通常，用戶軌跡上的位置點(diǎn)可以分為移動(dòng)點(diǎn)和停留點(diǎn)。移動(dòng)點(diǎn)只能分析出用戶途經(jīng)了哪些道路，而停留點(diǎn)卻能反映出用戶某個(gè)時(shí)間段的重要位置特征。通過(guò)對(duì)停留點(diǎn)進(jìn)行分析可以知道用戶頻繁訪問(wèn)的地點(diǎn)，進(jìn)而推測(cè)出用戶的工作地址、興趣愛好甚至是宗教信仰、身體狀況等私密信息。因此相比移動(dòng)點(diǎn)，停留點(diǎn)會(huì)暴露用戶更多的敏感信息。保護(hù)停留點(diǎn)不僅能夠確保用戶的隱私，還能減少對(duì)原始軌跡的破壞，在隱私保護(hù)和數(shù)據(jù)可用性之間取得了較好的平衡。

實(shí)際生活中，不同用戶對(duì)相同語(yǔ)義位置的敏感程度可能并不相同，如患者和醫(yī)生對(duì)醫(yī)院的敏感性就不一樣，患者可能并不想暴露自己的身體健康狀況，但醫(yī)生一般不介意自己的工作地點(diǎn)被泄露，因此，對(duì)軌跡進(jìn)行保護(hù)時(shí)不能忽略用戶的個(gè)性化隱私需求。假如對(duì)所有用戶采用相同的處理標(biāo)準(zhǔn)，就可能會(huì)導(dǎo)致部分用戶的軌跡保護(hù)程度不夠而造成隱私泄露，部分用戶的軌跡保護(hù)過(guò)度而造成數(shù)據(jù)損失。

忽略軌跡的語(yǔ)義屬性會(huì)導(dǎo)致部分現(xiàn)有方案容易遭受語(yǔ)義攻擊。相比自己路過(guò)的位置，用戶更關(guān)心自己曾經(jīng)頻繁訪問(wèn)、長(zhǎng)時(shí)間逗留的地點(diǎn)是否會(huì)泄露隱私。因此，為了維持軌跡的最大完整性，無(wú)須對(duì)軌跡上的所有采樣點(diǎn)進(jìn)行保護(hù)處理。

圖2提出的方案旨在維持軌跡安全性與數(shù)據(jù)可用性之間良好的平衡，用停留點(diǎn)周圍不同語(yǔ)義的興趣點(diǎn)取代用戶敏感的停留點(diǎn)，同時(shí)重置少量采樣點(diǎn)以隱藏用戶的敏感信息。該方案采取了個(gè)性化隱私保護(hù)，用戶可以自定義自身的敏感語(yǔ)義位置集和隱私保護(hù)程度，以在保證軌跡隱私安全的同時(shí)確保軌跡不被過(guò)度處理。

圖2  基于語(yǔ)義的軌跡隱私保護(hù)方案示意

1. 基于語(yǔ)義的軌跡隱私保護(hù)方案

該方案首先根據(jù)原始軌跡數(shù)據(jù)，分析用戶的移動(dòng)特征，針對(duì)時(shí)間、經(jīng)度和緯度3個(gè)屬性進(jìn)行多維聚類，提取出用戶一天內(nèi)的停留點(diǎn)集合，利用地圖反解析獲取停留點(diǎn)對(duì)應(yīng)的實(shí)際位置并標(biāo)記其語(yǔ)義；其次，根據(jù)用戶自定義的敏感語(yǔ)義位置集，獲取用戶的敏感停留點(diǎn)集合（即圖2中的銀行和酒店）；然后，結(jié)合用戶的移動(dòng)方向，為每個(gè)敏感停留點(diǎn)合理地規(guī)劃一個(gè)候選區(qū)，分析候選區(qū)內(nèi)興趣點(diǎn)的語(yǔ)義和距離特性，查找到滿足用戶隱私需求的不同語(yǔ)義的興趣點(diǎn)，將包含這些興趣點(diǎn)的最小矩形作為敏感區(qū)，并在敏感區(qū)內(nèi)隨機(jī)選取一個(gè)替代停留點(diǎn)（即圖2中的KFC和理發(fā)店）；最后，為了防止替換停留點(diǎn)導(dǎo)致軌跡上位置點(diǎn)發(fā)生突變，以減少軌跡變動(dòng)，僅對(duì)敏感區(qū)內(nèi)的局部采樣位置點(diǎn)進(jìn)行重新選擇，并確保敏感區(qū)內(nèi)的采樣位置點(diǎn)數(shù)量與原始軌跡的一致，進(jìn)而形成最終可發(fā)布的軌跡數(shù)據(jù)。

2. 語(yǔ)義停留點(diǎn)的提取

根據(jù)用戶軌跡進(jìn)行語(yǔ)義停留點(diǎn)提取是本方案的首要工作。

一個(gè)用戶在日常生活中會(huì)產(chǎn)生大量的停留點(diǎn)：對(duì)于大部分用戶來(lái)說(shuō)，在夜間12點(diǎn)到早晨6點(diǎn)都在自己家中，此時(shí)用戶的家庭位置就成為了他的一個(gè)停留點(diǎn)；用戶的日常工作地點(diǎn)也會(huì)成為他的一個(gè)停留點(diǎn)；在銀行辦理業(yè)務(wù)的用戶，銀行也會(huì)成為他的一個(gè)停留點(diǎn)。

對(duì)于具有地圖背景知識(shí)的惡意攻擊者，通過(guò)提取用戶軌跡中的停留點(diǎn)并將其映射到語(yǔ)義地圖上，可以獲取用戶大量的個(gè)人隱私。

用戶軌跡上的所有采樣位置點(diǎn)都具有相對(duì)應(yīng)的語(yǔ)義屬性。相比移動(dòng)中的位置點(diǎn)，惡意攻擊者對(duì)用戶頻繁訪問(wèn)和長(zhǎng)時(shí)間停留的位置點(diǎn)更感興趣，這是因?yàn)樗麄兡軓闹型诰蚍治龀龈嗟挠脩綦[私信息。因此，對(duì)停留點(diǎn)進(jìn)行隱私保護(hù)至關(guān)重要。

圖3所示為某個(gè)用戶在一段時(shí)間內(nèi)的軌跡數(shù)據(jù)Traj={P1,P2,…,P9}。通過(guò)分析可知，軌跡中的5個(gè)連續(xù)采樣位置點(diǎn){P3,P4,P5,P6,P7}均處于一定的范圍內(nèi)，由此推斷該用戶曾經(jīng)在這個(gè)地點(diǎn)（圖中虛線圈）停留過(guò)。具有地圖背景知識(shí)的惡意攻擊者此時(shí)就可以通過(guò)將停留點(diǎn)映射到真實(shí)地圖中，得到該用戶停留的地點(diǎn)，并由此獲得用戶的某些隱私信息。

圖3  個(gè)人停留點(diǎn)示意圖

從上面的例子不難看出，通過(guò)挖掘分析用戶停留點(diǎn)，具有背景知識(shí)的攻擊者就可以輕易獲得用戶大量隱私信息。而對(duì)敏感停留點(diǎn)進(jìn)行保護(hù)，無(wú)須處理軌跡上所有的采樣位置點(diǎn)，這不僅能隱藏軌跡上用戶的敏感信息，還能減少對(duì)原始軌跡的破壞。

該方法首先讀取某個(gè)區(qū)域在一段時(shí)間內(nèi)全體用戶的原始軌跡數(shù)據(jù)，如圖4所示，Lij表示用戶Mi(1≤i≤m)在tj(1≤j≤n)時(shí)刻的位置，依次對(duì)每個(gè)用戶的軌跡進(jìn)行多維聚類，包括時(shí)間、經(jīng)度和緯度聚類，以提取用戶個(gè)人停留點(diǎn)集合。聚類時(shí)需要3個(gè)閾值：時(shí)間閾值σt、距離閾值σd和位置點(diǎn)數(shù)閾值σn。

圖4  用戶原始軌跡數(shù)據(jù)

然后，通過(guò)遍歷一個(gè)用戶軌跡上的采樣位置點(diǎn)，可以找到所有停留核心點(diǎn)。停留核心點(diǎn)是用戶Mi在tj時(shí)刻的位置點(diǎn)Lij，遍歷該用戶軌跡上的所有位置點(diǎn)Lik(1≤k≤n)并使它們與其進(jìn)行比較，找到所有滿足|Lij-Lik|≤σd且|tj-tk|≤σt的點(diǎn)。如果Lij處滿足以上條件的點(diǎn)的數(shù)量不少于σn，則Lij為停留核心點(diǎn)。

最后，將時(shí)空上鄰近的停留核心點(diǎn)劃分到一個(gè)集合，最終得到多個(gè)停留核心點(diǎn)的集合，這個(gè)集合稱為語(yǔ)義停留點(diǎn)。

由此可見，通過(guò)多維聚類的方法對(duì)個(gè)體用戶的多維空間數(shù)據(jù)進(jìn)行分析，可以得到用戶的移動(dòng)特征；根據(jù)用戶的移動(dòng)特征，可以提取個(gè)人停留點(diǎn)集合；將停留點(diǎn)一一映射到地圖上，通過(guò)標(biāo)記其語(yǔ)義，并根據(jù)用戶自定義的敏感語(yǔ)義位置集，即可獲得個(gè)人敏感停留點(diǎn)集合（即語(yǔ)義停留點(diǎn)集合）。

3. 語(yǔ)義停留點(diǎn)的合并

采樣的用戶軌跡上可能由于某種原因存在采樣異常點(diǎn)，如一個(gè)采樣位置點(diǎn)與其前后相鄰時(shí)刻的采樣位置點(diǎn)之間的距離過(guò)大，如圖5所示。P5與P4和P6之間的距離差過(guò)大，不符合實(shí)際，即該采樣位置點(diǎn)和它相鄰的位置點(diǎn)在采樣時(shí)間內(nèi)是不可到達(dá)的。異常點(diǎn)的存在會(huì)影響個(gè)人停留點(diǎn)的提取及其語(yǔ)義標(biāo)記的精度，因此，在將相鄰的停留核心點(diǎn)聚集成停留點(diǎn)之前需要對(duì)軌跡數(shù)據(jù)進(jìn)行掃描以檢測(cè)異常點(diǎn)。正常用戶行走的速度大致為3 km/h，用戶在某個(gè)地方停留時(shí)一般會(huì)處于靜止或者慢速移動(dòng)的狀態(tài)，速度不應(yīng)該大于正常移動(dòng)速度，結(jié)合采樣時(shí)間可以計(jì)算出一個(gè)距離δ，如果tj時(shí)刻的采樣位置Lij與其前后相鄰時(shí)刻采樣位置點(diǎn)之間的距離差|Lij-Li(j-1)|和|Lij-Li(j+1)|均大于δ，則認(rèn)為L(zhǎng)ij是采樣異常點(diǎn)，在合并相鄰?fù)Ａ艉诵狞c(diǎn)時(shí)應(yīng)舍棄該異常點(diǎn)。完成軌跡數(shù)據(jù)檢測(cè)和異常點(diǎn)舍棄之后，便可以進(jìn)行停留核心點(diǎn)的合并。

圖5  采樣異常點(diǎn)

通過(guò)上述方法，可以提取到每個(gè)用戶在一段時(shí)間內(nèi)的停留點(diǎn)集合SP={SP1,SP2,…,SPn}，其中SPi(1≤i≤n)是包含多個(gè)停留核心點(diǎn)的停留點(diǎn)，每個(gè)停留點(diǎn)內(nèi)包含的停留核心點(diǎn)可以表示為SPi={P1,P2,…,Pm}。后續(xù)需要對(duì)停留點(diǎn)進(jìn)行替換和采樣點(diǎn)的重置，這里將能夠覆蓋SPi內(nèi)所有停留核心點(diǎn)的最小覆蓋圓的圓心作為停留點(diǎn)的代表坐標(biāo)，如圖5中的停留點(diǎn)，同時(shí)須求出最小覆蓋圓半徑以備后續(xù)重置采樣點(diǎn)。

針對(duì)每個(gè)停留點(diǎn)SPi={P1,P2,…,Pm}，求其最小覆蓋圓，基本思想為：首先在SPi內(nèi)任選3個(gè)停留核心點(diǎn)組成三角形，求出該三角形的最小覆蓋圓圓心與半徑；然后依次遍歷剩余的停留核心點(diǎn)，判斷該點(diǎn)是否在已得到的圓內(nèi)，如果在圓內(nèi)，則說(shuō)明該圓依舊是最小覆蓋圓，如果不在圓內(nèi)，則隨機(jī)在上述3個(gè)點(diǎn)中選擇兩個(gè)點(diǎn)與該點(diǎn)形成新的三角形，并重新計(jì)算新的最小覆蓋圓的圓心與半徑。重復(fù)以上過(guò)程，直到求出能覆蓋所有停留核心點(diǎn)的最小覆蓋圓的圓心與半徑。

通過(guò)上述方法可以獲得每個(gè)停留點(diǎn)的坐標(biāo)信息及覆蓋范圍。接著調(diào)用百度地圖Web服務(wù)API，利用逆地址編碼服務(wù)，獲取停留點(diǎn)坐標(biāo)所在的位置并標(biāo)記其語(yǔ)義屬性。

4. 敏感停留點(diǎn)的替換

在完成用戶原始軌跡上所有敏感停留點(diǎn)的提取后，接下來(lái)須根據(jù)用戶個(gè)性化的隱私保護(hù)程度要求，在合理的空間范圍內(nèi)將敏感停留點(diǎn)替換成不同語(yǔ)義的興趣點(diǎn)。其中，選擇合適的替代停留點(diǎn)是關(guān)鍵，為了保證處理后的軌跡的安全性和完整性，替代停留點(diǎn)的選取不能完全隨機(jī)，需要充分考慮用戶的移動(dòng)方向，興趣點(diǎn)的語(yǔ)義、距離等特性。替代停留點(diǎn)的選擇過(guò)程分為兩部分：首先為每個(gè)敏感停留點(diǎn)構(gòu)建一個(gè)合適的候選區(qū)，然后在候選區(qū)內(nèi)選擇一個(gè)合適的興趣點(diǎn)并將其作為替代停留點(diǎn)。

（1）候選區(qū)的構(gòu)建

為了防止替代停留點(diǎn)偏離相應(yīng)的敏感停留點(diǎn)太遠(yuǎn)，影響受保護(hù)后軌跡數(shù)據(jù)的可用性，須根據(jù)敏感停留點(diǎn)自身構(gòu)建候選區(qū)，候選區(qū)的范圍由該敏感停留點(diǎn)以及在軌跡上與其時(shí)空相鄰的前后兩個(gè)停留點(diǎn)之間的距離共同決定。

如圖6所示，用戶軌跡上分別有敏感停留點(diǎn)SP2和SP3。若在候選區(qū)的重疊區(qū)域內(nèi)選擇了各自的替代停留點(diǎn)SP′2和SP′3，則通過(guò)比較發(fā)現(xiàn)保護(hù)后的軌跡與原始軌跡在形狀、方向上都出現(xiàn)了較大的偏差，嚴(yán)重降低了兩條軌跡之間的相似性。由于保護(hù)后的軌跡與原始軌跡之間的相似性是衡量軌跡數(shù)據(jù)可用性的重要指標(biāo)，因此，為了防止敏感停留點(diǎn)替換后會(huì)破壞軌跡的可用性，需要確保相鄰敏感停留點(diǎn)的候選區(qū)不能存在重疊區(qū)域。若現(xiàn)有候選區(qū)范圍內(nèi)的興趣點(diǎn)無(wú)法滿足用戶隱私需求，則為了搜索更多的興趣點(diǎn)，應(yīng)擴(kuò)大候選區(qū)。如果候選區(qū)的擴(kuò)張導(dǎo)致部分候選區(qū)出現(xiàn)重疊，則應(yīng)避免在候選區(qū)的重疊區(qū)域選擇替代停留點(diǎn)。

圖6  候選區(qū)重疊導(dǎo)致軌跡相似度降低

方案中每個(gè)敏感停留點(diǎn)的候選區(qū)均是以其自身為圓心、其到相鄰?fù)Ａ酎c(diǎn)的距離中的較小值為直徑的圓域。對(duì)于軌跡上的第一個(gè)停留點(diǎn)，若它為敏感停留點(diǎn)，則由于它沒(méi)有上一個(gè)相鄰?fù)Ａ酎c(diǎn)，因此，它的候選區(qū)直徑為它與下一個(gè)停留點(diǎn)間的距離；同樣，若軌跡上的最后一個(gè)停留點(diǎn)為敏感停留點(diǎn)，則由于它不存在下一個(gè)相鄰?fù)Ａ酎c(diǎn)，因此，它的候選區(qū)直徑為它與上一個(gè)停留點(diǎn)間的距離。

如圖7所示，對(duì)某用戶進(jìn)行移動(dòng)特征分析，從其軌跡上提取出了5個(gè)停留點(diǎn){SP1,SP2,SP3,SP4,SP5}。若其中{SP1,SP2,SP3}為敏感停留點(diǎn)集合，則虛線圓域分別為它們的候選區(qū)。其中SP1和SP5由于是邊界點(diǎn)，僅有一個(gè)相鄰?fù)Ａ酎c(diǎn)，因此，它們的候選區(qū)半徑分別為SP1到SP2、SP4到SP5距離的一半；而SP3存在前后相鄰?fù)Ａ酎c(diǎn)SP2和SP4，因此它的候選區(qū)半徑為SP3到SP4距離的一半（因?yàn)镾P3到SP4的距離小于SP2到SP3的距離）。如此構(gòu)建的候選區(qū)不會(huì)導(dǎo)致替代位置點(diǎn)太偏離停留點(diǎn)本身，同時(shí)也能避免出現(xiàn)候選區(qū)重疊導(dǎo)致軌跡相似度降低的情況。

圖7  敏感停留點(diǎn)候選區(qū)

（2）替代停留點(diǎn)的選擇

隱私保護(hù)程度l表示敏感區(qū)中與敏感停留點(diǎn)距離最近但語(yǔ)義不同的其他興趣點(diǎn)的個(gè)數(shù)至少為l個(gè)。隱私保護(hù)程度體現(xiàn)了敏感區(qū)內(nèi)興趣點(diǎn)的多樣性。l值越大表示用戶隱私需求越高。

為每個(gè)敏感停留點(diǎn)構(gòu)造好合理的候選區(qū)之后，下一項(xiàng)工作是結(jié)合用戶自定義的隱私需求，在候選區(qū)內(nèi)為每個(gè)敏感停留點(diǎn)選取合適的興趣點(diǎn)并將它們作為替代停留點(diǎn)。如果選取與敏感停留點(diǎn)語(yǔ)義相同或者相似的興趣點(diǎn)并將它們作為替代停留點(diǎn)，則惡意攻擊者還是能夠從替換后的停留點(diǎn)的語(yǔ)義中推測(cè)出用戶的敏感信息；而且在實(shí)際環(huán)境中，某些具有相同語(yǔ)義的興趣點(diǎn)一般距離較遠(yuǎn)，這可能會(huì)導(dǎo)致選擇的替代停留點(diǎn)偏離敏感停留點(diǎn)較遠(yuǎn)，要重置的采樣位置點(diǎn)數(shù)量較多，軌跡的完整性較低。

在本方案中，敏感停留點(diǎn)會(huì)被替換成語(yǔ)義不同的興趣點(diǎn)。首先，以敏感停留點(diǎn)自身為中心，搜索替代停留點(diǎn)，并逐漸擴(kuò)大搜索半徑，直至找到不少于l個(gè)且語(yǔ)義與敏感停留點(diǎn)不同的興趣點(diǎn)；然后，將搜索到的興趣點(diǎn)按照離敏感停留點(diǎn)的距離由近至遠(yuǎn)排序，取前l(fā)個(gè)作為替代停留點(diǎn)的候選集，并把包含敏感停留點(diǎn)和這l個(gè)興趣點(diǎn)的最小矩形作為敏感區(qū)SA；最后，在敏感區(qū)內(nèi)隨機(jī)選擇一個(gè)興趣點(diǎn)并將其作為替代停留點(diǎn)。

在查找替代停留點(diǎn)集時(shí)，遍歷每一個(gè)新搜索到的興趣點(diǎn)，如果其語(yǔ)義與敏感停留點(diǎn)不同，則將其加入候選集，反之，則忽略它，最終在形成的敏感區(qū)內(nèi)隨機(jī)選擇一個(gè)興趣點(diǎn)并將其作為替代停留點(diǎn)。敏感區(qū)內(nèi)包含了位置和語(yǔ)義多樣性的興趣點(diǎn)，這加大了攻擊者推測(cè)出真實(shí)敏感停留點(diǎn)的難度，同時(shí)興趣點(diǎn)選擇的隨機(jī)性也提高了真實(shí)敏感停留點(diǎn)的安全性。將最小包圍矩形作為敏感區(qū)，可減少之后須重置的采樣點(diǎn)數(shù)量，為提高軌跡的完整性奠定基礎(chǔ)。

（3）局部采樣點(diǎn)的重置

為敏感停留點(diǎn)SPi選取合適的替代位置后，需要為替代停留點(diǎn)SPif選擇其包含的停留核心點(diǎn)。同時(shí)停留點(diǎn)替換后可能會(huì)造成部分移動(dòng)采樣點(diǎn)在采樣間隔內(nèi)不可到達(dá)替代停留點(diǎn)，從而導(dǎo)致位置突變，使攻擊者易推斷出該軌跡段被替換過(guò)，因此，為了提高發(fā)布后軌跡的安全性，還需要重新選擇軌跡上的部分移動(dòng)點(diǎn)。為了最大程度保持軌跡形狀的一致性，盡量少修改原始軌跡，局部采樣點(diǎn)重置僅在敏感區(qū)內(nèi)進(jìn)行，且重置時(shí)要充分考慮原始軌跡上移動(dòng)點(diǎn)的速度。同時(shí)敏感區(qū)內(nèi)包含的采樣點(diǎn)數(shù)量應(yīng)該與原來(lái)的相同，以提高重置后軌跡段的真實(shí)性。

局部采樣點(diǎn)重置分為3部分：敏感區(qū)入口到替代停留點(diǎn)之間的移動(dòng)采樣點(diǎn)重置、替代停留點(diǎn)包含的停留核心點(diǎn)重置，以及替代停留點(diǎn)到敏感區(qū)出口之間的移動(dòng)采樣點(diǎn)重置。首先進(jìn)行局部采樣點(diǎn)的重置，如圖8所示，敏感區(qū)內(nèi)的第一個(gè)采樣點(diǎn)為A，最后一個(gè)采樣點(diǎn)為B；在A到SPi的原始軌跡段上尋找點(diǎn)C，使C到SPi與C到SPif的距離差最小，同理在B到SPi的原始軌跡段上找到點(diǎn)D，使D到SPi與D到SPif的距離差最小；同時(shí)將敏感停留點(diǎn)SPi的覆蓋范圍作為替代停留點(diǎn)SPif的覆蓋范圍；然后獲取敏感區(qū)內(nèi)移動(dòng)點(diǎn)的速度取值范圍{Vmin,Vmax}，分別在C到SPif和D到SPif段根據(jù)速度值和采樣時(shí)間確定合適的新采樣位置，并保證兩條軌跡段上重置的采樣點(diǎn)數(shù)與對(duì)應(yīng)原始軌跡段上的采樣點(diǎn)數(shù)相等。最后進(jìn)行停留核心點(diǎn)的重置，在SPif覆蓋范圍內(nèi)隨機(jī)選取采樣點(diǎn)，同樣須保證采樣位置點(diǎn)數(shù)不變。同時(shí)，為了提高軌跡抵抗攻擊的能力，在選取任何新的采樣點(diǎn)時(shí)需要檢測(cè)其位置是否合理，采樣點(diǎn)一般不應(yīng)該位于湖泊中央等小概率的位置處。

圖8  局部采樣點(diǎn)重置示意圖

查找到C、D兩個(gè)采樣點(diǎn)使得在局部采樣點(diǎn)重置的過(guò)程中，不需要重新選擇整個(gè)敏感區(qū)的采樣位置點(diǎn)了。這不僅減少了需要處理的采樣位置點(diǎn)的數(shù)量，同時(shí)也提高了軌跡的完整性。局部采樣點(diǎn)重置后，用戶軌跡的敏感隱私信息已不存在，可直接發(fā)布共享，用于數(shù)據(jù)分析與研究。