基于K最近鄰算法的城市路段行程時間短時預(yù)測

涂 銳，秦江靈，趙志平，徐建川，陳順舉，夏 立

(1.重慶市公安局渝北區(qū)分局交通巡邏警察支隊， 重慶 401120；2.重慶大學 計算機學院， 重慶 400044)

隨著經(jīng)濟社會發(fā)展，我國各大中城市的汽車保有量近年開始急劇攀升,隨之帶來的環(huán)境污染、交通事故尤其是交通擁堵問題也日趨嚴重[1]。發(fā)展智能交通系統(tǒng)是解決城市道路交通擁堵、環(huán)境污染等問題的有效方法之一[2]，而城市道路行程時間短時預(yù)測作為智能交通系統(tǒng)中的一個重要研究領(lǐng)域，能夠?qū)崿F(xiàn)交通誘導，有效緩解城市道路的交通擁堵問題[3-4]。

短時交通流預(yù)測相關(guān)研究的數(shù)據(jù)來源主要包括GPS浮動車數(shù)據(jù)[5-6]、固定環(huán)形線圈檢測器數(shù)據(jù)[7]和汽車電子標識數(shù)據(jù)，但目前國內(nèi)外的行程時間短時預(yù)測問題大多集中于基于GPS浮動車和固定環(huán)形線圈檢測器的數(shù)據(jù)，GPS浮動車只包含了出租車和公共汽車的數(shù)據(jù)但不包含，大量的私家車的出行數(shù)據(jù)，具有樣本量小的缺點。而固定環(huán)形線圈檢測器通常只部署在十字交叉路口，在空間上不具有廣泛性的特點。而對于汽車電子標識數(shù)據(jù)，多用于短時交通流預(yù)測的相關(guān)研究，具有一定的新穎性，同時由于包含了私家車在內(nèi)的所有車輛的出行數(shù)據(jù)，具有樣本量大的優(yōu)點，在空間分布上也具有廣泛性的特點。

短時交通預(yù)測的方法主要包括線性回歸模型[8](linear regressive)、時間序列模型[4](time series)、卡爾曼濾波模型[9](Kalman filtering)，以及神經(jīng)網(wǎng)絡(luò)模型[10-11](neural network)、組合預(yù)測模型[12-13](nonparammetric regress model)等，而K最近鄰(KNN)算法相比于以上方法的主要優(yōu)點在于沒有復(fù)雜的參數(shù)估計，模型訓練時間短，適合處理海量歷史數(shù)據(jù)來實現(xiàn)實時預(yù)測。

目前已有文獻將KNN算法應(yīng)用于短時交通流預(yù)測。Wenxin Qiao等[14]利用藍牙數(shù)據(jù)，將KNN算法與傳統(tǒng)的預(yù)測模型進行對比，并提出了改進的KNN-T模型。SH Lim等[15]利用高速公路收費數(shù)據(jù)，將KNN算法應(yīng)用于行程時間的實時預(yù)測。Steve Robinson等[7]提出了KNN算法中選擇局部估計方法和k值的策略，并就提出的策略進行了實驗分析。

綜上可以發(fā)現(xiàn)：目前的研究大多基于GPS浮動車數(shù)據(jù)和固定環(huán)形線圈檢測數(shù)據(jù)，同時較少對城市道路進行相關(guān)研究。針對上述問題，本文提出了基于汽車電子標識數(shù)據(jù)和KNN算法的城市道路行程時間短時預(yù)測方法，重點研究了基于汽車電子標識數(shù)據(jù)的路段行程時間的估計和KNN算法中特征向量的構(gòu)建。

1 基于汽車電子標識數(shù)據(jù)的路段行程時間估計

1.1 汽車電子標識數(shù)據(jù)采集

汽車電子標識(electronic registration identification of the motor vehicle，簡稱ERI)將車牌號碼等信息存儲在射頻標簽中，能夠自動、非接觸、不停車地完成車輛的識別和監(jiān)控，是RFID技術(shù)在智慧交通領(lǐng)域的延伸[16]。RFID技術(shù)即射頻識別(radio frequency identification)技術(shù)[17]，其工作原理為通過利用無線射頻方式進行非接觸式雙向通信的識別，以實現(xiàn)自我識別的功能。RFID技術(shù)具有高保密性、讀寫距離遠、可識別如汽車等高速運動的物體、能進行非接觸式雙向通信等優(yōu)點，并且能在惡劣的環(huán)境下工作。目前，RFID技術(shù)與通信技術(shù)、互聯(lián)網(wǎng)技術(shù)等相結(jié)合，已大范圍應(yīng)用于物聯(lián)網(wǎng)、智能交通和商品防偽等領(lǐng)域。

電子車牌是指安裝于機動車上具有電子信息識別功能和車牌數(shù)字號碼圖案的車牌標識，同時具有普通車牌和電子車牌的功能。將RFID技術(shù)應(yīng)用到電子車牌中，相比于傳統(tǒng)的車牌具有能存儲信息、進行非接觸式自動識別、通過唯一的ID獲取車輛信息等特點。RFID電子車牌系統(tǒng)主要由標簽閱讀器(reader)、電子標簽(tag)以及交通信息中心3部分組成，見圖1。

圖1 RFID電子車牌系統(tǒng)

基于RFID電子車牌數(shù)據(jù)采集的工作原理是：將閱讀器部署在城市的主要交通干道，并與交通信息中心通過網(wǎng)絡(luò)相連接；當安裝有電子標簽的車輛進入到閱讀器的識別區(qū)域內(nèi)時，電子標簽通過吸收閱讀器發(fā)出射頻的能源而變?yōu)榧せ顮顟B(tài)，激活后通過電子標簽內(nèi)的天線采用某種調(diào)制方式將其攜帶的信息發(fā)射出去；閱讀器收到電子標簽發(fā)射的應(yīng)答信號后，解碼其中的信息并將結(jié)果發(fā)送至交通信息中心。交通信息包含了車輛的電子標簽ID、車輛類別、車輛通過時間等信息，通過這些采集到的RFID電子車牌數(shù)據(jù)可以獲取到車流量、平均速度、行程時間等重要的交通流參數(shù)，為城市道路交通的研究提供了數(shù)據(jù)來源。

1.2 路段行程時間估計

考慮圖2中在A、B兩個RFID采集點之間的道路，記為路段r。在觀測數(shù)據(jù)的一段時間間隔p內(nèi)，車輛標識分別為i=1,…,N的共N輛車分別在時間為s1

{(si,Xi),i=1,…,N}

(1)

{(tj,Yj),j=1,…,M}

(2)

在式(1)和(2)中，存在的Xi=Yj，則表明同一輛車x在一段時間p內(nèi)通過了RFID采集點A和采集點B，用tj減去si的值即可得到車輛x通過路段r的行程時間Tx。對于式(1)和(2)中所有存在的Xi=Yj，執(zhí)行上述操作即可得到時間段p內(nèi)所有通過了路段r的行程時間，如式(3)所示。

{Tx=tj-si|Xi=Yj}

(3)

設(shè)在式(3)中得到的車輛通過路段r的行程時間序列長度為L，即在時間段p內(nèi)通過了路段r的車輛數(shù)目為L，因此得到了L個行程時間值的序列：

{Tx,x=1,…,L}

(4)

本文使用時間段p內(nèi)所有通過路段r車輛的平均路段行程時間作為路段r在時間段p內(nèi)的行程時間來估計Trp，即求式(5)中這L個值的均值，得到

(5)

2 基于KNN的城市路段行程時間預(yù)測模型

2.1 K最近鄰算法

K最近鄰(KNN)算法的基本思想是：將當前輸入變量與具有相似輸入變量的歷史數(shù)據(jù)值相匹配，其中輸入變量通常稱為特征向量[14]。每個特征向量描述被稱為特征空間的多變量空間中的一個點，如果特征向量包含n個屬性值，則該特征空間是n維的。KNN算法的輸出值被定義為與輸入特征向量具有相似特征向量的已知輸出歷史記錄相關(guān)的函數(shù)。

設(shè)Yt是t時段的一個待求解的預(yù)測值，用Xt表示t時段的預(yù)測值所對應(yīng)的特征向量。KNN算法中對于給定的輸入特征向量Xt，在歷史數(shù)據(jù)集中搜索與輸入特征向量Xt距離最近的K個歷史特征向量Xh1,Xh2,…,Xhk，然后將這K個特征向量通過加權(quán)估計的方法求解預(yù)測值Yt。

2.2 數(shù)據(jù)準備

本文城市路段行程時間短時預(yù)測使用的數(shù)據(jù)集為重慶市的汽車電子標識數(shù)據(jù)。對于城市道路，在凌晨時的車流量較小，通常處于自由流狀態(tài)，因此沒有預(yù)測的必要。所以，預(yù)測的時間段選定為06∶00—23∶59。

設(shè)路段r為待進行路段行程時間預(yù)測的一條城市路段。根據(jù)路段r的歷史汽車電子標識數(shù)據(jù)，將一天的早上06∶00到凌晨00∶00共18 h，按每10 min作為一個時間段，即06∶00至06∶10作為一個時間段，06∶10至06∶20作為一個時間段，以此類推,共劃分為128個時間段。如果路段r有n天的歷史數(shù)據(jù)，那么共有n×128個歷史數(shù)據(jù)的時間段需要計算路段行程時間。然后計算路段r歷史數(shù)據(jù)在各個時間段的路段行程時間估計值，并將計算結(jié)果進行存儲。

2.3 構(gòu)造特征向量

特征向量的組成與路段行程時間需要有一定的相關(guān)性，同時能體現(xiàn)同一路段在不同時間的差異性，為了能夠滿足實時預(yù)測的需求，特征向量還需要能夠較容易地從歷史數(shù)據(jù)集中計算得出。由于交通流的特征，行程時間在時間序列中具有一定自相關(guān)性，所以一般都選擇當前時間段的前幾個時間段的路段行程時間作為特征向量的一部分。對于歷史時段p，選取p時段的前10個時間段(p-1,p-2,…,p-10)進行相關(guān)性分析，結(jié)果表明：當前時間段p與前4個時間段的相關(guān)性相對較高，因此選擇當前時間段的前4個時間段的行程時間(tp-1,tp-2,tp-3,tp-4)作為p時段的特征向量的一部分。

一段時間內(nèi)通過RFID采集器的車流量也反映了當前的道路的通行情況，與當前道路的行程時間有極大相關(guān)性。對于一段道路兩端的2個采集點A、B，假設(shè)時間段p內(nèi)(例如10 min內(nèi))通過采集點A、B的累計車流量分別為VA(p)和VB(p)，則p時間段的前4個時間段內(nèi)通過采集點A、B的車流量作為p時段特征向量的一部分。于是可以得到p時間段特征向量的表達式：

[tp-1,tp-2,tp-3,tp-4,vA(p-1),vB(p-1),…,

vA(p-4),vB(p-4)]

(6)

2.4 K值確定

K值是KNN算法中的唯一參數(shù)，其值的選定直接關(guān)系到預(yù)測結(jié)果的準確性。本文采用交叉驗證的方式來確定最優(yōu)K值，具體步驟如下：

① 選取K的最小值和最大值分別為Kmin和Kmax。

② 將路段r的歷史數(shù)據(jù)集以天為單位隨機平均分為M份，得到數(shù)據(jù)集集合D1,D2,…,DM，然后依次將數(shù)據(jù)集Di(i=1,2,…,M)作為測試數(shù)據(jù)集，其他的M-1份數(shù)據(jù)集作為歷史數(shù)據(jù)集。

③ 取K=K0，K0在最小值Kmin和最大值Kmax之間，計算測試數(shù)據(jù)集Di的平均絕對誤差百分比。

(7)

式中：Np為測試數(shù)據(jù)集中Di中的樣本量；Ar為測試數(shù)據(jù)集Di中第r條記錄的真實值；Ap是當K取值K0時，測試數(shù)據(jù)集Di中應(yīng)用預(yù)測方法得到的預(yù)測值。

④ 當K取K0時，分別按式(7)計算M個數(shù)據(jù)集對應(yīng)的平均絕對誤差百分比，并對這M個值求均值：

(8)

2.5 特征向量相似性度量

對于式(6)的特征向量，由于包括行程時間和車流量兩個不同維度的數(shù)據(jù)，因此采用歸一化的歐幾里德距離公式，將特征向量中的值歸一化到區(qū)間0～1。然后利用式(9)進行特征向量間的距離計算。

(9)

2.6 局部估計方法

應(yīng)用局部估計方法之前，首先在歷史數(shù)據(jù)中尋找與預(yù)測值的特征向量之間距離最近的K個特征向量，然后對這個特征向量所對應(yīng)的值進行加權(quán)估計得到預(yù)測值。由于當歷史數(shù)據(jù)的特征向量與待預(yù)測值的特征向量更接近時，該歷史數(shù)據(jù)的行程時間對待預(yù)測值具有更大的影響，則通過加權(quán)的方式得到路段r在時間段p的路段行程時間預(yù)測值TP(p)。

(10)

式中：TP(p)為待要預(yù)測的路段行程時間值；TK(u)為K個鄰近歷史特征向量中特征向量Xu(u=1,2,…,k)所對應(yīng)的路段行程時間值；ω(XP(p),XH(u))為用于加權(quán)估計的函數(shù)，

(11)

式中：XP(p)為路段r在時間段p對應(yīng)的特征向量；XH(u)表示K個最鄰近的歷史特征向量中的一個；d(XP(p),XH(u))表示XP(p)和向量XH(u)按特征向量相似性度量方法求得的向量之間的距離。

3 實驗

3.1 實驗環(huán)境

本文實驗環(huán)境的硬件配置為16 GB內(nèi)存、1TB的硬盤和一個3.60 GHz 的CPU，操作系統(tǒng)為Windows 7， 64位。實驗中應(yīng)用Java8進行數(shù)據(jù)預(yù)處理和預(yù)測模型的實現(xiàn)，使用MySQL5.1數(shù)據(jù)庫進行數(shù)據(jù)的存儲，同時應(yīng)用Python3.4對實驗的結(jié)果進行可視化展示。

本文實驗選取路段按照城市道路劃分標準，選取城市快速路、主干路各一段，并通過百度API計算路段的行車距離，具體的道路信息如表1所示。

表1 選擇的城市道路的詳細信息

3.2 評價指標

為了對模型的預(yù)測效果進行評估，需要對預(yù)測結(jié)果的誤差進行分析。按式(12)計算平均絕對誤差(mean absolute error，MAE)MMAE，按式(13)計算平均相對誤差百分比(mean absolute percentage error，MAPE)MMAPE。

(12)

(13)

3.3 實驗結(jié)果與分析

在KNN算法中，由于K值的選定對于實驗結(jié)果影響很大，不同路段、不同時間的最優(yōu)K選定均不相同。所以本小節(jié)首先就K值的標定進行了相關(guān)實驗。首先是對于快速路，選定K值在3～80，計算實驗結(jié)果的平均相對誤差，得到的結(jié)果如圖3所示?？梢园l(fā)現(xiàn)，K在取值20時平均相對誤差的值便收斂趨于穩(wěn)定，在K取值31時，平均相對誤差的值最小為0.052。

圖3 快速路平均相對誤差隨K值的變化

通過交叉驗證方式計算，對于不同路段的最優(yōu)K值選定如表2所示。

表2 不同路段的最優(yōu)K值選定

取K值為31，通過歷史數(shù)據(jù)對快速路在2016-03-05和2016-03-06的路段行程時間進行預(yù)測，預(yù)測結(jié)果和實際行程時間的對比如圖4、5所示。

圖4 快速路在2016-03-05的行程時間預(yù)測

圖5 快速路在2016-03-06的行程時間預(yù)測

對快速路行程時間預(yù)測的誤差分析表明，2016-03-05預(yù)測結(jié)果的平均相對誤差值為0.022，2016-03-06預(yù)測結(jié)果的平均相對誤差值為0.028。結(jié)果表明：行程時間預(yù)測模型較好地適應(yīng)了快速路的情況。具體的相對誤差如圖6和圖7所示。

取K值為23，通過歷史數(shù)據(jù)對主干路在2016-03-05和2016-03-06的路段行程時間進行預(yù)測，預(yù)測結(jié)果和實際行程時間的對比如圖8、9所示。

圖6 快速路在2016-03-05的行程時間預(yù)測相對誤差圖

圖7 快速路在2016-03-06的行程時間預(yù)測相對誤差圖

圖8 主干路在2016-03-05的行程時間預(yù)測

圖9 主干路在2016-03-06的行程時間預(yù)測

對主干路行程時間預(yù)測的誤差分析表明：2016-03-05預(yù)測結(jié)果的平均相對誤差值為0.092，2016-03-06預(yù)測結(jié)果的平均相對誤差值為0.071。通過主干路的行程時間預(yù)測可以發(fā)現(xiàn)，尤其是在對3月6日的結(jié)果預(yù)測中，對少數(shù)行程時間相對很長的時間段(即嚴重擁堵時段)的預(yù)測結(jié)果誤差很大，說明預(yù)測模型對突發(fā)的路段嚴重擁堵情況的適應(yīng)情況不是很好。

綜合上面的實驗結(jié)果，得到預(yù)測模型的預(yù)測結(jié)果誤差如表3所示。

表3 實驗結(jié)果誤差

3.4 對比實驗

為了對比基于KNN算法的行程時間預(yù)測模型的效果，本節(jié)將基于KNN算法的預(yù)測模型與常用的歷史平均模型以及自回歸移動平均模型(ARIMA模型)的結(jié)果進行對比。得到對快速路和主干路的預(yù)測結(jié)果，如表4、5所示。

表4 不同模型在快速路的預(yù)測結(jié)果

表5 不同模型在主干路的預(yù)測結(jié)果

由表4、5的結(jié)果容易發(fā)現(xiàn)：基于KNN算法的行程時間預(yù)測模型在快速路的預(yù)測結(jié)果要明顯優(yōu)于歷史平均模型和ARIMA模型的預(yù)測結(jié)果。

4 結(jié)束語

本文基于汽車電子標識數(shù)據(jù)集，提出了基于KNN算法的城市路段行程時間短時預(yù)測方法，結(jié)果表明：在城市快速路和主干路都取得了較好的預(yù)測效果。本文的預(yù)測結(jié)果可為大量的城市駕車出行車的道路選擇提供參考信息，以讓出行者避免擁堵而減少通勤時間；另一方面可為城市交通管理者提供相關(guān)的決策信息。

在下一步研究中，一方面可考慮實時處理汽車電子標識流數(shù)據(jù)，提高短時行程時間預(yù)測的實時性，同時可增大實驗的數(shù)據(jù)集，并將歷史數(shù)據(jù)集按是否擁堵、是否為周末等進行分類，分別對相應(yīng)的數(shù)據(jù)集構(gòu)建預(yù)測模型，以進一步提高預(yù)測結(jié)果的精確性。