DMVST-Net如何巧妙處理復(fù)雜的交通問題

摘要

在智慧城市的建設(shè)中，出租車需求預(yù)測是一個及其重要的問題。準(zhǔn)確的預(yù)測需求能夠幫助城市預(yù)分配交通資源，提前避免交通擁堵，從而緩解交通壓力，同時降低出租車空載率，提高出租車司機(jī)收入。傳統(tǒng)的出租車需求預(yù)測往往基于時序預(yù)測技術(shù)（time series forcasting techniques），無法對復(fù)雜的非線性時空關(guān)系進(jìn)行建模。深度學(xué)習(xí)技術(shù)的突破為交通預(yù)測問題帶來了曙光，但是現(xiàn)存的深度學(xué)習(xí)網(wǎng)絡(luò)架構(gòu)，往往只單一考慮了時間關(guān)系或者空間關(guān)系，沒有把兩者結(jié)合起來進(jìn)行建模。

本文提出了 DMVST-Net（Deep Multi-View Spatial-Temporal Network），同時對時間關(guān)系和空間更新進(jìn)行建模。更具體地，該模型同時從三個角度出發(fā)（分別是 temporal view, spatial view,semantic view），綜合考慮了出租車需求在路網(wǎng)上分布的時空關(guān)系，并利用語義信息，對相似區(qū)域的時空模式進(jìn)行了建模。

值得一提的是，本文運(yùn)用圖網(wǎng)絡(luò) 和 Local CNN 的方法，對由數(shù)萬路段組成的大型道路交通網(wǎng)，進(jìn)行了特征提取，這一舉措，將圖網(wǎng)絡(luò)的運(yùn)用拓寬到一個新的層次，使得大型交通網(wǎng)的建模有了新的解決思路。

主要貢獻(xiàn)

1、提出了一個多視角模型，該模型同時考慮了 spatial，temporal 和 semantic 信息。

2、提出了 Local CNN 的方法，用于捕獲區(qū)域的局部特征，該特征受到所捕獲區(qū)域鄰近區(qū)域的影響。

3、基于不同區(qū)域之間的時空模式的相似性，構(gòu)建了一個 region graph，用于表達(dá)區(qū)域特征的語義信息。

4、利用滴滴出行的出租車訂單數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，驗(yàn)證了模型的有效性和先進(jìn)性

模型架構(gòu)（DMVST-Net）

在介紹模型之前，先用通俗易懂的語言介紹一下論文的主要思路，先用一個易理解的例子來說明：

小明想預(yù)測整個廣州市對出租車的使用需求，可是掐指一算，整個廣州市有幾萬條道路，簡單的用一維向量去表示它的話，會丟失空間關(guān)系；用圖網(wǎng)絡(luò)去構(gòu)建交通網(wǎng)的話，得到的圖尺寸相當(dāng)大，瞅瞅自己只有四塊 GPU，怕是帶不動；轉(zhuǎn)念一想啊，好多前輩都是用一個個規(guī)則的格網(wǎng)來表示城市的不同區(qū)域，再用 CNN 時空圖像處理的方法建模，可是前輩們做了呀，這可咋整呢。于是小明想了一個辦法：我用傳統(tǒng)的格網(wǎng)去表示城市區(qū)域，每個格網(wǎng)的值就代表這個區(qū)域出租車的需求量，但是我分別對每個格網(wǎng)構(gòu)建一個CNN網(wǎng)絡(luò)。我再用圖網(wǎng)絡(luò)的方法，把城市中每個格網(wǎng)給連接起來，這樣不就能夠表示每個格網(wǎng)（城市區(qū)域）之間的聯(lián)系了嗎？

模型架構(gòu)（DMVST-Net）

給小明同學(xué)鼓個掌，下面就是小明同學(xué)提出的模型。

DMVST-Net 分為三個部分，分別是 Spatial View，Temporal View 和 Semantic View。

Spatial View：Local CNN

什么是Local CNN呢？舉個例子，如下圖所示，我要對 （a）提取特征，最常見的一種方式是把（a）這整張圖像送入到CNN中，進(jìn)行卷積運(yùn)算；而另一種方式就是把（a）分塊，把劃分后的每一小塊分別送入到CNN中，也就是每次只對（b）進(jìn)行卷積運(yùn)算，最后把每個部分的結(jié)果進(jìn)行綜合，這就是 Local CNN。

提出該方法的動機(jī)是地理學(xué)第一定律——near things are more related than distant things。舉個例子，相比于湖北省和河北省的人民，湖北省和湖南省的人民生活習(xí)慣要更相似，這是因?yàn)樗麄z靠的近。小明同學(xué)在這里把廣州市分成了20 x 20個區(qū)域，每個區(qū)域是0.7km x 0.7km，用7 x 7的二維圖像來表示每一個區(qū)域，圖像中每個像素點(diǎn)的灰度值代表出租車的需求量。每張圖像可以用 表示，其中 S=7 。經(jīng)過K個卷積層后得到?，進(jìn)行 flatten 操作得到?，最后進(jìn)行降維得到?具體公式如下：

? ? ?

? ? ?

最終我們Spatial View的輸出是 ? ? ?。

TemporalView:LSTM

小明同學(xué)在這里學(xué)習(xí)了牛頓的思想：“站在巨人肩膀上”。在該部分，小明同學(xué)直接利用了傳統(tǒng)的時序預(yù)測利器——LSTM。LSTM 網(wǎng)絡(luò)是一種特殊的 RNN 網(wǎng)絡(luò)，該網(wǎng)絡(luò)的全稱是 Long Short-Term Memory network（長短期記憶網(wǎng)絡(luò)）。LSTM 網(wǎng)絡(luò)可以說是為時序預(yù)測所量身打造的，該網(wǎng)絡(luò)不僅能夠捕獲近期的時間關(guān)系，還能記憶長期的時間模式，由于遺忘機(jī)制的引入，可以使得 LSTM 網(wǎng)絡(luò)對長時序列也有較好的處理能力。在這里，我們不做推導(dǎo)，直接把公式放出來，有興趣的朋友們可以參見文末的相應(yīng)鏈接【4】。

值得注意的是這里的 LSTM 網(wǎng)絡(luò)的輸入是其中??是 Spatial View 的輸出，而?是天氣、節(jié)假日等元數(shù)據(jù)特征，表示的是聯(lián)合操作。最終我們 Temporal View 的輸出是 。

SemanticView:StructuralEmbedding

接下來到了我們最期待的一步，如何利用圖網(wǎng)絡(luò)的方法，構(gòu)建城市各個區(qū)域的關(guān)系網(wǎng)絡(luò)，從而給我們的深度學(xué)習(xí)任務(wù)提供更高層次的特征。首先，小明同學(xué)根據(jù)一個直覺：具有相同功能的地點(diǎn)應(yīng)該具有相似的出租車需求模式，然而具有相同功能的地點(diǎn)在空間上不一定相鄰。舉個栗子，北京海淀區(qū)的一處 CBD 和朝陽區(qū)的一處 CBD 在很大程度上功能相似，但是這倆個地方隔得老遠(yuǎn)，可是卻可能有著相似的出租車需求模式?；谶@個直覺，小明同學(xué)構(gòu)建了區(qū)域和區(qū)域之間的全連接網(wǎng)絡(luò) ，?代表節(jié)點(diǎn)（即區(qū)域,總數(shù)為 20 x 20），代表每兩個節(jié)點(diǎn)的邊，為相似性矩陣，代表節(jié)點(diǎn) i 和 j 的相似性。

那么問題來了，這個相似性基于什么特征衡量呢？用什么方法去衡量呢？

我們的小明同學(xué)非常的聰明，他將每個節(jié)點(diǎn)的需求序列進(jìn)行整合，計算每周的平均需求量，作為節(jié)點(diǎn)的特征，然后采用了動態(tài)時間規(guī)整（DTW）【5】的方法來衡量節(jié)點(diǎn)之間的相似性。

? ? ?

為了將每個節(jié)點(diǎn)的特征進(jìn)行壓縮，并同時維持網(wǎng)絡(luò)的結(jié)構(gòu)信息，小明同學(xué)又采用了graph embedding 的方法，將每個節(jié)點(diǎn)的特征壓縮到更低的維度。為了構(gòu)建一個端到端的神經(jīng)網(wǎng)絡(luò)模型，小明同學(xué)又將壓縮后的特征送入到一個全連接層，最后得到了Semantic View 的輸出 ? ? ?。

請注意，這里的代表的是節(jié)點(diǎn) i 的語義特征，也就是說，Semantic View提取整個網(wǎng)絡(luò)的特征，但是只把單個節(jié)點(diǎn)所學(xué)習(xí)到的特征送到主體模型中。

模型綜合

最后就是模型綜合部分了，簡單的講，就是把Spatial View，Temporal View 和 Semantic View 這三個部分的輸出結(jié)果給聯(lián)合起來，再通過一些神經(jīng)網(wǎng)絡(luò)層進(jìn)一步提取特征，最后與真實(shí)值計算Loss，通過優(yōu)化算法不斷訓(xùn)練模型，最終得到一個較優(yōu)的結(jié)果。這里簡單列一下公式：

三個部分特征的綜合：? ? ??

輸出函數(shù)設(shè)計：? ? ??

誤差函數(shù)設(shè)計：

這里的 Loss Function 設(shè)計比較有趣，該公式由兩部分組成，第一部分是均方誤差（MSE）,第二部分是平均絕對百分誤差（MAPE）,MSE更多的和大值相關(guān)，而MAPE對大值和小值一視同仁，引入MAPE能夠避免訓(xùn)練過程被大值的樣本所主導(dǎo)。

模型訓(xùn)練算法

在這里，直接把算法貼出來，算法的主要思想就是每個區(qū)域的需求預(yù)測都使用相同的網(wǎng)絡(luò)結(jié)構(gòu)，但是每個區(qū)域?qū)?yīng)的網(wǎng)絡(luò)有著不同的參數(shù)，對所有的網(wǎng)絡(luò)結(jié)構(gòu)都進(jìn)行訓(xùn)練，直到滿足停止條件。這里的算法不是重點(diǎn)，就不再敘述了，有興趣的朋友可以看一下原文。

實(shí)驗(yàn)

數(shù)據(jù)集

在這里，將文章的數(shù)據(jù)集描述進(jìn)行了整理，方便大家快速閱讀

評價矩陣

主要結(jié)果

小明同學(xué)將自己的模型和當(dāng)前的主流模型進(jìn)行了對比，其中包括 Historical average，ARIMA，Ordinary least square regression，Ridge regression，Lasso，Multiple layer perceptron，XGBoost，ST-ResNet。

從表中可以看出，DMVST-Net的效果在兩種評價指標(biāo)上均為最優(yōu)，證明了模型的有效性和先進(jìn)性。

除此之外，小明同學(xué)還計算了各模型從工作日到休息日，相關(guān)誤差的增長（RIE）：

可以看到DMVST-Net的RIE最小，證明了模型魯棒性很高

分別展示了周一到周日各天的預(yù)誤差結(jié)果：

可以看到DMVST-Net每天的預(yù)測誤差（MAPE）都比其他模型小。

最后討論了LSTM輸入序列長度對模型結(jié)果的影響，及Local CNN輸入圖像尺寸的影響。

結(jié)語

這篇文章的作者說，該文的最大貢獻(xiàn)在于從三個視角考慮了城市出租車的需求模式，提出了DMVST-Net，然而這種多視角的建模方式，早就老生常談了。反到是對于圖網(wǎng)絡(luò)的巧妙運(yùn)用，才成就了這篇論文：利用區(qū)域作為節(jié)點(diǎn)構(gòu)圖，而不是采用路段作為節(jié)點(diǎn)構(gòu)圖，不僅避免了城市尺度下圖網(wǎng)絡(luò)過大的問題，而且很好的利用圖網(wǎng)絡(luò)的特性，構(gòu)建了不同區(qū)域之間的聯(lián)系，從而提取了各區(qū)域的語義特征。這種大而化小的思想值得我們?nèi)W(xué)習(xí)，在圖網(wǎng)絡(luò)尚未解決計算復(fù)雜性的今天，或許這種小trick更加有利于加速產(chǎn)學(xué)研結(jié)合，將圖網(wǎng)絡(luò)應(yīng)用到更多的地方！