基于时序关联规则挖掘的交通拥堵预测研究

乔春凯+++赵佳文

摘 要：交通拥堵造成的时间延误和能源浪费给社会带来了巨额的经济损失并严重影响了居民的生活环境，是当前亟需解决的重要问题。现有的交通拥堵预测方法并没有考虑到交通流量的时序性，因而不能很好地适应复杂的交通情况。针对这一背景，提出了一种基于遗传算法的时序关联规则挖掘的方法，并通过对挖掘出的时序关联规则进行分类来预测交通拥堵。实验结果表明，本方法能够准确有效地对交通拥堵事件进行预测，能够很好地适用于复杂的交通拥堵状况。

关键词：关联规则；交通拥堵预测；遗传算法；数据挖掘

引言

目前，城市交通拥堵已经成为我国各大中城市正在面临的通病，因其造成的时间延误和能源浪费已给社会带来了巨大的经济损失，对复杂的交通状况进行预测是当前亟需解决的重要难题。常见的预测交通拥堵的方法主要是基于各类数学模型并且大多只对单个时刻进行预测，由于交通系统复杂多变的特性，这类方法往往考虑到的参数并不全面，同时没有考虑到交通拥堵状况的时序性。

近年来，许多人开始致力于智能交通系统的研究，提出多种交通拥堵预测方法。文献[1]中，使用了多元线性回归模型，其具有实现起来容易且理论基础成熟等优点，但是该模型对不同交通状况的适应度较差。文献[2]中，Fahmy M.F.和Ranasinghe D.N.等人提出了一种使用排队模型从而对交通状态进行判别的算法。文献[3]通过人工神经网络模型进行交通拥堵预测，这种方法具有很强的学习能力，但对数据量的需求过于庞大，当交通系统数据不足时，预测结果不尽如人意。文献[4]采用了ARIMA模型，能够较好地体现出交通流量的非线性特征，但当系统中出现交通事故等突发性事件时，会使模型运算效率降低。

在实际的交通系统中，各个路段发生拥堵往往遵循一定因果关系，同时考虑到交通拥堵的时序性，提出一种基于遗传算法的时序关联规则挖掘的方法，挖掘出各个路段发生拥堵事件的潜在的规律，并通过将挖掘出的关联规则进行分类，以达到预测交通拥堵的目的，为提升交通系统整体性能提供前提保证。

1 问题分析

拥堵等级划分（一）：

在实际路网中，道路的车辆密度是评价该条路的拥堵等级的重要参数。车辆密度由道路长度，平均车长，平均车间距，车道数以及车辆总数等参数共同决定。

车辆密度计算公式如下：

公式（1）中，D为车辆密度，N为当前道路上的车辆总数，l和s分别为平均车长与平均车间距，L为当前道路的长度，n为当前道路的车道数。

根据道路的车辆密度，本文将拥堵等级划为三个等级，1级为通畅，2级为轻微拥堵，3级为严重拥堵，拥堵等级及密度阈值见表1。

2 时序关联规则挖掘

2.1 关联规则

关联规则就是在一个数据集中发现不同事务彼此之间的相关性，其两个最重要的约束参数，一个是支持度（Support），表示规则出现的频率程度，另一个是置信度（Confidence），表示规则可靠性的程度。本课题中关联规则如下所示：

可解读为，当满足道路1五分钟前轻微拥堵，以及道路2当前时刻通畅的情况时，那么道路3在五分钟后会发生严重拥堵。

2.2 遗传算法

為了适应交通系统的高度复杂性和各种突发事件，传统的利用数学模型的交通拥堵预测算法的实施困难性很大，而且难以加入时序关系，而交通拥堵事件的时序性又是有必要考虑的，所以本课题设计了一种利用遗传算法来挖掘时序关联规则的方法。

2.2.1 编码

如图1所示，遗传算法的每个染色体由上下两层结构组成，其中上层为道路的拥堵程度，取值为1～3，分别对应三个等级，下层为引入属性type，type取值为0～2，代表其上层拥堵程度的类型，type为1和2的个数为定值，染色体的长度与路网中道路的个数相对应。

2.2.2 解码

规定解码出的规则的前提有且最多有三个，规则的结论有且只有一个，若染色体type=1的个数为a，type=2的个数为b，当规则未添加时序时，每个染色体可解码出的规则数为（A3a+A2a+A1a）*A1b条，当规则添加时序时，规定规则取三个时刻，分别为t1，t2，t3，相邻两间隔相差300秒，t2为当前时刻，前提可为t1或t2时刻，结论只能为t3时刻，则每个染色体可解码出的规则数为（A3a*8+A2a*4+A1a*2）*A1b条。

2.2.3 交叉

若两个父染色体的第i 位上层属性分别为Lix，Liy，子染色体的第i位上层属性为Liz，当进行交叉操作时，子染色体的每一位的Liz，由随机从对应的Lix和Liy中选择一个遗传而来。

若每个染色体下层属性为2和1的个数分别为x个和y个，记录两个父染色体所有下层属性为2的位置，则子染色体下层属性在这些位置中随机选择x个设置为2，记录两个父染色体所有下层属性为1的位置，若子染色体下层属性已经设置为2，则排除该位置，子染色体下层属性在其余位置中随机选择y个设置为1，其余位置都为0，以确保子染色体与父染色体下层不同类型属性个数分别相同。

2.2.4 变异

染色体在发生突变时，上层属性的每一位会变化成其它拥堵程度，例如2会变成1或3，而不会停留在2。

若父染色体下层属性为2和1的个数分别为x个和y个，记录父染色体下层属性为2和1 的位置，则子染色体在这些位置之外，随机选取x位突变为2，随机选取y位突变为1，其余位置都为0，以确保子染色体与父染色体下层不同类型属性个数分别相同。变异操作如图3所示：

2.2.5 选择

通过Fitness函数，对种群中每个染色体进行评价，在每轮进化过程中利用轮盘赌方法选择出新的子代，该轮子代作为下一轮进化的父代，这样持续进化下去。Fitness函数如下所示：

其中，r为挖掘出的规则，R为染色体挖掘出的所有规则的集合，x2（r）为规则r的卡方值，recov为规则新颖程度，如果该规则是一条新规则，则给recov设置一个值，否则recov为0。卡方值可以表达数据样本实际值与理论值的偏差程度，即两个事务相关联的程度，利用卡方值可以很好的评价规则的质量。卡方值越高则说明该规则的前提和结论关联程度越过。

3 分类预测

将已挖掘出的关联规则按结论拥堵程度分成3类，分别为1，2，3，即通畅，轻微拥堵，严重拥堵。分类时并非只用置信度高的规则，而是利用与待分类数据匹配成功的规则进行计算，则分类过程如下所示：

3.1 获取Rk

获取交通数据之后，分别与每一类里的所有规则的前提进行匹配，Rk为匹配成功的规则的集合。

3.2 计算每一类的Creditk

其中，Confidencer是规则r的置信度，Creditk是在类别k中，所有匹配成功的规则的置信度的和。

3.3 计算每一类的Scorek

其中，Totalk是类别中包含的规则的数量，Scorek是计算出的评价值。

3.4 分类

在得到每一类的Scorek后，则认为分类结果就是Scorek值最高的那一类。

4 仿真实验及结果分析

实验环境：

样本数据收集工作来源于开源软件SUMO仿真器，使用Java语言以及MySQL数据库进行程序开发。

获取道路的车辆拥堵程度之后，采用本文提出的方法进行时序关联规则挖掘。其中，每个种群包含10个染色体，遗传算法中染色体的交叉率和变异率分别为80%和90%，设置的支持度阈值为5%，置信度阈值为60%，另外，评价每条规则过程中，如果该条规则为新规则，则设置recov为0.2。由于计算能力限制，实验设置每个染色体下层属性有5位可以作为前提，有3位可以作为结论，在进化过程中不断将满足条件的规则保存下来获取满足支持度和置信度的时序关联规则之后，使用本文的方法进行分类以达到预测的目的，最终使用获得的规则中最后100条规则作为测试集，其余规则作为训练集的方式来对预测结果做出评价。表2分别记录五次实验下获取的规则数量以及预测正确率。

从上述结果来看，当前预测准确率平均值达到85.2%，当规则个数较少时的准确率与规则个数多时的准确率有较大差距，分析其原因，可能是由于構建分类器的样本个数少，分类器构建不够完善的原因。第五次实验预测正确率相较第四次有所下降，分析其原因，可能是由于该次实验染色体进化所得的规则普遍置信度较低的原因。由此也说明挖掘通过挖掘时序关联规则时，应注重挖掘置信度高的质量好的规则，而不能仅仅关注规则的数量。

5 结束语

依据遗传算法的进化原理，并考虑在复杂多变的交通环境下，交通拥堵事件发生的时序关系，本文提出了一种基于时序关联规则挖掘的交通拥堵预测方法。经实验仿真证明，该方法准确有效。

同时在研究过程中也面临一些问题，当路网中道路个数过多时，本方法会面临计算能力不足，计算耗时过长的问题。这需要后续提出更好的路网划分方法以及采用MapReduce等大数据环境下的计算方法来加以解决。

参考文献

[1]Rice J， Van Zwet E. A simple and effective method for predicting travel times on freeways[J]. Intelligent Transportation Systems IEEE Transactions on， 2004，5（3）：200-207.

[2]Fahmy M F， Ranasinghe D N. Discovering automobile congestion and volume using vanet's[C]// ITS Telecommunications， 2008. ITST 2008. 8th International Conference on. IEEE， 2008：367-372.

[3]DOUGHERTY M S， KIRBYHR， BOYLE R D. The use of neural networks to recognize and predict traffic congestion[J]. Traffic Engineering and Control，1993，34（6）：311-314.

[4]HORVITZE J， APACIBLE J， SARIN R， et al. Prediction，expectation， and surprise： Methods， designs， and study of a deployed traffic forecasting service[C]//Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence. Edinburgh： [s.n.]， 2005：275-283.

[5]Zhou H. Data mining and classification for traffic systems using genetic network programming[J]. Genetic Programming，2011.

[6]Martí， Nez-Ballesteros M， Martí， et al. An evolutionary algorithm to discover quantitative association rules in multidimensional time series[J]. Soft Computing， 2011，15（10）：2065-2084.

作者简介：乔春凯（1992-），男，汉族，辽宁省瓦房店市，硕士，单位：沈阳理工大学，信息科学与工程学院，研究方向：数据库理论与信息系统。

赵佳文（1991-），男，满族，吉林省蛟河市，硕士，单位：沈阳理工大学，信息科学与工程学院，研究方向：数据库理论与信息系统。