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

应用数据挖掘的apriori关联规则技术分析交通事故唐丰飞()E-mail:tangffei@摘  要:随着我国道路交通事业的飞速发展,交通事故发生率呈上升趋势。由于交通事故的发生不仅造成大量人员伤亡,给无数家庭带来不幸,而且严重影响着经济发展和社会稳定,已引起了各级政府的高度重视和关注。人们在认为交通事故的发生具有一定规律性,而造成事故的原因又具有复杂性和多样性,本文根据数据挖掘技术中的关联规则理论,利用apriori关联规则挖掘算法,从记录交通事故的数据库中发现潜在的、有价值、有联系的规律,用以指导交通管理部门找出道路黑点,并做出决策,杜绝事故隐患、减少事故发生,保障人们的生命和财产的安全。关键词:交通事故;关联规则;数据挖掘;挖掘算法引言随着我国道路交通事业的飞速发展,交通事故猛增已成了交通管理所面临的严重问题。汽车交通作为人类文明的标志,彻底地改变了人类发展的历史进程,给人类以舒适和便捷等正面效应的同时也给人类生活带来一些负面效应,交通事故就是其中最严重、危害最大的负面效应之一。近年来在我国机动车数量快速增长的情况下,交通事故及伤亡人数呈不断上升趋势。因此结合数据挖掘技术研究我国道路交通事故,从记录交通事故的数据库中发现潜在的、有价值、有联系的规律,分析其成因具有非常重要的意义。第2章 关联规则的理论1关联规则的基本概念:设I={i1,i2,..,im}是项集,其中ik(k=1,2,…,m)可以是购物篮中的物品,也可以是保险公司的顾客。设任务相关的数据D是事务集,其中每个事务T是项集,使得TÍI。设A是一个项集,且AÍT。       关联规则是如下形式的逻辑蕴涵:AÞB,AÌI,AÌI,且A∩B=F。关联规则具有如下两个重要的属性:支持度:P(A∪B),即A和B这两个项集在事务集D中同时出现的概率。置信度:P(B|A),即在出现项集A的事务集D中,项集B也同时出现的概率。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。给定一个事务集D,挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则,也就是产生强规则的问题。2关联规则的分类: 1)基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的,它显示了这些变量之间的关系。数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。2)基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。在单层关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同的层次的。在多层关联规则中,对数据的多层性已经进行了充分的考虑。3)基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。在单维关联规则中,我们只涉及到数据的一个维,如时间。在多维关联规则中,要处理的数据将会涉及多个维,如时间,地点,产品。3关联规则的相关算法: 关联规则的算法的思想,首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则,这些规则必须满足最小支持度和最小可信度。  挖掘关联规则的总体性能由第一步决定,第二步相对容易实现。下面看看几个经典的算法。Apriori核心算法分析为了生成所有频集,使用了递推的方法。其核心思想简要描述如下:(1)     L1={large1-itemsets};(2)     for(k=2;Lk-1¹F;k++)dobegin(3)     Ck=apriori-gen(Lk-1);   //新的候选集(4)     foralltransactionstÎDdobegin(5)     Ct=subset(Ck,t);    //事务t中包含的候选集(6)     forallcandidatescÎCt  do(7)     ++;(8)     end(9)     Lk={cÎCk|³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,这里的验证过程是算