余沁瀟 凌 帥 吳 剛，2 馬壽峰▲

（1.天津大學(xué)管理與經(jīng)濟(jì)學(xué)部 天津 300072；2.天津高速公路集團(tuán)有限公司 天津 300384）

0 引言

隨著智能交通系統(tǒng)的發(fā)展，交通管理模式逐漸由被動(dòng)轉(zhuǎn)為主動(dòng)，短時(shí)交通流預(yù)測(cè)作為智能交通系統(tǒng)的核心技術(shù)之一，為交通信息服務(wù)、交通控制與誘導(dǎo)提供基礎(chǔ)數(shù)據(jù)，對(duì)預(yù)測(cè)效率和精度都要求較高。短時(shí)交通流預(yù)測(cè)的研究方法可分為2類：傳統(tǒng)的基于數(shù)學(xué)模型的方法；數(shù)據(jù)驅(qū)動(dòng)式的計(jì)算智能方法［1］。近年來(lái)，面對(duì)復(fù)雜的路況以及大量的交通數(shù)據(jù)集，第1類方法存在明顯不足，學(xué)者們逐漸將研究重點(diǎn)轉(zhuǎn)向后者［2－5］。非參數(shù)回歸預(yù)測(cè)就是1種基于數(shù)據(jù)驅(qū)動(dòng)式的計(jì)算智能方法，它實(shí)際上是基于模式匹配和數(shù)據(jù)挖掘的方法，其優(yōu)點(diǎn)在于它完全是數(shù)據(jù)驅(qū)動(dòng)的，幾乎不需要先驗(yàn)知識(shí)，只需要有足夠規(guī)模的模式庫(kù)，就可以做到比較準(zhǔn)確的預(yù)測(cè)。

近年來(lái)，許多學(xué)者將非參數(shù)回歸方法應(yīng)用于交通流預(yù)測(cè)，但在實(shí)際應(yīng)用中存在預(yù)測(cè)時(shí)間長(zhǎng)，實(shí)時(shí)性差的缺陷。1991 年，Davis和Nihan［6］首次將非參數(shù)回歸的方法應(yīng)用于交通預(yù)測(cè)中，指出該方法適用于預(yù)測(cè)非線性的交通數(shù)據(jù)，但該算法需要維護(hù)1個(gè)龐大且具有代表性的歷史數(shù)據(jù)庫(kù)，因此運(yùn)行所耗費(fèi)的時(shí)間相對(duì)較長(zhǎng)。Smith等［7］將非參數(shù)回歸模型應(yīng)用于單點(diǎn)短時(shí)交通流預(yù)測(cè)，但在實(shí)際使用上仍存在搜索速度過(guò)慢的問(wèn)題。后來(lái)，許多學(xué)者就這一問(wèn)題提出解決方案，Oswald等［8］用KD 樹(shù)來(lái)建立歷史模式庫(kù)進(jìn)行模糊最近鄰搜索，縮短了K 近鄰算法的運(yùn)行時(shí)間。張曉利等［9］針對(duì)非參數(shù)回歸中案例庫(kù)生成難和搜索速度慢的問(wèn)題，提出1種基于平衡二叉樹(shù)的K－鄰域非參數(shù)回歸預(yù)測(cè)方法，該算法首先對(duì)歷史數(shù)據(jù)進(jìn)行聚類，然后采用平衡二叉樹(shù)建立歷史數(shù)據(jù)庫(kù)，預(yù)測(cè)速度有一定提高。賈寧等［10］用KD 樹(shù)作為模式庫(kù)的存儲(chǔ)結(jié)構(gòu)，并基于KD 樹(shù)進(jìn)行最近鄰搜索，有效地提高了近鄰搜索速度。但KD 樹(shù)的形態(tài)高度依賴于數(shù)據(jù)的插入順序，不合理的插入順序會(huì)影響KD 樹(shù)的結(jié)構(gòu)，從而影響查詢效率。另外，數(shù)據(jù)的刪除會(huì)導(dǎo)致KD 樹(shù)結(jié)點(diǎn)的重新組織，而現(xiàn)實(shí)中預(yù)測(cè)系統(tǒng)不斷增加新數(shù)據(jù)，剔除舊數(shù)據(jù)，這使得模式庫(kù)的更新耗費(fèi)大量時(shí)間［11］。

綜上所述，非參數(shù)回歸方法可以解決交通流預(yù)測(cè)中的非線性和不確定性問(wèn)題，使預(yù)測(cè)精度達(dá)到滿意的效果。但該方法要求大量的歷史數(shù)據(jù)來(lái)構(gòu)建歷史模式庫(kù)，當(dāng)數(shù)據(jù)量和狀態(tài)向量維數(shù)增長(zhǎng)時(shí)，預(yù)測(cè)的速度將下降，從而影響預(yù)測(cè)的實(shí)時(shí)性。隨著大數(shù)據(jù)時(shí)代的到來(lái)，交通流數(shù)據(jù)不斷增長(zhǎng)，同時(shí)為了準(zhǔn)確預(yù)測(cè)交通流量，考慮的影響因素也越來(lái)越多，如檢測(cè)點(diǎn)歷史流量、速度、占有率，上下游的流量、速度、占有率，信號(hào)燈情況，天氣因素，地理位置等。這些問(wèn)題使得非參回歸方法中歷史模式數(shù)據(jù)庫(kù)建立和模式搜索的速度受到挑戰(zhàn)，而傳統(tǒng)的線性數(shù)據(jù)庫(kù)已經(jīng)不能滿足預(yù)測(cè)的實(shí)時(shí)性要求。因此，筆者提出了1種基于R 樹(shù)的K 近鄰非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法，該方法使用R 樹(shù)來(lái)建立模式庫(kù)，根據(jù)數(shù)據(jù)在空間中的分布進(jìn)行存儲(chǔ)，使相近數(shù)據(jù)存儲(chǔ)在同1個(gè)或相鄰的節(jié)點(diǎn)中，這便使得K 近鄰搜索的速度得以提高，從而提高預(yù)測(cè)的實(shí)時(shí)性。

1 基于R 樹(shù)的交通流非參數(shù)回歸預(yù)測(cè)方法

1.1 交通流非參數(shù)回歸預(yù)測(cè)方法

非參數(shù)回歸是1種數(shù)據(jù)驅(qū)動(dòng)的預(yù)測(cè)技術(shù)，是1種適合于不確定性和非線性性動(dòng)態(tài)系統(tǒng)的非參數(shù)估計(jì)方法。將其用到交通流預(yù)測(cè)中的主要過(guò)程就是在數(shù)據(jù)庫(kù)中尋找與當(dāng)前交通模式相近的歷史模式，再用這些歷史模式去預(yù)測(cè)當(dāng)前交通流量。在數(shù)據(jù)庫(kù)中，1條交通流模式由2部分組成，一部分為斷面交通流的狀態(tài)向量，即影響該斷面交通流量的因素f1～fn，如該斷面以及上下游的歷史交通流特征（流量、速度、占有率）、天氣、地理位置等；另一部分則為斷面的交通流量q，它由狀態(tài)向量所決定。因此，1 條交通流模式可表示為｛f1（ti），…，fn（ti）｜q（ti）｝。隨著交通系統(tǒng)的運(yùn)行，交通流模式將不斷被加入到歷史模式數(shù)據(jù)庫(kù)中。

1.2 R樹(shù)結(jié)構(gòu)

R 樹(shù)［12］最初由Guttman于1984年提出，作為1種空間索引機(jī)制，它將空間對(duì)象按范圍劃分，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)1個(gè)空間區(qū)域，在物理存儲(chǔ)上，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)1個(gè)磁盤頁(yè)。相應(yīng)于交通流數(shù)據(jù)，由于它的狀態(tài)向量往往都是多維的，因此1條交通流模式可被看作是多維空間中的1個(gè)點(diǎn)，那些狀態(tài)向量相似的模式在多維空間中是相鄰的，它們將被劃分到同1個(gè)字空間存入同1個(gè)磁盤頁(yè)。因此在進(jìn)行數(shù)據(jù)檢索時(shí)，可根據(jù)數(shù)據(jù)的空間位置快速有效地在多維空間中找到1組相似的數(shù)據(jù)。R 樹(shù)中的結(jié)點(diǎn)分為2種：葉結(jié)點(diǎn)和非葉結(jié)點(diǎn)，葉結(jié)點(diǎn)存儲(chǔ)的是其區(qū)域范圍內(nèi)所有空間對(duì)象的最小邊界矩形（minimum bounding rectangle，MBR），非葉結(jié)點(diǎn)存儲(chǔ)的是包絡(luò)其所有子結(jié)點(diǎn)所在空間范圍的MBR。該設(shè)計(jì)使得對(duì)空間對(duì)象進(jìn)行搜索時(shí)只需訪問(wèn)小部分結(jié)點(diǎn)，并且可以方便快速地進(jìn)行空間對(duì)象的插入和刪除操作，無(wú)需對(duì)樹(shù)中所有數(shù)據(jù)進(jìn)行空間上的再組織。

R 樹(shù)空間數(shù)據(jù)存儲(chǔ)方法是把多維空間進(jìn)行遞歸劃分，最終將空間對(duì)象劃分到不同的子空間中。每個(gè)子空間都由1個(gè)結(jié)點(diǎn)表示，而每個(gè)結(jié)點(diǎn)有惟一的記錄形式。葉結(jié)點(diǎn)的記錄形式為：（M，i）。其中：M為包絡(luò)了該結(jié)點(diǎn)中所有空間對(duì)象的MBR；i為該結(jié)點(diǎn)的標(biāo)識(shí)即其物理存儲(chǔ)地址。非葉結(jié)點(diǎn)的記錄形式為：（M，p）。其中：M為包絡(luò)了其所有子結(jié)點(diǎn)所在區(qū)域的MBR；p為指向其子結(jié)點(diǎn)存儲(chǔ)位置的指針。對(duì)于n維空間中的1 個(gè)MBR，M可表示為M＝（I0，I1，…，In－1），其中：Ii指空間對(duì)象在第i維上的取值范圍［a，b］，它在數(shù)值上等于該空間中所有數(shù)據(jù)第i維的最小值和最大值。

R 樹(shù)的構(gòu)造方法就是將數(shù)據(jù)點(diǎn)逐個(gè)插入到R樹(shù)中，在插入過(guò)程中，尋找最優(yōu)的路徑，使相近數(shù)據(jù)聚集在同1 個(gè)結(jié)點(diǎn)中，保證R 樹(shù)的結(jié)構(gòu)穩(wěn)定。下面給出R 樹(shù)構(gòu)造的偽代碼，設(shè)R 為R 樹(shù)的根結(jié)點(diǎn)，E為要存入到R 樹(shù)中的數(shù)據(jù)。

1.3 基于R 樹(shù)的K 近鄰搜索策略

歷史模式數(shù)據(jù)庫(kù)中交通流模式的狀態(tài)向量是多維的，而且模式數(shù)量眾多，R 樹(shù)組織結(jié)構(gòu)的特點(diǎn)就是將空間中相鄰的對(duì)象劃分在1個(gè)區(qū)域內(nèi)，使它們擁有共同的祖先，待測(cè)對(duì)象與其他對(duì)象間的距離可以通過(guò)它們的祖先與待測(cè)對(duì)象的距離表示。使用R 樹(shù)進(jìn)行近鄰搜索，可通過(guò)祖先與待測(cè)對(duì)象的距離剔除大部分距離遠(yuǎn)的分支，這樣便可提高查找效率。

R 樹(shù)中結(jié)點(diǎn)存儲(chǔ)的是其若干子結(jié)點(diǎn)或空間對(duì)象的MBR，MBR 為包絡(luò)對(duì)象所在空間的最小邊界矩形，通常用其主對(duì)角線上的2個(gè)頂點(diǎn)表示，例如，在二維空間里，用（xl，xh，yl，yh）表示。在本文中，用minDist表示點(diǎn)p到空間內(nèi)某矩形R的最小距離，若點(diǎn)p在矩形R內(nèi)，則兩者距離為零；若點(diǎn)p在矩形R外，則兩者的距離為p到矩形R上最近1點(diǎn)的歐式距離平方值。則minDist（p，R）表示為［13］

式中：pi為n維待測(cè)點(diǎn)p第i維的值，i＝1，2，…，n；ri為n維空間矩形R在第i維與待測(cè)點(diǎn)p距離較近的值，i＝1，2，…，n；si為n維空間矩形R在第i維上的最小值。ti為n維空間矩形R在第i維上的最大值。

可以證明，點(diǎn)p到MBR的minDist小于等于點(diǎn)p到該MBR中任意對(duì)象O的距離［14］。因此minDist值可以看作待測(cè)點(diǎn)p到每1個(gè)MBR中對(duì)象的距離下限，在查找過(guò)程中可以按照minDist值從小到大排列，確定MBR的搜索順序，從而減少需要訪問(wèn)結(jié)點(diǎn)的數(shù)量。但因?yàn)镸BR內(nèi)對(duì)象分布不均勻，待測(cè)點(diǎn)到MBR中對(duì)象的距離比minDist確定的距離遠(yuǎn)，如果先訪問(wèn)minDist值小的MBR，并將其中的對(duì)象都作為近鄰點(diǎn)，那么將損失更優(yōu)的對(duì)象，從而影響了預(yù)測(cè)精度。如圖1 所 示，minDist（p，MBR1）＜minDist（p，MBR2），但MBR2中的對(duì)象多集中于靠近點(diǎn)p一側(cè)，而MBR1中的對(duì)象多集中于遠(yuǎn)離點(diǎn)p的一側(cè)。因此，點(diǎn)p到MBR2中對(duì)象的距離比到MBR1中對(duì)象的距離小，若將MBR1中的對(duì)象均視為p的近鄰，則會(huì)影響預(yù)測(cè)精度。為解決該問(wèn)題，引入?yún)?shù)距離上限r(nóng)，它表示近鄰點(diǎn)與待測(cè)點(diǎn)之間的距離上限，若MBR中的對(duì)象到p的距離小于r，則將其視為近鄰點(diǎn)。因此，即使某個(gè)MBR到待測(cè)點(diǎn)p的minDist較小，若其中的對(duì)象到p的距離都大于r，舍棄該MBR，繼續(xù)搜索其它的MBR，直到搜索到K個(gè)近鄰或者遍歷完整棵樹(shù)。

圖1 minDist示意圖Fig.1 minDist

因此筆者采用的K 近鄰搜索策略是：首先設(shè)定1個(gè)距離上限r(nóng)，對(duì)于MBR中的任意對(duì)象O，當(dāng)Dist（p，O）≤r時(shí)，將其視為p的近鄰；然后對(duì)R 樹(shù)進(jìn)行有序深度優(yōu)先遍歷，從根結(jié)點(diǎn)開(kāi)始向下逐層訪問(wèn)MBR，對(duì)于同層的結(jié)點(diǎn)，計(jì)算所有MBR到待測(cè)點(diǎn)p的minDist，然后將結(jié)點(diǎn)按minDist由小到大排序后放入鏈表ABL中；之后選擇minDist最小的結(jié)點(diǎn)遞歸進(jìn)行以上過(guò)程，直至到達(dá)葉結(jié)點(diǎn)，在葉結(jié)點(diǎn)中選擇距離小于r的對(duì)象放入近鄰集合中；若近鄰個(gè)數(shù)等于K或遍歷完整棵樹(shù)，則搜索完成，否則，返回鏈表中ABL搜索下一個(gè)結(jié)點(diǎn)。

設(shè)R 樹(shù)的根節(jié)點(diǎn)為R，待測(cè)點(diǎn)為p，搜索的距離上限為r，近鄰個(gè)數(shù)為K，近鄰點(diǎn)存于Nearest列表中。則該搜索策略的偽代碼如下：

1.4 預(yù)測(cè)算法

預(yù)測(cè)算法是影響預(yù)測(cè)精度的重要因素，它是根據(jù)K 近鄰查找得到的近鄰點(diǎn)，利用預(yù)測(cè)函數(shù)做出合理的預(yù)測(cè)。

筆者采用帶權(quán)重的預(yù)測(cè)方法，設(shè)搜索到的K個(gè)近鄰點(diǎn)為n1，n2，…，nk，對(duì)應(yīng)的決策屬性為y1（t＋1），…，yk（t＋1），待測(cè)點(diǎn)與第i個(gè)近鄰點(diǎn)的距離為di（i＝1，2，…，k），距離越小的點(diǎn)在預(yù)測(cè)中所占的權(quán)重越大，則預(yù)測(cè)算法如下。

2 實(shí)驗(yàn)與應(yīng)用

2.1 線性和R 樹(shù)結(jié)構(gòu)下K 近鄰搜索速度的對(duì)比

首先針對(duì)2 種結(jié)構(gòu)下的歷史模式庫(kù)進(jìn)行K近鄰搜索速度的比較實(shí)驗(yàn)。在實(shí)驗(yàn)中，每個(gè)數(shù)據(jù)對(duì)象由10維狀態(tài)向量表示，狀態(tài)向量中的各分量是隨機(jī)生成的0～1 之間的實(shí)數(shù)，距離上限r(nóng)為1，近鄰個(gè)數(shù)K＝20。對(duì)不同規(guī)模的模式庫(kù)進(jìn)行查找實(shí)驗(yàn)。實(shí)驗(yàn)程序使用Java語(yǔ)言編寫，硬件環(huán)境為2.4GCPU，4G 內(nèi)存，實(shí)驗(yàn)結(jié)果見(jiàn)圖2。

圖2 R 樹(shù)結(jié)構(gòu)與線性結(jié)構(gòu)的搜索速度對(duì)比Fig.2 The comparison of searching performances under the R－tree and linear structure

由圖2可見(jiàn)，隨著數(shù)據(jù)規(guī)模的增大，線性結(jié)構(gòu)的查找耗時(shí)增長(zhǎng)快，而R 樹(shù)結(jié)構(gòu)查找速度比較穩(wěn)定，在耗時(shí)上沒(méi)有明顯的增長(zhǎng)。這是因?yàn)樵诰€性結(jié)構(gòu)的數(shù)據(jù)庫(kù)中進(jìn)行K 近鄰查找時(shí)，需要遍歷整個(gè)數(shù)據(jù)庫(kù)，進(jìn)行1次最近鄰搜索的時(shí)間復(fù)雜度是O（kN），k是數(shù)據(jù)對(duì)象的維數(shù)，N是數(shù)據(jù)庫(kù)規(guī)模，因此查找時(shí)間與數(shù)據(jù)庫(kù)規(guī)模N成正比。R 樹(shù)的查找速度與其遍歷的節(jié)點(diǎn)數(shù)目以及每個(gè)節(jié)點(diǎn)中數(shù)據(jù)對(duì)象的數(shù)量成正比，而其遍歷的節(jié)點(diǎn)數(shù)目與R樹(shù)的高度有關(guān)，R 樹(shù)的高度可表示為，因此R 樹(shù)最近鄰查找的時(shí)間復(fù)雜度可表示為O（k·，式中：k為數(shù)據(jù)對(duì)象的維數(shù)；N為數(shù)據(jù)庫(kù)規(guī)模；m為節(jié)點(diǎn)容量下限。因此使用R 樹(shù)進(jìn)行K 近鄰查找的速度明顯優(yōu)于線性結(jié)構(gòu)。

2.2 預(yù)測(cè)應(yīng)用

2.2.1 數(shù)據(jù)來(lái)源

實(shí)驗(yàn)采用的交通數(shù)據(jù)來(lái)自加利福尼亞州交通局的路況監(jiān)測(cè)系統(tǒng)［15］（caltrans performance measurement system），這些數(shù)據(jù)采集自圣地亞哥市I5號(hào)公路由北向南24.4km（15.2 mile）處的檢測(cè)器，包含了2013年1月1日～2014年1 月15日的流量數(shù)據(jù)，其中每5min記錄1條交通流量，1d共288個(gè)樣本。實(shí)驗(yàn)中將所有樣本的交通流量進(jìn)行歸一化處理，以2013年全年105 120條數(shù)據(jù)作為歷史模式來(lái)建立數(shù)據(jù)庫(kù)，2014 年的4 320條數(shù)據(jù)作為測(cè)試數(shù)據(jù)來(lái)進(jìn)行流量預(yù)測(cè)，預(yù)測(cè)周期為5 min。在預(yù)測(cè)中，僅考慮交通流量之間的時(shí)間關(guān)聯(lián)，用前10個(gè)時(shí)刻的流量來(lái)預(yù)測(cè)本時(shí)刻的流量。

2.2.2 近鄰個(gè)數(shù)和距離上限的確定

在本文涉及的K 近鄰搜索策略中，對(duì)最后預(yù)測(cè)精度及速度起到影響作用的參數(shù)有2 個(gè)，1 個(gè)是近鄰個(gè)數(shù)K，另1個(gè)是距離上限r(nóng)。對(duì)于近鄰個(gè)數(shù)K而言，過(guò)大或過(guò)小都會(huì)影響非參數(shù)回歸預(yù)測(cè)結(jié)果，如果K過(guò)大，那么需要搜索較多的結(jié)點(diǎn)，增加搜索耗時(shí)。如果K過(guò)小，則會(huì)降低預(yù)測(cè)精度。通過(guò)對(duì)比實(shí)驗(yàn)檢驗(yàn)K值與預(yù)測(cè)誤差的關(guān)系，其他參數(shù)固定，K分別取不同的值進(jìn)行預(yù)測(cè)，預(yù)測(cè)效果見(jiàn)圖3，當(dāng)K值為20時(shí)，預(yù)測(cè)結(jié)果的平均相對(duì)誤差最小，因此實(shí)驗(yàn)中K值取20。

圖3 近鄰個(gè)數(shù)K 與平均相對(duì)誤差關(guān)系Fig.3 The relationship between the number of neighbors and average relative error

對(duì)于距離上限r(nóng)來(lái)說(shuō)，如果r過(guò)大將起不到約束minDist的作用，雖然在進(jìn)行K 近鄰查找時(shí)，能較快找到K個(gè)近鄰，但這些近鄰與待測(cè)點(diǎn)的距離卻相對(duì)較遠(yuǎn)，即這些點(diǎn)并不是待測(cè)點(diǎn)的最優(yōu)匹配點(diǎn)，在未訪問(wèn)的結(jié)點(diǎn)中可能存在與待測(cè)點(diǎn)更加匹配的數(shù)據(jù)。這樣雖然達(dá)到一定的預(yù)測(cè)效率，卻在預(yù)測(cè)精度上略有不足。如果r過(guò)小，即對(duì)待測(cè)點(diǎn)的近鄰要求更嚴(yán)格，這樣在近鄰查找過(guò)程中將訪問(wèn)更多的結(jié)點(diǎn)來(lái)查找最優(yōu)近鄰，雖然提高預(yù)測(cè)精度，但是卻以犧牲預(yù)測(cè)效率為代價(jià)。圖4是不同r值與耗時(shí)的關(guān)系圖，在實(shí)驗(yàn)中，從0 開(kāi)始，每隔0.01 取1 個(gè)r值，直到r為1。每 個(gè)r值，進(jìn)行20次K 近鄰查找，其中K＝20，再計(jì)算平均耗時(shí)，結(jié)果如圖4所示，當(dāng)距離上限r(nóng)從0增到0.05時(shí)，耗時(shí)顯著減小，當(dāng)距離上限r(nóng)繼續(xù)增大時(shí)，耗時(shí)漸趨平穩(wěn)。

圖4 r值與耗時(shí)的關(guān)系Fig.4 The relationship between r and time－consuming

2.2.3 預(yù)測(cè)結(jié)果

非參數(shù)回歸是通過(guò)歷史數(shù)據(jù)對(duì)未來(lái)數(shù)據(jù)的模擬，方法自身具有一定誤差。線性結(jié)構(gòu)下的非參數(shù)回歸下的K近鄰搜索，在遍歷完所有的模式的前提下，找出K個(gè)近鄰點(diǎn)，所得近鄰點(diǎn)是距離待測(cè)點(diǎn)的最近的前K個(gè)，因此，它的誤差可以看作是非參數(shù)回歸方法自身的誤差。表1為線性結(jié)構(gòu)下，近鄰個(gè)數(shù)為20時(shí)的預(yù)測(cè)結(jié)果。

表1 線性結(jié)構(gòu)下的預(yù)測(cè)誤差及耗時(shí)Tab.1 Average relative error and time－consuming based on linear structure

R 樹(shù)結(jié)構(gòu)下的非參數(shù)回歸，除了非參數(shù)回歸自身的誤差之外，還應(yīng)考慮R 樹(shù)下K近鄰查找的誤差，該方法查找出來(lái)的K個(gè)近鄰點(diǎn)，并不是離待測(cè)點(diǎn)最近的K個(gè)近鄰，因此預(yù)測(cè)誤差較大。但是在該方法中，誤差的大小在一定程度上可以通過(guò)距離上限r(nóng)調(diào)節(jié)。如表2所示，隨著距離上限r(nóng)減小，預(yù)測(cè)耗時(shí)不斷增加，但都低于線性結(jié)構(gòu)下的預(yù)測(cè)耗時(shí)，而平均相對(duì)誤差不斷減小，接近甚至優(yōu)于線性結(jié)構(gòu)下的預(yù)測(cè)誤差。這是因?yàn)镽 樹(shù)的K近鄰查找算法中共有2個(gè)參數(shù)來(lái)約束近鄰點(diǎn)，當(dāng)r值較大時(shí)，它對(duì)近鄰點(diǎn)的約束條件放寬，更多的鄰居點(diǎn)被當(dāng)作近鄰點(diǎn)，此時(shí)近鄰個(gè)數(shù)K起到約束作用，即從多于K個(gè)的近鄰點(diǎn)中選出前K個(gè)與待測(cè)點(diǎn)最相似的近鄰點(diǎn)；當(dāng)r值較小時(shí)，越來(lái)越少的鄰居點(diǎn)符合近鄰點(diǎn)的要求，此時(shí)存在少數(shù)待測(cè)點(diǎn)的近鄰個(gè)數(shù)少于K，但這些近鄰點(diǎn)與待測(cè)點(diǎn)的相似度更高，因此誤差相對(duì)減小。

在表2中，當(dāng)距離上限大于等于0.02 時(shí)，R樹(shù)搜索到的平均近鄰個(gè)數(shù)為20個(gè)，此時(shí)線性結(jié)構(gòu)下搜索到的20個(gè)近鄰相對(duì)更精確，因此線性結(jié)構(gòu)下的預(yù)測(cè)誤差總是小于R 樹(shù)結(jié)構(gòu)下的預(yù)測(cè)誤差.但是在預(yù)測(cè)速度上，R 樹(shù)結(jié)構(gòu)下的搜索耗時(shí)遠(yuǎn)小于表1中線性結(jié)構(gòu)下的搜索耗時(shí)。當(dāng)距離上限為0.02時(shí)，R 樹(shù)結(jié)構(gòu)下的預(yù)測(cè)誤差比線性結(jié)構(gòu)的預(yù)測(cè)誤差上升了8.8%，但預(yù)測(cè)速度提高了59.6%。當(dāng)距離上限小于0.02時(shí)，R 樹(shù)搜索到的平均近鄰個(gè)數(shù)都小于20，與平均近鄰個(gè)數(shù)為20的線性結(jié)構(gòu)預(yù)測(cè)結(jié)果缺乏可比性，因此，為線性結(jié)構(gòu)下的K近鄰查找算法添加距離上限這一相同約束，其預(yù)測(cè)結(jié)果如表3所示，與表1結(jié)果比較，平均相對(duì)誤差增大，這是因?yàn)閷?duì)于大多數(shù)待測(cè)點(diǎn)來(lái)說(shuō)，模式庫(kù)中存在多余20個(gè)的近鄰點(diǎn)，在考慮距離上限這一約束后，只要滿足約束條件即可視為近鄰點(diǎn)，無(wú)需遍歷完所有模式，從而這些近鄰點(diǎn)與待測(cè)點(diǎn)的相似度變小，因此預(yù)測(cè)誤差增大，預(yù)測(cè)耗時(shí)減小。由表2與表3的對(duì)比結(jié)果顯示，2種結(jié)構(gòu)下搜索到的近鄰個(gè)數(shù)相等且都小于20，在同一水平的距離上限下，R 樹(shù)憑借自身的空間聚類特征，可以更快且更準(zhǔn)確地找到滿足條件的近鄰，因此，R 樹(shù)結(jié)構(gòu)下的預(yù)測(cè)精度和速度都優(yōu)于線性結(jié)構(gòu)下的預(yù)測(cè)結(jié)果。

表2 R 樹(shù)結(jié)構(gòu)下不同距離上限r(nóng)的預(yù)測(cè)結(jié)果Tab.2 The predicting result under different distance limits r based on R－tree

表3 線性結(jié)構(gòu)下不同距離上限r(nóng)的預(yù)測(cè)誤差及耗時(shí)Tab.3 The predicting result under different distance limits r based on linear structure

3 結(jié)束語(yǔ)

交通流影響因素眾多、交通數(shù)據(jù)海量增長(zhǎng)，這2個(gè)因素分別導(dǎo)致非參數(shù)回歸中的狀態(tài)向量維數(shù)增長(zhǎng)、歷史模式庫(kù)規(guī)模擴(kuò)大，最終影響非參數(shù)回歸的預(yù)測(cè)速度，尤其在短時(shí)交通流預(yù)測(cè)中，不能滿足預(yù)測(cè)實(shí)時(shí)性的要求。因此，筆者提出1種基于R樹(shù)索引結(jié)構(gòu)的非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法，使用R 樹(shù)建立空間高維模式庫(kù)，并依據(jù)R 樹(shù)的空間聚類特點(diǎn)使用K 近鄰搜索算法。實(shí)驗(yàn)結(jié)果顯示這一方法在預(yù)測(cè)精度達(dá)到要求的前提下，能夠大幅度地提高預(yù)測(cè)速度，即使模式庫(kù)規(guī)模不斷擴(kuò)大，預(yù)測(cè)耗時(shí)的增長(zhǎng)是緩慢穩(wěn)定的，這為實(shí)現(xiàn)大規(guī)模路網(wǎng)下的交通誘導(dǎo)和控制提供了1種方法。

［1］賀國(guó)光，李 宇，馬壽峰.基于數(shù)學(xué)模型的短時(shí)交通流預(yù)測(cè)方法探討［J］.系統(tǒng)工程理論與實(shí)踐，2000，12（11）：51－56.He Guoguang，Li Yu，Ma Shoufeng.Discussion on short－term traffic flow forecasting methods based on mathematical models［J］.Systems Engineering－theory＆Practice，2000，12（11）：51－56.（in Chinese）

［2］Karlaftis M G，Vlahogianni E I.Statistical methods versus neural networks in transportation research：Differences，similarities and some insights［J］.Transportation Research Part C：Emerging Technologies，2011，19（3）：387－399.

［3］劉 洋，馬壽峰.基于聚類分析的非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法［J］.交通信息與安全，2013，31（2）：27－32.Liu Yang，Ma Shoufeng.Non－parametric Regression for Short－term Traffic Flow Forecasting Based on Cluster Analysis［J］.Journal of Transport Information and Safety，2013（2）：27－32.（in Chinese）.

［4］Vlahogianni E I，Karlaftis M G，Golias J C.Short－term traffic forecasting：Where we are and where we’re going［J］.Transportation Research Part C：Emerging Technologies，2014，43（1）：3－19.

［5］徐華文，魏志強(qiáng).基于數(shù)據(jù)流集成回歸的短時(shí)交通流預(yù)測(cè)［J］.交通信息與安全，2014，32（4）：14－19.Xue Huawen，Wei Zhiqiang.An Online Shortterm Traffic Flow Prediction Model Based on Data Stream Ensemble Regression［J］.Journal of Transport Information and Safety，2014（4）：14－19.（in Chinese）.

［6］Davis G A，Nihan N L.Nonparametric regression and short－term freeway traffic forecasting［J］.Journal of Transportation Engineering，1991，117（2）：178－188.

［7］Smith B L，Demetsky M J.Traffic flow forecasting：Comparison of modeling approaches［J］.Journal of Transportation Engineering，1997，123（4）：261－266.

［8］Oswald R K，Scherer W T，Smith B L.Traffic flow forecasting using approximate nearest neighbor nonparametric regression［R］.Final Project of ITS Center Project：Traffic Forecasting：Non－parametric Regressions，Berkeley，CA：UC Berkeley Transportation library，2000.

［9］張曉利，賀國(guó)光，陸化普.基于K－鄰域非參數(shù)回歸短時(shí)交通流預(yù)測(cè)方法［J］.系統(tǒng)工程學(xué)報(bào)，2009，24（2）：178－183.Zhang Xiaoli，He Guoguang，Lu Huapu.Shortterm traffic flow forecasting based on K－nearest neighbors non－parametric regression［J］.Journal of Systems Engineering，2009，24（2）：178－183.（in Chinese）.

［10］賈 寧，馬壽峰，鐘石泉.基于遺傳算法優(yōu)化和KD樹(shù)的交通流非參數(shù)回歸預(yù)測(cè)方法［J］.控制與決策，2012，27（7）：991－996.Jia Ning，Ma Shoufeng，Zhong Shiquan.Nonparameter－regression traffic flow forecast method based on KD－tree and genetic optimization［J］.Control and Decision，2012，27（7）：991－996.（in Chinese）.

［11］Bentley J L.Multidimensional binary search trees used for associative searching［J］.Communications of the ACM，1975，18（9）：509－517.

［12］Guttman A.R－trees：A dynamic index structure for spatial searching［J］.ACM，1984，14（2）：47－57.

［13］Papadopoulos A，Manolopoulos Y.Performance of nearest neighbor queries in R－trees［C］∥Database Theory－ICDT′97.Springer Berlin Heidelberg，Delphi，Greece：Trier University，1997：394－408.

［14］Roussopoulos N，Kelley S，Vincent F.Nearest neighbor queries［J］.ACM Sigmod Record，ACM，1995，24（2）：71－79.

［15］PeMS.Caltrans Performance Measurement System［EB／OL］.（2014－01－16）［2014－01－30］http：／／pems.dot.ca.gov／，2014.