基于K近鄰與主成分分析的短時(shí)交通流預(yù)測(cè)

李 翠， 黃 侃， 李 霞

(江西交通職業(yè)技術(shù)學(xué)院 信息工程學(xué)院， 南昌 330013)

交通流數(shù)據(jù)為智能交通系統(tǒng)ITS(Intelligent Transportation System)的正常運(yùn)行提供了數(shù)據(jù)支撐，其中蘊(yùn)含的交通時(shí)空分布規(guī)律對(duì)現(xiàn)代交通的科學(xué)管理與決策、交通流的基礎(chǔ)理論研究具有重要利用價(jià)值[1]。ITS已在世界范圍內(nèi)廣泛應(yīng)用，并成為了高速公路和城市道路交通控制的有力工具。為了實(shí)現(xiàn)有效的交通控制和交通誘導(dǎo)，需在做出控制(誘導(dǎo))變量決策的時(shí)刻對(duì)下一決策時(shí)刻乃至以后若干時(shí)刻的交通流量做出實(shí)時(shí)、準(zhǔn)確的預(yù)測(cè)(即短時(shí)交通流預(yù)測(cè))。短時(shí)交通流預(yù)測(cè)一般不超過(guò)15 min的時(shí)間跨度[2]。

有關(guān)短時(shí)交通流預(yù)測(cè)的算法大致可劃分為3類[3-10]：第一類是基于傳統(tǒng)數(shù)理統(tǒng)計(jì)模型的算法，也可稱為參數(shù)法，主要包括歷史均值法[3]、時(shí)間序列法[4]、卡爾曼濾波法[5]等。該類算法模型簡(jiǎn)單、編程方便，但受交通流非線性和隨機(jī)性的影響，此類算法在較短預(yù)測(cè)周期下的預(yù)測(cè)精度較差。第二類是基于人工智能模型的算法，又稱為非參數(shù)法，主要包括神經(jīng)網(wǎng)絡(luò)法[6]、非參數(shù)回歸法[7]、支持向量機(jī)法[8]等。該類算法可充分逼近任意復(fù)雜的非線性和隨機(jī)性交通流序列，對(duì)短時(shí)交通流具有較好的預(yù)測(cè)效果，但存在參數(shù)設(shè)置困難、收斂速度慢等不足。第三類是基于混合模型的算法，即將前2類算法中的2個(gè)或多個(gè)預(yù)測(cè)模型進(jìn)行組合[9-10]。該類算法依賴于不同模型之間的協(xié)調(diào)，有利于預(yù)測(cè)精度的提高，但其參數(shù)調(diào)整依然是個(gè)難題。

K近鄰(K-nearest neighbors，KNN)是一種常用的非參數(shù)回歸方法，KNN法完全由數(shù)據(jù)驅(qū)動(dòng)而無(wú)需假設(shè)數(shù)據(jù)的分布模式，原理簡(jiǎn)單且易于擴(kuò)展[11-12]。相關(guān)研究主要針對(duì)狀態(tài)向量構(gòu)造、近鄰距離計(jì)算和近鄰權(quán)重選取等關(guān)鍵問(wèn)題展開(kāi)，取得了較多成果[13-14]。主成分分析PCA(Principle component analysis)是一種統(tǒng)計(jì)方法[15]，該方法通過(guò)正交變換將一組可能存在相關(guān)性的變量轉(zhuǎn)換為一組線性不相關(guān)的變量，轉(zhuǎn)換后的這組變量稱為主成分。任意向量均可表達(dá)為主成分的線性組合，組合系數(shù)則反映主成分對(duì)該向量的貢獻(xiàn)程度?，F(xiàn)有方法一般將PCA結(jié)合智能算法進(jìn)行短時(shí)交通流預(yù)測(cè)[16]，同樣存在參數(shù)難以確定和收斂速度慢等問(wèn)題。

本文將KNN法和PCA法相結(jié)合，提出用于短時(shí)交通流預(yù)測(cè)的KNN-PCA法，以期提供新的研究思路。

1 KNN法基本原理

1.1 計(jì)算流程

KNN法完全由數(shù)據(jù)驅(qū)動(dòng)，通過(guò)搜索歷史數(shù)據(jù)庫(kù)來(lái)尋找具有合適數(shù)量的、與當(dāng)前數(shù)據(jù)相似的多個(gè)近鄰，并對(duì)近鄰數(shù)據(jù)進(jìn)行加權(quán)組合以實(shí)現(xiàn)預(yù)測(cè)功能。KNN法的基本流程如下：1) 構(gòu)造具有較大容量且有代表性的歷史數(shù)據(jù)庫(kù)；2) 設(shè)定合適的狀態(tài)向量；3) 計(jì)算當(dāng)前交通流狀態(tài)向量與歷史數(shù)據(jù)狀態(tài)向量之間的距離；4) 設(shè)定距離閾值后確定近鄰個(gè)數(shù)k；5) 計(jì)算近鄰權(quán)重；6) 對(duì)k個(gè)近鄰進(jìn)行加權(quán)計(jì)算以獲得預(yù)測(cè)值。

由以上基本流程可知，KNN法的預(yù)測(cè)性能取決于狀態(tài)向量的構(gòu)造方式、距離的度量方式、近鄰的篩選規(guī)則和近鄰權(quán)重的計(jì)算方法。

1.2 狀態(tài)向量的構(gòu)造

當(dāng)前交通流的狀態(tài)向量為：

A=[at-p+1at-p+2…at-1at]T

(1)

式中：ai為第i個(gè)時(shí)刻采集的交通流量數(shù)據(jù)；p為狀態(tài)向量長(zhǎng)度；T表示轉(zhuǎn)置。

相應(yīng)地，設(shè)定歷史數(shù)據(jù)狀態(tài)向量為：

Hi=[hi,t-p+1hi,t-p+2…h(huán)i,t-1hit]Ti=1,2,…,q

(2)

式中：hij為第i個(gè)歷史數(shù)據(jù)狀態(tài)向量在第j個(gè)時(shí)刻采集的交通流量數(shù)據(jù)；q為歷史數(shù)據(jù)狀態(tài)向量的數(shù)量。

1.3 近鄰的篩選指標(biāo)

常用歐式距離來(lái)匹配當(dāng)前交通流和歷史數(shù)據(jù)的狀態(tài)向量，以便篩選用于短時(shí)交通流預(yù)測(cè)的近鄰。當(dāng)前交通流狀態(tài)向量與第i個(gè)歷史數(shù)據(jù)狀態(tài)向量之間的歐式距離為：

(3)

由于相關(guān)系數(shù)更能反映狀態(tài)向量的相似性，有利于判斷相似交通流，因此采用相關(guān)系數(shù)來(lái)代替歐式距離進(jìn)行近鄰的篩選。當(dāng)前交通流狀態(tài)向量與第i個(gè)歷史數(shù)據(jù)狀態(tài)向量之間的相關(guān)系數(shù)為：

(4)

根據(jù)式(3)或式(4)，可將歐式距離最小或相關(guān)系數(shù)最大的k個(gè)歷史數(shù)據(jù)狀態(tài)向量視作當(dāng)前交通流狀態(tài)向量的近鄰。

1.4 交通流量的預(yù)測(cè)

根據(jù)所挑選的近鄰來(lái)確定第t+1時(shí)刻的交通流量預(yù)測(cè)值：

(5)

式中：αi為第i個(gè)近鄰的權(quán)重；k為近鄰數(shù)量；hi,t+1為第i個(gè)近鄰在第t+1時(shí)刻的實(shí)測(cè)交通流量。歷史均值法和距離倒數(shù)法計(jì)算距離權(quán)重的公式分別為：

αi=1/k

(6)

(7)

2 KNN-PCA法基本原理

2.1 計(jì)算原理

將所有近鄰均延拓至第t+1時(shí)刻，得到新的向量為：

(8)

通過(guò)奇異值分解，對(duì)這些近鄰延拓向量進(jìn)行PCA[15]，即

(9)

式中：U= [u1u2…up+1]為由特征向量組成的酉矩陣，或稱主成分矩陣；S= diag (S1,S2, …,Sp+1)為對(duì)角矩陣；Si為特征值，且S1≥S2≥ … ≥Sp+1≥ 0(i=1,2,…,p+1)。

將當(dāng)前交通流狀態(tài)向量也延拓至第t+1時(shí)刻，得到新的向量為：

Ae=[at-p+1at-p+2…atat+1]T

(10)

進(jìn)一步將Ae近似表達(dá)為前m階起主要貢獻(xiàn)的主成分的線性組合，即

Ae=[u1u2…um]β=Umβ

(11)

式中：β為主成分組合系數(shù)構(gòu)成的列向量；Um為由前m階起主要貢獻(xiàn)主成分構(gòu)成的矩陣。由于at+1為待預(yù)測(cè)值，因此基于已測(cè)的p個(gè)數(shù)據(jù)，得到式(11)的最小二乘解為：

(12)

利用式(12)計(jì)算的組合系數(shù)對(duì)Ae′進(jìn)行重構(gòu)，得到：

Ae′=Umβ

(13)

Ae′中最后一個(gè)元素即為第t+1時(shí)刻的預(yù)測(cè)值at+1，其表達(dá)式為：

at+1=Ae′(end)

(14)

式中：end表示取最后一個(gè)元素。

由式(12)、式(13)可知，PCA法其實(shí)提供了一種新的近鄰權(quán)重計(jì)算方法。與歷史均值法式(6)和距離倒數(shù)法式(7)提供的經(jīng)驗(yàn)公式不同，PCA法提供了自適應(yīng)公式，即近鄰權(quán)重根據(jù)主成分的貢獻(xiàn)進(jìn)行自動(dòng)計(jì)算。

2.2 計(jì)算流程

KNN-PCA法的計(jì)算流程為：

1) 按式(1)、式(2)構(gòu)造狀態(tài)向量；

2) 按式(4)計(jì)算相關(guān)系數(shù)；

3) 挑選相關(guān)系數(shù)最大的前k個(gè)歷史數(shù)據(jù)作為近鄰；

4) 基于式(8)、式(9)計(jì)算主成分；

5) 采用式(12)計(jì)算主成分組合系數(shù)；

6) 利用式(13)、式(14)計(jì)算預(yù)測(cè)值。

3 評(píng)價(jià)指標(biāo)

采用以下3種常用的評(píng)價(jià)指標(biāo)來(lái)衡量各種算法的預(yù)測(cè)精度，包括均方根誤差(RMSE)、平均誤差(MAE)和平均百分比誤差(MAPE)，表達(dá)式分別為：

(15)

(16)

(17)

4 算例分析

4.1 數(shù)據(jù)來(lái)源與處理

以明尼蘇達(dá)大學(xué)交通數(shù)據(jù)研究實(shí)驗(yàn)室(TDRL)在2018年1月12日—2019年1月12日(共366 d)采集的交通流量數(shù)據(jù)(第250號(hào)測(cè)點(diǎn))為例展開(kāi)分析[17]。原始數(shù)據(jù)的采樣間隔為30 s，每d共有2 880個(gè)采樣點(diǎn)。經(jīng)統(tǒng)計(jì)，共有335 d未出現(xiàn)異常數(shù)據(jù)。將這些正常數(shù)據(jù)按15 min采樣間隔重新整理(共有96個(gè)采樣點(diǎn))，并將前334 d的數(shù)據(jù)作為歷史數(shù)據(jù)，將最后1 d的數(shù)據(jù)作為測(cè)試數(shù)據(jù)。

4.2 參與比較的預(yù)測(cè)算法

為更好地比較預(yù)測(cè)性能，考慮6種不同的KNN算法，如表1所示。算法1～3采用相關(guān)系數(shù)式(4)來(lái)篩選近鄰，而算法4～6則采用歐式距離式(3)。算法1即為本文提出的KNN-PCA法。6種算法的計(jì)算流程均可參照2.4節(jié)執(zhí)行。

表1 6種交通流預(yù)測(cè)算法

4.3 近鄰數(shù)k的取值

在篩選近鄰時(shí)，每個(gè)預(yù)測(cè)時(shí)刻對(duì)應(yīng)的最優(yōu)k值(即近鄰數(shù))往往難以預(yù)先確定，故采用動(dòng)態(tài)方法確定k值。對(duì)算法1～3，按式(4)計(jì)算相關(guān)系數(shù)，并將相關(guān)系數(shù)大于0.95的歷史數(shù)據(jù)視作近鄰，且k值至少取5，至多取10。算法4～6的k值與算法1～3的相同。對(duì)算法4～6，按式(3)計(jì)算歐式距離，并將歐式距離最小的k個(gè)歷史數(shù)據(jù)取為近鄰。

4.4 主成分分析

以算法1為例，設(shè)定狀態(tài)向量長(zhǎng)度p=35，并隨機(jī)選取測(cè)試數(shù)據(jù)第15、48、72和91個(gè)預(yù)測(cè)時(shí)刻進(jìn)行主成分分析。根據(jù)式(9)進(jìn)行奇異值分解后，各得到35階特征值(由大到小排序)，并將其對(duì)最大值歸一化。將前10階歸一化特征值列于表2，其余未列出的值均小于0.000 001。由表2可知，對(duì)所有預(yù)測(cè)時(shí)刻，第1階特征值均遠(yuǎn)大于其他階特征值。這表明第1階主成分對(duì)這些近鄰的貢獻(xiàn)最大，反映了它們共同的主要變化趨勢(shì)。

若將閾值設(shè)為0.000 001，則歸一化特征值大于該閾值的那些主成分對(duì)延拓后的狀態(tài)向量起主要貢獻(xiàn)。這4個(gè)預(yù)測(cè)時(shí)刻起主要貢獻(xiàn)的主成分?jǐn)?shù)量m分別為10、10、5和9。根據(jù)式(12)計(jì)算這些主成分對(duì)當(dāng)前交通流狀態(tài)向量的組合系數(shù)，如表3所示。

由表3可知，第1階主成分遠(yuǎn)比其他主成分的組合系數(shù)要大。此外，其他階主成分的組合系數(shù)(絕對(duì)值)并不完全與表1所示的特征值排序相同。這是由于特征值大小反映的是主成分對(duì)所有近鄰共同變化趨勢(shì)的貢獻(xiàn)，而組合系數(shù)則僅反映主成分對(duì)當(dāng)前交通流變化趨勢(shì)的貢獻(xiàn)。

表2 前10階歸一化特征值(算法1)

表3 前m階主成分對(duì)當(dāng)前交通流狀態(tài)向量的組合系數(shù)

4.5 預(yù)測(cè)結(jié)果

按照4.3、4.4節(jié)所述方法確定近鄰數(shù)k值和起主要貢獻(xiàn)的主成分?jǐn)?shù)量m值，并改變狀態(tài)向量長(zhǎng)度p。分別計(jì)算6種算法的預(yù)測(cè)結(jié)果，并將3種評(píng)價(jià)指標(biāo)RMSE、MAE和MAPE隨p值的總體變化趨勢(shì)和局部變化趨勢(shì)分別繪于圖1、圖2。

由圖1可知，在p較小時(shí)，算法1～4的3種評(píng)價(jià)指標(biāo)均較差，且波動(dòng)很大；算法5～6的評(píng)價(jià)指標(biāo)相對(duì)較好，但依然存在一定波動(dòng)。隨著p的增大，所有算法的3種評(píng)價(jià)指標(biāo)波動(dòng)范圍逐漸收窄且趨于穩(wěn)定。由圖2可知，沒(méi)有哪種算法能夠在所有評(píng)價(jià)指標(biāo)中一直保持最佳。比如，算法6在p介于48～72之間時(shí)具有最小的RMSE，但卻具有較大的MAE和MAPE。這說(shuō)明，難以確定合適的p值讓某種算法在所有評(píng)價(jià)指標(biāo)上均表現(xiàn)最佳。

總的來(lái)說(shuō)，算法1在p=32～96時(shí)波動(dòng)較為平穩(wěn)，特別是在p=93～96時(shí)，3種評(píng)價(jià)指標(biāo)均較小。相比其他算法，算法1的3種指標(biāo)在p=93～96時(shí)也均最佳。因此，在采用算法1進(jìn)行計(jì)算時(shí)，可將狀態(tài)向量長(zhǎng)度p取為96，即與每d的數(shù)據(jù)長(zhǎng)度相同。

(a) RMSE指標(biāo)

(b) MAE指標(biāo)

(c) MAPE指標(biāo)

(a) RMSE指標(biāo)(局部放大)

(b) MAE指標(biāo)(局部放大)

(c) MAPE指標(biāo)

6種算法在p=48、72、96時(shí)的預(yù)測(cè)結(jié)果如圖3所示。不難發(fā)現(xiàn)，算法1、算法4能很好地反映真實(shí)交通流的總體變化趨勢(shì)，尤其在交通流量較大的時(shí)間段(j=40～72時(shí))，這2種算法的預(yù)測(cè)值與真實(shí)值更為吻合。注意到算法1、算法4均對(duì)近鄰進(jìn)行了PCA，這表明PCA有利于預(yù)測(cè)交通流的總體變化趨勢(shì)。但也應(yīng)當(dāng)注意，在交通流變化較為劇烈的時(shí)刻(如j=67、68)，算法1、算法4的預(yù)測(cè)結(jié)果跟真實(shí)值依然存在一定偏差，這種現(xiàn)象是因交通流存在較大的隨機(jī)性所致。

進(jìn)一步比較算法1、算法4在p=48、72、96時(shí)的評(píng)價(jià)指標(biāo)如圖2所示，由此可知算法1總體上比算法4的預(yù)測(cè)性能更好一些，這表明采用相關(guān)系數(shù)比采用歐式距離來(lái)篩選近鄰更有利于保證KNN-PCA法的短時(shí)交通流預(yù)測(cè)精度。

(a) p=48

(b) p=72

(c) p=96

5 結(jié)束語(yǔ)

1) 6種KNN算法的預(yù)測(cè)性能與狀態(tài)向量長(zhǎng)度密切相關(guān)，難以確定合適的p值讓某種算法在所有評(píng)價(jià)指標(biāo)上均表現(xiàn)最佳。

2) 對(duì)篩選出來(lái)的近鄰進(jìn)行PCA，可提取反映近鄰主要變化趨勢(shì)的主成分，有利于預(yù)測(cè)當(dāng)前交通流的變化趨勢(shì)。

3) KNN-PCA法的預(yù)測(cè)結(jié)果能很好地反映真實(shí)交通流的總體變化趨勢(shì)，尤其在交通流量較大的時(shí)間段，預(yù)測(cè)值與真實(shí)值更為吻合。

4) 采用相關(guān)系數(shù)比采用歐式距離來(lái)篩選近鄰更有利于保證KNN-PCA法的預(yù)測(cè)精度。此外，將1 d的數(shù)據(jù)長(zhǎng)度作為KNN-PCA法的狀態(tài)向量長(zhǎng)度較為合適。

5) 提出的KNN-PCA法可用于高速公路的短時(shí)交通流預(yù)測(cè)，該方法原理清晰、計(jì)算簡(jiǎn)單、無(wú)需迭代。