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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 路段行程時(shí)間估計(jì)

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

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

(1)

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

(2)

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

{Tx=tj-si|Xi=Yj}

(3)

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

{Tx,x=1,…,L}

(4)

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

(5)

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

2.1 K最近鄰算法

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

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

2.2 數(shù)據(jù)準(zhǔn)備

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

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

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

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

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

[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ù)測(cè)結(jié)果的準(zhǔn)確性。本文采用交叉驗(yàn)證的方式來確定最優(yōu)K值，具體步驟如下：

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

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

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

(7)

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

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

(8)

2.5 特征向量相似性度量

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

(9)

2.6 局部估計(jì)方法

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

(10)

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

(11)

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

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

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

本文實(shí)驗(yàn)選取路段按照城市道路劃分標(biāo)準(zhǔn)，選取城市快速路、主干路各一段，并通過百度API計(jì)算路段的行車距離，具體的道路信息如表1所示。

表1 選擇的城市道路的詳細(xì)信息

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

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

(12)

(13)

3.3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 實(shí)驗(yàn)結(jié)果誤差

3.4 對(duì)比實(shí)驗(yàn)

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

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

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

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

4 結(jié)束語

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

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