基于相對熵和K-means 的形狀相似差分隱私軌跡保護機制

朱素霞，劉抒倫，孫廣路

（哈爾濱理工大學計算機科學與技術學院，黑龍江 哈爾濱 150080）

1 引言

隨著智能手機和5G 網絡的普及，移動設備可以運行更復雜的程序，并以更快的速度、更低的時延傳輸信息，這為物聯網的發展提供了堅實的基礎。物聯網中基于位置的服務（LBS,location-based service）[1-2]從僅應用于導航類軟件，到逐漸應用于社交、游戲等產品，目前已應用于越來越多的領域。由于LBS 要求用戶將位置數據提供給相應的服務提供商或第三方數據提供者，因此如何保護用戶的位置隱私成為LBS 的主要關注點[3]。數據在向服務商提交的過程中涉及網絡傳輸、數據采集等多重隱私泄露風險，用戶的隱私信息可能會隨著軌跡數據的發布而被泄露。軌跡隱私信息一旦暴露，用戶將遭受的最大威脅便是敏感位置泄露，這可能導致攻擊者獲取用戶的真實地理信息，并根據背景知識推測出用戶地理軌跡，進一步獲得興趣愛好、行為習慣等重要用戶隱私信息。文獻[4]中記載了30 個基于位置應用中有15 個應用[5]泄露用戶的位置信息給攻擊者或分析服務器。文獻[6]表明MySpace 有3.6 億用戶信息被泄露。文獻[7]使用基于Twitter 社交網絡應用數據分析了用戶的敏感信息，如工作單位的具體位置等。因此，敏感位置信息的泄露可能會使用戶處于不利的地位。

近幾年，許多位置隱私保護機制被提出[8-9]，用于解決LBS 或持續的位置共享，而差分隱私因其具有嚴謹的數學基礎，并嚴格定義了攻擊者的背景知識，在軌跡保護研究領域受到了廣泛的關注。但是，現有基于差分隱私的軌跡保護機制存在以下2 個問題。

1)現有連續軌跡保護機制可以保證軌跡的隱私性，但是大部分沒有考慮不同位置因敏感度不同而需要不同的隱私預算。對軌跡中的不同位置分配相同的隱私預算，會導致隱私預算的浪費。例如，對不需要高強度保護的位置點分配了高強度保護對應的隱私預算，使該位置點被過度保護。使用相同的隱私預算對位置點進行保護，還會導致軌跡的可用性變差。例如，在不需要高強度保護的位置點進行高強度保護，因此分配給該位置點的隱私預算較小，使該位置點的噪聲較大，從而導致軌跡的可用性變差。

2)大部分現有的隱私保護方法只考慮了軌跡的時間和空間對軌跡可用性的影響，忽略了軌跡的相似性對軌跡可用性的影響[10]。圖1 中有3 條軌跡，分別為真實軌跡、干擾軌跡1 和干擾軌跡2，每條軌跡由4 個位置點組成。干擾軌跡1 和干擾軌跡2中的各個干擾位置到其對應的真實位置的距離都相同。干擾軌跡1 穿過了真實軌跡，形成了與干擾軌跡2 完全不同的干擾軌跡。當LBS 中用戶發布的位置和干擾軌跡1 類似時，干擾軌跡就會不斷穿過真實軌跡，這會對軌跡的可用性和真實性造成嚴重影響。在真實位置的隱私預算較小的前提下，干擾位置與真實位置距離較遠，會出現該干擾點特別突出的情況。攻擊者可以對軌跡數據采用噪聲濾波等手段過濾異常軌跡、恢復真實位置，導致保護失效。如果用戶發布的位置類似于干擾軌跡2，即使隱私預算較小，也會盡量使干擾軌跡與真實軌跡形狀相似，不會使該干擾點被過濾掉而導致保護失效。

圖1 條軌跡間形狀的對比

針對上述兩點問題，本文首先利用相對熵設計了一種位置敏感的隱私級別實時計算算法，根據發布位置的敏感度的不同，為不同敏感度的位置實時分配隱私級別；其次，將該隱私級別實時計算算法與本地化差分隱私相結合，建立σ?隱私模型；最后，提出了基于K-means 的形狀相似差分隱私（DPKTS,differential privacy based onK-means shape similarity）軌跡保護機制，該機制在保證各個發布位置隱私性的前提下，通過聚簇與提高軌跡形狀相似性，獲得更好的軌跡可用性。

2 相關工作

針對LBS 中的敏感位置信息，研究者已經提出了很多隱私保護方法，依據采用的核心思想可將其大致分為4 類，即泛化、混合區、抑制和擾亂[11]。其中，泛化是將原始軌跡上的敏感位置替換成一個區域，從而起到保護位置隱私的目的。k?匿名是一種最常用的泛化手段，它將真實位置信息替換成至少包含k個用戶的空間區域。文獻[12]提出了一種雙k機制，通過將k個查詢位置發送到不同的匿名器以實現k?匿名。文獻[13]在k?匿名的基礎上針對敏感的數據集提出了一種改進的K-means 算法。混合區是對軌跡中的某些位置用假名代替，以阻止用戶軌跡隨著時間變化的可追溯性，使攻擊者不能獲取用戶的真實位置信息。文獻[14]提出了一種基于用戶流的算法來估計圖中節點間的遷移率，并針對遷移率的攻擊方法，對傳統的混合區進行了改進。抑制是在發布位置時對某些敏感位置進行屏蔽或時延等。文獻[15]提出了2 種基于頻次的軌跡發布方法，分別通過抑制整個缺陷軌跡和特定的局部抑制實現隱私保護。擾亂即位置擾動，它將各個時間點的真實位置通過替換或添加噪聲等方式生成假的位置，以隱藏用戶的真實位置，是一種被廣泛應用的位置隱私保護機制。文獻[16]提出了一種動態假名方案，用于構造移動用戶的備用可能路徑以保護其位置隱私。文獻[17]提出了一種新穎的基于擾動的方案，即使在顯示用戶身份時也可以保護連續LBS 的查詢隱私。

滿足差分隱私的位置擾動方法研究逐漸成為軌跡數據隱私保護的熱點。差分隱私概念由Dwork等[18-19]于2006 年提出，通過添加少量高斯或指數分布的隨機噪聲來擾動數據庫查詢的真實答案，從而保護隱私。其主要思想是降低數據集中添加或刪除某一條數據對查詢結果的影響，從而讓攻擊者很難通過多次查詢推理數據集中的某條真實數據，即假設攻擊者能夠獲得除目標記錄外所有其他記錄的最大背景知識。在此假設下，差分隱私對基于各種背景知識的攻擊具有很好的保護效果，因為這些背景知識不可能提供比最大背景知識更豐富的信息。差分隱私可大致分為以下2 類[19-22]：中心化差分隱私和本地化差分隱私。中心化差分隱私將原始數據集中到一個數據中心，然后發布滿足差分隱私的相關統計信息，因此中心化差分隱私對敏感信息的保護始終基于一個前提，即可信的第三方數據收集者，保證第三方數據收集者不會竊取或泄露用戶的敏感信息。但是，在實際應用中，無法找到絕對安全的第三方數據收集者。本地化差分隱私是將數據的隱私化處理過程轉移到每個用戶上，使用戶能夠單獨地處理和保護個人敏感信息。基于本地化差分隱私的軌跡數據隱私保護大致可以分為2 個方面：歷史數據的發布[23-28]和實時位置數據的發布[29-30]。實時位置數據的發布機制因其可以應用于各種基于位置服務的商業軟件，從而有較高的應用價值和研究價值。

文獻[29]基于差分隱私的Geo-Indistinguishability機制，提出一種可以使隱私級別適應于多種區域的方法。文獻[31]將差分隱私保護的發布機制利用線性規劃技術進行優化，提出了一種滿足地理不可分辨性的δ-spanner 解決方案。文獻[30]利用馬爾可夫鏈表示軌跡上各個位置點的時序關系，重新定義了相鄰數據集這個概念，提出一種基于敏感度外殼的差分隱私位置發布機制。文獻[32]為了解決當前發布位置對以前真實位置的影響，提出了一種基于時空相關性的差分隱私軌跡保護機制。文獻[33]通過對軌跡上敏感位置點及其附屬敏感點的保護，并結合用戶軌跡位置的敏感度和用戶隱私保護的要求和隱私預算，提出了一種基于互相約束的個性化差分隱私保護方法。文獻[34]設計了一種基于霧計算和k?匿名的軌跡保護方案，用于連續查詢中的實時軌跡隱私保護和軌跡發布中的離線軌跡數據保護。

然而，現有的實時差分隱私位置發布機制大部分僅保證了軌跡的隱私性，并沒有針對不同敏感度的位置分配不同的隱私預算，且沒有考慮發布位置形成的軌跡形狀，造成軌跡可用性變差。

3 預備知識

表1 總結了本文的常用符號。

3.1 發布位置定義

為了獲得狀態概率轉移矩陣，需要將軌跡GPS坐標轉換為不同時刻的狀態，而將GPS 坐標轉換為狀態，需要先形成坐標系。將地理形狀按照同比例形式放入直角坐標系，并將軌跡的經/緯度位置坐標轉化為直角坐標系內坐標。將地圖劃分成網格后，通過統計歷史軌跡數據可以得到概率轉移矩陣。根據文獻[30,32]中的網格劃分方法，本文將網格設置為長寬均為0.34 km 的正方形，網格中的位置的編號格式如圖2 所示。整個坐標系的編號規則為：從左到右依次遞增，從下到上依次遞增。

圖2 位置發布時的地圖定義

3.2 差分隱私

差分隱私是對原始數據或原始數據查詢結果添加隨機噪聲，使最終結果與真實結果盡可能相像，且最大限度地減少識別其記錄的機會。差分隱私中使用了相鄰數據集的概念：如果結構相同的2 個數據集D和D'有且僅有一條數據不同，那么這2 個數據集被稱為相鄰數據集。下面，給出差分隱私的形式化定義。

定義1差分隱私[18-19]。給定相鄰數據集D和D'及在D和D'上的一個算法A，若算法A在D和D'上的任意輸出結果O滿足式(1)，則說明算法A滿足差分隱私。

其中，參數εt是t時刻的差分隱私預算，表示t時刻的隱私保護程度。εt越大，說明t時刻的隱私保護程度越低；當εt趨近于0 時，則說明t時刻算法A在相鄰數據集D和D′上輸出結果相差不多，此時算法A不會泄露數據集中任何數據的敏感信息。

然而，軌跡數據中每一時刻的位置信息均可能屬于敏感信息，因此軌跡數據隱私中并不存在傳統的相鄰數據集概念。本文借鑒文獻[20-21,30]中對軌跡隱私保護中差分隱私的定義，即已知t時刻的發布位置為ot，根據發布位置，推斷當前時刻真實位置的后驗概率Pr(tlt|ot)除以當前時刻真實位置的先驗概率Pr(tlt)的值滿足差分隱私定義，描述為

其中，εt是t時刻真實位置所在區域的差分隱私預算。因此發布位置ot是經過隱私化處理的數據，滿足本地化差分隱私的概念，即由用戶進行隱私化處理。

若設定的隱私保護預算為ε，實際保護后的隱私保護預算為ε'，若ε＜ε′，則實際的隱私保護強度小于設定的隱私保護強度。

3.3 信息熵及相對熵

信息熵是系統對信息量的期望，信息量是對信息的度量，而信息量與具體發生的事件有關。信息量的大小與隨機事件的概率有關，概率越小的事件發生后產生的信息量越大，概率越大的事件發生后產生的信息量越小。信息量定義為

其中，p(x)為事件發生的概率，負號是為了保證信息量大于或等于0。

信息量用于度量一個隨機事件發生后所帶來的信息，而信息熵則是在結果產生之前對可能產生的信息量的期望，即考慮該隨機變量的所有可能取值。信息熵也常用來衡量一個系統的復雜程度，系統越復雜，信息熵越大；反之，一個系統越簡單，可能出現的情況種類越少，則信息熵越小。信息熵定義為

其中，p(xi)為事件發生的概率，與信息量的計算式相同，信息熵計算式中的負號也是為了保證信息熵大于或等于0。與信息熵不同，相對熵是用來衡量2 個概率分布之間的差異，又稱為 KL 散度（Kullback-Leibler divergence），定義為

根據式(5)可知，相對熵具有如下性質。

1)如果2 個分布p(xi)和q(xi)相同，那么相對熵等于0。

2)不對稱性，即DKL(p||q)≠DKL(q||p)。

3)DKL(p||q)≥0。

根據相對熵的性質可知，只有當p(xi)=q(xi)時，其值為0。若p(xi)和q(xi)略有差異，其值就會大于0，因此相對熵的值越小，則表明2 個概率分布之間的差異越小。

4 軌跡形狀相似性與軌跡可用性

為了描述2 條軌跡在視覺上的相似度，本文通過Fréchet 距離來衡量2 條軌跡的形狀相似性。Fréchet 距離最早由Fréchet 提出，隨后由Alt 等[35]給出了計算方法。如前文所述，大多數位置發布機制沒有考慮軌跡形狀對于軌跡可用性的影響，因此為了提高軌跡的可用性，本文從軌跡形狀相似性方面進行優化，通過計算Fréchet 距離衡量2 條軌跡之間的相似度，Fréchet 距離越小，2 條軌跡之間越相似；反之，2 條軌跡之間越不相似。Fréchet 距離離散化的表示形式為

其中，A和B分別為2 條曲線，t為時間點，A(α(t))、B(β(t))分別為曲線上A和B在t時刻的采樣點，d(A(α(t)),B(β(t)))為2 個采樣點之間的歐氏距離。在每次采樣中，t離散地遍歷區間[0,1]，得到該種采樣下的最大距離max{d(A(α(t)),B(β(t)))}。離散Fréchet距離是連續Fréchet 距離的近似，當曲線選取的離散點足夠多時，則近似等于連續Fréchet 距離。

假設某時刻可能的發布位置為ot，真實位置為zt，則本文將這2 個位置之間的距離作為誤差評價，可以描述為

如果發布位置與真實位置距離誤差為零，則說明2 個位置點重合，即發布位置與真實位置重合；反之則說明發布位置與真實位置不重合。

特別地，對于長度為n的軌跡，同樣以距離誤差[27,36]為基礎定義軌跡可用性，如式(7)所示，距離誤差TA 為發布位置與真實位置的均方根誤差之和，可以描述為

對某條發布軌跡而言，其距離誤差TA 越大，說明其與真實軌跡重合度越低，從而其可用性也就越差。因此，可以通過計算發布軌跡的距離誤差來判斷軌跡的可用性。

通過計算Fréchet 距離衡量發布軌跡和真實軌跡的形狀相似度，通過距離誤差計算發布軌跡的可用性，發布軌跡與真實軌跡間的形狀相似度越大，距離誤差就會越小，則發布軌跡的可用性就會越高。

5 σ?隱私模型

對于差分隱私位置擾亂算法，為不同位置分配相同的隱私預算并不合理，一方面會造成隱私預算的浪費，另一方面會造成位置節點的可用性變差。根據差分隱私的定義，隱私預算越少，保護強度越大，因此應為敏感位置分配較少的隱私預算，為不敏感位置分配較多的隱私預算。根據不同位置點與理想狀態的相對熵得到不同的敏感度，而不同的敏感度需要不同的隱私級別，本文提出了一個位置敏感的隱私級別實時計算算法，并將其與隱私預算結合，建立σ?隱私模型。

5.1 發布位置集合

通過對數據集中歷史軌跡進行統計，并根據前文提到的發布位置定義，將GPS 數據與地圖中預設的格子對應起來，得到狀態轉移矩陣。由于一個系統的某些因素在轉移中的第n次結果只受第n?1 次的結果影響，即只與當前所處狀態有關，而與過去狀態無關。因此可以根據狀態轉移矩陣，在當前時刻推測下一時刻可能位置的集合PRN，并對PRN 進行擴充，擴充規則為：以PRN 中的點形成凸包，求出凸包的中心點，以該中心點為圓心，通過控制半徑的大小來擴充整個集合，判斷某一點是否屬于可能發布位置的集合中。判斷規則為

其中，p表示要判斷的點，PRN.cfc 表示集合PRN的凸包的中心點，dis(a,b)表示a 點與b 點間的距離，r.length 表示圓的半徑，p.ic 表示判斷結果，只有p.ic=?1 時，該點才為集合中的點。擴充規則可以簡化為：以集合PRN 的凸包的中心點為圓心，選定一個值為半徑，圓內的點的并集。半徑的值越大，集合越大。擴充后的集合為PRNN={pr1,…,prm}。

擴充規則具體如圖3 所示。

圖3 中灰色的區域為可能發布的位置區域，如上述規則所示，如果發布位置的中心與圓心距離大于圓的半徑，則該位置不能被擴充到集合中。圖3中，位置a 的中心與圓心的距離大于圓的半徑，則位置a 不屬于可發布位置集合中，虛線為圓心到位置的距離，加粗的線為圓的半徑。

圖3 擴充規則

5.2 隱私級別計算

如果歷史數據被敵手獲得，敵手可以推測出狀態轉移矩陣，進而可以根據狀態轉移矩陣得到下一時刻可能存在位置的集合PRN，并根據PRN 大概率得到下一時刻的位置節點，因此本文采用信息熵來衡量敵手獲得可能存在位置集合后能獲得多少信息，并根據敵手獲得的信息量設定不同的敏感度。首先設定一個理想狀態，在該狀態下即使被敵手獲得可能存在位置集合，也無法大概率得到下一時刻的位置節點。

理想狀態具體解釋如下。假設有2 個路口R 和S，路口R 和S 分別有2 條岔路，其中旅行者在路口R去往每條岔路的概率為(1/2,1/2)，在路口S 去往每條岔路的概率為(1/4,3/4)，由于信息熵是對“不確定現象”的數學化度量，旅行者在路口S 與在路口R 相比，顯然在路口R 的選擇更加不確定，而在路口S則大概率會去往第二條岔路，因此，如果去往各個岔路的概率是平均分布的概率分布，則岔路口的去向具有更大的不確定性。因此本文中提到的理想狀態是一個大小與集合PRNN 相同，且每一個位置點的概率都為1/m的位置點的集合，因為這種理想狀態具有比PRNN 的概率分布更大的不確定性。

本文采用相對熵描述集合PRNN與理想狀態的概率分布差異，并以相對熵與理想狀態的信息熵的比值作為真實位置點的敏感度，可以描述為

其中，r(xi)為理想狀態中某一個事件的概率，p(xi)為PRNN 中某一個事件的概率，q(xi)為PRNN 中的某一個事件在理想狀態中對應事件的概率。式(9)中分母為理想事件概率分布的信息熵；分子為相對熵，對應理想事件與實際事件概率分布的信息熵的差值。因此，敏感度S表示實際事件距離理想事件所需信息熵占理想事件信息熵的比值。

根據敏感度確定PRNN 中各個點的隱私級別，規則如下。確定PRNN 中的點k是否屬于PRN，如果k點不屬于PRN，則k點的隱私級別為s/m；如果k點屬于PRN，則該點的隱私級別為(1?S)k.pr，k.pr 為k點對應狀態轉移矩陣中的值。上述規則可以總結為，對于屬于PRN 的點，分配較高的隱私級別；對于不屬于PRN 的點，分配較低的隱私級別。因為PRN 中的點是下一時刻大概率會出現的位置，所以對于大概率出現的位置應分配更高的隱私等級，對于下一時刻小概率出現的位置，應分配更低的隱私等級。

位置敏感的隱私級別實時計算算法如算法1所示。

5.3 建立差分隱私模型

在本地差分隱私預算基礎上，結合位置敏感的隱私級別實時計算算法，本文提出了σ?隱私模型。

定義2位置σ?隱私。如果一個發布位置能夠滿足σ?隱私，則該點的差分隱私預算ε和隱私級別pl 滿足

由式(10)可知，在σ相同的情況下，隱私級別pl 越大，則為該位置分配的隱私預算ε越小。根據差分隱私的原理可知，一個位置的隱私級別越大，其保護強度就會越大；反之，保護強度越小。當pl=1 時，ε=σ。由于本文算法是實時分配可能發布位置的隱私級別，發布位置之前要計算可能發布位置集合中各個位置的隱私級別，因此隱私模型不能太復雜，以免使算法的時間復雜度過高。

6 基于K-means 的形狀相似差分隱私軌跡保護機制

為了解決連續軌跡隱私保護機制軌跡可用性較差的問題，本文提出了一種基于K-means 的形狀相似差分隱私軌跡保護機制。該機制首先要保證軌跡中每個發布位置的隱私性，其次通過K-means 算法使發布軌跡的方向與真實軌跡相似，優化軌跡形狀相似性，提高軌跡的可用性。

6.1 隱私預算

根據軌跡數據中差分隱私的定義，隱私預算是發布位置的后驗概率與先驗概率的比值，而發布位置的先驗概率和后驗概率都需要通過馬爾可夫概率轉移矩陣得到。下面，說明如何獲得馬爾可夫概率轉移矩陣。

本文使用一階馬爾可夫鏈模擬用戶真實位置之間的相關性，并通過統計用戶的歷史記錄得到狀態轉移矩陣M。M是一個二維矩陣，矩陣中的元素mij表示用戶從第i個區域轉移到第j個區域的概率。

假設用戶真實位置區域集合為TL={tl1,…,tlt}，利用差分隱私位置發布機制處理后，生成的擾亂區域集合為DL={dl1,…,dlt}。利用馬爾可夫狀態轉移概率矩陣M，結合本文提出的位置敏感的差分隱私位置發布機制，對t時刻存在的位置進行推測，并構建t時刻的真實位置可能發布的集合PL={pl1t,和每個位置的先驗概率值的集合其中，n為集合中元素的個數。當t時刻的擾亂位置dlt發布后，就可以根據此擾亂位置推測出t時刻的真實位置tlt，即發布位置的后驗概率Pr(tlt|dlt)，并將各個時刻的后驗概率形成集合為計算后驗概率，考慮如何求得t時刻的差分隱私位置發布概率矩陣Rt。設t時刻發布的位置區域集合為PRNN={pr1,…,prm}。矩陣Rt是一個維度為n×m的矩陣，元素為t時刻真實區域到發布的擾亂區域為的概率值。則位置的后驗概率為

通過式(11)，可以得到每個區域位置的后驗概率，進而得到每個位置的隱私預算，并判斷該區域的隱私預算是否小于預設的預算。本文將各個區域的隱私預算形成一個隱私預算集合ept={ep1t,…,epmt}。

6.2 位置發布算法描述

為了使發布軌跡與真實軌跡方向盡可能一致，首先利用K-means 算法，對PRNN 中的位置點進行聚類，選擇與真實軌跡方向最相近的簇為備選集合；然后對備選集合內的位置點根據式(6)計算t時刻與t?1 時刻真實位置的軌跡與發布位置的軌跡的Fréchet 距 離，并 形 成 Fréchet 距 離 集 合frt={fr1t,…,frmt}；最后選擇符合隱私預算且Fréchet距離最小的位置點作為發布位置點。位置發布算法如算法2 所示。

算法2位置發布算法

輸入真實位置的轉移概率矩陣M，軌跡的隱私保護預算ε={ε1,…,εt}，圓的半徑r，t?1 時刻的真實位置tlt?1，t時刻的真實位置tlt，t?1 時刻的干擾位置dlt?1

6.3 算法分析

位置發布算法的運算時間是對集合PRN 擴展的時間、對集合PRNN 聚簇的時間以及運算Fréchet距離的時間之和。其中，對PRN 擴展的時間與理想狀態的大小有關，對PRNN 聚簇的時間與簇頭個數有關，運算Fréchet 距離的時間與簇內位置的個數有關。

在隱私和可用性方面，由于采用了滿足差分隱私的保護機制，并且引入了相對熵和K-means 算法，既可以使t時刻的發布位置滿足εt差分隱私，又能使發布軌跡與真實軌跡盡可能相似。因此，在保證隱私的前提下，算法選擇使發布軌跡與真實軌跡方向相似，且使軌跡形狀也相似的位置點作為發布位置，在滿足軌跡隱私性的前提下，通過軌跡形狀相似性提高了軌跡的可用性。

7 實驗與分析

本文采用數據集Geolife 和Gowalla 對DPKTS進行實驗分析。Geolife 數據集包含182 個用戶于2007 年4 月到2012 年8 月在北京活動的真實數據，一共有1 7621條軌跡。Gowalla數據集包含了15 116個用戶于2009 年2 月到2010 年10 月在加州范圍內移動社交網站上簽到的數據，共6 442 890 個簽到位置。對上述2 個數據集，抽取用戶編號、時間戳、經度和緯度作為新的數據集。

實驗的環境如下：Intel i7-9700K 3.6 GHz，16.00 GB 內存，Microsoft Windows 10 操作系統，算法均在Pycharm2018 下實現。

對于DPKTS，本文主要分析隱私模型參數σ及簇頭個數對軌跡可用性的影響、理想狀態的大小對運算時間的影響，以及簇頭個數對運算時間的影響。在衡量σ對軌跡用性的影響時，本文將DPKTS 與PIM（planar isotropic mechanism）[30]和DPLRM（differentially private location release mechanism）[32]進行對比。這2 種對比方法都是基于差分隱私的實時軌跡保護方法，且DPLRM 考慮了時序相關性。

首先，針對σ對發布軌跡可用性的影響進行實驗分析。在DPKTS 中，σ與傳統差分隱私中的隱私保護預算ε等價。如圖4 所示，DPKTS 的可用性較好，因為DPKTS 對位置是敏感的，而不同位置的敏感度不同，所以針對不同位置設定不同隱私級別且通過K-means 算法得到與真實軌跡方向最相似的備選集合，并以軌跡形狀相似性為優化目標，從而提高了軌跡的可用性，所以DPKTS 的軌跡可用性明顯優于其他方法。PIM 并沒有考慮軌跡的可用性，僅對發布位置做了基于差分隱私的處理，所以軌跡可用性一般。DPLRM 的軌跡可用性較PIM 略好，這是因為DPLRM 在滿足差分隱私的同時，還對軌跡中的半馬爾可夫模型進行優化。但由于DPLRM沒有針對軌跡可用性進行優化，軌跡可用性比DPKTS 略差。不同方法在Geolife 數據集上的表現均優于在 Gowalla 數據集的表現，這是因為Geolife 數據集采樣頻率更高，細粒度更好，所以結果更精確。

圖4 σ 對軌跡可用性的影響

本文還分析了簇頭個數對軌跡可用性的影響，當理想狀態數目為121、σ為1 時，分別計算不同簇頭數對于方法可用性的影響結果，如圖5 所示。隨著簇頭數的增加，軌跡可用性逐漸變差。這是因為隨著簇頭數的增加，每個簇中可選擇的位置點變少，且DPKTS 選擇與真實軌跡方向最相似的簇，所以當簇頭數增加時，簇內位置點變少，軌跡可用性降低。

圖5 簇頭數對軌跡可用性的影響

圖6 展示了不同數據集上隱私保護強度的對比結果，其中橫坐標為設定的隱私保護強度，縱坐標為實際隱私保護強度，ε′值越小，說明保護強度越好。從圖6(a)可以看出，DPKTS 的隱私保護強度與PIM 的隱私保護強度接近，最壞的情況是在σ=0.4 時，此時也只比PIM 降低了約2.6%，這是因為DPKTS 旨在提高軌跡可用性，而PIM旨在提高軌跡的保護強度，忽略了軌跡的可用性。與同樣旨在提高軌跡可用性的 DPLRM 相比，DPKTS 具有更好的隱私保護強度。當σ=0.6 時，DPKTS 比DPLRM 的隱私保護強度提高了2.0%。在圖6(b)中，由于所使用的數據集時序相關性較弱，采樣率較低，使不同方法的隱私保護強度更接近，可以看出DPKTS 對時序相關更強的數據有更好的表現。

其次，分析理想狀態的大小對運算時間的影響，實驗中聚類時的簇頭數為3，結果如圖7 所示。從圖7 中可以看出，運算時間與理想狀態的數目成正比，即理想狀態數目越多，運算時間越多。這是因為理想狀態數目越多，計算位置點的敏感度所需要的時間越多，計算各個位置點的隱私級別所需要的時間越多，在聚類后，簇中節點數也會增加，所以理想狀態數目越多，運算時間越長。

圖6 隱私保護強度

圖7 理想狀態數目對運算時間的影響

最后，分析簇頭數對運算時間的影響，結果如圖8 所示。實驗中，分別以不同理想狀態大小進行實驗，并對不同理想狀態數目設定多組實驗，以不同簇頭數進行實驗。由圖8 可知，當理想狀態數目為121、簇頭數為1 時，運算時間最少；當理想狀態數目為441、簇頭數為2 時，運算時間最少。每一種理想狀態下，都有可以使運算時間最少的簇頭數，因此設定不同理想狀態數目時，需要選用不同的簇頭數，不能使用相同簇頭數。但是，當理想狀態數目逐漸變多時，簇頭數也應逐漸變多，才可使預算時間最小。

圖8 簇頭數對運算時間的影響

8 結束語

針對位置服務中軌跡隱私保護問題，本文通過實時計算真實位置的相對熵衡量其敏感度，并根據敏感度為可能發布位置分配不同的隱私級別；通過結合節點隱私級別與差分隱私預算建立σ?隱私模型；利用K-means 獲得與真實軌跡方向一致的位置備選集合，使用Fréchet 距離來計算不同軌跡之間的相似程度，實現了一種基于形狀相似的K-means 差分隱私軌跡保護機制。實驗結果表明，本文方法在保證軌跡隱私性的前提下，提高了軌跡的可用性。