基于改进FP算法的隧道交通事故关联分析

刘云翔 韩贝

摘 要： 为了有效地对隧道交通事故进行预测，发现引起隧道交通事故的因素之间的潜在关系，针对隧道交通事故数据的特点，提出改进的FP?Growth算法，对事务与属性赋予权重，从而能够有效地挖掘出隐藏的、更有意义的关联规则。并利用改进后的WFP?Growth算法建立关联规则挖掘模型，通过挖掘采集的数据，找出导致隧道交通事故的频繁因素组合，分析结果找出决策规则。

关键词： 数据挖掘； 关联规则； WFP?Growth算法； 权重； 公路隧道； 交通事故

中图分类号： TN911.1?34； TP312 文献标识码： A 文章编号： 1004?373X（2018）17?0141?04

Abstract： In order to effectively predict the tunnel traffic accident and find the potential relationship between the factors causing the tunnel traffic accidents， an improved FP?Growth algorithm is proposed according to the data characteristic of tunnel traffic accident. The item and attribute are endowed with weight to effectively dig out the hidden and meaningful association rules. The improved WFP?Growth algorithm is used to establish the association rule mining model. The collected data is mined to find the factors combination causing the frequent tunnel traffic accidents， and decision rule by means of the analysis results.

Keywords： data mining； association rule； WFP?Growth algorithm； weight； highway tunnel； traffic accident

0 引 言

现如今，随着我国经济的快速发展，城市的公路隧道建设蓬勃发展，文献[1]指出截至2016年初，全国公路隧道为14 006处、1 268.39万米，公路隧道数量年增长率约为11.5%。随着隧道建设条数的增多，从而引发的交通事故也相应增加[2]。我国对隧道交通事故数据的分析主要是运用数据统计，分析引起隧道交通事故的主要原因。因此，本文采用挖掘关联规则[3]的FP?Growth算法，挖掘引发隧道事故各种属性之间的关联关系。

在频繁模式挖掘FP?Growth算法的挖掘过程中，对数据的度量是事先设定好的最小支持度与最小置信度，若最小支持度与最小置信度设置得过高，会使得频率较低的关键因素丢失，若设置得过低则会挖掘过多无用的关联规则。针对引起交通事故的因素中某些出现频率较低但是至关重要的因素，提出基于权重改进的FP?Growth算法，目的是挖掘出更加可靠的关联规则，可以指导交通部门对预防隧道交通事故采取相应的措施。

1 FP?Growth算法

FP?Growth算法是一种基于频繁模式树[4]的算法，该算法的策略主要分为以下两个步骤：首先，将代表频繁项集的事务数据库压缩到频繁模式树上，减少候选项集的大小，但仍保留项集之间的关联信息；然后，把这种压缩后的数据库划分成一组条件数据库，每个数据库关联一个频繁项，并分别对每个条件数据库进行挖掘。

FP?Growth算法的流程图如图1所示。

基于FP树[5]的关联规则挖掘FP?Growth算法是将挖掘长频繁模式的过程转变成在较小的条件数据库中递归地挖掘一些短的模式，然后加上后綴。这样使用出现次数较低的项作为后缀，增加了选择性，降低了搜索花费时间。

2 基于权重改进的FP?Growth算法

由于FP?Growth算法[6?7]只是根据其各个项出现的频率来确定该项的重要程度，没有考虑到各个项本身的重要性，从而挖掘出来的规则都是些大量无意义的关联规则，所以为了体现事务以及项的重要性，本文提出基于权重（Weight）[8]的WFP?Growth算法。

2.1 WFP?Growth算法思想

2.2 WFP?Growth算法的描述

经过上述描述的权重，对FP?Growth算法进行改进，具体步骤如下：

1） 扫描事务数据库，计算出每个事务以及各个事务中项的权重，即[w（Ii）]和[wt（Tj）]。根据预先设置的最小支持度，得到频繁项集后调整事务数据库。

2） 建立频繁项目头表，再次扫描事务数据库，并根据建立完成的频繁项目头表创建频繁模式树FP树。之后，根据FP树产生条件模式基，产生频繁模式。

3） 根据产生的频繁模式项集，计算每个项集的关键度量作为支持度。满足最小支持度与置信度的项集就是最后挖掘得到的关联规则。

3 改进的FP?Growth算法在公路隧道交通事故中的应用

3.1 数据准备与数据预处理

通过查看公安部交通管理局网站以及相关文献等[9?10]，搜集了1 607起上海13座过江公路隧道交通事故资料。

由于从得到的隧道交通事故的原始数据中无法直接获取有效信息，需要对搜集到的数据进行处理，保留有效的数据字段，将无效的数据删除，以减少每条数据的字段数。另外，对剩下的属性进行预处理，将属性映射为对应的编码，产生新的事故数据库。现有的公路隧道交通事故数据可以分为两大类：一类是量化型数据，一般由连续值来表示，如驾龄，时间等；另一类则是枚举类型数据，如事故发生区段，事故原因，事故形态等。根据不同的数据特点，对数据进行预处理。对于时间这样的量化属性，可以通过离散化来处理。例如，将隧道事故发生的时间分为[T1]：0：00—6：00，[T2]：6：00—9：00，[T3]：9：00—12：00，[T4]：12：00—15：00，[T5]：15：00—17：00，[T6]：17：00—20：00，[T7]：20：00—24：00等7个区间，用1个编码代表1个区间。根据隧道的自身特点，隧道的内外光线差异大，很大地影响到驾驶者的视觉，容易引发交通事故。文献[11]将隧道划分为4个路段进行数据分析。路段S1对应隧道出入口向外的50 m区域，路段S2对应隧道出入口向内50 m区域，路段S3对应隧道出入口向内50～100 m区域，路段S4对应剩余的中间路段。需进行预处理的属性字段还有驾龄、天气、车辆类型、事故原因、事故形态、事故类别等。

驾龄分为：B1，一年以内；B2，1～3年；B3，3～5年；B4，5年以上。

天氣分为：W1，晴；W2，雨；W3，雾。

车辆类型分为：C1，小轿车；C2，大型客车；C3，小型货车；C4，大型货车。

事故原因分为：R1，超速；R2，违章超车；R3，酒驾；R4，道路故障；R5，占道；R6，车辆故障。

事故类型分为：D1，追尾；D2，刮蹭；D3，翻车；D4，碾压；D5，坠车。

事故等级分为：G1，车辆损坏；G2，人员受伤；G3，人员死亡。

3.2 数据挖掘

1） 构建隧道事故的FP树

实验中先设置最小支持度为15%。首先扫描隧道事故事务数据库得到频繁项的集合，计算事务和各个项的权重以及项的关键度量，将项的关键度量作为该项的支持度，之后将频繁项的集合按其支持度递减排序。结果集可标记为[L]。创建树的根节点，以“null”标记，以及频繁项目头表，如表1所示。

再次扫描隧道事故事务数据库，其中每个事务的项按[L]次序处理，并对每个事务建立一个分支。当一个事务需要增加分支时共同前缀上的每个节点的计数增加1，构建出隧道事故的FP树。

2） 根据FP树找出频繁项集

根据隧道事故FP树的频繁项目头表，由长度为1的频繁模式开始，遍历FP树，构造出隧道事故的条件模式基。使用这些产生的条件模式基，构造出频繁模式的条件FP树，其只包含单个路径。然后连接后缀，产生频繁模式的所有组合。

3.3 挖掘关联规则

由于频繁模式产生关联规则需要同时满足设定好的最小支持度与最小置信度。预设最小支持度为15%，最小置信度为40%，得到一些有意义的关联规则表达式。列出每个关联规则的支持度与置信度以便访问，则产生的关联规则如表2所示。

4 实验结果分析

通过分析上述隧道事故挖掘出来的关联规则结果，可以总结出隧道事故发生时其各个属性之间的关联关系。

1） 规则①：超速?汽车损坏（sup=35.93%，conf=78.25%）。

规则⑤：小轿车?超速?人员受伤（sup=17.96%，conf=74.32%）。

规则⑧：超速?时间20：00—24：00?人员受伤（sup=15.56%，conf=41.02%）。

规则①表明，隧道交通事故中发生汽车损害是由超速引起的，该关联规则的置信度达到78.25%。规则⑤表明，驾驶小轿车并且超速行驶引发人员受伤，其置信度为74.32%。规则⑧表明，驾驶者在时间20：00—24：00超速行驶引发人员受伤，其置信度为41.02%。根据这些找到的关联规则，引起隧道交通事故的绝大多数原因为车辆超速所致。而其中小轿车的占有率比较大，发生车祸的时间在夜晚居多，交警人员应多注意对隧道出入口车辆车速进行控制，并在隧道中设置相应的警示牌。在夜晚时分也需要加强车速管理，尽量降低车辆进出隧道时的车速，避免车速过快使得驾驶员没有反应的时间，从而引起车祸的发生。

2） 规则②：违章超车?刮蹭（sup=23.95%，conf=65.46%）。

规则⑦：隧道出入口向内50 m?追尾 （sup=16.16%，conf=45.87%）。

规则②表明驾驶者违章超车引发隧道追尾事故，该关联规则的置信度为65.46%，规则⑦表明在隧道出入口向内50 m处发生汽车追尾事故，其关联规则的置信度为45.87%。这两个关联规则表明在隧道事故中引起追尾事故的主要原因是违章超车，而引发追尾的事故大部分是在隧道出入口向内50 m，由于隧道入口处和出口处光线强度与隧道外的光线强度有反差，容易扰乱驾驶者的视觉，使其看不清道路状况。为了避免这样的情况发生，驾驶员应尽量避免出入口超车。结合具体情况在隧道出入口设置照明灯和遮阳棚，尽可能避免隧道出入口与洞内外的光线强度差异。

3） 规则④： 雾天?追尾?人员受伤（sup=18.56%，conf=81.30%）。

规则⑥：驾龄在一年以内?雨天?车辆损坏（sup=17.36%，conf=40.50%）。

规则④表明车辆在雾天时，发生追尾后，造成人员受伤，其置信度为81.30%。规则⑥表明驾驶者驾驶年龄在一年以内，在雨天发生事故造成车辆损坏，其置信度为40.50%。这两个规则表明雨雾天气时，容易引发交通事故，驾驶员则需要在驾驶时提高注意力。同样，当一些驾驶技能还不够熟练的新手遇到天气不好的情况则更加容易发生交通事故，其中发生车辆刮擦的居多。因此，交通部门应增加驾驶考试的课时，使得新手可以得到足够的时间去练习，以减少事故的发生。

4） 规则③： 晴天?酒驾?人员死亡（sup=19.16%，conf=56.31%）。

该规则表明天晴时，驾驶员醉酒驾车引发交通事故，其置信度为56.31%。根据该规则，交通部门应加强对醉酒驾驶及其他违规驾驶行为的管理，对醉酒驾驶提起高度重视。应加大关于酒驾相关的处罚力度，以减少酒驾引起的交通事故。

5 结 语

本文针对隧道交通事故的特点，以及之前相关研究者的单面性和模糊性，提出WFP?Growth算法，该算法通过权重定义项在事务中的重要性，从而分析隧道交通事故预防措施。实验结果表明，该算法能够挖掘出隧道交通事故发生的时间、路段、驾龄、天气、车辆类型、事故原因、事故类型、事故等级等属性之间的相关性，产生出符合实际情况、更加有意义的关联规则，可以为交通部门预防隧道事故的发生，出台相关政策提供决策支持。

参考文献

[1] 交通运输部.2015年交通运输行业发展统计公报[N].中国交通报，2016?05?05（002）.

Ministry of Transport of the People′s Republic of China. 2015 statistics bulletin of transportation industry [N]. China transport news， 2016?05?05（002）.

[2] 云建平.高速公路隧道群交通事故分布特点及预防对策[J].科技与创新，2016（18）：60.

YUN Jianping. Distribution characteristics and preventive measures of traffic accidents in freeway tunnel group [J]. Technology and innovation， 2016（18）： 60.

[3] 李仕琼.数据挖掘中关联规则挖掘算法的分析研究[J].电子技术与软件工程，2015（4）：200.

LI Shiqiong. Analysis and research of association rules mining algorithm in data mining [J]. Electronic technology and software engineering， 2015（4）： 200.

[4] ALAVI F， HASHEMI S. DFP?SEPSF： a dynamic frequent pattern tree to mine strong emerging patterns in streamwise features [J]. Engineering applications of artificial intelligence， 2015， 37： 54?70.

[5] 石芹芹.基于FP树的极大频繁项集的挖掘方法[J].现代计算机（专业版），2015（36）：7?10.

SHI Qinqin. Mining method of maximal frequent itemsets based on FP tree [J]. Modern computer （professional edition）， 2015（36）： 7?10.

[6] 王艳辉，王淑君，李曼，等.基于改进FP?Growth算法的CRHX型动车组牵引系统关联失效模型研究[J].铁道学报，2016，38（9）：72?80.

WANG Yanhui， WANG Shujun， LI Man， et al. Research on correlative failure model of CRHX EMU traction system based on improved FP?Growth algorithm [J]. Railway journal， 2016， 38（9）： 72?80.

[7] 郑志成，姜昌金.基于FP?Growth的改进算法[J].工业控制计算机，2015，28（5）：105?106.

ZHENG Zhicheng， JIANG Changjin. Improved algorithm based on FP?Growth [J]. Industrial control computers， 2015， 28（5）： 105?106.

[8] 赵远东，方正华.带有权重函数学习因子的粒子群算法[J].计算机应用，2013，33（8）：2265?2268.

ZHAO Yuandong， FANG Zhenghua. Particle swarm optimization algorithm with weight function learning factor [J]. Journal of computer applications， 2013， 33（8）： 2265?2268.

[9] JIAN S Y， WONG Y D. Road traffic accidents in Singapore expressway tunnels [J]. Tunnelling & underground space technology， 2013， 38： 534?541.

[10] AMUNDSEN F H， RANES G. Studies on traffic accidents in Norwegian road tunnels [J]. Tunnelling & underground space technology， 2000， 15（1）： 3?11.

[11] LU L J， LU J， XING Y， et al. Statistical analysis of traffic accidents in Shanghai river crossing tunnels and safety countermeasures [J]. Discrete dynamics in nature & society， 2014（2）： 1?7.