应用数据挖掘的apriori关联规则技术分析.doc

应用数据挖掘的apriori关联规则技术分析交通事故唐丰飞 （1.北京交通大学软件学院 北京 100044） E-mail:摘要：随着我国道路交通事业的飞速发展，交通事故发生率呈上升趋势。由于交通事故的发生不仅造成大量人员伤亡，给无数家庭带来不幸，而且严重影响着经济发展和社会稳定，已引起了各级政府的高度重视和关注。人们在认为交通事故的发生具有一定规律性，而造成事故的原因又具有复杂性和多样性，本文根据数据挖掘技术中的关联规则理论，利用apriori关联规则挖掘算法，从记录交通事故的数据库中发现潜在的、有价值、有联系的规律，用以指导交通管理部门找出道路黑点，并做出决策，杜绝事故隐患、减少事故发生，保障人们的生命和财产的安全。 关键词： 交通事故； 关联规则； 数据挖掘； 挖掘算法第1章 引言随着我国道路交通事业的飞速发展，交通事故猛增已成了交通管理所面临的严重问题。汽车交通作为人类文明的标志，彻底地改变了人类发展的历史进程，给人类以舒适和便捷等正面效应的同时也给人类生活带来一些负面效应，交通事故就是其中最严重、危害最大的负面效应之一。近年来在我国机动车数量快速增长的情况下，交通事故及伤亡人数呈不断上升趋势。因此结合数据挖掘技术研究我国道路交通事故，从记录交通事故的数据库中发现潜在的、有价值、有联系的规律，分析其成因具有非常重要的意义。 第2章关联规则的理论1关联规则的基本概念：设I=i1,i2,.,im是项集，其中ik(k=1,2,m)可以是购物篮中的物品，也可以是保险公司的顾客。设任务相关的数据D是事务集，其中每个事务T是项集，使得TÍI。设A是一个项集，且AÍT。关联规则是如下形式的逻辑蕴涵：A Þ B，AÌI, AÌI，且AB=F。关联规则具有如下两个重要的属性：支持度: P(AB)，即A和B这两个项集在事务集D中同时出现的概率。置信度: P(BA)，即在出现项集A的事务集D中，项集B也同时出现的概率。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。2 关联规则的分类： 1) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。 2) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。在多层关联规则中，对数据的多层性已经进行了充分的考虑。 3) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维关联规则中，我们只涉及到数据的一个维，如时间。在多维关联规则中，要处理的数据将会涉及多个维，如时间，地点，产品。3关联规则的相关算法：关联规则的算法的思想，首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。挖掘关联规则的总体性能由第一步决定，第二步相对容易实现。下面看看几个经典的算法。1） Apriori核心算法分析为了生成所有频集，使用了递推的方法。其核心思想简要描述如下：(1)L1 = large 1-itemsets;(2)for (k=2; Lk-1¹F; k+) do begin(3)Ck=apriori-gen(Lk-1);/新的候选集(4)for all transactions tÎD do begin(5)Ct=subset(Ck,t);/事务t中包含的候选集(6)for all candidates cÎ Ctdo(7)c.count+;(8)end(9)Lk=cÎ Ck |c.count³minsup(10)end(11)Answer=kLk; 首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。为了提高算法的效率，Mannila等引入了修剪技术来减小候选集Ck的大小MTV94，由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。2) 基于划分的算法Savasere等设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。3)FP-树频集算法针对Apriori算法的固有缺陷，J. Han等提出了不产生候选挖掘频繁项集的方法：FP-树频集算法。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。4）多层关联规则挖掘对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。 5）多维关联规则挖掘对于多维数据库而言，除维内的关联规则外，还有一类多维的关联规则。例如：年龄（X，“20.30”） 职业（X,“学生”）= 购买(X，“笔记本电脑”)在这里我们就涉及到三个维上的数据：年龄、职业、购买。根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。年龄（X，“20.30”） 购买(X，“笔记本电脑”) = 购买(X，“打印机”)这个规则就是混合维关联规则。在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类：种类型和数值型。 第三章 交通事故数据处理1需求理解由于涉及到交通管理信息积累的原始数据特别多，大多是存在于不同的数据库中，甚至有些与交通安全相关的某些数据跨行业保存在其他行业的数据库中，如气象部门记录的天气气象数据，司机的详细信息存放在公安部数据库中，司机的身体状况可能存放在医院里，这些数据库大多是事务性的数据库，其中的数据各自独立、互不相关。数据挖掘的主题是从这些互不相关的数据中寻找出与交通事故相关的信息，导致交通事故发生的各种因素以及交通事故对各种因素的概率分布。2. 数据准备由于人的信息、车辆的信息、道路信息、天气信息、相关经济方面的信息、交通管理的信息、交通法规相关信息。这些信息的建设都是针对特定需求建立起来的事务性数据库，其中存放的数据往往不能直接用于挖掘主题的数据挖掘，必须进行必要的数据预处理或数据准备，包括数据选择、净化、转换、数据缩减等工作，获取与挖掘主题直接相关的有效数据。数据准备是非常重要的一个步骤，将影响数据挖掘的效率和准确度以及最终模式的有效性。人的信息主要包过机动车驾驶员、乘车人、骑自行车人、行人等，其中公共属性包过姓名，性别，年龄，学历，籍贯等一些基本信息。机动车还包过驾龄、准驾车辆类别、驾驶证编号、发证机关等一些其他属性。车辆的信息主要包过车主身份证好，车主的名字，车主的联系方式，车辆的型号，车辆的类别，车辆的颜色，发动机型号，车架号，出厂时间，购买信息，使用年限，车辆用途，购买时间等。道路的信息包过道路编号，道路开通日期，道路状况，道路上的红绿灯编号，道路上红绿灯的状态等。天气信息主要包过日期，地方，天气现象，最低温度，最高温度，风向，风力等信息。经济方面的信息主要包过事故发生区域，该地区的机动车销售量等信息。交通管理信息主要包过投入警力数，交通科学水平，各相关部门的管理等信息，管理决策者的信息，综合治理方面的信息。交通法规的信息包过交通法规的数量，交通法规相关惩罚力度，公民的自律性和安全行车意识等相关信息。3数据建模 根据上面的数据准备资料建立道路交通事故属性的数据模型：事故因素人的因素车辆因素道路因素经济因素天气因素其他因素姓名角色.机动车驾驶员骑自行车人.建立如下数据模型表事故数据信息表（accidentInfo）：字段名称数据类型是否为空数据描述personchar(100)not null人vehiclechar(100)not null交通timechar(100)not null时间rodechar (100)not null路面情况economychar (100)not null经济weatherchar (100)not null天气otherchar (100)not null其它发生事故时间表accidentTime字段名称数据类型是否为空数据描述time_codechar(32)not null时间编号timechar(32)not null时间发生事故天气表（accidentWeather）字段名称数据类型是否为空数据描述weather_codechar(32)not null天气标号weatherchar(32)not null天气发生事故路况表（accidentRode）字段名称数据类型是否为空数据描述rode_codechar(32)not null道路编号rodechar(32)not null道路名称交通工具表（accidentVehicle）字段名称数据类型是否为空数据描述vehicle_codechar(32)not null交通工具编号vehiclechar(32)not null交通工具名称发生事故的成员字段名称数据类型是否为空数据描述person_codechar(32)not null身份证号role_namechar(32)not null角色名称role_codechar(32)not null角色编号发生事故区域的经济字段名称数据类型是否为空数据描述economy _codechar(32)not null经济编号economychar(32)not null区域经济状况发生事故的其它信息字段名称数据类型是否为空数据描述other_codechar(32)not null其它编号otherchar(32)not null其它信息.4 数据转换与上面数据模型对应的数据表为：发生事故的时间表发生事故时间编号time_code12345678时间 time工作日上午工作日中午工作日下午工作日晚上休息日上午休息日中午休息日下午休息日晚上发生事故的天气表发生事故天气编号weather_code123456789天气 weather晴天多云阴天大雨/暴雨中雨小雨大雪/暴雪中雪小雪交通工具表：交通工具编号vehicle_code123456789交通工具名称vehicle大型客车大型货车小型客车小型货车轿车农用车摩托车电动车自行车发生事故路况表道路编号rode_code1234道路名称rode平直弯道陡坡交叉路口发生事故的成员表角色编号role_code1234角色名称role_ name机动车驾驶员乘车人骑自行车人行人发生事故区域的经济表经济编号economy _code1234区域经济状况economy富裕小康温饱贫穷驾驶员原因表（发生事故的其它信息）驾驶原因编号cause_code1234区域经济状况cause酒后驾车疲劳驾驶超速驾驶红灯驾驶事故类别表（发生事故的其它信息）事故类别编号class_code1234事故类别class轻微一般重大特大5 数据清理去掉数据中的噪声，由于交通事故在国庆和春运等放假的时候特别多，所以先过滤掉国庆和春运等节假日高峰期的交通事故。纠正不一致。由于事故数据比较全面，某些事故属性出现空值的数量较小，所以采用人工填写空缺值。但也有些事故属性出现的空值比较大采用平均值处理。6 数据集成现在开始将最原始数据合并成上面的数据表中，其中我们的数据是来自于江西省南昌市的部分交通事故数据。下面是集成后的交通事故数据部分表：时间1234567810000000000000001000000000100000010000000000010000000001010100000000000000000000010000101000000000000010000100000000000100000000000100001000000000100001000000001000000000000000101010100000010000000000000001000101000000100000天气123456789000000100100000000000001000100000000001000100000001010100000000000010100101111000100000000000000100101000000000000000000100000000000000000000000000000000000000000000000100001000000000000000000000000110000000000000000000000000100100000000000000000000000交通工具123456789100000000000000000000000000001100000000000100000000000000001001100000100001010001010000010001100000100010101001000000000001000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001路况12341010000000100000001000000001010100001000100001010010010000000010000100101000100100100000100101000101000001001000成员12340001011001010001000000000101001000010010101011000011000000001000100001000010010010101100000000000000000110000000经济12341000000000010000001010100000010000100100100100010001001000101101001001001000010010010001000010000010010000000100驾驶员原因12341000001000011000000010000010011001010110010000000100010100011000100000100000001110000000000000000001111100000000事故 4 3 3 4 2 2 2 4 3 1 2 2 3 4 1 2 3 4 2 3 4 2 3 3 2 1 4 4类别第4章 交通事故的数据挖掘分析1事故数据预处理由上章集成后的数据可以看出只有0,1两个取值，数据字段根据数据的分布分成布尔字段。每个布尔字段都是表示一个数值字段区间，落在其中则为1，反之为0。上表的每一列代表一条记录，现在的交通事故数据的每条记录都是定长的，每一数据项都在记录中，仅仅是取值不一样，记录中的数据项都转化成枚举类型了，用代码表示，如成员，时间，路况，天气，交通工具等因其特点知，交通事故数据挖掘不是进行单维，单层，布尔型的数据挖掘，而是进行量化型关联规则挖掘。下面我们来对上面的数据结果进行讨论。2结果讨论由Apriori算法实现挖掘出的关联规则如下表：得出的强关联规则表： 强关联规则 支持度 置信度酒后驾车&平直&工作日下午&小型客车&大雨&富裕=重大事故13.3381.12 酒后驾车&弯道&工