基于AP聚類的支持向量機公交站點短時客流預(yù)測*

楊信豐　劉蘭芬

(蘭州交通大學(xué)交通運輸學(xué)院　蘭州　730070)

?

基于AP聚類的支持向量機公交站點短時客流預(yù)測*

楊信豐劉蘭芬

(蘭州交通大學(xué)交通運輸學(xué)院蘭州730070)

摘要：公交站點短時客流預(yù)測是公交調(diào)度決策的基礎(chǔ)，文中設(shè)計了一種基于AP聚類算法的支持向量機用于公交短時客流預(yù)測.該方法利用AP聚類算法將客流調(diào)查數(shù)據(jù)劃分為若干個聚類子集，對每一子集建立支持向量機預(yù)測模型，并采用遺傳算法對預(yù)測模型的參數(shù)進行優(yōu)化選擇.該方法在蘭州市快速公交站點客流數(shù)據(jù)統(tǒng)計的基礎(chǔ)上進行實例分析，結(jié)果表明：設(shè)計的遺傳算法可以有效解決支持向量機模型中的參數(shù)優(yōu)選問題，使用AP聚類算法對客流數(shù)據(jù)進行分類可以提高支持向量機的預(yù)測精度，該預(yù)測方法可有效的對公交車站客流進行短時預(yù)測.

關(guān)鍵詞：公交；短時客流預(yù)測；支持向量機；AP聚類算法；遺傳算法

楊信豐(1978- )：男，博士，副教授，主要研究領(lǐng)域為運輸系統(tǒng)分析與決策.

*國家自然科學(xué)基金項目(批準號:61164003, 61364026)、教育部人文社會科學(xué)研究項目(批準號:13XJC630017)、甘肅省自然科學(xué)基金項目(批準號:1310RJZA032,148RJZA052)資助

0引言

公交是一種高效利用道路資源的交通方式.掌握客流變化規(guī)律、準確預(yù)測客流是公交企業(yè)科學(xué)制定運營計劃的基礎(chǔ)和關(guān)鍵[1].公交站點短時客流預(yù)測是智能公交調(diào)度系統(tǒng)中重要的決策基礎(chǔ)與技術(shù)支持[2].

短時客流的隨機性和時變性使得短時客流預(yù)測與中長期客流預(yù)測存在顯著差異.公交短時客流預(yù)測已受到國內(nèi)外學(xué)者的廣泛關(guān)注，其研究方法主要有人工神經(jīng)網(wǎng)絡(luò)[3-4]、小波理論[5-6]、卡爾曼濾波[7]及支持向量機(support vector machine, SVM)[8-11]等.其中，SVM是一種基于統(tǒng)計學(xué)習(xí)理論的機器學(xué)習(xí)算法，在短時預(yù)測領(lǐng)域有較好的應(yīng)用.影響SVM預(yù)測效果的因素主要有訓(xùn)練樣本及訓(xùn)練參數(shù).但不同時間公交短時客流的變化較大，很難直接采用原始訓(xùn)練樣本得到合適的SVM訓(xùn)練參數(shù).

針對上述問題，文中利用AP聚類算法對公交車站短時客流數(shù)據(jù)樣本集進行聚類分析，將客流數(shù)據(jù)分為若干個子樣本，針對每一子樣本，利用遺傳算法對SVM參數(shù)進行訓(xùn)練優(yōu)化，得到較優(yōu)的SVM預(yù)測模型，用于公交車站短時客流的預(yù)測，具體流程見圖1.

圖1　公交車站短時客流預(yù)測流程圖

1聚類分析

Frey等[12]提出了近鄰傳播聚類算法(affinity propagation，AP算法)，該方法能較快地處理大規(guī)模數(shù)據(jù).相比較于其他傳統(tǒng)的聚類算法，AP算法將每個數(shù)據(jù)點都作為候選的類代表點，避免了聚類結(jié)果受限于初始類代表點的選擇.同時該算法對于數(shù)據(jù)集生成的相似度矩陣的對稱性沒有要求，并在處理大規(guī)模多類數(shù)據(jù)時運算速度快，所以能夠很好的解決非歐空間問題以及大規(guī)模稀疏矩陣計算問題等[13].因而，與傳統(tǒng)的聚類算法相比，AP算法是一種確定性的聚類算法，有比較穩(wěn)定的聚類結(jié)果.

不同日公交短時客流差異較大，為了提高SVM的泛化能力，文中使用AP算法將客流數(shù)據(jù)分為若干個SVM訓(xùn)練子樣本集.

對于一個有N個樣本的公交短時客流數(shù)據(jù)集，AP算法定義任意2個樣本xi,xk之間的相似度為

(1)

定義可信度為

(2)

定義可用度為

(3)

AP 算法的基本步驟如下.

步驟1設(shè)m=0，最大迭代次數(shù)為M，計算數(shù)據(jù)集的相似度矩陣S，設(shè)定p值，設(shè)定初始可信度和可用度r(0)(i,k)=0,a(0)(i,k)=0及阻尼系數(shù)λ.

步驟2如果m大于M，則轉(zhuǎn)步驟5，否則，m=m+1按式(2)及(3)計算r(m)(i,k),a(m)(i,k).

步驟3按下式更新可用度和可信度.

(4)

(5)

步驟4確定聚類中心，(r(m)(i,k)+a(m)(i,k)>0時認為是一個聚類中心)，返回步驟2.

步驟5將其余點根據(jù)相似度劃分到各個聚類中，算法結(jié)束.

2基于聚類的SVM預(yù)測算法

支持向量機在回歸預(yù)測方面有廣泛的應(yīng)用，其核函數(shù)和參數(shù)的選擇對其應(yīng)用結(jié)果有較大影響.文中首先對每一個數(shù)據(jù)聚類子樣本，構(gòu)造一個SVM預(yù)測模型，然后以聚類子樣本訓(xùn)練支持向量.

2.1SVM模型及核函數(shù)選取

支持向量機是通過一個非線性映射函數(shù)，將輸入空間的低維數(shù)據(jù)映射到高維特征空間中，通過高維空間的線性回歸計算，實現(xiàn)低維空間里非線性回歸的效果[14].其線性回歸函數(shù)模型可表示為

(6)

式中：K(x,xi)為SVM模型的核函數(shù).

常用的核函數(shù)有線性核函數(shù)、多項式核函數(shù)、徑向基核函數(shù)(RBF)、Sigmoid核函數(shù).文獻[14]對上述4類核函數(shù)的SVM預(yù)測性能進行了測試，結(jié)果表明RBF核函數(shù)具有較高的預(yù)測準確率.文中選取RBF函數(shù)作為核函數(shù)，其具體形式為

(7)

2.2SVM參數(shù)優(yōu)化

正則化參數(shù)和核參數(shù)共同決定著SVM的性能好壞，只有選擇合適的正則化參數(shù)和核參數(shù)，才能得到較好的SVM模型.正則化參數(shù)γ能夠有效平衡模型的復(fù)雜度與誤差精度.核函數(shù)參數(shù)σ2決定著數(shù)據(jù)樣本的分布特性，其值較大時，越容易產(chǎn)生欠學(xué)習(xí)現(xiàn)象，其值較小時，易產(chǎn)生過學(xué)習(xí)現(xiàn)象.為獲得較好的預(yù)測性能，有必要對SVM的參數(shù)進行優(yōu)化選擇.

遺傳算法是一種具有自適應(yīng)優(yōu)化搜索的方法, 為此，文中采用遺傳算法對SVM的參數(shù)進行優(yōu)化選擇.

1) 染色體的編碼染色體V由兩個基因組成，采用將γ,σ2參數(shù)擴大100倍，用整數(shù)編碼的方式表示.

2) 交叉操作按交叉概率Pc從父代選擇交叉染色體，兩兩分組，并對每組染色體進行如下操作：隨機選擇一個要交叉的基因，將染色體中該基因進行交換，從而得到兩條新的染色體.

3) 變異操作對popsize個染色體以變異概率Pm進行變異：選擇一個要變異的基因，并隨機產(chǎn)生一個[-原基因/10，原基因/10]間的整數(shù)R，令新基因=原基因+R，從而得到一條新的染色體.

4) 適應(yīng)度評價將種群中染色體相對誤差絕對值的倒數(shù)定義為該染色體的適應(yīng)度值，則染色體的適應(yīng)度函數(shù)為

(8)

式中：L為實際值；D為絕對誤差，若D=0，令Fit(V)=+∞.

5) 選擇操作采用最佳個體保存和適應(yīng)度比例相結(jié)合的選擇策略.將每代群體中的個體按照適應(yīng)度由大到小排列，排在第一位的個體性能最優(yōu)，將它直接復(fù)制一個進入下一代，并排在第一位，其余個體采用輪盤賭法選擇產(chǎn)生.

6) 終止準則程序終止控制采用適應(yīng)值變化控制準則，當(dāng)連續(xù)G代個體最優(yōu)適應(yīng)值不發(fā)生變化時，終止算法.

3公交短時客流預(yù)測

3.1 公交短時客流聚類分析

文中選取蘭州市快速公交的蘭州交通大學(xué)站點進行觀測，以10 min為觀測間隔，對2014年5～6月站點06:00～08:00間的客流到達數(shù)據(jù)進行統(tǒng)計.利用AP算法進行聚類分析，取不同的參考度p得到的聚類數(shù)及聚類結(jié)果見表1.

表1　聚類結(jié)果表

從聚類結(jié)果來看，聚類數(shù)主要受參考度p值的影響.周六和周日在一個相對穩(wěn)定的聚類內(nèi)，隨著聚類數(shù)的減少，周一與周二，周四與周五的數(shù)據(jù)分別聚集為一類，而部分周三與周一、周二、周四或周五在一個分類內(nèi)，最終周一至周五為一大類.從聚類的過程來看，部分數(shù)據(jù)的聚類不太穩(wěn)定，這也說明了公交短時客流受到多種因素的影響.

3.2基于子類的核函數(shù)參數(shù)優(yōu)化分析

以時段為輸入變量，利用前7周的客流數(shù)據(jù)對第8周客流數(shù)據(jù)進行校驗.設(shè)遺傳算法種群個數(shù)為30，G=150，交叉概率Pc=0.25，變異概率Pm=0.35.利用文中設(shè)計的計算方法對不同聚類進行參數(shù)優(yōu)選.其中，在不進行分類情況下，采用遺傳算法對SVM模型的參數(shù)進行優(yōu)化，其進化過程見圖2.由圖2可見, 遺傳算法可以在較少代內(nèi)找到穩(wěn)定滿意解, 因此, 采用遺傳算法尋找SVM模型的參數(shù)是一種有效的途徑.

圖2　總誤差與進化代數(shù)變化曲線圖

各聚類參數(shù)優(yōu)選的結(jié)果見表2，其中設(shè)每個預(yù)測時段的相對誤差為(絕對誤差/真值)×100%，總誤差為一周所有預(yù)測時段相對誤差的總和.由表2可以看出，6個分類的總誤差最小，為493.07%，2個分類的總誤差次之，為504.54%，但與6個分類的總誤差相差不大，無分類的誤差最大，為753.70%.

3.3預(yù)測結(jié)果對比分析

利用上述各分類得到的最佳參數(shù)γ和σ2對SVM進行訓(xùn)練及預(yù)測，將第8周客流預(yù)測數(shù)據(jù)與實際數(shù)據(jù)進行對比，部分結(jié)果見圖3.

從圖中可以看出，6個分類的預(yù)測效果較好，與實際數(shù)據(jù)趨勢較為符合，平均相對誤差也較小，6個分類的最大相對誤差不超過15%；對于周末，采用分類預(yù)測與不分類預(yù)測結(jié)果差異較大，不分類預(yù)測的結(jié)果相對誤差較大.2個分類的預(yù)測效果好于不分類，當(dāng)部分數(shù)據(jù)樣本聚類不穩(wěn)定時，可采用2個分類進行預(yù)測.由此可見，訓(xùn)練樣本的分類會直接影響SVM的預(yù)測效果.

3.4短時客流的預(yù)測

選取6個分類的檢驗樣本及優(yōu)選參數(shù)建立預(yù)測模型，并訓(xùn)練樣本，對未來一周內(nèi)06：00～08：00間10 min間隔客流數(shù)據(jù)進行預(yù)測，結(jié)果見表3.

通過對BRT蘭州交通大學(xué)站客流調(diào)查分析，發(fā)現(xiàn)該站客流在上下課時間段客流會突然的增多，而其他時間段，客流較為平穩(wěn).

4結(jié)論

文中設(shè)計了一種基于AP聚類的SVM公交短時客流預(yù)測方法，該方法先用AP聚類算法將客流數(shù)據(jù)劃分成若干個聚類子集，對每一子集建立SVM預(yù)測模型，通過遺傳算法對模型的參數(shù)進行優(yōu)化選擇，并利用蘭州市快速公交車站實際調(diào)查數(shù)據(jù)進行驗證，得出以下結(jié)論：

表2　參數(shù)優(yōu)選結(jié)果表

圖3　客流預(yù)測結(jié)果與實際值對比圖

星期以下時間段的客流量/人06:00～06:1006:10～06:2006:20～06:3006:30～06:4006:40～06:5006:50～07:0007:00～07:1007:10～07:2007:20～07:3007:30～07:4007:40～07:5007:50～08:00一639525017714499616883496950二5579225177149101756052677949三5578237219154117826660613741四6069203243156108847774425054五5810922423717789836471705152六648995948782757967526357日6276851028192837971605662

1) 使用AP 聚類算法優(yōu)化數(shù)據(jù)集，可以得到高質(zhì)量、小樣本的SVM訓(xùn)練集.

2) 訓(xùn)練樣本的分類會直接影響SVM的預(yù)測效果.采用分類的SVM預(yù)測結(jié)果精度更高.

3) 遺傳算法可以在較少代內(nèi)完成SVM 模型參數(shù)的優(yōu)選，是確定SVM模型參數(shù)的一種有效方法.

參 考 文 獻

[1]楊兆升．城市智能公共交通系統(tǒng)理論與方法[M]．北京：中國鐵道出版社，2002．

[2]張春輝,宋瑞,孫楊.基于卡爾曼濾波的公交站點短時客流預(yù)測[J].交通運輸系統(tǒng)工程與信息,2011,11(4):154-159.

[3]YIN H, WONG S C, XU J, et al. Urban traffic flow prediction using a fuzzy-neural approach[J]. Transportation Research Part C: Emerging Technologies,2002,10(2):85-98.

[4]俞潔,楊曉光.基于改進BP神經(jīng)網(wǎng)絡(luò)的公交線路OD矩陣推算方法[J].系統(tǒng)工程,2006,24(4):89-92.

[5]劉凱,李文權(quán),趙錦煥.短時公交客流小波預(yù)測方法研究[J].交通運輸工程與信息學(xué)報,2010(2):111-117.

[6]楊軍,侯忠生.基于小波分析的最小二乘支持向量機軌道交通客流預(yù)測方法[J].中國鐵道科學(xué),2013,34(3):122-127.

[7]GONG M, FEI X, WANG Z H, et al. A sequential framework for short-term passenger flow prediction at bus stop[C].Transportation Research Board 93rd Annual Meeting，2014，14：116-123.

[8]鄧滸楠,朱信山,張瓊,等.基于多核最小二乘支持向量機的短期公交客流預(yù)測[J].交通運輸工程與信息學(xué)報,2012,10(2):84-88.

[9]王樹洋,黃天民,方新.基于PSO-SVM的交通流量短時預(yù)測[J].重慶交通大學(xué)學(xué)報：自然科學(xué)版，2012,31(4)：55-58.

[10]郭士永,李文權(quán),白薇,等.基于最小二乘向量機的公交站點短時客流預(yù)測[J].武漢理工大學(xué)學(xué)報:交通科學(xué)與工程版,2013,37(3):603-607.

[11]CHEN Q, LI W, ZHAO J. The use of LS-SVM for short-term passenger flow prediction[J]. Transport,2011,26(1):5-10.

[12]FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science,2007,315(5814):972-976.

[13]馮曉磊.近鄰傳播聚類算法研究[D].鄭州：解放軍信息工程大學(xué)，2011.

[14]黃成泉,周麗華,王林.基于SVM的年度收入預(yù)測模型研究[J].統(tǒng)計與決策,2013(17):24-26.

Short-term Passenger Flow Forecasting on Bus Station

Based on Affinity Propagation and Support Vector Machine

YANG XinfengLIU Lanfen

(SchoolofTrafficandTransportation,LanzhouJiaotongUniversity,Lanzhou730070,China)

Abstract：Short-term passenger flow forecasting on bus stop is an important technical support for bus dispatch strategy. A Support Vector Machine (SVM) method based on Affinity Propagation (AP) is developed to forecast short-term passenger flow based on the characteristic analysis．The AP clustering algorithm is used to divide the passenger flow into several cluster subsets and the prediction model of SVM is established based on each subset. Then, the parameters of prediction model are optimized by genetic algorithms. This forecasting method is validated on some bus stations on Lanzhou bus rapid transit. The results show that the designed genetic algorithm can effectively solve the problem of parameter optimization in SVM model, the classified passenger flow data using the AP algorithm can improve the forecasting accuracy of SVM and this method is suitable for the short-term passenger flow forecasting.

Key words：bus; short-term passenger flow forecasting; SVM; AP algorithm; genetic algorithm

收稿日期：2015-11-02

doi:10.3963/j.issn.2095-3844.2016.01.008

中圖法分類號：U491