（计算机软件与理论专业论文）基于数据挖掘的道路交通事故分析处理系统研究.pdf

山东师范大学硕士学位论文 摘要 我国是道路交通事故总数，事故死亡人数最多的国家，连续数年一直居世界 第一位。交通事故已严重影响国民经济的发展，社会的稳定以及和谐社会的建设。 为妥善处理交通事故，公平公正的认定事故责任入，减少交通事故，保障国家财 产和人民生命财产安全，国家每年都要花费大量人力、财力用于道路交通事故的 处理。 交通事故的发生既有其特定的、偶然的原因，又受其他各种因素的支配。如 果能够发现道路交通事故数据中各种因素之间的关联，特别是驾驶员、车辆、道 路、天气、时间等可能引起道路交通事故发生的原因因素与事故本身属性中的事 故类型、事故主要原因和现场等可能导致道路交通事故的结果因素之间的规律， 那么交通管理部门就可以根据驾驶员、车辆、道路、天气、时间等因素来判断导 致道路交通事故发生的可能性。从而 x 山东师范大学硕士学位论文 及事故辅助决策分析处理模块。事故基本信息模块可对事故基本信息进行存储， 修改和维护。事故模拟再现模块对事故案例进行模拟再现，展现交通事故的发生 过程，辅助交通管理部门进行决策。事故辅助决策分析模块利用多维a p r i o r i 改进 算法，针对济南市市区的道路交通事故数据进行测试，分析交通事故发生的主要 原因。并对事故信息进行分析总结，认定事故责任。对交通安全给出建议，为决 策者提出具有实际意义的治理方案及预防措施提供了辅助参考。 本系统以数据挖掘的相关理论为基础，利用有效的挖掘方法，从大量的道路 交通事故数据中挖掘出有价值的信息。将数据挖掘应用到道路交通事故数据分析 中，找出环境与事故原因、事故形态之间的联系，分析事故形成的原因。同时根 据事故现场信息，采用虚拟现实技术模拟交通事故发生的全过程，辅助交通管理 部门客观公正地处理交通事故，认定事故责任，提高交通事故处理的工作质量。 关键词：交通事故；数据挖掘；关联规则；多维a p r i o r i 算法；模拟再现 分类号：t p 3 1 1 山东师范大学硕士学位论文 a b s t r a c t w i t ht h em o s tt o t a ln u m b e r0 fr o a dt r a f f l ca c c i d e n t sa n dd e a t ht o l l ，c h i n ah a s b e e nr a n k i n gf i f s tf o rs e v e r a ly e a r si nt h ew o r l d t r a m ca c c i d e n t sh a v es e r i o u s l y a f f e c t e dt h en a t i o n a le c o n o m i cd e v e l o p m e n ta n ds o c i a ls t a b i l i t ya sw e l la st h eb u i l d i n g 0 f h a n i l o n i o u ss 喇e t y t 0p r o p e d yh a n d l et h et r a f f i c ，f i n dr e s p o n s i b l ep e r s o nf o rt h e a c c i d e n tf a i r l ya i l di m p a r t i a l l y ，r c d u c et r a f f i ca c c i d e n t s ，p r o t e c ts t a t ep r o p e r t ya n d p e o p l e sl i v e s ，t h es t a t eh 弱s p e n tal o t0 fm a n p o w e ra i l df i n a n c i a lr e s o u r c e st od e a l w i t hr o a dt r a f f i ca c c i d c n t sc v e r yy e a r t h eo c i c i i l l f e n c eo ft r a f l e i ca c c i d e n t sh a si t ss p e c i f i c ，f o n u i t o u sr e a s o n s ，a n ds u b j e c t t 0t h ei n n u e n c eo fv a r i o u so t h e rf a c t o l _ s i fw ec a nf i n dt h er e l a t i o n sb e t w e e nv a r i o u s f a c i o r si nt h er o a dt r a f f i ca c c i d e n td a t a e s p e c i a l l y ，t h em l eb e t w e e nt m f f i ca c i d e n t s r e 器o ns u c h 舔d r i v e r s ，v e l l i c l e s i o a d s ，w e a t h e r ，t i m e ，w h i c hm a yc a u s et r a f f i c a c c i d e n t s 觚dt h er e s u l tf a c t o 塔蛐c h 鹬t h ea c c i d e n tt ) ，p 伪，t h em a i n 陀a s o n ，s c e n e w h i c hm a yc a u s et h et r a f ! f i c 撤i d e n tr c 跚l t t h e nt h et r a f 乱m 觚a g e m e n td 印a n m e i l t s w i l lj u d g em ep o s s i b i l i t yw h i c ht h er o a dt r a f ! f i ca c c i d e n t0 c c l l 娼a o c 0 r d i n gt ot h ed r i v e r s ， v e l l i d e s ，r o a d s ，w e a t h e ra n dt i m ef a c t o r s i t c a ng u i d et h e 仃a f ! f i c m a n a g e m e n t d e p a n m e n tt ow o r kb e t t e r 锄dt h e r ci sg r e a ts i 印i f i c 锄c ei nr e d u c i i l g 也eo c c u r r e n c eo f a c c i d e n t s ht h i sa n i c l ei tm a l 【e s 弱s o c i a t i o nm l e sd a t am i i l i l l ga m o n gt h er o a dt r a f ：f i c a c c i d e n tc h a r a c t e r i s t i c s ，d r i v e r s ，v e h i c l e sa i l dm a df a c t o r s ，s i m u l a t e st r a f n ca c c i d e n t u s i n gv i n u a lr e a l i t y ，a l l d 柚a l y s c s t h el m f ! f i cd a t a n e r e b yi t h e l p st h ct r a 雎c m 强a g e m e n td e p a r t m e n t st 0i d e n t 毋a c c i d e n tr e s p o n s i b i l i t yf a i r l y 觚di m p a n i a l l y 1 l l e m a j o rr c s e a r c hw o r k sa r e 舔f 矾l o w s ： 1 r o d u c i n gt h c c l l i 高度非线性、不可导、 x 独创声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 它人已经发表或撰写过的研究成果，也不包含为获得( 注：如没有其它需要特别声明的，本栏可空) 或其它教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位做作者签名疹北莽 导师签字： 学位论文版权使用授权书 叫 本学位论文作者完全了解兰邀有关保留、使用学位论文的规定，有权保留并 向国霎雾薹嵇雾蓊蓁萋露辫。嚣荦冀羹 蠢篓；蓁葡薹薹蓁薹雾羹殛篓蓁霸。萤醺墼冀童蓁；| 蓁琴垂墓萋兰蒌篓冀| | | 萋篱霎 秦 忠强等碰撞检测在大型虚拟场景中的应用工程图学学报【j 】，2 0 0 7 ( 1 ) ：3 3 3 6 1 9 王天柱，李文辉等基于组建的虚拟手建模及碰撞检测吉林大学学报【j 】，2 0 0 6 ( 4 ) ：5 9 9 6 0 5 2 0 王冬冬，王琰，祁燕基于树状层次有向包围盒的碰撞检测算法【j 】沈阳理工大学学 报，2 0 0 6 ( 1 0 ) ：1 3- 1 5 2 1 和莉，刘惠义碰撞检测技术在三维交互漫游系统中的应用计算机技术与发展【j 】，2 0 0 6 ( 6 ) ： 山东师范大学硕士学位论文 1 1 研究背景第1 章绪论道路交通事故是一个世界性的社会问题，它已成为国际社会一大公害。随着 我国国民经济、城市规模的快速发展，道路及交通设施日新月异，机动车、非机动车保有量平均每年以1 5 - 2 0 的速度增长，城市节奏日益加快，与这一切喜人 发展相对立，道路交通事故( 特别是重大事故) 每年都呈上升趋势。 据公安部统计，2 0 0 1 年我国共发生7 5 5 万起交通事故，死亡人数为1 0 6 万 人。2 0 0 2 年全国共发生道路交通事故7 7 3 万起，造成1 0 9 万人死亡。2 0 0 3 年全 国共发生道路交通事故6 群嚣耍鸶魏募霹；8 i 篓i 霪警蒌萎黼鬻簋委1 霎蓁 圈鎏雾；霾蓁同竖蓁鋈塾；醢羹霪霆霆蚕蓁甬i 耋o n t h eb a s i so fa n a l y z i n go fe x i s t i n ga l g o r i t h m s ，at w c tt r e es t r u c t u r ei s p r o p o s e dw i t ht i l te d - t i m ew i n d o wf r a m e w o r ki n t e g r a t e d ，w h i c hc a l lm a in t a i n st h e c o m p l e t es e to ff r eq u e n tp a t t e r n sa tm u l t i p l et i m eg r a n u l a r i t i e s a n dw ed e s i g nt h e s e q u e n t i a lu p d a t ea n dd e l e t ea l g o r i t h m sf o rt h es t r u c t u r e ，w h i c hm a k e si tc a nb e s a v e di na u x i l i a r ys t o r a g ei no r d e rt or e d u c et h ea l g o r i t h m s r e q u i r e m e n t so ft h e m a i nm e m o r ye f f e c t i v e l y t a k ea d v a n t a g eo ft h i sc h a r a c t e r i s t i c , t w c t - s t r e a m ，a f r e q u e n tp a t t e r nmi n i n ga l g o r i t h mi nd a t as t r e a m ，i sp r o p o s e d a n di t sp a t t e r ng r o w t h a l g o r i t h m ，t w c t - gr o w t h ，g e n e r a t e sf r e q u e n tp a t t e r n si nl e x i c a lo r d e rs u i t a b l ef o r t h es e q u e n t i a lu p d a t i n go f i w c ts t r u c t u r e e x p e r i m e n t sh a v ep r o v e di t sm e m o r y r e q u i r e m e n t sl o w e rt h a nt h es a n l ek i n do f a l g o r i t h m sl i k ef p s t r e a m a n ds oo n 一w ep r o p o s ev d t - s ws t r u c t u r eb a s e do ns l i d i n gw i n d o wm o d e l ，w h i c hh a s c h a r a c t e r i 【s t i e so fh o r i z o n t a la n dv e r t i c a ld a t af o r m a t t h i ss t r u c t u r ei sc o n v e n i e n tf o r u p d a t i n gd a t ai ns li d i n gw i n d o w , a n di tc a ni n t e g r a t ew i t hv a r i o u sk i n d so ff r e q u e n t p a t t e r nm i n i n ga l g o r i t h m s a n dal o w e rt i m ec o m p l e x i t ya l g o r i t h mo ff a s ti t e m s e t c o u n tq u e r y , n a m e dv d t - s w - q u e r y , i sp r o p o s e d a p p l y i n gf r e q u e n tp a t t e r nm i n i n g i nd a t as t r e a mb a s edo nv d t - s ws t r u c t u r ei nt h ef i e l do ft e l e c o m m u n i c a t i o nd a t a a n a l y z i n g ，ad a t as t r e a mp r o c e s s i n gs y s t e mm o d e li sd e s i g n e d ，w h i c hc a no f f e r v a l u a b l ei n f o r m a ti o nf o ro p e r a t i o n sa n dm a i n t e n a n c eo fc o m m u n i c a t i o nn e t w o r k t h r o u g ht h em i n i n go fc o m p l a i n tr e c o r d s m i n i n gf r e q u e n tp a t t e r n si nd a t as t r e a mh a sb e e no n eo ft h ef o c u s e so fd a t a 山东师范大学硕士学位论文 1 2 研究现状 目前，交通事故处理过程大致分为三个阶段：事故现场勘查取证、事故原因 和过程分析以及根据分析结果进行事故责任认定。 在上述三个阶段中，第一阶段工作是在交通事故现场完成的，我国交通管理 部门处理事故现场的常用方法1 3 】是：先封锁事故地点的部分或全部车道，工作人 员人工判断刹车车轮胎印、通过皮尺、目测等方法量测刹车距离和各种有关数据， 拍摄现场照片，访问目击证人。然后根据人体伤痕部位或车的破损情况，来判断 车辆与人或物相撞的情况。最后对这些资料进行分析，分清驾驶员与被害者的责 任大小。这种处理方法能够给交通事故的处理提供足够的材料，但也存在明显的 缺陷：在事故分析处理过程中，由于工作人员的经验和掌握的材料不同，处理上 会产生偏差。 我国道路交通事故研究主要建立在采集分析统计大量交通事故数据资料的基 础上，主要依靠公安部9 8 版和2 0 0 3 版事故信息管理系统或其它一些省市自己组 织的道路交通事故管理软件系统，这些系统都具有数据采集、传输、查询和统计 功能。一般的情况是，事故处理的基层单位各事故大队负责本区域内的数据采集 和事故报表统计，同时向支队传输数据，支队在完成本区域内的数据汇总和统计 的同时向总队传输数据，总队完成全省范围内的数据汇总、报表统计并向公安部 传输数据，公安部根据各省上报的数据进行汇总和统计。从数据采集上来讲，这 些数据的采集工作都是各级部门人为进行的，所以在各级之间采集和统计的数据 可能会存在差异，出现数据缺失或不标准的情况。从数据统计上来讲，系统统计 着重于对事故发生后的经济损失和死伤人数的简单统计，未能反映出事故发生的 条件因素，难以为基层交通事故预防、处理、决策工作服务。 目前国内道路交通事故的分析决策等基本上处于手工处理阶段，而手工处理 是导致大数据量的交通事故分析决策工作效率低下，准确性差的主要原因。因此， 对道路交通事故的分析决策工作进行科学的研究和有效的改善势在必行。如果能 够重视事故数据库系统的建立，通过相应的数据挖掘模型，则可以高效快捷地发 现事故的新规律，有利于从事故中吸取教训。 将事故涉案车辆由碰撞后的终止位置反推回碰撞过程，再反推回碰撞前的运 行状态，来分析事故原因，然后根据有关法律规定进行责任认定。近年来发展起 来的事故重建技术，为这种事故分析方法提供了科学的手段。当前主要的交通事 故现场重建方法，有二维方法、三维方法等。交通事故智能处理系统侧重分析事 故发生的过程，事故重建技术为事故分析提供了先进科学的手段。许多国家相继 研究出了用于事故重建的应用软件，如美国国家道路交通安全局( n h t s a ) 资助开发 了大型事故再现软件系统s m a c 和c r a s h ；奥地利开发了p c c r a s h 、e e s a r m 、h 、o s m 2 山东师范大学硕士学位论文 及i m a p g 等。这些系统一直在不断地完善发展中。 国内也已经开始了探索汽车碰撞事故的计算机模拟研究。清华大学汽车研究 所与云南省道路交通管理科学技术研究所合作开发的“道路交通事故再现分析系 统”，也取得了一定的成果。但是我国在这个领域的研究还处于起步阶段，事故数 据处理和计算机模拟研究的基础很薄弱，需要进一步发展和改进。 以数据挖掘的相关理论为基础，利用有效的挖掘方法，从大量的道路交通事 故数据中挖掘出有价值的信息，为解决道路交通问题提供了一个新的思考方式。 将数据挖掘应用到道路交通事故数据分析中，找出道路环境与事故原因、事故形 态之间的联系，分析事故形成的原因。并根据事故现场信息采用虚拟现实技术模 拟交通事故发生的全过程，辅助交通管理部门客观公正地处理交通事故，认定事 故责任，提高交通事故处理的工作质量。 1 3 本文的内容及工作 本文主要研究的是道路交通事故的关联规则数据挖掘，并用虚拟现实技术模 拟交通事故的发生过程，实现对交通事故数据分析，从而辅助交通部门公平公正 的认定事故责任。具体的组织结构如下： 第l 章绪论。概述了道路交通事故分析处理系统的研究背景和现状，介绍了 本文的主要内容。 第2 章道路交通事故分析处理技术。先介绍了常见的交通事故致因研究方 法，然后介绍了数据挖掘理论、关联规则、a p r i o r i 算法以及多维多层的关联规则。 最后介绍了交通事故现场模拟再现关键技术，o b b 包围盒碰撞检测算法及三维仿 真技术。 第3 章道路交通事故分析处理系统模型。针对道路交通事故这一具体问题， 分析道路交通事故属性后确定基于关联规则的星型全连接的数据模型，用改进的 多维a p r i o r i 算法提取关联规则。 第4 章道路交通事故分析处理系统的开发与实现。将系统分成事故基本信息 处理模块、事故模拟再现模块及事故辅助决策分析处理模块三个模块。可对事故 进行基本信息处理，对事故信息进行分析总结，认定事故责任，并对道路交通安 全给出建议。 第5 章总结与展望。对本文的研究工作做了一些总结、评价和展望。 3 山东师范大学硕士学位论文 第2 章道路交通事故分析处理技术2 1 交通事故致因研究方法 道路交通安全法对交通事故的定义为：车辆在道路上有过错或意外造成 的人身伤亡或财产损失的事件。交通事故是多种因素综合作用的结果，从交通事 故的发生原因到交通事故的后果，交通事故涉及道路设计、施工、使用、路面秩 序、人身伤害和财产损失多个领域。不同领域的研究者因其研究目标各异，而采 用不同的研究方法。这些研究方法包括： ( 1 ) 模拟 互塑 鹕童鬻娥斟鞋割雾陴鹚疆姿譬瞪；曼犁暮垣曼雾利蔫蒙。鬯备霎狂缝翌套 霾毽掘羞毯期则苊塑。 i 毒l 鬻劐型纛晤 型蓄誉譬藩够擎蓁俺揣攀鋈j 苍墓蓑黠魁盔圭；燮幕篓祸萄蠡西捌酣彰墅歪 一袷笳掣话签娶篷掣簇鎏亏零系统；删鄞 的发生而引起另外一些事件的发 生。关联规则在决策支持系统、专家系统和智能信息系统等各个方面有着重要的作用。数据挖掘中产生关联规则的方法以及应用方面的研究已取得很大的成绩，并 已被集成在一些系统中，如i b m 的q u e s t 项目，s i m o n f a r s e 大学的d b m i n e r 等。几年来，诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作 包括对原有的挖掘算法进行优化，如aprioritid、apriorihybrid、fup、cad、 p d m 、m l 等，以提高算法挖掘规则的效率，对关联规则的应用进行推广。_t2l1 2 2 1 关联规则基本概念 设，一 f 。，f ：，) 是二进制文字的集合，其中的元素称为项( i t e m ) 。设d 为相 关的数据集合，也就是一个交易t ( t r a n s a c t i o n ) 数据库，这里交易t 是一个数据项 的子集合，并且t i 。对应每一个交易有唯一的标识，记作t i d 。 4 ，4 2 ，彳一b ，b 2 , - - - , b 。，其中，a i o 一1 ，2 ，n ) 和b ，( j 一1 ，2 ，m ) 代表 谓词或数据项，这样的规则通常解释为“在相同的事务中，当彳，彳：，4 发生时， 常常b 1 ，b ：，吃也发生。 设a 是一个项集，事务t 包含a 当且仅当4 t 。则 关联规则是形如a 号b 的蕴涵式，其中么，b ，并且彳n 口；巾。 规则爿穹b 在交易数据库d 中的支持度( s u p p o a ) 是交易集中包含a 和b 的 交易数与所有交易数之比，记为s u p p o r t ( a 净b ) ，即p 0u 口) 5 rt(a净b)，即p0u 口) 5 山东师范大学硕士学位论文 学和心理学等各个因素的影响。对事故进行精确的数据采集、分析和再现。 2 2 数据挖掘 数据挖掘【4 1 ( d a t am i n i n g ，简称d m ) 就是从大量的数据中挖掘出有用的信息， 是根据人们的特定要求，从浩如烟海的数据中找出所需的信息供给人们的特定需 求使用。 关联规则( 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 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，它反映一 个事物与其他事物之间的相互依赖性或相互关联性。关联规则挖掘大量数据中项 集之间有趣的关联或相关联系，侧重于确定数据中不同领域之间的联系，找出满 足给定支持度和置信度阈值的多个域之间的依赖关系。挖掘关联规则是指在数据 库中挖掘出具有这种形式的规则：由于某些事件的发生而引起另外一些事件的发 生。关联规则在决策支持系统、专家系统和智能信息系统等各个方面有着重要的 作用。 数据挖掘中产生关联规则的方法以及应用方面的研究已取得很大的成绩，并 已被集成在一些系统中，如i b m 的q u e s t 项目，s i m o nf a r s e 大学的d b m i n e r 等。 几年来，诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作 包括对原有的挖掘算法进行优化，如a p r i o r i t i d 、a p r i o r i h y b r i d 、f u p 、c a d 、 p d m 、m l - t 2 l 1 等，以提高算法挖掘规则的效率，对关联规则的应用进行推广。 2 2 1 关联规则基本概念 设，一 f 。，f ：，) 是二进制文字的集合，其中的元素称为项( i t e i n ) 。设d 为相 关的数据集合，也就是一个交易t ( t r a n s a c t i 伽) 数据库，这里交易t 是一个数据项 的子集合，并且t i 。对应每一个交易有唯一的标识，记作t i d 。 4 ，4 2 ，彳一巨，b ：，b 。，其中，4 0 一1 ，2 ，n ) 和b ，( j 一1 ，2 ，m ) 代表 谓词或数据项，这样的规则通常解释为“在相同的事务中，当彳，彳：，4 发生时， 常常曩，b ：，吃也发生。 设a 是一个项集，事务t 包含a 当且仅当4 丁。则 关联规则是形如彳号b 的蕴涵式，其中么，b ，并且彳n 口；巾。 规则爿穹曰在交易数据库d 中的支持度( s u p p o n ) 是交易集中包含a 和b 的 交易数与所有交易数之比，记为s 卿d 似么净b ) ，即p 0u 口) 5 山东师范大学硕士学位论文 2 2 2 关联规则分类关联规则按不同的情况可进行如下分类。 ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系；数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段 进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型 关联规则中也可以包含种类变量。 ( 2 ) 基于规则中数撵蓁副萋蝻酣羹虱观察蒸霎剖鲴雕剩剿i 嗍翁怦璩缔降呤胆；劐翻匪塑孽草垂型暨矍灞徭氍星蠢譬醛鹤繇霎量薪霆捌 姆栓苌! 一蒯狴璀渐碍醺蒹。酾耐衔釜薹畦摊雾旧嘲嘴冀勘羹数据子j | 奏! 雾惑叶箨蓁u 拶猷则骢羹蓁痧舫i 穗薄劈隗潜囊萄蓁镒锩倘蠡羹断； 窝国籍俪簪晕惑囊j 析的薷缈劐到型一 时 间顺序为主的项集发生序列。 2 2 4 多维多层关联规则 以上介绍的关联规则都只涉及一个谓词，是单维单层的。大多数的数据库都 是复杂的多维多层的，这样就要考虑挖掘多维多层的关联规则。 2 2 4 1 多维关联规则 在多维数据库的研究中，称规则的每一个不同的谓词为维( d i m e n s i o n ) 。将规 则中每个不同的谓词当作一维，称为单维关联规则，包含两个或更多谓词的关联 规则称为多维关联规则。 在利用多维数据模型进行关联挖掘时，根据规则中出现的维度的数量及种类， 从数据库中可发现三种类型的规则： ( 1) 维内关联规则( i n t r a d i m e n s i o n 加；s o d a t i o nr u l e ) ：一条关联规则只包含一 个惟一的维，也称为单维关联规则( s i n 西e d e m e n s i o nr u l e ) 。 ( 2 )维间关联规则( i i l t e r - d i m e n s i o na s s o c i a t i o nr u l e ) ：一条关联规则的主体和 头包含两个或多个不相同的维，在这个关联规则中所有的项目都在不同的维中， 且没有重复。 ( 3) 混和维关联规则( h y b r i d d i m e n s i o n 缸s o c i a t i o nr u l e ) ：上两种关联规则的 合成，一条关联规则包含多个维，其中有重复出现的维，也称为多维关联规则。 在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类： 种类型和数值型。对于种类型的字段，原先的算法都可以处理。而对于数值型的 字段，需要进行一定的处理之后才可以进行。处理数值型字段的方法基本上有以 山东师范大学硕士学位论文 下几种： ( 1 ) 数值字段被分成一些预定义的层次结构。这些区间都是由用户预先定义 的，得出的规则叫做静态数量关联规则。 ( 2 ) 数值字段根据数据的分布分成了一些布尔字段，每个布尔字段都表示一 个数值字段的区间，落在其中则为1 ，反之为0 。这种分法是动态的，得出的规则 叫布尔数量关联规则。 ( 3 ) 数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的 因素，得出的规则叫基于距离的关联规则。 ( 4 ) 直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字 段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而 得出一些有用的规则叫多层数量关联规则。 根据处理数值量的三种基本方法对挖掘多维关联规则【7 l 相关技术进行分类讨 论： ( 1 ) 利用概念层次树将定量属性离散化。这一离散化过程需要在数据挖掘之 前完成，这里的离散化是静态的且是事先确定好的，利用区间范围离散化后所获 得的数值量就可以当作符号量。这种挖掘就被称为是利用定量属性静态离散化的 多维关联规则挖掘。 ( 2 ) 基于数据分布而将定量属性离散化，在挖掘过程中将离散量做进一步的 组合。离散过程是动态的，以满足某种挖掘标准。这种方法仍将数据属性当作数 值而没有当作事先确定好的范围或符号，利用这种方法挖掘出的关联规则就称为 定量关联规则。 ( 3 ) 量化属性离散化，以紧扣区间数据的语义。动态离散化过程主要考虑数 据点之间的距离，这类定量关联规则称为基于距离的关联规则。 2 2 4 2 多层关联规则 对于很多的应用来说，由于数据在多维空间中存在的多样性，所以很难在数 据细节的层次上发现一些强关联规则。当引入概念层次后，就可以在较高的层次 上进行挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用 户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样 一种在多个层次上进行挖掘相应关联规则知识的能力，并能够较为容易对不同抽 象空间的内容进行浏览与选择。 由于利用概念层次树所挖掘出的关联规则涉及到多个概念层次，因此这样的 关联规则就称作多层关联规则。根据规则中涉及到的层次，多层关联规则可以分 为同层关联规则和层间关联规则。 多层关联规则的挖掘基本上可以沿用“支持度置信度 的框架。同层关联规 1 1 山东师范大学硕士学位论文 则可以采用两种支持度策略： 1 圆型黔酷塑紊裂；酉茎垂篡蠢舞塑包俐i 莲型蓉姒封衙鳟谣j 那雠 副篱签委辈薹翼葡薹智霉二省攀谶褥滗液绻匾。了鑫叩维生霎则该候选项! 集丝 尘魁群撼塑嚣毁i 划刚型坚霎蚕嘶，憎鞴薹翼一明问扣静舀两；础耐钥扫剃弱砸 邕羹强制礁渖臻薹髓虢筘目。贼爵廉隆蔗黼喜q 蓁；涟滴淄翠笾留雀繁善螽翟曩 蕲型鬻添学含萑果项集i 不满足最小支持度阈值m i n _ s u p ，则i 不是频繁的，即 尸( ，) k ) 扫描数据库时 不再需要它们。 ( 3 ) 基于划分的方法( 为找候选项集划分数据) 为了降低算法对内存的需求同时提高并行性，基于划分的方法把数据库从逻 辑上分成几个互不相交的块，每次单独考虑一个块并对它生成所有的频繁项集， 然后把产生的频繁项集合并，用来生成所有可能的频繁项集，最后计算这些频繁 项集的支持度。 ( 4 ) 基于选样的方法( 在给定数据的一个子集挖掘) 所谓采样技术就是对给定数据集的一个子集进行挖掘。选取给定数据库d 的 随机样本s，在s 中而不是在d 中搜索频繁项集，得到一些在整个数据库中可能 成立的规则，然后对数据库的剩余部分验证这个结果。用这种方法，牺牲了一些 精度换取了有效性。当效率最为重要时，如计算密集的应用必须在频繁度不同的 数据上运行 x 山东师范大学硕士学位论文 2 3 交通事故现场模拟再现关键技术 交通事故发生后，根据事故现场照片、事故信息，获取碰撞后车辆位移、损 坏程度、拖痕长度、路面情况等现场特征。通过事故现场模拟方法，来研究事故 发生前后车辆速度运行轨迹，最后将模拟的运行以屏幕显示，说明事故发生过程。 较好的协助交警处理事故，认定事故责任人。 2 3 1 碰撞检测 假设三维空间中有n 个运动模型，随着时间改变位置和姿态，通俗的讲碰撞 检测就是判断是否存在一对或多对模型占有的空间发生重叠。从计算几何的角度 可以这样理解碰撞检测：设三维几何空间为r ，用三维几何坐标系统昂表示，在 岛中用l 表示模型a 所占的集合，虽然l 是的子集，) g z , 随着时间的变 化构成了一个四维空间坐标系统c 0 ，模型a 沿着一定轨迹运动就形成了c 矽的子 集表示为巳。碰撞检测【1 0 】就判断气c 肼妒是否成立。 这个定义在理论上给出了碰撞检测的精确方法，但是它的实现代价非常高， 其中的瓶颈问题就是四维集合c 。的计算，这种计算的复杂度在实际中是不能接受 的，但可以牺牲计算的精度，提高计算速度。 2 3 1 1 影响碰撞检测的要素 碰撞检测的方法很多，但各有其优缺点和适应范围。为设计和选择合适的方 法，需要从以下五个方面来做需求分析。 ( 1 ) 实时性 虚拟环境中碰撞检测的研究目标是如何在很高的实时交互要求下完成对大量 复杂物体的碰撞检测，最根本的是降低算法的复杂度。 ( 2 ) 精确度 采用近似检测还是精确检测取决于具体的应用。 ( 3 ) 模型类别 模型类别是静态检测的基础。关键是解决不同类型的模型的相交检测问题。 虚拟环境中的物体所用的模型首先可大致分为面模型和体模型两大类。面模型用 物体边界来表示物体，不包括物体内部信息。体模型采用体元来表示物体，可描 山东师范大学硕士学位论文 述物体的内部信息。现在碰撞检测的研究工作大多是基于面模型的。面模型又可 分为多面体模型、c s g 、隐式曲面、参数化曲面等。不同的模型类别决定了采用 不同的方法进行检测。 ( 4 ) 检测类别 可根据对检测结果的如下4 种要求来分析： 检测是否有碰撞。 检测碰撞发生的位置。 检测物体间的距离。 检测下一次碰撞将在何时发生。 最常见的情况是要求得到前两个检测结果，但后两个结果也可运用于检测碰 撞，预测碰撞和避免碰撞。 ( 5 ) 场景特征 场景可按物体的运动状况分为静态部分和动态部分。动态物体越多，碰撞发 生的概率越大，碰撞检测的复杂程度也就越高。 场景中的运动物体还可分为刚性和柔性( 或称可变形物体) 两种。刚体在运动 中不改变物体的形状，其运动形式只限于平移或旋转，柔体在运动中则除了平移 和旋转外，还可以变形。柔体的碰撞检测比刚体的要复杂的多。 2 3 1 2 碰撞检测方法 最简单的检测方法是固定时间片长度的碰撞检测方法，其特征是给出一个适 当小的固定时间片，在每个时间片末，系统对空间内所有对象间的位置关系进行 一次碰撞检测。如果检测到碰撞则接下来可以做进一步处理。这样做的一个前提 条件是，时间片的选取必须保证不发生漏报现象，即碰撞发生了却没有检测到。 当空间中物体体积相对于速度来说很小时，将会增加静态检测算法的调用次数( 即 检测次数) ，计算量和计算时间加大。为同时获得满意的速度和准确性，提出了基 于可变时间片长度的碰撞检测方法。其基本思想是：在两个物体距离较远时，时 间片可以取地很大，越是靠近碰撞的发生，时间片取地越小，需要的碰撞检测次 数也就越多，这一问题称之为时间步长问题。 当判别出物体问的距离很小时，为了防止漏报的发生，这时时间片选取的比 较小，计算量非常大，为了降低计算量，提高运算速度，可通过去掉一些明显不 可能发生碰撞的物体对，避免对所有物体对做求交测试。这一问题称之为多物体 对测试问题。 另外，由于物体本身的模型可能很复杂，若直接用原模型来检测两物体的碰 撞，这时要对两物体的所有顶点、边和面均进行求交计算，计算量非常大。此处 也可以通过各种技巧加以改进，如包围盒方法，减少将要发生碰撞物体中需要检 1 4 山东师范大学硕士学位论文 果被检测的几何体是一些简单的几何体那么它们之间可能潜在的分离轴是可以事 先计算出来的。在测试的时候只需测试这些潜在的分离轴，而不用漫无边际的根 据定义去找分离轴。计算量大大减少。 三维空间中任意方向的长方体与长方体之间的潜在分离轴最多有1 5 根。它们 是每个长方体的三根方向轴，有3 2 = 6 根潜在分离轴，一个长方体的一条边矢 量与另一个长方体的边矢量的叉乘，有3 x 3 - - 9 根潜在分离轴；总共有6 + 9 = 1 5 根 潜在分离轴。如果两个长方体相互平行，那么实际潜在分离轴退化为3 根非零矢 量，即长方体的方向轴矢量；如果此时长方体的方向轴和坐标轴平行，就成为 a a b b 包围盒的情况。 ( 2 ) 包围盒的重叠测试算法 包围盒类型不一样，包围盒重叠测试算法也不一样。基于分离轴理论的算法 是进行重叠测试的最佳选择。a a b b 包围盒分别在三根分离轴上投影之后，在每 一根分离轴上采用区间测试，可以确定两个a a b b 包围盒是否重叠。区间测试在 每根轴上最多进行两次，每一对包围盒最多进行6 次比较运算；即在每根轴上进 行这样的比较：设a 包围盒在x 轴上的投影的最小值为a x 晌，最大值以嗽；b 包围盒在x 轴上的投影的最小值为b 晌，最大值也一；如果a x 曲 见一，那 么a 与b 不相交；如果4 一 = m i n j u p ) t h e n 厶= 厶u 口) ； ) r e t u m t ； 第二步：产生关联规则。 输入：1 ) 频繁项集l 。 2 ) 最小置信度阈值m i n n 。 输出：关联规则r r = m ； f o re a c hf r e q u e n t f = ，l ，2 ， ) l c o n ( s 辛伊一s ) ) = s u p p o n ( d s u p p o n ( s ) ；项f 中的每个非空子集s 山东师范大学硕士学位论文 i fc o n m i i l j c o n ； n l l er “s 专( 厂一s ) ”； r = r u r ) ； 多维a p r i o r i 算法的基本工作原理： 第一步找出所有符合最小支持度的频繁项集。在此阶段，输入的是与任务相 关的n 维数据库d 【d 1 ，d 2 ，琅】，最小支持度和用户的限制条件。根据关联规则 的类型【4 2 1 ，输出的是满足条件的多维频繁项集【4 3 1 。 该算法以a p r i o r i 算法为基础，在关联规则挖掘时，把要挖掘的维称为项目维， 而把与这个维相关的另外的维称为事务处理维，产生频繁项集的算法m 和a p d o r i 算法类似，只是在判断是否满足最小支持度时，a p r i o r i 算法扫描的是交易数据库， 而该方法扫描的是部分数据库。由于维之内关联规则挖掘的频繁项集产生方法和 a p r i o r i 算法的一样，而合成关联规则挖掘的频繁项集产生方法是维之间关联规则 挖掘频繁项集产生方法。维之间关联规则就是存在于一组维之内的关联规则【4 5 1 。 因为项目存在于不同的维中，这里通过利用数据库的概念分层结构来直接获取每 个项目集的置信度。 根据a p r i o r i 性质( 一个频繁项集的所有非空子集必须也是频繁项集) ，算法首 先找出每一维所有的1 - i t 锄s e t s 候选项集c 。、频繁项集。，然后迭代循环从频繁 项集厶一。中陆续找出k i t 锄s e t s 候选集q 、频繁项集厶。 算法改进的是候选集q 的产生方式，即函数g e 玎柚d i d a t e o 中候选集的产生。 在产生新的候选集时，在k - 1 项频繁集中，任取频繁子集z 。和z ：，判断f 1 中每一个 项i 所在的维m 是否在l 中所有项所在维的集合m 中存在，如果不存在，则将粒 度i 加入z ：中，产生k - 项集c ，然后判断c 能否加入候选集c 。中。在函数 g e n i n f r q u e n t o ，从候选集c 中生成频繁项集k ，在生成厶时，首先通过连接操 作厶一，e q 来生成可能的k i t e m s e t s ，再利用a p r i 嘶性质对连接生成的可能的 k i t e m s e t s 进行删除，只有满足此性质的将其加入到候选k i t e m s e t s 的集合g 中。 对于每一个候选k - i t e m s e t s ，丁c i ，统计在k - 维数据表中与之对应的计数值( 支 持度) ，根据数据定义，存储在属性数据中的c o u n t 值是从原始属性集数据中的一 山东师范大学硕士学位论文 个聚集值，即为该属性数据所代表的项目集的频度，将它与最小支持度m i ns u p 比较，如果大于，则将其加入到l 。中。 第二步是利用前面产生的频繁项集产生期望的关联规则。在此阶段，输入的 是