（系统工程专业论文）粗集预处理数据的神经网络交通事件自动检测算法研究.pdfVIP

中文摘要 随着高速公路的发展和大城市交通问题的日益严重，建立交通应急系统的要 求也越来越迫切，而有效的交通事件检测是应急系统成功运行的第一步，也是关 键之所在，所以对交通事件检测算法的研究就成为热点问题。本文试图把粗集理 论和神经网络理论相结合，建立一种全新的粗集预处理数据的神经网络交通事件 自动检测算法，主要研究内容包括以下几个方面： 总结现有的交通事件自动检测算法，对其性能进行比较分析，并详细地列举 出评价算法优劣的评价指标和评价准则，提出本文欲建立算法的基本原理。 对粗集理论进行数据挖掘的若干问题进行了比较深入地研究，如属性特征的 选择、连续属性离散化、和约简算法寻优等。对神经网络检测交通事件的几种算 法也做了介绍和比较，详细研究了网络结构的选择和训练问题，为建立本文的算 法提供了基础。 提出了建立粗集预处理数据的神经网络交通事件自动检测算法，该算法充分 发挥了粗集理论和神经网络理论各自的优势。神经网络具有并行处理、信息分布 存储等特点，可通过训练、学习产生一个非线性映射，白适应地对数据进行聚类， 同时具有较好的抑制噪声干扰的能力和较强的鲁棒性。其缺点是当输入信息空间 的维数较大时，网络不仅结构复杂，而且训练时间也很长。而粗集可对数据进行 属性约简和值约简，消除样本中的噪声和冗余对象。这两者的结合不仅可以减小 网络的规模，同时通过消除对象冗余可减少网络的训练和学习负担，还可以通过 消除噪声提高神经网络预测的准确性。本文算法中的神经网络采用的是多层前向 反馈神经网络，并引入了动量项，采用白适应的学习率，可以获得更好的性能。 为检验算法的有效性，建立了事件仿真模型，获得所需数据，并用获得的交 通流数据来训练和检测本文算法，对已有神经网络算法和传统检测算法与本文算 法做了对比试验和分析，分析结果表明，本文算法可获得较高的检测率和较低的 误报率，对评价指标的协调性也比其它算法更好。 关键词：交通流，交通事件自动检测，粗集理论，神经网络 a b s t r a c t w i t ht h ed e v e l o p m e n to fh i g h w a ya n dt r a f f i cp r o b l e mb e i n gs e r i o u sd a yb yd a yi n b i gc i t i e s ，t h ed e m a n do fe s t a b l i s h i n ge m e r g e n c em a n a g e m e n ts y s t e m s ( e m s ) b e c o m e su r g e n t e f f e c t i v ed e t e c t i o nf o rt r a f f i ci n c i d e n ti st h ef i r s ts t e pa n dt h ek e y c o m p o n e n to fo p e r a t i n gt h ee m ss u c c e s s f u l l y ；t h e r e f o r e ，t h es t u d yo nd e t e c t i o n a l g o r i t h mf o rt r a f f i ci n c i d e n th a sb e c o m eah o ti s s u e t h es t u d yt r i e st oc o m b i n et h e r o u g hs e tt h e o r ya n dn e u r a ln e t w o r kt oe s t a b l i s han e wa u t o m a t i cd e t e c t i o na l g o r i t h m f o rt r a f f i ci n c i d e n tu s i n gn e u r a ln e t w o r kb a s e do nr o u g hs e tf i l t r a t i o n m a i nr e s e a r c h w o r ki sl i s t e da sf o l l o w s ： t h ee x i s t i n ga u t o m a t i cd e t e c t i o na l g o r i t h m sf o rt r a f f i ci n c i d e n ta r es u m m a r i z e d ， t h ep e r f o r m a n c e so fi ta r ec o m p a r e da n da n a l y z e d ，t h ei n d e xf o re v a l u a t i n g a l g o r i t h m sp e r f o r m a n c ei sl i s t e d ，a n dt h e nt h eb a s i cp r i n c i p l eo f t h ea l g o r i t h mi nt h e t h e s i si se x p o u n d e d an u m b e ro fp r o b l e m si nd a t am i n i n gu s i n gr o u g hs e th a db e e ns t u d i e dd e e p l yi n t h et h e s i s ，f o re x a m p l e ，f e a t u r es e l e c t i o n ，c o n s e c u t i v ef e a t u r ed i s c r e t i z a t i o n ，s e e k i n g t h eo p t i m u md e d u c t i o na l g o r i t h m s e v e r a la l g o r i t h m su s i n gn e u r a ln e t w o r kt od e t e c t t r a f f i ci n c i d e n ta l s oh a db e e ni n t r o d u c e da n dc o m p a r e d t h es t r u c t u r e ss e l e c t i o na n d t r a i n i n go fn e u r a ln e t w o r kw e r es t u d i e di np a r t i c u l a r , w h i c hw e r et h eb a s i co f e s t a b l i s h i n gt h ea l g o r i t h mi nt h et h e s i s an e wa u t o m a t i cd e t e c t i o na l g o r i t h mf o rt r a f f i ci n c i d e n tu s i n gn e u r a ln e t w o r k b a s e do nr o u g hs e tf i l t r a t i o nw a sp r o p o s e d ，w h i c hh a st h ea d v a n t a g e so fn e u r a l n e t w o r ka n dr o u g hs e tt h e o r y n e u r a ln e t w o r kh a ss e v e r a lc h a r a c t e r i s t i c s ，s u c ha s d i s p o s i n gd a t u mi np a r a l l e l ，s t o r i n gi n f o r m a t i o nd i s t r i b u t e da n ds oo n ，w h i c hc a n p r o d u c ean o n l i n e a rm a pb yt r a i n i n ga n dl e a r n i n g 。c l u s t e rd a t aa d a p t i v e l y ，w i t ht h e a b i l i t i e so fr e s t r a i n i n gt h en o i s e sd i s t u r b a n c ea n dg o o dr o b u s t n e s s i t ss h o r t c o m i n g s a r et h a tw h e nt h es p a c ed i m e n s i o no ft h ei n p u ti n f o r m a t i o ni sl a r g e r , n o to n l yc o m p l e x t h en e t w o r k ss t r u c t u r ei s ，b u ta l s ot h en e t w o r kn e e dm o r et i m et ot r a i n r o u g hs e tc a n d e d u c tf e a t u r ea n dv a l u eo ft h ed a t a ，e l i m i n a t et h en o i s ea n dr e d u n d a n tt a r g e t si n s a m p l e t h em e r g en o to n l yr e d u c e dt h es c a l eo ft h en e t w o r k ，l e s s e n e db u r d e no f t r a i n i n ga n dl e a r n i n gb ye l i m i n a t i n gr e d u n d a n tt a r g e t s ，b u ta l s oi m p r o v e dt h ea c c u r a c y o fd e t e c t i o nb ye l i m i n a t i n gn o i s e t h en e t w o r ki nt h et h e s i sh a sm u l t i - l a y e rf e e d f o r w a r da r c h i t e c t u r e ；t h em o m e n t u ma n dt h ea d a p t i v el e a r n i n gr a t ea r ea l s oa d o p t e d f o rb e t t e rp e r f o r m a n c e i no r d e rt ov e r i f yt h ee f f e c to ft h ea l g o r i t h mp r o p o s e di nt h et h e s i s ，s i m u l a t i o n m o d e lo ft r a f f i ci n c i d e n tw a se s t a b l i s h e dt oo b t a i nt h et r a 珩cd a t aw h i c hw a su s e dt o t r a i na n dt e s tt h ea l g o r i t h m c o m p a r i n ga n da n a l y z i n gh a db e e nd o n ea m o n gt h e a l g o r i t h m i nt h et h e s i s ，t h e e x i s t i n g n e u r a ln e t w o r ka n dt r a d i t i o n a ld e t e c t i o n a l g o r i t h m s t h er e s u l t ss h o wt h a tt h ea l g o r i t h mi nt h et h e s i sh a sh i g h e rd e t e c t i o nr a t e a n dl o w e rf a l s ed e t e c t i o nr a t e i t sc o o r d i n a t i o na b i l i t yt oe v a l u a t i o ni n d e xi sa l s o b e t t e rt h a no t h e ra l g o r i t h m s k e yw o r d s ：t r a f f i cf l o w , a u t o m a t i cd e t e c t i o no ft r a f f i ci n c i d e n t ，r o u g hs e tt h e o r y , n e u r a ln e t w o r k 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 劾也岛 签字日期：m 年7 月夕日 学位论文版权使用授权书 本学位论文作者完全了解丞鲞盘堂有关保留、使用学位论文的规定。 特授权墨壅盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：矽哆年 弛4 冯 r 日 ， 导师签名： 颈翻九 签字日期：夕吖聿月秒日 第一章绪论 第一章绪论 本章首先对交通事件应急系统进行了简要介绍，然后阐明交通事件检测在应 急系统中所发挥的重要作用的基础上说明其研究意义，通过对国内外研究现状的 分析，对现有的交通事件检测技术进行了总结和比较，提出了一种粗集预处理数 据的神经网络交通事件自动检测算法，最后综述了本文的主要框架结构。 1 1 本文的选题背景与研究意义 在交通领域中，“应急系统”( 有的叫做紧急救援系统) 已经被多次提到，有 人把其归为i t s ( i n t e l l i g e n tt r a n s p o r ts y s t e m s ) ，或者归在a t m s ( a d v a n c e d t r a n s p o r t a t i o nm a n a g e m e n ts y s t e m ) 中。“应急系统”代表的是目前世界上比较先 进、科学的危机处理方法，核心作用是能实现紧急突发事件处理的全过程跟踪和 支持。从突发事件的侦测、相关数据的采集、紧急程度的判断、到实时沟通、联 动指挥、应急现场支持、领导辅助决策等，即在最短的时间内对突发性危机事件 做出最快的反应并提供最恰当适合的应对措施预案等。交通事件主要包括交通事 故、车辆抛锚、货物洒落、修路等。在交通领域中，不但各种偶发的交通事故损 坏交通设施，造成人员伤亡，经济损失，而且城市中每天车辆高峰时段常发的交 通拥挤也带来巨大经济损失。而各种非人为因素，如恶劣天气、自然灾害等，也 在不同程度地影响正常的交通运行。建立城市交通应急系统，具有重要的现实意 义，可以帮我们从容应对诸如此类的问题，防患于未然。 交通事件检测( 以下简称为事件检测) 即通过分析交通流的流量特性，确定 潜在的、将要发生的和已经发生的事件，是事件应急管理过程的第一步，也是核 心和关键【1 1 。任何事件管理系统的快速反应能力都在很大程度上依赖于高效、可 靠的事件检测技术。尽早地检测出交通事件对于制定恰当的响应策略，控制和引 导其它车辆避开事发地点，为驾驶员提供实时的交通信息，从而使事件总的影响 降到最低是非常重要的。 事件检测不但对于事件应急管理本身意义重大，而且对于i t s 的其它子系统 也有重要作用。事件检测为这些系统提供的非周期性交通流状态变化信息( 这些 信息是无法从历史数据中得到的，也是交通流变化实时性的表现) 。为使这些系 统能够高效运行也必须建立快速、可靠的事件检测系统。另外，高效的事件检测 第一章绪论 还可以进一步提高高速公路匝道控制和城市道路信号控制之间的协调，有助于建 立真正意义上的集成式高速公路城市道路控制系统。 鉴于以上原因，对交通事件检测技术的进一步研究具有重要的实际意义和应 用价值。 1 2 国内外事件检测算法的研究现状 自2 0 世纪6 0 年代发展起来以后，形成了各种各样的事件检测方法和技术， 总的说来，它们可以概括地分为非自动检测技术和自动检测技术。从整体看，非 自动检测技术的主要优点是方便、直接、经济、效率比较高；缺点是要求当地当 时有目击者，事件地点比较难以准确确定，需要专门的人员对报告进行筛选确认， 人员工作量和强度都比较大。 非自动检测技术一般运行成本较高，受事件和天气影响较大，检测时间较长， 检测率较低。因此，各国交通工程专家纷纷积极研究和开发运行成本低、能够全 天候、全程地发挥作用、且检测率高的自动事件检测技术( a u t o m a t i ci n c i d e n t d e t e c t i o n ，佃) 。美国早在1 9 6 8 年就开始研究以a i d 技术为核心的事件检测系 统，3 0 多年来，大约有4 0 多个研究机构在研究开发和改进a i d 方法方面做了大 量工作，使a i d 技术日益成为事件检测研究的主流。近年来，伴随着电子、检 测、通信以及计算机技术的飞速发展和r r 技术的渗透，a i d 技术不断推陈出新， 形成了i t s 研究的一项非常重要的内容。 交通事件自动检测系统能否成功运行，快速有效的事件检测算法起着非常重 要的作用。已有的交通事件自动检测算法都是基于交通事件发生时的交通流的以 下特性【2 】：即当交通事件发生时，引起一个车道或几个车道交通阻断，该处上游 变得相对拥挤，占有率增加，速度降低，下游的情况则正好相反。有的检测算法 还能把常发性交通拥挤和偶发的交通事件区分开，是基于以下交通特性差异：常 发性拥挤是由于需求超过道路容量( 超载) 而产生的拥挤，从不拥挤到拥挤需要 一个过程，因而，拥挤前后的交通流参数( 交通量、速度和道路占有率) 的变化 是连续的；而偶发性拥挤是由于事件造成道路通行能力暂时下降而引起的拥挤， 因而，反映拥挤前后的3 个交通参数的变化呈不连续状态，并且前后的差值随 事件的严重性而增大。因此，根据以上理论分析， 可以很容易判别出交通拥挤 的类型，即如果检测到道路上交通拥挤前后的交通流参数的变化值在一定限域 内，则可以认为该交通拥挤为常发性拥挤； 当变化值超过了一定的限域，则说 明路上的交通呈不连续的变化，则认为发生偶发性拥挤。此外，如果在路段交 通量不大的情况下发生拥挤，而此时检测到的参数值又在一定的限域内变化， 第一章绪论 则可判断该交通拥挤为偶发性拥挤而非常发性拥挤，因为，常发性拥挤是发生在 路上交通量达到或接近拥挤能力的时候。交通事件自动检测是在分析交通流特性 的基础上，通过某种算法确定或预测交通事件，缓解交通拥堵或交通公害，提高 事件检测的准确性，并缩短检测时间。 1 2 1 交通事件检测算法的分类比较 交通事件检测算法按照算法原理可归纳成六类，即模式识别算法、统计预测 算法、突变理论算法、时间序列和平滑滤波算法、低流量事件检测算法、基于人 工智能的算法f 3 】，分类描述见图1 - 1 ，各类算法比较分析见表1 1 。前五类算法具 有以下缺点：不能解决算法的复杂性和检测的准确性之间的矛盾；误报率、检测 率和平均检测时间之间的冲突仍然存在：受线圈的性能影响较大；对低流量条件 下和路肩处发生的交通事件的检测效果较差。基于人工智能的算法已在交通事件 检测领域展现出常规算法所不具备的优势和潜力，可大大降低误报率，提高准确 率。 事厂 i 件i i 检 j 测1 l 算 i 法【 1 ) 模式识别算法：一加州算法- - m i n n e s o t a 算法 统计预测算法： 贝叶斯算法一正态偏差算法 突变理论算：一m c m a s t e r 算法 时间序列和平滑滤波算法：一时间序列a r i m a 算法一低通滤波算法 低流量事件检测算法 基于人工智能的算法：一神经网络算法一模糊控制方法- d , 波分析算法 图1 - 1 事件检测算法分类 1 2 2 交通事件检测算法的评价指标和评价准则 目前，用来评价检测算法优劣的指标有：误报率( r 讯) 、检测率( d r ) 和 平均检测时间( m 1 ) ，定义如下： d r = 柰燮淼( 1 - 1 ) = - - - 。- 。- 。- - - 。一 实际发生的事件的次数 f a r = 蠢淼 ( 1 2 ) 第一章绪论 则可判断该交通拥挤为偶发性拥挤而非常发性拥挤，因为，常发性拥挤是发生在 路上交通量达到或接近拥挤能力的时候。交通事件自动检测是在分析交通流特性 的基础上，通过某种算法确定或预测交通事件，缓解交通拥堵或交通公害，提高 事件检测的准确性，并缩短检测时间。 1 2 1 交通事件检测算法的分类比较 交通事件检测算法按照算法原理可归纳成六类，即模式识别算法、统计预测 算法、突变理论算法、时间序列和平滑滤波算法、低流量事件检测算法、基于人 工智能的算法 3 1 ，分类描述见图1 - 1 ，各类算法比较分析见表1 - 1 。前五类算法具 有以下缺点：不能解决算法的复杂性和检测的准确性之间的矛盾；误报率、检测 率和平均检测时间之间的冲突仍然存在；受线圈的性能影响较大；对低流量条件 下和路肩处发生的交通事件的检测效果较差。基于人工智能的算法已在交通事件 检测领域展现出常规算法所不具备的优势和潜力可大大降低误报率，提高准确 率。 事厂1 ) 模式识别算法： 一加州算法一m i n n e s o t a 算法 件l 2 ) 统计预测算法：贝叶斯算法正态偏差算法 检l3 ) 突变理论算：一m c m a s t e r 算法 测 l4 ) 时间序列和平滑滤波算法：一时间序州a r i m a 算法一低通滤波算法 算l5 ) 低流量事件检测算法 法 l6 ) 基于人工智能的算法：一神经网络算法一模糊控制方法- d 、波分析算法 图卜1 事件检测算法分类 1 2 2 交通事件检测算法的评价指标和评价准则 目前，用来评价检测算法优劣的指标有：误报率( f a r ) 、检测牢( d r ) 和 平均检测时间( m t r d ) ，定义如下： 平均检测时间( m t r d ) ，定义如下： d r = 柰拦淼 m ， 实际发生的事件的次数 、7 f a r 一丽罴 ( 1 - 2 ) 第一章绪论 m t t d 一三罗濞法检测到事件的时间一事件发生的时间) ( 1 3 ) 九钎 k a r lep e t t y 【4 】认为，用f a r 、d r 和m t f d 作为某种算法的评价指标在实 际使用时将遇到许多困难，如收到报警信号后需依赖于专家的经验判断该报警信 号是否为真正的交通事件，不可避免地带有主观性，因此同样的交通数据，不同 的算法可能做出不同的判断，因此提出了基于检测算法费效分析的h ( s ，a ) 指标。 吼l 甜g 鬈，矿 ，以，彳) + g ( s ，吼，彳) h ( s ，彳) 一，( s ，吼，彳) + g ( s ，吼，彳) ( 1 4 ) ( 1 5 ) 式中，s 为依赖于参数向量仇的自动检测算法，a 为收集的交通流数据( 包 括事件发生的位置和持续时间，路段速度和流量以及其他对事件检测算法重要的 数据) ，f 、g 代表延误和实施费用函数( 将车小时转换为货币费用) ，从而寻找使 h 最小的检测算法s 。 另外，通用性强的事件自动检测算法还应该具有以下属性和能力【5 】： ( 1 ) 高性能：比如上面所说的高检测率、低误报率和最短检测时间。很明显， 高性能只能通过细心的选择有代表性的输入特征，强大的模式识别逻辑和代表所 有可能情况的训练数据来获得。 ( 2 ) 快速的训练和校验：算法的训练是繁琐和费时的，实际上，没有所谓的 最合理的i ) l i 练时间。然而，训练和训练过程越快速和简单，在线实时再训练的潜 力越大。 ( 3 ) 可移植性强的逻辑：算法建立的逻辑或理论基础不应受时间、空间或任 何其它可能限制用于其它地点的因素的约束。 ( 4 ) 要求最少的原始训练数据：很明显，高质量、详细的真实事件数据不仅 分散而且很难获得，如果收集能够代表所有情况下的真实事件数据，并能校验最 微小的错误可行的话，也将是一项非常费时的工作。现有的事件检测算法的一项 重要限制因素是原始训练数据的质量。人们经常只是用有限的真实数据或者大量 的模拟数据来校验算法。这样就可能限制最终算法的质量并影响可移植性。因此， 一个有效的算法应该能应用最少的事件数据，然后随着提供数据的积累自动地提 高性能。 ( 5 ) 考虑错误分类交通模型的成本差异：虽然误报和漏报都属于错误分类， 成本却不一样。哪一个成本更高取决于以下几个因素，如高速公路的路段，一天 中的时间段，事件的特点，投入事件的资源成本，管理中心的管理范围、能力和 0 第一章绪论 偏好等等。 ( 6 ) 估计事件的严重程度：这项功能能帮助交通管理中心有效应对同一时间 发生的交通事件，决定优先权，以及如何分配有限的资源。 ( 7 ) 估计事件持续时间：表明恢复正常交通流所需的关键信息。 ( 8 ) 具有适应不同检测设计和技术的工作灵活性：检测算法的成功应用不应 局限在特定设计的检测系统，包括传感器技术、空间铺设等。比如，有些算法要 求特殊的环形线圈铺设在漏斗状的高速公路路段，在这样的要求下，一旦不满足 就会产生限制。 ( 9 ) 对很小的交通波动的敏感性小：在尽可能的情况下，算法不应受容易产 生误报率的很小的短期交通波动的影响。 ( 1 0 ) 对瓶颈影响的敏感性小：算法具有区分真正发生事件的模式和由于物理 瓶颈使队列模式相似事件发生而产生的类似事件模式的能力。 ( 1 1 ) 对连续检测故障和偏差的敏感性小。 表1 - 1 事件检测算法比较 时间与创始 平均检测 对数据 算法基本思想 优缺点时间 人的需求 ( m i n ) 比较两个上下游检测站 测量的占有率的三个表 计算简单，门限值确定需 达式：上下游占有率的 要大量计算( 交通流周期 绝对差、上下游占有率 性波动如高峰与非高峰时 加州算法 1 9 7 6 年p a y n e 差与上游占有率之比、 交通参数差异对门限值的 占有 e ta 1上下游占有率差与下游 影响不在算法考虑之内) 5 率、交 占有率之比，根据这三 误报率高，检测时间长，通量 式与预先设定的门限值 不能动态检测，交通参数 正、疋、正比较来判断是 选取简单，没有反应复杂 的交通本质。 否有交通事件发生。 线圈间距不能太大，不适 m i n n i s o t a 1 9 9 3年与历史上事件发生条件 于流量小的道路，检测时 算法 s t e p h a n e d a s 下的典型值设定的门限间长，受线圈影响大，削 3 占有率 c h a s s i a k o s 值比较，判断事件弱了不确定因素对上下游 占有率的不利影响 由两个相邻线圈检测的 贝叶斯算1 9 7 8 年l e v i n 数据构成三个数据库，判断事件发生，给出发生 计算由事件引起的占有 概率；准确度高，平均检 3 9 占有率 法e ta l 率变化的次数于总的占测时间长 有率变化次数之比 该算法考虑到了噪声对检 低通滤波测结果的影响，采用低通 4 0 占有率 算法 滤波技术，使检测指标有 了明显的改善。但由于滤 第一章绪论 波过程的存在，平均检测 时间长。 在中等到高流量时检测效 果较好，在低流量时效果 通过计算时n t 前3 个差；算法采用低阶线性模 时间间隔交通参数的预型，并假定日交通量保持 测值和观测值问的误差稳定，根据实测数据对模 占有 a r i m a 算1 9 8 2年平均值，可预测交通参 型参数进行设置，理论上 0 4 率、交 法a h m e d e ta l 数在时刻f 的值。通过分 存在着缺陷，难以反映交 通量 析、平滑处理原始数据，通复杂的非线性的特点； 然后与预定的门限值进算法较多依赖于原始数 行比较。 据，受交通流的日变化、 天气条件、施工等因素的 影响较明显。 采用单检测线圈的测量数 据，不能充分利用交通流 的空间变化特点，仅根据 交通数据的时间改变来检 突变理论能够区分偶发测事件的发生与否；适用 性拥堵和交通事件。是于受各种条件限制不能大 改进 1 9 8 9年 目前最准确的事件检测 量铺设检测线圈或线圈相 占有 m c m a s t e r p e r s a u d和 算法之一，检测准确率 距较远的地区。该算法与 2 2 率、交 在7 0 8 5 之间，而误报模式识别算法的区别是g 算法h a l l 通量 率在1 以下，常用来比应用两个变量即占有率和 较其他算法的性能优 交通量，与重发性交通拥 劣。挤时数据的走势对比后进 行判断；而模式识别算法 仅采用一个变量，通过与 设定的门限值比较，来鉴 别是否有事件发生。 9 0 年代以来 k o l t o ， 交通问题是无穷维的、 s t e p h e n 时变的、高阶的和混沌 g r i t c h i e 、 的复杂动力学系统，神 占有 神经网络 e d m o n d经网络作为一种并行的 0 9 6 率、交 算法c h i n - p i n g 信息处理结构，特别适 通量 c h a n g 、合于非线性复杂系统的 a r d e s h i r 模拟和优化以及交通事 f a g h r 、姜紫峰 件的实时检测。 w 综合了不确定性因素和 人类决策过程中的抽象 本质，以模糊集合和隶 采用模糊逻辑算法的难点 模糊逻辑 属度函数的形式表示系在于隶属度函数的形状和 比传统算 占有 统参数的边界条件，采 类型不易决定，有时根据法最多快 率、交 算法 专家经验确定的推理规则 3 m i n 通量 用i f - t h e n 语言推理规 则，概念上容易理解， 并不能得到最优的方案。 对数据的准确性和连续 性要求不高，特别适用 第一章绪论 1 3 粗集预处理数据的神经网络交通事件自动检测算法的提出 由于交通流模型是无穷维的、非线性的、随机的、时变的和高阶的，是非常 复杂的动力学系统，想直接从理论上推导某种规律来描述交通流，是不可能涵盖 它的全部特性的。各种现代检测算法和设备对事件的检测与传统算法比较有很多 优势，像人工神经网络理论、小波理论、模糊控制理论的日趋成熟和实用化，有 利于建立事件检测的新算法。而各种算法都有各自的优缺点，仍需对它们进行分 析和比较，而且这些算法的评价指标目前还不是很理想。本论文试图建立粗集理 论预处理交通事件数据，由神经网络技术检测事件的一种新方法，希望获得较好 的评价效果。 1 3 1 算法的特点 本文提出一种粗集和神经网络结合的交通事件自动检测方法，其特点在于： ( 1 ) 将粗集作为神经网络的预处理环节，通过属性约简、消除样本冗余和噪 声等一系列处理，在不降低数据一致性的前提下，最终得到尽可能精简的属性集。 以此尽可能地减少神经网络的输入，而又不影响网络对事件的检测能力。从而减 少神经网络的复杂度和训练时间，提高交通事件的自动检测速度。 ( 2 ) 算法中不仅考虑了反映交通流本身特性的参数，还引入了与事件发生与 否相关的各种因素，从而提高了对交通事件的检测能力。 1 3 2 算法原理 神经网络具有并行处理、信息分布存储等特点，可通过训练、学习产生一个 非线性映射，自适应地对数据进行聚类，同时具有较好的抑制噪声干扰的能力和 较强的鲁棒性。但是，当输入信息空间的维数较大时，网络不仅结构复杂，而且 训练时间也很长。本文运用粗集理论预处理交通流数据，采用的是一种二维约简 方法。具体做法是利用粗集进行属性约简、并消除样本中噪声( 不致对象) 和 消除样本中冗余对象( 是指条件属性和决策属性都相同的样本数据，它对于预测 的准确性没有影响却增加了训练学习的负担) ，然后把处理的样本数据输入神经 网络进行训练。通过上述处理不仅减小了网络的规模，同时通过消除对象冗余减 少了网络的训练和学习负担，也通过消除噪声提高了神经网络预测的准确性。 第一章绪论 1 4 本文的主要研究工作 本文以粗集理论和神经网络理论为主要研究方法，寻求效果较好的交通事件 自动检测算法，具体的研究工作如下： 第一章为本文的绪论部分。首先分析了本文的选题背景和研究意义，然后简 单介绍了检测算法的研究现状，对现有算法在分类的基础上，分析其优缺点，并 指出了算法的评价指标和评价标准，最后提出了本文所要采用的研究方法，并对 其特点和原理进行了说明，最后指出本文的主要研究工作。 第二章首先简单列举粗集理论从建立到目前人们获得的一些成果。粗集理论 的扩展模型的几种基本种类和粗集理论应用领域。然后对粗集理论所涉及的一些 关键概念给出了定义。并描述了粗集理论对数据处理的特点和步骤。最后，对租 集处理数据的几个关键问题分别加以详细地描述。 第三章在对神经网络交通事件检测算法与事件发生和不发生交通流特征差 异的介绍之后，简单地阐述了不同的神经网络交通事件自动检测算法的基本结 构，本文采用的是多层前向神经网络模型，所以针对这种模型详细介绍了它的算 法原理。神经网络结构的确定是一个很重要的问题，在本章的最后讨论了模型结 构问题。 第四章介绍仿真模型的基本原理，建立微观仿真模型以获得所需的仿真数 据。 第五章介绍建立粗集预处理数据的交通事件自动检测算法，详细说明了本文 算法的具体步骤，然后结合高速公路的具体情况，建立了决策表，用于最后检验 该算法的检测效果。 第六章对粗集预处理数据的神经网络交通事件自动检测算法和各种神经网 络算法、传统算法进行了比较，最后总结了本文算法的优缺点。 第七章总结了全文的内容，指出了本文算法的创新之处，并对完善该算法需 要做的后续工作进行了说明。 第二章使用粗集理论进行数据挖掘 第二章使用粗集理论进行数据挖掘 粗集理论的主要思想是在保持分类能力不变的前提下，通过属性约简，导出 问题的决策或分类规则，通过垂直约简，消除样本的冗余。应用粗集理论处理不 确定性问题的最显著特点是不需提供问题所需处理的数据集合之外的任何先验 信息，算法简单、易于操作【6 】。 2 1 粗集理论的发展 粗集理论是一种研究不精确、不确定、不完备性知识的数学工具，由波兰科 学家p a w l a k 在1 9 8 2 年提出【7 】。在处理大量数据，消除冗余信息等方面，粗集理 论有着良好的效果，因此广泛用于数据预处理、数据缩减、数据依赖关系发现等 方面i 叭3 。二十年来，众多研究者投入粗集理论的研究，涌现了大量的研究成果 1 1 4 - 2 1 j ，使粗糙集理论取得了进一步的发展和丰富，这突出地表现在两个方面：一 是粗糙集的模型，由最初p a w l a k 创立的标准粗糙集模型( 又称p a w l a k 模型) ， 演变出了各种形式的变形和推广。这些推广的粗糙集模型统称为广义粗糙集模型 ( g e n e r a l i z e dr o u g hs e tm o d e l s ) t 硐；二是粗糙集应用的领域，由最初的信息表、数 据库挖掘，拓展到拓扑代数、实数域、粗糙逻辑和近似推理等。 最初的p a w l a k 粗集理论定义的概念限制性条件太强，在实际应用中往往并 不实用。特别是对于含有噪声的数据进行处理时，得到的规则知识往往存在泛化 能力差的问题。各种扩展的粗集理论模型从不同的角度出发，对p a w l a k 粗集模 型进行了扩展，从而构造出不同的粗集理论扩展模型。从目前的广义粗糙集模型 来看，模型的扩展主要是从逼近算子的构造和粗糙隶属函数的推广两个方面进行 的。逼近算子的构造方向上，包括有两类：( 1 ) 从模型的代数结构人手，将定义 标准粗糙集的等价关系推广为相应的二元关系，得到各种形式的代数粗糙集模型 1 2 2 - 2 3 】；( 2 ) 将粗糙集理论推广到实数域中，研究诸如粗糙数、粗微分、粗积分等 一般数学问题的粗糙函数模型1 2 4 。在粗糙隶属函数的推广方面，主要包括：( 1 ) 将概率论的观点和统计信息引入到p a w l a k 模型中的概率粗糙集模型瞄2 6 j ；( 2 ) 将 粗糙包含概念引入到近似推理中的粗糙m e r e o l o g y 模型1 2 7 j 等。 可变精度( v a r i a b l ep r e c i s i o nr o u g hs e t ，v p r s ) 模型是最为著名的一种粗集 理论扩展模型。它通过引入一个分类误差率系数，将原来的p a w l a k 粗集理论的 第二章使用粗集理论进行数据挖掘 所有基本概念( 如等价关系、上下近似关系、近似质量等) 由绝对条件转变为概 率条件。它在继承原有理论的所有数学特性的基础上，使得模型的推理更加符合 实际情况。文献 1 4 贝j j 着重讨论了可变精度粗集模型中求取属性约简的问题。口 粗集理论模型【1 5 】贝i j 通过向p a w l a k 模型加入“模糊 的思想将粗集理论拓展到可 以处理模糊数据的情况。 对粗集理论数学性质的研究也在不断深入地进行。p a w l a k 区分了粗集理论中 对模糊性和不确定性的定义，指出模糊性是针对集合而言的，而不确定性则是针 对集合中的元素而言的，模糊性也是一种不确定性。文献 1 6 贝j j 定义和分析了粗 集理论中的一致性和完全性，提出学习一致规则和完全规则比学习覆盖上、下近 似的规则更简单。从实际应用的角度出发，文献【1 7 1 和文献【1 8 】对粗集理论中的 问题设计了一系列的算法，并分析了它们的计算复杂度，文献 1 9 贝j j 着重于提高 使用粗集理论求取属性约简算法的效率。 另外，很多的研究集中于粗集理论与其它相关理论的相互关系，如粗集理论 与模糊集理论、d s 证据理论的关系；粗集理论与决策理论、贝叶斯定理的关系 【冽以及粗集理论中定义的知识与信息熵之间的关系等。 2 2 粗集理论的相关基本概念 2 2 1 信息系统 为了处理数据，需要知识的符号表达，在粗集理论中以信息系统的形式给出 s = 。这里的u 是对象的集合，c ud 是属性集合( u 表示并集) ，子 集c 和d 分别成为条件属性和决策属性，y u 。e a v a 是属性值的集合，v 。表示 了属性a e a 的范围，f ：u x a _ y 是一个信息函数，它指定u 中的每个对象x 的属性值。即对于任意a e a , x u ，满足f 伍，a ) v a 。 2 2 2 不可分辨关系 粗集理论主要是基于u 中对象的不可分辨关系的思想。给定属性集p 彳， x u 和对象x ，y e u ，当对所有的a ef ( x ，a ) = f ( y a ) 时，我们就称x 和y 在p 上是不可分辨的。因此，任一属性集p 爿都可以在u 中产生一个二元的不可分 辨关系，以r r q d ( p ) 表示。很明显i n d ( p ) 是一等价关系，i 帅( p ) 或u p 表示通 过等价关系i n d ( p ) 对u 中对象的分类，b 粕表示u 中任一元素x 在i n d ( p ) 下的等价类。定义如下： i n d ( p ) = ( x ，”u u ：f ( x ，a ) = f ( y ，a ) ，va e p ( 2 1 ) 第二章使用粗集理论进行数据挖掘 2 2 3 上、下近似集 粗集对数据的分析主要基于“下近似集 和上近似集”两个重要的基本概 念。给定一论域子集x 的对象元素集合，对于p 的“下近似集”和“上近似集” 分别定义如下： 只伍) = u ：陟】肋( p ) x ( 2 2 ) ，伍) = y eu ： y l ( p ) n x 矽 ( 2 3 ) 只伍) 表示肯定属于x 的元素，p 伍) 表示可能属于x 的元素。集合x 关于 p 的近似质量定义为： 以) = 制 ( 2 - 4 ) 如果似) = 1 ，则x 相对于p 是精确的；否则，x 相对于p 是粗糙的。c a r d ( ) 表示集合的基。 2 2 4 属性依赖关系 假设t = 为一个决策表。分类u i n d ( d ) 关于条件属性c 的 正域，或简称d 的c 正域，定义如下： p o s c ( d ) = u c 。( x ) ( 2 - 5 ) d 在c 上的依赖度定义为： ( 。) = c a r d 面( p o 厕s e ( _ d ) ) ( 2 6 ) 依赖度也称作一致度，如果y cp ) = 1 ，则决策表是一致的；否则它是不一致 的。不一致决策表中含有不一致实例。 如果y c ( d ) = y c 一缸 ( d ) ，则称属性a 相对于d 在c 中是不必要的；否则，a 相对d 是c 的必要属性。 2 2 5 独立度 独立度是独立于知识的度量，也可理解为对对象分类的能力，用公式表示为： i n d 。= 1 只( x y u 1 1 ( 2 - 7 ) 第二章使用粗集理论进行数据挖掘 2 2 6 属性的相对重要度i m p 。 属性的相对重要度反映了不同属性对分类影响的大小，属性的相对重要度可 以去除该属性的子集的独立度差来度量，设两属性子集b 和b + ，且 b 。b ，c b b + 贝u i m p 。一r i d 口一r i d 口 ( 2 8 ) 2 2 7 属性约简 在许多实际数据的分析中各属性之间可能存在着依赖性，当给定尺伍u ) 和 p ( p q ) ，如果i n d ( p ) i n d ( r ) ，则r 依赖于p ，用p _ 尺表示。消除这种依 赖性，也就可以在不影响分类的近似质量时以较小属性集表达整个信息系统。具 体的做法是在尺p q 时，判断口p 伍) ；口r x )