基于AP聚類的支持向量機(jī)公交站點(diǎn)短時(shí)客流預(yù)測(cè)*

楊信豐　劉蘭芬

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

?

基于AP聚類的支持向量機(jī)公交站點(diǎn)短時(shí)客流預(yù)測(cè)*

楊信豐劉蘭芬

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

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

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

楊信豐(1978- )：男，博士，副教授，主要研究領(lǐng)域?yàn)檫\(yùn)輸系統(tǒng)分析與決策.

*國(guó)家自然科學(xué)基金項(xiàng)目(批準(zhǔn)號(hào):61164003, 61364026)、教育部人文社會(huì)科學(xué)研究項(xiàng)目(批準(zhǔn)號(hào):13XJC630017)、甘肅省自然科學(xué)基金項(xiàng)目(批準(zhǔn)號(hào):1310RJZA032,148RJZA052)資助

0引言

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

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

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

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

1聚類分析

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

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

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

(1)

定義可信度為

(2)

定義可用度為

(3)

AP 算法的基本步驟如下.

步驟1設(shè)m=0，最大迭代次數(shù)為M，計(jì)算數(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)計(jì)算r(m)(i,k),a(m)(i,k).

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

(4)

(5)

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

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

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

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

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

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

(6)

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

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

(7)

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

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

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

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

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

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

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

(8)

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

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

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

3公交短時(shí)客流預(yù)測(cè)

3.1 公交短時(shí)客流聚類分析

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

表1　聚類結(jié)果表

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

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

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

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

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

3.3預(yù)測(cè)結(jié)果對(duì)比分析

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

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

3.4短時(shí)客流的預(yù)測(cè)

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

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

4結(jié)論

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

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

圖3　客流預(yù)測(cè)結(jié)果與實(shí)際值對(duì)比圖

星期以下時(shí)間段的客流量/人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)練樣本的分類會(huì)直接影響SVM的預(yù)測(cè)效果.采用分類的SVM預(yù)測(cè)結(jié)果精度更高.

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

參 考 文 獻(xiàn)

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

[2]張春輝,宋瑞,孫楊.基于卡爾曼濾波的公交站點(diǎn)短時(shí)客流預(yù)測(cè)[J].交通運(yùn)輸系統(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]俞潔,楊曉光.基于改進(jìn)BP神經(jīng)網(wǎng)絡(luò)的公交線路OD矩陣推算方法[J].系統(tǒng)工程,2006,24(4):89-92.

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

[6]楊軍,侯忠生.基于小波分析的最小二乘支持向量機(jī)軌道交通客流預(yù)測(cè)方法[J].中國(guó)鐵道科學(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]鄧滸楠,朱信山,張瓊,等.基于多核最小二乘支持向量機(jī)的短期公交客流預(yù)測(cè)[J].交通運(yùn)輸工程與信息學(xué)報(bào),2012,10(2):84-88.

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

[10]郭士永,李文權(quán),白薇,等.基于最小二乘向量機(jī)的公交站點(diǎn)短時(shí)客流預(yù)測(cè)[J].武漢理工大學(xué)學(xué)報(bào):交通科學(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ù)測(cè)模型研究[J].統(tǒng)計(jì)與決策,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

中圖法分類號(hào)：U491