数据挖掘在交通事故预防中的应用研究

1、毕业设计（论文）题目 数据挖掘在交通事故预防中的应用研究专业信息与计算科学班级1班学生蔡文龙指导教师韩逢庆重庆交通大学2010 年目 录摘 要 .IABSTRACT .II前 言 .III第 1 章 交通事故预防形势严峻 .11.1交通事故预防形势不容乐观 .11.1.1背景 .11.1.22009年全国交通事故概述 .11.2目前国内国外事故分析情况 .21.2.1国内事故分析情况 .21.2.2国外事故分析情况 .2第 2 章 数据挖掘 .32.1数据挖掘技术 .32.1.1数据挖掘概念 .32.1.2数据挖掘方法 .32.1.3数据挖掘应用 .32.2关联规则 .52.2.1背景 .52

2、.2.2支持度 .52.2.3置信度 .52.3算法 .72.3.1Apriori 算法描述 .72.3.2改进的 Apriori 算法 .82.3.3 FP-GROWTH 算法 .9第 3 章 交通事故数据准备和整理 .113.1数据准备 .113.1.1需求理解 .113.1.2数据准备 .113.2数据整理和转换 .123.2.1数据整理 .123.2.2数据转换 .14第 4 章 交通事故的数据挖掘分析 .174.1事故数据预处理 .174.2结果讨论 .19结 论 .20论文小结 .21致 谢 .22参考文献 .232010 届信息与计算科学专业毕业设计（论文）摘 要城市机动车数量的

3、增加已经导致城市交通事故的频繁发生，能否对已发生事故做出正确的分析将直接影响到能否对未来类似事故的成功避免。随着社会的发展，道路交通事故系统的复杂性也在逐渐增强，传统的分析、预防方法已呈现其局限性。现提出一种使用数据挖掘领域中的多维关联规则技术分析大量交通事故记录的方法，通过找出可能导致交通事故发生的频繁因素组合来发现某些事故发生的规律，以期为道路安全管理提供科学的决策依据。通过该方法，我们可以有效地识别和发现事故数据的新模式，且能为交通管理决策提供有效支持，该方法易于实现，便于推广。关键词：交通事故，数据挖掘，关联规则，交通事故预防I蔡文龙：数据挖掘在交通事故预防中的应用研究ABSTRACT

4、Increase in the number of urban motor vehicles has led to frequent traffic accidents the city, whether the accident had occurred to make the right analysis will directly affect the ability to succeed in the future to avoid similar incidents. With the development of society, the complexity of road tr

5、affic systems are gradually increased, the traditional analysis, prevention, has presented its limitations. Now presents a use of data mining association rules in the multidimensional analysis the method of traffic accident records, could lead to traffic accidents by identifying the frequent combina

6、tion of factors to find that some of the laws of the accident, for road safety management in order to provide scientific basis for decision making. Using this method, we can effectively identify and find a new model of accident data, and can provide effective decision-making for traffic management s

7、upport, the method is easy to implement, easy to promote.KEY WORDS: Data mining, association rules, traffic accident preventionII2010 届信息与计算科学专业毕业设计（论文）前 言长期以来，道路交通事故甚至特大恶性交通事故时有发生，对人们的生命财产安全构成了严重威胁。交通事故带来的严重后果和给整个社会造成的负面影响远远超过了事故本身。道路的交通安全问题正日益引起世界各国的高度重视，并成为建设现代化交通运输中急需解决的一个重要问题。因此，如何从以往大量的交通事故数据中

8、发现问题，分析事故的原因，以便于有关部门采取相应的对策，从而减少交通事故发生的概率将变得尤为重要。交通事故的发生既有其特定的、偶然的原因，又受各种其他因素的支配。传统的交通事故分析大多使用数理统计方法，统计事故发生概率、分析事故发生原因，以此为基础建立数学模型，评估道路安全性能。但交通事故数据具有多维、稀疏、不全等特点，用此类方法并不能收到良好的效果。而为了克服事故数据库中多维、稀疏、不全等因素的不利影响、有效地识别和发现事故数据的新模式及其内在规律，有必要引进一种新的交通事故分析方法。数据挖掘是一项从大量的记录数据中提取有价值信息的技术，这些被提取出的信息可以帮助相关人员认清当前的交通状况并

9、制定相应对策。数据挖掘中的多维关联规则相对数理统计方法更适合于事故诱因分析，它不但可以有效地简化并处理事故记录数据，还可以推导出一些有用的规则表达式，以充分展示事故发生的客观因素对事故发生的影响程度，是当前数据分析的一种先进手段。本文就事故发生时的各种因素（内在联系）对事故发生所产生的影响，借助数据挖掘领域中的多维关联规则技术对交通事故记录进行分析，通过清理大量初始记录行数据，并根据交通事故诱因特点提炼出与发生事故有联系的记录字段数据，组成新的事故记录表；从表中找出诱因记录字段值和事故结果字段值组成的频繁字段组合；最后通过预先给定的支持度和置信度来衡量该频繁字段组合是否能推导出事故关联规则。如

10、果能够从大量的交通事故的诱因中发现它们之间联系的内在规律，进行人为控制和干预，使事故发生条件缺失，就可以减少交通事故的发生概率。III2010 届信息与计算科学专业毕业设计（论文）第 1 章 交通事故预防形势严峻1.1 交通事故预防形势不容乐观1.1.1背景近年来，随着中国现代化进程的不断加快，汽车消费越来越多地走进了普通家庭的生活。但随着车辆和驾驶人员数量的高速增长，道路里程的延伸，道路交通压力大大增加，道路交通安全形势复杂，交通事故有愈演愈烈的趋势。1.1.2 2009年全国交通事故概述分析 2009 年全国道路交通事故情况， 主要有以下特点： 一是超速行驶、 酒后驾驶、疲劳驾驶等严重交通

11、违法行为导致的死亡人数降幅明显，同比分别下降 10.1%、13%和15.2%。 8 月 15 日开展严厉整治酒后驾驶违法行为专项行动以来，全国因酒后驾驶肇事导致人数同比下降 39.6%。二是国省道发生事故导致的死亡人数同比下降9.8%，高速公路平均百公里发生事故造成的死亡人数下降10%。三是恶劣天气导致的事故死亡人数同比增加，特别是下半年全国雨、雪、雾等恶劣天气条件下发生道路交通事故导致的死亡人数同比上升13.3%。从全国各片区情况看，西北片区恶劣天气发生事故导致的死亡人数同比增幅最大，上升22.9%，东北、华东和华北片区分别增加8.9%、8.2%和 3.1%。四是摩托车肇事导致死亡人数波动上

12、升。自3 月份以来，摩托车肇事导致的死亡人数呈逐月波动上升，无证驾驶、未按规定让行、超速行驶是摩托车肇事的主要原因，导致的死亡人数分别占摩托车肇事死亡人数的25.1%、11.7%和 8.1%。五是营运车辆肇事导致一次死亡10 人以上特大道路交通事故比例上升。共 19 起，占同类事故总量的79.2%，同比增加 3.3 个百分点。营运车辆肇事导致一次死亡10 人以上特大道路交通事故中，8 起为驾驶人超速行驶导致，占42.1%；14 起发生在国省道，占 73.7%，同比增长 7.7 个百分点； 8 起事故中肇事客运车辆的营运距离小于400公里，占 42.1%，同比增加 3.2 个百分点。营运车辆肇事

13、比例居高不下，主要是个别运输企业对从业驾驶人员录用把关不严；少数运输企业违法挂靠经营，给明显不符合国家相关标准的营运车辆安全发放二级维护合格证；部分运输企业不履行对驾驶人的安全教育和管理职责；一些地方运输管理机构不对隐患整改不力的企业追究相关责任。1蔡文龙：数据挖掘在交通事故预防中的应用研究1.2 目前国内国外事故分析情况1.2.1国内事故分析情况目前，对于事故数据的分析国内主要是政府机关行为。我国每年由公安部交通管理局组织发布中国道路交通事故统计年报，从交通事故总体分析、历年交通事故情况、当年交通事故情况、相关基础资料、特大道路交通事故案例几个方而，公布交通安全的相关统计数据。对道路交通事故

14、数据的统计分析，主要是针对交通事故的宏观形势进行统计分析，包括事故次数、死亡人数、受伤人数、自接财产损失等四项指数的统计分析，还包括时间分布、事故原因、责任者情况、伤亡人员情况、道路情况、特大事故统计分析等。在一些科研院所，也有一些学者运用数学分析方法研究事故成因以及对具体路段交通事故特征的分析等。针对某些特定道路的特点进行分析，探讨道路交通事故发生的深层次原因，并对我国道路交通事故未来发展趋势进行了一些预测研究。但目前对事故的分析尚处于原始事故数据统计的层面上，对事故原因进行的分析主要是四项指数的分析，对数据进行简单处理，无法经由数据分析来发现并充分利用数据中存在的关系，也无法深层次挖掘事故

15、发生的原因及机理。1.2.2国外事故分析情况美国、加拿大、日本等发达国家对交通安全研究工作非常重视，这些国家有专门的交通安全研究机构， 专门负责事故调查与分析统计, 并运用先进的数据挖掘技术进行分析，普遍建立了道路交通事故分析、预防和评估预警技术体系。在基础数据统计方面，一些发达国家交通事故统计数据采集全面翔实，历年统计数据齐全，统计报表以多维数据项为主，除基本的事故次数、死亡人数和受伤人数等统计项外，更加注重与道路交通安全直接相关因素数据的统计，交通安全相对指标数据较为丰富，可以较好地客观评价道路交通安全整体发展态势，且交通安全综合评价指标较为全面。美国死亡事故的数据采集项目多达100 余条

16、，涵盖与交通事故有关的驾驶人、车辆、道路、管理、医疗等各个方面。日本成立了专门的道路交通事故分析研究机构对交通事故进行翔实的分析研究，每年发布的交通安全白皮书对交通事故的基本数据、发展趋势以及应对措施的效果进行评价分析，指导政府及时调整交通管理对策。22010 届信息与计算科学专业毕业设计（论文）第 2章数据挖掘2.1 数据挖掘技术2.1.1数据挖掘概念数据挖掘 1 是通过仔细分析大量数据来揭示有意义的新的关系、趋势和模式的过程。其出现于20 世纪 80 年代后期，是数据库研究中一个很有应用价值的新领域，是一门交叉性学科，融合了人工智能、数据库技术、模式识别、机器学习、统计学和数据可视化等多个

17、领域的理论和技术。数据挖掘技术简单地说，数据挖掘是从大量数据中提取或“挖掘”知识。通常把它视为另一个常用的术语数据库中的知识发现或KDD (knowledge discovery indatabase) 的同义词。数据挖掘是识别数据的新的模式和发现数据反映的事物内在规律的过程。模式即描述数据集的某个子集的一个表达式。它是数据库技术、人工智能、机器学习和统计学等学科相结合的产物，并最先从商业和企业中发展起来。由于大量数据的出现，其中蕴含着许多可以利用的规律，人们迫切希望使用各种技术，从中挖掘出具有价值的规律来，数据挖掘技术就是可以用来挖掘这些规律的一种有效工具。其已在金融投资、信用评估、网络管理

18、、销售等多个领域得到令人满意的应用。最经典的数据挖掘的例了就是 :90%的顾客在购买面包和黄油的同时也会购买牛奶。此外它的优点还体现在从更高的层次对数据进行泛化，比如将上例抽象为食品等。2.1.2数据挖掘方法数据挖掘方法 2 结合了数据库技术、 机器学习、统计学等领域的知识， 从深层次挖掘有效的模式。常见方法有关联规则、决策树、神经网络、粗糙集法、分类、聚类方法、遗传算法和统计分析方法等，数据挖掘技术具有广泛的应用前景。2.1.3数据挖掘应用数据挖掘技术最初就是面向应用的，尤其是在银行、电信、保险、交通、零售(如超级市场 )等商业领域。数据挖掘所能解决的典型商业问题有：客户关系管理、数据库营销

19、、客户群体划分、交叉销售等市场分析行为，以及客户流失性分析、客户信用记分及欺诈发现等等。加拿大Simon Fraser大学 KDD 研究组根据加拿大BC 省电话公司拥有的十多年的客户数据，总结、分析并提出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策；美国职业篮球联赛（NBA ）教练，利用 IBM 公司提3蔡文龙：数据挖掘在交通事故预防中的应用研究供的数据挖掘工具 Advanced Scout临场决定替换队员；美国 Firstar 银行使用 Marksman 数据挖掘工具，根据客户的消费模式预测何时为客户提供何种产品； 还有不少 DM/KDD 产品用来筛选 Internet 上

20、的新闻，保护用户不受无聊电子邮件和商业推销的干扰。 另外数据挖掘在生物学以及工业领域也有很广泛的应用。42010 届信息与计算科学专业毕业设计（论文）2.2 关联规则2.2.1背景关联规则 3 的发现是数据挖掘技术中最成功和最重要的一项任务，它的目的是发现数据集中的所有的频繁模式。一个大型的数据库，其各个字段之间存在着各种各样的关系，这些关系就隐含在数据库所包含的数据中，关联规则挖掘的目的就是要找出这些隐含的关系。 数据挖掘中的多维关联规则相对数理统计方法更适合于事故诱因分析，它不但可以有效的简化并处理事故记录数据，还可以推导出一些有用的规则表达式，以充分展示事故发生的各客观因素对事故发生的影

21、响程度，是当前数据分析的先进手段。2.2.2支持度关联规则所表述的是一种关联关系，并且这种关联关系是在一定概率约束下才有意义的。拿开始的A B 例子来说，如果A,B 这一事件组合在总事务记录中出现概率过低，低于预先给定的临界值，则说明这一事件组合发生的次数太少，少到我们没有必要关注它的程度。相反，如果这一事件组合的出现概率高于预先给定的临界值，说明这个模式具有一定程度的普遍意义，我们发现并进一步研究它是有价值的。称以上的这个概率为“支持度” 。2.2.3置信度在进一步研究 A B 这一模式的过程中， 有必要考虑另一个概率约束， 称为“置信度”。考虑到即使 A,B 这一事件组合发生频繁， 但如果

22、这一事件组合的发生次数比上A 事件的所有发生次数的值过低，低于预先给定的临界值的话，说明A 的发生不足以导致 B 的发生。使用以上例子做进一步阐述:假设平均在 100 条事故记录中都存在“路滑”这一因素，而平均来说，在相应的100 条事故记录中只有一条存在“撞车”这一结果，这时， A 事件的发生导致B 事件发生的概率平均来说只有1%，这不足以支撑 A能推导出 B 这一结果。2.2.4频繁项集设 I = i1, i2 ,.,i n 是项的集合。设任务相关的数据D 是数据库事务的集合，其中每个事务 T 是项的集合，使得 TI 。每一个事务有一个标识符，称作TD。设 A 是一个项集，事务 T 包含

23、A 当且仅当 AT。关联规则是形如的蕴涵式，其中 A I,BA=BI ，并且 A B= 。规则 A=B在事务集 D 中成立，具有支持度 s，其中 s 是 D中事务包含 AUB ( 即 A 和 B 二者 ) 的百分比。它是概率 P(A U B) 。规则 A=B在事务集 D中具有置信度 c, 如果 D 中包含 A 的事务同时也包含 B 的白分比是 c, 这是条件概率 P(B| A)。5蔡文龙：数据挖掘在交通事故预防中的应用研究即是support(A=B)=P(A U B)(2.1)confidence (A=B)=P(B|A)(2.2)同时满足最小支持度( m in _ sup)和最小置信度 (m

24、 in_conf)的规则称作强关联规则。由以上描述可知，A 和 B 都是项的集合，称为项集。包含k 个项的项集称为k-项集。项集的支持度计数是指 D 中包含该项集的事务数，如果项集的支持度计数不小于 m in_ sup 与 D 中事务总数的乘积，则其为频繁项集。2.2.5关联规则挖掘步骤关联规则的挖掘分解为两步:第一步找出所有频繁项集；首先找出频繁1- 项集，然后利用频繁1- 项集来挖掘频繁 2- 项集，不断如此循环下去直到无法发现更多的频繁k- 项集为止。第二步由频繁项集产生强关联规则 : 关联规则的发现问题实质上是在满足于最小支持度的项集中，找出满足于最小置信度的相关联的规则。62010

25、届信息与计算科学专业毕业设计（论文）2.3 算法2.3.1 Apriori算法描述Apriori算法 4-7是关联规则挖掘中的经典算法，是一种具有影响力的挖掘布尔关联规则频繁项集的算法。关联规则挖掘整个执行过程的第一步是核心，当找到所有频繁项目集后，相应的关联规则就很容易产生。 Apriori算法就是用于发现频繁项目集的。它的循环过程是 : 第 k 步中，根据第k-1 步生成的 (k-1) 维最大项目集产生k 维候选项目集，然后对数据库进行搜索，得到候选项目集的项集支持度，与最小支持度比较，从而找到 k 维最大项目集。为方便下文的叙述，作如下约定:T1D 表示相应事务的标识符， item 表示

26、项目名称， K-items 表示 K 维项集， L k 是具有最小支持度的最大K 维项集， Ck 是候选项集， Apriori 算法描述如下 :(1)C1 =candidate1-itemsets;(2)L1 =cC1 |c.count minsupport;(3)For(k=2, Lk -1 ,k+)/直到不能再生成最大项目集为止(4)Ck ,=apriori_gen() (Lk 1 ); 知道生成含 k 个元素的侯选项目集(5)for all transactions tD(6)Ct =Subset(C k ,t); /事务 t 中包含的侯选项目集(7)for all candidates

27、 cCt(8) c.count=c.count+1;(9) next(10)Lk =c C k |c.countminsupport;(11)next(12)resultset=resultsetL k ,其中， resultset表示所有最大项目集， apriori_gen() 函数的参数为L k -1 ，即 :所有最大 k-1 维项目集，结果返回含有k 个项目的候选项目集 Ck 。该函数通过两步实现上述功能：首先在连接 (join)步，对 L k-1 自连接生成 Ck 。用 SQL语言表示为 :insert into Ck ,selectP.item1 ,P.item 2 , ,P.ite

28、mk 1 ,Q.itemk 1from L k-1 P, L k-1 QwhereP.item 1 =Q.item 1 , ,P.itemk 2 ,=Q.itemk 2 ,P.item k 1 Q.item k 1然后是修剪 (prune) 步，即对任意的 c,c Ck ，删 Ck 中所有那些 (k-1)维子集不在7蔡文龙：数据挖掘在交通事故预防中的应用研究L k 1 中的项目集，得到候选项目集Ck 表述为 :for all itemset cCkfor all (k-1)维子集 s of cif (s 不属于 L k 1 )then delete c from Ck在 Apriori 算法中

29、， Ck 中的每个元素需在交易数据库中进行白验证来决定其是否加入 L k 。这里的验证过程要求多次扫描可能很大的数据库，即如果频繁项集最多包含10 个项，那么就需要扫描交易数据库10 遍，这需要很大的I/O 负载。虽然修剪步骤可以降低计算所有的候选集的支持度的代价，但需要多次扫描数据库，候选项目集合Ck是以指数速度增长的， L k 自连接会产生大量的候选k- 项目集，随着数据库的记录的增加，扫描的次数将呈现出几何级数的增加。这是Apriori方法的缺陷。要提高算法效率，关键是尽可能减小候选集的数量。2.3.2改进的 Apriori算法在扫描数据库的过程中，有些项目或事务是不必多次扫描的，如果能

30、避免这些不必要的扫描，则可以提高Apriori算法的效率。若在每次生成候选项集之后，删除其中没有用的项集，可以大大减少下一步接连生成的项集数量，从而减少数据库扫描次数，节省算法过程所需的存储空间，减少运算时间。可以根据Apriori以下的一个性质对算法进行改进 : 某元素要成为 K 维项目集的一元素的话， 该元素在 k-1 阶频繁项目集中的计数次数必须达到k-1 个，否则不能生成k 维项目集。改进后算法沿用逐层迭代的方法由候选项直接生成频繁项集。我们约定：L k 是长度为k 的大项目集， Ck 1 是长度为 k+l的候选项目集， Tk 是与 Ck 相对应的原数据库 D的子集，改进的算法可描述如

31、下 :(1) L1=large1-itemset;(2) T1=D;(3) for(k=1;L; k+);(4)Ck1 =apriori_gen() (L k );/ 对 L k 执行函数 apriori-gen(Lk ) ，生成候选项目集 Ck 1 ;(5) for all transactions tT k do begin;(6)C t =Subset(L k,t);/对 Tk 中每一交易 t ，求 t 包含的 Lk 中的项目个数(7)t.count=| Ct|;/记为 t.count(8)if(t.countk+1)Tk 1 =Tk -;/不小于 k+1的 t.count值对应的 t组

32、成的集合构成参照数据集 Tk 1 ，即如果 t.countmin sup;(16)end;(17)Answer=U k L k2.3.3 FP-GROWTH算法FP-Growth(Frequent一 PatternGrowth，频繁模式增长 ) 算法 8 是一种不产生候选项集的挖掘频繁模式的算法。它的基木思想是：首先将数据库中的所有频繁项集压缩到一颗频繁模式树 (FP-Tree) ，但仍保留项集关联信息，然后将FP-Tree 分成一组条件数据库，每个库和一个长度为1 的频集相关，最后对每个条件数据库进行挖掘。FP-Growth 算法的操作步骤如下：（1）频繁 1 项集排序：首先对数据库 D进行

33、扫描，得到频繁 1 项集和每个频繁项集的支持度，然后根据频繁项集的支持度对频繁 1 项集进行降序排列 . 得到结果集 L。（2）构造 FP-treeFP-tree 定义如卜：a. 它由一棵以标记为null的根节点和一系列代表频繁项的节点构成的树，以及一个频繁项头表组成。b. 除根节点外，树中的每个节点包含三个域：项名 (item_name) ，计数 (count) ，以及节点链 (node_ink) 其中，项名是指该节点所代表的项 ; 计数用于记录经过此节点的事务的数目；节点链指向具有相同项名的下一个节点，如果没有下一个节点就为空c. 在频繁项头表中的每一个条目由两个域组成，即项名(item_

34、name) 和节点链头(head of node_link)，其中节点链头指向FP 树中具有相同项名的节点链中第一个节点。（3）挖掘 FP-tree 得到频繁项集的方法：由每个长度为 1 的频繁模式 ( 初始后缀模式 ) 开始。构造它的条件模式基 （一个“子数据库”，由 FP-tree中与后缀模式一起出现的前缀路径集组成），然后构造它的 ( 条件)FP-tree ，并递归地对该树进行挖掘。模式增长通过后缀模式与条件FP-tree产生的频繁模式连接实现。9蔡文龙：数据挖掘在交通事故预防中的应用研究当找出数据库D 中的所有频繁项集后，就可以从它们中产生关联规则。对于给定的一个交易集D，挖掘关联规则

35、问题就是产生支持度和置信度分别大于最小支持度(minsupp) 和最小置信度（ minconf ）的关联规则。支持度可以用式（ 2.3 ）表示：support(X, Y)support _ cont ( X , Y)(2.3)D其中 X 和 Y 分别表示数据库中两个项， sup port_count ( X,Y )表示包含项集 X和 Y 的事务数， D 表示数据库中的事务总数。对于置信度，可以用式（2.4 ）表示：confidence (XY)sup port _ cont ( X ,Y )(2.4)sup port _( X )其中， sup port_count ( X )是包含项集 X

36、的事务数。根据支持度和置信度，可以产生如下关联规则：对于每个频繁项集 l，产生 l 的所有非空子集。对于 l 的每个非 空子集 s ，如果 supp o r t c o n(tl)min c o n f ，则 可输出supp o r t (s)“ s(ls) ”。其中 minconf 是最小置信度值。102010 届信息与计算科学专业毕业设计（论文）第 3 章 交通事故数据准备和整理3.1 数据准备3.1.1需求理解涉及到交通管理信息积累的原始数据很多，存在于不同的数据库中，甚至有些与交通安全相关的某些数据跨行业保存在其他行业的数据库中，如气象部门记录的天气气象数据。这些数据库大多是事务性的数据库，其中的数据各自独立、互不相关。数据挖掘的主题是从这些互不相关的数据中寻找出与交通事故相关的信息，导致交通事故发生的各种因素以及交通事故对各种因素的概率分布。3.1.2数据准备任何交通事故的发生都有一定的主观和