（计算机软件与理论专业论文）数据挖掘技术在出租车交通事故分析中的应用研究.pdf

。j ； r _ 1 ， at h e s i sf o rt h ed e g r e eo fm a s t e ri n c o m p u t e rs o f t w a r ea n dt h e o r y ，“l o + 一一一 a p p l i c a t i o nr e s e a r c h o nd a t am i n i n g t e c h n o l o g y i nt a x it r a f f i ca c c i d e n t s b yd uc h u n s u p e r v i s o r ：a s s o c i a t e p r o f e s s o rb a oy u b i n n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 7刚96洲0m 4 眦8ii1y 卜k b 二 l 东北大学硕士学位论文摘要 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：稍 ，v 签字日 期：移册占7 罗 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年日 学位论文作者签名：夼者 签字日期：翻加吕z 多 导师签名：幺缈形 ， 签字日期：硼7 东北大学硕士学位论文 摘要 数据挖掘技术在出租车交通事故分析中的应用研究 摘要 随着经济的发展和人们生活水平的提高，出租车占城市客运交通的比重越来越大， 同时大量出租车交通事故也随之而来，因此必须加强出租车行业各方面管理，尽量减少 交通事故的发生。数据库技术己经在交通管理领域得到充分的应用，使得交通领域尤其 是交通事故领域积累了海量的数据，而在这些数据中存在着大量有价值的、有潜在关联 关系的数据。将数据挖掘技术应用在交通领域，通过数据挖掘技术对交通事故数据进行 挖掘，成为国内外关注的一个重要科研课题。本文的主要工作是对数据挖掘中的聚类分 析和关联规则技术进行研究，并将其应用到出租车交通事故分析系统中。 首先，结合国内外研究的现状和发展趋势，系统论述了数据挖掘技术及其算法。根 据出租车交通事故的特点，有选择地构建数据挖掘模型。然后，详细介绍了系统的需求 分析和系统设计，重点讨论了在数据预处理阶段，对事故数据进行处理的各种方法。在 此基础上，具体介绍了实现的过程和意义。 本文研究核心是如何将数据挖掘技术应用到出租车交通事故分析系统中，深入研究 聚类分析中的k - m e a n s 算法和关联规则中的a p r i o r i 算法，分析算法中存在的问题，对 原算法进行了改进，是本文的一个创新点，实验证明改进算法优于原算法。本文通过利 用关联规则和聚类分析的改进算法对交通事故数据进行数据挖掘，并对挖掘结果进行了 分析，验证了系统有效性，达到了实验的目的。 关键词：出租车交通事故；数据挖掘；关联规则；聚类分析；a p r i o r i 算法 一i i 一。 东北大学硕士学位论文 a b s t r a c t a p p l i c a t i o nr e s e a r c ho nd a t am i n i n gt e c h n o l o g yi nt a x i t r a f f i ca c c i d e n t s a b s t r a c t w i t ht h ed e v e l o p m e n to fe c o n o m ya n dt h ei m p r o v e m e n to f p e o p l e sl i v i n gs t a n d a r d ， t a x i e st a k eal a r g ep r o p o r t i o no fc i t yp a s s e n g e rt r a n s p o r t a t i o n m e a n t i m e ，al o to ft r a f f i c a c c i d e n t sc o m e t h e r e f o r e ，t h et a x im a n a g e m e n tm u s tb er e i n f o r c e da n dt h eh a p p e n i n go ft h e t r a f f i ca c c i d e n t sm u s tb e1 e s s o n d a t a b a s eh a sb e e nf u l l yu s e di nt r a f f i cm a n a g e m e n ta r e a s oal a r g en u m b e ro fd a t aa r ea c c u m u l a t e di nt h i sa r e a w h a t sm o r e al o to fd a t aw h i c ha r e v a l u a b l ea n dh a v ep o t e n t i a la s s o c i a t i o ne x i s ti nt h ed a t a b a s e i th a sb e c o m ea l li m p o r t a n t s c i e n t i f i cr e s e a r c ht a s kt oa p p l yd a t am i n i n gt e c h n o l o g yt ot r a n s p o r t a t i o na r e aa n du s et h e t e c h n o l o g yt om i n et h et v d 伍ca c c i d e n t sd a t aa n dh a sr e c e i v e dm u c ha t t e n t i o nf r o mb o t h d o m e s t i cc o u n t r ya n da b r o a d t h em a i n p a r to ft l l et h e s i si st or e s e a r c ht h ec l u s t e r i n ga n a l y s i s a n da s s o c i a t i o nr u l eo ft h ed a t am i n i n gt e c h n o l o g ya n dt oa p p l yt h e mt ot r a f f i ca c c i d e n t s a n a l y s i ss y s t e m f i r s t l y ，t h r o u g hc o m b i n i n gt h ep r e s e n ts i t u a t i o na n di t sd e v e l o p i n gt r e n do fb o t h d o m e s t i ca n d a b r o a d ，t h ed a t am i n i n gt e c h n o l o g ya n di t s a l g o r i t h ma r e d i s c u s s e d s y s t e m a t i c a l l y a c c o r d i n gt ot h ec h a r a c t e r i s t i co ft a x it r a f f i ca c c i d e n t s ，d a t am i n i n gm o d e li s c o n s t r u c t e d t h e nt h ed e m a n da n a l y s i so ft h es y s t e ma n ds y s t e md e s i g na r ep r e s e r t e di nd e t a i l e m p h a s i si sl a i do nm e t h o d su s e dt op r o c e s st h ea c c i d e n td a t ao nt h ed a t ap r e p r o c e s s i n gs t a g e t h ec o r eo ft h et h e s i si sh o wt oa p p l yd a t am i n i n gt e c h n o l o g yt ot a x it r a f f i ca c c i d e n t a n a l y s i ss y s t e m k m e a n sa l g o r i t h mf o rc l u s t e r i n g a n a l y s i sa n da p r i o r ia l g o r i t h mf o r a s s o c i a t i o nr u l ea r ed e e p l ys t u d i e d t h ei n n o v a t i v ep a r to ft h e t h e s i si st h a tt h ep r o b l e m s e x i s t i n gi na l g o r i t h ma r ea n a l y z e da n dt h eo r i g i n a la l g o r i t h mi si m p r o v e d t h ee x p e r i m e n t p r o v et h a tt h ei m p r o v e da l g o r i t h mi sb e t t e rt h a nt h eo r i g i n a lo n e t h ea s s o c i m i o nr u l ea n dt h e i m p r o v e do nc l u s t e r i n ga n a l y s i sa l g o r i t h mw e r eu s e dt om i n et h et r a f f i ca c c i d e n td a t aa n dt h e r e s u l t sa r ea n a l y z e d t h ev a l i d i t yo ft h es y s t e mi sp r o v e da n dt h ep u r p o s eo ft h ee x p e r i m e n ti s r e a c h e d k e y w o r d s ：t a x it r a f f i ca c c i d e n t s ；d a t am i n i n g ；a s s o c i a t i o nr u l e ；c l u s t e r i n g ；a p r i o r i a l g o r i t h m i i i 一 篓” 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t 一i i i 第1 章绪论1 1 1 出租车在城市交通中的地位1 1 2 出租车交通事故国内外研究现状1 1 3 系统开发的必要性2 1 4 采用数据挖掘技术的意义3 1 5 论文的主要内容4 1 6 本文的结构4 第2 章数据挖掘简介5 2 1 数据挖掘的概念5 2 2 数据挖掘的功能5 2 3 数据挖掘的过程6 2 4 关联规则挖掘7 2 。4 1 关联规则的算法及演化8 2 4 2 多维多层的关联规则1o 2 5 聚类分析概述1 1 2 6 数据预处理1 2 2 6 1 数据预处理基本过程12 2 6 2 数据转换与清理l3 2 6 3 数据集成1 4 2 6 4 数据变换1 4 2 6 5 数据归约1 4 2 7 数据挖掘应用和存在问题1 5 2 8 本章小结1 7 第3 章需求分析与系统设计1 9 3 1 交通事故分析系统的需求分析1 9 3 2 系统设计2 0 一一 东北大学硕士学位论文 目录 3 2 1 系统结构2 0 3 2 2 系统功能设计2 2 3 2 3 系统实施方案2 4 3 2 4 数据库设计2 5 3 3 系统配置2 6 3 4 本章小结2 6 第4 章交通事故的聚类分析2 7 4 1 用于聚类分析的数据预处理2 7 4 1 1 数据清理方法2 7 4 1 2 噪声数据方法2 7 4 1 3 数据归约方法2 8 4 2 基于属性聚类的应用2 8 4 2 1 单属性聚类分析3 0 4 2 2 多属性聚类分析3 1 4 3 本章小结3 3 第5 章交通事故的关联规则发现3 5 5 1a p r i o r i 算法介绍3 5 5 2 经典的发现频繁项目集算法3 5 5 3 关联规则生成算法3 6 5 4 算法改进思想3 8 5 5 改进的a p r i o r i 算法正确性证明4 0 5 6 本章小结4 1 第6 章出租车交通事故分析系统的实现4 3 6 1 聚类分析的实现4 3 6 1 1 实现的关键技术4 3 6 1 2 聚类分析的实现4 6 6 2 关联规则的实现4 7 6 3 挖掘工作的指导意义5l 6 4 本章小结5 2 第7 章总结与展望5 3 7 1 本文工作的总结5 3 7 2 进一步的工作。5 3 参考文献5 5 j g 【谢：5 8 一v 一 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 出租车在城市交通中的地位 近年来，随着经济的发展和人们生活水平的提高，出租车占城市客运交通的比重越 来越大，出租车已经成了城市中人们出行的重要交通工具。由于受人口数量和城市面积 的限制，在小城市中构筑四通八达、方便快捷的公交网是不现实的。而出租车由于不受 线路和站点的限制，无论在大街，还是小巷，以其灵活的运营方式，方便快捷的运输服 务，成为大家出行的首选。出租车已成为现代城市中不可缺少的一个行业，是城市流 动的窗口，它直接体现出城市的文明程度和信用程度。出租汽车以其绝对多数的保有量 和在城市公共交通系统中的作用，近几年己成为热点话题。出租汽车是城市公共交通中 最为活跃的客运交通方式，它以其方便、快捷、和服务面广的特点区别于其它公交方式。 它虽属于城市公共交通的辅助系统，但一定程度上是代表城市现代化水平的标志之一。 出租车在城市的经济繁荣、方便居民生活、促进国内外交流、发展城市旅游事业等方面， 起到了积极的推动作用，在未来城市公共交通系统中，仍会继续发挥独特的、不可代替 的作用。 与大城市相对完善的出租车市场相比，中小城市因经济发展水平和市场需求的差 异，出租车市场还很不完善，还存在很多的问题和挑战。由于出租车行业的迅速发展， 给城市的建设带来一些负面影响，例如：胡乱收费、欺诈顾客、城市交通堵塞、车辆乱 停乱放、城市的大气污染加剧等，尤其是出租车交通事故的频繁发生，给社会和民众带 来了太多的灾难，交通事故带来的严重后果和给整个社会带来的负面影响远远超过了事 故本身。究竟是什么原因导致出租车交通事故的频繁发生呢? 如何客观、科学地分析， 找出事故的真正原因，是目前迫切需要解决的问题。 1 2 出租车交通事故国内外研究现状 许多发达国家通过完善交通安全法律体系，调整交通安全政策，明确交通安全责任， 强化政府的交通安全管理职能，重点加强驾驶员的安全意识，提高驾驶技术，大力推广 和使用新技术、新方法，全面提高道路、车辆的安全性，交通安全状况大为改观。在最 近二、三十年内，交通事故总量下降并渐趋稳定。进入二十一世纪后，主要发达国家相 继提出了以预防交通事故n 1 ，降低事故严重性为核心的交通安全政策和预防道路交通事 故的交通安全管理机制，以促进交通安全水平的进一步提高。 国内外关于交通事故影响因素的理论研究主要经历了三个阶段：最早出现也是最简 东北大学硕士学位论文第1 章绪论 单的致因理论是单因素理论，这种理论把事故简单地归结为由一种原因引起，它较偏重 于对人的分析：单因素理论逐渐发展成为多因素理论，该理论广泛地用于各种事故的分 析，认为在道路交通事故分析中，主要应从“人、车、路”三因素着手；国外在2 0 世纪 8 0 年代提出了系统致因理论，该理论以系统的观点对引发事故的多种因素及其关系f 主 要是逻辑关系) 进行研究。 单因素理论不能全面系统地揭示事故发生的规律，但当要寻找事故的主要原因时， 单因素理论的简单直观性非常有用；多因素理论的贡献主要在于使人们改变了对交通事 故成因的单向性、局部性思维，开始从社会整体的角度来考虑交通安全问题，然而多因 素理论的不足在于对因素之间的关系及互相影响考虑不够，没有对因素之间的逻辑关系 进行深入分析。通过对有记载的交通事故成因的分析可以发现，我国交通事故主要是由 人( 占9 3 ) 、车( 占4 ) 两方面原因引起的，而道路、交通、气候、管理等方面原因仅占 3 ，这与其它国家1 6 左右的比例相去甚远。究其原因，主要是在事故处理过程中必 须确定主要责任者，事实上一起交通事故的发生一般说来都是偶然的，往往是由两个或 多个原因共同引起的，其中不乏道路、交通、气候及管理方面的原因。因此有必要对事 故成因进行深入分析，以期确定各影响因素在交通事故产生过程中所起的真正作用 瞳儿3 m 。但是由于与事故发生息息相关的路面状况、车辆系统、人为因素千差万别，错综 复杂，通过事故数据库系统的建立，应用相应的数据挖掘模型，则可高效快捷地发现事 故的新知识和规律，有利于真正从事故中吸取教训畸l 1 3 系统开发的必要性 对于出租车交通事故而言，作为出租车司机，由于工作性质的关系，本身具有很多 优势：作为职业的驾驶人员，驾驶技术非常熟练；出租车就是他的两条腿，始终离不开 车，驾驶时间长，对出租车的性能状况十分了解；长时间工作在一个城市，对道路非常 熟悉等。按常理发生意外交通事故的可能性应该很小，但由于多方面的原因，出租车交 通事故还是接连不断地发生，因此非常有必要分析这类交通事故的原因，尤其是在事故 中肇事司机的各方面的原因。 由于本论文中对出租车交通事故的分析与研究，是建立在大量的交通事故统计数据 的基础上。当地交警支队保存大量的交通事故数据，但数据资料侧重于事故处理，不能 全面反应出交通事故之间内在的联系和规律，因此，在此基础上建立一个基于数据挖掘 的出租车交通事故数据库势在必行。本论文中对朝阳市出租车交通事故分析系统的研究 既是为了应用现代化的信息技术进行交通事故原因分析，也是为了适应交通管理研究的 发展趋势。 综上所述，本论文的研究意义在于： 一2 一 东北大学硕士学位论文第1 章绪论 ( 1 ) 一起具体交通事故的发生往往是由1 到3 个具体诱导因素单独作用或相互作用 而致。例如对于一个发生了大量交通事故的多发地点而言，必然有其内在的规律性，累 计事故诱导因素是多方面的，涉及到道路条件、天气与交通环境状况、车状况、交通参 与者的行为特征等诸方面的因素。即在众多的事故诱导因素中存在某些主导因素，它们 直接或潜在地诱导着交通事故的发生，这是事故多发地点处事故发的直接原因，如果能 够分析出这些原因，减少事故发生的诱因，可以达到减少交通事故的目的。 ( 2 ) 在不同国家、不同城市的交通水平下，交通事故与各影响因素之间的关系是不 确定的，所以对朝阳市有必要提出符合其自身特点的事故与因素之间的关系，而为我市 出租车事故现状的分析和改进对策提供及时有力的支持。 ( 3 ) 建立基于数据挖掘技术的朝阳市出租车交通事故分析系统对于具体分析出租车 行业存在的各种问题，通过出租车管理部门具体管理，达到消除事故隐患，减少事故发 生的目的。 1 4 采用数据挖掘技术的意义 数据挖掘技术可以发现数据中存在的关系和规则，根据现有的数据预测未来的发展 趋势。数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。数据挖掘使数据 库技术进入了一个更高级的阶段，它不仅能对的数据进行查询和遍历，而且能够找出过 去数据之间的潜在联系，从而提高数据的利用价值。 出租车管理部门，在交通事故预防工作中，主要是根据不同时期、不同地点交通事 故的态势做出相对应的管理对策，从管理上把事故压下来。要做到这一点首先要对事故 发生的情况进行数据分析，从中发现规律性的东西，做到有的放矢。交通事故研究主要 建立在大量事故统计分析资料的基础上，由于交通事故难以现场直接观测其发生过程， 需要通过事后的资料分析来研究其发生规律。正因为如此，建立事故分析基础数据资料 系统显得尤为重要。在交通事故数据采集分析统计上，目前主要依靠公安部2 0 0 3 版事 故信息管理系统，具有数据采集、传输、查询和统计功能。从数据采集上来讲，这些数 据的采集工作都是各级部门人为进行的，所以在各级之间采集和统计的数据可能会存在 差异，出现数据缺失或不标准的情况；从数据统计上来讲，系统统计着重于对事故发生 后的经济损失和死伤人数的统计，未能反映出事故发生的条件因素，难以为基层交通事 故预防、处理、决策工作服务。所以，本文主要以分析事故原因为主，分析结果以图表 形式显示，力求为决策者做出决策时提供辅助参考。尤其是作为交通事故最密切的机动 车辆驾驶员，通过分析原因，在管理中加强相应方面的指导，达到减少事故发生的目的。 一3 一 东北大学硕士学位论文第1 章绪论 1 5 论文的主要内容 数据挖掘是数据处理的一个新的热点和前沿研究领域7 1 ，它的研究目标是采用有 效的算法，从大量现有的数据中发现并找出最初未知，可理解的有用知识，并用可理解 的语言方式显示出来。关联规则和聚类规则是数据挖掘研究的两个重要方面。本文使用 数据挖掘中的聚类分析和关联规则分析方法对出租车交通事故原因中的肇事司机相关 属性数据进行了分析，重点研究聚类分析和关联规则分析方法在出租车交通事故中的应 用，在v c + + 环境下完成系统功能的实现，并分析了数据挖掘结果所反映的有价值的信 息，为出租车管理提供参考。在关联规则分析中，采用经典的a p r i o r i 算法，并对算法 进行了改进，通过实验证明，改进的算法在效率上高于原算法。 1 6 本文的结构 在出租车交通事故分析系统中主要研究的是基于聚类和关联规则理论对出租车交 通事故的数据挖掘，实现了对出租车交通事故中主要是肇事司机等有关事故原因方面的 聚类分析和关联规则分析。本文的具体组织结构如下： 第一章首先介绍了研究背景，然后阐述了城市出租车交通事故的国内外的现状，开 发交通事故分析系统的必要性以及数据挖掘技术应用的意义。 第二章介绍了数据挖掘的概念、功能和数据挖掘的过程等基础理论知识，介绍了关 联规则和聚类分析的相关内容，以及在数据预处理方面的理论知识，最后介绍了数据挖 掘的应用和存在的问题。 第三章讨论了出租车交通事故分析系统的需求分析和系统设计。介绍了数据挖掘分 析系统的意义、系统的需求分析、系统设计、数据库的设计、系统开发环境和工具。 第四章介绍了在聚类分析中数据预处理过程采用的方法，接着重点介绍了在多属性 聚类分析过程中，采用的算法和具体步骤。 第五章主要介绍了改进a p f i o r i 算法的改进思想和过程，以及算法的正确性证明和 性能分析。 第六章介绍了交通事故分析系统的聚类分析和关联规则分析的实现过程，并对系统 挖掘的信息以图形方式显示出来，并进行了详细分析，证明了系统的价值。 第七章总结了全文的工作并对系统的下一步工作进行了展望。总结前期工作，阐述 论文的研究成果和存在的很多不足并，对未来的工作提出展望。 一4 一 东北大学硕士学位论文第2 章数据挖掘简介 第2 章数据挖掘简介 2 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ) 是指从大量的、不完全的、有噪声的、模糊的、随机的数据 中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程秘1 。 数据挖掘有以下特点：数据挖掘是对一个真实的、大量的数据源进行的一种操作。数据 挖掘是要发现隐含的、先前未知的信息并且是用户感兴趣的知识。数据挖掘产生的信息 应该是具有潜在价值的，发现的知识要可接受、可理解、可运用，最好能用自然语言表 达结果。 数据挖掘是目前国际数据库和信息决策领域的最前沿研究方向之一，已经引起了学 术界和工业界的广泛关注四1 ，目前研究的主要目标是发展有关理论、方法和工具，以支 持从大量数据中提取有价值的知识和模式。数据挖掘是- - f l 交叉学科，融合了数据库、 人工智能、机器学习、统计学等多个领域的理论和技术。数据库、人工智能和数理统计 是数据挖掘研究的三根强大的技术支柱。数据挖掘的方法和数学工具包括统计学、决策 树、神经网络、模糊逻辑、线性规划等。我国的数据挖掘技术研究开始于9 0 年代中期， 到9 0 年代中后期，初步形成了知识发现和数据挖掘的基本框架。 2 2 数据挖掘的功能 在许多情况下，用户并不知道数据存在哪些有价值的信息知识，因此对于一个数据 挖掘系统而言，它应该能够同时搜索发现多种模式的知识，以满足用户的期望和实际需 要。数据挖掘能够实现的功能n 伽主要有以下五种： ( 1 ) 关联分析 从广义上讲，关联分析( a s s o c i a t i o na n a l y s i s ) 是数据挖掘的本质。既然数据挖掘的目 的是发现潜藏在数据背后的知识，那么这种知识一定是反映不同对象之间的关联。它刻 画了数据库中对象之间的关联及其关联的程度。关联知识反映一个事件和其他事件之间 的依赖或关联。关联规则挖掘是关联知识发现的最常用方法，最著名的是a g r a w a l 等提 出的a p r i o r i 算法及其改进算法。为了发现有意义的关联规则，需要给定两个阈值：最 小支持度( m i n i m u ms u p p o r t ) 和最小置信度( m i n i m u mc o n f i d e n c e ) 。挖掘出的关联规则必 须满足规定的最小支持度，它表示了一组项目关联在一起需要满足的最低联系程度u 。 挖掘出的关联规则也必须满足用户规定的最小置信度，它反映了一个关联规则的最低可 靠度。在这个意义上，关联规则挖掘系统的目的就是从数据库中挖掘出满足最小支持度 一5 东北大学硕士学位论文第2 章数据挖掘简介 和最小置信度的关联规则。关联规则的研究和应用是数据挖掘中最活跃的分支之一，已 经提出了许多关联规则挖掘的理论和算法。 ( 2 ) 分类和预测 分类( c l a s sf i c a t i o n ) 是对数据的过滤、抽取、压缩以及概念提取，是数据挖掘中的一 个重要的目标和任务，在商业上应用较多。分类的目的是学会一个分类函数或分类模型 ( 也常称作分类器) 。分类通常用于预测未知数据实例的归属类别( 有限离散值) ，但在一 些情况下，需要预测某数值属性的值( 连续数值) ，这样的分类称为预澳1 ( p r e d i c a t i o n ) 。分 类模式可以采用多种形式表示，如分类规贝j j ( i f t h e n ) 、判定树、数学公式或神经网络 等。应用于分类知识挖掘的代表性技术有：决策树、贝叶斯分类、神经网络分类、遗传 算法、类比学习和案例学习，以及粗糙集和模糊集等方法。 ( 3 ) 聚类分析 一般把学习算法分成有导师学习和无导师学习两种方式，主要区别是有没有类信息 作为指导。聚类( c l u s t e r i n g ) 是典型的无导师学习算法，一般用于自动分类。聚类就是将 数据对象分为多个类或簇，同一个类中的对象具有较高的相似度，而不同类中的对象差 别较大。聚类按照某个特定标准形成每个类，所形成的类在空间上是一个稠密的区域， 可以导出某些规则。 ( 4 ) 异类分析 一个数据库中的数据一般不可能都符合分类预测或聚类分析所获得的模型，那些不 符合大多数数据对象所构成的规律或模型的数据对象就被称为异类( o u t l i e r ) 。以前许多数 据挖掘方法都在正式进行数据挖掘前就将这些异类作为噪声或意外排除在分析处理范 围之外。但在一些特殊应用场合，如各种商业欺诈行为的自动检测，小概率发生的事件 往往比经常发生的事件更有挖掘价值。对异类数据的分析处理通常就称为异类挖掘。 ( 5 ) 概念描述 概念描述本质上就是对某类对象的内涵特征进行概括，一个概念常常是对一个包含 大量数据的数据集合总体情况的概述。 2 3 数据挖掘的过程 谈到数据挖掘，必须提到另外一个名词：数据库中的“知识发现”( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) 。从数据挖掘的概念可以看出它与k d d 许多重合的地方。 有人说，k d d 在人工智能界更流行，而d a t am i n i n g 在数据库界使用更多。也有人说， 一般在研究领域被称作k d d ，在工程领域则称之为数据挖掘。事实上在现今的文献中， 许多场合，如技术综述等，这两个术语仍然不加区分地使用着。在本文中将数据挖掘看 作是k d d 过程的一个步骤【l 羽。 一6 一 东北大学硕士学位论文 第2 章数据挖掘简介 一般地说，k d d 是一个多步骤的处理过程n 3 儿1 4 1 ，分为问题定义、数据抽取、数据 预处理、数据挖掘以及模式评估等基本阶段。 k d d 过程如图2 1 所示。 知识 图2 1k d d 过程不总图 f i g 2 1k d dp r o c e s s s c h e m a t i cc h a r t 数据挖掘的核心技术是人工智能、机器学习、统计等，但它并非多种技术的简单组 合，而是一个不可分割的整体。数据挖掘是一个多步骤的处理过程，粗略可分为以下四 步： 第一步：问题定义( t a s kd e f i n i t i o n ) 。了解相关领域的有关情况，熟悉背景知识，弄 清用户要求。 第二步：数据收集和预处j 里( d a t ap r e p a r a t i o na n dp r e p r o c e s s i n g ) 。首先，根据要求从 数据库中收集相关的数据。然后对前一阶段产生的数据进行再加工，检查数据的完整性 及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补。 第三步：数据挖掘算法执行。运用选定的数据挖掘算法，从数据中提取用户所需要 的知识，这些知识可以用一种特定的方式表示或使用一些常用的表示方式。 第四步：知识的解释和评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 。将发现的知识以用户能 理解的方式呈现，如某种规则，再根据实际情况对知识发现过程中的具体处理阶段进行 优化，直到满足用户要求。 整个挖掘过程是一个不断反馈的过程。比如用户在挖掘途中发现选择的数据不太 好，或使用的挖掘技术产生不了期望的结果，这时用户需要重复先前的过程，甚至重新 开始。 2 4 关联规则挖掘 关联规则数据挖掘( 简称关联规则挖掘) 是数据挖掘的一种研究方法n 目。目的是找 一7 东北大学硕士学位论文第2 章数据挖掘简介 出数据库中不同数据项集之间隐藏的关联关系n 剐。a g r a w a 等人于1 9 9 3 年首先提出了挖 掘顾客交易数据库中项集间的关联规则问题，从大量交易数据库中不同商品之间的关联 联系，找出顾客购买行为模式，可以应用于商品货架设计、库存安排以及根据购买模式 对用户进行分类等。 2 4 1 关联规则的算法及演化 由于关联规则发现的主要对象是事物型数据库，设i = i i ，i 2 ，i m ) 是项的集合。 设与任务相关的数据d 是数据库事务的集合，其中每个事务t 是项的集合，使得t c i ， 每一个事务有一个标识符，称作t i d 。设a 是一个项集，事务t 包含a 当且仅当a c t 。 关联规则是形如a j b 的蕴涵式，其中a c i ，b c i ，并且a n b = 。规则a j b 在 事务集d 中成立，具有支持度s ，其中s 是d 中事务包含a ub ( 即a 和b 二者) 的百分 比，它是概率p ( a w b ) ，如公式2 1 所示。规则a j b 在事务集d 中具有置信度c ，如 果d 中包含a 的事务同时也包含b 的百分比是c 。这是条件概率p ( bla ) ，如公式2 2 所示。既是 s u p p o r t ( ajb ) 2 p ( a u b )( 2 1 ) c o n f i d e n c e ( ajb ) = p ( bia )( 2 2 ) 同时满足最小支持度阈值( m i n和最小置信度阈值的规则称作强规 则。前者即用户规定的关联规则必须s 满u p 足) 的最小支持度，它表( m 示i n 了e o n f 组) 项集在统计意义 上的需满足的最低程度；后者即用户规定的关联规则必须满足的最小可信度，它反映了 关联规则的最低可靠度。 项的集合称为项集( i t e m s e t ) 。包含k 个项的集合称为k 项集。例如集合 a g e ，i n c o m e 是一个2 项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或 计数。如果项集的出现频率大于或等于m i ns u p 与d 中事务总数的乘积，认为项集满足 最小支持度m i ns u p ，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。频繁k - 项集的集合通常记作 l k 。 a g r a w a l 等人于1 9 9 3 年提出了一个挖掘顾客交易数据库中项集间的关联规则的重 要方法，a p r i o r i 算法。该关联规则在分类上属于单维、单层、布尔关联规则，其核心是 基于两阶段频集思想的递推算法，找出所有频繁项集和由频繁项集产生强关联规则n 们。 这两步中，第二步最容易。挖掘关联规则的总体性能由第一步决定。第一步是近年来关 联规则挖掘算法研究的重点。 a p r i o r i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法n 8 1 ，使用一种逐层 搜索的迭代方法：k 项集用于搜索( k + 1 ) 项集。首先，找到频繁l - 项集的集合，记作l l 。 一8 一 东北大学硕士学位论文 第2 章数据挖掘简介 l l 用于找到频繁2 项集的集合l 2 ，而l 2 用于找l 3 ，如此下去，直到不能找到频繁k - 项 集，每一次搜索都需要扫描一次数据库，为提高频繁项集逐层产生的效率，一般做法是 利用a 研o r i 性质压缩收缩空间。 a p f i o f i 算法具体过程可以描述为：第一步从包含每个项的候选1 项集( c 1 ) 中找出频 繁1 项集的集合l l 。第二步利用l k 1 连接产生候选c k ，并根据a p r i o r i 性质删除那些具 有非频繁子集的项集的候选项集。接下来，扫描数据库，统计候选项集的支持计数，与 最小支持计数相比，形成频繁集l k 。 在找到了事务数据库中的所有频繁项集后，利用这些频繁项集可以产生关联规则， 强关联规则是满足最小支持度和最小置信度n 引。对于置信度，可以用公式2 3 ，其中条 件概率用项集支持度计数表示。 s u pp o r tc o u n t ( au b 、l c o n f i d e n c e ( a b ) = p ( a | b ) = 葫荔赢而广 ( 2 3 ) 过程： 对每个频繁项集l ，产生l 的所有非空子集。 对于的每个非窄子集supp o r t _ c o u n t ( a u b)minl ，2 厂， 对于 的每个非空子集s u p p o _ r t 磊历n 云t 彳广m 一形， c d “i 以i 则输出规则“s ( 1 s ) ”，其中m i nc o r f f 是最小置信度阈值。 s u p p o r t是d 中包含项集的事务数。 由于规则c o 由u n 频t ( 繁s ) 项集产生，每个规s 则都自动满足最小支持度。 虽然a p r i o f i 算法自身己经进行了一定的优化，但从执行过程可以看到，在每一次 产生候选项集时都要扫描一遍数据库，而用于关联规则挖掘的数据库的规模通常是非常 大的，所以这样就无形之中增加了额外的开销，影响了算法的效率啪3 。为了提高却a p f i o f i 算法的有效性，人们相继提出了一些优化的方法。 ( 1 ) 基于散列的技术 该算法由p a r k 等在1 9 9 5 年提出，通过实验发现寻找频繁项集的主要计算是在生成 频繁2 一项集l 2 上，p a r k 就是利用这个性质引入散列技术来改进产生频繁2 一项集的方 法昭。当扫描数据库中每个事务，由c l 中的候选1 一项集产生频繁1 项集l l 时，对每个 事务产生所有的2 项集，将它们散列到散列表结构的不同桶中，并增加对应的桶计数， 在散列表中对应的桶计数低于支持度闽值的2 项集不可能是频繁2 项集，可从候选项集 中删除，这样就可大大压缩了要考虑的k 项集( 特别是当k = 2 时) 。 ( 2 ) 事务压缩 a g r a w a l 等提出压缩进一步迭代扫描的事务数的方法。一个基本的原理就是不包含 任何k 项集的事务不可能包含任何附1 ) 项集。因此这样的记录出现时，可以给其加上 一9 一 东北大学硕士学位论文 第2 章数据挖掘简介 标记或从交易数据库中移出，以后为产生频繁j 项集0 k ) 而进行的数据库扫描就无需在 对这些记录进行扫描分析了。 ( 3 ) 划分 s a v a s e r e 等设计了一个基于划分的算法，它只需要再次数据库扫描，以挖掘频繁项 集。第一遍，算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块 并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算 这些项集的支持度。第二遍，评估每个候选的实际支持度，在候选项集中找出全局频繁 项集。 ( 4 ) 动态项集计数 b r i n 等人给出该算法。动态项集计数技术将数据库划分为标记开始点的块。不象 a p f i o f i 仅在每次完整的数据库扫描之前确定新的候选，在这种方法中，可以在任何开始 点