基于改進KNN算法的交通流異常數據修復方法

，，， ，

(上海工程技術大學 汽車工程學院，上海 201620)

0 引言

交通數據是智能交通系統(intelligent transportation system, ITS)中主要的數據支撐，可以直接反映交通的運行狀態，能夠為交通規劃、管理和決策提供重要的信息[1]。交通流數據質量的高低直接影響著交通流狀態分析的準確度。交通數據在實際獲取中，由于受到檢測器自身異常、傳輸網絡異常及環境因素等的影響，采集到的交通流數據難免會出現數據缺失、數據錯誤等質量問題[2]，對交通流數據分析以及交通管控精準性造成影響。因此，進行異常數據修復，提高交通流檢測數據的質量，是交通狀態辨識、交通管理及控制等工作正常進行的必然要求。

交通流異常數據修復方面的研究通常是基于歷史數據構建數據修復模型[3]。目前，對交通流異常數據修復方法的研究大致可以分為三類：一類是傳統數學模型，包括歷史趨勢法[4]、移動平均法[5]、插值法[6-7]、灰色殘差模型[8]等；第二類是智能修復方法，包括非參數回歸[9]、神經網絡[10]等；第三類是組合模型[11-12]，是指兩種或兩種以上的數據處理方法進行組合的方法。智能修復方法主要是采用機器學習算法對異常數據進行識別和修復，該方法是目前普遍采用的數據修復方式[13]。

K最近鄰(K-Nearest Neighbor，KNN)算法模型屬于非參數回歸方法，是一個理論上比較成熟的方法，也是最基本的機器學習算法之一。在交通領域中，KNN算法模型早期一般用于交通流預測。Davis和Nihan[14]率先運用k近鄰法的非參數理論方法對高速路交通流量進行預測。隨著KNN模型在交通領域的引入，有研究者針對如何提升k近鄰運算速度的問題進行了一系列探索[15-16]。隨后，于濱等[17]分析了k近鄰算法的時間和空間參數，提出4種狀態向量組合的k近鄰模型，通過優化算法參數來提高數據處理精度。謝海紅等[18]分析了原有的短時交通流預測的k近鄰算法，用模式距離搜索方法代替原有的歐氏距離搜索方法，引入多元統計回歸模型，建立了一種改進的k近鄰算法，結果表明，改進的k近鄰算法應用效果比原有k近鄰算法要好。Habtemichael F.G.[19]通過采用加權歐氏距離作為相似性度量標準，采用指數權重作為近鄰值權重，提出了非參數和數據驅動的短期交通流預測方法，結果證明其方法能有效提高預測精度。

目前KNN算法模型主要應用于交通流預測方面，在交通數據修復方面的應用和研究較少。因此，本文在對KNN算法特性分析的基礎上，通過對k值、修復狀態向量以及近鄰值權重等模型主要相關要素的優選和改進，進而構建基于改進KNN算法的交通流異常數據修復模型。研究結果旨在為交通流數據修復方法提供一種新的思路，為交通管控提供準確的基礎數據支持。

1 KNN異常數據修復模型

1.1 KNN基礎算法

KNN算法主要以數據為驅動，通過搜索歷史數據庫中與當前數據相似的狀態向量數據來進行數據修復。模型的基本流程如下：首先，構建具有較大容量且有代表性的歷史數據庫。其次，設定模型的相關要素，包括近鄰個數k，狀態向量，距離度量方式和修復算法等，其中近鄰個數k、狀態向量和距離度量方式組成了模型的搜索機制。最后，根據輸入的異常數據狀態向量和搜索機制，從歷史數據庫中找到與異常數據狀態向量相匹配的近鄰，利用修復算法得到修復后的交通數據值。

模型的運算速度和修復精度主要與4個要素密切相關：近鄰個數、狀態向量、距離度量方式、算法實施。模型性能的優劣很大程度上取決于這4個要素的選取。近鄰數k表示從歷史數據庫中選取與當前數據相似的數據組數，k值的選取主要與歷史數據庫有關。狀態向量作為當前數據與歷史數據庫實施匹配的一個匹配標準，表征了歷史數據庫中的數據特征。距離度量方式用于計算異常數據狀態向量與歷史數據庫中各個狀態向量之間的距離。修復算法構造了采用k組近鄰數據集修復異常數據值的方案。

1.2 改進KNN算法

異常數據修復是交通管控有效實施的基礎，采用KNN算法能夠實現在眾多的歷史數據組群中匹配到異常數據相似組群，進而實現對異常數據的修復。因此，本文提出基于改進KNN算法的異常數據修復方法。KNN異常數據修復模型實施過程如圖1所示。

針對出現異常的交通流數據，運用改進KNN算法對其異常數據進行修復，其實現方法具體步驟如下：

1)選取異常數據出現的同一監測點的正常交通流檢測器數據作為數據源，選取連續5個數據為一組，建立歷史數據狀態向量庫Xn。

2)識別異常數據，選取異常數據前后兩個時間間隔的正常數據，建立異常數據狀態向量X。

3)計算異常數據狀態向量X與歷史數據狀態向量庫Xn之間的歐式距離d，對其距離按照由小到大進行排序，記為di。

4)通過數據驗證平均相對誤差與k值的關系，對近鄰值個數k進行優選。

5)選取距離占比的近鄰值權重選取方式。

7)對異常值進行刪除，并填補修復后的數值。

本文在對KNN基礎模型以及交通流數據特性分析的基礎上，對KNN基礎模型的改進主要體現為三點：一是對k值進行優選；二是考慮異常數據前后時刻的關聯數據，建立了狀態向量；三是提出了一種新的近鄰值權重選取方式。

1)參數k優化選取:

近鄰值個數k表示從歷史數據庫中選取的近鄰個數，k值大小是影響算法計算時間和數據修復精度的一個重要因素。一般情況下，k值越大，修復精度越高但其運算時間會相應增加。

由圖2可知，隨著k值的增大，平均相對誤差不斷減小，并逐漸趨于平緩。當k值為25時，圖形基本收斂，隨著k值再增大，平均相對誤差已無明顯變化。因此本文優選k值為25。

圖2 平均相對誤差與k值的關系

2)狀態向量建立:

分別建立歷史數據狀態向量庫和異常數據狀態向量。

目前對交通流異常數據的修復，通常考慮的是利用異常數據的前向數據對其進行修復。圖3表示一段時間內交通流速度變化趨勢。從圖中可以看出，交通流速度隨著時間的變化，具有不確定性、波動性和隨機時變特性。交通流數據自身具有一定的特征和規律，相鄰時間之間的數據具有某種關聯性，前一時刻速度大小會影響后一時刻速度大小，數據之間具有很強的連續性和關聯性。并且時間距離越近的數據之間關聯性越大[20]。

圖3 交通流速度數據趨勢圖

(1)

3)距離度量:

距離度量方式是用于度量異常數據狀態向量與歷史數據庫中各個狀態向量之間的相似程度，一般采用歐氏距離作為衡量標準：

(2)

4)修復算法構建:

修復算法構造了采用k組近鄰數據集修復異常數據值的方案，即:

(3)

尋找到的k個最近鄰中，距離越近，說明此近鄰值與當前異常數據狀態向量的相似度越大。為了提高其修復精度，采取對其近鄰值賦予權重的方式，距離越近的近鄰值，賦予的權重越大。

關于近鄰值權重的選取，現有的k近鄰權重選取方式主要有距離倒數權重和排隊指數權重兩種，分別定義為權重1、權重2。如式(4)、式(5)。

距離倒數權重：

(4)

排隊指數權重：

(5)

在現有權重的基礎上，根據KNN算法的基本原理，綜合考慮算法復雜度和計算速度，提出距離占比的權重選取方式，定義為權重3，如式(6)。

距離占比權重：

(6)

式中,αi是第i組近鄰值；k指近鄰值的個數；di是當前異常數據狀態向量與歷史數據庫中第i組狀態向量數據之間的歐式距離；di是第i個近鄰值的權重。

2 實驗驗證

2.1 評價指標

本文采用平均相對誤差為主要評價指標，均方根誤差、相關系數評價指標作為輔助對交通流異常數據修復的有效性進行評價。平均相對誤差(MAPE)表示修復值與真實值之間相對誤差的均值，其值越小表示修復效果越好。均方根誤差(RMSE)表示修復值和真實值之間的偏差，可以反映其修復能力，誤差值低表示效果好。計算公式分別為：

(7)

(8)

相關系數r表示修復值和真實值之間的相似程度，其值大小范圍為[-1,1]。其絕對值大小代表了數據之間的相關程度，負號表示數據關系為負相關，其絕對值越接近1表示相關性越強。計算公式如下：

(9)

2.2 數據來源與處理

本文選取山東某高速公路監測點獲取的實際交通流速度數據作為實驗樣本數據。為了更好地反映交通流量的運行情況，把交通速度數據合成為5分鐘時間間隔的速度數據。選取60天正常交通流速度數據作為實驗樣本數據，其中90%作為歷史數據庫樣本，10%作為測試數據樣本。部分交通流速度數據示例如表1所示。

表1 部分交通流速度數據示例

2.3 結果比較與討論

2.3.1 不同k值的結果比較

為了檢驗改進后的KNN數據修復模型的整體修復效果，用實驗數據分析了3種KNN模型進行數據修復的平均相對誤差和近鄰值k的關系，并與常用的數據修復方法移動平均法相對比，結果如圖4所示。

圖4 平均相對誤差與k值的關系

從圖4中可以看出：

1)當k值大于6時，帶權重2的KNN模型的修復效果優于移動平均法，當k值大于4時，帶權重1、3的KNN模型修復效果優于移動平均法。由此可以得出，相比較移動平均法，KNN修復模型的異常數據修復效果明顯較好，說明KNN模型適用于數據修復，采取k近鄰的思想進行數據修復的方法可行。

2)隨著k值的增大，3種KNN數據修復模型的平均相對誤差不斷降低，并逐漸趨于平緩，權重3的KNN修復模型所得修復結果的平均相對誤差值比權重1和權重2修復模型的誤差值小，說明改進的KNN數據修復模型的整體修復效果優于另兩種權重KNN模型的整體修復效果。

2.3.2 不同模型結果比較

將平均相對誤差、均方根誤差、相關系數3種指標作為修復算法的誤差評估方式對實驗結果進行全面評價。將3種KNN數據修復模型和傳統移動平均法4種方法的修復結果進行比較，見圖5、圖6和表2。

圖5 平均相對誤差

圖6 均方根誤差

修復方法相關系數rKNN修復模型權重10.72權重20.71權重30.73移動平均法0.66

圖5顯示了4種修復方法實驗結果的平均相對誤差(MAPE)結果比較。平均相對誤差反映了交通流量數據修復值偏離真實值的程度。其值越小表示修復值與真實值的偏離程度越小，說明兩者越相近。

從圖5中可以看出，4種修復方法實驗結果的平均相對誤差值大小依次為9.93%、10.1%、9.88%、10.23%。由誤差值大小可以看出，KNN修復模型的誤差值大小明顯小于移動平均法，權重3修復模型的誤差值要小于另兩種權重修復模型。

圖6顯示了4種修復方法實驗結果的均方根誤差(RMSE)結果比較。表1顯示了采用4種方法進行數據修復實驗的修復值與真實值之間的相關系數r。相關系數表示修復數據與實際數據之間的相似性，其值越接近1表示修復值與真實值的相關度越高，修復效果越好。

從圖6可以看出，4種修復方法實驗結果的均方根誤差值大小依次為10.88、11.07、10.82、12.23。從表1可以得知，在KNN修復模型中，權重3的KNN修復模型的修復值與真實值的相關系數最大，為0.73，權重1和權重2的KNN修復模型次之，分別為0.72和0.71，移動平均法的相關系數最小，為0.66。

由此可以得出，3種KNN數據修復模型的修復效果明顯優于移動平均法的修復效果，權重3的KNN修復模型的修復精度明顯高于權重2的修復模型，略高于權重1的修復模型，其平均相對誤差大小為9.88%。由此可以說明采用改進后的KNN異常數據修復模型進行數據修復取得了較好的修復效果。

為了更好的體現改進KNN修復模型的優勢，本文還分析了各個方法實驗結果的相對誤差在不同誤差范圍內所占的比例。圖7表示采用4種修復方法實驗結果的修復值與真實值的相對誤差在[0,20%)、[20%,+∞)內的數據個數所占比例。可以看出，采用KNN修復模型的相對誤差小于20%的占比高于移動平均法，大于20%的占比低于移動平均法。在KNN修復模型中，權重3的修復模型，其相對誤差值在[0,20%)范圍內的占比最大。這說明改進后KNN修復模型的修復效果能夠滿足數據修復精度需求。

圖7 相對誤差占比

3 結論

針對目前交通流數據異常和數據質量不高的問題，將k近鄰模型引用到數據修復中。對KNN基礎模型相關要素進行改進和優化，建立了一種適用于交通流數據修復的KNN異常數據修復模型。通過實際數據驗證，可得出以下結論：

1)提出基于改進KNN算法的異常數據修復模型，該修復模型與傳統的移動平均修復方法相比，具有更優的修復精度，其平均相對誤差值為9.88%，能夠滿足基本的異常數據修復精度需求。

2)針對KNN算法模型，進行k值和狀態向量的優選、提出一種距離占比的近鄰值權重選取方式，進而實現對基礎模型的改進。結果表明，采用距離占比的近鄰值權重方式的KNN數據修復模型能夠有效提高數據修復精度，具有更好的數據修復效果。

本文所提出的數據修復方法實施性較強，可有效提升交通流數據質量，其修復思想對交通數據在實際應用方面具有理論指導意義。