李翠，黃侃，李霞

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

交通流數據為智能交通系統(tǒng)的正常運行提供數據支撐，其中蘊含的交通時空分布規(guī)律對現代交通的科學管理與決策及交通流的基礎理論研究具有重要價值。但由于設備故障、傳輸問題和處理錯誤等原因，現場采集的交通流數據經常出現錯誤與缺失等異常現象，需對異常數據進行修復處理。

交通流具有很強的周期性和隨機性，因而?；跉v史數據建立交通流異常數據修復模型。常見修復方法可分為傳統(tǒng)數學方法、智能方法和混合方法，其中智能方法包括非參數回歸法、深度學習法等。作為一種非參數回歸方法，K近鄰算法(K-Nearest Neighbors，KNN)完全由數據驅動而無需假設數據的分布模式，原理簡單且易于擴展。在交通領域，KNN法主要用于交通流預測。近年來，將KNN算法應用于交通流異常數據修復的研究也受到關注，如文獻[8]通過優(yōu)選近鄰數量和調整近鄰權重來修復交通流異常數據，但僅討論了異常數據非連續(xù)分布的情況。實際上，異常數據的位置是隨機的，也存在連續(xù)分布的情況。為適應異常數據隨機出現的特點，該文提出改進KNN算法來實現交通流異常數據的修復。

1 KNN法的基本原理

KNN法完全由數據驅動，通過搜索歷史數據庫尋找具有合適數量、與當前數據(包含異常數據)相似的多個近鄰，并對近鄰數據進行加權組合以實現異常數據的修復。基本流程為構造具有較大容量且有代表性的歷史數據庫→設定合適的狀態(tài)向量→計算異常數據狀態(tài)向量與歷史數據狀態(tài)向量之間的距離→設定距離閾值后選取近鄰個數k→選取近鄰權重計算方式→對k個近鄰進行加權計算，獲得異常數據修復值。

根據以上流程，KNN法的修復性能同時取決于狀態(tài)向量的構造方式、狀態(tài)向量之間距離的度量方式及近鄰個數和近鄰權重的選取方法。狀態(tài)向量作為當前數據與歷史數據相似程度的匹配模式，表征歷史數據庫中的數據特征。距離度量方式用于計算異常數據狀態(tài)與歷史數據庫中各狀態(tài)向量之間的距離。近鄰個數k表示從歷史數據庫中選取與當前數據相似的數據組數，k值的確定與歷史數據庫的容量及設定的距離閾值相關。各近鄰的權重系數一般按經驗指定，決定k個近鄰對修復異常數據的貢獻。

2 改進KNN算法

篩選近鄰之前需構造狀態(tài)向量。狀態(tài)向量的長度一般較小，如文獻[8]僅利用5個連續(xù)采樣點來構造狀態(tài)向量，狀態(tài)向量中間的元素為異常數據。這么短的狀態(tài)向量很難滿足隨機出現且連續(xù)分布的異常數據修復需求，利用較多的采樣點來構造較長的狀態(tài)向量更合適。此外，近鄰的篩選方式及近鄰權重的取值都應進行改進，以提高修復精度。

2.1 狀態(tài)向量的構造

歷史數據狀態(tài)向量為：

Hi=[hi1，hi2，…，hin]T；i=1,2,3,…,p

(1)

相應地，某待修復的異常數據狀態(tài)向量為：

A=[a1，a2，…，an]T

(2)

式中：ai為異常數據狀態(tài)向量的第i個采樣點。

需指出的是，A中同時包含正常數據和異常數據。

2.2 近鄰的篩選指標

常用歐式距離衡量2個狀態(tài)向量之間的匹配程度(相似程度)，以便從歷史數據狀態(tài)向量庫中篩選出異常數據狀態(tài)向量的近鄰。歐式距離的表達式為：

(3)

式中：li為異常數據狀態(tài)向量和第i個歷史數據狀態(tài)向量之間的歐式距離；E為異常數據對應采樣點的集合。

考慮到相關系數更能反映狀態(tài)向量的相似性，有利于判斷相似交通流，采用相關系數代替歐式距離進行近鄰篩選。相關系數的表達式為：

(4)

根據式(3)或式(4)可將歐式距離最小或相關系數最大的k個歷史數據狀態(tài)向量視作異常數據狀態(tài)向量的近鄰。

2.3 異常數據的修復

經典的異常數據修復公式為：

(5)

式中：αi為第i個近鄰的權重；k為近鄰數量。

近鄰權重有多種取值方法，常見的有歷史均值法和距離權重法，計算公式分別為：

αi=1/k

(6)

(7)

近鄰與異常數據具有良好的相似性是式(5)成立的前提，這種相似性同時體現在相關系數和歐氏距離這2個指標上。顯然，較大的相關系數和較小的歐氏距離有利于異常數據的修復。但挑選出的近鄰可能存在如下情況：1) 歐氏距離相當但相關系數差別較大；2) 歐式距離過大造成近鄰與異常數據的曲線明顯偏離。因此，同時采用相關系數和調幅系數對式(7)進行修正，得到新的近鄰權重：

(8)

采用ci進行修正的目的是希望相關系數更大的近鄰能獲得更大的近鄰權重。采用γi進行修正的目的是將Hi的幅值拉回到A的幅值水平，最終目的是對式(5)中him進行調整。因此，式(8)給出的近鄰權重計算方法可稱為調幅權重法。

2.4 改進KNN算法流程

改進KNN算法流程為按式(1)、式(2)構造較長的狀態(tài)向量→按式(4)計算相關系數→挑選相關系數最大的前k個歷史數據作為近鄰→按式(8)計算近鄰權重→按式(5)進行異常數據修復。改進KNN算法也可稱為相關系數-調幅權重法。

3 評價指標

均方根誤差RMSE是最常見的用來評價異常數據修復效果的指標，RMSE越小，修復效果越好。其表達式為：

(9)

另一個常見評價指標是平均相對誤差MRE，MRE越小，修復效果越好。其表達式為：

(10)

4 算例分析

4.1 數據來源與處理

采用明尼蘇達大學交通數據研究實驗室在2018年1月12日—2019年1月12日(共366 d)采集的交通流量數據(第25號測點)展開分析。原始數據的采樣間隔為30 s，每天共有2 880個采樣點。經統(tǒng)計，共有146 d未出現異常數據。在出現異常數據的220 d中，有218 d的數據異常率小于6.32%，另外2 d的數據異常率分別為15.4%和46.5%。此外，異常數據呈現隨機分布的特點。

為檢驗上述異常數據修復算法的性能，將146 d的正常數據按15 min采樣間隔重新進行整理(96個采樣點)，形成實驗數據庫。以前面142 d的數據作為歷史數據，后面4 d的數據作為測試數據(分別稱為測試數據1、2、3、4)。

4.2 算法的修復性能比較

分別采用表1所示6種不同修復算法進行處理，比較其修復性能。這些算法均以天為時間單位構造較長的狀態(tài)向量，每個狀態(tài)向量均包含96個采樣數據。算法1～3采用相關系數[式(4)]篩選近鄰，算法4～6采用歐式距離[式(3)]篩選近鄰。

表1 6種異常數據修復算法

由于異常數據的出現位置具有很強的隨機性，需從統(tǒng)計意義上比較各種修復算法的優(yōu)劣。采用蒙特卡洛抽樣方法進行統(tǒng)計分析。每次抽樣時，先根據指定的數據異常率生成異常數據數量，再隨機生成它們的位置。需指出的是，在篩選近鄰時，最優(yōu)k值難以預先確定，故采用動態(tài)方法確定k值。每次抽樣均按式(4)計算相關系數，對于算法1～3，將相關系數大于0.95的歷史數據視作近鄰，且k值至少取10，最多取20；對于算法4～6，k值與算法1～3相同，將歐式距離最小的k個歷史數據視作近鄰。

考慮20%的數據異常率，對每個測試數據進行5 000次隨機抽樣，隨機生成異常數據的位置。對計算結果進行統(tǒng)計分析，得到6種算法的RMSE值(見圖1)。

圖1 不同算法的RMSE值(數據異常率=20%)

由圖1可知：對于測試數據1、2，算法1遠好于其他算法，算法2、3最差，算法4～6相當；對于測試數據3，從中值判斷，算法1遠好于算法2、3，但僅比算法4～6稍好；對于測試數據4，從中值判斷，算法1稍好于其他5種算法?？偟膩碚f，對于測試數據1、2，算法1表現最好；對于測試數據3、4，算法1與算法4～6相當?？梢?，算法1對異常數據的修復能力具有更廣泛的適應性。

4.3 近鄰的相關系數與歐式距離

將不同算法在某次抽樣分析時篩選出的近鄰挑選出來，繪制圖2所示相關系數與歐式距離之間的關系圖，分析算法1具有更廣泛適應性的原因。

圖2 不同算法k個近鄰的相關系數-歐式距離關系

由圖2可知：測試數據1和2、測試數據3和4的散點分布規(guī)律分別較為相似。對于測試數據1、2，算法1～3挑選出的近鄰大多具有較大的相關系數和歐式距離，而算法4～6挑選出的近鄰大多具有較小的相關系數和歐式距離。在篩選近鄰時，總是希望近鄰具有較大的相關系數和較小的歐式距離。對于測試數據1、2，兩類算法(算法1～3為一類，算法4～6為另一類)挑選出的近鄰的相關系數和歐式距離背離嚴重；對于測試數據3、4，算法1～3和算法4～6挑選出的近鄰均大多具有較大的相關系數和較小的歐式距離，兩類算法挑選出的近鄰的相關系數和歐式距離背離程度較輕。

圖3為測試數據與所挑選近鄰之間的關系。由3(a)可知：測試數據與該近鄰之間的距離明顯較遠(li=411.98)，而實際上它們之間的相關系數較大(ci=0.974)。由圖3(b)可知：測試數據與該近鄰之間的距離明顯較近(li=105.82)，而實際上它們之間的相關系數也較大(ci=0.980)。對于圖3(a)所示歐式距離很大的情況，若仍采用歷史均值法和距離權重法計算近鄰權重，則異常數據的修復值會發(fā)生嚴重失真，采用經調幅系數修正的調幅權重法計算近鄰權重更合理。圖1表明，調幅權重法只有和相關系數篩選近鄰法相結合時(即算法1)才具有最佳的修復效果。

圖3 測試數據與所挑選近鄰之間的典型關系

綜合圖1～3分析，算法1比其他算法具有更廣泛的適應性，即使對于近鄰相關系數與歐式距離嚴重背離的情況，算法1也具有良好的修復性能。而其他算法只有在近鄰相關系數與歐式距離較為一致時才表現出較好的修復性能。

4.4 數據異常率的影響

將數據異常率以10%步長從10%增加至90%，對每個數據異常率進行5 000次抽樣，分析算法1的修復性能與數據異常率的關系。不同數據異常率下算法1的RMSE值見圖4。

由圖4可知：對于所有測試數據，隨著數據異常率的增大，箱形圖的中值和下限上升，表明算法1的修復性能下降；RMSE指標的變化幅度先減小后增大，在數據異常率約為50%時最小。這是由于數據異常率較小時，異常數據容易集中在數值較大或較小的采樣點上，RMSE指標出現較大值或較小值。而當數據異常率較大時，由于正常數據較少，算法1的修復性能變差，進一步導致RMSE指標的變化幅度增大。

圖4 算法1在不同數據異常率下的RMSE值

5 結論

(1) 構造較長且長度固定的狀態(tài)向量可很好地適應異常數據隨機分布的特點。

(2) 按式(3)或式(4)挑選出的近鄰有時不能同時滿足相關系數較大且歐式距離較小的要求。對于歐式距離較大的情況，采用經調幅系數修正的調幅權重法來計算近鄰權重更合理。

(3) 相關系數-調幅權重法具有廣泛的適應性，即使在近鄰相關系數與歐式距離嚴重背離時，該算法也具有良好的修復性能。