聚类分析和支持向量机回归的交通流预测
2019-07-16邓晶张倩
邓晶 张倩
中文摘要：本文以交通流数据为研究对象，主要对数据挖掘技术在交通流预测方面的应用进行了研究和探讨。并基于研究内容，提出了基于聚类分析和支持向量机回归的交通流预测模型。并针对支持向量机参数选择，提出了人工鱼群算法使其快速寻找到最优参数组合。最后，通过实验数据论证本文所提出的算法和模型。
关键词：数据挖掘;交通流预测;聚类分析;支持向量机;人工鱼群算法
中图分类号：TP18 文献标识码：A
文章编号：1009-3044（2019）15-0013-04
Abstract： This paper takes traffic flow data as the research object， mainly studies and discusses the application of data mining technology in traffic flow prediction. Based on the research content， a traffic forecasting model based on clustering analysis and support vector machine regression is proposed. Aiming at the parameter selection of support vector machine， an artificial fish swarm algorithm is proposed to quickly find the optimal parameter combination. Finally， the algorithm and model proposed in this paper are demonstrated by experimental data.
Key words： data mining; Traffic flow forecasting; cluster analysis; Support Vector Machine; afsa
随着城市规模和交通出行需求的不断增长，人们对出行决策服务的需求越来越强烈。如何能够实时准确地预测交通流成为交通管理和控制是否能有效实现的关键问题。传统的交通流预测模型早已无法满足实践中高实时性、高精度的预测要求。目前，在智能交通流预测领域，主要采用基于非线性理论的预测模型、基于神经网络的预测模型、基于支持向量机的预测模型和多模型融合的预测模型等，以研究、开发和实现实时道路交通预测。支持向量机（SVM）是近十几年出现的一种先进的数据挖掘方法。由于交通流数据具有数据量大、维度高、非线性等特征，SVM采用结构风险最小化的学习方式可以实现在小样本的学习环境下，采用凸优化的学习方式，有效地避免过拟合和局部最优，从而使交通流预测性能大大提高。对于样本量较大的交通流数据，按照不同的属性对数据进行聚类分析，同一类别内的数据相似度更高，且数据样本量相对减小，使用支持向量机回归进行预测能够获得更好的预测效果。最后的实验数据也证明了这一点。
1 数据预处理
交通数据采集的途径和方法有很多。在采集过程中不可避免的会产生一些问题。假如不对原始采集数据进行预处理，检查并清除问题数据，妥善处理好缺失值和异常值，必然会使研究结果产生很大偏差。
本文采用牛顿插值法对缺失数据进行补值计算。采用合适的小波函数对数据进行一定尺度的小波变换，通过信号重构，去掉噪声数据。考虑到交通数据的特点，采用0均值标准化对数据进行归一化处理。
最后，从大量的交通流原始数据中选择出特征集。数据特征选择是从已知的特征集合中选择一个子集，该子集可以全面有效地对数据进行描述，后续的预测分析工作可以针对该子集进行。选择出优良的特征数据，不仅可以降低数据计算量，提升效率，而且可以帮助研究者更深入的理解研究对象。
2 基于聚类分析和支持向量机回归的交通流预测
交通流数据具有非线性、高维度的特性。支持向量机回归算法在处理小样本、非线性、高维度数据时，具有很好的预测效果。因此，我们采用支持向量机作为核心预测算法。但交通流数据样本数量比较庞大，可能会导致支持向量机的训练速度缓慢，且预测容易产生偏差。针对这一问题，我们首先采用K-means++聚类算法将数据按照交通流量、天气、节假日等属性进行聚类得到若干类别。同一类别内的数据相似度高，数据规模也相对较小。然后，通过实时数据匹配相应类的数据进行样本训练，再使用支持向量机进行预测能够获得更好的预测效果。
在支持向量机模型参数的选择的问题上，采用人工鱼群算法对支持向量机回归的参数进行优化，采用合适的参数能够进一步提高预测精度和推广能力。
2.1交通流数据的聚类分析
传统的K-means聚类算法需要人为确定初始聚类中心。不同的聚类中心可能会导致不同的聚类结果。在交通流数据聚类分析中，我们采用K-means++聚类算法，它的核心思想是选择的初始聚类中心之间的距离要尽可能远。
2.3人工鱼群算法优化支持向量机参数
支持向量机回归中参数的选择对模型的预测效果有着十分重要的影响。即损失函数ε、惩罚因子C、高斯径向基函数。如何组合这三个参数成了支持向量机回归不可避免的问题。由于参数选择的复杂性，目前还没有确定的理论来指导，而群体智能算法在参数优化问题上有很好的效果。本文使用群体智能化算法中的人工鱼群算法对支持向量机的参数进行寻优。人工鱼群算法对初值和参数不太敏感，具有自适应搜索空间的能力，且鲁棒性强，收敛速度快。更重要的是，能夠避免陷入局部极值而失去全局最优。
在人工鱼群算法中包括三种主要的算子：聚群算子、追尾算子和觅食算子。这三种算子是算法的核心，并且决定算法的性能和最优解搜索的准确度。
设Xi表示第i条人工鱼的位置;Yi表示第i条人工鱼的适应度值。其中，Yi=f（Xi）;β表示拥挤度因子;try表示人工鱼在觅食算子中的最大试探次数。
（1） 觅食算子
人工鱼按式（6）随机选择当前感知范围内的一个位置Xj，若Yi〉Yj，则按式（7）向该位置前进一步，达到一个新位置Xnext。反之，则重新随机选择位置，判断是否满足前进条件;这样反复尝试try次后，如仍不能满足前进条件，则在感知范围内随机移动一步。
Xj = xi + rand * visual （6）
Xnext = Xi + rand * step *
（2） 聚群算子
人工鱼i以自身位置Xi为中心，其感知范围内的人工鱼数目为nf，当nf ≥1时，这些人工鱼形成如式（8）的集合Si，按式（9）计算Si的中心位置Xcenter。如果Yenter< Yi且Ycenter/nf>β*Yi，表明伙伴中心有很多食物且不太拥挤，则按式（10）朝该中心方向移动一步;否则，执行觅食算子。
Si = { xj∣〡xj - xi〡≤ visual } （8）
Xcenter =
Xnext = xi + rand * step *
（3） 追尾算子
人工鱼i根据当前位置搜索其感知范围内所有伙伴中适应度最小的伙伴位置Xmin，其适应度为Ymin，如果Ymin< Yi，就Xmin为中心搜索其感知范围内的人工鱼。数目为nf，且Ymin< Yi且Ymin/nf>β*Yi，表明该位置较优且不太拥挤，则按式（11）向着适应度最小伙伴位置Xmin的方向前进一步。否则，执行觅食算子。
Xnext = xi + rand * step *
人工鱼群算法中每条人工鱼首先分别试探执行聚群算子和追尾算子，通过目标函数计算其适应度是否得到改善。将适应度改善较大的算子作为该条人工鱼的更新算子;否则执行觅食算子;若这条人工鱼达到觅食算子的最大尝试次数后，适应度依旧没有改变，则在自己周围随机移动一个位置。所有人工鱼执行上述操作后，最终人工鱼群集结在几个局部最优解周围，且全局最优极值区域周围也有较多人工鱼集结。
该模型的详细描述如下：
Step1：设置支持向量机回归相关参数的取值范围：包括损失函数ε、惩罚因子C、高斯径向基函数δ。对人工鱼群算法进行参数设置。包括鱼群的种群规模，种群迭代次数，种群的拥挤度因子，最多试探次数，人工鱼的感知距离以及人工鱼移动的步长等;
Step2：在聚类分析后得到的数据集中，选取部分测试数据，剩下的数据作为训练数据集用来进行SVR的預测分析，从而判别SVR的预测效果;
Step3：人工鱼群中的每条鱼是SVR优化参数组合（ε、C、δ），即损失函数、惩罚因子、高斯径向基函数。根据setp1中的参数取值范围初始化鱼群位置。对所有人工鱼并行寻优;
Step4：根据SVR运用训练数据集得到的预测结果，通过计算预测值与实际值的均方根误差，以此作为人工鱼的目标值。同时，比较每条人工鱼目标值的大小，将其中的最小值作为当前鱼群中的最优，并保存当前的最优人工鱼参数组合（ε、C、δ）;
Step5：每条人工鱼分别模拟聚群行为和追尾行为，通过选择游动后目标值比较小的行为来确定实际执行的行为。觅食行为是缺省行为;
Step6：在鱼群中，每更新一次位置，都需要计算当前鱼群的最优目标值。如果其中一条鱼对应的目标值小于目前保存的最优目标值，那么将其替代保存的最优目标值，同时保存最优人工鱼参数组合（ε、C、δ）。否则，最优目标值和参数组合保持不变;
Step7：判断迭代次数是否达到最大迭代次数。如果达到，输出人工鱼参数组合（ε、C、δ）和最优目标值。否则，返回step5。
2.4基于K-means++聚类算法和支持向量机回归交通流预测
本文研究的交通流数据包括交通流量、车速、占有率、日期、天气、交通时间等，在分析各方面因素后，设计了一种基于基于K-means++聚类算法和支持向量机回归的交通流预测模型。该模型的预测流程为：
Step1：对数据进行预处理，得到相对完整准确的交通流特征数据;
Step2：将交通流特征数据按照交通流量、天气、节假日等属性进行聚类得到若干类别，使得同一类别内的数据相似度更高，每个类别数据的规模也相对小;
Step3：计算交通流实时数据与已经生成的所有聚类簇的欧氏距离，匹配到相应的簇中，使得簇内的数据与预测当天的特征相似度更高。将该簇内的交通流数据作为训练样本;
Step4：使用选取的训练样本数据，应用人工鱼群算法对支持向量机参数寻优，得到支持向量机最优参数组合;
Step5：使用参数优化后的支持向量机回归模型进行预测，得出预测结果;
3实验结果和分析
3.1数据来源与评价指标
本文实验数据来源于美国加州交通局的PEMS系统。PEMS系统的数据是开源的，用于各类研究者学习和使用。在PEMS系统中，我们随机选取一个时段的数据。该段数据已经被处理成5分钟一个间隔的交通流数据。包括车辆流数、车速及车道占有率等。另外，引入天气因子，对天气情况特征做出说明;引入时间类别，对普通工作日、节假日、重大节日等作出区分。
针对本文的最终目的是为了准确地进行回归预测，我们引入了广泛应用于回归问题的评价指标，分别为平均绝对百分比误差（MAPE）和均方跟误差（RMSE）。其中，MAPE表征了预测值偏离实际值的程度。MAPE越小，表明预测值越接近于实际值，预测效果越好。RMSE表征了误差大小以及误差分布的离散程度。RMSE越小，误差离散程度就越低，预测效果也就越好。
3.2 实验一：基于聚类分析和支持向量机回归的交通流预测
3.2.1 聚类分析
本文抽取了2017年12月的交通流数据进行聚类分析。12月一共有31天，将其中的2日、11日、18日的交通流数据抽出，作为测试样本进行验证。剩下的28天数据进行聚类分析。根据最佳聚类数计算方法，即聚类数应该在2到
由上表可知，当K=4时，聚类效果最好。即最佳聚类数K为4，聚类结果为四个簇。第一类为圣诞节及连接的周末;第二类是周末;第三类是工作日且天气良好;第四类为普通工作日且天气状况差。由此可见，聚类后的每个类的特征都比较相似，类间特征差别比较明显。之后将预测的日期匹配到相应的聚类簇中，使用簇内数据作为训练样本，得到更好的预测效果。
3.2.2 支持向量机交通流预测
本文对2日、11日、18日部分时段进行交通流预测。计算预测时段前三个小时的交通流量数据与四个簇类样本中心的欧式距离，得到某一个聚类簇的欧式距离最小，并将其归为一类。将这一簇内的数据作为训练样本数据集
以下以11日的预测为例，说明实验结果。
当预测11日的交通流量时，计算得到与第三个聚类的欧式距离最小。选取第三个类中14天的数据为训练样本。使用人工鱼群算法计算得到最优参数组合（ε、C、δ）=（0.74、69、0.26）。使用优化的参数组合建立预测模型得到预测结果。与传统的SVR预测结果和实际值的对比如图1。
为了验证本文提出的预测算法，将其与传统的支持向量机回归算法、ARIMA预测算法、BP神经网络预测算法进行对比。在相同的实验环境下，不同算法的MAPE和RMSE指标如表2。
3.2.3 实验结果分析
由图1可以看出，基于聚类分析和支持向量机回归预测模型要优于传统的支持向量机模型。其预测曲线与原始实际值拟合的更好，变化趋势也与原始实际值基本一致。这表明本文提出的预测模型使用聚类对数据区分后进行训练，并对参数进行优化，可以有效地削弱随机数据导致的误差，从而有助于提升短期交通流预测的准确性。
由表2可以看出，ARIMA算法预测精度最差。传统的支持向量机和BP神经网络算法两项指标比较接近，預测精度基本相似。但支持向量机还是略胜一筹。两种SVR预测模型都优于两种经典的预测算法。而基于聚类分析和支持向量机回归预测模型的两项指标又优于传统的SVR。其中MAPE降低了30.2%，RMSE降低了35.7%。
4 结束语
本文在对交通流数据进行预处理后，通过聚类分析和支持向量机回归算法建立预测模型，实现对非线性、高唯度交通流数据的有效预测。经实验验证，优于传统的预测模型且更接近于实际交通流数据。
由于时间和水平有限，本文的研究内容有待于进一步拓展。主要有以下几点：
由于影响交通流的因素很多，本文只考虑了其中重要的若干因素，需要考虑将更多的影响因子加入模型中。
人工鱼群算法对SVR参数寻优收敛速度较慢，可以研究其与其他寻优算法结合，以达到更好的参数优化效果。
参考文献：
[1] 李青. 城市交通流预测关键技术研究[D]. 西南科技大学， 2015.
[2]王允森，盖荣丽，孙一兰. 基于牛顿迭代法的NURBS曲线插补算法[J].组合机床与自动化加工技术，2013（4）：13-17.
[3]丁世飞，齐炳娟，谭红艳.支持向量机理论与算法研究综述[J].电子科技大学学报，2011，40（1）：1-28.
[4] Son J，Jung I，Park K，et al . Tracking-by-Segmentation with Online Gradient boosting decision Tree[C]. IEEE Internatiomal Conference on Computer Vision .IEEE，2015： 3056-3064.
[5] Arthur D，Vassilvitskii S. k-means++：the advantages of careful seeding[C]Eighteenth Acm-Siam Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics，2007：1027-1035.
[6] EI-Sheimy N， Nassar S， Noureldin A . Wavelet de-noising for IMU alignment[J].IEEE Aerospace & Electronic System Magazine，2004，19（10）：32-39.
[7]朱連江，马炳先，赵学泉. 基于轮廓系数的聚类有效性分析[J]. 计算机应用，2010（s2）：139-141.
[8] 李晓磊，薛云灿，路飞，等. 基于人工鱼群算法的参数估计方法[J]. 山东大学学报（工学版），2014，34（3）：84-87.
[9] Yao X ， Wang X， Zhang Y. Summary of feature selection algorithms [C]. International Conference on Advances in Multimedia Modeling. Spring-Verlag， 2012：452-462.
[10]谭满春，冯牵斌，徐建闽. 基于ARIMA与人工神经网络组合模型的交通流预测[J]. 中国公路学报，2007，20（4）：118-121.
【通联编辑：唐一东】
