KNN在短時交通流預測上的應用與研究

林羅杰，殷鋒，袁平

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

0 引言

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

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

1 理論基礎

1.1 短時交通流預測

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

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

1.2 KNN 方法

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

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

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

2 相關應用與發展

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

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

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

3 分析展望

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

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

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

4 結語

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