王 輝,陳 宇,申自浩,劉沛騫

(1.河南理工大學(xué)軟件學(xué)院,河南 焦作 454000;2.河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

1 引言

隨著定位設(shè)備的增多,移動(dòng)定位設(shè)備產(chǎn)生軌跡數(shù)據(jù)的速度以指數(shù)級增長。移動(dòng)設(shè)備硬件的快速發(fā)展使得利用GPS獲取用戶的信息變得異常容易,只要用戶授權(quán),用戶的位置信息就可被運(yùn)營商服務(wù)器隨時(shí)隨地地獲取[1-3]。軌跡數(shù)據(jù)是一種規(guī)模大、變化快、用戶普遍關(guān)注的位置信息,主要來源于車輛網(wǎng)絡(luò)、移動(dòng)設(shè)備、社交網(wǎng)絡(luò)等[4]?，F(xiàn)在軌跡數(shù)據(jù)的許多應(yīng)用方便了人們的日常生活,因此軌跡數(shù)據(jù)服務(wù)被稱為一種新的移動(dòng)計(jì)算服務(wù)[5]。然而,大量用戶的軌跡數(shù)據(jù)被收集和存儲,且對軌跡數(shù)據(jù)進(jìn)行分析處理,對用戶的隱私安全來說是一種不可見的隱患。根據(jù)用戶的軌跡可以推斷出用戶的敏感信息,如個(gè)人愛好、家庭住址等。當(dāng)從軌跡中提取出具有高度價(jià)值的信息點(diǎn)時(shí),用戶的數(shù)據(jù)隱私已經(jīng)不具有安全性。若不做好軌跡隱私保護(hù)措施就肆意發(fā)布給研究人員進(jìn)行分析挖掘,用戶的私密信息甚至人身安全無疑將受到嚴(yán)重的威脅[6],所以對于軌跡隱私的保護(hù)一直都是非常必要的研究。

2006年由微軟研究院的科學(xué)家Dwork提出的差分隱私保護(hù)技術(shù)是隱私保護(hù)研究中常用的技術(shù)。作為一種可嚴(yán)格證明的隱私保護(hù)模型,差分隱私保護(hù)技術(shù)嚴(yán)格定義了隱私保護(hù)的強(qiáng)度,任意一條記錄的添加或刪除都不會影響最終的查詢結(jié)果。同時(shí),該技術(shù)定義了極為嚴(yán)格的攻擊模型,不關(guān)心攻擊者的背景知識,即使攻擊者掌握了除原數(shù)據(jù)外的任何輔助信息,差分隱私仍能將原數(shù)據(jù)的隱私泄漏風(fēng)險(xiǎn)控制在一個(gè)可接受的范圍[7]。隱私預(yù)算分配是決定數(shù)據(jù)隱私是否安全的一個(gè)重要因素。吳萬青等人[8]提出一種等差隱私預(yù)算分配算法,在樹形存儲結(jié)構(gòu)不同的高度為數(shù)據(jù)分配不同大小的隱私預(yù)算,能有效保證數(shù)據(jù)可用性,但不適用于多種樹形結(jié)構(gòu),無法保證隱私預(yù)算在其他樹形結(jié)構(gòu)中的合理分配。傅繼彬等人[9]提出了一種高效的分層細(xì)化方法MAXGDDP(MAXimum Geometric Distribution Differential Privacy),對原始分類數(shù)據(jù)進(jìn)行分層細(xì)化,在同一層次的概念細(xì)化中提出了最大值屬性索引算法,在不同層次之間利用類幾何分配機(jī)制來更加合理地分配隱私預(yù)算。Yuan等人[10]提出了一種平均隱私預(yù)算分配方法,使用約束一致性規(guī)定隱私的分配,在不同層高分配相同的預(yù)算對抗具有信息背景知識的攻擊,但隱私預(yù)算分配不夠合理,不能有效提高利用率。徐川等人[4]提出了一種基于差分隱私的個(gè)性化位置隱私保護(hù)方案,在保護(hù)用戶隱私的前提下,滿足用戶個(gè)性化隱私需求。該方案通過定義歸一化的決策矩陣,描述導(dǎo)航推薦路線的效率和隱私效果;引入多屬性理論,建立效用模型,將用戶的隱私偏好整合到該模型中,為用戶選擇效益最佳的駕駛路線;根據(jù)用戶的隱私偏好需求,以距離占比為衡量指標(biāo),為用戶分配合適的隱私預(yù)算。Zhao等人[11]提出了一種基于前綴樹的差分隱私軌跡數(shù)據(jù)保護(hù)方法。該方法首先提出了軌跡段前綴樹的概念,然后基于MDL(Minimum Description Length)原理提出了PMDL(Point Minimum Description Length)方法,以降低數(shù)據(jù)處理的時(shí)間和空間復(fù)雜度;然后,利用Dijkstra算法尋找最佳軌跡分割,利用差分隱私方法對軌跡段進(jìn)行保護(hù);最后,采用馬爾可夫鏈限制噪聲量,從而保證用戶的隱私信息和數(shù)據(jù)可用性。

計(jì)算軌跡之間相似度的方法在近些年不斷更迭。Yu等人[12]提出了一種增強(qiáng)的軌跡模型,并提出了一種基于多特征軌跡相似度度量的軌跡聚類算法,可以最大化同一聚類中的軌跡相似度,更好地服務(wù)于交通監(jiān)控、道路擁堵等應(yīng)用。Yao等人[13]提出 NeuTraj(Neural Trajectory)來加速軌跡相似度計(jì)算。NeuTraj可以適應(yīng)任何現(xiàn)有的軌跡測量,并且可以快速計(jì)算給定軌跡對在線性時(shí)間內(nèi)的相似性。此外,NeuTraj具有彈性,可以與所有基于空間的軌跡索引方法協(xié)作,以縮小搜索空間。Liang等人[14]提出了一種無監(jiān)督的學(xué)習(xí)方法。該方法通過卷積自編譯器CAE(Convolutional Auto-Encoder)自動(dòng)提取低維特征,在保持時(shí)空特性的同時(shí),首先將原始船只軌跡重新映射為二維矩陣生成信息豐富的軌跡圖像,然后基于采集到的大量船舶軌跡,CAE無監(jiān)督地學(xué)習(xí)信息軌跡圖像的低維表示,軌跡相似度最終等價(jià)于低維特征之間的相似度,這些特征與原始船只軌跡具有很強(qiáng)的相關(guān)性。Li等人[15]首次提出了把深度學(xué)習(xí)模型用于軌跡相似度度量的方法,該方法對低質(zhì)量數(shù)據(jù)具有魯棒性,能夠支持準(zhǔn)確和高效的軌跡相似度計(jì)算和搜索。Liu等人[16]提出了考慮軌跡差異的深度學(xué)習(xí)模型,新的對比模型區(qū)分了軌跡之間的軌跡級和點(diǎn)級差異來學(xué)習(xí)軌跡表示,有效提高軌跡相似度度量的科學(xué)性。

上述方法在軌跡數(shù)據(jù)的存儲方面還存在存儲結(jié)構(gòu)檢索效率不高的問題;當(dāng)軌跡數(shù)據(jù)量比較大時(shí),會出現(xiàn)無法高效計(jì)算與比對的問題。為此,本文提出一種結(jié)合對比監(jiān)督模型和排序樹的軌跡數(shù)據(jù)差分隱私保護(hù)方案SDTS(Supervised Differential Trajectory Sort),用于軌跡數(shù)據(jù)的存儲與發(fā)布;通過監(jiān)督學(xué)習(xí)模型來保障軌跡數(shù)據(jù)的充足有效;利用損失函數(shù)計(jì)算軌跡之間的軌跡相似度,根據(jù)軌跡之間的相似性將軌跡存儲到基于二叉排序樹的排序樹中對應(yīng)的節(jié)點(diǎn)中;利用差分隱私技術(shù)對其節(jié)點(diǎn)存儲的敏感數(shù)據(jù)添加噪聲。本文工作主要包括以下3個(gè)方面:

(1)為了提高軌跡查詢效率,提出一種基于二叉排序樹的存儲樹形結(jié)構(gòu),以提高查詢速率。通過比較軌跡之間的相似性計(jì)算結(jié)果,把用戶軌跡信息存儲到所對應(yīng)的節(jié)點(diǎn)。

(2)為保證軌跡相似度計(jì)算的精確度,將對比監(jiān)督學(xué)習(xí)模型加入到軌跡存儲的方案中,有效保障結(jié)果的科學(xué)性。

(3)采用等比隱私預(yù)算分配的方式為節(jié)點(diǎn)中的敏感數(shù)據(jù)添加噪聲,通過閾值判斷隱私預(yù)算分配的合理性,保障數(shù)據(jù)的可用性。

2 預(yù)備知識

定義1(軌跡) 軌跡是移動(dòng)用戶在時(shí)空里按照順序,通過一系列連續(xù)位置點(diǎn)組成的集合T=P1→P2→…→Pn,其中n為軌跡中位置點(diǎn)的個(gè)數(shù),Pi是二維空間點(diǎn)坐標(biāo)(xi,yi)。

定義2(軌跡數(shù)據(jù)集) 軌跡數(shù)據(jù)集由多個(gè)軌跡數(shù)據(jù)組成D={T1,T2,T3,…,Tm}。其中m代表軌跡數(shù)據(jù)集中的軌跡總數(shù),Ti表示數(shù)據(jù)庫中第i個(gè)軌跡數(shù)據(jù)對應(yīng)的軌跡信息。

定義3(原軌跡) 預(yù)先對軌跡進(jìn)行分類處理,規(guī)定出現(xiàn)重要軌跡點(diǎn)最多的軌跡是原軌跡。

定義4(全局敏感度) 對于2個(gè)數(shù)據(jù)集D1和D2,給出任意的查詢函數(shù)f:D→Rd,則全局敏感度如式(1)所示:

Δf=maxD1,D2‖f(D1)-f(D2)‖1

(1)

其中,‖·‖1是一階范數(shù)距離,即曼哈頓距離。

(2)

其中,Pr[f(D)=S]表示數(shù)據(jù)集D通過函數(shù)f輸出的值等于S的概率,S表示函數(shù)f輸出的所有可能。

定義7(并行組合性[18]) 假設(shè)Di(1≤i≤n)是原始數(shù)據(jù)集D中彼此不相交的子集,對每個(gè)子集Di作用一個(gè)差分隱私函數(shù)fi,其隱私預(yù)算為εi,函數(shù)組合F(f1(D1),f2(D2),…,fn(Dn))提供(maxεi)-差分隱私保護(hù)。則稱函數(shù)fi在D上的并行組合滿足(maxεi)-差分隱私。

定義8(信息推理攻擊模型[19]) 攻擊者利用出行目的、出行方式等背景知識,從移動(dòng)用戶的非軌跡位置信息中,直接或間接地推斷出用戶的出行軌跡、家庭地址等敏感信息的模型。

3 軌跡相似度計(jì)算

3.1 預(yù)訓(xùn)練軌跡編碼

編碼器-解碼器模型是當(dāng)前研究中常用的軌跡表示模型,但是該模型在重建時(shí)會忽略軌跡之間的點(diǎn)級差異,造成排序任務(wù)的準(zhǔn)確度降低。加入一種對比模型,通過區(qū)分軌跡之間軌跡級和點(diǎn)級差異來訓(xùn)練學(xué)習(xí)軌跡表示,并保證非均勻采樣率和數(shù)據(jù)噪聲的魯棒性。在訓(xùn)練軌跡數(shù)據(jù)不足的情況下,使用一種自監(jiān)督方法來增加訓(xùn)練軌跡對[16]。

對比模型如圖1所示。通過和一個(gè)對比目標(biāo)比較來區(qū)分軌跡級和點(diǎn)級的差異,以學(xué)習(xí)軌跡表示。

Figure 1 Contrast model

給定1條原軌跡和2條候選軌跡,通過識別其差異來選擇相似的軌跡。為了保證模型對非均勻采樣率和數(shù)據(jù)噪聲的魯棒性,將點(diǎn)級差異限制在一個(gè)較小的范圍內(nèi)。

本文模型分為2個(gè)部分:編碼器和對比損失函數(shù)。編碼器使一條軌跡T變成一個(gè)表示向量f(T),對比損失函數(shù)通過比較原軌跡和候選軌跡的相似性來訓(xùn)練編碼器,然后選擇相似的軌跡。

編碼器總體結(jié)構(gòu)如圖2所示。嵌入層的作用是將每個(gè)定位點(diǎn)轉(zhuǎn)換為相對固定的輸入嵌入。具體來說,對于給定的標(biāo)記,其輸入嵌入是通過將相應(yīng)的標(biāo)記嵌入和位置編碼相加來構(gòu)造的。標(biāo)記嵌入是一個(gè)可學(xué)習(xí)的向量,位置編碼包含了標(biāo)記在軌跡中的位置信息。

Figure 2 Encoder

為了獲得固定長度的軌跡表示,本文向上下文向量添加一個(gè)池化層。本文采用了2種池化策略:(1)CLS(CLaSsification):利用CLS的上下文令牌;(2)MEAN:使用所有上下文令牌的均值。默認(rèn)使用的策略是MEAN。

為了捕獲軌跡的上下文信息,采用掩模軌跡模型對編碼器進(jìn)行預(yù)訓(xùn)練。該模型隨機(jī)地屏蔽了軌跡上的一些定位點(diǎn),其目標(biāo)是根據(jù)其上下文對掩蔽點(diǎn)進(jìn)行預(yù)測。本文使用了一批包含50%原始軌跡和50%噪聲軌跡的預(yù)訓(xùn)練數(shù)據(jù),在每個(gè)軌跡中隨機(jī)屏蔽15%的標(biāo)記。

3.2 自我監(jiān)督數(shù)據(jù)增加

本文使用了一種自監(jiān)督的方法來生成包含軌跡級和點(diǎn)級特征的軌跡對。

首先,使用下采樣機(jī)制來生成包含軌跡級差異的軌跡對。給定原軌跡T,通過降低一些定位點(diǎn)的比率生成正軌跡T2。然后隨機(jī)選擇另一個(gè)軌跡Q作為它的負(fù)軌跡。正軌跡與原軌跡具有相同的軌跡級特征。經(jīng)過訓(xùn)練后選擇正軌跡時(shí),可以識別2個(gè)候選軌跡之間的軌跡級差異,并獲得軌跡級特征。接下來,使用下采樣機(jī)制來增加具有點(diǎn)級差異的軌跡對。正軌跡T1和負(fù)軌跡T2通過丟棄相同的點(diǎn)生成,正軌跡相比負(fù)軌跡具有更低的丟棄率。這2種增量軌跡具有相同的軌跡級特征,但負(fù)軌跡的采樣點(diǎn)較少,噪聲較大。自監(jiān)督方法通過區(qū)分差異來學(xué)習(xí)T1和T2之間的點(diǎn)級特征。

3.3 對比損失函數(shù)

設(shè)gap1和gap2分別表示軌跡級差和點(diǎn)級差,其計(jì)算方法分別如式(3)和式(4)所示:

gap1=sim(T,T2)-sim(T,Q)

(3)

gap2=sim(T,T1)-sim(T,T2)

(4)

sim(Ti,Tj)=cos(f(Ti),f(Tj))=

(5)

為了更好地區(qū)分軌跡級和點(diǎn)級的差異,應(yīng)當(dāng)最大化gap1和gap2。使用一個(gè)損耗函數(shù),并設(shè)定gap1和gap2的下限為ε1和ε2。此外,為了提高模型對非均勻采樣率和數(shù)據(jù)噪聲的魯棒性,gap2不能太大。限制gap2的最大值為ε3,如式(6)所示:

L=max(ε1-gap1,0)+max(ε2-gap2,0)+

max(-ε3+gap2,0)

(6)

gap1和gap2對模型性能有至關(guān)重要的作用。一個(gè)較小的gap1會導(dǎo)致監(jiān)督學(xué)習(xí)模型無法獲取軌跡級特征,一個(gè)較大的gap1會增加模型訓(xùn)練的難度。一個(gè)較小的gap2能限制數(shù)據(jù)噪聲的影響,因此可以高效率地表示帶有魯棒性任務(wù)的數(shù)據(jù)噪聲。然而,在處理排序任務(wù)過程中,一個(gè)較小的gap2又會增加軌跡排列錯(cuò)誤的概率。

4 軌跡數(shù)據(jù)保護(hù)

4.1 軌跡排序樹

二叉排序樹在中序遍歷中可以得到一個(gè)有序序列。構(gòu)造二叉排序樹的過程即是對無序序列進(jìn)行排序的過程。在軌跡存儲中,單一的排序樹節(jié)點(diǎn)存儲沒有現(xiàn)實(shí)意義,軌跡是對空間位置點(diǎn)采樣得來的序列,既具有空間特征,又具有時(shí)間特征。結(jié)合軌跡的時(shí)空性和二叉排序樹的特點(diǎn),本文提出了一種基于二叉排序樹的軌跡排序樹結(jié)構(gòu)。該結(jié)構(gòu)既保證了軌跡的時(shí)空完整性,又可以對軌跡進(jìn)行快速查詢。為了保證軌跡的時(shí)空特征,軌跡點(diǎn)序列存儲在具有時(shí)空特征的軌跡相似樹節(jié)點(diǎn)中。

下面給出構(gòu)建軌跡排序樹的步驟:

步驟1數(shù)據(jù)初始化。結(jié)合實(shí)際情況,將相同移動(dòng)用戶的軌跡數(shù)據(jù)分在同一組,并計(jì)算具有相同軌跡的移動(dòng)用戶數(shù)據(jù),一個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為{N(p),T(p),C(p),S(p)},其中p表示軌跡,N(p)為軌跡相似度,T(p)為軌跡點(diǎn)序列,C(p)為相應(yīng)軌跡點(diǎn)序列上的所有移動(dòng)用戶數(shù)量,S(p)為敏感信息。

步驟2節(jié)點(diǎn)選取。新的軌跡點(diǎn)序列插入時(shí),從根節(jié)點(diǎn)開始向下遍歷,比較相似度大小。若軌跡相似度大于根節(jié)點(diǎn)相似度,插入根節(jié)點(diǎn)的右節(jié)點(diǎn)中;若軌跡相似度小于根節(jié)點(diǎn)相似度,則插入根節(jié)點(diǎn)的左節(jié)點(diǎn)中;若軌跡相似度相同,軌跡點(diǎn)序列和相應(yīng)軌跡點(diǎn)序列用戶數(shù)量和其他信息并入根節(jié)點(diǎn)。

步驟3更新父節(jié)點(diǎn)。在排序樹中,插入新的軌跡點(diǎn)序列數(shù)據(jù)時(shí),需要更新父節(jié)點(diǎn)的索引記錄。根據(jù)軌跡相似度數(shù)值在排序樹中找到節(jié)點(diǎn)的添加位置,并更新父節(jié)點(diǎn)的用戶計(jì)數(shù)值。

步驟4加噪處理。經(jīng)過前面步驟的處理后,需要保護(hù)節(jié)點(diǎn)中存儲的數(shù)據(jù)信息,用于抵抗攻擊者的攻擊。本文采用差分隱私技術(shù)對節(jié)點(diǎn)信息中的計(jì)數(shù)進(jìn)行保護(hù),對隱私預(yù)算分配采用等比分配方式。

圖3給出了一個(gè)軌跡排序樹的示例。

Figure 3 Sorting tree

排序樹的節(jié)點(diǎn)存儲軌跡的相似度值、軌跡點(diǎn)序列、所有移動(dòng)用戶數(shù)量、背景知識和上下文的敏感信息。以根節(jié)點(diǎn)T1為例,60表示與目標(biāo)軌跡的相似度值,3表示移動(dòng)用戶的數(shù)量,S1表示背景知識和上下文敏感信息。

假設(shè)添加的軌跡點(diǎn)序列T6的相似度為70,在排序樹中插入節(jié)點(diǎn)后如圖4所示。

Figure 4 Sorting tree after adding the new node

添加新軌跡節(jié)點(diǎn),首先要計(jì)算軌跡相似度;然后,根據(jù)計(jì)算的相似度結(jié)果添加到相對應(yīng)的節(jié)點(diǎn)位置。從根節(jié)點(diǎn)依次往下比較相似度值。從圖4可以看出,新節(jié)點(diǎn)添加到了T3的左子樹上。同理,假設(shè)添加的軌跡點(diǎn)序列T7的相似度為30,新節(jié)點(diǎn)會添加在T4的左子樹上。但是,此時(shí)排序樹是不平衡二叉樹,查詢效率不高。為了提升查詢效率,對排序樹進(jìn)行了優(yōu)化處理,如圖5所示。

Figure 5 Balanced sorting tree

通過右旋轉(zhuǎn)使排序樹變成一棵平衡二叉樹,解決了不平衡樹結(jié)構(gòu)造成的查詢效率低的問題。同理,右子樹造成的排序樹不平衡問題也可以采用相對應(yīng)的旋轉(zhuǎn)方法解決。

4.2 差分隱私保護(hù)方案

改進(jìn)后的排序樹保存了移動(dòng)用戶的空間位置信息。一系列連續(xù)的位置點(diǎn)構(gòu)成一條軌跡序列,位置點(diǎn)具有順序特征?？梢?軌跡具有時(shí)空性,即空間位置和時(shí)間特征。大多數(shù)軌跡隱私保護(hù)不關(guān)注軌跡時(shí)間特征。但是,在軌跡的相似性計(jì)算比較中,軌跡的時(shí)間特性具有提高軌跡相似度計(jì)算準(zhǔn)確性的作用。本文基于二叉排序樹提出了一種改進(jìn)的軌跡排序樹,在保證軌跡時(shí)空特征的同時(shí),能夠有效地提高軌跡的檢索效率,降低復(fù)雜度。

通過二叉樹規(guī)則完成軌跡樹的排序,使其中序遍歷是一組從小到大的順序排列的軌跡相似度值,最底層的節(jié)點(diǎn)中的軌跡分別代表最相異原軌跡和最相似原軌跡的軌跡,2種計(jì)算結(jié)果具有同等重要性。

對于給定的軌跡排序樹,規(guī)定以下限制約束:

(1)對于排序樹中的任意一個(gè)節(jié)點(diǎn),如果該節(jié)點(diǎn)不是根節(jié)點(diǎn)或父節(jié)點(diǎn),那么該節(jié)點(diǎn)上的移動(dòng)用戶數(shù)量需要不大于父節(jié)點(diǎn)或根節(jié)點(diǎn)的。

(2)對于排序樹中的任意一個(gè)非葉子節(jié)點(diǎn),其節(jié)點(diǎn)上的移動(dòng)用戶數(shù)量是其所有子節(jié)點(diǎn)的移動(dòng)用戶數(shù)量之和。

本文使用等比數(shù)列隱私預(yù)算分配算法。對于給定的隱私預(yù)算和排序樹結(jié)構(gòu)高度,根據(jù)不同比值q的計(jì)算,每層的隱私預(yù)算分配都不同,如式(7)所示:

(7)

由式(7)可知,當(dāng)q=1時(shí),排序樹每層結(jié)構(gòu)分配的隱私預(yù)算相同;當(dāng)q>1時(shí),從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)每層結(jié)構(gòu)分配的隱私預(yù)算為以q為單位逐級遞增。根據(jù)隱私保護(hù)度的不同需求來調(diào)整q值,選擇合適的隱私預(yù)算分配方案。使用不同的比值q,隱私預(yù)算會根據(jù)q值的不同而變化,找到一個(gè)合理規(guī)范的最優(yōu)比值,既可以有效合理地分配預(yù)算,又能夠在保證數(shù)據(jù)可用性的同時(shí)保證數(shù)據(jù)安全性。

通過在軌跡排序樹上的位置數(shù)據(jù)等信息中添加拉普拉斯噪聲,能夠有效對抗攻擊者對軌跡的信息推理攻擊,從而保護(hù)用戶隱私。本文采用等比數(shù)列隱私預(yù)算分配算法,并對每一層設(shè)置相應(yīng)的閾值Qi來限制噪聲量的添加。本文定義第i層閾值為a×i-1+b,a>0,b>0,a和b為閾值參數(shù)。若加噪后節(jié)點(diǎn)計(jì)數(shù)值超過閾值,則必須重新選擇噪聲量,直到可以通過,具體如算法1所示。

算法1等比數(shù)列隱私預(yù)算分配算法GPPA(Geometric Progression Privacy Assignment)

輸入：軌跡數(shù)據(jù)集D,總隱私預(yù)算ε和樹高度h,常數(shù)q。

輸出：噪聲保護(hù)數(shù)據(jù)集D′。

步驟1初始化ε,h和q;

步驟2創(chuàng)建高度為h的排序樹和根節(jié)點(diǎn);

步驟3fori

步驟4if(q=1)then

步驟5εi=ε/(h+1);

步驟6else

步驟7εi=εqh-i(1-q)/(1-qh+1);

步驟8endif

步驟9Qi=a×i-1+b;

步驟10for每一個(gè)vi節(jié)點(diǎn)的孩子節(jié)點(diǎn)vi+1do

步驟11vi+1·count=vi+1·count+Lap(1/εi+1);

步驟12ifvi+1·count≤Qithen

步驟13節(jié)點(diǎn)vi+1存入排序樹中;

步驟14sum=sum+vi+1·count;

步驟15ifsum>vi·countthen

步驟16break;

步驟17endif

步驟18endif

步驟19endfor

步驟20endfor

步驟21returnD′

4.3 查詢處理

軌跡排序樹建立軌跡序列的索引結(jié)構(gòu),幫助實(shí)現(xiàn)軌跡數(shù)據(jù)的查詢和存儲。查詢過程中通過軌跡相似度查詢節(jié)點(diǎn),查詢具體步驟如下所示:

步驟1從上到下遍歷軌跡排序樹,順序訪問所有節(jié)點(diǎn);

步驟2計(jì)算查詢軌跡和目標(biāo)軌跡之間的軌跡相似度;

步驟3根據(jù)計(jì)算結(jié)果查詢排序樹中相對應(yīng)的節(jié)點(diǎn);

步驟4返回查詢結(jié)果和節(jié)點(diǎn)中移動(dòng)用戶數(shù)量。

下面簡單說明軌跡排序樹的查詢處理過程。假設(shè)給定查詢軌跡T4,軌跡之間的軌跡相似度為40,查詢結(jié)果為查詢節(jié)點(diǎn)的移動(dòng)用戶數(shù)量。

如圖6所示,通過比較軌跡排序樹中相似度值判斷節(jié)點(diǎn)的位置。根節(jié)點(diǎn)T1的相似度為60,大于T4的相似度,根據(jù)二叉排序樹的性質(zhì)繼續(xù)查詢左子樹。左子樹上T2的相似度為50,大于查詢節(jié)點(diǎn)相似度,繼續(xù)查詢左子樹。查詢到左子樹的相似度等于40,說明此節(jié)點(diǎn)為所要查找的節(jié)點(diǎn)。最后,將查詢到的節(jié)點(diǎn)中的移動(dòng)用戶的數(shù)量返回。

Figure 6 Query processing

5 實(shí)驗(yàn)及結(jié)果分析

本文主要從數(shù)據(jù)可用性、查詢效率及隱私保護(hù)程度3個(gè)方面來評估方案的有效性。Yuan等人[10]提出了一種平均級數(shù)差分隱私預(yù)算分配方案DPTS(Differential Privacy Trajectory Similarity);Zhao等人[11]提出了一種基于前綴樹的差分隱私軌跡數(shù)據(jù)保護(hù)方案NTPT(Novel Trajectory Privacy Tree)。本節(jié)將本文方案SDTS與上述2種方案進(jìn)行比較。

實(shí)驗(yàn)使用的數(shù)據(jù)來自ECML/PKDD 15的出租車軌跡數(shù)據(jù)[20],測試數(shù)據(jù)隨機(jī)選擇10 000條軌跡構(gòu)造軌跡數(shù)據(jù)集。本文使用的模型在PyTorch中實(shí)現(xiàn),通過編碼器對軌跡進(jìn)行訓(xùn)練,編碼器和解碼器固定為3層,模型的隱藏尺寸大小默認(rèn)為256。實(shí)驗(yàn)環(huán)境為Windows11 64位操作系統(tǒng),16 GB內(nèi)存,Intel?CoreTMi5-12500H @3.10 GHz。

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

本節(jié)對本文提出的隱私保護(hù)方案SDTS進(jìn)行數(shù)據(jù)可用性分析。數(shù)據(jù)可用性和隱私保護(hù)程度成反比,軌跡數(shù)據(jù)中加入的噪聲越少,真實(shí)數(shù)據(jù)的干擾越小,發(fā)布的數(shù)據(jù)可用性就越好。所以,選取一個(gè)合理的隱私預(yù)算分配機(jī)制可以有效增強(qiáng)數(shù)據(jù)的可用性。本文采用平均絕對誤差來衡量數(shù)據(jù)可用性。平均絕對誤差計(jì)算公式如式(8)所示:

(8)

其中,m代表數(shù)據(jù)庫集包含的總軌跡數(shù),Di表示原始數(shù)據(jù)集,D′i表示隱私保護(hù)后的數(shù)據(jù)集,|Q(Di)-Q(D′i)|表示查詢計(jì)數(shù)值產(chǎn)生的絕對誤差。

在不同的隱私預(yù)算下,根據(jù)不同的軌跡總數(shù)之間的對比檢測數(shù)據(jù)可用性。本文將實(shí)驗(yàn)分為4組,軌跡數(shù)分別為50,100,150,200。每組實(shí)驗(yàn)20次,取平均值作為最終實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果如圖7所示。

Figure 7 Mean absolute errors under different number of trajectories

在相同的軌跡總數(shù)下,平均絕對誤差隨著隱私預(yù)算的增加而減小。而隨著軌跡總數(shù)的增加,平均絕對誤差也隨之增加。因?yàn)檐壽E數(shù)增加,排序樹高度會隨之增加,導(dǎo)致加入樹中節(jié)點(diǎn)軌跡的噪聲增加,進(jìn)而造成平均絕對誤差增大。實(shí)驗(yàn)結(jié)果顯示,與其他方案相比,本文方案SDTS更優(yōu),平均絕對誤差最小,相對其他方案更加有效。

5.2 查詢效率分析

本節(jié)對本文提出的隱私保護(hù)方案SDTS進(jìn)行查詢效率分析。查詢效率和查詢次數(shù)成正比。查詢的次數(shù)越多,說明查詢效率越低;反之,查詢次數(shù)越少,說明查詢效率越高,所使用到的方案查詢效果越好。查詢效率計(jì)算公式如式(9)所示:

(9)

其中,m代表總軌跡數(shù),N(Di)代表查詢節(jié)點(diǎn)的次數(shù)。

通過比較方案查詢次數(shù)分析不同方案之間的查詢效率。本組實(shí)驗(yàn)考慮了50,100,150,200的軌跡總數(shù)。每組實(shí)驗(yàn)20次,取平均值作為實(shí)驗(yàn)結(jié)果。

如圖8所示?？傑壽E數(shù)增加會導(dǎo)致樹增高,查詢次數(shù)隨之增多。通過實(shí)驗(yàn)不同的軌跡總數(shù)發(fā)現(xiàn),在相同的軌跡總數(shù)下,本文提出的隱私保護(hù)方案SDTS查詢次數(shù)都低于其他方案的,查詢效率更高,隨著實(shí)驗(yàn)軌跡總數(shù)的不斷增加,兩者的查詢效率相差更加明顯。因?yàn)殡S著軌跡數(shù)量的增加,樹形存儲結(jié)構(gòu)高度也隨之增加,導(dǎo)致查詢的次數(shù)以倍數(shù)增加。其他2種方案每次查詢都需要對根節(jié)點(diǎn)下的所有節(jié)點(diǎn)進(jìn)行遍歷查詢,導(dǎo)致查詢效率較低。而本文使用的排序樹方案不需要全部遍歷,只需對比相似度值,進(jìn)而其查詢效率大大優(yōu)于其他方案的。

Figure 8 Query ratios under different trajectories

通過實(shí)驗(yàn)結(jié)果表明,本文方案SDTS查詢效率相比其他方案有明顯優(yōu)勢。

此外,考慮到大數(shù)據(jù)對實(shí)驗(yàn)結(jié)果的影響,本文在本組實(shí)驗(yàn)基礎(chǔ)上加入大數(shù)據(jù)量軌跡數(shù)據(jù)進(jìn)行實(shí)驗(yàn)對比。當(dāng)軌跡數(shù)量增加到1 000條以上時(shí),實(shí)驗(yàn)結(jié)果對比出現(xiàn)了數(shù)倍的差異。NTPT和DPTS的查詢比值分別為0.85和1.08,本文排序樹查詢比值為0.025。這表明,使用本文樹形結(jié)構(gòu)的查詢比值是其他2種對比方案的數(shù)十倍以上,這明顯地表明了本文提出的SDTS方案在大數(shù)據(jù)量軌跡數(shù)據(jù)上的優(yōu)勢。

5.3 隱私保護(hù)分析

數(shù)據(jù)隱私保護(hù)性和數(shù)據(jù)可用性都是比較重要的屬性。當(dāng)數(shù)據(jù)加入的噪聲相對較多,隱私保護(hù)性增強(qiáng),數(shù)據(jù)可用性就會減弱;反之,加入的噪聲較少,隱私保護(hù)程度就不夠強(qiáng),但數(shù)據(jù)可用性會更優(yōu)。本節(jié)測試在不同的預(yù)算分配算法下,數(shù)據(jù)的隱私保護(hù)程度隨著樹形結(jié)構(gòu)的樹高而發(fā)生的變化。本文分析了在不同的樹高下不同的隱私預(yù)算算法對平均絕對誤差的影響,如圖9所示。

Figure 9 Mean absolute errors under different privacy budgets

本文方案SDTS的平均絕對誤差隨著隱私預(yù)算算法的增加而減少。原因在于:隱私預(yù)算越大,添加的噪聲越少,數(shù)據(jù)可用性越好,隱私保護(hù)程度越低。

6 結(jié)束語

進(jìn)入電子信息時(shí)代后,電子設(shè)備獲取用戶包括敏感信息在內(nèi)的各種位置信息后,通過分析對比這些數(shù)據(jù)信息,可以為用戶提高服務(wù)質(zhì)量。但是,在數(shù)據(jù)發(fā)布過程中會有數(shù)據(jù)泄露的現(xiàn)象發(fā)生,因此在數(shù)據(jù)發(fā)布過程中如何防止數(shù)據(jù)泄露是一個(gè)重要的研究問題。

本文提出了一種用于軌跡隱私保護(hù)的排序樹方案SDTS,該方案通過排序樹結(jié)構(gòu)存儲軌跡序列,避免了破環(huán)軌跡的時(shí)空性問題。在排序樹節(jié)點(diǎn)存儲軌跡之間的相似度和其他敏感信息,使用差分隱私對其數(shù)值做加噪處理,以保障發(fā)布的數(shù)據(jù)信息不會輕易泄露。實(shí)驗(yàn)結(jié)果表明,在數(shù)據(jù)可用性和查詢效率上,本文方案SDTS優(yōu)于其他方案,能有效保護(hù)軌跡隱私,且同時(shí)能保證數(shù)據(jù)的可用性。

軌跡隱私保護(hù)是未來一段時(shí)間里一項(xiàng)具有重大意義的研究課題。大數(shù)據(jù)時(shí)代里各種設(shè)備產(chǎn)生大量的位置信息,操作不當(dāng)會導(dǎo)致大量的用戶軌跡數(shù)據(jù)信息泄露,這對軌跡隱私保護(hù)是一項(xiàng)重大挑戰(zhàn)。在未來的研究中將主要關(guān)注以下幾點(diǎn):(1)在軌跡相似度計(jì)算時(shí),如何有效提高準(zhǔn)確性,保證數(shù)值的科學(xué)性;(2)進(jìn)一步優(yōu)化差分隱私預(yù)算分配算法,提高數(shù)據(jù)可用性。