基于演化模式挖掘和代價敏感學習的交通擁堵指數(shù)預(yù)測①

張翔宇 張 強 呂明琪*

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

0 引 言

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

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

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

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

1 方 法

1.1 方法總體框架

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

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

圖1 本文方法的總體框架

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

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

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

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

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

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

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

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

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

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

1.3 機器學習預(yù)測器

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

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

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

(2)時間特征。時間特征包括待預(yù)測天是星期幾、是否是假期。時間特征向量記為Tk。

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

(1)

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

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

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

1.4 融合器

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

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

2 實 驗

2.1 實驗準備

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

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

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

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

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

(2)

(3)

2.2 實驗1演化模式預(yù)測器測試

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

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

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

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

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

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

2.3 實驗2機器學習預(yù)測器測試

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

圖8 參數(shù)h對機器學習預(yù)測器性能的影響

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

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

2.4 實驗3比較實驗

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

圖10 不同方法的性能比較

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

3 結(jié) 論

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