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

摘要

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

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

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

主要貢獻(xiàn)

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

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

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

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

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

在介紹模型之前，先用通俗易懂的語(yǔ)言介紹一下論文的主要思路，先用一個(gè)易理解的例子來(lái)說(shuō)明：

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

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

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

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

Spatial View：Local CNN

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

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

? ? ?

? ? ?

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

TemporalView:LSTM

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

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

SemanticView:StructuralEmbedding

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

那么問(wèn)題來(lái)了，這個(gè)相似性基于什么特征衡量呢？用什么方法去衡量呢？

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

? ? ?

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

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

模型綜合

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

三個(gè)部分特征的綜合：? ? ??

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

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

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

模型訓(xùn)練算法

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

實(shí)驗(yàn)

數(shù)據(jù)集

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

評(píng)價(jià)矩陣

主要結(jié)果

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

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

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

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

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

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

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

結(jié)語(yǔ)

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