钟慧玲，邝朝剑，黄晓宇，蔡文学

（1.华南理工大学 经济与贸易学院，广东 广州510006；2.中国移动，广东 东莞523129）

0 引 言

交通流预测是利用交通流信息选择最合适的模型和方法来预测未来一段时间的交通状况，预测结果可广泛应用于交通诱导、出行路线规划等领域。根据预测时段的长短，分为短时交通流预测 （15分钟内）和中长期预测［1］。

目前，常用的预测模型有时间序列模型［2］、卡尔曼滤波模型［3］、非参数回归模型［4］、神经网络模型［5］、支持向量机［6］以及这些模型的组合模型［7－8］。随着研究的深入，有学者将数据挖掘方法引入交通流预测［9－10］。文献［10］提出了基于K近邻的非参数回归方法，通过挖掘历史数据中的K最近邻，拟合成预测值，然而该方法需要维护庞大且有代表性的历史数据库。文献［11］通过研究发现道路交通流具有自身的规律，通过挖掘这些规律，可对道路的交通流进行预测。总结国内外研究，主要存在以下两个问题：一是通过增加模型的复杂性来提高预测精度，计算量大，不能很好满足实时要求；二是研究集中于短时交通流预测，支持中长期交通流预测的模型较少。

针对这两个问题，在张涛和戢晓峰的研究基础上，本文提出基于历史频繁模式的交通流预测算法，通过挖掘道路交通流的历史频繁模式，结合道路实时的交通信息，进行交通流预测。与基于K近邻的非参数回归方法不同，本文提出算法使用历史数据中频繁出现的交通流模式进行预测，而不是简单使用历史数据拟合成预测值，更强调交通流出现的规律性；而且，预测模型更简单。经实例证明，算法具有较高预测精度、且支持交通流短时和中长期预测。

1 基于历史频繁模式的交通流预测算法

1.1 算法框架

基于历史频繁模式的交通流预测算法是一种数据驱动的预测方法，通过挖掘交通流历史数据的频繁模式，与当前获取的实时交通信息进行模式匹配，预测未来一段时间内道路的交通状况。算法的关键因素是交通流历史频繁模式的挖掘和预测算法的构建，其流程如图1所示。

图1 基于历史频繁模式的交通流预测算法流程

1.2 交通流历史频繁模式挖掘

频繁模式挖掘是数据挖掘领域一个重要的研究内容，广泛应用于商业分析、Web数据挖掘和生物序列分析，然而，在交通流预测中还没有相关应用。目前，国内外学者提出了许多挖掘频繁模式的算法，如Apriori算法、GSP算法、SPADE算法、FreeSpan算法等［12－14］，然而，这些算法在挖掘频繁模式时，大多采用精确匹配，要求相同的模式在数据库中重复出现，且算法效率低，挖掘的模式有冗余。在实际应用中，绝对相同的模式很少，因此，挖掘近似的频繁模式更有意义。H.C.Kum等［15］提出了挖掘数据库中近似频繁模式的ApproxMAP算法，该算法有效且高效，能挖掘出长频繁模式。这里，结合ApproxMAP算法挖掘交通流历史频繁模式。

1.2.1 相关定义

设I＝ ｛i1，i2，…，in｝是由n个不同的项组成的集合，I的子集称为项集。序列就是由若干个项集组成的有序列表，一个交通流时间序列S表示为＜s1，s2，…，sn＞，其中si为项集 （即交通状况），可表示为 （x1，x2，…，xn），当si只包含一项时，可省略括号。长度为L的序列记为L－序列。

定义1 对于交通流时间序列数据库中的序列X，X的支持度定义为序列X在数据库中出现的次数，记为support（X）。

定义2 给定最小支持度阈值min＿sup，如果序列X的支持度support（X）≥min＿sup，则称序列X为频繁序列。

定义3 给定最小距离阈值min＿dist，序列X的近似支持度定义为数据库中与X的编辑距离不超过min＿dist的另一序列Y的数目；如果序列X的近似支持度不小于给定的min＿sup，则称序列X为近似频繁序列。

1.2.2 挖掘算法

结合ApproxMAP算法的交通流历史频繁模式挖掘算法主要包含两个阶段。一是交通流历史数据分类，通过聚类算法，把相关性较强的交通流历史数据分成一类；二是在交通流历史数据分类的基础上，对每一分类的数据进行多序列比对，挖掘出交通流历史频繁模式。

为了对交通流历史数据进行有效分类，原始数据经噪声数据处理和缺失数据填充预处理之后，以5分钟划分间隔，使用符号累积近似 （SAX）技术［16］按5级把交通流历史数据转化成交通流历史数据时间序列，计算序列间交通流的相似性。这里，使用编辑距离来度量两交通流序列之间的相似性，编辑距离越小，相似性越大。给定序列X＝＜x1，x2，…，xn＞和Y＝＜y1，y2，…，ym＞的编辑距离可用以下动态规划算法求解。

然后，使用基于密度的K最近邻聚类算法将这些交通流历史数据时间序列根据交通流的相似程度划分到不同的类中，其主要步骤如下。

（1）初始化每一交通流序列为一类。对每一类中的序列Si，令Density（CSi）＝Density（Si）；

（2）基于序列密度合并近邻。对于每一个交通流序列Si，设Si1，…，Sin为其编辑距离不大于dk的近邻；对于每一个交通流序列Si∈ ｛Si1，…，Sin｝，如果Density（Si）＜Density（Sj）且 不 存 在S′j满 足：dist（Si，S′j） ＜dist（Si，Sj）且Density（Si）＜Density（S′j），合并Si和Sj所在类CSi和CSj，令新类密度为：max ｛Density（CSi），Density（CSj）｝；

（3）基于类密度合并。对交通流时间序列中所有序列Si，如果不存在序列密度大于其的近邻，但存在一些密度等于Density（Si）的近邻Sj，如果Density（CSi）＞Density（CSj），合并Si和Sj所在类CSi和CSj。

其中，交通流序列Si的密度为

式中，d＝max｛d1，d2，…，dk｝——交通流序列Si与其他序列的编辑距离的第k最小值，k——用户定义参数，n＝ ｛Sj∈S｜dist（Si，Sj）≤d｝ ——所有交通流序列中与序列Si的编辑距离不大于d的序列的数目。

对交通流历史数据进行分类后，可使用多序列比对方法，挖掘每一分类的交通流历史数据的近似频繁模式。定义 “交通状况加权序列”结构为 “WS＝＜X1：v1，…，Xl：vl＞：n”，一个交通状况加权序列包含以下信息：

（1）当前类中包含n个交通流序列，且n是交通状况加权序列的全局权重；

（2）当前类中，有vi个交通流序列在位置i包含交通状况项目集Xi（1≤i≤l）；

（3）交通状况加权序列中每个交通状况项目集格式为Xi＝ （xj1：wj1，…，xjm：wjm），表示在当前类中，有wjk个交通流序列在位置i包含xjk（1≤i≤l且1≤k≤m）。

对于交通状况加权序 列WS＝＜ （x11：w11，…，x1m1：w1m1）：v1，…，（xl1：wl1，…，xlm1：wlm1）：vl＞：n，位置i的交通状况项目集xij：wij的支持度定义为

交通状况项目集的支持度越大表示该交通状况在交通流历史数据中被更多的序列包含。通过定义最小支持度阈值min＿sup（0≤min＿sup≤1），从交通状况加权序列中移除支持度小于min＿sup的项目，得到满足支持度要求的近似频繁模式。

假设聚类后交通流序列S1＝＜1，1，2，2，3＞、S2＝＜1，2，1，3，2＞和S3＝＜2，1，3，2，2＞合成一类，其交通状况加权序列计算如表1所示。定义最小支持度阈值min＿sup＝0.5，则类中近似频繁模式为＜1，1＞和＜2，2＞。

表1 加权序列计算

1.3 预测算法

结合ApproxMAP算法可以有效地挖掘出交通流历史频繁模式，在此基础上，通过结合获取的实时交通信息，可对交通状况进行预测。利用滑动窗口技术，通过逐项计算实时交通信息序列与等长的历史频繁子模式的相似性，根据最近邻匹配原则，选择交通流相似度最大时的最佳点进行预测。交通流预测算法流程如图2所示。

2 实验与分析

交通流预测要求预测结果有效、准确，以保证交通诱导、出行路线规划等应用的可行性。为了验证本文提出的基于历史频繁模式的交通流预测算法的有效性和准确性，使用从珠海市城市路网中采集的真实的GPS浮动车数据，随机选取实验路段和预测时间，对提出的算法进行重复实验，统计预测值与实际值的平均误差。

2.1 数据来源

实验数据来自于珠海市城市路网采集的GPS浮动车数据，如表2所示。随机选取路网中的10条路段作为实验样本，使用的实验数据见 “历史数据”和 “测试数据”所示。其中，“历史数据”是用于挖掘交通流历史频繁模式的数据，“测试数据”为用于预测与对比的随机选取的某天数据。

2.2 结果分析

实验对不同的预测时长，随机选取100个时段进行交通流预测，以全面考虑在不同交通状况 （高峰、闲时）下算法的有效性和准确性，以及算法的稳定性。实验内容包括算法准确性分析、参数影响、以及与基于K近邻的非参数回归预测算法的对比。

图2 预测算法流程

表2 实验数据量

2.2.1 算法准确性分析

为了验证算法的有效性和准确性，实验选取近邻参数K＝5，最小支持度参数min＿sup＝0.5，分别设置预测时长为15分钟、30分钟、45分钟和60分钟，对于每个预测时长，随机选取起止时间预测100次，计算真实值与预测值标准差的均值。实验结果如图3所示。

图3 交通流预测误差结果

结合实际路网拓扑和图3结果，发现算法对交通状况平稳的道路预测精度较高，而对交叉路口 （特别是存在信号灯路口）上的道路，由于其交通状况波动较大，预测精度稍差。

从图3还知，算法对随机选取的10条道路的平均误差约为0.35。为了验证算法的平均预测误差不超过0.3，我们进行t检验 （假设H0：μ≤0.3，H1：μ＞0.3），设置显著性水平α＝0.05，分别对各个预测时长的统计量进行右边检验，得到的P值分别为0.495、0.495、0.444和0.393，均大于α＝0.05，因此，接受假设H0，即算法的平均预测误差不超过0.3。

此外，为了说明算法对中长期交通流预测和短时交通流预测 （15分钟内）具有同样的预测精度，我们对预测时长为15分钟与30分钟、15分钟与45分钟、15分钟与60分钟的实验结果进行了配对t检验，设置显著性水平α＝0.05，得到双尾检验的P值分别为1.00、0.718和0.537，均大于α＝0.05，因此，算法对交通流进行中长期预测具有与短时预测同样高的预测精度。

2.2.2 参数影响

算法具有两个关键参数，最近邻参数K和最小支持度参数min＿sup，H.C.Kum已经通过实验确定最佳参数K的选取范围为 ［3，10］，可根据历史数据的规模进行设置。因此，这里主要讨论最小支持度参数min＿sup对算法的影响。

通过固定参数K取值，选取不同的min＿sup值进行实验来分析参数min＿sup对算法的影响。实验设置近邻K取值范围为 ［4，7］，对于每一个预测时长和每条随机选取实验路段，随机选取起止时间预测100次，计算预测值与真实值的标准差，然后统计所有道路预测误差的均值。实验结果如图4所示。

由图4可知，固定参数K时，参数min＿sup在 ［0.3，0.7］范围内取值对预测结果的精度影响不大。然而，如果最小支持度参数min＿sup设置过大，会减少挖掘到的交通流历史频繁模式的数量，因此，在实际应用中，为了保证挖掘到更多的交通流历史频繁模式用于预测，建议min＿sup取值范围为 ［0.3，0.5］。

2.2.3 算法对比

使用本文提出的算法与张涛等提出的基于K近邻的非参数回归方法进行实验对比，本文算法选取参数K＝5，min＿sup＝0.5，基于K近邻的非参数回归方法近邻K取值范围为 ［1，20］。对于每一个预测时长，和每条随机选取实验路段，随机选取起止时间预测100次，计算预测值与真实值的标准差，然后统计所有道路预测误差的均值，实验结果如图5所示。

计算不同预测时长 （5－60分钟）下各算法预测误差均值的方差，本文算法的方差为0.0003，而基于K近邻的非参数回归方法当K＝20时方差最小，为0.0048，远大于本文算法。结合图5中实验结果可以发现，本文提出算法的预测性能比基于K近邻的非参数回归方法稳定，且中长期预测与短时预测具有同样高的精度，预测误差波动不大，而基于K近邻的非参数回归方法预测误差波动较大，预测性能不稳定。

3 结束语

通过深度挖掘交通流历史数据的规律，本文提出的基于历史频繁模式的交通流预测算法能有效地对交通流进行短时和中长期预测，且具有中长期预测与短时预测具有同样高的预测精度、受参数影响小的优点。最后，与基于K近邻的非参数回归预测方法进行对比，结果表明基于历史频繁模式的预测方法具有更高的预测精度和预测性能，预测误差波动更小。通过实验还发现，算法要求有足够的数据量支持以有效地挖掘出用于预测的交通流历史频繁模式，道路数据量越丰富，预测精度越高，因此，可以将浮动车数据与环形感应线圈数据进行融合，提高数据的数量和质量，进而提高算法的适用性。此外，还可以进一步考虑路网中道路间的空间相关性，从时空角度挖掘交通流规律，增加预测结果的准确性。

图4 参数min＿sup取不同值时实验结果

图5 与基于K近邻的非参数回归方法对比结果

［1］LU Haiting，ZHANG Ning，HUANG Wei，et al.Research progress of short term traffic flow prediction methods ［J］.Journal of Transportation Engineering and Information，2009，7 （4）：84－91 （in Chinese）.［陆海亭，张宁，黄卫，等.短时交通流预测方法研究进展 ［J］.交通运输工程与信息学报，2009，7 （4）：84－91.］

［2］DONG H H，JIA L M，SUN X L，et al.Road traffic flow prediction with a time－oriented ARIMA model ［C］.International Joint Conference on INC IMS and IDC，2009.

［3］Abdi J，Moshiri B，Jafari E，et al.Traffic state variables estimating and predicting with extended Kalman filtering ［C］.International Conference on Power Control and Embedded Systems，2010.

［4］ZHANG T，HU L F，LIU Z X，et al.Nonparametric regression for the short－term traffic flow forecasting ［C］.International Conference on Mechanic Automation and Control Engineering，2010.

［5］Gültekin Cetiner B，Murat Sari，Oˇguz Borat.A neural network based traffic－flow prediction model［J］.Mathematical and Computational Applications，2010，15 （2）：269－278.

［6］SUN D Z，WANG Q X，JIANG X Q.The application of support vector machines （SVM）for traffic condition prediction using ITS data ［C］.Proceedings of the Conference on Traffic and Transportation Studies，2010.

［7］GUO X，DENG F Q.Short－term of intelligent traffic flow based on BP neural network and ARIMA model［C］.International Conference on E－Product E－Service and E－Entertainment，2010.

［8］YE Yan，LU Zhilin.Neural network short－term traffic flow forecasting model based on particle swarm optimization ［J］.Computer Engineering and Design，2009，30 （18）：4296－4298（in Chinese）.［叶嫣，吕智林.基于粒子群优化的神经网络短时交通流量预测 ［J］.计算机工程与设计，2009，30 （18）：4296－4298.］

［9］YAN Wei，LIU Yungang，WANG Guihua，et al.Data mining using in a novel traffic flow forecasting model［J］.Systems Engineering－Theory ＆ Practice，2010，30 （7）：1320－1325 （in Chinese）.［闫伟，刘云岗，王桂华，等.基于数据挖掘的交通流预测 模 型 ［J］. 系 统 工 程 理 论 与 实 践，2010，30 （7）：1320－1325.］

［10］ZHANG Tao，CHEN Xian，XIE Meiping，et al.K－NN based nonparametric regression method for short－term trafficflow forecasting ［J］.Systems Engineering－Theory ＆ Practice，2010，30 （2）：376－384 （in Chinese）.［张涛，陈先，谢美萍，等.基于K近邻非参数回归的短时交通流预测方法［J］.系统工程理论与实践，2010，30 （2）：376－384.］

［11］JI Xiaofeng.An overview on methods of urban road traffic state analysis and their prospect ［J］.Road Traffic ＆Safety，2008，9 （6）：11－15 （in Chinese）.［戢晓峰.城市道路交通状态分析方法回顾与展望 ［J］.道路交通与安全，2008，9（6）：11－15.］

［12］Aaron Ceglar，John F Roddick.Association mining ［J］.ACM Computing Surveys， 2006， 38 （2 ）： DOI 10. 1145／1132956.1132958.

［13］HAN J，CHENG H，XIN D，et al.Frequent pattern mining：Current status and future directions ［J］.Data Min Knowl Disc，2007，15 （1）：55－86.

［14］PEI Jian，HAN Jiawei，WANG Wei.Constraint－based sequential pattern mining：The pattern－growth methods ［J］.Journal of Intelligent Information Systems，2007，28 （2）：133－160.

［15］KUM H C，CHANG J H，WANG W.Benchmarking the effectiveness of sequential pattern mining methods ［J］.Data and Knowledge Engineering，2007，60 （1）：30－50.

［16］Jessica Lin，Eamonn Keogh，LI Wei，et al.Experiencing SAX：A novel symbolic representation of time series ［J］.Data Mining and Knowledge Discovery，2007，15 （2）：107－144.