孔秀平,陸 林

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

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 基于軌跡嵌入表示的聚類(lèi)

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

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

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

(1)

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

最新的實(shí)驗(yàn)結(jié)果表明,序列自編碼已經(jīng)是軌跡序列表征學(xué)習(xí)的state-of-art方法. 然而,上述研究中需要對(duì)所有車(chē)輛的軌跡進(jìn)行集中學(xué)習(xí),也就是所有車(chē)輛都要分享自己的GPS數(shù)據(jù),這樣明顯暴露了各用戶(hù)的相關(guān)隱私,比如家庭住址、上班場(chǎng)所以及通勤路線(xià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ù)擁有者,對(duì)應(yīng)的數(shù)據(jù)集為D={D1,…,Dn},聯(lián)邦機(jī)器學(xué)習(xí)的主要思想是每個(gè)數(shù)據(jù)擁有者k先接收第三方聚合者的初始化全局模型MFED,接著利用自身的數(shù)據(jù)進(jìn)行本地訓(xùn)練得到局部模型Mk,然后僅通過(guò)傳遞參數(shù)來(lái)更新全局模型.聚合者接收數(shù)據(jù)擁有者的模型參數(shù)進(jìn)行聚合,得到更新后的全局模型.該過(guò)程一直持續(xù)直到達(dá)到終止條件為止.

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

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

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

(2)

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

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

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

2.1 問(wèn)題定義

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

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

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

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

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

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

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

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

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

2.3 軌跡序列自編碼模型

本文提出的框架中使用LSTM通過(guò)重建軌跡的GPS序列來(lái)生成固定長(zhǎng)度的深度表示的嵌入向量. 在實(shí)踐中,LSTM作為循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)的變體,通過(guò)加入門(mén)機(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ù)

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

2.4.3 云端模型聚合

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

(4)

2.5 聚類(lèi)分析

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

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

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

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

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

3.2 不同客戶(hù)端的效果對(duì)比

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

3.3 訓(xùn)練過(guò)程對(duì)比分析

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

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

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

3.4 頻繁軌跡聚類(lèi)挖掘

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

具體驗(yàn)證手段為,對(duì)3種模型輸出的嵌入表示分別利用Gmeans算法進(jìn)行自動(dòng)聚類(lèi),最大簇?cái)?shù)目為100,然后將聚類(lèi)簇大小不小于10條軌跡的結(jié)果,作為頻繁軌跡集合. 令3種模型輸出的聚類(lèi)結(jié)果分別為C,CFed,CDPFed,對(duì)應(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)行聚類(lèi)效果驗(yàn)證. 這3種度量方法中,前兩個(gè)方法的值越高表示聚類(lèi)效果越好,第三個(gè)則相反.

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

表1 3種模型聚類(lèi)效果對(duì)比Table 1 Comparison of clustering effect of three models

4 結(jié)論

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

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