隱私保護(hù)下的車輛軌跡聯(lián)邦嵌入學(xué)習(xí)與聚類

孔秀平,陸 林

(1.揚(yáng)州工業(yè)職業(yè)技術(shù)學(xué)院信息中心,江蘇 揚(yáng)州 225127) (2.中電云數(shù)智科技有限公司,湖北 武漢 430056)

隨著網(wǎng)聯(lián)汽車的普及,車聯(lián)網(wǎng)技術(shù)可以采集到大量的車輛時(shí)空軌跡數(shù)據(jù). 對時(shí)空軌跡數(shù)據(jù)的挖掘和語義推理,既可以發(fā)現(xiàn)頻繁的行駛路線或異常車輛,也可以幫助推理用戶的出行意圖,無論對物流行業(yè)、交管部門還是運(yùn)營商來說,都具有很大的應(yīng)用價(jià)值.

本文旨在利用某城市電動網(wǎng)約車實(shí)際運(yùn)行數(shù)據(jù),發(fā)現(xiàn)不同時(shí)段下的頻繁運(yùn)營路線,從而輔助智能交通決策與提升車輛運(yùn)營效率. 發(fā)現(xiàn)頻繁路線的通常做法是應(yīng)用空間聚類算法[1],并將聚類的結(jié)果進(jìn)行過濾得到滿足要求的頻繁線路. 但傳統(tǒng)方法需要直接利用原始的軌跡經(jīng)度、緯度數(shù)據(jù)來計(jì)算不同行駛軌跡之間的相似度,從而忽略了信息共享的隱私問題[2-4].

智能網(wǎng)聯(lián)汽車的信息共享是富有挑戰(zhàn)性的,因?yàn)槿藗內(nèi)找娓杏X到數(shù)據(jù)安全和隱私的重要性[5]. 一般來說,不同渠道收集的不同車輛的狀態(tài)數(shù)據(jù)、行駛軌跡都屬于個(gè)人隱私,信息共享將帶來安全隱私隱患. 另外,出租車、網(wǎng)約車包含乘客的敏感信息,例如住所、上班地和通勤路線等,這一事實(shí)需要在訓(xùn)練過程中考慮隱私.

針對這一挑戰(zhàn),一種可行的方法通過應(yīng)用擾亂技術(shù)進(jìn)行隱私保護(hù)式分布式聚類[6],但是其隱私保護(hù)程度有限. 另一種是通過潛空間表征[7],將原始軌跡壓縮到統(tǒng)一維度的特征空間,表示為只有機(jī)器可以理解的特征向量. 然后再構(gòu)建基于潛空間特征的機(jī)器學(xué)習(xí)算法,來解決相應(yīng)的分類與聚類問題,從而避免對原始數(shù)據(jù)的直接利用敏感問題. 然而該軌跡表示的訓(xùn)練過程仍然需要數(shù)據(jù)擁有者分享自身的數(shù)據(jù)進(jìn)行集中式學(xué)習(xí),仍然存在隱私泄露的風(fēng)險(xiǎn). 本文提出了一種差分聯(lián)邦學(xué)習(xí)的軌跡嵌入學(xué)習(xí)方法,在充分保護(hù)用戶隱私的前提下發(fā)現(xiàn)個(gè)體用戶不敏感的頻繁路線. 本文的主要貢獻(xiàn)包括:

(1)提出了利用橫向聯(lián)邦學(xué)習(xí)框架在各方不共享原始軌跡數(shù)據(jù)的前提下,共同學(xué)習(xí)軌跡自編碼模型.

(2)針對解碼器可能還原具體用戶原始軌跡的問題,利用差分隱私算法對模型進(jìn)一步加密,避免模型參數(shù)泄露.

(3)在真實(shí)數(shù)據(jù)集上對差分后的軌跡嵌入進(jìn)行了聚類分析,通過對比發(fā)現(xiàn)其聚類效果與無隱私保護(hù)的方法效果一致.

1 相關(guān)工作

1.1 基于軌跡嵌入表示的聚類

Yao等[8]嘗試將每條軌跡轉(zhuǎn)換成固定長度的表示形式,從而很好地編碼對象的移動行為. 一旦學(xué)習(xí)到高質(zhì)量的軌跡表示,就可以根據(jù)實(shí)際需要輕松地應(yīng)用任何經(jīng)典的聚類算法. Yue等[9]提出了一種用于移動行為聚類的無監(jiān)督神經(jīng)方法-DETECT. 它利用LSTM自編碼[10]學(xué)習(xí)了行為潛在空間中軌跡的強(qiáng)大表示,從而使聚類算法(例如k均值)得以應(yīng)用.

給定一個(gè)自編碼模型M,它包括編碼器Menc和解碼器Mdec.該模型學(xué)習(xí)的目標(biāo)是給定任意變長的軌跡序列x∈R,學(xué)習(xí)其定長的嵌入變量z∈Rd(d為嵌入空間維度)使得其盡可能包含原有軌跡的信息,表示為:

x≈Mdec(z=Menc(x)).

(1)

利用自編碼模型將所有車輛的行程軌跡映射到嵌入空間Z后,就可以利用傳統(tǒng)的聚類算法基于相似度度量進(jìn)行自動分組. 每一組的中心向量,經(jīng)過解碼器還原后就代表了一條頻繁的運(yùn)行路線.

最新的實(shí)驗(yàn)結(jié)果表明,序列自編碼已經(jīng)是軌跡序列表征學(xué)習(xí)的state-of-art方法. 然而,上述研究中需要對所有車輛的軌跡進(jìn)行集中學(xué)習(xí),也就是所有車輛都要分享自己的GPS數(shù)據(jù),這樣明顯暴露了各用戶的相關(guān)隱私,比如家庭住址、上班場所以及通勤路線等信息[10].

1.2 基于差分隱私的聯(lián)邦學(xué)習(xí)

聯(lián)邦學(xué)習(xí)(federated learning,FL)[11-12]模式因其允許數(shù)據(jù)擁有者在不共享原始數(shù)據(jù)的前提下多方共同參與進(jìn)行機(jī)器(深度)學(xué)習(xí)得到了廣泛關(guān)注. 假設(shè)一共有n個(gè)數(shù)據(jù)擁有者,對應(yīng)的數(shù)據(jù)集為D={D1,…,Dn},聯(lián)邦機(jī)器學(xué)習(xí)的主要思想是每個(gè)數(shù)據(jù)擁有者k先接收第三方聚合者的初始化全局模型MFED,接著利用自身的數(shù)據(jù)進(jìn)行本地訓(xùn)練得到局部模型Mk,然后僅通過傳遞參數(shù)來更新全局模型.聚合者接收數(shù)據(jù)擁有者的模型參數(shù)進(jìn)行聚合,得到更新后的全局模型.該過程一直持續(xù)直到達(dá)到終止條件為止.

雖然聯(lián)邦學(xué)習(xí)有效避免原始數(shù)據(jù)的傳輸和泄露,但是在深度學(xué)習(xí)模型的聯(lián)邦訓(xùn)練過程中,仍然存在梯度泄露風(fēng)險(xiǎn).針對這一問題,相關(guān)的研究利用差分隱私(differential privacy,DP)來解決. 差分隱私最早由DWORK[13]于2006年提出,典型的定義如下:

給定隨機(jī)化算法A,對于任意兩個(gè)相鄰數(shù)據(jù)集D,D和A可能的輸出O,算法A符合(ε,δ)-DP,滿足

P[A(D)∈O]≤eεP[A(D′)]+δ.

(2)

式中,δ表示允許ε-DP被打破的概率,ε表示保護(hù)級別或隱私預(yù)算,ε越小表示隱私保護(hù)級別越高.此定義可確?；谒惴ǖ妮敵?對手具有有限的(取決于ε,δ的大小)識別任何個(gè)人存在或不存在的能力.

深度學(xué)習(xí)中實(shí)現(xiàn)DP的主要方式是對模型添加一定的噪聲來滿足[14].常用的噪聲機(jī)制包括拉普拉斯和高斯噪聲.以高斯差分隱私(Gaussian DP,GDP)為例,高斯機(jī)制從服從均值為μ,標(biāo)準(zhǔn)差為σ的分布 N(μ,σ2)中,隨機(jī)采樣添加到每一維的模型參數(shù)中.通過本地化差分隱私,每個(gè)客戶端的梯度上傳的第三方可以是不可信的.該梯度下降算法滿足(ε,δ)-DP,最終模型參數(shù)的誤差趨近于常數(shù).相較于同態(tài)加密、密鑰共享和混淆電路燈隱私保護(hù)技術(shù),差分隱私因其計(jì)算和傳輸成本低的優(yōu)勢成為了聯(lián)邦學(xué)習(xí)研究的新方向.

2 相關(guān)問題與研究方法

2.1 問題定義

定義1軌跡數(shù)據(jù) 考慮一組移動車輛集合,表示為V={v1,v2,…,vl}.某車輛的軌跡TR定義為其在時(shí)間維度上的一系列位置點(diǎn).位置點(diǎn)為包含時(shí)間戳、經(jīng)度和緯度的三元組,表示為p=.對于每個(gè)對象vi,其歷史序列可表示為TRvi=(pi1,pi2,…,pim).

定義2周期時(shí)段軌跡 首先將車輛的軌跡點(diǎn)根據(jù)時(shí)間解析出所在星期,然后給定時(shí)間槽(表示為Δ),將該位置點(diǎn)映射到當(dāng)天所在的時(shí)段.比如時(shí)間槽為0.5 h,那么一天被劃分為48個(gè)時(shí)段.周期時(shí)段軌跡則是將車輛軌跡按星期時(shí)段維度進(jìn)行分組得到的軌跡序列.

定義3軌跡嵌入表示 根據(jù)定義1和定義2,所有車輛的周期時(shí)段軌跡集用Ψ=(trip1,trip2,…,tripm)表示.因?yàn)檐壽E的變長特性,我們定義軌跡的嵌入映射Ψ→Rm×d,其中R為嵌入空間,d為嵌入向量維度.經(jīng)過該變換每一段軌跡都會被表示一個(gè)d維的向量表示.

基于以上定義,本文需要解決的問題是,給定任意周期時(shí)段內(nèi)車輛的運(yùn)行軌跡,找出其中的頻繁路線.該問題的挑戰(zhàn)主要是:(1)車輛原始軌跡不能分享以進(jìn)行集中式的學(xué)習(xí).(2)學(xué)習(xí)到的嵌入需要加密以保證個(gè)體用戶的軌跡信息不被查詢到.(3)最終聚類的效果要保證較高的精確度,即需要隱私保護(hù)和模型精度之間的折衷.

圖1 差分隱私聯(lián)邦軌跡嵌入聚類框架Fig.1 DP FL of trajectory embedding for clustering framework

2.2 軌跡嵌入的差分聯(lián)邦學(xué)習(xí)框架

針對上述問題,本文提出了圖1所示的差分隱私聯(lián)邦軌跡嵌入聚類(DP FL of trajectory embedding for clustering,DP-FL-TE4C)框架. 圖1主要包括了差分隱私聯(lián)邦軌跡嵌入(DP-FL-TE)學(xué)習(xí)與軌跡嵌入聚類和解碼兩部分.

框架第一部分主要是包括一個(gè)第三方服務(wù)器(FL Server)和多輛車輛組成的聯(lián)邦學(xué)習(xí)流程.這里假設(shè)車輛具有邊緣計(jì)算能力,他們有選擇地參與序列自編碼模型的訓(xùn)練,并將添加噪聲后的梯度上傳給服務(wù)器.第三方服務(wù)器在云端進(jìn)行云計(jì)算,它主導(dǎo)模型的聯(lián)邦訓(xùn)練過程.它首先將模型及數(shù)據(jù)處理邏輯發(fā)送給圖1中各個(gè)數(shù)據(jù)持有方,然后接收各本地結(jié)點(diǎn)訓(xùn)練好的模型參數(shù),進(jìn)行聚合得到一個(gè)全局最優(yōu)的模型.

該框架第二部分的工作是FL Server接受各方發(fā)送的差分加密后的軌跡嵌入向量,應(yīng)用無監(jiān)督聚類算法得到頻繁的簇,最后對頻繁簇的中心嵌入向量應(yīng)用解碼器還原.

2.3 軌跡序列自編碼模型

本文提出的框架中使用LSTM通過重建軌跡的GPS序列來生成固定長度的深度表示的嵌入向量. 在實(shí)踐中,LSTM作為循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)的變體,通過加入門機(jī)制,能更好地捕獲時(shí)序結(jié)構(gòu).

(3)

2.4 差分隱私聯(lián)邦訓(xùn)練

本文提出的DP-FL-TE實(shí)現(xiàn)如算法1所示,它主要包括本地局部更新、差分隱私保護(hù)機(jī)制和云端模型聚合3個(gè)部分.

2.4.1 本地局部更新

2.4.2 差分隱私保護(hù)

對模型成功的攻擊使攻擊者能夠與數(shù)據(jù)集中的具體記錄建立鏈接,從而在記錄包含敏感信息時(shí)導(dǎo)致隱私泄漏. 通過這些記錄鏈接,可以根據(jù)乘客的軌跡分析出工作地點(diǎn)、家庭住址、活動模式和其他敏感信息. 本文與傳統(tǒng)局部更新唯一的區(qū)別是采用Noisy Adam[15]算法來實(shí)現(xiàn)差分隱私,使得向FL Server分享的是隱私保護(hù)的模型信息.

2.4.3 云端模型聚合

服務(wù)器端接收到這K個(gè)模型參數(shù)后,通過聚合算法合并為一個(gè)全局模型MFed.本文采用經(jīng)典的聯(lián)邦平均方法來聚合.以第t輪聯(lián)邦訓(xùn)練為例,云端接收K輛車的局部帶“噪聲”的參數(shù)并進(jìn)行聚合方式為

(4)

2.5 聚類分析

3 實(shí)驗(yàn)結(jié)果與分析

3.1 數(shù)據(jù)集與參數(shù)設(shè)定

本文使用一份真實(shí)數(shù)據(jù)集來進(jìn)行測試,該數(shù)據(jù)集來自武漢市的88輛純電動網(wǎng)約車,車輛GPS傳感器每10 s獲取當(dāng)前的位置坐標(biāo). 數(shù)據(jù)跨度是從2018年3月1日到31日,共抽取到1 008條有效軌跡,這些軌跡幾乎覆蓋了城市所有主干道路,有利于發(fā)現(xiàn)用戶不同時(shí)段的網(wǎng)約出行規(guī)律. 本文設(shè)置時(shí)段Δ=30 min,那樣每個(gè)時(shí)段最多采集180條記錄,也是自編碼網(wǎng)絡(luò)輸入的最大序列長度. 整個(gè)數(shù)據(jù)集利用固定的隨機(jī)種子進(jìn)行二八劃分,取20%放在云端server作為測試數(shù)據(jù),剩余80%被劃分到10(K=10)個(gè)客戶端來模擬聯(lián)邦學(xué)習(xí).

本文采用了FedML框架進(jìn)行仿真,利用Facebook開源的Opacus實(shí)現(xiàn)差分隱私,具體網(wǎng)絡(luò)模型使用Pytorch來實(shí)現(xiàn). LSTM編碼器的輸入為(180,2),輸出的嵌入變量d為200,解碼器輸入輸出與編碼器剛好相反. 軌跡數(shù)據(jù)事先經(jīng)過了歸一化,故最后對解碼輸出加入了Sigmoid激活函數(shù). 訓(xùn)練過程中的批大小為64,非DP的方法使用Adam優(yōu)化器,學(xué)習(xí)率為0.001,局部迭代次數(shù)為20,最大輪詢次數(shù)為1 000,損失函數(shù)使用均方誤差(mean squared error,MSE).

圖2 不同參與客戶端數(shù)目下的模型在測試集上的 MSE效果對比Fig.2 Comparison of MSE on the test set of models with different number of participating clients

3.2 不同客戶端的效果對比

首先,我們探討了不同的客戶數(shù)量對聯(lián)邦模型在測試集上性能的影響. 仿真結(jié)果如圖2所示,其中顯然的NonFL-TE在測試集上的損失最低為0.013 8%. 其次,FL-TE最低的損失在0.07%左右. DP-FL-TE損失與FL-TE相關(guān)不大. 另外,可以看到隨著客戶端數(shù)目的增加,FLServer聚合的全局模型性能逐步提高. FL-TE和DP-FL-TE在客戶端數(shù)目為9時(shí)驗(yàn)證損失最小.

3.3 訓(xùn)練過程對比分析

圖3顯示了3種模型在訓(xùn)練集上的平均訓(xùn)練損失情況. 可以看到,NonFL-TE模型收斂最快且訓(xùn)練損失最低. FL-TE收斂速度次之,因?yàn)槠涿看斡?xùn)練集的批次受限于本地?cái)?shù)據(jù)集且利用聯(lián)邦平均來優(yōu)化多個(gè)局部模型. DP-FL-TE的聯(lián)邦平均損失在前兩輪急劇下降,最終收斂速度最慢,不過收斂時(shí)的訓(xùn)練損失與FL-TE相差不大.

圖3 不同模型的訓(xùn)練損失對比Fig.3 Training loss comparison of different models

我們觀察到:(1)在差分隱私聯(lián)邦模式下,聚合模型雖然精度有所損失,但最終依然能夠有效地收斂. (2)模型精度的提高會導(dǎo)致隱私預(yù)算上升,也就是模型信息泄露的風(fēng)險(xiǎn)增加. 通過隱私分析結(jié)合訓(xùn)練損失,可以輔助確定兩者的折衷點(diǎn).

3.4 頻繁軌跡聚類挖掘

本文的最終目的是對隱私軌跡進(jìn)行聚類,對學(xué)習(xí)到的軌跡嵌入進(jìn)行聚類,對比非聯(lián)邦模式下的結(jié)果來驗(yàn)證DP-FL-TE的精度損失是否影響到最終聚類結(jié)果的有效性. 探索使用該框架來聚類將所有車輛軌跡數(shù)據(jù),將相似的軌跡組合在一起,從而發(fā)現(xiàn)頻繁行駛路線.

具體驗(yàn)證手段為,對3種模型輸出的嵌入表示分別利用Gmeans算法進(jìn)行自動聚類,最大簇?cái)?shù)目為100,然后將聚類簇大小不小于10條軌跡的結(jié)果,作為頻繁軌跡集合. 令3種模型輸出的聚類結(jié)果分別為C,CFed,CDPFed,對應(yīng)的軌跡嵌入矩陣為Z,ZFed,ZDPFed,然后將(Z,C)、(Z,CFed)、(Z,CDPFed)作為輸入,使用Silhouette系數(shù)、Calinski Harabasz score(CH_score)和Davies-Bouldin score(DB_score)進(jìn)行聚類效果驗(yàn)證. 這3種度量方法中,前兩個(gè)方法的值越高表示聚類效果越好,第三個(gè)則相反.

表1中列出了這三種模型進(jìn)行10次聚類后的結(jié)果. 可見,3種模型輸出的頻繁簇?cái)?shù)目大致相近,且非聯(lián)邦模型聚類效果最好. 以非聯(lián)邦模型聚類結(jié)果為基準(zhǔn),可以發(fā)現(xiàn)聯(lián)邦模型輸出聚類結(jié)果在非聯(lián)邦嵌入上的劃分性能雖然有所下降,但下降幅度不大,且有趣的是DP-FL-TE4C稍微好于FL-TE4C. 這是因?yàn)橐环矫嫱ㄟ^圖3可以看到DP-FL-TE收斂時(shí)的訓(xùn)練損失水平與FL-TE模型的幾乎相同,甚至略優(yōu). 另一方面,DP-FL-TE4C通過添加高斯噪聲,使得軌跡自編碼網(wǎng)絡(luò)相對FL-TE4C具有更好的泛化能力,使得來自不同車輛相似的軌跡在潛空間上的生成表示更為接近.

表1 3種模型聚類效果對比Table 1 Comparison of clustering effect of three models

4 結(jié)論

本文提出了一種隱私保護(hù)的車輛軌跡深度表征框架. 該框架一方面使用序列自編碼網(wǎng)絡(luò)學(xué)習(xí)原始GPS軌跡的嵌入表示,解決了序列長度不一致(高維度)問題. 另一方面通過聯(lián)邦學(xué)習(xí)模式避免用戶隱私的直接暴露,并進(jìn)一步利用差分隱私來避免模型參數(shù)的第三方攻擊.

為了證明該框架的有效性,利用實(shí)際數(shù)據(jù)集通過聯(lián)邦學(xué)習(xí)仿真,比較了該框架下模型的嵌入學(xué)習(xí)效果. 最后將其應(yīng)用到實(shí)際場景中,通過對真實(shí)數(shù)據(jù)集上的軌跡嵌入學(xué)習(xí)以及聚類效果對比,可獲得有用的頻繁軌跡簇,即頻繁路線.