（计算机应用技术专业论文）决策树分类在交通数据分析系统中的应用研究.pdf

摘要 智能交通系统( i t s ) 已经成为2 1 世纪交通运输体系的发展趋势，其实质是 对交通信息的分析、共享和综合利用。数据挖掘，简单地说，就是从大量数据中 提取或“挖掘”知识。分类分析是数据挖掘的一个重要组成部分，决策树分类又 是分类分析中最为典型的方法。在交通数据分析中使用决策树分类技术，并学会 一个分类模型，能够有效地利用海量交通数据进行交通状况的分析和预测。 交通拥塞是困扰城市交通的一种常见交通现象。在历史交通拥塞相关数据的 基础上使用数据分类技术，能很大程度上去发现城市交通中的拥塞知识，从而做 到对拥塞的估计和预防。发现交通拥塞知识首先必须学会交通拥塞分类模型，我 们把这种分类模型称之为“交通拥塞分类器”。 基于以上理论，本文着重于分类算法及在此基础上建立的“交通拥塞分类器” 的研究。在简要介绍了数据挖掘与分类技术的基本知识后，基于上海安装的交通 数据采集分析系统s c a t s 采集的交通数据，本文首先分析了交通数据的特点并 着重讨论了交通数据的预处理技术，在通常的只分析动态交通数据流属性的基础 上增加了对城市道路本身的静态地理空间属性的分析。然后，讨论了急切分类决 策树算法c 4 5 ，针对c 4 5 算法构造分类模型时间开销较大，而且时效性较差的 缺点，提出了一种基于懒散分类的改进算法：l d t a 。该算法的思想是将懒散的 基于示例的方法和c 4 5 分类方法有机的进行结合，从而可以充分发挥它们的优 点，克服各自的缺点。这样就有效地提高了算法的时效性、运算速度，而又有较 高的分类精确度。另外，本文从减少分类器分类复杂度、提升分类性能的角度出 发，提出了构建“二层交通拥塞分类器”的思想，即分类器采用分别对静态地理 空间属性和动态交通属性进行分类的分类器结构。实验表明，该分类器在对交通 进行拥塞分类预测时达到了较好的效果。 最后，本文讨论了“交通数据分析和查询系统”，分析了其中使用的交通数 据仓库模型以及系统的结构和功能，并就其中“二层交通拥塞分类器”的实际应 用情况作了介绍。 关键词：数据挖掘，懒散分类，c 4 5 ，s c a t s ，决策树，分类器，交通拥塞，预 处理，数据仓库 a b s t r a c t i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ( i t s ) r e p r e s e n t st h em a i nd e v e l o p m e n tt r e n do f t r a n s p o r t a t i o na r c h i t e c t u r ei n21s tc e n m r y a n a l y s i s ，s h a r i n ga n di n t e g r a t i o no ft r a f f i c i n f o r m a t i o ni st h ee s s e n t i a lo fi t s d a t am i n i n g ，w h i c hi sd e f m e da st h ep r o c e s so f d i s c o v e r i n gp a t t e r n si nm a s sd a t a ，i sa f o c u so fm u l f i d i s c i p l i n er e s e a r c h c l a s s i f i c a t i o n i sa ni m p o r t a n tp a r tf o rd a t am i n i n gw h i l ed e c i s i o nt r e ei st h em o s tt y p i c a lm e a n s c l a s s i f i c a t i o n w i t ht h eu s eo f d e c i s i o nt r e ei nt r a f f i cd a t aa n a l y s i s ，w ec a na n a l y z ea n d p r e d i c tt r a f f i cs t a t u se f f i c i e n t l yb yl e a r n i n gac l a s s i f i c a t i o nm o d e l t r a f f i cj a w li st h ep r e v a l e n tp h e n o m e n ai nc i t yt r a f f i c d a t ac l a s s i f i c a t i o no nt h e b a s i so fr e l a t e dh i s t o r i c a lt r a f f i cd a t ac a nd i s c o v e rk n o w l e d g eo ft r a f f i cj a ma n d p r e d i c t i t i nt h ep r o c e s so fk n o w l e d g ed i s c o v e r i n g ，t h ef i r s t s t e p i st ol e a r na c l a s s i f i c a t i o nm o d e l ，w h i c hi sc a l l e dt j c ( t r a f f i cj a mc l a s s i f i e r ) b a s e do na b o v er e a s o n s ，t h i sp a p e rc o n c e n t r a t e so nc l a s s i f i c a t i o na l g o r i t h ma n d t h er e s u l t i n gt j cb a s eo ni t a f t e ri n t r o d u c e sb a s i ck n o w l e d g eo fd a t am i n i n ga n d c l a s s i f i c a t i o nt e c h n i q u e sb r i e f l y , t h i sp a p e rf i r s ta n a l y s e st r a f f i cd a t aa t t r i b u t e sa n di t s p r e p r o c e s s i n gt e c h n i q u e sb a s eo nt r a f f i cd a t ac o l l e c t e db ys c a t sw h i c hh a sb e e n e q u i p p e di ns h a n g h a i i na t t r i b u t e st h a t sb e e na n a l y s e d ，s t a t i cs p a c ea t t r i b u t e so f r o a dn e t w o r ki sa t t a c h e db e s i d e sd y n a m i ct r a f f i ca t t r i b u t e s t h e n ，w ed i s c u s st h ee a g e r c l a s s i f i c a t i o na l g o r i t h mc 4 5 b e c a u s eo ft h ed i s a d v a n t a g e so fc 4 5 ，p r o p o s e da r e f i n e da l g o r i t h m ：l d t a t h eb a s i ci d e ao f t h i sa l g o r i t h mi st oc o m b i n eb o t ht h ec 4 5 a l g o r i t h ma n dl a z yc l a s s i f i c a t i o na l g o r i t h mb a s e do ne x a m p l ei no r d e rt ot a k e a d v a n t a g eo ft h e i rs t r o n g p o i n tw h i l ed i s c a r d t h e s h o r t c o m i n g s t h u s ，p r e f e r a b l y c l a s s i f i c a t i o np r e c i s i o nr e s u l tc a nb eg o tw i t ht h ei m p r o v e m e n to fs p e e d b e s i d e s ，i n o r d e rt od e c r e a s ec l a s s i f i c a t i o nc o m p l e x i t ya n di m p r o v ep e r f o r m a n c eo fc l a s s i f i e r , t l t j c ( t w ol a y e rt r a f f i cj a mc l a s s i f i e r ) i sp r o p o s e dw h i c hc l a s s i f i e ss t a t i c g e o g r a p h i cs p a c e a t t r i b u t e sa n dd y n a m i ct r a f f i ca t t r i b u t e s h i e r a r c h i c a l l y a n d r e s p e c t i v e l y e x p e r i m e n t ss h o wt h a tb e t t e rr e s u l tc a n b eg o tw i t l lt h i sc l a s s i f i e ri nt h e c l a s s i f y i n go f t r a f f i cj a l t l f i n a l l y , w ed i s c u s st h et r a f f i cd a t aa n a l y s i sa n dq u e r ys y s t e ma n da n a l y s ei t s s t r u c t u r e ，f u n c t i o n sa n dd a t aw a r e h o u s em o d e l ，a l s ow ei n t r o d u c et h ea p p l i c a t i o no f t l t j ci nt h es y s t e m k e yw o r d ：d a t am i n i n g ，l a z yc l a s s i f i c a t i o n ，c 4 5 ，s c a t s ，d e c i s i o nt r e e ，c l a s s i f i e r t r a f f i cj a m ，p r e p r o c e s s ，d a t aw a r e h o u s e i i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：龇日期逊：1 侈 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留 论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容。 ( 保密的论文在解密后应遵守此规定) 签名：滥导师签名：逻数 日期：声玎；f 弓 上海大学硕士学位论文 ! 坠! ! 塑! 型! 煎! ! 垒! ! 坚坐! 皇塑g ! 型望里! ! 型型 第1 章绪论 1 1 研究背景与意义 随着人类社会的发展，人们面临着越来越复杂的社会生活环境。从日益复 杂的社会生活环境中提取广泛适用的知识和规则，并应用到实际生活中去，对 改善人们的生活质量，缓解各相关职能部门的管理压力具有极为重要的意义。 在城市生活中，交通问题是涉及城市居民民生的主要问题。交通状况的好 坏，人们出行是否便利，都直接影响到城市的发展，也影响到城市居民的生活 舒适程度。在这种情况下，智能交通系统( i n t e l l i g e n tt r a n s p o r ts y s t e m ，简称1 t s ) 应运而生【l 。”。智能交通系统应用电子信息技术，为城市交通的分流，车辆的导 航，交通状况的预测，提供了一种高效高质的解决方案。目前，世界范围内的 很多大城市都纷纷致力于智能交通系统的应用和研发。但是，交通问题本身的 复杂性决定了智能交通系统的发展必将是一个任重而道远的过程。智能交通系 统中的一个核心问题是交通数据的分析，因为城市交通行为在一定程度上的可 再现性，所以通过对历史交通数据进行总结和归纳，能有效地对实时交通或未 来交通状况做出预测，从而引导交通更加合理地运行。 随着数据挖掘技术的发展，越来越多的专家学者期望在交通数据分析中有 效地结合传统的分析技术和新兴的数据挖掘技术对交通状况进行分析和预测。 数据挖掘是一门广义的交叉学科，涉及的主要学科有数据库、人工智能、数理 统计、可视化、并行计算等。数据挖掘技术从一开始就是面向应用的。它不仅 是面向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃 至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间 的相互关联，甚至利用已有的数据对未来的活动进行预测。分类分析是数据挖 掘领域最为常见的技术之一，它的一些主要技术如决策树等在各个领域内都有 广泛的应用前景。在数据分析领域，依靠分类技术可以得出有效的知识，并用 于数据的预测。在对数据的分类中，采用什么样的算法以及如何构建一个有效 的分类器是数据分类挖掘中的核心问题。 本文针对交通数据的特点，主要研究了分类算法的改进，在此基础上提出 了构建依靠交通空间属性和动态交通属性二层属性的二层交通数据分类器思 想，并实现了相应的分类器，将其应用于交通数据分析系统中。 第1 页 上海大学硕上学位论文 垡! ! ! ! ! 匹型! ! ! ! ! n 塑i ! ! 坠磐吐坠堕! ! 翌! ! 盟 1 2 国内外研究现状 k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会 议上 “1 。由美国人工智能协会主办的k d d 国际研讨会规模由原来的专题讨论 会发展到国际学术大会，研究重点也逐渐从发现方法转向系统应用，并且注重 多种发现策略和技术的集成，以及多种学科之间的相互渗透。其他内容的专题 会议也把数据挖掘和知识发现列为议题之一，成为当前计算机科学界的一大热 点。 伴随着对数据挖掘研究的不断深入，数据挖掘在智能交通系统与交通数据 分析这一领域中也取得了卓越的成就，例如澳大利亚使用改进的线性预测算 法实现了机场快速公交车辆行程时间预测系统。日本的智能交通系统中采用了 预测、分类等多种数据挖掘技术，能够向装备车载导航系统的汽车提供道路状 况、行车时间等多种交通信息并能蟛向司机推荐以最短旅行时间到达目的地的 线路，提高行车方便性，分散交通流量，缓解交通拥塞j 。 目前，智能交通系统在国内的应用和研究也正在积极地展开，如何合理、 有效地在传统的交通数据分析技术的基础上应用数据挖掘技术正纳入许多专家 学者的视线，在国内外的刊物上也发表了些与此相关的论文。但是，总体而 言，在国内智能交通领域的数据挖掘研究尚起步未久，在智能交通数据分析领 域，依靠的手段仍以传统的数据统计理论和多维数据分析理论为主。 1 3 项目背景与主要研究内容 1 3 1 项目背景 本文的课题来源于上海科臻咨询有限公司，是该公司的“交通数据分析和 查询系统”项目的组成部分。“交通数据分析和查询系统”是在充分分析国内外 信息技术发展趋势的基础上提出的，符合当前上海信息化科技工作的需要，从 而保证了项目的正确研究开发方向以及技术上的可行性。系统利用上海市交通 数据采集及分析系统( s c a t s ，s y d n e yc o o r d i n a t e d a d a p l i v ef r a f f i cs y s t e m ，悉 尼自适应交通控制系统) 采集的交通数据，运用多种数据分析手段进行道路状 况分析、交通拥塞预测等任务。其主要功能包括历史交通状况分析、实时交通 状况分析、路段拥塞预测、行程时间预测及交通信息发布等几个部分。 本文的研究成果将能应用于“交通数据分析和奄询系统”中，并有望和科 臻公司自主研发的车辆导航设备结合起来，在城市交通导航中发挥作用。 臻公司自主研发的车辆导航设备结合起来，在城市交通导航中发挥作用。 第2 丽 上海大学硕士学位论文 ! 竖! ! ! 臣! 业坐! j 鲤! ! ! i ! 垫些坠! ! i ! ! ! ! ! 壁 1 3 2 主要研究内容 本文主要对数据挖掘在智能交通数据分析中的应用进行了探讨，着重论述 了交通数据的分类技术。主要的工作和研究内容如下： ( 1 ) 交通数据的预处理 在用数据挖掘技术对交通数据进行分析和挖掘的的过程中，数据的准备是 一个核心环节。因此，花了大量时间分析交通拥塞状况的特点，找出了影响交 通拥塞的关键属性，提出了整合空间数据和动态采集数据共同对交通拥塞进行 分析的方法。并在此基础上，使用数据预处理技术，构建了适应拥塞挖掘的交 通数据仓库。 ( 2 ) 分类算法的改进 用分类技术对交通数据进行分析预测，其关键是选取合适的分类算法。分 类算法可以分为急切分类算法和懒散分类算法，针对急切分类算法构造分类模 型时间丌销较大，而且时效性较差的缺点，本文提出了一种结合懒散分类的改 进算法l d t a 。该算法的思想是将懒散的基于示例的方法和c 4 5 分类方法有机 的进行结合，从而可以充分发挥它们的优点，克服各自的缺点。这样就有效地 提高了算法的时效性、运算速度，而又有较高的分类精确度。 ( 3 ) 用于拥塞分类及预测的交通数据分类器的设计及实现 数据分类是数据挖掘的一个重要方面，其核心内容是学会一个分类函数或 分类模型( 也常常称作分类器) ，该模型能把数据库中的数据项映射到给定类别 中的某一个。所以，要使用分类技术去得到交通拥塞规则，关键就在于构建一 个适用的交通数据分类器。基于这个目的，在工作中研究了交通数据分类器的 构建技术，对其工作的流程及实现方法进行了深入地探讨。 ( 4 ) 交通数据分类器的训练及测试 按照二层分类器的思想建立分类器后，必须证明该分类器是合理的、有效 的。因此，在工作中使用准备好的交通拥塞数据对分类器进行了训练，并提取 了分类模式。对交通拥塞数据的交叉验证表明，该分类器达到了设计要求。 第3 页 上海大学硕士学位论文 ! 生! ! ! g 翌i 坠坠! ! ! ! ! ! ! 生! ! ! ! g ! 型型! ! ! ! ! ! ! 型 第2 章智能交通数据分析与数据挖掘 数据挖掘技术的发展为数据分析和预测提供了一种强有力的解决方案。目 前，智能交通系统中交通数据分析的传统方法是统计理论和多维数据分析，如 果在传统数据分析理论的基础上结合数据挖掘理论，并提取出适合智能交通处 理的知识，必将为智能交通数据分析技术带来极为有意义的变革。 2 智能交通数据分析 本节对智能交通系统及其数据分析技术进行介绍。在本节的最后小节将介 绍目前在上海市应用的交通数据采集和分析系统s c a t s ，本文后续章节中采用 的数据很大一部份就取自于该系统。 2 1 1 智能交通系统 日本、美国和西欧等发达国家为了解决共同所面临的交通问题，竞相投入 大量资金和人力，大规模地进行了道路交通运输智能化的研究试验。起初进行 道路功能和车辆智能化的研究，随着研究的不断深入，系统功能扩展到道路交 通运输的全过程及其有关服务部门，发展成为带动整个道路交通运输现代化的 “智能交通系统”。智能交通系统的服务领域为：先进的交通管理系统、出行信 息服务系统、商用车辆运营系统、电子收费系统、公共交通运营系统、应急管 理系统、先进的车辆控制系统。“智能交通系统”实质上就是利用高新技术对传 统的交通系统进行改造而形成的一种信息化、智能化、社会化的新型交通系统。 它使交通基础设施能发挥最大的效能，从而获得巨大的社会经济效益。主要表 现在：提高交通的安全水平、提高道路网的通行能力和提高汽车运输生产率和 经济效益。 中国政府十分重视i t s 在国内的发展，有关部门从1 9 9 6 年开始组织了i t s 领域的一系列国际交流和合作，支持在国内开展研究和开发。1 9 9 7 年和1 9 9 8 年由欧盟委员会信息总司和中国国家科技部( 原国家科委) 共同组织在北京和 布鲁塞尔召开了中欧智能交通系统研讨会，这些会议对中国有关方面和技术人 员认识智能运输系统起到了很好的作用。在国家“九五”科技攻关项目中科技 部安排了“中国智能运输系统体系框架的研究”，该项目于2 0 0 1 年9 月通过了 国家鉴定和验收。这是我国第一次就一个应用系统开展跨部门和跨学科的框架 研究，在该研究中将分布在不同行业和部门的信息按照服务功能分类，按照信 第4 页 上海大学硕士学位论文 ! 堕旦! 塾g 翌i ! ! 堡! ! 塑堡! ! j ! 翌g ! 型婪! ! ! ! ! ! 监 息共享的原则建立数据流图，使智能交通系统体系框架是一个整体，在完成以 上工作的同时，充分考虑了中国现行的行政管理体制，使智能交通系统能够在 中国实施。该研究成果从整体上勾画了智能交通系统的构成，将指导中国今后 i t s 的发展。 2 1 2 交通数据采集与分析系统s c a t s 智能交通系统为能够有效地控制交通行为，通常要对城市各主要道路、道 口的交通数据进行记录，以便通过实时的交通数据分析来预测未来的交通状况。 目前，用于智能交通中的数据采集系统有很多种，本文后续章节所用到的交通 数据来源于上海市使用的s c a t s 系统【1 8 。s c a t s 系统是全球范围内应用比较 广泛的智能交通控制系统之一，在悉尼、墨尔本、奥克兰以及国内的香港、上 海等城市使用。基于s c a t s 的动态交通信息数据实时采集和处理系统，能够充 分利用安装的s c a t s 系统，对其相位信息、流量信息等进行采集。 基于s c a t s 的动态交通信息数据实时采集和处理系统，主要分为三个子系 统：数据采集、数据分析、数据通讯和存储。 数据采集部分，运行在s c a t s 区控机上，负责与s c a t s 区控程序通 讯和信息采集。通过与s c a t s 运行状态的交互，使用不影响s c a t s 运行机制的采集控制方法，达到利用s c a t s 采集设备并扩展s c a t s 采集流量范围的目的。 数据分析部分，对采集部分得到的原始信息进行分析和处理，得到加 工的交通信息。主要包括，s c a t s 相位信息、流量信息、适合大范围 比较的路口车道饱和度值、折算流量值等。同时，根据通讯协议以及 交通信息数据规范协议，对数据进行标准化处理。 数据通讯和存储部分，针对分析部分的数据，产生通讯命令流以及数 据库操作命令。并通过调用标准通讯协议和数据库引擎完成与外部通 讯及历史数据的存储。 图2 1 显示了s c a t s 系统的结构图。 s c a t s 系统集数据采集和数据分析功能为一体，但是，其数据分析部分还 比较简单，只是简单地计算饱和度、折算流量值等信息，这对于深层次交通数 据的应用是完全不够的。所以，需要在s c a t s 系统的基础上重新开发面向具体 应用( 如交通状况预测) 的功能模块，并将其集成到s c a t s 系统中去。 第5 页 上海大学硕士学位论文 ! 韭! ! 韭! 型! 坐! ! ! ! ! ! ! ! ! ! 塑吐丝! ! ! ! 型丝 图2 1s c a t s 系统结构图 2 1 3 交通数据分析 s c a t s 系统通过各个交通路口地数据采集器记录了大量的实时交通数据， 如何利用如此海量的数据来找到有用的信息成为了交通工作者的一个迫切任 务。因为交通数据的特点，传统的交通数据分析方法主要是统计的方法和多维 数据分析方法，这些方法都不能够充分地满足新的需求( 如发现交通知识) ，因 此，交通数据分析领域迫切地需要提出新的分析手段。具体来说，交通数据的 特点及可能的应对途径归纳如下： 交通信息来源广泛、种类繁多、表现形式多样、信息量巨大。因此，信 息的存储、组织、表示、查询优化等成为函待解决的问题。针对传统的 基于统计学的经典分析方法难以处理非数值型或非结构化的数据，传统 的基于数据库的决策支持系统难以支持日益膨胀的海量信息分析的现 状，引入以数据仓库、联机分析处理( o l a p ) 、数据挖掘和基于智能计 算等为代表的新一代分析技术不失为应对挑战的有效途径。在此，数据 仓库为不同结构的海量数据提供统一的存储与分析平台：联机分析实现 在不同时间跨度、不同粒度的数据分析与趋势预测；数据挖掘与知识发 现等能提炼出隐藏在大量信息背后的规律与知识，从而使“数据丰富、 知识贫乏”的现状得到根本改变。 信息具有很强的时空相关性。如车流量数据，只有在与一定的时刻及路 口相关联时才有意义，否则，难以被理解与利用。交通信息的时空相关 第6 页 上海大学硕士学位论文 坠! 呈竺! ! 墅! ! 些坠壁垒2 1 墨旦垫吐型堕! ! ! 里! 旦 性一方面为交通控制、预测、研究等提供强大的支持；另一方面，对信 息处理技术提出了新的要求。现代信息处理技术中的时间序列分析、空 间数据挖掘等对这类数据具有很强的适应性，能对其变化趋势进行较为 精确的预测，为实时交通控制提供参考。 信息具有明显的主题相关性。交通信息按照主题可划分为交通流信息、 交通信号控制信息、交通事故信息、交通违章信息、公交调度信息、停 车场信息等等。各主题内部还可细分，按照不同的主题，可以把信息分 类以便优化处理。而数据仓库正是一个面向主题的、集成的、时变的、 非易失的数据集合，支持管理部门的决策过程。可见，用数据仓库技术 来处理交通信息的分析与辅助决策具有不可比拟的优势。 信息具有生命特性。与生物类似，智能交通系统中的信息存在自繁衍、 自进化、消亡这三大生命体的基本特征。信息从采集、融合、加工、应 用到最后被扬弃的过程，体现了生物进化中遗传、变异、选择和进化的 思想。因此，可以借鉴生物进化论、智能计算中的遗传算法、神经网络 等进行相关研究。 从上述分析可见，鉴于智能交通系统存在动态性、不确定性、时空相关性、 主题相关性和生命特性等信息特征，经典的数学公式与传统的建模方法已不能 满足现实世界的信息分析要求，因此急需采用新一代的数据融合、决策支持和 分析手段，综合知识工程、人工智能、数据挖掘技术等方面的研究成果进行智 能分析，才能充分发掘各应用系统的潜力，为动态交通管理提供科学准确的决 策依据，使智能交通应用的深度和广度更上一个台阶。 2 。2 数据挖掘 2 2 1 数据挖掘的含义 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程。 以上定义包含以下几层含义：数据源必须是真实的、大量的、含噪声的； 应发现用户感兴趣的知识；发现的知识应是可接受、可理解、可运用的：不要 求发现放之四海皆准的知识，但需要支持特定的发现问题。 2 2 2 数据挖掘研究的内容 目前数据挖掘的主要研究内容包括基础理论、发现算法、数据仓库、可视 第7 页 上海大学硕士学位论文 ! ! ! 里殳塾趔竺堕! 塾! ! 堕! ! ! ! 塑g ! 型型! ! ! ! 堡! 型 化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结 构化和非结构化数据中的知识发现以及网上数据挖掘等。 数据挖掘所发现的知识最常见的有以下五种： ( 1 ) 广义知识：指类别特征的概括性描述知识。根据数据的微观特性发现 其表征的、带有普遍性的、较高层次概念的、中观和宏观的知识，反 映同类事物共同性质，是对数据的概括、精炼和抽象。 ( 2 ) 关联知识：它反映一个事件和其他事件之间依赖或关联的知识。如果 两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其 他属性值进行预测。 ( 3 ) 分类知识：它反映同类事物共同性质的特征型知识和不同事物之间的 差异型特征知识。 ( 4 ) 预测型知识：它根据时间序列型数据，由历史的和当前的数据去推测 未来的数据，也可以认为是以时间为关键属性的关联知识。 ( 5 ) 偏差型知识：它是对差异和极端特例的描述，揭示事物偏离常规的异 常现象，如标准类外的特例，数据聚类外的离群值等。 2 2 3 数据挖掘过程简介 数据挖掘一般应包含以下几个步骤： ( 1 ) 确定业务对象：即清晰地定义出业务问题。 数据挖掘时应认清数据挖掘的目的，虽然挖掘的最后结构是不可预测的， 但要探索的问题应是有预见的。 ( 2 ) 数据准备。其中又包括以下步骤： 数据的选择：搜索所有与业务对象有关的内部和外部数据信息，并从 中选择出适用于数据挖掘应用的数据。 数据的预处理：研究数据的质量，为进一步的分析作准备。并确定将 要进行的挖掘操作的类型。 数据的转换：将数据转换成一个分析模型，这个分析模型是针对挖掘 算法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功 的关键。 ( 3 ) 数据挖掘：即在合适的挖掘算法上对所得到的经过转换的数据进行挖 掘。 ( 4 ) 结果分析：即解释并评估结果。 ( 5 ) 知识的同化：即将分析所得到的知识集成到业务信息系统的组织结构 第8 页 上海大学硕士学位论文 ! 监! i 培型! ! 生! 皇! ! 堡生苎! 塑吐! l 堕翌i ! ! ! ! 盟 中去。 2 2 4 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要寻找的模式类型。数据挖掘任务 一般可以分为两类：描述和预测。描述性挖掘任务提取数据库中数据的一般特 性。预测性挖掘任务在当前数据上进行推断，以进行预测。 数据挖掘系统能够挖掘多种类型和各种粒度的模式，以适应不同的用户需 求或不同的应用。其功能主要如下： ( 1 ) 概念描述：特征化和区分 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者 描述不同类对象之间的区别。 概念描述有两种基本实现方法：基于数据立方体o l a p 的方法和面向属性 归纳的方法。对基本方法稍加扩充，概念描述挖掘可以用增量方式、并行方式 或分布方式进行。 ( 2 ) 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变 量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、 因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据 库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有 可信度。 关联规则发现方法主要有a p r i o r i 算法及其变形和频繁模式增长( f p 增长) 法。a p r i o r i 算法及其变形是一种产生大量候选频繁项集的方法，而f p 一增长法 是一种不产生候选频繁项集的方法。 ( 3 ) 分类和预测 分类和预测是数据分析的两种形式，可以用于提取描述重要数据类的模型 或预测未来的数据趋势。分类预测分类标号( 或离散值) ，而预测建立连续值函 数模型。 分类技术主要有：决策树归纳分类、贝叶斯分类、向后传播分类、基于关 联规则挖掘概念的分类。预测技术主要有回归统计建模，包括线性回归建模、 非线性回归建模、多元回归建模、广义回归建模等。 ( 4 ) 聚类 聚类是将物理或抽象对象的集合划分为由类似的对象组成的多个类的过 第9 页 上海大学硕士学位论文 ! 堕里! 壁g ! 盟! 坐! ! ! ! 坚! ! 兰! 塑韭型堕! ! ! ! 些丝 程。它与分类不同，聚类没有类标记作为指导，类标记由它本身产生。由聚类 所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似， 与其他簇中的对象相异。在许多应用中，可以将一个簇中的数据对象作为一个 整体来对待。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先 决条件。 聚类算法主要有：划分方法、层次方法、基于密度的方法、基于网格的方 法和基于模型的方法。 ( 5 ) 孤立点分析 孤立点是这样一些数据对象，它们不符合数据的一般模型，或者说它们与 数据的其他部分不同或不一致。孤立点可能是度量或执行错误所导致的，因此 许多挖掘算法试图使孤立点的影响最小化，或者干脆排除它们。但是孤立点也 可能蕴涵着重要信息，比如在欺诈探测中，孤立点可能预示着欺诈行为。因而 孤立点探测和分析是一个有趣的数据挖掘任务，被称为孤立点挖掘。 孤立点挖掘方法可分为三类：第一种统计学方法，此方法对给定的数据集 合假设了一个分布或概率模型，然后根据模型采用不一致检验来确定孤立点。 第二种基于距离的孤立点检测。第三种基于偏离的孤立点检测，它通过一组对 象的主要特征来确定孤立点，与给出的描述“偏离”的对象被认为是孤立点。 ( 6 ) 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。包 括趋势分析、相似性搜索、与时间有关的序列模式挖掘和周期模式挖掘。 有四种主要的变化和元素用于特化时序数据：长期或趋势变化、循环变化、 季节性变化、非规则性或随机变化。通过对趋势、循环、季节和非规则成分的 变动的系统分析，使人们可以在较合理的情况下制定出长期或短期的预测。 2 2 5 数据挖掘的应用领域 数据挖掘技术从一开始就是面向应用的，它能够发现以前未知的模式，预 测未来趋势和行为，因此其应用领域相当广泛。以下是其典型应用： 商业应用：包括银行、电信、保险、交通、零售( 如超市) 等商业领域， 其能解决的典型商业问题包括：数据库营销、客户群体划分、背景分析、 交叉销售等市场分析行为，以及客户流失性分析、客户信用记分、欺诈 发现等等。 生物医学和d n a 数据分析：如d n a 序列间相似搜索和比较、同时出 现的基因序列的识别、发现在疾病不同阶段的致病基因、可视化工具和 第1 0 页 上海大学硕士学位论文 ! 盟旦竺! ! 赶型! ! 塑! 皇! ! ! ! 垡墨! 塑g ! 型竺翌! ：! ! ! 盟 遗传数据分析等。 w e b 挖掘：w e b 文本内容分类和聚类挖掘、w e b 组织结构和链接关系挖 掘、w e b 使用记录挖掘等。 此外，数据挖掘还在化工、制造、司法、军事、城市交通、工程与科学数 据分析、多媒体挖掘等领域有广泛研究与应用。 2 3 数据挖掘与交通数据分析 数据挖掘技术能够从大量不完全、有噪声、模糊、随机的数据中挖掘出隐 藏的知识、找到对决策生成有重要参考价值的信息。因此，将数据挖掘运用到 交通数据分析中十分具有吸引力。在交通数据分析中，数据挖掘技术至少可以 应用在以下几个方面： ( 1 ) 交通数据分类 交通数据的特性之一就是具有重复性。所谓重复性是指在一段时期内某个 路段每天的交通状况是基本相似的，这样就使得我们可以用历史数据作为一个 参考，来对当前的交通状况进行评估。同时，我们也可以使用历史交通数据对 道路状态进行评估。评估的手段可以采用数据挖掘中的分类技术与聚类技术。 利用分类技术可以把相似特征的数据进行归类，- 从而得出适用于这些特征的知 识。利用聚类技术可以得出数据的分布特点，然后根据聚出的每一个簇的中心 点( 原型) 去确定数据的分类情况。 ( 2 ) 交通流量预测 所谓交通流量预测就是根据当前掌握的交通数据和历史交通数据，利用某 种算法来预测未来某个时间段内的交通流量状况。交通流量预测又可以分为短 期流量预测与长期流量预测。其中短期流量预测可以作为司机出行时的重要参 考，例如通过将未来3 0 分钟的流量预测值发送到车载导航系统中可以帮助车载 导航系统进行最优路线的规划。而长期流量预测则可以作为道路建设部门的重 要参考。 目前，交通流量的预测方法主要有三种： 基于历史数据法。即主要利用历史数据并结合当前交通流量的实测数 据建立预测模型。 时间序列法。即在已知过去若干时刻的交通流量的基础上预测未来流 量，具体的有a r i m a 模型、m a 模型； 神经网络仿真法。即利用神经网络能够模拟不确定的、复杂的、非线 性的过程特点，以当前的实测流量、历史流量、平均速度、环境状况等 第1 i 页 上海大学硕士学位论文 ! 业! ! ! g ! 塑! 坐! ! ! ! ! ! 生! 垫塑吐型堕坠! ：! ! ! ! 生 作为输入量，应用b p 神经网络进行未来时刻的流量预测。与前两种方 法相比，第三种方法没有时间延迟，特别是在对高峰小时流量的预测 时显示出较好的动态应答性。 ( 3 ) 拥塞分类及预测 当道路发生拥塞时，其产生原因是不同的，有可能是超过道路通车能力产 生的拥塞，也有可能是车祸造成的拥塞。针对不同的拥塞类型，交通管理部门 可能需要采取不同的疏通措施。 对于不同拥塞状况的识别，一个可行的方法是在不同的路段设置观测员， 遇有交通拥塞即根据状况向信息汇总中心进行汇报。这种方法过分依赖观测员 的主观判断，且会浪费大量的人力物力。 另外一种方法是可以利用现有的交通数据，根据各种拥塞产生原因的不同 特性，使用数据挖掘算法对拥塞进行分类，使得每个类里的对象具有相似的属 性，而不同类型里的对象的属性也不同。这样交通管理部门可以根据不同类型 的拥塞采取完全不同的应对措施，如此一来降低了成本、提高拥塞的疏导速度， 也有效地解决了交通警力不足的问题。同样，依据数据挖掘技术，可以从历史 拥塞记录中挖掘出拥塞产生时具有的普遍适用的知识，从而利用该知识对未来 可能产生的拥塞进行预测，做到防范于未然。 第1 2 页 上海大学硕士学位论文 ! 生! ! 堡! 型! 型! ! ! ! ! 坚坐! i 塑韭坠望! i ! ! ! ! i 型 第3 章数据挖掘中的分类技术 数据分类( d a t ac l a s s f i c a t i o n ) 是数据挖掘的一个重要方面，几乎每个数据挖 掘系统都有数据分类模块。数据分类是对数据库中数据对象( 元组) 进行分类， 在数据对象上产生分类规则的过程。分类的目的是学会一个分类函数或分类模 型( 也常常称作分类器) ，该模型能把数据库中的数据项映射到给定类别中的某 一个【l 。许多分类的方法己被机器学习、专家系统、统计学和神经生物学方面 的研究者提出。 3 1 分类挖掘 3 1 1 数据分类的基本过程 分类数据挖掘也称作分类分析，一般可描述如下 3 】： 给定一数据集t ( 称为训练集，t r a i n i n gs e t ，通常该数据集针对于某一应 用领域，并满足该领域数据分布的规律) 及其属性集合4 ，4 中的元素x 称为r 的属性。x 可为离散( d i s c r e t e ) 属性或连续( n u m e r i c 或c o n 6 n u o u s ) 属性。在 丁的属性中，存在一个称为类别标示的离散属性c ( c l a s sl a b e l ) ，用于标示7 1 中记录的类别： c = c l ，c 2 ，c k ) ，k 表示类别的个数。 为便于叙述，将a 一 c ) 记作x ，并用向量表示如下： j ，- x ，x 2 ，h ，即t 除类别属性之外有n 个属性。 将属性t x ( 1 5 i s n ) 的值域记作d o m ( x , ) ，则： d o r a ( x , ) = 确，t 2 ，) ，m 为t 的值域d o m ( x i ) 所包含元素的个数。则其 中的一条记录t 可写作f = 。 这样，训练集t 隐含地确定了一个从x 到c 的函数日：h ( x ) - - c 。分类 分析的目的就是采用合适的手段将函数日拟合出来，之后用该拟合函数对新的 记录进行类别的判断。 从步骤上来看，数据分类( d a t ac l a s s 斫c a t i o n ) 可分为两步进行( 如图3 1 ) 。 第一步，建立一个模型，描述预定的数据类集或概念集。通过分析由属性 描述的数据库元组来构造模型。假定每个元组属于一个预定义的类，由一个类 第1 3 页 上海大学硕士学位论文 ! 盐! ! ! 墅! ! ! 坐! ! 型! ! ! ! 皇塑业型婪巳! ! 垡! 丝 标号属眭( c l a s st a b e la t t r i b u t e ) 的属性确定。对于分类，数据元组也称为样本、实 例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的 单个元组称为训练样本，并随机的由样本集中选取。由于预先知道每个训练样 本的类标号，这个建立模型的学习过程属于有指导的学习( 即模型的学习在知 道每个训练样本属于哪个类的指导下进行) 。这不同于无指导的学习( 例如聚 类) ，无指导的学习中的每个训练样本的类标号事先是未知的，要学习的类集合 或数量也可能事先不知道，整个学习的过程是在无指导的情况下进行的。 通常，通过第一步的学习建立的模型用分类规则、决策树或数据公式的形 式表示。例如：给定一个表示交通状况的数据库，通过分类算法学习得出分类 规则，根据这些规则，决定交通状况是否为拥塞( 如图3 i a ) 。即这些规则就是 分类模型，可以利用这个模型为其他数据样本进行分类，同时也能对数据库的 内容提供更好的理解。 第二步( 如图3 1 b ) ，使用这些规则进行分类。首先要评估模型的预测准确 率。最常用的一种方法是保持( h o l d o u t ) 方法，该方法使用类标号样本测试集， 这些样本随机选取，并独立于训练样本集，即测试样本集完全不同于训练样本 集。模型在测试样本集上的准确率是指正确被模型分类的测试样本的百分比。 对于每个测试样本，按照分类模型学习得出的预测类与已知的类标号比较，如 果相同，则表示分类成功，不相同，则表示分类不成功。之所以使用完全不同 于训练样本集的测试样本集，是因为学习模型倾向于过分适合数据，即学习模