基于改進KNN算法的城軌進站客流實時預(yù)測

郇 寧，謝 俏，葉紅霞，姚恩建*

(1.北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京100044；2.廣州地鐵集團有限公司，廣州510030)

0 引言

隨著城市軌道交通網(wǎng)絡(luò)化運營規(guī)模不斷擴大，準(zhǔn)確地掌握客流分布狀況成為提高客運組織水平的重要前提.高精度、小粒度的實時進站量預(yù)測能夠幫助管理者及時掌握網(wǎng)絡(luò)客流演化態(tài)勢，為客運組織提供重要的決策依據(jù).

針對客流預(yù)測問題，國內(nèi)外學(xué)者對短期和中長期的需求預(yù)測關(guān)注較多.蔡昌俊[1]通過構(gòu)建乘積ARIMA模型，消除趨勢性特征影響，推演客流長期變化規(guī)律.姚恩建等[2]考慮車站可達性指標(biāo)，建立新線接入后既有站的進出站量預(yù)測模型.光志瑞[3]針對節(jié)假日客流中動態(tài)特征的非線性序列，分析了制約預(yù)測精度的關(guān)鍵因素.徐瑞華等[4]提出了站臺—列車客流交互模型，為斷面客流等精細(xì)化指標(biāo)預(yù)測提供了理論基礎(chǔ).包磊[5]通過灰色模型和馬爾科夫鏈預(yù)測線路客運量等宏觀指標(biāo).此類研究普遍針對客流周期性變化，旨在為運力配置提供測算依據(jù)，而對實時運算邏輯和效率約束等因素關(guān)注較少，難以適應(yīng)動態(tài)增量的數(shù)據(jù)環(huán)境.

近年來，非參數(shù)回歸模型憑借其靈活性和強大的數(shù)據(jù)處理能力，在實時預(yù)測領(lǐng)域應(yīng)用廣泛.Davis G.A.[6]于1991年將非參數(shù)回歸模型應(yīng)用到交通流量預(yù)測中，并系統(tǒng)地梳理了相關(guān)基礎(chǔ)理論.宮曉燕等[7]針對基于動態(tài)聚類和散列函數(shù)的數(shù)據(jù)組織方式，提出了基于密集度的變K搜索算法.張濤等[8]分析了K最近鄰(K-nearest-neighbor,KNN)算法中狀態(tài)向量等關(guān)鍵因素對精度的影響.謝俏等[9]將KNN算法應(yīng)用于城軌車站的進出站量實時預(yù)測問題，考慮了客流的時間關(guān)聯(lián)性，取得良好的預(yù)測效果.目前，同類研究所提出的模型普遍針對15 min或1 h粒度的客流數(shù)據(jù)，由于采樣時間跨度較大，樣本的數(shù)值型特征相對明顯，因而對實時數(shù)據(jù)中噪聲擾動等因素考慮不足，其預(yù)測機制也往往難以適用于現(xiàn)實環(huán)境.此外，在傳統(tǒng)KNN算法的模式匹配過程中，普遍采用基于歐式距離的“點對點”度量方法，當(dāng)序列中波峰、波谷在時間軸上產(chǎn)生偏移時，造成誤差顯著升高.本文以5 min粒度的實時進站量數(shù)據(jù)為研究對象，結(jié)合序列降維擬合技術(shù)和動態(tài)時間規(guī)整算法，改進傳統(tǒng)KNN算法的模式匹配環(huán)節(jié)，在規(guī)避噪聲擾動的同時，實現(xiàn)考慮序列形態(tài)的樣本匹配；在回歸預(yù)測階段，引入距離權(quán)重和趨勢系數(shù)以順應(yīng)客流的自然增長規(guī)律；最后，通過精度分析論證了方法的可行性與有效性.

1 城軌進站客流變化規(guī)律分析

深入分析客流變化規(guī)律是客流預(yù)測的重要前提.其一，進站客流規(guī)律受周邊土地性質(zhì)等環(huán)境因素影響明顯，以廣州地鐵線網(wǎng)中區(qū)域跨度較大的3號線為例，隨機選擇某日的分時進站量進行橫向?qū)Ρ龋鐖D1所示.由圖1可知，5 min粒度下的進站量波動較強，并且站點的客流規(guī)模與峰值分布存在差異.因此，考慮以車站為基本單元組建歷史樣本庫.在數(shù)據(jù)條件不足的情況下，可結(jié)合聚類等手段，選擇與本站客流規(guī)律相近的同類站點擴充樣本.其二，客流規(guī)律受雙休日、節(jié)假日安排等因素影響明顯，以位于中心商務(wù)區(qū)的珠江新城站為例，對不同日期進行縱向?qū)Ρ?，如圖2所示.

圖1 廣州地鐵3號線站點分時進站量對比圖Fig.1 Entrance passenger flow of stations in Guangzhou Metro Line 3

圖2 珠江新城站分時進站量變化圖Fig.2 Entrance passenger flow of Zhujiang New Town station among certain days

可見，珠江新城站基本不存在早高峰，但具有傍晚通勤和晚間出行帶來的雙高峰特征.圖2中：(a)、(d)、(e)、(f)分別對應(yīng)不同星期數(shù)的工作日，客流規(guī)律較為相近；(b)、(c)為雙休日，傍晚通勤高峰明顯弱于工作日；(g)雖為周六，但受端午節(jié)調(diào)休影響，規(guī)律與工作日一致；(h)、(i)為端午假期，晨間客流進一步衰減，存在晚間高峰強于傍晚高峰的特殊現(xiàn)象.基于此，將預(yù)測場景初步劃分為工作日、雙休日、節(jié)假日3類.

2 城軌進站客流實時預(yù)測模型

結(jié)合進站客流數(shù)據(jù)特性，構(gòu)建基于改進KNN算法的實時預(yù)測模型.首先，確定狀態(tài)向量選取規(guī)則以合理描述樣本特征；其次，為解決“點對點”歐氏距離匹配適用性差的問題，提出改進的模式匹配方法，實現(xiàn)考慮序列形態(tài)的精準(zhǔn)匹配；最后，根據(jù)近鄰樣本與預(yù)測目標(biāo)的差異引入距離權(quán)重和趨勢系數(shù)，給出一般化的預(yù)測算法.

2.1 狀態(tài)向量選取

考慮到進站客流具有較強的時間關(guān)聯(lián)性，故選擇與當(dāng)前鄰近的m個時段的進站量構(gòu)成狀態(tài)向量，用于描述樣本特征.通過計算歷史分時進站量的自相關(guān)系數(shù)推算m值，公式為[9]

以2016—2017年全網(wǎng)的分時進站量數(shù)據(jù)為對象，將每日每站216條(6:00-24:00)分時進站量視為1個序列樣本.根據(jù)式(1)和式(2)計算自相關(guān)系數(shù).當(dāng)≥0.5時，通常認(rèn)為序列中相鄰的q個時段相關(guān)性顯著[9].統(tǒng)計符合該條件的樣本比例，結(jié)果如表1所示.

表1 廣州地鐵分時進站客流自相關(guān)性統(tǒng)計表Table 1 Self correlation feature of entrance passenger flow in Guangzhou metro(%)

表1結(jié)果顯示，5 min粒度下的進站客流時間關(guān)聯(lián)性明顯.綜合考慮樣本分布及實際預(yù)測的精度表現(xiàn)，確定若樣本總量的85%以上滿足≥0.5，則認(rèn)為鄰近的前q個時段具有較強相關(guān)性，進而確定工作日、雙休日、節(jié)假日對應(yīng)的m值為9、8、7，并以此作為狀態(tài)向量選取依據(jù).

2.2 基于關(guān)鍵點的序列表示方法

考慮到進站量序列中離群點較多且波動頻繁，若直接進行處理不僅會降低實時運算效率，而且影響預(yù)測效果.所以，在模式匹配之前，采用關(guān)鍵點法(Key Point Segmentation,KPS)對序列進行降維擬合處理，尋找關(guān)鍵極值點(Key Extreme Point,KEP)和關(guān)鍵轉(zhuǎn)折點(Key Turning Point,KTP)對序列進行抽象化表示.首先，設(shè)置極值保持時段閾值K0，篩選KEP以去除序列中的過多細(xì)節(jié)；其次，利用夾角法描述序列轉(zhuǎn)折趨勢，通過轉(zhuǎn)折角度閾值θ0篩選KTP，如圖3所示.

對于圖3中的子序列(xi-1,xi,xi+1)，通過計算轉(zhuǎn)折角的余弦值量化轉(zhuǎn)折程度，公式為[10]

圖3 KTP選取指標(biāo)計算示意圖Fig.3 Illustration of parameter calculation for KTP selection

定義序列壓縮比C和擬合優(yōu)度R2評價降噪擬合算法的有效性.壓縮比用于描述對序列的剪裁能力，低壓縮比意味著低的計算成本，但過低亦會造成信息損失；擬合優(yōu)度用于描述對序列的還原程度，值越接近1，表示擬合效果越好.公式為

式中：N0為原始序列的維數(shù)；NKP為關(guān)鍵點集的元素數(shù)；yi和分別為序列點的原始值和擬合值；為原始序列的均值.

隨機選取部分日期進行測試，指標(biāo)如圖4所示.確定參數(shù)K0取2，θ0取90°時，能夠在獲得較高擬合優(yōu)度時，取得良好的壓縮比.

2.3 基于動態(tài)時間規(guī)整的相似性度量方法

模式匹配是KNN算法的核心步驟，指尋找特征空間中K個最鄰近樣本的過程.對于時間序列這一研究對象，通常采用序列間相似性度量實現(xiàn).針對序列樣本在時間軸上的偏移、扭曲等現(xiàn)象，采用動態(tài)時間規(guī)整(Dynamic Time Warping,DTW)算法對非等長序列進行相似性度量，適當(dāng)擴張或壓縮局部特征，進而得到更好的形態(tài)度量效果，如圖5所示.

圖4 KPS序列表示方法指標(biāo)統(tǒng)計圖Fig.4 Evaluation index for KPS algorithm

圖5 DTW相似性度量示意圖Fig.5 Diagram of similarity measurement with DTW algorithm

對于序列A=(a1,…,ai,…,am)和B=(b1,…,bj,…,bn)，構(gòu)建m×n的距離矩陣Dm×n，DTW的目的在于尋找一條通過若干格點的路徑P=(p1,…,pk,…,pK)，使得其全局代價最小，即令累積距離C滿足條件

式中：pk為該路徑元素在矩陣中的位置，即表示ai和bj間的匹配關(guān)系.

一般而言，序列間存在多條路徑，但有效路徑P應(yīng)滿足邊界性、連續(xù)性和單調(diào)性約束[11].采用動態(tài)規(guī)劃方法構(gòu)造一個代價矩陣γm×n，即序列間DTW距離，公式為

式中：D(i,j)為ai和bj間的距離，3種匹配方式如圖6所示.

圖6 子序列匹配方式示意圖Fig.6 Illustration of matching patterns for subsequences

2.4 預(yù)測算法

以每個預(yù)測節(jié)點可獲取的最新時段進站量為對象，通過調(diào)整K值對該時段進行迭代預(yù)測，取預(yù)測誤差最小的K值作為應(yīng)用值.同時，為順應(yīng)客流的自然增長規(guī)律，引入距離權(quán)重與趨勢系數(shù)以修正預(yù)測結(jié)果.若匹配所得近鄰日期為{z1,z2,…,zk}，預(yù)測值的計算公式為

3 精度分析

依托廣州地鐵客流數(shù)據(jù)倉庫對預(yù)測模型進行精度分析，以站點的全天分時平均絕對百分比誤差ET和累積全天平均絕對百分比誤差ED為評價指標(biāo)，公式為

首先，測試模型于不同時間粒度下的預(yù)測效果，結(jié)果如表2所示.

表2 不同時間粒度下的預(yù)測誤差Table 2 Forecast error under different granularities(%)

與本文預(yù)測模式較為相近的文獻[9]中，15 min粒度下全網(wǎng)平均ET為12.4%，證明本文提出的方法具有更強的時效性與準(zhǔn)確性.在后續(xù)分析中，默認(rèn)采用5 min時間粒度.

其次，對比KNN算法改進前后預(yù)測效果.具體分為以下4類：方法(i)為“逐點歐式距離匹配+近鄰距離加權(quán)”的傳統(tǒng)模式，方法(ii)為“KPS-DTW+近鄰距離加權(quán)”的模式，方法(iii)為“逐點歐式距離匹配+近鄰距離加權(quán)-趨勢系數(shù)”的模式，方法(iv)為“KPS-DTW+近鄰距離加權(quán)-趨勢系數(shù)”的改進模式.結(jié)果如表3所示.

表3 不同方法下的預(yù)測誤差Table 3 Forecast error with different algorithms(%)

由表3可知，匹配模式的改進對預(yù)測精度有較大提升，趨勢系數(shù)的引入也具有良好的效果.然后，從線路層面進行分析，結(jié)果如表4所示.

表4 不同線路的預(yù)測誤差Table 4 Forecast error of each line

由表4可知，客流量較大的站點往往預(yù)測精度更優(yōu).以7號線的謝村站為例，每日約90個時段的進站量小于5人次，致使該站誤差較高，但在應(yīng)用中可忽略此類影響.

此外，以客流規(guī)律不同的4個典型車站為例，隨機選擇某日的完整預(yù)測結(jié)果進行展示，如圖7～圖10所示.

圖7 珠江新城站預(yù)測樣本圖Fig.7 Forecasting sample of Zhujiang New Town station

圖8 東曉南站預(yù)測樣本圖Fig.8 Forecasting sample of Dongxiaonan station

可以看出，該方法在不同類型車站的預(yù)測中均表現(xiàn)出良好的效果，基本不存在局部偏離現(xiàn)象.

最后，探究模型在不同數(shù)據(jù)條件下的適用性問題.依據(jù)2017年長期的實時預(yù)測記錄，對不同時期歷史數(shù)據(jù)在預(yù)測中發(fā)揮的實際效用進行分析，統(tǒng)計其被成功匹配為近鄰的頻率，結(jié)果如圖11所示.

圖9 楊箕站預(yù)測樣本圖Fig.9 Forecasting sample of Yangji station

圖10 長壽路站預(yù)測樣本圖Fig.10 Forecasting sample of Changshou Road station

圖11 歷史樣本選取頻率分布直方圖Fig.11 Frequency distribution histogram of sample selection

從圖11可知，實際被匹配的樣本中，九成以上處于預(yù)測日期前一年內(nèi).因此，為保證預(yù)測準(zhǔn)確性，歷史數(shù)據(jù)庫應(yīng)盡量覆蓋近一年的客流數(shù)據(jù).對于節(jié)假日等特殊場景，則需結(jié)合實際情況提供更長時限的同類場景歷史樣本.

4 結(jié) 論

針對小粒度客流數(shù)據(jù)的高維數(shù)、多噪聲等特征，本文提出一種基于改進KNN算法的實時進站客流預(yù)測方法.其一，通過KPS序列表示法實現(xiàn)序列的降維表示，當(dāng)擬合優(yōu)度達0.8時，平均壓縮比為62.4%，可在充分保留特征的同時規(guī)避細(xì)節(jié)擾動；其二，采用DTW算法解決不同維數(shù)序列間的相似性度量問題，可容忍小粒度客流數(shù)據(jù)中的偏移、拉伸現(xiàn)象，優(yōu)化匹配邏輯；其三，在真實的動態(tài)數(shù)據(jù)環(huán)境中開展精度檢測，5 min粒度下全網(wǎng)站點全天分時進站量預(yù)測的平均絕對百分比誤差的均值為11.6%，并給出了歷史樣本庫構(gòu)建的參考規(guī)則.綜上，該模型具有較好的可行性與有效性，能夠為路網(wǎng)狀態(tài)監(jiān)控提供可靠的數(shù)據(jù)支撐.