改进的Apriori算法在交通事故分析中的应用_图文

1、邮局订阅号:82-946360元/年技术创新 软件天地PLC 技术应用200例您的论文得到两院院士关注改进的Apriori 算法在交通事故分析中的应用Application of Improved Aproiri Algorithm in Traffic Accident Analysis(北京航空航天大学熊桂喜刘谢XIONG Gui-xi LIU Xie摘要:针对当前交通管理工作中交通事故分析的特点与需求,为了有效地对事故发生时各方面因素关联分析,本文采用一种改进的基于Hash Tree 的Apriori 算法提取交通事故历史数据库中的关联规则,得到导致交通事故各因素的具体特征,发现多方面的

2、深层规律。根据这些规律,交通管理者能制定有针对性的事故预防和管理措施。并对具体应用过程中数据准备过程、数据预处理方法进行了阐述,重点介绍了改进的Apriori 算法的实现。关键词:交通事故分析;关联规则;关联规则发现;Hash Tree;Apriori 中图分类号:TP391.1文献标识码:AAbstract:To effectively perform association analysis of various factors of traffic accident,this paper make use of an improved Aproiri algorithm to mine

3、association rules in the database of traffic accident and find the detail features Deep-seated laws of factors leading to traffic accidents.According to these laws,traffic manager can develop targeted measures for accident prevention and man -agement.And the process of data preparation,data preproce

4、ssing in specific applications are described,highlighting the improved Apriori algorithm.Key words:Traffic Accident Analysis;Association Rules;Association Rules Mining;Hash Tree;Apriori文章编号:1008-0570(201009-1-0205-031引言交通事故分析是交通数据综合分析与预报系统的重要组成部分,主要是分析事故发生的原因,目的在于找出事故的典型形态,发现交通事故发生规律,对交通管理者提供警力配置、事故

5、预防宣传、培训考核等决策支持。交通事故的发生不仅和驾驶员的行为有关,而且与道路环境条件、天气条件、交通状况等有一定的联系,是综合因素共同作用的结果。全面系统地分析交通事故的成因,并用发现的有用知识和规律调整交通安全管理措施、改进道路交通安全设施,已成为交通管理工作的一项重要任务。目前,对于交通事故数据的分析,主要是运用多元统计分析和数据挖掘的相关方法来研究事故成因以及事故多发点段的特征。文献用主成分分析理论对引起道路交通事故的天气、交通违法行为等因素进行分析;文献采用灰色关联分析法,对个主元素的事故指标进行统计分析,从而确定与事故相关的主因素;文献是利用粗糙集的思想对道路交通中的不利因素进行筛

6、选,找到导致交通数据的最大诱因;文献采用模糊聚类法实现道路交通事故成因的聚类分析,找到事故多发的主要原因、诱导原因以及潜在的事故隐患。这些方法都是对于单个影响因素进行分析和评估,没有将事故发生时各方面因素关联起来进行多方面的分析。文献和提出用关联规则发现技术,从人、车、路、环境各方面着手,将各因素关联分析,但是对关联规则发现算法和它在交通事故分析中的具体实现过程没有作详细讨论。2关联规则发现算法发现关联规则的过程可以分解为两个子问题:1.找到所有出现频度大于最小支持度的频繁项目集2.由频繁项目集生成需要的规则,即同时满足最小支持度和最小置信度的强关联规则。支持度和置信度的定义如下:Suppor

7、t(A B=P(A B;支持度揭示了A 和B 同时出现的频率Confidence(A B=P(A |B;置信度则揭示了A 出现时,B 是否一定会出现2.1生成频繁项目集频繁项目集的生成是关联规则发现的关键问题,也是算法时间开销最大的部分。目前已提出大量的发现频繁项集的算法,其中最重要的是R.Agrawal 等人提出的Apriori 算法,该算法是一种发现频繁项集的基本算法。经典的Apriori 算法需要频繁扫描数据库,对于大规模数据而言,开销过大;并且在候选频繁项集Ck 计数中要多次扫描Lk-1,当C k 很大时,效率并不理想。对Apriori 算法的相关改进大多是在这两个方面的工作。文献提出

8、利用Hash Tree 存储候选频繁项集C k ,本文提出一种基于Hash Tree 的Apriori 算法,将在3.2节具体讨论。2.2发现强关联规则在得到频繁项集后,生成强关联规则的步骤是:对每个频繁项集,找到它的所有非空子集,对每个非空子集,可以得到一条强关联规则“”如果的支持度比上的比值大于minconf 。3关联规则发现在交通事故分析中的应用应用关联规则发现技术对交通事故的分析流程如图1所示。本文的目标是充分结合交通管理领域的交通事故数据分析要求,围绕着人、车、路和环境各方面因素,采用关联分析(发现关联规则的方法,对交通事故历史数据库提取关联规则,从中找出熊桂喜:副教授205-技术创

9、新微计算机信息(测控自动化2010年第26卷第9-1期360元/年邮局订阅号:82-946现场总线技术应用200例软件天地可能导致交通事故的相关人员特征、什么情况下的哪些交通违法行为最可能导致交通事故、具有哪些典型特征的路口路段是潜在的交通事故多发点等规律,同时将这些方面的事故诱因组合,更充分揭示导致交通事故的深层规律。图1应用关联规则发现技术对交通事故的分析流程3.1数据准备和数据预处理本文分析的主要数据源为历年的交通事故数据。交通事故数据记录了交通事故发生时,驾驶员、车辆、道路、天气和时间的状态,以及事故本身的特点。本文采用星形模型构筑交通事故多维数据结构。在该结构中,交通事故情况为事实表

10、,存放了6个维表的主码,事实表的每个部分与一个维表的主码相对应,查询时利用这种对应关系,返回查询结果,得到交通事故影响要素集合。形如:男,24,2,工人,私用,摩托车,躲避障碍,窄路,积水,沥青,一般坡,其他城市路,无控制,白天,雨,星期三,12,伤人事故,其他意外,侧面相撞。数据预处理的过程主要有两个阶段:数据清理和格式变换。数据清理主要是检验数据字段的有效值,本文采用SQL 中的CHECK 约束来进行交通事故信息记录集中各字段的有效值检查。以下为CHECH 约束的具体实现。ALTER TABLE TrafficAccidentADD CONSTRAINT chk_TrafficAccide

11、nt CHECK (TrafficAc -cident .age BETWEEN 1AND 80and TrafficAccident.StreetLine in('一般弯','一般坡','急弯','陡坡','一般弯坡','急弯陡坡','一般坡急弯','一般弯陡坡','平直'and 格式变换是为了算法处理的需要,本文采用对数值型数据进行数量离散化,对非数值型数据进行代码标识的方法。如驾龄离散化为JL1:1年及以下,JL2:2年,JL3:3年,JL4:4

12、年,JL 5:5-10年,JL6:10-20年,JL7:20年以上,路面情况按照潮湿、积水、漫水、冰雪、泥泞、翻浆、泛油、坑槽、塌陷、路障、平坦、其他依次标识成代码LQ1-LQ12。最终得到的是面向分析主题的格式化的记录集合。前述的记录格式化为XB2,NL6,JL2,RL4,CS12,JF6,XZ8,LL9,LQ2,LM1,DX2,DL11,JK7,ZM1,TQ1,TW3,TH12,SL2,SY21,SX2。3.2关联规则发现过程生成频繁项目集:本文采用基于Hash Tree 的发现频繁项集的Apriori 算法,算法描述如下:下面对算法中的三个关键步骤:建立Hash Tree 、支持度计数和

13、扫描Hash Tree 得到频繁k-项集进行描述。Hash Tree 相关概念:Hash Tree 是一种多叉的无序树,在层和层之间采用的是Hash 查找的思想。一般采用除余法作为Hash 函数,如:Hash(key=key mod m,其中key 为关键字,m 是分支结点的度。Hash Tree 的详细结构请参见文献。文献提供了两种构建Hash Tree 的方法,具体讨论了候选频繁项插入溢出的解决方法,指出关键在于内部节点的Hash 表的大小m 的取值。本文用L k -1中所包含的不同项的总数作为构建Hash Tree 中Hash 表的大小。在本文的算法实现中,Hash Tree 的结点结构

14、定义如下。建立Hash Tree 算法:算法的相关说明:(1C k 中的候选项集c 中的项均按字典序升序排列。(2用Hash 函数处理时,c 中的每个项是经过预处理的代码标识,如XB2,NL6,JL2,RL4,需先将其转化为整数,为尽可能的减少Hash 冲突,采用如下转换方法:把项中每个字符的ASC 码累加到变量h 上,并在每次累加前把h 的值左移一位,即扩大两倍。(3Hash Tree 的树高与候选项集c 的项目数k 相等,叶子节点的存储阈值基于Hash Tree 的支持度计数算法:表1事故类型为死亡事故的频繁项集扫描Hash Tree 得到L k 的算法也采取同样的思想,这里不再赘述。本文

15、设定minsupport 为100,在1000条交通事故记录集合共得到4个频繁项集L 1、L 2、L 3和L 4。邮局订阅号:82-946360元/年技术创新 软件天地PLC 技术应用200例您的论文得到两院院士关注由频繁项集生成关联规则:如用户想了解造成人员伤亡的重大交通事故的影响因素,可在频繁项集中搜索含有项SL1(死亡事故的项集,得到表1所示的频繁项集。本文设定最小置信度minconf=10%。以频繁4项集XB2,JL1,SY21,SL1为例来说明生成关联规则的过程,由于在这里我们只关心结果为SL1的规则,所以只需用XB2,JL1,SY21,SL1的支持度比上XB2,JL1,SY3的支持

16、度,比值大于10%,作为强关联规则输出XB2,JL21,SY21SL1,支持度为11.3%(1000个样本,113个数据出现了这种情况,置信度为40.2%,这说明驾龄在1年及以下的男性驾驶员出现操作不当而导致交通死亡事故的可能性为40.2%。表2为最终生成的结果为SL1(死亡事故的强关联规则一部分。表2事故类型为死亡事故的强关联规则3.3结果分析与应用本文的目的就是找出人、车、路、环境与交通事故结果间的关联关系,发现各方面因素对交通事故的影响程度。在关联规则分析的过程中,可以对前件为人员信息的关联规则分析,包括性别、年龄、驾龄、人员类型等项进行组合,从中找出可能导致交通事故的相关人员特征,如在

17、3.2节得到的规律:驾龄在1年及以下的男性驾驶员出现操作不当而导致交通死亡事故的可能性为40.2%,得到这些特征从而可以提出有针对性的教育宣传、培训考核等预防方法。根据交通环境和事故原因的组合为前件进行分析,得到天气为晴、照明条件为夜间有路灯照明的情况下超速行驶、不按规定让行等导致的交通事故占很大比例,可以针对这些交通违法行为,提出对应的处理对策。还可以把道路信息属性中的路口路段类型,路面情况,路面类型等属性组合,根据关联规则中发现的具体道路特征,直接根据地理位置信息数据库得到符合条件的路口路段,这些路口路段就是潜在的交通事故多发点。4结论在交通事故分析中,为将事故发生时各方面因素关联起来,本

18、文运用关联规则发现技术来分析人、车、路、环境等多方面因素对事故发生的影响程度,以充分展示导致事故发生的潜在的深层次规律。给出了具体运用过程中的数据准备过程、数据预处理方法,重点介绍了基于Hash Tree 的发现频繁项集的Apri -ori 算法,该算法解决了频繁项集发现过程中效率不高的问题。由于样本数据的随机性和波动性,并不是所有的关联规则都能形成有指导意义的知识,需要交通管理人员和交通领域专家进行甄别和修正。同时,采用统一最小支持度和最小置信度的限制方法也是导致产生大量无意义的关联规则的重要原因,如何增加其他限制和约束来提高关联规则发现的效率,这个问题值得做进一步的研究。本文作者创新点:将

19、关联规则发现技术应用到交通事故分析中来,采用一种改进的基于Hash Tree 的Apriori 算法对交通事故历史数据库提取关联规则,得到导致交通事故的人、车、路、环境各方面影响因素之间的关联关系,为交通管理者制定有针对性的交通事故预防和管理措施提供决策支持。参考文献1许卉莹,包勇强等.道路交通事故数据分析挖掘研究J.中国人民公安大学学报,2008(4:69-732过秀成,盛玉刚.公路交通事故黑点分析技术M.南京:东南大学出版社,2009:253-2623林忠,宇仁德.基于主成分分析理论的交通事故成因研究J.山东交通学院学报,2006,14(1:55-574潘昭宇,过秀成,盛玉刚等.灰色关联分

20、析法在公路交通事故黑点成因分析中的应用J.交通运输工程与信息学报,2008,6(3:96-1015董立岩,刘光远,范淼淼等.数据挖掘技术在交通事故分析中的应用J.吉林大学学报,2006,44(6:951-9556张鹏,张靖,刘玉增等.粗集在交通事故黑点成因分析中的应用J.电子科技大学学报,2007,36(2:267-2707肖慎,过秀成,徐建东.糊聚类法在交通事故黑点成因分析中的应用J.交通运输系统工程与信息,2002,2(8:40-438颜跃进,李舟军,陈火旺.频繁项目集挖掘算法J.计算机科学,2004,31(3:112-1149Jiawei Han,Jian Pei,Yiwen Yin,Runying Mao.Mining Frequent Patterns without Candidate Generation:A Frequent-Pattern T