基于AP聚类的支持向量机公交站点短时客流预测*

杨信丰　刘兰芬

(兰州交通大学交通运输学院　兰州　730070)



基于AP聚类的支持向量机公交站点短时客流预测*

杨信丰刘兰芬

(兰州交通大学交通运输学院兰州730070)

摘要：公交站点短时客流预测是公交调度决策的基础，文中设计了一种基于AP聚类算法的支持向量机用于公交短时客流预测.该方法利用AP聚类算法将客流调查数据划分为若干个聚类子集，对每一子集建立支持向量机预测模型，并采用遗传算法对预测模型的参数进行优化选择.该方法在兰州市快速公交站点客流数据统计的基础上进行实例分析，结果表明：设计的遗传算法可以有效解决支持向量机模型中的参数优选问题，使用AP聚类算法对客流数据进行分类可以提高支持向量机的预测精度，该预测方法可有效的对公交车站客流进行短时预测.

关键词：公交；短时客流预测；支持向量机；AP聚类算法；遗传算法

杨信丰(1978- )：男，博士，副教授，主要研究领域为运输系统分析与决策.

*国家自然科学基金项目(批准号:61164003, 61364026)、教育部人文社会科学研究项目(批准号:13XJC630017)、甘肃省自然科学基金项目(批准号:1310RJZA032,148RJZA052)资助

0引言

公交是一种高效利用道路资源的交通方式.掌握客流变化规律、准确预测客流是公交企业科学制定运营计划的基础和关键[1].公交站点短时客流预测是智能公交调度系统中重要的决策基础与技术支持[2].

短时客流的随机性和时变性使得短时客流预测与中长期客流预测存在显著差异.公交短时客流预测已受到国内外学者的广泛关注，其研究方法主要有人工神经网络[3-4]、小波理论[5-6]、卡尔曼滤波[7]及支持向量机(support vector machine, SVM)[8-11]等.其中，SVM是一种基于统计学习理论的机器学习算法，在短时预测领域有较好的应用.影响SVM预测效果的因素主要有训练样本及训练参数.但不同时间公交短时客流的变化较大，很难直接采用原始训练样本得到合适的SVM训练参数.

针对上述问题，文中利用AP聚类算法对公交车站短时客流数据样本集进行聚类分析，将客流数据分为若干个子样本，针对每一子样本，利用遗传算法对SVM参数进行训练优化，得到较优的SVM预测模型，用于公交车站短时客流的预测，具体流程见图1.

图1　公交车站短时客流预测流程图

1聚类分析

Frey等[12]提出了近邻传播聚类算法(affinity propagation，AP算法)，该方法能较快地处理大规模数据.相比较于其他传统的聚类算法，AP算法将每个数据点都作为候选的类代表点，避免了聚类结果受限于初始类代表点的选择.同时该算法对于数据集生成的相似度矩阵的对称性没有要求，并在处理大规模多类数据时运算速度快，所以能够很好的解决非欧空间问题以及大规模稀疏矩阵计算问题等[13].因而，与传统的聚类算法相比，AP算法是一种确定性的聚类算法，有比较稳定的聚类结果.

不同日公交短时客流差异较大，为了提高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参数优化

正则化参数和核参数共同决定着SVM的性能好坏，只有选择合适的正则化参数和核参数，才能得到较好的SVM模型.正则化参数γ能够有效平衡模型的复杂度与误差精度.核函数参数σ2决定着数据样本的分布特性，其值较大时，越容易产生欠学习现象，其值较小时，易产生过学习现象.为获得较好的预测性能，有必要对SVM的参数进行优化选择.

遗传算法是一种具有自适应优化搜索的方法, 为此，文中采用遗传算法对SVM的参数进行优化选择.

1) 染色体的编码染色体V由两个基因组成，采用将γ,σ2参数扩大100倍，用整数编码的方式表示.

2) 交叉操作按交叉概率Pc从父代选择交叉染色体，两两分组，并对每组染色体进行如下操作：随机选择一个要交叉的基因，将染色体中该基因进行交换，从而得到两条新的染色体.

3) 变异操作对popsize个染色体以变异概率Pm进行变异：选择一个要变异的基因，并随机产生一个[-原基因/10，原基因/10]间的整数R，令新基因=原基因+R，从而得到一条新的染色体.

4) 适应度评价将种群中染色体相对误差绝对值的倒数定义为该染色体的适应度值，则染色体的适应度函数为

(8)

式中：L为实际值；D为绝对误差，若D=0，令Fit(V)=+∞.

5) 选择操作采用最佳个体保存和适应度比例相结合的选择策略.将每代群体中的个体按照适应度由大到小排列，排在第一位的个体性能最优，将它直接复制一个进入下一代，并排在第一位，其余个体采用轮盘赌法选择产生.

6) 终止准则程序终止控制采用适应值变化控制准则，当连续G代个体最优适应值不发生变化时，终止算法.

3公交短时客流预测

3.1 公交短时客流聚类分析

文中选取兰州市快速公交的兰州交通大学站点进行观测，以10 min为观测间隔，对2014年5～6月站点06:00～08:00间的客流到达数据进行统计.利用AP算法进行聚类分析，取不同的参考度p得到的聚类数及聚类结果见表1.

表1　聚类结果表

从聚类结果来看，聚类数主要受参考度p值的影响.周六和周日在一个相对稳定的聚类内，随着聚类数的减少，周一与周二，周四与周五的数据分别聚集为一类，而部分周三与周一、周二、周四或周五在一个分类内，最终周一至周五为一大类.从聚类的过程来看，部分数据的聚类不太稳定，这也说明了公交短时客流受到多种因素的影响.

3.2基于子类的核函数参数优化分析

以时段为输入变量，利用前7周的客流数据对第8周客流数据进行校验.设遗传算法种群个数为30，G=150，交叉概率Pc=0.25，变异概率Pm=0.35.利用文中设计的计算方法对不同聚类进行参数优选.其中，在不进行分类情况下，采用遗传算法对SVM模型的参数进行优化，其进化过程见图2.由图2可见, 遗传算法可以在较少代内找到稳定满意解, 因此, 采用遗传算法寻找SVM模型的参数是一种有效的途径.

图2　总误差与进化代数变化曲线图

各聚类参数优选的结果见表2，其中设每个预测时段的相对误差为(绝对误差/真值)×100%，总误差为一周所有预测时段相对误差的总和.由表2可以看出，6个分类的总误差最小，为493.07%，2个分类的总误差次之，为504.54%，但与6个分类的总误差相差不大，无分类的误差最大，为753.70%.

3.3预测结果对比分析

利用上述各分类得到的最佳参数γ和σ2对SVM进行训练及预测，将第8周客流预测数据与实际数据进行对比，部分结果见图3.

从图中可以看出，6个分类的预测效果较好，与实际数据趋势较为符合，平均相对误差也较小，6个分类的最大相对误差不超过15%；对于周末，采用分类预测与不分类预测结果差异较大，不分类预测的结果相对误差较大.2个分类的预测效果好于不分类，当部分数据样本聚类不稳定时，可采用2个分类进行预测.由此可见，训练样本的分类会直接影响SVM的预测效果.

3.4短时客流的预测

选取6个分类的检验样本及优选参数建立预测模型，并训练样本，对未来一周内06：00～08：00间10 min间隔客流数据进行预测，结果见表3.

通过对BRT兰州交通大学站客流调查分析，发现该站客流在上下课时间段客流会突然的增多，而其他时间段，客流较为平稳.

4结论

文中设计了一种基于AP聚类的SVM公交短时客流预测方法，该方法先用AP聚类算法将客流数据划分成若干个聚类子集，对每一子集建立SVM预测模型，通过遗传算法对模型的参数进行优化选择，并利用兰州市快速公交车站实际调查数据进行验证，得出以下结论：

表2　参数优选结果表

图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 聚类算法优化数据集，可以得到高质量、小样本的SVM训练集.

2) 训练样本的分类会直接影响SVM的预测效果.采用分类的SVM预测结果精度更高.

3) 遗传算法可以在较少代内完成SVM 模型参数的优选，是确定SVM模型参数的一种有效方法.

参 考 文 献

[1]杨兆升．城市智能公共交通系统理论与方法[M]．北京：中国铁道出版社，2002．

[2]张春辉,宋瑞,孙杨.基于卡尔曼滤波的公交站点短时客流预测[J].交通运输系统工程与信息,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].系统工程,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].统计与决策,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