個性化時空數據隱私保護

（沈陽航空航天大學計算機學院，沈陽 110136）

0 引言

在數字化時代，隱私保護已成為一個越來越具有挑戰性的問題。隨著科學技術的發展，許多科研機構、企業、國家和個人希望從個人信息中找到可利用的信息，這使得個人信息被許多第三方獲取。其中，基于時空數據的大數據分析方法可以幫助實現規劃城市發展、制定最優出行計劃等功能。時空數據在提供多重緯度數據分析的同時，也存在著嚴重的個人隱私（如住址、生活習慣和健康狀況等）泄露威脅。因此，保護時空數據中的隱私已經成為一項熱點研究問題［1-2］。

圖1（a）中的用戶時空數據以軌跡數據形式列出，每條軌跡由若干個簽到數據按時間先后順序排列而成。圖1（b）為用戶設置的敏感數據。其中，位置l3為醫院，其在軌跡tr1、tr3和tr5中均出現過，用戶不想泄露在任何時間前往過該位置的時空數據，將l3設置為敏感位置；位置l7是酒吧，軌跡tr2中的（l7，t23）是用戶在t23時刻前往過位置l7形成的簽到數據，t23屬于用戶上班時間段內，用戶不想泄露此簽到數據，將（l7，t23）設置為敏感簽到數據。而軌跡tr4中的（l7，t42）是用戶在t42時刻出現在酒吧形成的簽到數據，該時刻屬于用戶的休息時間，用戶沒有將其設置為敏感數據；（l1，t31）→（l5，t32）→（l3，t33）為用戶在某段時間內經過的軌跡，對應圖1（a）中的軌跡tr3，該條軌跡包含用戶的私密行程，用戶將tr3設置為敏感軌跡。可見，對于時空數據，用戶具有個性化隱私保護需求。

目前針對時空數據的隱私保護方法分別對位置隱私［3-7］和軌跡隱私［8-11］單獨進行保護，針對上述個性化時空數據隱私保護需求，會造成隱私數據泄露或者過度保護，使得數據可用性降低。為解決此問題，本文提出一種個性化時空數據隱私保護方法，用戶可以個性化設置隱私數據（位置隱私、簽到數據隱私、軌跡隱私），從而有效地對用戶的時空數據進行個性化隱私保護。

圖1（c）為泛化匿名后的時空數據（以軌跡數據形式列出，泛化后的時空數據如虛下劃線處所示）。其中，軌跡tr1、tr3和tr5中的敏感位置l3均被泛化為位置集合｛l3，l8，l9，l12｝，使得l3的泄露概率為1/4；軌跡tr2中的敏感簽到數據（l7，t23）被泛化為（｛l7，l10，l11｝，t23），使其泄露率為1/3；敏感軌跡tr3中的簽到數據（l5，t32）和（l3，t33）分別被泛化為（｛l5，l4，l13，l14｝，t33）和（｛l3，l8，l9，l12｝，t33），使得軌跡tr3的軌跡匿名（Trajectory Anonymity，TA）率（具體定義后文給出）為50%，軌跡泄露的概率為（100%-50%）=50%。

圖1 時空數據和敏感數據及泛化后的時空數據Fig.1 Spatio-temporal data，sensitive data and generalized spatio-temporal data

本文采用啟發式泛化方法處理隱私數據，在滿足個性化隱私保護需求的前提下，盡可能減少信息損失。例如，針對軌跡隱私保護，以往的研究方法都是對敏感軌跡中所有的簽到位置進行處理，這樣會因過度保護造成大量信息損失。而采用啟發式泛化方法，泛化操作的每一步都同時考慮隱私保護的最大化和信息損失的最小化，減少因過度保護造成的信息損失。實驗結果表明，本文算法能有效地個性化保護隱私數據，且信息損失最低。

本文研究內容主要面臨3個挑戰，如下所述：

1）針對用戶分類設置的隱私數據，如何實現個性化隱私保護具有挑戰性。以往的研究中，對位置隱私和軌跡隱私單獨進行保護，而且沒有考慮針對簽到數據的隱私保護。如何實現3 種隱私數據的綜合保護，且不造成隱私過度保護是研究的難點。

2）如何實現隱私保護最大化的同時降低信息損失具有挑戰性。被保護的時空數據最終是要通過大數據分析方法得到利用，以往的研究中，往往只考慮隱私保護最大化，忽略了信息損失造成的影響。本文針對此問題設計的啟發式泛化方法是研究的難點。

3）候選泛化位置的選取具有挑戰性。如果將簽到數據（l，t）中的位置l泛化到位置集合g=｛l，l′｝，假設簽到數據（l，t）的前驅和后繼簽到數據分別為（lp，tp）和（ls，ts），那么，位置集合g中的泛化位置l′需要滿足以下約束條件：1）泛化位置l′∈g應滿足lp和ls之間的時空可達性。以lp為例，用戶能在從lp到l的時間（t-tp）內由lp到達l′，即滿足時空可達性；2）泛化位置l′應符合用戶的運動模式，否則泛化位置l′容易被攻擊者識別為假位置；3）因為道路網中的位置數量巨大，如何有效地選擇滿足上述約束條件的泛化位置是研究的難點，而且是個性化隱私保護算法高效實用的關鍵。

本文主要貢獻包括：1）定義了時空數據發布中保護用戶個性化設置的隱私數據的問題；2）提出了一種個性化時空數據隱私保護算法保護用戶數據隱私；3）優化了候選泛化位置搜索技術，提高算法執行效率；4）經過大量基于真實時空數據的實驗，證明本文算法能有效地保護用戶隱私，同時保持已發布時空數據的高可用性。

1 相關工作

針對位置隱私的保護方法主要有差分隱私、空間匿名和加密技術。差分隱私保護技術通過在原始數據中添加隨機噪聲來干擾隱私數據，能夠有效防止基于背景知識的惡意攻擊。Xiong等［3］提出一種基于獎勵機制的空間眾包分配方法，并通過向用戶位置信息中添加Laplace噪聲來達到位置隱私保護的目的。但是，由于差分隱私方法需要在查詢結果中添加大量隨機化噪聲信息來保護隱私，這樣會導致數據可用性急劇下降，甚至在有些復雜查詢中，某些真實結果會被隨機添加的噪聲數據完全掩蓋。空間匿名技術最早是由Sweeney［4］提出的一種避免個人敏感數據泄露隱私保護技術，主要思想是用戶的敏感位置不能與其他用戶的至少k-1個位置區分。Vu等［5］提出了基于局部敏感哈希［6］的隱私保護機制，將用戶的位置進行分組，每組包含至少k位用戶以實現空間匿名。基于加密技術的隱私保護方法是對用戶的基于位置服務查詢信息進行加密處理，使攻擊者獲取到用戶信息后也無法分析出隱私信息。Khoshgozaran等［7］提出了一種基于PIR（Protocol Independent Routing）協議并通過模糊位置查詢獲取k-NN（k-Nearest Neighbor）服務的方法，這種方法可以降低計算和通信的復雜度。

軌跡隱私保護方法主要有抑制法、假軌跡法、泛化法和差分隱私法。抑制法是有選擇地抑制發布軌跡數據中的敏感位置或者整條軌跡。趙婧等［8］提出了基于軌跡頻率的軌跡抑制方法，采用特定的軌跡局部抑制法對數據進行處理。抑制法雖能簡單直接地對軌跡隱私進行保護，但會造成大量信息損失，且當攻擊模型不確定時，抑制法將失效。假軌跡法是通過向原始軌跡數據中加入虛假軌跡來進行干擾，降低原始軌跡泄露的概率。董玉蘭等［9］提出了通過旋轉真實軌跡得到候選假軌跡的方法，然后根據隱私保護要求閾值對假軌跡進行篩選，并將假軌跡添加到真實軌跡中以達到保護隱私的目的。基于泛化的軌跡隱私保護方法的核心思想是采用空間匿名技術，找到k-1 條與敏感軌跡相似的泛化軌跡與敏感軌跡同時發布，使敏感軌跡泄露的概率不超過1/k以達到隱私保護目的。Abul 等［10］提出了基于貪心聚類算法的（k-δ）-匿名模型，利用每一個采樣時間點的位置均值形成聚類軌跡進行發布。基于差分隱私的軌跡隱私保護方法類似于位置差分隱私保護技術，主要思想是向原始軌跡數據中添加隨機噪聲來擾動原始數據。Hua 等［11］提出了以空間泛化為基礎的差分隱私算法，利用Laplace 機制向軌跡數據中添加噪聲來保護敏感軌跡。

關于個性化隱私保護方法中，目前的研究同樣都是分別對位置隱私和軌跡隱私進行保護，沒有考慮用戶個性化隱私保護需求。Jia 等［12］提出了基于p-敏感k-匿名的個性化敏感特征匿名技術，利用敏感層次樹推廣敏感屬性級別來保護位置隱私。Tian等［13］提出了一種用于軌跡數據發布的新型個性化差分隱私機制，利用Hilbert 曲線原理對原始軌跡數據進行擾動來實現隱私保護。同樣，此方法采用了差分隱私機制，會造成大量的信息損失，使數據可用性降低。孫嵐等［14］提出一種個性化隱私保護軌跡匿名算法。該算法采用基于貪心聚類的等價類劃分思想對含有不同隱私需求的軌跡集合進行個性化匿名處理。Gedil 等［15］提出了一種針對移動系統中位置隱私的個性化匿名模型，利用統一的個性化隱私框架使每個移動節點能夠指定其最低的匿名級別，通過消息擾動引擎來實現隱私數據保護。Deldar等［16］通過提出一種針對移動對象的個性化隱私保護算法來滿足不同運動對象的個性化隱私保護要求。此算法將非時空敏感屬性和差分隱私有機結合起來，以統一的方式實現個性化隱私屬性泛化。

現有的個性化隱私保護方法沒有對隱私數據進行分類，用戶不能設置自己的隱私數據，不能達到真正的個性化隱私保護要求。本文針對此問題，提出了個性化時空數據隱私保護方法。

2 預備知識與問題定義

時空數據（Spatio-Temporal Data，STD）是同時具有時間和空間維度的數據，時空數據集合用DST表示。位置是地圖上的空間坐標點（家、超市、藥店、醫院、公司等），表示為l=（x，y），其中x為經度，y為緯度，直接使用l代表位置，用L表示位置集合。簽到數據是帶有時間戳的位置信息，用cd=（li，tdm）來表示，用DC來表示簽到數據集合。一條軌跡是由m個簽到數據組成的序列，可以將軌跡表示為tr=（l1，t11）→（l2，t12）→（li，tdm），軌跡集合表示為DTR。

定義1時空數據隱私。用戶不愿泄露的時空數據稱為時空數據隱私。本文將時空數據隱私分為3 個類型，分別為位置隱私、簽到數據隱私和軌跡隱私。

位置隱私指用戶不愿泄露的敏感空間位置l，如圖1（b）中的位置l3是醫院，用戶不想泄露在任何時間前往過此位置的信息，將其定義為位置隱私，其集合表示為SL；簽到數據隱私指用戶不想泄露某一具體時刻簽到的敏感空間位置（l，t），如圖1（b）中的簽到數據（l7，t23）中的位置l7是酒吧，用戶在休息時間可以隨意前往該位置，但是t23時刻屬于用戶上班時間段內，用戶不想泄露此簽到數據，將其定義為簽到數據隱私，其集合表示為SC；軌跡隱私指用戶不愿泄露的某一天內敏感簽到數據按時間先后順序排列形成的集合，如圖1（b）中的軌跡（l1，t31）→（l5，t32）→（l3，t33）是用戶某天依次經過了位置l1、l5、l3所形成的軌跡，用戶不想泄露此條軌跡，將其定義為軌跡隱私，其集合表示為STR。

定義2位置距離dist。給定兩個位置li和lj，兩個位置間的歐氏距離稱為位置距離，如式（1）所示：

定義3位置泄露率lri。給定用戶時空數據集DST，每個簽到數據中時刻tdm對應的位置集為gi，在此時刻泄露用戶真實位置的概率為

其中，位置集gi為對該位置泛化處理后，tdm時刻時空數據所包含所有位置的集合。

定義4軌跡匿名率TA。給定一條敏感軌跡tr，該軌跡泛化處理后的軌跡匿名率如式（2）所示：

其中：|Gtr|為軌跡tr泛化后的軌跡數量；|gtri|表示每條泛化軌跡中位置的數量；dl表示泛化后的位置是否與原位置相同，相同為0，不同為1。

軌跡匿名率用來衡量對敏感軌跡泛化處理后相應軌跡集的匿名程度。例如，圖1（c）中敏感軌跡tr3所形成的泛化軌跡數量 |Gtr|=1×4×4=16 條，每條泛化軌跡中的位置數量|gtri|=3個。如果第16 條泛化軌跡gtr16=（l1，t31）→（l14，t32）→（l12，t33），其中：l1與原軌跡中的位置相同，l14和l12與原軌跡中的位置不同，則公式TA中的dl1、dl2、dl3分別為0、1、1。所以，敏感軌跡tr3的軌跡匿名率

此定義保證了敏感軌跡中不同位置的泛化程度均滿足隱私保護需求。例如，針對敏感軌跡tr3，若僅考慮其泄露概率小于20%，那么對其泛化后的時空數據可為tr3=（l1，t31）→（l5，t32）→（｛l3，l8，l9，l12l14｝，t33）。因位置l3被泛化成位置集合｛l3，l8，l9，l12l14｝，所以，敏感軌跡tr3的泄露概率為20%；但是，此方法中，位置l1和l5沒有得到保護，攻擊者容易推斷出真實的敏感軌跡。采用定義4 給出的軌跡匿名率TA度量軌跡匿名程度，可以使敏感軌跡tr3中2/3 的敏感位置得到匿名保護，使得此軌跡被推演攻擊的概率降低。

定義5時空數據隱私泄露。給定用戶時空數據集DST，敏感數據集DS=｛SL，SC，STR｝，隱私保護閾值（p，q，ε），如果：

1）存在位置l∈SL泄露概率大于1/p；

2）存在簽到數據cd∈SC泄露概率大于1/q；

3）存在軌跡tr∈STR軌跡匿名率小于ε。

以上任意一條成立，則稱為時空數據隱私泄露。

例如，將位置隱私保護閾值p設為5，圖1（c）中的敏感位置l3全部泛化為｛l3，l8，l9，l12｝，使l3泄露的概率為1/4，大于1/p，將造成位置隱私泄露。同理，簽到數據隱私泄露指敏感簽到數據泄露概率大于1/q。軌跡隱私泄露指敏感軌跡泛化后按式（2）計算得到軌跡匿名率小于ε，即泄露概率大于（1-ε）。

定義6時空數據泛化。給定一個簽到數據（li，tdm），泛化操作定義為將簽到數據（li，tdm）中的位置li轉換為位置集合g=｛li，l′1，…，l′s｝，g中有s+1 個位置，g中的每個位置出現在td（m-1）時刻到td（m+1）時刻之間的概率相等。

定義7信息損失。給定時空數據集DST=｛（l1，t11），（l2，t12），…，（ln，tdm）｝，將敏感簽到數據中的位置li（1≤i≤n）泛化到一個位置集合gi中，得到泛化后的時空數據集DST′=｛（g1，t11），（g2，t12），…，（gn，tdm）｝。時空數據的熵定義為H(DST)=lp× lb(lp)=其中lp=如果位置li被抑制，則 |gi|=|Li|，|Li|為敏感位置所在軌跡的位置數。對時空數據集DST進行泛化和抑制操作時，造成的信息損失定義為

此信息損失定義考慮了位置信息熵對于用戶整個時空數據集的影響。以往關于時空數據信息損失的定義，只考慮替換或刪除某個位置后該位置的信息損失比率、本文定義更有利于計算因時空數據泛化操作所造成的信息損失。

定義8（p，q，ε）-匿名。給定用戶時空數據集DST，隱私保護閾值（p，q，ε），經泛化處理后，得到匿名時空數據集DST′中任一位置隱私泄露率不大于1/p，簽到數據隱私泄露率不大于1/q，軌跡匿名率不小于ε，則認為時空數據集DST′滿足（p，q，ε）-匿名。

圖1（c）中的時空數據集滿足（4，3，0.5）-匿名。

問題1 給定用戶的時空數據集DST，用戶設置的隱私數據集合｛SL，SC，STR｝，隱私保護閾值（p，q，ε），通過對時空數據進行泛化處理，得到的時空數據集DST′滿足（p，q，ε）-匿名要求，且保證最低信息損失。

3 個性化時空數據隱私保護

在本章中，提出個性化時空數據隱私保護（Personalized Privacy Protection for Spatio-temporal Data，PPPST）算法，對用戶個性化設置的隱私數據進行保護，設計了啟發式規則度量泛化操作，并優化了候選泛化位置搜索方法。

首先，提出敏感數據判定（Sensitive Data Determination，SDD）算法，對用戶定義的敏感數據集DS=｛SL，SC，STR｝進行判斷，生成敏感數據列表S，以便進行啟發式迭代泛化。

3.1 敏感數據判定算法

如算法1 所示，算法SDD 以時空數據集合DST、敏感數據集合DS=｛SL，SC，STR｝、隱私保護閾值（p，q，ε）作為輸入，輸出一個敏感數據列表S。

算法1 敏感數據判定算法（SDD）。

對敏感數據集合｛SL，SC，STR｝進行分類判斷，若時空數據DST中每個包含敏感位置l的簽到數據cd泛化后的位置集合g中位置個數小于閾值p，則將該簽到數據添加到敏感數據列表S中（第2）～6）行）；若敏感簽到數據集SC中每個簽到數據cd泛化后的位置集合g中位置個數小于q，則將該簽到數據添加到敏感數據列表S中（第7）～9）行）；若敏感軌跡集STR中每條敏感軌跡tr泛化后的軌跡匿名率小于ε，則將該敏感軌跡中對應的簽到數據添加到敏感數據列表S中（第10）～14）行）。最后，算法SDD返回一個敏感數據列表S（第15）行）。

3.2 個性化時空數據隱私保護算法

算法PPPST的主要思想是根據用戶的隱私保護需求對每個敏感數據進行啟發式迭代泛化，直到滿足匿名需求，生成可發布的時空數據集合，且保證最低的信息損失。算法2 以用戶時空數據集合DST、用戶設置的敏感數據集合DS=｛SL，SC，STR｝、隱私保護閾值（p，q，ε）作為輸入，返回一個可發布的時空數據集DST′。

算法2 個性化時空數據隱私保護算法（PPPST）。

每一種泛化處理方法都傾向于增加隱私數據匿名性和降低信息損失，關鍵在于泛化處理的每一步都同時考慮這兩種影響，使泛化收益最大。所以，本文采用啟發式迭代泛化方法，對隱私數據進行處理。算法2 首先通過SDD 算法生成敏感數據列表S（第1）行）。然后，算法PPPST獲得一個Score值降序排列的候選泛化列表Q（第2）行）。其中，Score是一個啟發式函數，其值度量了泛化操作匿名性和信息損失的共同影響。Score值越高，泛化操作的匿名性越高，且信息損失越小。列表Q中所有的候選泛化數據通過位置泛化（Location Generalization，LG）算法計算得到。算法2 循環選擇Score值最大（在列表Q頂端）的候選泛化位置集合g加入到時空數據集DST中，直到敏感數據列表S為空，即隱私數據全部泛化完畢（第3）～5）行）。最后，算法返回一個符合個性化隱私保護要求的時空數據集合DST′（第6）行）。

3.3 泛化數據度量

對敏感時空數據進行泛化處理，實際上是對各類敏感數據中簽到數據（l，t）中的位置l進行泛化。用op=（li，g）表示一次數據泛化，其中g是一個泛化位置集合，g中的位置由泛化位置搜索（Generalized Location Search，GLS）算法搜索得到。用op=（li，-）表示抑制操作，是將因用泛化操作無法達到保護要求的位置數據進行刪除。

泛化操作的每一步都需考慮隱私保護的最大化和信息損失的最小化。本文通過位置多樣性（表示為Div（g，DST））和信息損失度（表示為InfoLoss（op））來衡量泛化處理的影響，為了最大化泛化處理的作用效果，本文設計了如式（3）所示的啟發式規則來度量泛化數據：

其中：位置多樣性Div（g，DST）取值越大，Score值越高，隱私保護效果越好，但會造成更多的信息損失；信息損失度InfoLoss（op）越低，Score值越高，數據可用性越高，但隱私不能得到很好的保護。對隱私數據進行泛化操作時，每一步操作都生成一個Score值，并將其降序排列，最終選擇Score值最大的位置匿名集合添加到時空數據集中。

位置多樣性Div（g，DST）的定義如式（4）所示，此式表示泛化處理后，時空數據集中有數量變化的簽到數據集數占總簽到數據集數的比例。

其中：div（g，DC）表示簽到數據集合DC在添加位置集g后的數據量變化，有變化為1，無變化為0。如圖1（c）所示，對用戶原始時空數據泛化處理完后的位置多樣性為Div(g，DST)=

信息損失度InfoLoss（op）的公式表示為InfoLoss(op)=H(DSTop)-H(DST)，其中H（DST）和H（DSTop）分別表示時空數據在泛化操作前后的熵值（由前文定義7給出）。

3.4 位置泛化算法

本文提出位置泛化算法LG，以生成按Score值降序排列的候選泛化時空數據列表Q。泛化過程受兩個條件約束，分別是時空可達性和用戶運動模式。

定義9時空可達性。用戶在兩個相鄰簽到位置間，以該用戶平均最大的位移速度vmax在某一時間段內是可達的，稱為時空可達性，由式（5）判斷：

其中：dist（li-1，li）表示tdi時刻的敏感位置li與td（i-1）時刻的簽到位置li-1之間在路網中的最短距離，vmax表示用戶時空數據中的平均最大位移速度。如果式（5）第1 行不等式不成立，用戶將不能在（tdi-td（i-1））時間內由泛化位置li-1到達敏感位置li。同理，很容易推導出式（5）第2 行不等式。當敏感位置li是起始位置時，只考慮式（5）第2行不等式；當敏感位置li是終點位置時，只考慮式（5）第1行不等式。

如圖2所示，簽到數據（l3，tdi）中的l3為敏感位置，（l2，td（i-1））是其前一時刻td（i-1）的簽到數據，（l6，td（i+1））是其后一時刻td（i+1）的簽到數據。根據式（5）計算判斷可得候選泛化區域Z。

圖2 候選泛化區域ZFig.2 Candidate generalized region Z

為了防止攻擊者識別出泛化位置，算法LG還必須保證泛化位置符合用戶的運動模式。因此設置閾值α，只有泛化位置出現的頻度大于α才被作為候選泛化位置。

如算法3 所示，輸入時空數據集DST，敏感數據列表S，隱私保護閾值（p，q，ε）；輸出一個Score值按降序排列的候選泛化時空數據列表Q。

算法3 位置泛化算法（LG）。

在算法3 中，對敏感數據列表S里每個敏感簽到數據cd中的敏感位置sl進行泛化操作op=（sl，g=｛l′｝）（第2）～10）行）。其中，候選區域Z是通過式（5）計算得來，針對敏感位置sl的候選泛化位置l均從泛化位置搜索算法生成的區域Z中選擇（第3）行），且候選泛化位置l要符合用戶運動模式約束條件，即l在時空數據集DST中出現的頻度不小于閾值α（第5）行）。然后，計算泛化操作op的Score值，并將泛化操作op、敏感位置sl對應的簽到時間tdi和Score值插入到列表Q中（第9）～10）行）。

算法3還要對生成的候選泛化位置集合g進行判斷，判斷其中的位置數是否滿足隱私保護閾值的要求，若敏感位置或敏感簽到數據泛化后的位置集合g中的位置數分別小于p或q，敏感軌跡泛化后的軌跡匿名率小于ε，則將相應的位置集合g中敏感位置進行抑制操作op=（sl，-）（第12）～13）行）。然后，計算抑制操作op的Score值，并將抑制操作op、敏感位置sl對應的簽到時間tdi和Score值插入到列表Q中（第14）～15）行）。最后，算法LG 返回一個Score值降序排列的列表Q（第16）行）。

3.5 泛化位置搜索算法

本文提出泛化位置搜索（GLS）算法，對生成泛化區域Z中的位置搜索進行優化。因生成泛化區域Z時采用寬度優先遍歷（Breadth First Search，BFS）搜索候選位置，每個敏感位置需要對路網進行兩次BFS，對于一個敏感位置集SL總共需要次BFS，會增加算法運行時間，本文提出Dist-Index數據結構來存儲候選泛化位置，以此節省算法運行時間。

定義10距離索引Dist-Index。給定一個敏感位置l，該位置與其他位置的距離索引Dist-Index 定義為一個列表，用l.D表示。列表中存儲的元素是搜索得到的候選位置l′和l與l′之間在路網中的距離，l.D中所有的元素按照位置間距離升序排列。

圖3（a）所示為道路網中各位置之間的距離矩陣，距離的單位為千米（km）。圖3（b）表示各位置間的距離索引。設l.D（d）表示與位置l距離dkm的一組位置，其中d是輸入的參數。例如，對于距離敏感位置l30.5 km 的區域搜索，結果為l3.D（0.5）=｛l1，l2，l5｝。

如算法4 所示，輸入時空數據集DST，敏感位置sl，輸出位置列表l.D。運用數據結構Dist-Index，算法以DST中的每個位置l作為起點，執行一次BFS就可以得到所有可達的位置及位置間的距離。

算法4 泛化位置搜索（GLS）算法。

輸入：時空數據集DST，敏感位置sl；

輸出：位置列表l.D。

算法4 首先以敏感位置sl為中心點，通過式（5）計算并判斷出用戶在最大移動速度下行駛的最大距離dmax（第2）～12）行）。然后，以敏感位置sl為起點在道路網中進行一次寬度優先遍歷，將搜索得到的候選位置和相應的距離插入以Dist-Index 為存儲結構的l.D中，直到搜索距離等于dmax時結束（第13）行）。最后，算法返回一個列表l.D。

圖3 距離矩陣和每個位置的Dist-IndexFig.3 Distance matrix and Dist-Index of different locations

3.6 算法復雜度分析

在本節中，將對算法的復雜度進行理論分析。設DST為時空數據集合，DS為敏感數據集合，SC為敏感數據集中的簽到數據集合，L為時空數據集中簽到位置集合，tr為敏感位置所在的軌跡。

在算法SDD 中，需要對|SC|個敏感位置進行判斷，所以，算法SDD 的時間復雜度為O（|SC|）。在算法GLS 中，需要對敏感位置sl所涉及到的時空數據集中的前后位置進行BFS 遍歷搜索，所以，算法GLS的時間復雜度為O（|tr|2）。在算法LG中，需要進行|SC|次泛化區域搜索，時間復雜度為O（|SC|·|tr|2），每個泛化操作計算Score值的時間復雜度為O（4·|SC|），最多耗時2|tr|·|SC|，所以算法LG 生成列表Q的時間復雜度為O（2|tr|·|SC|2·|tr|2）。對于算法PPPST，在每次迭代泛化中（第3）～5）行），分別需要O（|SC|）和O（4·|SC|·|Q|）的時間來更新列表S和Q，Q中最多包含|SC|·|L|·|tr|個元素，算法需要循環迭代|SC|·|L|·|tr|次，所以，算法PPPST的時間復雜度為O（2|tr|·|SC|3·|L|·|tr|3）。

4 實驗評估與分析

本章通過實驗測試對提出的個性化時空數據隱私保護算法進行性能分析和評價。用戶的時空數據來自斯坦福大學復雜網絡分析平臺公開的兩個真實數據集Gowalla和Brightkite，同時也利用了這兩個數據集所在California 州的道路網數據，包括21 047個節點和21 692條邊。本文從兩個數據集中分別隨機選取了5 000 個用戶在加州簽到的時空數據集，表1 展示了數據集的相關信息。

表1 實驗數據集的統計信息Tab.1 Statistics of experimental datasets

本文提出的個性化時空數據隱私保護算法PPPST，通過與個性化信息數據K-匿名算法（Information Data Used through Kanonymity，IDU-K）［14］和個性化Clique Cloak（Personalized Clique Cloak，PCC）算法［15］進行對比實驗來分析本文算法的性能。最后，通過實驗評估各算法對數據可用性的影響。

實驗環境如下。

1）計算機硬件配置：Intel Core i5 2.5 GHz，8 GB DRAM；

2）操作系統：Windows 10；

3）編程環境：Java語言，IDEA開發平臺。

實驗中，敏感數據集DS中簽到數據個數|SC|是用戶個性化設置的敏感位置、敏感簽到數據和敏感軌跡中的簽到數據數量之和，其取值范圍為［5，25］（默認為5）；隱私保護閾值p和q根據兩個真實時空數據集實驗總結所得，其取值范圍均為［2，6］（默認為2），軌跡匿名率閾值ε的取值范圍為［0.5，1］（默認為0.5）；用戶運動模式頻度閾值α由關聯規則挖掘算法根據實驗數據集統計所得，其默認值為2。

4.1 算法性能分析

圖4 展示了時空數據集DST的平均信息損失隨敏感時空數據集DS中簽到數據個數|SC|變化的情況。對于時空數據集DST，定義其平均信息損失為，其中Loss為定義7 中給出的時空數據集DST總共的信息損失為時空數據集中簽到數據的數量。

由圖可見，隨著|SC|的增加，信息損失越多，但本文提出的PPPST算法造成的信息損失遠低于IDU-K 和PCC 算法，平均低約82.53%。由于本文算法考慮了隱私分類保護，軌跡隱私中可能包含位置隱私和簽到數據隱私，采用啟發式泛化方法時，當敏感軌跡匿名率大于給定閾值后結束泛化操作，這在一定程度上會降低隱私過度保護造成的信息損失。

圖4 信息損失Fig.4 Information loss

圖5展示了三個算法的運行時間隨敏感簽到數據個數|SC|變化的情況。可以看出，隨|SC|的增加，運行時間也逐漸增加。本文算法PPPST運行時間始終比IDU-K 和PCC 算法運行時間高，平均多出29.36%的運行時間，因為本文算法采取了啟發式時空數據泛化方法，需要更多的時間計算泛化操作的Score值并更新泛化區域Z。但本文算法GLS（算法4）優化了泛化位置的搜索，在一定程度上節省了一半的位置搜索時間。

圖5 算法運行時間Fig.5 Algorithm running time

根據定義3 中給出的位置泄露率公式lri，時空數據集DST的平均位置泄露率可以定義為

圖6展示了平均位置泄露率AL隨敏感位置隱私保護閾值p的變化情況。可見，閾值p越高，時空數據的平均位置泄露率越低。因為隨著泛化位置的增加，每個敏感位置得到的混淆位置更多，位置泄露的概率就會降低。本文算法PPPST的平均位置泄露率比IDU-K 和PCC 算法平均低約6.54%，因IDUK 算法對未被泛化的位置信息進行舍棄，會使攻擊者通過關聯規則攻擊技術更容易判斷出發布軌跡與原始軌跡的差別，使得平均位置泄露率遠高于本文算法；而PCC 算法采用自適應敏感分級的方法對敏感數據進行保護，對于敏感級別較低的屬性，該算法不予以保護，所以平均位置泄露率高于本文保護算法。

圖6 平均位置泄露率Fig.6 Average location leakage rate

圖7 為平均簽到數據泄露率AC=隨敏感簽到數據隱私保護閾值q的變化情況。可見，閾值q越高，平均簽到數據泄露率越低。因本文算法PPPST考慮了用戶設置的簽到數據隱私，即同一位置不同時刻的隱私保護需求。而算法IDU-K 和PCC 僅考慮保護軌跡隱私或者位置隱私，沒有根據用戶的實際隱私保護需求對敏感簽到數據進行保護，導致其平均簽到數據泄露率遠高于本文算法，平均高約88.2%。

圖7 平均簽到數據泄露率Fig.7 Average check-in data leakage rate

圖8展示了平均軌跡泄露率ATR=其中，TA為定義4 給出的軌跡匿名率（隨軌跡匿名率閾值ε的變化情況）。由圖可見，閾值ε越高，平均軌跡泄露率越低。本文算法PPPST采用啟發式泛化方法，當敏感軌跡匿名率大于匿名閾值ε后，終止對敏感軌跡的泛化操作，使敏感軌跡得到保護的同時，其信息損失最低。算法IDU-K 對敏感軌跡中的所有簽到位置進行匿名操作，其軌跡匿名率最高，平均軌跡泄露率最低，比本文算法平均低約19.8%。算法PCC 只對敏感位置進行個性化保護，導致敏感位置所在的軌跡泄露概率最高，比本文算法平均高約65.3%。

圖8 平均軌跡泄露率Fig.8 Average trajectory leakage rate

4.2 數據可用性分析

本文評估了發布的時空數據在頻繁模式挖掘中的性能，圖9展示了數據可用率隨敏感位置數|SC|變化的情況。頻繁模式置信度閾值設置為10%，時空數據泛化前挖掘出的頻繁模式（大于10%）定義為P，泛化后的頻繁模式定義為POP，則數據可用率可以定義為DR=

圖9 數據可用率Fig.9 Data availability rate

由圖可見，隨著|SC|的增加，需要在用戶原始數據集中添加更多的泛化位置來保護隱私數據，使得DR逐漸降低。因IDU-K 算法對未被聚類的位置進行舍棄，造成大量信息損失，所以其DR值最低；本文算法中考慮了用戶的時空可達性和運動模式的限制，使得泛化位置更接近于敏感位置，所以本文算法PPPST的平均數據可用率分別比PCC 和IDU-K 算法高約4.66%和15.45%。

5 結語

本文首次提出面向時空數據的個性化隱私保護模型，并基于該模型提出一種個性化時空數據隱私保護算法PPPST。該算法采用啟發式規則來選擇候選泛化數據，并對泛化位置搜索進行了優化。PPPST算法可以對用戶個性化設置的時空數據隱私進行保護，同時實現了數據的高可用性。基于真實時空數據集進行實驗測試和分析，實驗結果表明PPPST算法能有效地保護個性化時空數據隱私。由于本文采用歐氏距離的方式計算簽到位置間的距離，這與用戶真實的移動軌跡存在差異，怎樣將真實路網添加到時空數據隱私保護中，將是下一步的研究方向。