【導語(yǔ)】自 2018 年 6 月 DeepMind 發(fā)表論文“Relational inductive biases, deep learning, and graph networks”至今，深度圖網(wǎng)絡(luò )火的一塌糊涂，然而在交通領(lǐng)域等需要構建大型圖網(wǎng)絡(luò )的應用中，深度圖網(wǎng)絡(luò )似乎“舉步維艱”。大型圖網(wǎng)絡(luò )建模往往需要大量的計算資源，這無(wú)論是在研究中還是在工業(yè)生產(chǎn)中，都是難以逾越的障礙。然而AAAI 2018 收錄的一篇論文，從交通領(lǐng)域出發(fā)，巧妙給出了這個(gè)問(wèn)題的解決辦法。
在智慧城市的建設中，出租車(chē)需求預測是一個(gè)及其重要的問(wèn)題。準確的預測需求能夠幫助城市預分配交通資源，提前避免交通擁堵，從而緩解交通壓力，同時(shí)降低出租車(chē)空載率，提高出租車(chē)司機收入。傳統的出租車(chē)需求預測往往基于時(shí)序預測技術(shù)（time series forcasting techniques），無(wú)法對復雜的非線(xiàn)性時(shí)空關(guān)系進(jìn)行建模。深度學(xué)習技術(shù)的突破為交通預測問(wèn)題帶來(lái)了曙光，但是現存的深度學(xué)習網(wǎng)絡(luò )架構，往往只單一考慮了時(shí)間關(guān)系或者空間關(guān)系，沒(méi)有把兩者結合起來(lái)進(jìn)行建模。
本文提出了 DMVST-Net（Deep Multi-View Spatial-Temporal Network），同時(shí)對時(shí)間關(guān)系和空間更新進(jìn)行建模。更具體地，該模型同時(shí)從三個(gè)角度出發(fā)（分別是 temporal view, spatial view,semantic view），綜合考慮了出租車(chē)需求在路網(wǎng)上分布的時(shí)空關(guān)系，并利用語(yǔ)義信息，對相似區域的時(shí)空模式進(jìn)行了建模。
值得一提的是，本文運用圖網(wǎng)絡(luò ) 和 Local CNN 的方法，對由數萬(wàn)路段組成的大型道路交通網(wǎng)，進(jìn)行了特征提取，這一舉措，將圖網(wǎng)絡(luò )的運用拓寬到一個(gè)新的層次，使得大型交通網(wǎng)的建模有了新的解決思路。
1、提出了一個(gè)多視角模型，該模型同時(shí)考慮了 spatial，temporal 和 semantic 信息。
2、提出了 Local CNN 的方法，用于捕獲區域的局部特征，該特征受到所捕獲區域鄰近區域的影響。
3、基于不同區域之間的時(shí)空模式的相似性，構建了一個(gè) region graph，用于表達區域特征的語(yǔ)義信息。
4、利用滴滴出行的出租車(chē)訂單數據進(jìn)行實(shí)驗，驗證了模型的有效性和先進(jìn)性
在介紹模型之前，先用通俗易懂的語(yǔ)言介紹一下論文的主要思路，先用一個(gè)易理解的例子來(lái)說(shuō)明：
小明想預測整個(gè)廣州市對出租車(chē)的使用需求，可是掐指一算，整個(gè)廣州市有幾萬(wàn)條道路，簡(jiǎn)單的用一維向量去表示它的話(huà)，會(huì )丟失空間關(guān)系；用圖網(wǎng)絡(luò )去構建交通網(wǎng)的話(huà)，得到的圖尺寸相當大，瞅瞅自己只有四塊 GPU，怕是帶不動(dòng)；轉念一想啊，好多前輩都是用一個(gè)個(gè)規則的格網(wǎng)來(lái)表示城市的不同區域，再用 CNN 時(shí)空圖像處理的方法建模，可是前輩們做了呀，這可咋整呢。于是小明想了一個(gè)辦法：我用傳統的格網(wǎng)去表示城市區域，每個(gè)格網(wǎng)的值就代表這個(gè)區域出租車(chē)的需求量，但是我分別對每個(gè)格網(wǎng)構建一個(gè)CNN網(wǎng)絡(luò )。我再用圖網(wǎng)絡(luò )的方法，把城市中每個(gè)格網(wǎng)給連接起來(lái)，這樣不就能夠表示每個(gè)格網(wǎng)（城市區域）之間的聯(lián)系了嗎？
給小明同學(xué)鼓個(gè)掌，下面就是小明同學(xué)提出的模型。
DMVST-Net 分為三個(gè)部分，分別是 Spatial View，Temporal View 和 Semantic View。
Spatial View：Local CNN
什么是Local CNN呢？舉個(gè)例子，如下圖所示，我要對 （a）提取特征，最常見(jiàn)的一種方式是把（a）這整張圖像送入到CNN中，進(jìn)行卷積運算；而另一種方式就是把（a）分塊，把劃分后的每一小塊分別送入到CNN中，也就是每次只對（b）進(jìn)行卷積運算，最后把每個(gè)部分的結果進(jìn)行綜合，這就是 Local CNN。
提出該方法的動(dòng)機是地理學(xué)第一定律——near things are more related than distant things。舉個(gè)例子，相比于湖北省和河北省的人民，湖北省和湖南省的人民生活習慣要更相似，這是因為他倆靠的近。小明同學(xué)在這里把廣州市分成了20 x 20個(gè)區域，每個(gè)區域是0.7km x 0.7km，用7 x 7的二維圖像來(lái)表示每一個(gè)區域，圖像中每個(gè)像素點(diǎn)的灰度值代表出租車(chē)的需求量。每張圖像可以用
表示，其中 S=7 。
經(jīng)過(guò)K個(gè)卷積層后得到
，進(jìn)行 flatten 操作得到
，最后進(jìn)行降維得到
，具體公式如下：
最終我們Spatial View的輸出是
。
Temporal View: LSTM
小明同學(xué)在這里學(xué)習了牛頓的思想：“站在巨人肩膀上”。在該部分，小明同學(xué)直接利用了傳統的時(shí)序預測利器——LSTM。LSTM 網(wǎng)絡(luò )是一種特殊的 RNN 網(wǎng)絡(luò )，該網(wǎng)絡(luò )的全稱(chēng)是 Long Short-Term Memory network（長(cháng)短期記憶網(wǎng)絡(luò )）。LSTM 網(wǎng)絡(luò )可以說(shuō)是為時(shí)序預測所量身打造的，該網(wǎng)絡(luò )不僅能夠捕獲近期的時(shí)間關(guān)系，還能記憶長(cháng)期的時(shí)間模式，由于遺忘機制的引入，可以使得 LSTM 網(wǎng)絡(luò )對長(cháng)時(shí)序列也有較好的處理能力。在這里，我們不做推導，直接把公式放出來(lái)，有興趣的朋友們可以參見(jiàn)文末的相應鏈接【4】。
值得注意的是這里的 LSTM 網(wǎng)絡(luò )的輸入是
，其中
是 Spatial View 的輸出，而
是天氣、節假日等元數據特征，
表示的是聯(lián)合操作。最終我們 Temporal View 的輸出是
。
Semantic View: Structural Embedding
接下來(lái)到了我們最期待的一步，如何利用圖網(wǎng)絡(luò )的方法，構建城市各個(gè)區域的關(guān)系網(wǎng)絡(luò )，從而給我們的深度學(xué)習任務(wù)提供更高層次的特征。首先，小明同學(xué)根據一個(gè)直覺(jué)：具有相同功能的地點(diǎn)應該具有相似的出租車(chē)需求模式，然而具有相同功能的地點(diǎn)在空間上不一定相鄰。舉個(gè)栗子，北京海淀區的一處 CBD 和朝陽(yáng)區的一處 CBD 在很大程度上功能相似，但是這倆個(gè)地方隔得老遠，可是卻可能有著(zhù)相似的出租車(chē)需求模式?；谶@個(gè)直覺(jué)，小明同學(xué)構建了區域和區域之間的全連接網(wǎng)絡(luò )
，
代表節點(diǎn)（即區域,總數為 20 x 20），
代表每?jì)蓚€(gè)節點(diǎn)的邊，
為相似性矩陣，
代表節點(diǎn) i 和 j 的相似性。
那么問(wèn)題來(lái)了，這個(gè)相似性基于什么特征衡量呢？用什么方法去衡量呢？
我們的小明同學(xué)非常的聰明，他將每個(gè)節點(diǎn)的需求序列進(jìn)行整合，計算每周的平均需求量，作為節點(diǎn)的特征，然后采用了動(dòng)態(tài)時(shí)間規整（DTW）【5】的方法來(lái)衡量節點(diǎn)之間的相似性。
為了將每個(gè)節點(diǎn)的特征進(jìn)行壓縮，并同時(shí)維持網(wǎng)絡(luò )的結構信息，小明同學(xué)又采用了graph embedding 的方法，將每個(gè)節點(diǎn)的特征壓縮到更低的維度。為了構建一個(gè)端到端的神經(jīng)網(wǎng)絡(luò )模型，小明同學(xué)又將壓縮后的特征送入到一個(gè)全連接層，最后得到了Semantic View 的輸出
。
請注意，這里的代表的是節點(diǎn) i 的語(yǔ)義特征，也就是說(shuō)，Semantic View提取整個(gè)網(wǎng)絡(luò )的特征，但是只把單個(gè)節點(diǎn)所學(xué)習到的特征送到主體模型中。
模型綜合
最后就是模型綜合部分了，簡(jiǎn)單的講，就是把Spatial View，Temporal View 和 Semantic View 這三個(gè)部分的輸出結果給聯(lián)合起來(lái)，再通過(guò)一些神經(jīng)網(wǎng)絡(luò )層進(jìn)一步提取特征，最后與真實(shí)值計算Loss，通過(guò)優(yōu)化算法不斷訓練模型，最終得到一個(gè)較優(yōu)的結果。這里簡(jiǎn)單列一下公式：
這里的 Loss Function 設計比較有趣，該公式由兩部分組成，第一部分是均方誤差（MSE）,第二部分是平均絕對百分誤差（MAPE）,MSE更多的和大值相關(guān)，而MAPE對大值和小值一視同仁，引入MAPE能夠避免訓練過(guò)程被大值的樣本所主導。
在這里，直接把算法貼出來(lái)，算法的主要思想就是每個(gè)區域的需求預測都使用相同的網(wǎng)絡(luò )結構，但是每個(gè)區域對應的網(wǎng)絡(luò )有著(zhù)不同的參數，對所有的網(wǎng)絡(luò )結構都進(jìn)行訓練，直到滿(mǎn)足停止條件。這里的算法不是重點(diǎn)，就不再敘述了，有興趣的朋友可以看一下原文。
數據集
在這里，將文章的數據集描述進(jìn)行了整理，方便大家快速閱讀
評價(jià)矩陣
主要結果
小明同學(xué)將自己的模型和當前的主流模型進(jìn)行了對比，其中包括 Historical average，ARIMA，Ordinary least square regression，Ridge regression，Lasso，Multiple layer perceptron，XGBoost，ST-ResNet。
從表中可以看出，DMVST-Net的效果在兩種評價(jià)指標上均為最優(yōu)，證明了模型的有效性和先進(jìn)性。
除此之外，小明同學(xué)還計算了各模型從工作日到休息日，相關(guān)誤差的增長(cháng)（RIE）：
可以看到DMVST-Net的RIE最小，證明了模型魯棒性很高
分別展示了周一到周日各天的預誤差結果：
可以看到DMVST-Net每天的預測誤差（MAPE）都比其他模型小。
最后討論了LSTM輸入序列長(cháng)度對模型結果的影響，及Local CNN輸入圖像尺寸的影響。
結語(yǔ)
這篇文章的作者說(shuō)，該文的最大貢獻在于從三個(gè)視角考慮了城市出租車(chē)的需求模式，提出了DMVST-Net，然而這種多視角的建模方式，早就老生常談了。反到是對于圖網(wǎng)絡(luò )的巧妙運用，才成就了這篇論文：利用區域作為節點(diǎn)構圖，而不是采用路段作為節點(diǎn)構圖，不僅避免了城市尺度下圖網(wǎng)絡(luò )過(guò)大的問(wèn)題，而且很好的利用圖網(wǎng)絡(luò )的特性，構建了不同區域之間的聯(lián)系，從而提取了各區域的語(yǔ)義特征。這種大而化小的思想值得我們去學(xué)習，在圖網(wǎng)絡(luò )尚未解決計算復雜性的今天，或許這種小trick更加有利于加速產(chǎn)學(xué)研結合，將圖網(wǎng)絡(luò )應用到更多的地方！
參考文獻
（本文為投稿文章，轉載請微信聯(lián)系1092722531）
聯(lián)系客服
