基于改進(jìn)KNN算法的交通流異常數(shù)據(jù)修復(fù)方法

，，， ，

(上海工程技術(shù)大學(xué) 汽車(chē)工程學(xué)院，上海 201620)

0 引言

交通數(shù)據(jù)是智能交通系統(tǒng)(intelligent transportation system, ITS)中主要的數(shù)據(jù)支撐，可以直接反映交通的運(yùn)行狀態(tài)，能夠?yàn)榻煌ㄒ?guī)劃、管理和決策提供重要的信息[1]。交通流數(shù)據(jù)質(zhì)量的高低直接影響著交通流狀態(tài)分析的準(zhǔn)確度。交通數(shù)據(jù)在實(shí)際獲取中，由于受到檢測(cè)器自身異常、傳輸網(wǎng)絡(luò)異常及環(huán)境因素等的影響，采集到的交通流數(shù)據(jù)難免會(huì)出現(xiàn)數(shù)據(jù)缺失、數(shù)據(jù)錯(cuò)誤等質(zhì)量問(wèn)題[2]，對(duì)交通流數(shù)據(jù)分析以及交通管控精準(zhǔn)性造成影響。因此，進(jìn)行異常數(shù)據(jù)修復(fù)，提高交通流檢測(cè)數(shù)據(jù)的質(zhì)量，是交通狀態(tài)辨識(shí)、交通管理及控制等工作正常進(jìn)行的必然要求。

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

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

目前KNN算法模型主要應(yīng)用于交通流預(yù)測(cè)方面，在交通數(shù)據(jù)修復(fù)方面的應(yīng)用和研究較少。因此，本文在對(duì)KNN算法特性分析的基礎(chǔ)上，通過(guò)對(duì)k值、修復(fù)狀態(tài)向量以及近鄰值權(quán)重等模型主要相關(guān)要素的優(yōu)選和改進(jìn)，進(jìn)而構(gòu)建基于改進(jìn)KNN算法的交通流異常數(shù)據(jù)修復(fù)模型。研究結(jié)果旨在為交通流數(shù)據(jù)修復(fù)方法提供一種新的思路，為交通管控提供準(zhǔn)確的基礎(chǔ)數(shù)據(jù)支持。

1 KNN異常數(shù)據(jù)修復(fù)模型

1.1 KNN基礎(chǔ)算法

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

模型的運(yùn)算速度和修復(fù)精度主要與4個(gè)要素密切相關(guān)：近鄰個(gè)數(shù)、狀態(tài)向量、距離度量方式、算法實(shí)施。模型性能的優(yōu)劣很大程度上取決于這4個(gè)要素的選取。近鄰數(shù)k表示從歷史數(shù)據(jù)庫(kù)中選取與當(dāng)前數(shù)據(jù)相似的數(shù)據(jù)組數(shù)，k值的選取主要與歷史數(shù)據(jù)庫(kù)有關(guān)。狀態(tài)向量作為當(dāng)前數(shù)據(jù)與歷史數(shù)據(jù)庫(kù)實(shí)施匹配的一個(gè)匹配標(biāo)準(zhǔn)，表征了歷史數(shù)據(jù)庫(kù)中的數(shù)據(jù)特征。距離度量方式用于計(jì)算異常數(shù)據(jù)狀態(tài)向量與歷史數(shù)據(jù)庫(kù)中各個(gè)狀態(tài)向量之間的距離。修復(fù)算法構(gòu)造了采用k組近鄰數(shù)據(jù)集修復(fù)異常數(shù)據(jù)值的方案。

1.2 改進(jìn)KNN算法

異常數(shù)據(jù)修復(fù)是交通管控有效實(shí)施的基礎(chǔ)，采用KNN算法能夠?qū)崿F(xiàn)在眾多的歷史數(shù)據(jù)組群中匹配到異常數(shù)據(jù)相似組群，進(jìn)而實(shí)現(xiàn)對(duì)異常數(shù)據(jù)的修復(fù)。因此，本文提出基于改進(jìn)KNN算法的異常數(shù)據(jù)修復(fù)方法。KNN異常數(shù)據(jù)修復(fù)模型實(shí)施過(guò)程如圖1所示。

針對(duì)出現(xiàn)異常的交通流數(shù)據(jù)，運(yùn)用改進(jìn)KNN算法對(duì)其異常數(shù)據(jù)進(jìn)行修復(fù)，其實(shí)現(xiàn)方法具體步驟如下：

1)選取異常數(shù)據(jù)出現(xiàn)的同一監(jiān)測(cè)點(diǎn)的正常交通流檢測(cè)器數(shù)據(jù)作為數(shù)據(jù)源，選取連續(xù)5個(gè)數(shù)據(jù)為一組，建立歷史數(shù)據(jù)狀態(tài)向量庫(kù)Xn。

2)識(shí)別異常數(shù)據(jù)，選取異常數(shù)據(jù)前后兩個(gè)時(shí)間間隔的正常數(shù)據(jù)，建立異常數(shù)據(jù)狀態(tài)向量X。

3)計(jì)算異常數(shù)據(jù)狀態(tài)向量X與歷史數(shù)據(jù)狀態(tài)向量庫(kù)Xn之間的歐式距離d，對(duì)其距離按照由小到大進(jìn)行排序，記為di。

4)通過(guò)數(shù)據(jù)驗(yàn)證平均相對(duì)誤差與k值的關(guān)系，對(duì)近鄰值個(gè)數(shù)k進(jìn)行優(yōu)選。

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

7)對(duì)異常值進(jìn)行刪除，并填補(bǔ)修復(fù)后的數(shù)值。

本文在對(duì)KNN基礎(chǔ)模型以及交通流數(shù)據(jù)特性分析的基礎(chǔ)上，對(duì)KNN基礎(chǔ)模型的改進(jìn)主要體現(xiàn)為三點(diǎn)：一是對(duì)k值進(jìn)行優(yōu)選；二是考慮異常數(shù)據(jù)前后時(shí)刻的關(guān)聯(lián)數(shù)據(jù)，建立了狀態(tài)向量；三是提出了一種新的近鄰值權(quán)重選取方式。

1)參數(shù)k優(yōu)化選取:

近鄰值個(gè)數(shù)k表示從歷史數(shù)據(jù)庫(kù)中選取的近鄰個(gè)數(shù)，k值大小是影響算法計(jì)算時(shí)間和數(shù)據(jù)修復(fù)精度的一個(gè)重要因素。一般情況下，k值越大，修復(fù)精度越高但其運(yùn)算時(shí)間會(huì)相應(yīng)增加。

由圖2可知，隨著k值的增大，平均相對(duì)誤差不斷減小，并逐漸趨于平緩。當(dāng)k值為25時(shí)，圖形基本收斂，隨著k值再增大，平均相對(duì)誤差已無(wú)明顯變化。因此本文優(yōu)選k值為25。

圖2 平均相對(duì)誤差與k值的關(guān)系

2)狀態(tài)向量建立:

分別建立歷史數(shù)據(jù)狀態(tài)向量庫(kù)和異常數(shù)據(jù)狀態(tài)向量。

目前對(duì)交通流異常數(shù)據(jù)的修復(fù)，通?？紤]的是利用異常數(shù)據(jù)的前向數(shù)據(jù)對(duì)其進(jìn)行修復(fù)。圖3表示一段時(shí)間內(nèi)交通流速度變化趨勢(shì)。從圖中可以看出，交通流速度隨著時(shí)間的變化，具有不確定性、波動(dòng)性和隨機(jī)時(shí)變特性。交通流數(shù)據(jù)自身具有一定的特征和規(guī)律，相鄰時(shí)間之間的數(shù)據(jù)具有某種關(guān)聯(lián)性，前一時(shí)刻速度大小會(huì)影響后一時(shí)刻速度大小，數(shù)據(jù)之間具有很強(qiáng)的連續(xù)性和關(guān)聯(lián)性。并且時(shí)間距離越近的數(shù)據(jù)之間關(guān)聯(lián)性越大[20]。

圖3 交通流速度數(shù)據(jù)趨勢(shì)圖

(1)

3)距離度量:

距離度量方式是用于度量異常數(shù)據(jù)狀態(tài)向量與歷史數(shù)據(jù)庫(kù)中各個(gè)狀態(tài)向量之間的相似程度，一般采用歐氏距離作為衡量標(biāo)準(zhǔn)：

(2)

4)修復(fù)算法構(gòu)建:

修復(fù)算法構(gòu)造了采用k組近鄰數(shù)據(jù)集修復(fù)異常數(shù)據(jù)值的方案，即:

(3)

尋找到的k個(gè)最近鄰中，距離越近，說(shuō)明此近鄰值與當(dāng)前異常數(shù)據(jù)狀態(tài)向量的相似度越大。為了提高其修復(fù)精度，采取對(duì)其近鄰值賦予權(quán)重的方式，距離越近的近鄰值，賦予的權(quán)重越大。

關(guān)于近鄰值權(quán)重的選取，現(xiàn)有的k近鄰權(quán)重選取方式主要有距離倒數(shù)權(quán)重和排隊(duì)指數(shù)權(quán)重兩種，分別定義為權(quán)重1、權(quán)重2。如式(4)、式(5)。

距離倒數(shù)權(quán)重：

(4)

排隊(duì)指數(shù)權(quán)重：

(5)

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

距離占比權(quán)重：

(6)

式中,αi是第i組近鄰值；k指近鄰值的個(gè)數(shù)；di是當(dāng)前異常數(shù)據(jù)狀態(tài)向量與歷史數(shù)據(jù)庫(kù)中第i組狀態(tài)向量數(shù)據(jù)之間的歐式距離；di是第i個(gè)近鄰值的權(quán)重。

2 實(shí)驗(yàn)驗(yàn)證

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

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

(7)

(8)

相關(guān)系數(shù)r表示修復(fù)值和真實(shí)值之間的相似程度，其值大小范圍為[-1,1]。其絕對(duì)值大小代表了數(shù)據(jù)之間的相關(guān)程度，負(fù)號(hào)表示數(shù)據(jù)關(guān)系為負(fù)相關(guān)，其絕對(duì)值越接近1表示相關(guān)性越強(qiáng)。計(jì)算公式如下：

(9)

2.2 數(shù)據(jù)來(lái)源與處理

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

表1 部分交通流速度數(shù)據(jù)示例

2.3 結(jié)果比較與討論

2.3.1 不同k值的結(jié)果比較

為了檢驗(yàn)改進(jìn)后的KNN數(shù)據(jù)修復(fù)模型的整體修復(fù)效果，用實(shí)驗(yàn)數(shù)據(jù)分析了3種KNN模型進(jìn)行數(shù)據(jù)修復(fù)的平均相對(duì)誤差和近鄰值k的關(guān)系，并與常用的數(shù)據(jù)修復(fù)方法移動(dòng)平均法相對(duì)比，結(jié)果如圖4所示。

圖4 平均相對(duì)誤差與k值的關(guān)系

從圖4中可以看出：

1)當(dāng)k值大于6時(shí)，帶權(quán)重2的KNN模型的修復(fù)效果優(yōu)于移動(dòng)平均法，當(dāng)k值大于4時(shí)，帶權(quán)重1、3的KNN模型修復(fù)效果優(yōu)于移動(dòng)平均法。由此可以得出，相比較移動(dòng)平均法，KNN修復(fù)模型的異常數(shù)據(jù)修復(fù)效果明顯較好，說(shuō)明KNN模型適用于數(shù)據(jù)修復(fù)，采取k近鄰的思想進(jìn)行數(shù)據(jù)修復(fù)的方法可行。

2)隨著k值的增大，3種KNN數(shù)據(jù)修復(fù)模型的平均相對(duì)誤差不斷降低，并逐漸趨于平緩，權(quán)重3的KNN修復(fù)模型所得修復(fù)結(jié)果的平均相對(duì)誤差值比權(quán)重1和權(quán)重2修復(fù)模型的誤差值小，說(shuō)明改進(jìn)的KNN數(shù)據(jù)修復(fù)模型的整體修復(fù)效果優(yōu)于另兩種權(quán)重KNN模型的整體修復(fù)效果。

2.3.2 不同模型結(jié)果比較

將平均相對(duì)誤差、均方根誤差、相關(guān)系數(shù)3種指標(biāo)作為修復(fù)算法的誤差評(píng)估方式對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行全面評(píng)價(jià)。將3種KNN數(shù)據(jù)修復(fù)模型和傳統(tǒng)移動(dòng)平均法4種方法的修復(fù)結(jié)果進(jìn)行比較，見(jiàn)圖5、圖6和表2。

圖5 平均相對(duì)誤差

圖6 均方根誤差

修復(fù)方法相關(guān)系數(shù)rKNN修復(fù)模型權(quán)重10.72權(quán)重20.71權(quán)重30.73移動(dòng)平均法0.66

圖5顯示了4種修復(fù)方法實(shí)驗(yàn)結(jié)果的平均相對(duì)誤差(MAPE)結(jié)果比較。平均相對(duì)誤差反映了交通流量數(shù)據(jù)修復(fù)值偏離真實(shí)值的程度。其值越小表示修復(fù)值與真實(shí)值的偏離程度越小，說(shuō)明兩者越相近。

從圖5中可以看出，4種修復(fù)方法實(shí)驗(yàn)結(jié)果的平均相對(duì)誤差值大小依次為9.93%、10.1%、9.88%、10.23%。由誤差值大小可以看出，KNN修復(fù)模型的誤差值大小明顯小于移動(dòng)平均法，權(quán)重3修復(fù)模型的誤差值要小于另兩種權(quán)重修復(fù)模型。

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

從圖6可以看出，4種修復(fù)方法實(shí)驗(yàn)結(jié)果的均方根誤差值大小依次為10.88、11.07、10.82、12.23。從表1可以得知，在KNN修復(fù)模型中，權(quán)重3的KNN修復(fù)模型的修復(fù)值與真實(shí)值的相關(guān)系數(shù)最大，為0.73，權(quán)重1和權(quán)重2的KNN修復(fù)模型次之，分別為0.72和0.71，移動(dòng)平均法的相關(guān)系數(shù)最小，為0.66。

由此可以得出，3種KNN數(shù)據(jù)修復(fù)模型的修復(fù)效果明顯優(yōu)于移動(dòng)平均法的修復(fù)效果，權(quán)重3的KNN修復(fù)模型的修復(fù)精度明顯高于權(quán)重2的修復(fù)模型，略高于權(quán)重1的修復(fù)模型，其平均相對(duì)誤差大小為9.88%。由此可以說(shuō)明采用改進(jìn)后的KNN異常數(shù)據(jù)修復(fù)模型進(jìn)行數(shù)據(jù)修復(fù)取得了較好的修復(fù)效果。

為了更好的體現(xiàn)改進(jìn)KNN修復(fù)模型的優(yōu)勢(shì)，本文還分析了各個(gè)方法實(shí)驗(yàn)結(jié)果的相對(duì)誤差在不同誤差范圍內(nèi)所占的比例。圖7表示采用4種修復(fù)方法實(shí)驗(yàn)結(jié)果的修復(fù)值與真實(shí)值的相對(duì)誤差在[0,20%)、[20%,+∞)內(nèi)的數(shù)據(jù)個(gè)數(shù)所占比例?？梢钥闯?，采用KNN修復(fù)模型的相對(duì)誤差小于20%的占比高于移動(dòng)平均法，大于20%的占比低于移動(dòng)平均法。在KNN修復(fù)模型中，權(quán)重3的修復(fù)模型，其相對(duì)誤差值在[0,20%)范圍內(nèi)的占比最大。這說(shuō)明改進(jìn)后KNN修復(fù)模型的修復(fù)效果能夠滿足數(shù)據(jù)修復(fù)精度需求。

圖7 相對(duì)誤差占比

3 結(jié)論

針對(duì)目前交通流數(shù)據(jù)異常和數(shù)據(jù)質(zhì)量不高的問(wèn)題，將k近鄰模型引用到數(shù)據(jù)修復(fù)中。對(duì)KNN基礎(chǔ)模型相關(guān)要素進(jìn)行改進(jìn)和優(yōu)化，建立了一種適用于交通流數(shù)據(jù)修復(fù)的KNN異常數(shù)據(jù)修復(fù)模型。通過(guò)實(shí)際數(shù)據(jù)驗(yàn)證，可得出以下結(jié)論：

1)提出基于改進(jìn)KNN算法的異常數(shù)據(jù)修復(fù)模型，該修復(fù)模型與傳統(tǒng)的移動(dòng)平均修復(fù)方法相比，具有更優(yōu)的修復(fù)精度，其平均相對(duì)誤差值為9.88%，能夠滿足基本的異常數(shù)據(jù)修復(fù)精度需求。

2)針對(duì)KNN算法模型，進(jìn)行k值和狀態(tài)向量的優(yōu)選、提出一種距離占比的近鄰值權(quán)重選取方式，進(jìn)而實(shí)現(xiàn)對(duì)基礎(chǔ)模型的改進(jìn)。結(jié)果表明，采用距離占比的近鄰值權(quán)重方式的KNN數(shù)據(jù)修復(fù)模型能夠有效提高數(shù)據(jù)修復(fù)精度，具有更好的數(shù)據(jù)修復(fù)效果。

本文所提出的數(shù)據(jù)修復(fù)方法實(shí)施性較強(qiáng)，可有效提升交通流數(shù)據(jù)質(zhì)量，其修復(fù)思想對(duì)交通數(shù)據(jù)在實(shí)際應(yīng)用方面具有理論指導(dǎo)意義。