KNN在短時交通流預(yù)測上的應(yīng)用與研究

林羅杰，殷鋒，袁平

（1.四川大學(xué)計算機學(xué)院，成都 610065；2.西南民族大學(xué)計算機科學(xué)與技術(shù)學(xué)院，成都 610041；3.重慶第二師范學(xué)院數(shù)學(xué)與信息工程學(xué)院，重慶 400067）

0 引言

智能交通系統(tǒng)（Intelligent Transportation System，ITS）的目標(biāo)是盡可能提高交通資源的利用率，并對其進行有效的控制和管理。為了達到這個目的，ITS需要對現(xiàn)有的交通狀態(tài)做出合適的響應(yīng)，除此之外，利用歷史數(shù)據(jù)和當(dāng)前狀態(tài)對未來的交通狀況做出及時、準(zhǔn)確的預(yù)測也是十分重要的一環(huán)，這將更好地幫助系統(tǒng)做出正確的決策。

針對交通流預(yù)測的研究和模型眾多，大致可以分為兩類：①基于統(tǒng)計學(xué)理論、②基于數(shù)據(jù)驅(qū)動?；诮y(tǒng)計學(xué)理論的方法一般基于某種特定的假設(shè)，例如時間序列分析中被廣泛應(yīng)用的ARIMA(自回歸積分移動平均)模型就建立在時間序列平穩(wěn)的基礎(chǔ)假設(shè)之上，在滿足條件的情況下才能進行后續(xù)的模型識別以及參數(shù)確定。除了時間序列分析之外，常見的基于統(tǒng)計學(xué)理論的預(yù)測方法還有歷史平均法、局部線性回歸法、卡爾曼濾波法等。該類方法大多比較簡單，計算方便，但是不能很好地應(yīng)對交通流的隨機特性，更適合做一些粗略的估計[1]?；跀?shù)據(jù)驅(qū)動的方法雖然研究時間起步較晚，但是隨著數(shù)據(jù)的增長以及機器學(xué)習(xí)的興起，近年來受到的關(guān)注也越來越多[2]?；跀?shù)據(jù)驅(qū)動的方法往往直接從數(shù)據(jù)中學(xué)習(xí)經(jīng)驗，不需要嚴(yán)格的先驗知識也能達到較好的預(yù)測效果，常見的模型有SVR（支持向量回歸）模型，KNN模型和基于神經(jīng)網(wǎng)絡(luò)的模型等，其中KNN模型作為一種簡單有效的數(shù)據(jù)驅(qū)動方法，已經(jīng)被廣泛運用于各種交通流預(yù)測研究之中。

1 理論基礎(chǔ)

1.1 短時交通流預(yù)測

交通流預(yù)測可以看作是一個指定興趣區(qū)域和時間間隔，并根據(jù)當(dāng)前交通狀態(tài)和歷史數(shù)據(jù)對下一個時間間隔的交通量進行預(yù)測的過程，常見的交通量有流量、速度、密度和旅行時間等。所謂短時交通流是相對長時交通流而言的，二者的區(qū)別體現(xiàn)在時間間隔上，前者的時間間隔一般不超過一個小時，一般用于對交通狀況實時地進行預(yù)測和管理；而后者的研究目標(biāo)通常是一整天或更長時間，一般用于對特定交通區(qū)域進行長期的預(yù)測和規(guī)劃。

從時間序列分析的角度來看，可以把預(yù)測問題定義為已知歷史交通流序列X=[X1，X2,…,Xi,…,XT-1]和當(dāng)前交通量XT，求下一時刻的交通量XT+1。其中T是當(dāng)前時段，T+1是要預(yù)測的下一時段，Xi對應(yīng)第i段時間間隔中采集的交通量數(shù)值，X1是歷史數(shù)據(jù)集的起始參照點。

1.2 KNN 方法

KNN方法本質(zhì)上是一種模式識別的方法，該方法通過某種相似性度量函數(shù)計算歷史狀態(tài)與當(dāng)前狀態(tài)的相似程度，如果能找到與當(dāng)前狀態(tài)最相似的K個歷史狀態(tài)（也稱作狀態(tài)向量），那么這K個歷史狀態(tài)就成為了的K個“近鄰”，“近鄰”的相關(guān)特性可用于評估當(dāng)下的狀態(tài)。

在交通流預(yù)測領(lǐng)域中，KNN方法最簡單的應(yīng)用方式就是將歷史時序數(shù)據(jù)“切片”構(gòu)建成樣本庫（每一個時間片就是一個狀態(tài)向量），當(dāng)有預(yù)測需求時，將當(dāng)前時間片與樣本庫中的時間片進行比對，選出最相似的K個時間片，然后對這K個時間片各自對應(yīng)的下一時間間隔的交通量進行累加求平均，方可求得預(yù)測值。

KNN方法的四個核心問題分別是：①如何選擇合適的狀態(tài)向量；②如何衡量狀態(tài)向量之間的相似性；③如何確定K的大小；④如何根據(jù)K個近鄰進行預(yù)測。上述過程只是簡單地利用了順序時序數(shù)據(jù)并使用累加求平均的方式獲得預(yù)測值，實際情況中往往需要考慮更多的因素，采取更復(fù)雜的算法，才能取得較好的預(yù)測效果。

2 相關(guān)應(yīng)用與發(fā)展

Smith團隊[3]早在1996年就提出了使用“非參數(shù)回歸模型”對高速公路流量進行預(yù)測，此處“非參數(shù)回歸模型”的核心就是KNN方法，該研究指出在構(gòu)建狀態(tài)向量時除了利用歷史時間序列之外，引入歷史平均值可以取得更優(yōu)的預(yù)測精度。另外，相較于傳統(tǒng)的建模方法只能預(yù)測未來最近的一個時間段而言，KNN方法可以一次性預(yù)測即將到來的多個時間段，實驗證明“多步預(yù)測”的預(yù)測效果與預(yù)測時間點有關(guān)，但總體效果在可以接受的范圍內(nèi)。1997年，該團隊[4]發(fā)現(xiàn)KNN方法在同一數(shù)據(jù)集上的預(yù)測效果要優(yōu)于HA（歷史平均）模型，ARIMA模型和神經(jīng)網(wǎng)絡(luò)模型，通過在兩個測試站點上的對比實驗，證明KNN方法的誤差分布情況最好，且不需要根據(jù)數(shù)據(jù)的變化而調(diào)整模型本身，泛化能力較好。2016年，F(xiàn)ilmon等人[5]對傳統(tǒng)的KNN方法進行了多個方面的改進，包括引入加權(quán)的歐氏距離，使用縮尾處理（winsorization）抑制占主導(dǎo)地位的“近鄰”和LOESS（局部估計散點平滑）技術(shù)，使平均絕對誤差相較于其他對照模型降低了25%以上。

KNN方法存在的一個問題是隨著數(shù)據(jù)庫的增大，搜索“鄰居”的時間也會隨之增加。數(shù)據(jù)的多樣性和完整性是KNN有效運行的前提，這要求歷史數(shù)據(jù)庫必須包含盡量多的交通狀態(tài)，如何減少搜索時間成為了保證算法實時性的關(guān)鍵。2015年，Marcin等人[6]發(fā)現(xiàn)最近的“鄰居”總是出現(xiàn)在一個相對較窄的時間段內(nèi)，于是提出了一種數(shù)據(jù)分割的方法，該方法可以通過“軟計算分析”從歷史時間序列中分割出對預(yù)測算法最有用的片段，這樣可以縮減匹配的規(guī)模，從而提升計算速度。同年，Meng等人[7]針對KNN搜索時間優(yōu)化的問題，提出應(yīng)該用平衡二叉樹（AVL）結(jié)構(gòu)取代傳統(tǒng)的線性結(jié)構(gòu)。首先采用聚類方法和AVL技術(shù)對數(shù)據(jù)庫進行更新，然后通過改良的KNN來預(yù)測未來的交通流，并在搜索的過程中兩次使用模式識別分別確定鄰居和模式的大小，實驗證明該方法可以有效提高實時搜索速度。

近年來，僅僅研究時間依賴對交通流的影響已經(jīng)不能滿足需求，越來越多的學(xué)者發(fā)現(xiàn)交通網(wǎng)絡(luò)中的空間依賴也會對預(yù)測產(chǎn)生影響。2016年，Yu等人[8]將預(yù)測站點的上下游鏈路信息考慮到預(yù)測算法中，并建立了四種不同的空間相關(guān)性KNN預(yù)測模型，發(fā)現(xiàn)考慮了空間因素的預(yù)測模型要優(yōu)于只考慮時間依賴的傳統(tǒng)模型，除此之外實驗數(shù)據(jù)還表明下游鏈路信息相對于上游鏈路信息而言更加重要。2018年，Unsok等人[9]認為現(xiàn)有的研究沒有全面地利用預(yù)測點周邊的空間信息，提出了一種利用互信息（Mutual Information）評價時空相關(guān)性的方法，該方法可以從多個與預(yù)測點相關(guān)的路段中挖掘出最相關(guān)和路段和滯后時延，并通過貪婪選擇算法構(gòu)建交通狀態(tài)向量，其效果優(yōu)于傳統(tǒng)KNN方法和普通時空模型。

3 分析展望

KNN方法的優(yōu)點是簡單，易于部署和泛化能力好。并且相對于傳統(tǒng)方法中需要對數(shù)據(jù)進行平滑處理和歷史平均等情況，KNN方法的比較對象往往是更加真實的數(shù)據(jù)，因此也更有可能捕捉到一些不常見的交通狀況，例如車輛突增、交通事故等。在實際應(yīng)用中，這些非典型的交通狀況更加需要被及時地發(fā)現(xiàn)，從而進行有效地管理，從這個層面來看KNN是一個很有潛力的預(yù)測方法。

數(shù)據(jù)庫的質(zhì)量對KNN方法的預(yù)測效果有很大的影響，理想的樣本數(shù)據(jù)庫應(yīng)該具有代表性，即能夠利用更少的數(shù)據(jù)覆蓋更多的交通狀況。另外，由于數(shù)據(jù)收集過程中難免出現(xiàn)設(shè)備損壞，統(tǒng)計錯誤等問題，異常數(shù)據(jù)和缺失數(shù)據(jù)對預(yù)測結(jié)果的影響也是不可忽視的。解決此類問題的方法通常是對應(yīng)用數(shù)據(jù)進行預(yù)處理，包括線性插值、閾值去噪等。從預(yù)測模型的角度來思考，如何設(shè)計出一種更加先進的KNN模型，使其對數(shù)據(jù)缺失和異常點的敏感度降低，提高算法的魯棒性也是值得研究的分支。針對時空關(guān)系的挖掘，無論是通過人工指定還是特定算法分析，大量的研究都發(fā)現(xiàn)空間依賴的引入的確可以提高預(yù)測的性能。但是如何科學(xué)地說明交通網(wǎng)絡(luò)中空間關(guān)系，怎樣利用空間依賴構(gòu)建合適的狀態(tài)向量，可能是下一步需要努力的方向。

無論是基于統(tǒng)計學(xué)理論的方法還是基于數(shù)據(jù)驅(qū)動的方法，現(xiàn)有的研究都沒有明確地指出某一方絕對優(yōu)于另一方。每種方法都有自己特定的適用場景，應(yīng)該根據(jù)具體的問題和需求選擇合適的方法。除此之外，如何將兩種甚至多種預(yù)測方法整合起來，發(fā)揮各自的優(yōu)勢以在更短的時間內(nèi)取得更優(yōu)的預(yù)測效果，這種混合模型也是當(dāng)下研究的主流之一。

4 結(jié)語

本文立足于KNN方法在交通流預(yù)測上的研究和應(yīng)用，介紹了該領(lǐng)域的基本任務(wù)以及KNN方法的原理和發(fā)展過程，并對KNN方法的優(yōu)劣和未來研究方向進行了簡單的分析。由于篇幅有限，本文沒有對現(xiàn)存的所有預(yù)測模型進行綜述，但我們有理由相信隨著各種科學(xué)理論和計算模型的不斷進步，今后會有越來越多優(yōu)秀的預(yù)測方法被應(yīng)用到該領(lǐng)域中來。