（沈陽航空航天大學(xué)計(jì)算機(jī)學(xué)院，沈陽 110136）

0 引言

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

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

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

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

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

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

本文研究內(nèi)容主要面臨3個(gè)挑戰(zhàn)，如下所述：

1）針對用戶分類設(shè)置的隱私數(shù)據(jù)，如何實(shí)現(xiàn)個(gè)性化隱私保護(hù)具有挑戰(zhàn)性。以往的研究中，對位置隱私和軌跡隱私單獨(dú)進(jìn)行保護(hù)，而且沒有考慮針對簽到數(shù)據(jù)的隱私保護(hù)。如何實(shí)現(xiàn)3 種隱私數(shù)據(jù)的綜合保護(hù)，且不造成隱私過度保護(hù)是研究的難點(diǎn)。

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

3）候選泛化位置的選取具有挑戰(zhàn)性。如果將簽到數(shù)據(jù)（l，t）中的位置l泛化到位置集合g=｛l，l′｝，假設(shè)簽到數(shù)據(jù)（l，t）的前驅(qū)和后繼簽到數(shù)據(jù)分別為（lp，tp）和（ls，ts），那么，位置集合g中的泛化位置l′需要滿足以下約束條件：1）泛化位置l′∈g應(yīng)滿足lp和ls之間的時(shí)空可達(dá)性。以lp為例，用戶能在從lp到l的時(shí)間（t-tp）內(nèi)由lp到達(dá)l′，即滿足時(shí)空可達(dá)性；2）泛化位置l′應(yīng)符合用戶的運(yùn)動(dòng)模式，否則泛化位置l′容易被攻擊者識別為假位置；3）因?yàn)榈缆肪W(wǎng)中的位置數(shù)量巨大，如何有效地選擇滿足上述約束條件的泛化位置是研究的難點(diǎn)，而且是個(gè)性化隱私保護(hù)算法高效實(shí)用的關(guān)鍵。

本文主要貢獻(xiàn)包括：1）定義了時(shí)空數(shù)據(jù)發(fā)布中保護(hù)用戶個(gè)性化設(shè)置的隱私數(shù)據(jù)的問題；2）提出了一種個(gè)性化時(shí)空數(shù)據(jù)隱私保護(hù)算法保護(hù)用戶數(shù)據(jù)隱私；3）優(yōu)化了候選泛化位置搜索技術(shù)，提高算法執(zhí)行效率；4）經(jīng)過大量基于真實(shí)時(shí)空數(shù)據(jù)的實(shí)驗(yàn)，證明本文算法能有效地保護(hù)用戶隱私，同時(shí)保持已發(fā)布時(shí)空數(shù)據(jù)的高可用性。

1 相關(guān)工作

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

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

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

現(xiàn)有的個(gè)性化隱私保護(hù)方法沒有對隱私數(shù)據(jù)進(jìn)行分類，用戶不能設(shè)置自己的隱私數(shù)據(jù)，不能達(dá)到真正的個(gè)性化隱私保護(hù)要求。本文針對此問題，提出了個(gè)性化時(shí)空數(shù)據(jù)隱私保護(hù)方法。

2 預(yù)備知識與問題定義

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

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

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

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

定義3位置泄露率lri。給定用戶時(shí)空數(shù)據(jù)集DST，每個(gè)簽到數(shù)據(jù)中時(shí)刻tdm對應(yīng)的位置集為gi，在此時(shí)刻泄露用戶真實(shí)位置的概率為

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

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

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

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

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

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

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

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

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

以上任意一條成立，則稱為時(shí)空數(shù)據(jù)隱私泄露。

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

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

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

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

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

圖1（c）中的時(shí)空數(shù)據(jù)集滿足（4，3，0.5）-匿名。

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

3 個(gè)性化時(shí)空數(shù)據(jù)隱私保護(hù)

在本章中，提出個(gè)性化時(shí)空數(shù)據(jù)隱私保護(hù)（Personalized Privacy Protection for Spatio-temporal Data，PPPST）算法，對用戶個(gè)性化設(shè)置的隱私數(shù)據(jù)進(jìn)行保護(hù)，設(shè)計(jì)了啟發(fā)式規(guī)則度量泛化操作，并優(yōu)化了候選泛化位置搜索方法。

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

3.1 敏感數(shù)據(jù)判定算法

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

算法1 敏感數(shù)據(jù)判定算法（SDD）。

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

3.2 個(gè)性化時(shí)空數(shù)據(jù)隱私保護(hù)算法

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

算法2 個(gè)性化時(shí)空數(shù)據(jù)隱私保護(hù)算法（PPPST）。

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

3.3 泛化數(shù)據(jù)度量

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

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

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

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

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

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

3.4 位置泛化算法

本文提出位置泛化算法LG，以生成按Score值降序排列的候選泛化時(shí)空數(shù)據(jù)列表Q。泛化過程受兩個(gè)條件約束，分別是時(shí)空可達(dá)性和用戶運(yùn)動(dòng)模式。

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

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

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

圖2 候選泛化區(qū)域ZFig.2 Candidate generalized region Z

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

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

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

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

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

3.5 泛化位置搜索算法

本文提出泛化位置搜索（GLS）算法，對生成泛化區(qū)域Z中的位置搜索進(jìn)行優(yōu)化。因生成泛化區(qū)域Z時(shí)采用寬度優(yōu)先遍歷（Breadth First Search，BFS）搜索候選位置，每個(gè)敏感位置需要對路網(wǎng)進(jìn)行兩次BFS，對于一個(gè)敏感位置集SL總共需要次BFS，會(huì)增加算法運(yùn)行時(shí)間，本文提出Dist-Index數(shù)據(jù)結(jié)構(gòu)來存儲候選泛化位置，以此節(jié)省算法運(yùn)行時(shí)間。

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

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

如算法4 所示，輸入時(shí)空數(shù)據(jù)集DST，敏感位置sl，輸出位置列表l.D。運(yùn)用數(shù)據(jù)結(jié)構(gòu)Dist-Index，算法以DST中的每個(gè)位置l作為起點(diǎn)，執(zhí)行一次BFS就可以得到所有可達(dá)的位置及位置間的距離。

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

輸入：時(shí)空數(shù)據(jù)集DST，敏感位置sl；

輸出：位置列表l.D。

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

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

3.6 算法復(fù)雜度分析

在本節(jié)中，將對算法的復(fù)雜度進(jìn)行理論分析。設(shè)DST為時(shí)空數(shù)據(jù)集合，DS為敏感數(shù)據(jù)集合，SC為敏感數(shù)據(jù)集中的簽到數(shù)據(jù)集合，L為時(shí)空數(shù)據(jù)集中簽到位置集合，tr為敏感位置所在的軌跡。

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

4 實(shí)驗(yàn)評估與分析

本章通過實(shí)驗(yàn)測試對提出的個(gè)性化時(shí)空數(shù)據(jù)隱私保護(hù)算法進(jìn)行性能分析和評價(jià)。用戶的時(shí)空數(shù)據(jù)來自斯坦福大學(xué)復(fù)雜網(wǎng)絡(luò)分析平臺公開的兩個(gè)真實(shí)數(shù)據(jù)集Gowalla和Brightkite，同時(shí)也利用了這兩個(gè)數(shù)據(jù)集所在California 州的道路網(wǎng)數(shù)據(jù)，包括21 047個(gè)節(jié)點(diǎn)和21 692條邊。本文從兩個(gè)數(shù)據(jù)集中分別隨機(jī)選取了5 000 個(gè)用戶在加州簽到的時(shí)空數(shù)據(jù)集，表1 展示了數(shù)據(jù)集的相關(guān)信息。

表1 實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)信息Tab.1 Statistics of experimental datasets

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

實(shí)驗(yàn)環(huán)境如下。

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

2）操作系統(tǒng)：Windows 10；

3）編程環(huán)境：Java語言，IDEA開發(fā)平臺。

實(shí)驗(yàn)中，敏感數(shù)據(jù)集DS中簽到數(shù)據(jù)個(gè)數(shù)|SC|是用戶個(gè)性化設(shè)置的敏感位置、敏感簽到數(shù)據(jù)和敏感軌跡中的簽到數(shù)據(jù)數(shù)量之和，其取值范圍為［5，25］（默認(rèn)為5）；隱私保護(hù)閾值p和q根據(jù)兩個(gè)真實(shí)時(shí)空數(shù)據(jù)集實(shí)驗(yàn)總結(jié)所得，其取值范圍均為［2，6］（默認(rèn)為2），軌跡匿名率閾值ε的取值范圍為［0.5，1］（默認(rèn)為0.5）；用戶運(yùn)動(dòng)模式頻度閾值α由關(guān)聯(lián)規(guī)則挖掘算法根據(jù)實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)所得，其默認(rèn)值為2。

4.1 算法性能分析

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

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

圖4 信息損失Fig.4 Information loss

圖5展示了三個(gè)算法的運(yùn)行時(shí)間隨敏感簽到數(shù)據(jù)個(gè)數(shù)|SC|變化的情況?？梢钥闯?，隨|SC|的增加，運(yùn)行時(shí)間也逐漸增加。本文算法PPPST運(yùn)行時(shí)間始終比IDU-K 和PCC 算法運(yùn)行時(shí)間高，平均多出29.36%的運(yùn)行時(shí)間，因?yàn)楸疚乃惴ú扇×藛l(fā)式時(shí)空數(shù)據(jù)泛化方法，需要更多的時(shí)間計(jì)算泛化操作的Score值并更新泛化區(qū)域Z。但本文算法GLS（算法4）優(yōu)化了泛化位置的搜索，在一定程度上節(jié)省了一半的位置搜索時(shí)間。

圖5 算法運(yùn)行時(shí)間Fig.5 Algorithm running time

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

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

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

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

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

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

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

4.2 數(shù)據(jù)可用性分析

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

圖9 數(shù)據(jù)可用率Fig.9 Data availability rate

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

5 結(jié)語

本文首次提出面向時(shí)空數(shù)據(jù)的個(gè)性化隱私保護(hù)模型，并基于該模型提出一種個(gè)性化時(shí)空數(shù)據(jù)隱私保護(hù)算法PPPST。該算法采用啟發(fā)式規(guī)則來選擇候選泛化數(shù)據(jù)，并對泛化位置搜索進(jìn)行了優(yōu)化。PPPST算法可以對用戶個(gè)性化設(shè)置的時(shí)空數(shù)據(jù)隱私進(jìn)行保護(hù)，同時(shí)實(shí)現(xiàn)了數(shù)據(jù)的高可用性?；谡鎸?shí)時(shí)空數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測試和分析，實(shí)驗(yàn)結(jié)果表明PPPST算法能有效地保護(hù)個(gè)性化時(shí)空數(shù)據(jù)隱私。由于本文采用歐氏距離的方式計(jì)算簽到位置間的距離，這與用戶真實(shí)的移動(dòng)軌跡存在差異，怎樣將真實(shí)路網(wǎng)添加到時(shí)空數(shù)據(jù)隱私保護(hù)中，將是下一步的研究方向。