一種修復(fù)交通流異常數(shù)據(jù)的改進(jìn)KNN算法*

李翠，黃侃，李霞

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

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

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

1 KNN法的基本原理

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

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

2 改進(jìn)KNN算法

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

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

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

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

(1)

相應(yīng)地，某待修復(fù)的異常數(shù)據(jù)狀態(tài)向量為：

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

(2)

式中：ai為異常數(shù)據(jù)狀態(tài)向量的第i個(gè)采樣點(diǎn)。

需指出的是，A中同時(shí)包含正常數(shù)據(jù)和異常數(shù)據(jù)。

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

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

(3)

式中：li為異常數(shù)據(jù)狀態(tài)向量和第i個(gè)歷史數(shù)據(jù)狀態(tài)向量之間的歐式距離；E為異常數(shù)據(jù)對(duì)應(yīng)采樣點(diǎn)的集合。

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

(4)

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

2.3 異常數(shù)據(jù)的修復(fù)

經(jīng)典的異常數(shù)據(jù)修復(fù)公式為：

(5)

式中：αi為第i個(gè)近鄰的權(quán)重；k為近鄰數(shù)量。

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

αi=1/k

(6)

(7)

近鄰與異常數(shù)據(jù)具有良好的相似性是式(5)成立的前提，這種相似性同時(shí)體現(xiàn)在相關(guān)系數(shù)和歐氏距離這2個(gè)指標(biāo)上。顯然，較大的相關(guān)系數(shù)和較小的歐氏距離有利于異常數(shù)據(jù)的修復(fù)。但挑選出的近鄰可能存在如下情況：1) 歐氏距離相當(dāng)?shù)嚓P(guān)系數(shù)差別較大；2) 歐式距離過大造成近鄰與異常數(shù)據(jù)的曲線明顯偏離。因此，同時(shí)采用相關(guān)系數(shù)和調(diào)幅系數(shù)對(duì)式(7)進(jìn)行修正，得到新的近鄰權(quán)重：

(8)

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

2.4 改進(jìn)KNN算法流程

改進(jìn)KNN算法流程為按式(1)、式(2)構(gòu)造較長的狀態(tài)向量→按式(4)計(jì)算相關(guān)系數(shù)→挑選相關(guān)系數(shù)最大的前k個(gè)歷史數(shù)據(jù)作為近鄰→按式(8)計(jì)算近鄰權(quán)重→按式(5)進(jìn)行異常數(shù)據(jù)修復(fù)。改進(jìn)KNN算法也可稱為相關(guān)系數(shù)-調(diào)幅權(quán)重法。

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

均方根誤差RMSE是最常見的用來評(píng)價(jià)異常數(shù)據(jù)修復(fù)效果的指標(biāo)，RMSE越小，修復(fù)效果越好。其表達(dá)式為：

(9)

另一個(gè)常見評(píng)價(jià)指標(biāo)是平均相對(duì)誤差MRE，MRE越小，修復(fù)效果越好。其表達(dá)式為：

(10)

4 算例分析

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

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

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

4.2 算法的修復(fù)性能比較

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

表1 6種異常數(shù)據(jù)修復(fù)算法

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

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

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

由圖1可知：對(duì)于測(cè)試數(shù)據(jù)1、2，算法1遠(yuǎn)好于其他算法，算法2、3最差，算法4～6相當(dāng)；對(duì)于測(cè)試數(shù)據(jù)3，從中值判斷，算法1遠(yuǎn)好于算法2、3，但僅比算法4～6稍好；對(duì)于測(cè)試數(shù)據(jù)4，從中值判斷，算法1稍好于其他5種算法。總的來說，對(duì)于測(cè)試數(shù)據(jù)1、2，算法1表現(xiàn)最好；對(duì)于測(cè)試數(shù)據(jù)3、4，算法1與算法4～6相當(dāng)。可見，算法1對(duì)異常數(shù)據(jù)的修復(fù)能力具有更廣泛的適應(yīng)性。

4.3 近鄰的相關(guān)系數(shù)與歐式距離

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

圖2 不同算法k個(gè)近鄰的相關(guān)系數(shù)-歐式距離關(guān)系

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

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

圖3 測(cè)試數(shù)據(jù)與所挑選近鄰之間的典型關(guān)系

綜合圖1～3分析，算法1比其他算法具有更廣泛的適應(yīng)性，即使對(duì)于近鄰相關(guān)系數(shù)與歐式距離嚴(yán)重背離的情況，算法1也具有良好的修復(fù)性能。而其他算法只有在近鄰相關(guān)系數(shù)與歐式距離較為一致時(shí)才表現(xiàn)出較好的修復(fù)性能。

4.4 數(shù)據(jù)異常率的影響

將數(shù)據(jù)異常率以10%步長從10%增加至90%，對(duì)每個(gè)數(shù)據(jù)異常率進(jìn)行5 000次抽樣，分析算法1的修復(fù)性能與數(shù)據(jù)異常率的關(guān)系。不同數(shù)據(jù)異常率下算法1的RMSE值見圖4。

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

圖4 算法1在不同數(shù)據(jù)異常率下的RMSE值

5 結(jié)論

(1) 構(gòu)造較長且長度固定的狀態(tài)向量可很好地適應(yīng)異常數(shù)據(jù)隨機(jī)分布的特點(diǎn)。

(2) 按式(3)或式(4)挑選出的近鄰有時(shí)不能同時(shí)滿足相關(guān)系數(shù)較大且歐式距離較小的要求。對(duì)于歐式距離較大的情況，采用經(jīng)調(diào)幅系數(shù)修正的調(diào)幅權(quán)重法來計(jì)算近鄰權(quán)重更合理。

(3) 相關(guān)系數(shù)-調(diào)幅權(quán)重法具有廣泛的適應(yīng)性，即使在近鄰相關(guān)系數(shù)與歐式距離嚴(yán)重背離時(shí)，該算法也具有良好的修復(fù)性能。