余沁瀟 凌 帥 吳 剛,2 馬壽峰▲
(1.天津大學(xué)管理與經(jīng)濟學(xué)部 天津 300072;2.天津高速公路集團(tuán)有限公司 天津 300384)
隨著智能交通系統(tǒng)的發(fā)展,交通管理模式逐漸由被動轉(zhuǎn)為主動,短時交通流預(yù)測作為智能交通系統(tǒng)的核心技術(shù)之一,為交通信息服務(wù)、交通控制與誘導(dǎo)提供基礎(chǔ)數(shù)據(jù),對預(yù)測效率和精度都要求較高。短時交通流預(yù)測的研究方法可分為2類:傳統(tǒng)的基于數(shù)學(xué)模型的方法;數(shù)據(jù)驅(qū)動式的計算智能方法[1]。近年來,面對復(fù)雜的路況以及大量的交通數(shù)據(jù)集,第1類方法存在明顯不足,學(xué)者們逐漸將研究重點轉(zhuǎn)向后者[2-5]。非參數(shù)回歸預(yù)測就是1種基于數(shù)據(jù)驅(qū)動式的計算智能方法,它實際上是基于模式匹配和數(shù)據(jù)挖掘的方法,其優(yōu)點在于它完全是數(shù)據(jù)驅(qū)動的,幾乎不需要先驗知識,只需要有足夠規(guī)模的模式庫,就可以做到比較準(zhǔn)確的預(yù)測。
近年來,許多學(xué)者將非參數(shù)回歸方法應(yīng)用于交通流預(yù)測,但在實際應(yīng)用中存在預(yù)測時間長,實時性差的缺陷。1991 年,Davis和Nihan[6]首次將非參數(shù)回歸的方法應(yīng)用于交通預(yù)測中,指出該方法適用于預(yù)測非線性的交通數(shù)據(jù),但該算法需要維護(hù)1個龐大且具有代表性的歷史數(shù)據(jù)庫,因此運行所耗費的時間相對較長。Smith等[7]將非參數(shù)回歸模型應(yīng)用于單點短時交通流預(yù)測,但在實際使用上仍存在搜索速度過慢的問題。后來,許多學(xué)者就這一問題提出解決方案,Oswald等[8]用KD 樹來建立歷史模式庫進(jìn)行模糊最近鄰搜索,縮短了K 近鄰算法的運行時間。張曉利等[9]針對非參數(shù)回歸中案例庫生成難和搜索速度慢的問題,提出1種基于平衡二叉樹的K-鄰域非參數(shù)回歸預(yù)測方法,該算法首先對歷史數(shù)據(jù)進(jìn)行聚類,然后采用平衡二叉樹建立歷史數(shù)據(jù)庫,預(yù)測速度有一定提高。賈寧等[10]用KD 樹作為模式庫的存儲結(jié)構(gòu),并基于KD 樹進(jìn)行最近鄰搜索,有效地提高了近鄰搜索速度。但KD 樹的形態(tài)高度依賴于數(shù)據(jù)的插入順序,不合理的插入順序會影響KD 樹的結(jié)構(gòu),從而影響查詢效率。另外,數(shù)據(jù)的刪除會導(dǎo)致KD 樹結(jié)點的重新組織,而現(xiàn)實中預(yù)測系統(tǒng)不斷增加新數(shù)據(jù),剔除舊數(shù)據(jù),這使得模式庫的更新耗費大量時間[11]。
綜上所述,非參數(shù)回歸方法可以解決交通流預(yù)測中的非線性和不確定性問題,使預(yù)測精度達(dá)到滿意的效果。但該方法要求大量的歷史數(shù)據(jù)來構(gòu)建歷史模式庫,當(dāng)數(shù)據(jù)量和狀態(tài)向量維數(shù)增長時,預(yù)測的速度將下降,從而影響預(yù)測的實時性。隨著大數(shù)據(jù)時代的到來,交通流數(shù)據(jù)不斷增長,同時為了準(zhǔn)確預(yù)測交通流量,考慮的影響因素也越來越多,如檢測點歷史流量、速度、占有率,上下游的流量、速度、占有率,信號燈情況,天氣因素,地理位置等。這些問題使得非參回歸方法中歷史模式數(shù)據(jù)庫建立和模式搜索的速度受到挑戰(zhàn),而傳統(tǒng)的線性數(shù)據(jù)庫已經(jīng)不能滿足預(yù)測的實時性要求。因此,筆者提出了1種基于R 樹的K 近鄰非參數(shù)回歸短時交通流預(yù)測方法,該方法使用R 樹來建立模式庫,根據(jù)數(shù)據(jù)在空間中的分布進(jìn)行存儲,使相近數(shù)據(jù)存儲在同1個或相鄰的節(jié)點中,這便使得K 近鄰搜索的速度得以提高,從而提高預(yù)測的實時性。
非參數(shù)回歸是1種數(shù)據(jù)驅(qū)動的預(yù)測技術(shù),是1種適合于不確定性和非線性性動態(tài)系統(tǒng)的非參數(shù)估計方法。將其用到交通流預(yù)測中的主要過程就是在數(shù)據(jù)庫中尋找與當(dāng)前交通模式相近的歷史模式,再用這些歷史模式去預(yù)測當(dāng)前交通流量。在數(shù)據(jù)庫中,1條交通流模式由2部分組成,一部分為斷面交通流的狀態(tài)向量,即影響該斷面交通流量的因素f1~fn,如該斷面以及上下游的歷史交通流特征(流量、速度、占有率)、天氣、地理位置等;另一部分則為斷面的交通流量q,它由狀態(tài)向量所決定。因此,1 條交通流模式可表示為{f1(ti),…,fn(ti)|q(ti)}。隨著交通系統(tǒng)的運行,交通流模式將不斷被加入到歷史模式數(shù)據(jù)庫中。
R 樹[12]最初由Guttman于1984年提出,作為1種空間索引機制,它將空間對象按范圍劃分,每個結(jié)點對應(yīng)1個空間區(qū)域,在物理存儲上,每個結(jié)點對應(yīng)1個磁盤頁。相應(yīng)于交通流數(shù)據(jù),由于它的狀態(tài)向量往往都是多維的,因此1條交通流模式可被看作是多維空間中的1個點,那些狀態(tài)向量相似的模式在多維空間中是相鄰的,它們將被劃分到同1個字空間存入同1個磁盤頁。因此在進(jìn)行數(shù)據(jù)檢索時,可根據(jù)數(shù)據(jù)的空間位置快速有效地在多維空間中找到1組相似的數(shù)據(jù)。R 樹中的結(jié)點分為2種:葉結(jié)點和非葉結(jié)點,葉結(jié)點存儲的是其區(qū)域范圍內(nèi)所有空間對象的最小邊界矩形(minimum bounding rectangle,MBR),非葉結(jié)點存儲的是包絡(luò)其所有子結(jié)點所在空間范圍的MBR。該設(shè)計使得對空間對象進(jìn)行搜索時只需訪問小部分結(jié)點,并且可以方便快速地進(jìn)行空間對象的插入和刪除操作,無需對樹中所有數(shù)據(jù)進(jìn)行空間上的再組織。
R 樹空間數(shù)據(jù)存儲方法是把多維空間進(jìn)行遞歸劃分,最終將空間對象劃分到不同的子空間中。每個子空間都由1個結(jié)點表示,而每個結(jié)點有惟一的記錄形式。葉結(jié)點的記錄形式為:(M,i)。其中:M為包絡(luò)了該結(jié)點中所有空間對象的MBR;i為該結(jié)點的標(biāo)識即其物理存儲地址。非葉結(jié)點的記錄形式為:(M,p)。其中:M為包絡(luò)了其所有子結(jié)點所在區(qū)域的MBR;p為指向其子結(jié)點存儲位置的指針。對于n維空間中的1 個MBR,M可表示為M=(I0,I1,…,In-1),其中:Ii指空間對象在第i維上的取值范圍[a,b],它在數(shù)值上等于該空間中所有數(shù)據(jù)第i維的最小值和最大值。
R 樹的構(gòu)造方法就是將數(shù)據(jù)點逐個插入到R樹中,在插入過程中,尋找最優(yōu)的路徑,使相近數(shù)據(jù)聚集在同1 個結(jié)點中,保證R 樹的結(jié)構(gòu)穩(wěn)定。下面給出R 樹構(gòu)造的偽代碼,設(shè)R 為R 樹的根結(jié)點,E為要存入到R 樹中的數(shù)據(jù)。
歷史模式數(shù)據(jù)庫中交通流模式的狀態(tài)向量是多維的,而且模式數(shù)量眾多,R 樹組織結(jié)構(gòu)的特點就是將空間中相鄰的對象劃分在1個區(qū)域內(nèi),使它們擁有共同的祖先,待測對象與其他對象間的距離可以通過它們的祖先與待測對象的距離表示。使用R 樹進(jìn)行近鄰搜索,可通過祖先與待測對象的距離剔除大部分距離遠(yuǎn)的分支,這樣便可提高查找效率。
R 樹中結(jié)點存儲的是其若干子結(jié)點或空間對象的MBR,MBR 為包絡(luò)對象所在空間的最小邊界矩形,通常用其主對角線上的2個頂點表示,例如,在二維空間里,用(xl,xh,yl,yh)表示。在本文中,用minDist表示點p到空間內(nèi)某矩形R的最小距離,若點p在矩形R內(nèi),則兩者距離為零;若點p在矩形R外,則兩者的距離為p到矩形R上最近1點的歐式距離平方值。則minDist(p,R)表示為[13]
式中:pi為n維待測點p第i維的值,i=1,2,…,n;ri為n維空間矩形R在第i維與待測點p距離較近的值,i=1,2,…,n;si為n維空間矩形R在第i維上的最小值。ti為n維空間矩形R在第i維上的最大值。
可以證明,點p到MBR的minDist小于等于點p到該MBR中任意對象O的距離[14]。因此minDist值可以看作待測點p到每1個MBR中對象的距離下限,在查找過程中可以按照minDist值從小到大排列,確定MBR的搜索順序,從而減少需要訪問結(jié)點的數(shù)量。但因為MBR內(nèi)對象分布不均勻,待測點到MBR中對象的距離比minDist確定的距離遠(yuǎn),如果先訪問minDist值小的MBR,并將其中的對象都作為近鄰點,那么將損失更優(yōu)的對象,從而影響了預(yù)測精度。如圖1 所 示,minDist(p,MBR1)<minDist(p,MBR2),但MBR2中的對象多集中于靠近點p一側(cè),而MBR1中的對象多集中于遠(yuǎn)離點p的一側(cè)。因此,點p到MBR2中對象的距離比到MBR1中對象的距離小,若將MBR1中的對象均視為p的近鄰,則會影響預(yù)測精度。為解決該問題,引入?yún)?shù)距離上限r(nóng),它表示近鄰點與待測點之間的距離上限,若MBR中的對象到p的距離小于r,則將其視為近鄰點。因此,即使某個MBR到待測點p的minDist較小,若其中的對象到p的距離都大于r,舍棄該MBR,繼續(xù)搜索其它的MBR,直到搜索到K個近鄰或者遍歷完整棵樹。
圖1 minDist示意圖Fig.1 minDist
因此筆者采用的K 近鄰搜索策略是:首先設(shè)定1個距離上限r(nóng),對于MBR中的任意對象O,當(dāng)Dist(p,O)≤r時,將其視為p的近鄰;然后對R 樹進(jìn)行有序深度優(yōu)先遍歷,從根結(jié)點開始向下逐層訪問MBR,對于同層的結(jié)點,計算所有MBR到待測點p的minDist,然后將結(jié)點按minDist由小到大排序后放入鏈表ABL中;之后選擇minDist最小的結(jié)點遞歸進(jìn)行以上過程,直至到達(dá)葉結(jié)點,在葉結(jié)點中選擇距離小于r的對象放入近鄰集合中;若近鄰個數(shù)等于K或遍歷完整棵樹,則搜索完成,否則,返回鏈表中ABL搜索下一個結(jié)點。
設(shè)R 樹的根節(jié)點為R,待測點為p,搜索的距離上限為r,近鄰個數(shù)為K,近鄰點存于Nearest列表中。則該搜索策略的偽代碼如下:
預(yù)測算法是影響預(yù)測精度的重要因素,它是根據(jù)K 近鄰查找得到的近鄰點,利用預(yù)測函數(shù)做出合理的預(yù)測。
筆者采用帶權(quán)重的預(yù)測方法,設(shè)搜索到的K個近鄰點為n1,n2,…,nk,對應(yīng)的決策屬性為y1(t+1),…,yk(t+1),待測點與第i個近鄰點的距離為di(i=1,2,…,k),距離越小的點在預(yù)測中所占的權(quán)重越大,則預(yù)測算法如下。
首先針對2 種結(jié)構(gòu)下的歷史模式庫進(jìn)行K近鄰搜索速度的比較實驗。在實驗中,每個數(shù)據(jù)對象由10維狀態(tài)向量表示,狀態(tài)向量中的各分量是隨機生成的0~1 之間的實數(shù),距離上限r(nóng)為1,近鄰個數(shù)K=20。對不同規(guī)模的模式庫進(jìn)行查找實驗。實驗程序使用Java語言編寫,硬件環(huán)境為2.4GCPU,4G 內(nèi)存,實驗結(jié)果見圖2。
圖2 R 樹結(jié)構(gòu)與線性結(jié)構(gòu)的搜索速度對比Fig.2 The comparison of searching performances under the R-tree and linear structure
由圖2可見,隨著數(shù)據(jù)規(guī)模的增大,線性結(jié)構(gòu)的查找耗時增長快,而R 樹結(jié)構(gòu)查找速度比較穩(wěn)定,在耗時上沒有明顯的增長。這是因為在線性結(jié)構(gòu)的數(shù)據(jù)庫中進(jìn)行K 近鄰查找時,需要遍歷整個數(shù)據(jù)庫,進(jìn)行1次最近鄰搜索的時間復(fù)雜度是O(kN),k是數(shù)據(jù)對象的維數(shù),N是數(shù)據(jù)庫規(guī)模,因此查找時間與數(shù)據(jù)庫規(guī)模N成正比。R 樹的查找速度與其遍歷的節(jié)點數(shù)目以及每個節(jié)點中數(shù)據(jù)對象的數(shù)量成正比,而其遍歷的節(jié)點數(shù)目與R樹的高度有關(guān),R 樹的高度可表示為,因此R 樹最近鄰查找的時間復(fù)雜度可表示為O(k·,式中:k為數(shù)據(jù)對象的維數(shù);N為數(shù)據(jù)庫規(guī)模;m為節(jié)點容量下限。因此使用R 樹進(jìn)行K 近鄰查找的速度明顯優(yōu)于線性結(jié)構(gòu)。
2.2.1 數(shù)據(jù)來源
實驗采用的交通數(shù)據(jù)來自加利福尼亞州交通局的路況監(jiān)測系統(tǒng)[15](caltrans performance measurement system),這些數(shù)據(jù)采集自圣地亞哥市I5號公路由北向南24.4km(15.2 mile)處的檢測器,包含了2013年1月1日~2014年1 月15日的流量數(shù)據(jù),其中每5min記錄1條交通流量,1d共288個樣本。實驗中將所有樣本的交通流量進(jìn)行歸一化處理,以2013年全年105 120條數(shù)據(jù)作為歷史模式來建立數(shù)據(jù)庫,2014 年的4 320條數(shù)據(jù)作為測試數(shù)據(jù)來進(jìn)行流量預(yù)測,預(yù)測周期為5 min。在預(yù)測中,僅考慮交通流量之間的時間關(guān)聯(lián),用前10個時刻的流量來預(yù)測本時刻的流量。
2.2.2 近鄰個數(shù)和距離上限的確定
在本文涉及的K 近鄰搜索策略中,對最后預(yù)測精度及速度起到影響作用的參數(shù)有2 個,1 個是近鄰個數(shù)K,另1個是距離上限r(nóng)。對于近鄰個數(shù)K而言,過大或過小都會影響非參數(shù)回歸預(yù)測結(jié)果,如果K過大,那么需要搜索較多的結(jié)點,增加搜索耗時。如果K過小,則會降低預(yù)測精度。通過對比實驗檢驗K值與預(yù)測誤差的關(guān)系,其他參數(shù)固定,K分別取不同的值進(jìn)行預(yù)測,預(yù)測效果見圖3,當(dāng)K值為20時,預(yù)測結(jié)果的平均相對誤差最小,因此實驗中K值取20。
圖3 近鄰個數(shù)K 與平均相對誤差關(guān)系Fig.3 The relationship between the number of neighbors and average relative error
對于距離上限r(nóng)來說,如果r過大將起不到約束minDist的作用,雖然在進(jìn)行K 近鄰查找時,能較快找到K個近鄰,但這些近鄰與待測點的距離卻相對較遠(yuǎn),即這些點并不是待測點的最優(yōu)匹配點,在未訪問的結(jié)點中可能存在與待測點更加匹配的數(shù)據(jù)。這樣雖然達(dá)到一定的預(yù)測效率,卻在預(yù)測精度上略有不足。如果r過小,即對待測點的近鄰要求更嚴(yán)格,這樣在近鄰查找過程中將訪問更多的結(jié)點來查找最優(yōu)近鄰,雖然提高預(yù)測精度,但是卻以犧牲預(yù)測效率為代價。圖4是不同r值與耗時的關(guān)系圖,在實驗中,從0 開始,每隔0.01 取1 個r值,直到r為1。每 個r值,進(jìn)行20次K 近鄰查找,其中K=20,再計算平均耗時,結(jié)果如圖4所示,當(dāng)距離上限r(nóng)從0增到0.05時,耗時顯著減小,當(dāng)距離上限r(nóng)繼續(xù)增大時,耗時漸趨平穩(wěn)。
圖4 r值與耗時的關(guān)系Fig.4 The relationship between r and time-consuming
2.2.3 預(yù)測結(jié)果
非參數(shù)回歸是通過歷史數(shù)據(jù)對未來數(shù)據(jù)的模擬,方法自身具有一定誤差。線性結(jié)構(gòu)下的非參數(shù)回歸下的K近鄰搜索,在遍歷完所有的模式的前提下,找出K個近鄰點,所得近鄰點是距離待測點的最近的前K個,因此,它的誤差可以看作是非參數(shù)回歸方法自身的誤差。表1為線性結(jié)構(gòu)下,近鄰個數(shù)為20時的預(yù)測結(jié)果。
表1 線性結(jié)構(gòu)下的預(yù)測誤差及耗時Tab.1 Average relative error and time-consuming based on linear structure
R 樹結(jié)構(gòu)下的非參數(shù)回歸,除了非參數(shù)回歸自身的誤差之外,還應(yīng)考慮R 樹下K近鄰查找的誤差,該方法查找出來的K個近鄰點,并不是離待測點最近的K個近鄰,因此預(yù)測誤差較大。但是在該方法中,誤差的大小在一定程度上可以通過距離上限r(nóng)調(diào)節(jié)。如表2所示,隨著距離上限r(nóng)減小,預(yù)測耗時不斷增加,但都低于線性結(jié)構(gòu)下的預(yù)測耗時,而平均相對誤差不斷減小,接近甚至優(yōu)于線性結(jié)構(gòu)下的預(yù)測誤差。這是因為R 樹的K近鄰查找算法中共有2個參數(shù)來約束近鄰點,當(dāng)r值較大時,它對近鄰點的約束條件放寬,更多的鄰居點被當(dāng)作近鄰點,此時近鄰個數(shù)K起到約束作用,即從多于K個的近鄰點中選出前K個與待測點最相似的近鄰點;當(dāng)r值較小時,越來越少的鄰居點符合近鄰點的要求,此時存在少數(shù)待測點的近鄰個數(shù)少于K,但這些近鄰點與待測點的相似度更高,因此誤差相對減小。
在表2中,當(dāng)距離上限大于等于0.02 時,R樹搜索到的平均近鄰個數(shù)為20個,此時線性結(jié)構(gòu)下搜索到的20個近鄰相對更精確,因此線性結(jié)構(gòu)下的預(yù)測誤差總是小于R 樹結(jié)構(gòu)下的預(yù)測誤差.但是在預(yù)測速度上,R 樹結(jié)構(gòu)下的搜索耗時遠(yuǎn)小于表1中線性結(jié)構(gòu)下的搜索耗時。當(dāng)距離上限為0.02時,R 樹結(jié)構(gòu)下的預(yù)測誤差比線性結(jié)構(gòu)的預(yù)測誤差上升了8.8%,但預(yù)測速度提高了59.6%。當(dāng)距離上限小于0.02時,R 樹搜索到的平均近鄰個數(shù)都小于20,與平均近鄰個數(shù)為20的線性結(jié)構(gòu)預(yù)測結(jié)果缺乏可比性,因此,為線性結(jié)構(gòu)下的K近鄰查找算法添加距離上限這一相同約束,其預(yù)測結(jié)果如表3所示,與表1結(jié)果比較,平均相對誤差增大,這是因為對于大多數(shù)待測點來說,模式庫中存在多余20個的近鄰點,在考慮距離上限這一約束后,只要滿足約束條件即可視為近鄰點,無需遍歷完所有模式,從而這些近鄰點與待測點的相似度變小,因此預(yù)測誤差增大,預(yù)測耗時減小。由表2與表3的對比結(jié)果顯示,2種結(jié)構(gòu)下搜索到的近鄰個數(shù)相等且都小于20,在同一水平的距離上限下,R 樹憑借自身的空間聚類特征,可以更快且更準(zhǔn)確地找到滿足條件的近鄰,因此,R 樹結(jié)構(gòu)下的預(yù)測精度和速度都優(yōu)于線性結(jié)構(gòu)下的預(yù)測結(jié)果。
表2 R 樹結(jié)構(gòu)下不同距離上限r(nóng)的預(yù)測結(jié)果Tab.2 The predicting result under different distance limits r based on R-tree
表3 線性結(jié)構(gòu)下不同距離上限r(nóng)的預(yù)測誤差及耗時Tab.3 The predicting result under different distance limits r based on linear structure
交通流影響因素眾多、交通數(shù)據(jù)海量增長,這2個因素分別導(dǎo)致非參數(shù)回歸中的狀態(tài)向量維數(shù)增長、歷史模式庫規(guī)模擴大,最終影響非參數(shù)回歸的預(yù)測速度,尤其在短時交通流預(yù)測中,不能滿足預(yù)測實時性的要求。因此,筆者提出1種基于R樹索引結(jié)構(gòu)的非參數(shù)回歸短時交通流預(yù)測方法,使用R 樹建立空間高維模式庫,并依據(jù)R 樹的空間聚類特點使用K 近鄰搜索算法。實驗結(jié)果顯示這一方法在預(yù)測精度達(dá)到要求的前提下,能夠大幅度地提高預(yù)測速度,即使模式庫規(guī)模不斷擴大,預(yù)測耗時的增長是緩慢穩(wěn)定的,這為實現(xiàn)大規(guī)模路網(wǎng)下的交通誘導(dǎo)和控制提供了1種方法。
[1]賀國光,李 宇,馬壽峰.基于數(shù)學(xué)模型的短時交通流預(yù)測方法探討[J].系統(tǒng)工程理論與實踐,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ù)回歸短時交通流預(yù)測方法[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]徐華文,魏志強.基于數(shù)據(jù)流集成回歸的短時交通流預(yù)測[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]張曉利,賀國光,陸化普.基于K-鄰域非參數(shù)回歸短時交通流預(yù)測方法[J].系統(tǒng)工程學(xué)報,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ù)回歸預(yù)測方法[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.