（通信与信息系统专业论文）交通事故数据挖掘的多维关联规则研究.pdf

山东大学硕士学位论文 摘要 随着车速提高、交通量增长，道路交通事故已日益引起各有关部门的重 视。交通事故的发生受多种因素的影响，能否对已发生事故做出正确的分析 将直接影响到能否对未来类似事故的成功避免。随着社会的发展，交通事故的 复杂性也在逐渐增强，传统的分析、预防方法已呈现其局限性。本文提出一种 利用数据挖掘领域中的多维关联规则技术从记录交通事故的海量数据中寻找 有用信息的方法，通过找出可能导致交通事故发生的频繁因素组合来发现某 些事故诱因之间联系的内在规律。如果根据事故诱因之间的联系规律，进行 人为控制和干预，使事故发生条件缺失，可以降低交通事故发生的概率。 数据挖掘( d a t am i n i n g ) 是一个从海量有噪声、不完整数据中挖掘出有意 义知识模式的过程。数据挖掘方法的提出，让人们有能力发现海量数据中蕴 藏的有用信息。关联规则是数据挖掘的主要方法，反映一个事物与其它事物 之间的相互依存性和关联性n 1 ，是指在数据集中支持度和置信度分别满足给定 阈值的规则。关联规则挖掘的经典a p r i o r i 算法就是根据有关频繁项集特性 的先验知识而命名的，算法中蕴含的一条基本性质是一个频繁项集的任一子 集均应是频繁的。借助一定的专业领域知识，关联规则可以直接用于分析数 据的因果关系，进一步探索，做出规则预测。从大量的数据中发现其关联关 系对于决策分析是极为有用的。 本文针对道路交通事故这一实际问题，对经典单维单层的a p r i o r i 算法 进行改进，实现挖掘多维多数据类型关联规则的新算法；给出了道路交通事 故属性的定义，并且采取全星型连接数据模型对道路交通事故属性的数据组 织建模；将大量杂乱无章的交通事故数据组织为可进行数据挖掘的属性信息， 用于分析各种相关因素间的复杂关系；通过数据挖掘的关联规则技术处理交 山东大学硕士学位论文 通事故数据，提取和分析了道路交通事故的规律；重点分析、阐述了车辆事 故属性数据关联规则提取的算法，然后对该算法进行了验证。 用本文的方法对交通事故数据进行提取、分析得到关联规则，展现了关 联规则提取技术的使用价值。对于本文建立的道路交通事故属性的数据模型， 可以进一步细化，以便能够包含更多的信息，而进行更详细的数据关联规则 分析。 关键词：交通事故；数据挖掘；多维关联规则 2 山东大学硕士学位论文 a b s t r a c t w i t ht h ee n h a n c e ds p e e do fv e h i c l e sa n di n c r e a s e dt r a f f i cv o l u m e ，r o a dt r a f f i c a c c i d e n t ss h o wai n c r e a s i n gg r a d u a l l yt e n d e n c y ，t h a th a sa r r e s t e ds o m er e l a t i v e d e p a r t m e n t sa t t e n t i o ng r a d u a l l y t h e r ea r em a n yk i n d so ff a c t o ri n f l u e n c et r a f f i c a c c i d e n t so c c u r r e n c e i tw o u l di n f l u e n c et h es u c c e s sa v o i d a n c eo ft h ef u t u r e s i m i l a ra c c i d e n t s ，w h e t h e rt om a k et h ec o r r e c ta n a l y s i so ft h eh a p p e n e da c c i d e n t w i t ht h e s o c i e t y sd e v e l o p m e n t ，t r a f f i ca c c i d e n t sc o m p l e x i t y i s g r a d u a l l y s t r e n g t h e n i n g ，t h et r a d i t i o n a la n a l y s i sh a v ep r e s e n t e di t sl i m i t a t i o n t h i sp a p e r p r o p o s e dam e t h o d ，t h r o u g hf o u n d st h ef r e q u e n tf a c t o rc o m b i n a t i o nw h i c hc o u l d c a u s et h et r a f n ca c c i d e n tt od i s c o v e rt h ei n h e r e n tr e l a t i o n a ll a w sb e t w e e nc e r t a i n a c c i d e n tc a u s e i fw ec a nf i n dt h e i ri n h e r e n tl a w so ft h ec o n n e c t i o nf r o mt h e i n d u c e m e n t so fal a r g en u m b e ro ft r a f f i ca c c i d e n t s ，c o n t r o la n di n t e r v e n e a r t i f i c i a l l y ，m a k et h ec a u s ef a c t o r sl a c k ，i tc a nr e d u c et h ee m e r g e n c ep r o b a b i l i t yo f t h et r a m ca c c i d e n t s d a t am i n i n gi sac o a r s eo fe x c a v a t i n gm e a n i n g f u lk n o w l e d g em o d ef r o mt h e n o i s ea n di n c o m p l e t ed a t a b a s e t h ep r o p o s i t i o no fd a t am i n i n gm e t h o d sm a k e p e o p l eh a v ea b i l i t i e st or e a l i z et h es t e r l i n gw o r t ho ft h ed a t a a s s o c i a t i o nr u l e si s t h em a i nd a t am i n i n gm e t h o d s ，w h i c hr e f l e c t st h ei n t e r d e p e n d e n c ea n dr e l a t i o n a m o n go n et h i n ga n do t h e rt h i n g s i tm e a n st h er u l e s t h a tt h es u p p o r t a n d c o n f i d e n c ea c c o r dw i t ht h eg i v e nv a l u ei nd a t as e t s t h ec l a s s i c a la l g o r i t h mo f a s s o c i a t i o nr u l e si sa p r i o r i ，w h i c hi sn a m eb yt h ep r i o r ik n o w l e d g ea b o u tt h e c h a r a c t e r i s t i co ff r e q u e n ti t e m s e t s af u n d a m e n t a lp r o p e 啊t h a tc o n t a i n si nt h e a l g o r i t h mo fa p r i o r ii s t h a ta n ys u b s e t so faf r e q u e n ti t e m s e t ss h o u l db e f r e q u e n t i nv i r t u eo fc e r t a i np r o f e s s i o n a lk n o w l e d g e ，a s s o c i a t i o nr u l e s c a nb e d i r e c t l y u s e dt oa n a l y s et h ed a t ac a u s a l i t i e s ，t o s t u d yf u r t h e ra n dt om a k e p r e d i c t i o n so fr u l e s f i n d i n g r e l a t e dr e l a t i o n sf r o mal a r g en u m b e ro fd a t ai s e x t r e m e l yu s e f u li nt h ed e c i s i o na n a l y s i s i na l l u s i o nt ot h ef a c to ft h et r a f f i ca c c i d e n t ，t h i st e x ti m p r o v e st h ec l a s s i c a l s i n g l e - d i m e n s i o n a la n ds i n g l e l a y e ra l g o r i t h mo fa p r i o r ia n du t i l i z e st h en e w m u l t i d i m e n s i o n a la n dm u t l i t y p ea l g o r i t h mo fa p r i o r ib a s e do na s s o c i a t i o n 3 山东大学硕士学位论文 r u l e s i to r g a n i z e sal a r g en u m b e ro fc o m p l i c a t e da n dd i s o r d e r e dt r a f f i ca c c i d e n t d a t at ob ei n f o r m a t i o n ，a n a l y s e sv a r i o u sk i n d so fc o m p l i c a t e dr e l e v a n tf a c t o r s h e r e p r o v i d e st h ed e f i n i t i o n o fp r o p e r t yo ft h er o a dt r a f f i ca c c i d e n t sa n da d o p t s s t a r t y p et h ef u l l - c o n n e c t i o nd a t am o d e lt ob u i l d ，a n da n a l y s e sw i t he m p h a s i st h e a l g o r i t h mf o ra b s t r a c t i n ga s s o c i a t i v er u l e sf r o mv e h i c l ea c c i d e n ta t t r i b u t ed a t a i t d i s p o s e st h et r a f f i ca c c i d e n td a t a ，d i s t i l l sa n da n a l y s e st h et r a f f i ca c c i d e n tl a w sb y a s s o c i a t i o nr u l e si nd a t am i n i n g t h em e t h o dt h a ti su s e dt od r a wa n da n a l y s ea s s o c i a t i o nr u l e so ft h et r a f f i c a c c i d e n td a t ai nt h i st e x t ，w h i c hr e p r e s e n t st h eu s ev a l u eo ft h ed r a w i n gt e c h n o l o g y o fa s s o c i a t i o nr u l e s w ec a nb u i l dt h ed a t am o d e lo fp r o p e r t yo ft h er o a dt r a f f i c a c c i d e n ti nm o r ed e t a i ls ot h a tt h em o d e lc a nc o n t a i nm o r ei n f o r m a t i o na n dc a n c a r r yo nm o r ed e t a i ld a t aa s s o c i a t i o nr u l e st oa n a l y s i s 4 k e y w o r d s ：t r a f f i ca c c i d e n t s ，d a t am i n i n g ， m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e s 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：耳塞整 日期：兰：z ：z ：! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：臼薹4 里 导师签名： 山东文学硕士学位论文 1 1 论文选题背景和目的 第一童前言 道路交通事故是世界性的灾害和难题。我国交通事故数量、死伤人数和直接 经济损失从2 0 0 1 年起连续居高不下，不仅已经成为世界道路交通事故最多的国 家之一，而且事故致死率比欧洲国家要高出1 0 倍以上，经济损失更加惊人乜1 。 如何从以往大量的交通事故数据中发现问题，分析事故的原因，以便于有关部门 采取相应的对策，从而减少交通事故发生的概率变得尤为重要。本文选题的目的 就在于深入研究道路交通事故的分布规律、成因特性、评价和预测方法，提出科 学有效的事故预防对策，为降低事故率及事故严重程度奠定理论和实践基础。 道路交通是由人、车、路三个因素构成的运输系统d 1 ( 如图卜1 ) ，其中任 何一个方面的不协调均将造成交通事故，例如驾驶员违章操作、车辆系统的技术 故障和道路的缺陷都可能造成交通事故。每一起交通事故的发生，单独进行分析 似乎具有偶然性，实质上是有其必然性的，即入、车、路三方面出现了不协调， 造成汽车不能正常行驶而发生交通事故。由于道路交通事故涉及的面较广，既有 驾驶员的操作、行人的穿行、车辆的技术状况等因素的影响，又有道路状况、车 流量、车速、交通状况的影响。事实上，一起道路交通事故的发生一般说来都是 偶然的，往往是由两个或多个原因共同引起的。因此，有必要对事故成因进行深 入分析，以期确定各影响因素在道路交通事故产生过程中所起的真正作用。 图1 - 1 人、车、路组成的道路交通系统 1 2 国内外道路交通事故研究的现状 国内外关于道路交通事故影响因素的理论研究主要经历了三个阶段：最早出 现也是最简单的致因理论是单因素理论，这种理论把事故简单地归结为由一种原 5 山东大学硕士学位论文 因引起，它较偏重于对人的分析：单因素理论逐渐发展成为多因素理论，该理论 广泛地用于各种事故的分析，认为在道路交通事故分析中，主要应从“人、车、 路”三因素着手；国外在2 0 世纪8 0 年代提出了系统致因理论，该理论以系统的 观点对引发事故的多种因素及其关系( 主要是逻辑关系) 进行研究。 1 2 1 国外研究现状 1 8 6 8 年英国人在伦敦议会大厦门前的马路上安装了两盏煤气灯，用红色灯 表示禁止通行，绿灯表示可以通过。1 9 2 5 年，年仅2 0 岁的中国留学生胡汝鼎先 生建议美国人在红绿灯中间装黄色信号灯，以提醒人们注意交通安全【4 】。这些都 标志着人们已经开始意识到阻止道路交通事故发生的重要性。 瑞典国会于1 9 9 7 年1 0 月通过了一项在道路交通系统中的长远安全目标 零点计划( t h ev i s i o nz e r o ，v z ) ，或称为无死亡和严重损伤计划【5 l 。它要求交 通系统设计者确保整个交通系统内的安全，道路使用者有获得道路系统安全的权 利，同时，也必须严格遵守各项交通规则。 美国、日本、加拿大等发达国家在道路交通运输和信息化建设方面走在了世 界的前例，相应地在交通事故数据采集和分析系统的建设方面处于领先地位。在 美国有许多的交通事故多学科研究机构，如：国家交通统计局建立了事故分析报 告系统f a r s ( f e d e r a la c c i d e n tr e p o r t i n gs y s t e m ) ，它是一个包括1 9 7 5 年以 后美国各种严重交通事故信息的数据库【6 1 。f a r s 数据库的数据来自警察报告的数 据、车辆、驾驶员以及发照机关和医院的报告( 包括解剖结果) 。通过该系统可 以得到全美各地区和城市的交通事故分布情况。该系统是美国交通安全年度评价 报告的主要数据来源。除联邦政府外，各州也建立了类似的交通事故统计分析系 统，如加州建立了收集当地交通事故数据的c a r a s 分析系统，该系统能生成各种 交通事故统计图表，计算和分析高事故率的地段和地区，同时该系统也加强了交 通事故管理部门和其它公众组织的联系，实现了信息的共享【7 1 。德州交通研究所 开展了t r a f f i cs e r v i c e s ( t r a s e r ) 项目，目标是分析交通事故数据、确定事故 多发地点、改善交通安全设施，减少交通事故。 在日本，由交通、建设和警察部门联合建立了交通事故研究分析中心，其主 要目标是从微观和宏观分析评价日本交通安全状况，制定相应的安全措施，实现 数据和信息共享。在加拿大，交通运输部建立了t r a i d ( t r a f f i ca c c i d e n t i n f o r m a t i o nd a t a b a s e ) 交通事故信息数据库，为交通事故的分析研究提供技术 6 山东大学硕士学位论文 支持l 丌。 1 2 2 国内研究现状 在国内，除公安部交管局开发了交通事故统计系统外，也有部分省市开始建 立交通事故分析系统。 2 0 0 2 年1 0 月2 9 日由清华大学汽车研究所与云南省道路交通管理科学技术 研究所合作共同开发“道路交通事故再现分析系统”【8 】在昆明通过正式鉴定和 验收，专家组评审认为，该系统的成功研发和应用，将改变我国道路交通事故长 期由人工处理的局面，可以大大提高交通事故处理速度和质量。该系统由“道路 交通事故现场信息采集”、“道路交通事故再现”、“道路交通事故处理及原因 分析”三个子系统组成。交警在应用这一系统处理交通事故时，可以既快速又准 确地勘测并采集到事故现场信息数据，输入这些数据后，系统可以很快以三维方 式再现出交通事故的发生过程，并自动分析出结果。 自2 0 0 5 年5 月起由同济大学与德国大众汽车公司、上海公安交巡警总队等 单位合作开展了“中国道路交通事故研究一项目，它试图通过对事故信息的安 全科学地采集和对具体案例的系统研究，发现中国道路交通的自身特点，探求在 中国降低交通事故发生率的对策。项目组的主要工作包括事故现场勘测、事故车 辆及人员信息手机、事故再现及事故数据处理等。2 0 0 7 年1 2 月开始，该项目组 又与吉林大学、上海工程技术大学等合作，将事故研究区域范围扩大至长春市和 上海市松江区，以涵盖更多的环境特征及相关的事故形态，从而为全面进行中国 道路交通事故研究奠定了基础。同济大学从2 0 0 6 年起至今，已连续召开了三届 中国道路交通事故研究学术研讨会，使之成为相关研究人员交流合作的平台【9 】。 1 3 工作介绍 道路交通事故的发生既有其特定的、偶然的原因，又受各种其他客观因素的 支配。如何从大量的道路交通事故的诱发因素中发现它们之间联系的内在规律， 进行人为控制和干预，使事故发生条件缺失，以减少交通事故的发生概率是大家 所关注的焦点。 1 3 1 本文主要研究以下内容： ( 1 ) 基于关联规则的道路交通事故数据挖掘的模型； 7 山东大学硕士学位论文 数据挖掘是一种人工智能技术，已广泛应用于多个领域。数据挖掘是从海量 数据中发现有效的、新颖的、潜在的、以及最终可理解的模式。用于发现潜藏在 大规模数据内部，不能被人轻易察觉的规律或知识。道路交通事故处理数据库规 模庞大，在道路交通管理工作中，急需有一个自动化的事故原因排查工具，以便 在交通管理中做出更加科学的决策，减少道路交通事故的发生。 关联规则也是数据挖掘的主要方法，反映一个事物与其它事物之间的相互依 存性和关联性，是指在数据集中支持度和置信度分别满足给定阈值的规则。关联 规则理论的主要特点是数据的自然连接【l o i ，在数据分析方面具有较好的客观性； 另外，基于关联规则的相关算法的不断改进，方便大规模数据的处理。本文结合 道路交通事故数据的实际背景，建立基于关联规则的数据挖掘模型。对道路交通 事故的历史数据应用数据挖掘方法进行类型分类，得出有效的决策规则。 ( 2 ) 研究关联规则的多维a p r i o r i 算法； a p r i o r i 算法是关联规则用于数据分析的重要手段，高效的a p r i o r i 算法是关 联规则应用于数据挖掘的基础。通过多维a p r i o r i 算法研究，降低计算的复杂度， 利用改进的算法对数据库进行关联，以便生成关联规则。改进的a p r i o r i 算法中 利用关联规则的重要结论“任意数据项集的支持度总是小于等于其子集的支持度 【l l 】”，减少了算法搜索数据项集的范围，提高了算法的效率。因此，有必要运用 交通管理知识等启发信息来简化计算。本文通过研究发现关联信息的多维 a p r i o r i 算法，达到在不改变信息表达能力的前提下对交通事故历史数据进行关 联，达到数据挖掘模型实用化的目的。 ( 3 ) 研究关联规则的类型和影响因素。 如果不考虑关联规则的支持度和置信度，那么在事务数据库中存在无穷多的 关联规则。而使用“支持度一置信度 框架的算法，有时会产生一些矛盾甚至错 误的结果，于是本文引入了相关度与兴趣度，用来修剪无趣的规则，以避免生成 “错觉 的关联规则，同时提高算法的效率。 1 3 2 本文主要完成了以下几个方面的工作： ( 1 ) 利用关联规则原理查找道路交通事故数据信息的频繁项集，进而找出影 响道路交通事故各方面因素的关联规则； ( 2 ) 基于道路交通事故属性的分类与关联规则的融合； ( 3 ) 建立道路交通事故属性的数据挖掘模型； 8 山东大学硕士学位论文 ( 4 ) 对事故数据进行预处理，对数据属性进行分析、清理，删除事故决策者 不关心的属性，缩小进行规则提取的数据库，对数值型的属性进行离散化，以便 用适合的工具进行规则提取。 ( 5 ) 对规则提取中参数的设置进行研究，通过不同参数的设置，对规则的数 量、有效性的影响分析。 1 4 内容组织 本文具体内容安排如下： 第一章：介绍论文选题背景和研究意义。 第二章：介绍数据挖掘的知识。包括数据挖掘概述、在交通领域应用数据挖 掘的必要性、数据挖掘的研究现状、数据挖掘的种类。 第三章：介绍关联规则理论基础。包括关联规则的基本概念、关联规则的分 类及提取方法、关联规则的基本挖掘算法、多维多层的关联规则，建立多维 a p r i o r i 算法的算法流程，相关度的概念、关联规则的价值衡量等内容。 第四章：介绍交通事故成因分析，从分析多维数据模型入手，设计道路交通 事故数据属性及其数据模型，从而为下一步的提取关联规则做准备。 第五章：设计关联规则提取过程。包括算法的详细描述及其用于道路交通事 故数据的实验结果分析。 第六章：论文总结和展望。 9 山东大学硕士学位论文 2 1 数据挖掘概述 第二章数据挖掘技术 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程1 2 】。发现的知识可以被用于信息管理、查询优化、决策支持、过程控制等， 还可以用于数据自身的维护。因此，数据挖掘是一门广义的交叉学科。 2 2 在交通领域应用数据挖掘的必要性 要合理利用现有的交通设施引导和控制车流，就必须根据交通量数据来 制定控制策略。目前的情况是，一方面，许多已建交通监控系统所采集的数 据不被重视；另一方面，许多人一提到解决交通问题，马上想到使用人工进 行交通数据抽样调查，这种方法不仅成本高，而且调查的数据偶然性大，可 靠性差、应变性差，并且一些隐藏在其中的规律和交通特点不能被发现。我 们可以利用数据挖掘技术对监控系统采集的交通数据进行分析，从众多的数 据中找到一些交通流的特点，针对这些特点制定有效的控制策略，做到有的 放矢，而且这些方法是实时的，即当交通流特点发生变化时，能够及时发现 以便及时改变控制策略。例如：在城市交通中，利用数据挖掘找到各个路口的 交通量的关联关系，制定相应交通诱导策略。 目前，数据库中的知识发现( k d d ) 和数据挖掘( d m ) 技术已成为研究的热 点和焦点【l3 1 。机器学习和数据分析的理论及实践成为数据挖掘研究的铺垫， 极大的商业应用前景是推动数据挖掘研究的又一主要因素。自1 9 9 5 年以来国 外在数据挖掘方面的论文已非常多，并有许多这方面的具体应用和成熟算法。 目前，比较先进的数据挖掘系统，可以从数据库中开采不同层次知识。它包 括一系列的开采功能：概括、特征、分类、预测等，并有多种开采技术：面 向属性的开采、统计分析等。 1 0 山东大学硕士学位论文 2 3 数据挖掘的种类1 1 4 1 1 关联规则 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是数据挖掘研究的一个重要分支， 它是数据挖掘的众多知识类型中最为典型的一种【1 5 】。关联规则挖掘可以发现 存在于数据库中的项目或属性间的有趣关系，这些关系是预先未知的和被隐 藏的，也就是说不能通过数据库的逻辑操作或统计的方法得出。这说明它们 不是基于数据自身的固有属性，而是基于数据项目的同时出现特征。一般地 关联规则挖掘是指从一个大型的数据集中发现有趣的关联或相关关系。通常， 给定一个事务数据集及用户指定的最小支持度和最小信任度，关联规则挖掘 问题即是发现所有满足最小支持度与最小信任度约束的关联规则。 2 分类规则 分类是指根据已经分好类别的数据，从中学习分类的规则并构建模型， 然后根据该模型对新数据进行分类。常用的分类技术【1 2 】有：决策树，贝叶斯 置信网络，后向传播神经网络等。此外，k 近邻，基于事例的推理，遗传算法， 模糊集，粗糙集等都可以用于分类。虽然分类与预测比较相象，不过分类中 要预测的是枚举型的类别标识，而预测则是要预测连续的数值。常用的预测 方法有线性回归，多元回归，非线性回归等。分类规则与聚类规则的最大区 别在于分类规则是指当数据库中数据的类别指定后，对这些类别进行研究， 从而发现出其中蕴含的分类方法的知识模式。 3 聚类规则 俗话说“物以类聚，人以群分”，聚类就是用计算机技术来实现这一目的 的一种技术。其输入的是一组未分类的记录，且事先不知道如何分类，把相 似性大的对象聚集为一个类。通过分析数据，合理划分记录集合，确定每个 记录所属的类别。聚类的标准是使类内相似度尽可能大，类间相似度尽可能 小。聚类规则是指发现数据库中的数据其内在的相似性并将其按照这些相似 性进行自动分类【1 2 1 。聚类规则可以在缺乏有关分类的先验知识的条件下，按 照“物以类聚的思想将数据进行分类，在模式识别、机器学习和神经网络 等领域中都有明显的应用价值。聚类规则的挖掘方法基本上使用的是统计分 析方法，通过计算数据间的距离来判断数据的相似性。统计分析方法的一个 明显的困难是无法找到一个对所有数据聚类模式都有效的聚类算法，并且不 1 1 山东大学硕士学位论文 同的聚类算法总可以产生其相应的分类。因此近年的聚类规则的挖掘研究更 多地转向借助于机器学习的方法，即用概念来表示距离，因此聚类又称为概 念聚类。 4 时间序列规则 时间序列规则可以认为是一类特殊规则，主要研究的是时间序列中重复 发生概率较高的模式。时间序列规则的挖掘需要找出在某个最小时间内出现 比率一直高于阈值的规则，难点主要在于数据量大和发掘模式的算法选择。 一般来说，数据立方和相关时序是解决时间序列规则常用的方法。时间序列 预测，是对数值型数据，根据其历史数值，对其将来一段时间内的数值进行 预测。一般说来，预测都需要有足够长时间的历史数据积累，在分析挖掘历 史数据内在规律和趋势的基础之上，才能有效地进行预测。 5 偏差和例外性规则 数据库中的数据存在很多的意外情况，对某些异常情况进行分析也是很 重要的，它可以得到分类中的反常实例，模式的例外等多种信息。该种规则 的发现主要是通过将观测结果与一定的参照进行对比而进行挖掘的。参照可 以是通过对数据按照一定的规律得到的预测、外界提供的标准或另外的观察， 对于一定的变量，可以通过卡尔曼滤波的方式得到。 2 4 关联规则研究现状 由于关联规则挖掘可以发现用传统方法无法发现的项与项或属性与属性 之间的关系规律，因此具有重要的研究价值，同时它满足了人们从大规模数 据存储中获取知识的迫切需求，因此国内外很多学者对它进行了研究。 美国斯坦福大学智能数据库系统实验室开发出了大量的商用化数据挖掘 系统，如d b m i n e r 挖掘系统【l6 1 ，它包含了许多先进的挖掘算法，用户无需具 有高级的统计知识和培训即可利用它挖掘出包含关联规则、序列模式、分类 等在内的多种类型的知识；该系统可以在多种平台上运行，并与许多主流的 数据库管理系统( 如s q l s e r v e r ，o r a c l e 等) 结合紧密；同时还引入了在线分析 挖掘技术，使得系统更能充分发挥数据仓库的分析优势。i b m 公司的a l m a d e n 实验室所进行i 拘q u e s t 项目同样也是数据挖掘研究领域中的佼佼者，该项目包 含了对关联规则、序列模式、分类及时间序列聚类的研究，其代表性的产品 1 2 山东大学硕士学位论文 有：d b 2i n t e l l i g e n tm i n e rf o rd a t a ，该产品在i b m 的d b 2 平台上应用，也有 w i n d o w sn t 下的类似产品【l7 1 。除了以上提及的世界知名公司和科研机构外， 还有许多大学的研究机构和学者对该领域的发展做出了重要贡献，如加拿大 s i m o nf r a s e r 大学的j i a w e ih a n ，比利时赫尔辛基大学的m a n n i l a ，t o i v o n n e n 等都是数据挖掘研究的著名专家【1 8 ，他们的许多工作都是该领域中具有奠基 性的。 在1 9 9 7 年s e r g e yb r i n 等首次在关联规则中考虑了否定属性f 1 9 】。随后很多 学者对其进行了深入的研究，j e a n f r a n c o i sb o u l i c a u t 等在2 0 0 1 年提出了计 算负关联规则的两种基本算法【2 0 1 。 近年来，国内的关联规则挖掘研究也逐渐掀起高潮，出现了一批相关的 科研项目，在算法和应用方面取得了一些具有扩展性或突破性的研究成果。 x i n d o n gw u 等提出了一种有效的挖掘正、负关联规则的算法【2 1 1 。陆晶等提出 了一种基于综合度量的关联规则挖掘算法【2 2 】，能够在挖掘正关联规则的同时， 挖掘出部分的负关联规则。卢炎生等提出了一种挖掘带否定关联规则的算法 【2 3 1 ，该算法能够挖掘出所有的带否定的关联规则。董祥军等提出了一种基于 最小兴趣度的正、负关联规则挖掘【2 4 1 。尽管很多研究者指出负关联规则的重 要性，从上面可以看到，仅有很少的科研机构和学者进行这方面的研究，一 方面是由于负关联规则的新奇性，另一方面是因为完善地挖掘负关联规则有 很大的难度。 1 3 山东大学硕士学位论文 第三章关联规则理论 3 1 关联规则的概念及属性 关联规则( a s s o c i a t i o nr u l e s ) 的概念首先由r a g r a w a l 等于1 9 9 3 年提出 1 2 5 1 ，是反映一个事物与其他事物之间的相互依赖性或相互关联性。关联规则 挖掘是数据挖掘中最活跃的研究方法之一。最初提出的动机是针对购物篮分 析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则。 之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。 在抽象层次上，关联规则揭示数据间的相互关系，关联规则的挖掘就是 从一组给定的数据项以及事务集合中，分析出数据项集在事务集合中出现的 频度关系。 3 1 1 关联规则的概念 设，= ，之，乙) 是m 个不同项目的集合，其中的元素称为项 ( i t e m ) ，d 是针对i 的事务集，每一事务t 包含若干项目 ，z 2 ，k 属于，且有一个标识t i d ，如果对于，中的一个子集x ，有x ，我们就 说一个事务丁包含x 。一条关联规则就是一个形如xjy 的蕴涵式，其中 x ，y i ，而且x n r = 囝。x 称作规则的前提，】，是结果【2 6 1 。 说明： ( 1 ) 对于x ，如果d 中包含x 的事务数为s ，则称s 为石的支持度。 若用s u p p o r t ( x ) 表示石的支持度，贝o s u p p o a ( x ) = s 。 ( 2 ) 关联规则x y 在事物数据库d 中具有大小为s 的支持度，定义为 s u p p o r t ( xj 】，) = s u p p o i r t ( x u y ) 。 ( 3 ) 如果d 中支持项集x 的事物中有c 的事物同时也支持项集y ，称规则 xjy 在事物数据库d 中具有大小为c 的可信度。 一般把一些项目的集合称作项集( i t e ms e t ) 。在一个项集中所含项目的个 数称为该项集的长度，即x 为项集，工的长度等于z 中项目的个数。包含k 1 4 山东大学硕士学位论文 个数据项的项集称为k 项集。 项集的出现频率是在整个交易数据集d 中包含该项集的交易记录数，简 称为项集的频率、支持度( s u p p o nc o u n t ) 或计数。 如果项集的出现频率大于或等于m i ns u p 与d 中事务总数的乘积，称项集 满足最小支持度m i ns u p 。如果项集满足最小支持度，则称它为频繁项集 ( f r e q u e n ti t e ms e t ) ，简称频集。频繁k 项集的集合通常记作l k 。 关联规则的提取问题就是在d 中筛选出所有具有用户指定的最小支持度 ( m i n i m u ms u p p o r tc o u n t ，简称m i n s u p ) 和最小可信度( m i n i m u mc o n f i d e n c e c o u n t ，简称m i n c o n ) 的关联规则。 因此，关联规则挖掘可定义为：给定一个事务数据库d ，寻找出所有满 足s u p p o r t m i n s u p ，c o n f i d e n c e m i n _ c o n 的关联规则aj b 。 3 1 2 关联规则的属性 1 支持度( s u p p o r t ) 如果x 、y 这一事件组合在总事务记录中出现概率过低，低于预先给定 的临界值，则说明这一事件组合发生的次数太少，少到我们没有必要关注它 的程度。相反，如果这一事件组合的出现概率高于预先给定的临界值，说明 这个模式具有一定程度的普遍意义，我们发现并进一步研究它是有价值的。 我们称这个概率为“支持度”。这里的临界值的设置要根据领域专家的建议和 实际情况来综合决定。 2 置信度( c o n f i d e n c e ) 定义为c o n f i d e n c e ( x y ) = s u p p o r t ( x u y ) s u p p o r t ( xo 考虑到即使 x 、y 这一事件组合发生频繁，但如果这一事件组合的发生次数比上x 事件的 所有发生次数的值过低，低于预先给定的临界值的话，说明x 的发生不足以导 致y 的发生。该临界值的设置要根据领域专家的建议和实际情况来综合决定。 如果不考虑关联规则的支持度和置信度，那么在事务数据库中存在无穷 多的关联规则。事实上，人们一般只对满足一定的支持度和置信度的关联规 则感兴趣。 3 期望置信度( e x p e c t e dc o n f i d e n c e ) 对于关联规则a b ，项集b 的支持度称为关联规则的期望置信度1 2 7 】 ( e x p e c t e dc o n f i d e n c e ) ，即在没有任何条件影响下b 出现的概率：p ( b ) 。如果 1 5 山东大学硕士学位论文 某天共有1 0 0 0 个顾客到商场购买物品，其中有2 0 0 个顾客购买了铁钉，则上述 的关联规则的期望可信度就是2 0 。 4 相关性作用度 相关性定义f 1 9 】：若以x ) 表示事务中x 发生的概率，p ( x ，】，) 表示x 、y 同 时发生的概率。将如下公式： c o r r x ，l r = p ( x y ) p ( x ) p ( y ) 定义为x 、y 的统计相关性。对于挖掘规则xjy ，若c o r r x ，y = 1 ，说明x 的 出现对y 的出现并无直接关系，我们不需要这个规则；当c o r r x ，y 1 时，说明 x 的出现和y 的出现正相关，起促进作用，这个正是我们在市场分析时候感 兴趣的；当c o r r x ，y 。1 时，x 的出现和y 的出现负相关，起阻碍作用。 如果我们把上式变形，则 名= p ( x y ) p ( x ) p ( y ) = p ( yx ) p ( y ) = c o n f ( xj 】，) s u p ( y ) 这样就可以把c o r r x 。y 看成是x 条件下】，出现的概率与不考虑x 条件下】， 出现概率的比值，即置信度与期望可信度的比值。 有些文献也称其为作用度( l i f t ) ，它描述的是a 的出现对b 的出现的影响 程度，反映的是关联规则的有效性。 用p ( a ) 表示事物中出现物品集a 的概率，用p ( b i a ) 表示在出现物品 集a 的事务中，出现物品集b 的概率，则以上四个参数可用表3 1 表达： 表3 - 1关联规则参数说明表 评估指标描述公式作用门槛值 支持度 事务a 、b 同时出现的度量规则的有用 最小支持 p ( a n 占) ( s u p p o r t )概率 性 度m i n _ s u p 置信度事h a 出现的前提下，度量规则的确定 最小置信 p ( bi 彳) ( c o n f i d e n c e ) 事务b 出现的概率性 度m i n c o n 期望可信度 度量事务包含b 事务b 出现的概率 p ( 口) ( e x p e c t e d 曲d e f 蛐的确定性 相关度作用度，兴趣度置信度对期望可信度量事务包含a 与事最小兴趣 p ( bi 彳) p ( b ) ( c o r r l i r i n t )度的比值务嗡的髓撇 度m i n _ i n t 1 6 山东大学硕士学位论文 3 1 3 几种典型的兴趣度模型 1 基于差异思想的兴趣度模型 关联规则xjy 给出信息的正确度是由它的置信度c 0 矿( x 】，) = s u p p ( x uy ) s u p p ( x ) 决定的；然而所有原始记录支持该规则所反映信息的比 例可以用原始记录右部】，的支持度s u p p g ( y ) 来表示， 即 s u p p r ( y ) = ( iyl id1 ) ，则可以定义规则x y 的兴趣度为： i n t e r e s f ( xj】，)：conf(x j y)-suppr(y) 、。 m a x ( c o n f ( xj 】，) ，s u p p r ( y ) ) 显然，置信度c d 矿( x r ) 与支持度s u p p r ( y ) 之间并不存在任何数量关 系，然而计算出来的兴趣度i n t e r e s t ( xj 】，) 可能大于0 也可能小于0 。引入的 分母m a x ( c o n f ( xj 】，) ，s u p p r ( y ) ) 是一个标准化因子，使得兴趣度的值介于一l 和1 之间，以方便对问题的讨论。但是，兴趣度i n t e r e s t ( xj 】，) 把规则的支持 度与置信度联系了起来。s u p p r ( y ) 相当于事件y 发生的概率p ( y ) ， 国矿( x