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

楊信豐　劉蘭芬

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

?

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

楊信豐劉蘭芬

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

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

關鍵詞：公交；短時客流預測；支持向量機；AP聚類算法；遺傳算法

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

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

0引言

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

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

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

圖1　公交車站短時客流預測流程圖

1聚類分析

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

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

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

(1)

定義可信度為

(2)

定義可用度為

(3)

AP 算法的基本步驟如下.

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

步驟2如果m大于M，則轉步驟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將其余點根據相似度劃分到各個聚類中，算法結束.

2基于聚類的SVM預測算法

支持向量機在回歸預測方面有廣泛的應用，其核函數和參數的選擇對其應用結果有較大影響.文中首先對每一個數據聚類子樣本，構造一個SVM預測模型，然后以聚類子樣本訓練支持向量.

2.1SVM模型及核函數選取

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

(6)

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

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

(7)

2.2SVM參數優(yōu)化

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

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

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

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

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

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

(8)

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

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

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

3公交短時客流預測

3.1 公交短時客流聚類分析

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

表1　聚類結果表

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

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

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

圖2　總誤差與進化代數變化曲線圖

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

3.3預測結果對比分析

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

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

3.4短時客流的預測

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

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

4結論

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

表2　參數優(yōu)選結果表

圖3　客流預測結果與實際值對比圖

星期以下時間段的客流量/人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)化數據集，可以得到高質量、小樣本的SVM訓練集.

2) 訓練樣本的分類會直接影響SVM的預測效果.采用分類的SVM預測結果精度更高.

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

參 考 文 獻

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

[2]張春輝,宋瑞,孫楊.基于卡爾曼濾波的公交站點短時客流預測[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神經網絡的公交線路OD矩陣推算方法[J].系統(tǒng)工程,2006,24(4):89-92.

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

[6]楊軍,侯忠生.基于小波分析的最小二乘支持向量機軌道交通客流預測方法[J].中國鐵道科學,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].交通運輸工程與信息學報,2012,10(2):84-88.

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

[10]郭士永,李文權,白薇,等.基于最小二乘向量機的公交站點短時客流預測[J].武漢理工大學學報:交通科學與工程版,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].鄭州：解放軍信息工程大學，2011.

[14]黃成泉,周麗華,王林.基于SVM的年度收入預測模型研究[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