張翔宇 張 強(qiáng) 呂明琪*

(*中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190)(**中國(guó)科學(xué)院大學(xué) 北京 100049)(***北京賽迪時(shí)代信息產(chǎn)業(yè)股份有限公司 北京 100048)(****浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 杭州 310014)

0 引 言

交通擁堵指數(shù)(traffic congestion index，TCI)是對(duì)道路交通擁堵程度進(jìn)行量化評(píng)價(jià)的一種指標(biāo)[1]。然而，相比于對(duì)當(dāng)前交通擁堵指數(shù)進(jìn)行實(shí)時(shí)監(jiān)測(cè)，對(duì)未來(lái)交通擁堵指數(shù)進(jìn)行準(zhǔn)確預(yù)測(cè)具有更大的價(jià)值。如幫助司機(jī)更好地進(jìn)行路線規(guī)劃[2]，幫助城市管理者更好地進(jìn)行道路建設(shè)規(guī)劃[3]。

交通擁堵指數(shù)預(yù)測(cè)是一種交通流預(yù)測(cè)(交通流包括車(chē)流量、平均車(chē)速、交通擁堵指數(shù)等)。傳統(tǒng)交通流預(yù)測(cè)主要在考慮交通系統(tǒng)物理特性的基礎(chǔ)上采用交通模擬的方法[4-6]。然而，交通模擬需要設(shè)置大量的參數(shù)，而這些參數(shù)在真實(shí)環(huán)境中往往無(wú)法獲得，因此交通模擬通常無(wú)法大規(guī)模地應(yīng)用到整個(gè)城市的道路網(wǎng)絡(luò)。隨著交通數(shù)據(jù)采集設(shè)備的廣泛部署，目前主流的交通流預(yù)測(cè)工作均采用數(shù)據(jù)驅(qū)動(dòng)的方法。數(shù)據(jù)驅(qū)動(dòng)的交通流預(yù)測(cè)方法主要包括統(tǒng)計(jì)模型、機(jī)器學(xué)習(xí)模型、深度學(xué)習(xí)模型。其中，統(tǒng)計(jì)模型主要基于時(shí)間序列分析實(shí)現(xiàn)預(yù)測(cè)，代表性方法包括Kalman濾波[7]、ARIMA模型[8]等。然而，統(tǒng)計(jì)模型無(wú)法有效地處理非線性數(shù)據(jù)，通常在交通流預(yù)測(cè)上難以取得理想的效果。機(jī)器學(xué)習(xí)模型可有效學(xué)習(xí)到交通流數(shù)據(jù)和各類(lèi)影響因素的非線性關(guān)系，因此可實(shí)現(xiàn)更準(zhǔn)確的預(yù)測(cè)，代表性方法包括支持向量機(jī)模型[9]、貝葉斯模型[10]、K近鄰模型[11]等。然而，機(jī)器學(xué)習(xí)模型的性能?chē)?yán)重依賴于特征，而特征主要依賴領(lǐng)域知識(shí)人工設(shè)計(jì)。因此，在處理復(fù)雜關(guān)聯(lián)和潛在因素時(shí)顯得能力不足。近年來(lái)，深度學(xué)習(xí)模型也逐漸應(yīng)用到交通流預(yù)測(cè)領(lǐng)域。深度學(xué)習(xí)模型可自動(dòng)從復(fù)雜數(shù)據(jù)中提取有效特征，擺脫了對(duì)人工設(shè)計(jì)特征的依賴，代表性方法包括前饋神經(jīng)網(wǎng)絡(luò)[12]、深度信念網(wǎng)絡(luò)[13]、自動(dòng)編碼機(jī)[14]等。由于交通流是一類(lèi)時(shí)序數(shù)據(jù)，時(shí)間關(guān)聯(lián)對(duì)預(yù)測(cè)性能具有十分顯著的影響，因此循環(huán)神經(jīng)網(wǎng)絡(luò)(如LSTM、GRU)逐漸成為交通流預(yù)測(cè)的主流深度學(xué)習(xí)方法[15-17]。此外，由于不同的道路間存在復(fù)雜的空間關(guān)聯(lián)，且這些空間關(guān)聯(lián)發(fā)生在不能用歐式距離度量的道路網(wǎng)絡(luò)中，因此少量較新的研究工作嘗試采用圖神經(jīng)網(wǎng)絡(luò)進(jìn)行交通流預(yù)測(cè)[18,19]。

現(xiàn)有方法雖然在交通流預(yù)測(cè)方面取得了顯著的進(jìn)展，但這些方法普遍存在一個(gè)問(wèn)題：這些方法在短期交通流預(yù)測(cè)任務(wù)上性能優(yōu)異，但在長(zhǎng)期交通流預(yù)測(cè)任務(wù)上表現(xiàn)不佳(這里的長(zhǎng)期預(yù)測(cè)指預(yù)測(cè)若干天后的交通流情況)。這是由于雖然這些工作采用了各種各樣的模型，但這些模型本質(zhì)上都屬于回歸模型?；貧w模型擅長(zhǎng)捕捉數(shù)據(jù)的潛在關(guān)聯(lián)，但不擅長(zhǎng)捕捉數(shù)據(jù)的演化趨勢(shì)。

針對(duì)此問(wèn)題，本研究提出了一種融合演化模式挖掘和代價(jià)敏感學(xué)習(xí)的交通擁堵指數(shù)預(yù)測(cè)方法。該方法工作流程如下：給定某條道路的歷史交通擁堵指數(shù)數(shù)據(jù)，首先對(duì)歷史交通擁堵指數(shù)數(shù)據(jù)進(jìn)行離散化，并采用序列模式挖掘算法從中挖掘出交通擁堵指數(shù)的演化模式，在此基礎(chǔ)上設(shè)計(jì)一個(gè)基于演化模式的交通擁堵指數(shù)預(yù)測(cè)器。之所以對(duì)歷史交通擁堵指數(shù)數(shù)據(jù)進(jìn)行離散化，是由于演化模式是由離散型數(shù)據(jù)構(gòu)成的。然后，從多個(gè)角度對(duì)影響交通擁堵指數(shù)的時(shí)空特征(如路網(wǎng)特征、區(qū)域特征、時(shí)序特征)進(jìn)行提取，在此基礎(chǔ)上建立基于機(jī)器學(xué)習(xí)的交通擁堵指數(shù)預(yù)測(cè)器。一方面，為與基于演化模式的交通擁堵指數(shù)預(yù)測(cè)器進(jìn)行融合，基于機(jī)器學(xué)習(xí)的交通擁堵指數(shù)預(yù)測(cè)器的輸出也應(yīng)為離散型數(shù)據(jù)，因此采用分類(lèi)模型構(gòu)造預(yù)測(cè)器；另一方面，由于離散化后的交通擁堵指數(shù)數(shù)據(jù)間仍存在量化比較關(guān)系，而普通分類(lèi)模型無(wú)法表示類(lèi)型間的量化比較關(guān)系，因此采用代價(jià)敏感學(xué)習(xí)訓(xùn)練預(yù)測(cè)器。最后，基于Stacking技術(shù)對(duì)2個(gè)預(yù)測(cè)器的預(yù)測(cè)結(jié)果進(jìn)行融合。

1 方 法

1.1 方法總體框架

定義1(交通擁堵指數(shù))交通擁堵指數(shù)是一種用于對(duì)道路交通擁堵程度進(jìn)行量化評(píng)價(jià)的指標(biāo)。原始交通擁堵指數(shù)通常是連續(xù)型數(shù)據(jù)，數(shù)值越大代表?yè)矶鲁潭仍礁?。根?jù)《城市道路交通擁堵評(píng)價(jià)指標(biāo)體系》[20]，將原始交通擁堵指數(shù)離散化為5個(gè)級(jí)別，交通擁堵指數(shù)離散值1～5分別代表非常暢通、暢通、輕度擁堵、中度擁堵和嚴(yán)重?fù)矶?。因此，一個(gè)交通擁堵指數(shù)數(shù)據(jù)可表示為一個(gè)三元組tci=(d,r,t)，其中d為交通擁堵指數(shù)離散值，r為待監(jiān)測(cè)道路，t為采樣時(shí)間。

圖1展示了本文方法的總體框架，由演化模式預(yù)測(cè)器、機(jī)器學(xué)習(xí)預(yù)測(cè)器和融合器3個(gè)模塊構(gòu)成。其中，由于序列模式被現(xiàn)有研究證實(shí)可較好地捕捉時(shí)序數(shù)據(jù)的長(zhǎng)期演化規(guī)律[21]，演化模式預(yù)測(cè)器采用序列模式挖掘算法挖掘歷史交通擁堵指數(shù)的演化模式，在此基礎(chǔ)上基于演化模式匹配實(shí)現(xiàn)交通擁堵指數(shù)預(yù)測(cè)。機(jī)器學(xué)習(xí)預(yù)測(cè)器基于一系列的時(shí)空特征(如道路特征、區(qū)域特征、時(shí)序特征)，采用代價(jià)敏感學(xué)習(xí)技術(shù)建立預(yù)測(cè)模型。融合器基于Stacking技術(shù)對(duì)演化模式預(yù)測(cè)器和機(jī)器學(xué)習(xí)預(yù)測(cè)器的輸出進(jìn)行動(dòng)態(tài)融合，得到最終的預(yù)測(cè)結(jié)果。

圖1 本文方法的總體框架

1.2 演化模式預(yù)測(cè)器

交通擁堵指數(shù)在一定時(shí)間范圍內(nèi)通常存在特定的演化模式，演化模式預(yù)測(cè)器的構(gòu)建方法如下。

第1步，為挖掘交通擁堵指數(shù)離散值的演化模式，擴(kuò)展PrefixSpan算法[22]，提出了一種基于數(shù)據(jù)投影的演化模式挖掘算法(投影的定義如下)。該算法的主要思路與PrefixSpan算法類(lèi)似，給定一個(gè)序列集，首先根據(jù)當(dāng)前前綴(頻繁元素)去分割每一個(gè)序列，形成子序列集(當(dāng)前前綴和分割得到的子序列集即為投影)。然后再遞歸地在子序列集上重復(fù)上述操作，使得前綴不斷增長(zhǎng)，形成演化模式。該思路的主要優(yōu)勢(shì)在于利用序列中元素的順序信息逐漸減少搜索空間以提高算法效率。而提出的算法與PrefixSpan算法不同之處是在子序列集上搜索頻繁元素?cái)U(kuò)展現(xiàn)有前綴時(shí)，僅在每個(gè)子序列的頭部范圍內(nèi)進(jìn)行搜索，一方面保證演化模式元素在原始序列中的相對(duì)連續(xù)性，另一方面進(jìn)一步減少搜索空間、提高算法效率。如圖2所示，給定歷史交通擁堵指數(shù)離散值序列AS，算法首先通過(guò)序列分割為每個(gè)交通擁堵指數(shù)離散值ci構(gòu)造一個(gè)投影(第1～3行)。然后，算法調(diào)用函數(shù)ExpandProjections遞歸地在現(xiàn)有投影基礎(chǔ)上生成更多的投影。

圖2 交通擁堵指數(shù)演化模式挖掘算法偽代碼

定義2(投影)投影P可表示為一個(gè)二元組P=(PRP,SSP)。其中，PRP為該投影的前綴，可用于代表演化模式；SSP為一個(gè)AS的子序列集。

圖3顯示了ExpandProjections的工作流程：(1)在當(dāng)前投影P的子序列集中搜索所有的頻繁交通擁堵指數(shù)離散值(第1行)。(2)為每個(gè)頻繁交通擁堵指數(shù)離散值cj構(gòu)建一個(gè)新的投影NP(第2～3行)。其中，NP的前綴為連接P的前綴和cj得到，NP的子序列集為對(duì)每個(gè)頭部范圍內(nèi)存在元素cj的P的子序列進(jìn)行截?cái)嗟玫?第4～8行)。之所以僅在子序列的頭部范圍內(nèi)搜索元素cj，是為了保證前綴中相鄰的元素在歷史交通擁堵指數(shù)離散值序列中的間隔也不是太大，以保證其相對(duì)連續(xù)性。(3)函數(shù)被不斷地遞歸調(diào)用，直到新生成的投影包含的子序列集大小小于min_sup(第9～11行)。最后，當(dāng)算法終止，可得到一個(gè)生成的投影集PS。對(duì)PS中每個(gè)投影P，PRP可被認(rèn)為是一個(gè)演化模式，而SSP的大小可被認(rèn)為是該演化模式的支持度。

圖3 ExpandProjections函數(shù)偽代碼

ExpandProjections每次執(zhí)行過(guò)程中，頻繁元素搜索步驟(第1行)的時(shí)間復(fù)雜度為O(|Y|×|SSp|)，投影生成步驟(第2～8行)的時(shí)間復(fù)雜度為O(|Y|×|SSp|×head_range)，因此函數(shù)一次執(zhí)行的時(shí)間復(fù)雜度為O(|Y|×|SSp|×head_range)。由于ExpandProjections是一個(gè)遞歸函數(shù)，其每次執(zhí)行都會(huì)縮短投影子序列的長(zhǎng)度，直至無(wú)法搜索到頻繁元素，因此最壞的情況下ExpandProjections會(huì)被執(zhí)行|Y||AS|次，而在該情況下整個(gè)算法的時(shí)間復(fù)雜度為O(|SSp|×|Y||AS|×head_range)。此外，head_range對(duì)算法實(shí)際的計(jì)算復(fù)雜度影響巨大，這是由于增大head_range不僅會(huì)增加迭代次數(shù)，更重要的是會(huì)擴(kuò)大頭部搜索范圍，使得搜索到目標(biāo)交通擁堵指數(shù)離散值的概率大大增加，導(dǎo)致新投影的子序列數(shù)量難以快速減少，從而算法的遞歸次數(shù)更接近最壞情況。

第2步，基于挖掘得到的演化模式構(gòu)造演化模式預(yù)測(cè)器。其核心思想是假定數(shù)據(jù)的演化過(guò)程遵循固定的一些模式，則當(dāng)數(shù)據(jù)某次觀測(cè)到的演化過(guò)程與某個(gè)模式的前部匹配時(shí)，將模式的后部作為本次的預(yù)測(cè)結(jié)果。該思路的核心步驟為演化模式匹配，即搜索前綴能夠匹配交通擁堵指數(shù)當(dāng)前觀測(cè)到的演化過(guò)程的演化模式。本文基于樹(shù)對(duì)演化模式進(jìn)行索引(將該樹(shù)稱為演化模式樹(shù))，其每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)交通擁堵指數(shù)離散值及相應(yīng)演化模式的支持度(根節(jié)點(diǎn)除外)。演化模式樹(shù)構(gòu)造方法如下：掃描所有演化模式，對(duì)每一個(gè)演化模式，采用深度優(yōu)先搜索算法在演化模式樹(shù)中搜索與該演化模式某個(gè)前綴完全匹配的分枝，然后將該演化模式的后綴插入到該分枝中并更新分枝每個(gè)節(jié)點(diǎn)的支持度。否則，將該演化模式直接插入根節(jié)點(diǎn)作為一個(gè)新的分枝。

第3步，給定交通擁堵指數(shù)當(dāng)前觀測(cè)到的演化過(guò)程RAS(即最近若干個(gè)交通擁堵指數(shù)離散值的序列)和演化模式樹(shù)PT。交通擁堵指數(shù)預(yù)測(cè)方法如下：首先，在PT中搜索前綴能夠匹配RAS的演化模式。演化模式樹(shù)索引結(jié)構(gòu)在這里的優(yōu)勢(shì)在于所有演化模式都可以直接以根節(jié)點(diǎn)作為入口搜索得到，從而有效減少搜索時(shí)間。然而，某些情況下可能會(huì)無(wú)法搜索到匹配的演化模式。針對(duì)這種情況，通過(guò)縮短RAS(刪除RAS的第一個(gè)元素)進(jìn)行再搜索，直到RAS的長(zhǎng)度被縮短為1(此時(shí)一定能夠搜索到匹配的演化模式)。此外，計(jì)算模式匹配率MR，即最終能夠搜索到匹配的演化模式的RAS長(zhǎng)度與最初RAS長(zhǎng)度的比例(MR將在2.1節(jié)用作構(gòu)造機(jī)器學(xué)習(xí)預(yù)測(cè)器的特征)。然后，以搜索到的演化模式的匹配前綴的最后一個(gè)節(jié)點(diǎn)作為入口，進(jìn)行深度優(yōu)先搜索直到葉子節(jié)點(diǎn)，所經(jīng)過(guò)的路徑即為預(yù)測(cè)結(jié)果。深度優(yōu)先搜索的每一步都優(yōu)先搜索支持度最高的子節(jié)點(diǎn)，且可得到一個(gè)交通擁堵指數(shù)離散值的概率向量(概率向量每個(gè)元素為某個(gè)交通擁堵指數(shù)離散值子節(jié)點(diǎn)在這一步被搜索到的概率，計(jì)算為該子節(jié)點(diǎn)的支持度與可選的子節(jié)點(diǎn)支持度之和的比例)。在該預(yù)測(cè)算法中，由于演化模式的長(zhǎng)度通常有限，RAS太長(zhǎng)會(huì)導(dǎo)致頻繁無(wú)法搜索到匹配的演化模式，因此將RAS長(zhǎng)度限制為max_length。

1.3 機(jī)器學(xué)習(xí)預(yù)測(cè)器

演化模式能發(fā)現(xiàn)交通擁堵指數(shù)數(shù)據(jù)的長(zhǎng)期演化規(guī)律，但卻無(wú)法捕捉交通擁堵指數(shù)數(shù)據(jù)和各影響因素間的潛在非線性關(guān)聯(lián)，而機(jī)器學(xué)習(xí)技術(shù)在這方面有顯著的優(yōu)勢(shì)。機(jī)器學(xué)習(xí)技術(shù)能夠有效工作的關(guān)鍵包括2個(gè)方面：一是定義能夠有效表征影響因素的特征，二是構(gòu)建有效的機(jī)器學(xué)習(xí)模型。

在特征定義方面，許多現(xiàn)有工作發(fā)現(xiàn)，當(dāng)前交通流除了與歷史交通流相關(guān)之外，還與某些外部因素相關(guān)，如道路結(jié)構(gòu)、城市功能分區(qū)等[23]。因此，機(jī)器學(xué)習(xí)預(yù)測(cè)器使用的特征包括從歷史交通流數(shù)據(jù)集中抽取的時(shí)序特征以及從道路網(wǎng)絡(luò)和興趣地點(diǎn)數(shù)據(jù)集中抽取的外部特征。給定一個(gè)交通擁堵指數(shù)樣本D=(rk,d)，rk為樣本所在道路，d為樣本當(dāng)前日期，具體特征抽取方法如下。

(1)時(shí)序特征。由于本文預(yù)測(cè)日平均交通擁堵指數(shù)，因此時(shí)序特征為rk在d的前h天到d的日平均交通擁堵指數(shù)序列，記為Mk=。其中，ci為rk在d的前i天的日平均交通擁堵指數(shù)，c0為rk在d的日平均交通擁堵指數(shù)。

(2)時(shí)間特征。時(shí)間特征包括待預(yù)測(cè)天是星期幾、是否是假期。時(shí)間特征向量記為T(mén)k。

(3)道路特征。道路特征包括rk的道路類(lèi)型(如高架路、主干路、次干路)、道路方向(如雙行線、單行線)、交叉口數(shù)量、道路長(zhǎng)度、道路扭曲度(即道路長(zhǎng)度與道路端點(diǎn)直線距離的比例)，rk的道路特征向量記為Rk。

(1)

綜上，Rk和Pk為靜態(tài)特征，Mk和Tk為動(dòng)態(tài)特征，則樣本D的特征向量為。

在模型構(gòu)建方面，由于演化模式是離散的數(shù)據(jù)序列而演化模式預(yù)測(cè)器輸出的也是交通擁堵指數(shù)離散值，因此本文基于分類(lèi)模型建立交通擁堵指數(shù)的機(jī)器學(xué)習(xí)預(yù)測(cè)器，以便于后續(xù)演化模式預(yù)測(cè)器和機(jī)器學(xué)習(xí)預(yù)測(cè)器的融合。然而，直接采用標(biāo)準(zhǔn)的分類(lèi)模型用于交通擁堵指數(shù)預(yù)測(cè)存在標(biāo)準(zhǔn)分類(lèi)模型的訓(xùn)練目標(biāo)為最大化準(zhǔn)確率，并對(duì)所有分類(lèi)錯(cuò)誤同等對(duì)待。例如，對(duì)于一個(gè)真實(shí)交通擁堵指數(shù)離散值為2的樣本，預(yù)測(cè)結(jié)果為3和5對(duì)于標(biāo)準(zhǔn)分類(lèi)模型的分類(lèi)錯(cuò)誤損失是一樣的。然而，在本問(wèn)題中，預(yù)測(cè)結(jié)果為5相比預(yù)測(cè)結(jié)果為3更不能接受，即預(yù)測(cè)結(jié)果為5的分類(lèi)錯(cuò)誤損失應(yīng)該更大。針對(duì)此問(wèn)題，本文采用代價(jià)敏感學(xué)習(xí)技術(shù)訓(xùn)練分類(lèi)模型。代價(jià)敏感學(xué)習(xí)的主要思想是通過(guò)定義不同分類(lèi)錯(cuò)誤的代價(jià)，使得分類(lèi)錯(cuò)誤代價(jià)大的樣本在模型訓(xùn)練過(guò)程中造成更大的損失，從而最終的模型能夠最小化總的分類(lèi)錯(cuò)誤代價(jià)。具體步驟如下。

首先，定義用于計(jì)算分類(lèi)錯(cuò)誤代價(jià)的代價(jià)矩陣C，使得預(yù)測(cè)誤差越大分類(lèi)錯(cuò)誤代價(jià)越高。假定真實(shí)交通擁堵指數(shù)離散值為i，而預(yù)測(cè)交通擁堵指數(shù)離散值為j，則C為一個(gè)5 × 5的矩陣，分類(lèi)錯(cuò)誤代價(jià)為C[i,j]=|i-j|。然后，基于代價(jià)矩陣，采用代價(jià)敏感學(xué)習(xí)算法GLL-MCBoost[24]訓(xùn)練分類(lèi)模型。除了能將分類(lèi)錯(cuò)誤代價(jià)反映到損失函數(shù)中，GLL-MCBoost算法還具有如下優(yōu)勢(shì)：其可以有效處理arbitrary guess樣本，arbitrary guess樣本指該樣本在多個(gè)類(lèi)型上的預(yù)測(cè)概率相同，這種情況下分類(lèi)器只能給出一個(gè)隨意猜測(cè)。GLL-MCBoost算法通過(guò)boosting機(jī)制在每輪迭代中增加arbitrary guess樣本的權(quán)重，使其能在下一輪迭代中得到更有效的訓(xùn)練。

1.4 融合器

演化模式預(yù)測(cè)器和機(jī)器學(xué)習(xí)預(yù)測(cè)器的輸出均可表示為一個(gè)5維向量，其中向量的第k個(gè)元素代表預(yù)測(cè)交通擁堵指數(shù)離散值為k的概率。由于這2個(gè)預(yù)測(cè)器采用完全不同的技術(shù)構(gòu)建，它們具有不平衡的預(yù)測(cè)能力，甚至對(duì)不同樣本預(yù)測(cè)能力的不平衡程度也不同。因此，簡(jiǎn)單對(duì)2個(gè)預(yù)測(cè)器的預(yù)測(cè)概率求平均無(wú)法取得理想的性能。針對(duì)此問(wèn)題，采用Stacking技術(shù)對(duì)2個(gè)預(yù)測(cè)器的輸出進(jìn)行融合。其主要思想為融合多個(gè)子模型，將這多個(gè)子模型輸出的預(yù)測(cè)結(jié)果作為新的特征，在此基礎(chǔ)上再訓(xùn)練一個(gè)元模型。元模型可學(xué)習(xí)到不同子模型預(yù)測(cè)能力的不平衡性，并基于此給子模型輸出的預(yù)測(cè)結(jié)果分配權(quán)重，這比簡(jiǎn)單對(duì)子模型輸出的預(yù)測(cè)結(jié)果求平均效果更好。

給定訓(xùn)練樣本集TS={S1,S2,…,SN}和交通擁堵指數(shù)離散值值域Y={1, 2, 3, 4, 5}，Ppattern(Sk,y)和Pfeature(Sk,y)分別代表演化模式預(yù)測(cè)器和機(jī)器學(xué)習(xí)預(yù)測(cè)器預(yù)測(cè)樣本Sk的交通擁堵指數(shù)離散值為y的概率。此外，采用2.1節(jié)中的模式匹配率MR(Sk)作為一個(gè)額外的特征(這是由于模式匹配率對(duì)演化模式預(yù)測(cè)器的預(yù)測(cè)性能有很大影響)。綜上，可得到一個(gè)元特征向量MF={MR(S1),Ppattern(S1, 1),…,Ppattern(S1, 5),Pfeature(S1, 1),…,Pfeature(S1, 5)},…,MR(SN),Ppattern(SN, 1),…,Ppattern(SN, 5),Pfeature(SN, 1),…,Pfeature(SN, 5)}。在此基礎(chǔ)上，訓(xùn)練一個(gè)將MF映射到Y(jié)的元預(yù)測(cè)器MP。最終，當(dāng)對(duì)樣本Sk進(jìn)行實(shí)時(shí)預(yù)測(cè)時(shí)，首先分別采用演化模式預(yù)測(cè)器和機(jī)器學(xué)習(xí)預(yù)測(cè)器對(duì)其進(jìn)行預(yù)測(cè)，得到元特征向量MFk={MR(Sk),Ppattern(Sk, 1),…,Ppattern(Sk, 5),Pfeature(Sk, 1),…,Pfeature(Sk, 5)}。然后，采用元預(yù)測(cè)器MP對(duì)MFk進(jìn)行預(yù)測(cè)得到最終結(jié)果。

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)準(zhǔn)備

為進(jìn)行實(shí)驗(yàn)，從杭州市采集了如下真實(shí)數(shù)據(jù)集。

(1)交通擁堵指數(shù)數(shù)據(jù)集。從杭州市交通擁堵指數(shù)實(shí)時(shí)監(jiān)測(cè)平臺(tái)[25]上爬取了3年多的歷史交通擁堵指數(shù)數(shù)據(jù)(從2014年8月至2017年12月)。該數(shù)據(jù)集包含199條道路(其中一條雙向道路被認(rèn)為是兩條不同的道路)。原始交通擁堵指數(shù)每15分鐘發(fā)布一次，為預(yù)測(cè)日平均交通擁堵指數(shù)，對(duì)每天的交通擁堵指數(shù)求平均，最終得到229 709個(gè)樣本。

(2)道路網(wǎng)絡(luò)數(shù)據(jù)集。該數(shù)據(jù)集包含交通擁堵指數(shù)數(shù)據(jù)集涉及的199條道路，其中道路平均長(zhǎng)度為2.6 km，包括30條高架路、153條主干路、16條次干路。

(3)興趣點(diǎn)數(shù)據(jù)集。該數(shù)據(jù)集包含從百度地圖中采集的杭州市的39 305個(gè)興趣點(diǎn)(每個(gè)興趣點(diǎn)屬于居住、工作、商業(yè)、賓館、學(xué)校、交通、預(yù)測(cè)和景區(qū)的其中一個(gè)類(lèi)型)。

實(shí)驗(yàn)采用10折交叉驗(yàn)證作為測(cè)試方案(即90%的數(shù)據(jù)作為訓(xùn)練集，10%的數(shù)據(jù)作為測(cè)試集，測(cè)試重復(fù)10次取平均性能)。實(shí)驗(yàn)采用如下2個(gè)指標(biāo)進(jìn)行性能評(píng)價(jià)，即準(zhǔn)確率(ACC)和誤差(ERR)，計(jì)算方法如式(2)和式(3)所示。其中，pi和gi分別為測(cè)試樣本Si的預(yù)測(cè)值和真實(shí)值，x為真則I(x)=1，x為假則I(x)=0，n為測(cè)試樣本數(shù)量。

(2)

(3)

2.2 實(shí)驗(yàn)1演化模式預(yù)測(cè)器測(cè)試

第1個(gè)實(shí)驗(yàn)測(cè)試min_sup(演化模式最小支持度閾值)對(duì)預(yù)測(cè)性能的影響。首先，由于min_sup的值依賴于歷史交通擁堵指數(shù)離散值序列的長(zhǎng)度L(例如，若L較短，則應(yīng)設(shè)置一個(gè)較小的min_sup，以避免挖掘不出演化模式的情況)，導(dǎo)致其具體數(shù)值范圍難以確定。因此，設(shè)置一個(gè)取值范圍為(0, 1)的相對(duì)值min_sup_rate，并計(jì)算min_sup=min_sup_rate×L。然后，固定max_length=5，將min_sup_rate從0.05減少至0.0006以觀察演化模式預(yù)測(cè)器性能的變化，結(jié)果如圖4所示，其中“Day +k”指預(yù)測(cè)未來(lái)第k天的交通擁堵指數(shù)?？梢钥闯觯?dāng)min_sup_rate從0.05減少至0.01時(shí)，ACC明顯上升，而當(dāng)繼續(xù)減少min_sup_rate時(shí)，ACC的上升趨勢(shì)趨于穩(wěn)定，ERR的變化趨勢(shì)與此類(lèi)似。這是由于min_sup_rate較大時(shí)，則演化模式挖掘算法對(duì)演化模式的要求更為嚴(yán)格，因此挖掘出的演化模式數(shù)量更少、長(zhǎng)度更短，導(dǎo)致演化模式預(yù)測(cè)器的能力減弱。然而，將min_sup_rate設(shè)置的過(guò)小會(huì)極大地增加計(jì)算復(fù)雜度，且容易引入更多的噪聲[26]。綜上，將min_sup_rate設(shè)置為0.002。

圖4 參數(shù)min_sup_rate對(duì)演化模式預(yù)測(cè)器性能的影響

第2個(gè)實(shí)驗(yàn)測(cè)試max_length(當(dāng)前演化趨勢(shì)長(zhǎng)度)對(duì)預(yù)測(cè)性能的影響。首先，固定min_sup_rate=0.002，將max_length從1增加至10以觀察演化模式預(yù)測(cè)器性能的變化。如圖6所示，當(dāng)max_length增加時(shí)，ACC的變化趨勢(shì)是先明顯上升，再趨于穩(wěn)定(甚至有少量下降)，ERR的變化趨勢(shì)與此類(lèi)似。這說(shuō)明演化模式預(yù)測(cè)器的有效工作依賴于一定長(zhǎng)度的當(dāng)前演化趨勢(shì)。然而，由于挖掘出的演化模式長(zhǎng)度通常有限，max_length長(zhǎng)度過(guò)長(zhǎng)通常會(huì)引入過(guò)多無(wú)用甚至是噪聲的元素，導(dǎo)致模式匹配失敗。綜上，將max_length設(shè)置為7。

圖6 參數(shù)max_length對(duì)演化模式預(yù)測(cè)器性能的影響

第3個(gè)實(shí)驗(yàn)測(cè)試演化模式挖掘算法的計(jì)算復(fù)雜度。根據(jù)第2.2節(jié)的討論，參數(shù)head_range對(duì)算法的計(jì)算復(fù)雜度影響巨大，因此本實(shí)驗(yàn)探索在不同head_range取值的情況下演化模式挖掘算法的運(yùn)行耗時(shí)。算法的輸入為一條道路的所有歷史交通擁堵指數(shù)數(shù)據(jù)序列(長(zhǎng)度約為106 560)，min_sup_rate設(shè)置為0.002，實(shí)驗(yàn)采用的計(jì)算機(jī)配置為Intel雙核CPU(2.70 GHz × 2)、16GB內(nèi)存，程序采用Java語(yǔ)言編寫(xiě)。實(shí)驗(yàn)結(jié)果如圖7所示，可以看出隨著head_range的增大，算法運(yùn)行耗時(shí)急劇增加。此外，head_range設(shè)置的過(guò)大會(huì)破壞演化模式中元素在原始序列中的連續(xù)性。后續(xù)實(shí)驗(yàn)中將head_range設(shè)置為1。

圖7 head_range參數(shù)對(duì)演化模式挖掘算法運(yùn)行耗時(shí)的影響

2.3 實(shí)驗(yàn)2機(jī)器學(xué)習(xí)預(yù)測(cè)器測(cè)試

第1個(gè)實(shí)驗(yàn)測(cè)試參數(shù)h(時(shí)序特征中考慮前幾天的數(shù)據(jù))對(duì)預(yù)測(cè)性能的影響并確定參數(shù)取值。如圖8所示，當(dāng)h增大時(shí)，ACC逐漸上升而ERR逐漸降低，特別是h取值較小的時(shí)候。這說(shuō)明過(guò)去幾天的交通擁堵指數(shù)可有效用于對(duì)未來(lái)的交通擁堵指數(shù)的預(yù)測(cè)。然而，h增大到一定程度之后無(wú)法持續(xù)改善預(yù)測(cè)性能。綜上，將h設(shè)置為6。

圖8 參數(shù)h對(duì)機(jī)器學(xué)習(xí)預(yù)測(cè)器性能的影響

第2個(gè)實(shí)驗(yàn)驗(yàn)證靜態(tài)特征、動(dòng)態(tài)特征以及代價(jià)敏感學(xué)習(xí)機(jī)制的有效性。圖9比較了3種方法的預(yù)測(cè)性能，即Dynamic(僅使用動(dòng)態(tài)特征，基于代價(jià)敏感學(xué)習(xí)機(jī)制構(gòu)建機(jī)器學(xué)習(xí)預(yù)測(cè)器)、Dynamic + Static(使用所有特征，基于代價(jià)敏感學(xué)習(xí)機(jī)制構(gòu)建機(jī)器學(xué)習(xí)預(yù)測(cè)器)和RF(使用非代價(jià)敏感學(xué)習(xí)機(jī)制構(gòu)建機(jī)器學(xué)習(xí)預(yù)測(cè)器，這里所有特征都被使用，分類(lèi)模型采用隨機(jī)森林)。首先，Dynamic + Static的性能始終優(yōu)于Dynamic。這說(shuō)明靜態(tài)特征對(duì)交通擁堵指數(shù)預(yù)測(cè)任務(wù)是有效的。其次，與RF相比，Dynamic + Static的ACC較低，但ERR較高。這說(shuō)明代價(jià)敏感學(xué)習(xí)機(jī)制不能減少被錯(cuò)誤預(yù)測(cè)的測(cè)試樣本的數(shù)量(甚至?xí)黾?，但可以有效減少被錯(cuò)誤預(yù)測(cè)的測(cè)試樣本造成的總體損失。

圖9 不同方法設(shè)置的性能比較

2.4 實(shí)驗(yàn)3比較實(shí)驗(yàn)

將本文提出的方法(稱為OUR)與如下3個(gè)方法進(jìn)行比較：(1)PATTERN，即演化模式預(yù)測(cè)器；(2)FEATURE，即機(jī)器學(xué)習(xí)預(yù)測(cè)器；(3)LSTM，采用深度學(xué)習(xí)模型LSTM構(gòu)建交通擁堵指數(shù)預(yù)測(cè)模型[16]。實(shí)驗(yàn)結(jié)果如圖10所示，從圖中可以得出如下結(jié)論。

圖10 不同方法的性能比較

(1)當(dāng)預(yù)測(cè)較近的未來(lái)交通擁堵指數(shù)時(shí)(如Day +1)，F(xiàn)EATURE相比于PATTERN具有較為明顯的優(yōu)勢(shì)，而PATTERN的優(yōu)勢(shì)在預(yù)測(cè)較遠(yuǎn)的未來(lái)交通擁堵指數(shù)時(shí)逐漸顯示出來(lái)。這說(shuō)明演化模式可較好地捕捉長(zhǎng)期的交通擁堵指數(shù)變化規(guī)律。(2)LSTM在ACC上始終優(yōu)于FEATURE，這說(shuō)明深度學(xué)習(xí)模型的學(xué)習(xí)能力比傳統(tǒng)機(jī)器學(xué)習(xí)模型更強(qiáng)。然而，LSTM和FEATURE在ERR上的表現(xiàn)差別不大，這說(shuō)明代價(jià)敏感學(xué)習(xí)機(jī)制可更有效地減少預(yù)測(cè)誤差。(3)相比PATTERN和FEATURE，OUR的總體性能更優(yōu)。這說(shuō)明融合器能有效地利用演化模式預(yù)測(cè)器和機(jī)器學(xué)習(xí)預(yù)測(cè)器各自的優(yōu)勢(shì)，從而得到更準(zhǔn)確的預(yù)測(cè)結(jié)果。(4)LSTM在預(yù)測(cè)較近的未來(lái)交通擁堵指數(shù)時(shí)的性能比OUR要好，但OUR在預(yù)測(cè)較遠(yuǎn)的未來(lái)交通擁堵指數(shù)上表現(xiàn)更好。因此，在實(shí)用中，OUR和LSTM可作為互補(bǔ)的方法，即采用LSTM對(duì)短期交通擁堵指數(shù)進(jìn)行細(xì)粒度預(yù)測(cè)，采用OUR對(duì)長(zhǎng)期交通擁堵指數(shù)進(jìn)行粗粒度預(yù)測(cè)。

3 結(jié) 論

本文提出了一種融合演化模式和機(jī)器學(xué)習(xí)的交通擁堵指數(shù)預(yù)測(cè)方法。其中，演化模式預(yù)測(cè)器通過(guò)挖掘能夠捕捉交通擁堵指數(shù)長(zhǎng)期變化規(guī)律的演化模式實(shí)現(xiàn)預(yù)測(cè)，機(jī)器學(xué)習(xí)預(yù)測(cè)器通過(guò)學(xué)習(xí)交通擁堵指數(shù)與一系列交通特征的關(guān)聯(lián)實(shí)現(xiàn)預(yù)測(cè)?；谡鎸?shí)數(shù)據(jù)的實(shí)驗(yàn)發(fā)現(xiàn)，本文提出的方法一方面在預(yù)測(cè)粗粒度長(zhǎng)期交通擁堵指數(shù)任務(wù)上具有優(yōu)勢(shì)，另一方面能夠有效降低預(yù)測(cè)的總體損失。