（计算机应用技术专业论文）模糊聚类及其在交通事故黑点成因分析中的应用研究.pdf

江苏大学硕士学位论文 摘要 在各类事故中，交通事故无论从发生次数，还是从死亡人数上来 讲，都位列各类事故之首，且呈上升势态，其死亡人数约占各类事故 总死亡人数的7 0 。2 0 0 1 年起交通事故死亡人数突破l o 万( 1 0 6 万) 大关，交通安全问题成了道路交通运输领域亟待解决的重要问题。事 故黑点作为交通事故的高发点段，所造成的经济损失及伤亡人数都占 有较大比重，黑点的形成原因并不是单方面的，往往是由两个或者多 个原因共同弓【起的，如何判定事故黑点、分析黑点成因及对未知黑点 进行排查是当前交通管理工作的难点所在。研究、分析事故黑点的成 因及其影响度，可以为事故黑点的预防及解决提供决策支持，对降低 我国的交通事故数量，提高交通管理工作的实效性，提升我国交通的 综合形象具有重要意义。 聚类分析作为数据挖掘技术的重要组成部分，是分析海量、复杂 数据的有效工具，获取智能决策信息的主要手段。传统获取信息的方 式是从单数据集合挖掘知识，而忽略了多数据集合之间的合作影响。 而事故黑点成因并不单一，存在多种因素各自独立而又相互合作影响 的情况。面对交通事故的日趋严峻，事故黑点的逐日增加，利用信息 合作来对其成因进行分析，更确切的反映实际情况显得尤为必要。 本文以某事故黑点为例，在模糊聚类分析方法的基础上，深入研 究了基于信息合作的模糊聚类法在事故黑点成因分析中的应用，着重 开展了以下研究工作： 1 对各种模糊聚类初始化算法进行分析比较，提出了改进的模糊 聚类初始化算法，通过计算平均信息熵值结合减法聚类方法对模糊聚 类数目和初始聚类中心进行优选。 2 选择信息合作聚类算法模型进行数据集之间的合作分析，针对 应用提出改进的合作模糊聚类算法，对选择初始中心点的方法以及聚 江苏大学硕士学位论文 类有效性函数方面做了改进，实验结果说明合作模糊聚类算法在迭代 次数和接近类中心程度上优于合作聚类算法。 3 提出并分析、实现了基于合作模糊聚类的事故黑点成因分析方 法，以某事故黑点为例进行实例分析，结果表明该合作分析法能用于 实践辅助决策。 最后总结了全文的工作和创新之处，并对进一步应用研究进行了 展望。 关键词：交通事故黑点，事故黑点成因，信息合作，信息增益，平均 信息熵，合作模糊聚类 a b a st r a c t a m o n ga l ll d n d so fa c c i d e n t s ，t r a 衙ca c c i d e n t sa r ea l w a y so nt h et o p r a m ( ，n o t0 n l yo n 丘e q u e n c yb u ta i s oo nc a s u a i t y ，a n di th 弱at e n d e n c yo f c l i m b i n g t h ec a s u a l t yo ft r a 硒ca c c i d e n t st a k e sa b o u t7 0p e r c e n to ft h e t o t a la c c i d e m s s i n c et h ec a s u a l t yo ft r a 硒ca c c i d e n t sb r o k et h ea m o u n to f 10 0 ，0 0 0 ( 16 0 t h o u s a l l d )i n2 0 0 l ， t r a 珩c s a f e t yh a sb e c o m ea nu r g e n t p r o b l e mw h i c hs h o u l db es o l v e di n t r a n s p o r t a t i o nr e a l m a sah ig h f 沁q u e n c ys e c t i o no ft r a 衔ca c c i d e n t ，t r a 伍cb l a c k s p o tc a u s et r e m e n d o u s e c o n o m i cl o s sa n dc a s u a l t mw h i c ht a k eag r e a tp a no ft h et o t a l t h er e a s o n p 一 一 t o rb l a c k 。s p o tf _ 0 n n l n gl sn o tmo n ea s p e c t i ta l w a y sc a u s e db y 帆oo r m o r er e a s o n s h o wt oc o n f i m b l a c k s p o t ，h o wt oa 1 1 a l y z eb l a c k s p o ta n d h o wt oc h e c kt h e ma r ed i 伍c u l t p o i n t sf o rp r e s e n tt r a 衔cm a n a g 锄e n t r e s e a r c h i n ga i l da 1 1 a l y z i n gr e a s o n so f b l a c k s p o tf o m i n ga i l di t si n n u e n c e c a nn o to n l yp r o v i d e d e c i s i o n - m d k i n gs u p p o r t sf - o ra c c i d e n tb l a c k s p o t p r e v e n t i n g ，b u t a l s oh a v eg r e a t m e a n i n gf o rr e d u c i n gt r a 伍ca c c i d e n t s 舶q u e n c y ， e 1 1 l l a n c i n g仃a m cm a i l a g e m e n te f i k t i v e n e s sa n dp r o m o t i n g g e n e r a l i m p - e s s i o no fo u rc o u n t 巧st m 衔c a sa ni m p o r t a n ts e c t i o no f d a t a 商n i n g ，c l u s t e 咖gi s 锄e 毹c t i v et o o l f o ra n a l y z i n gl a 唱ea m o u n ta n dc o m p l i c a t ed a t aa n dam a j o rm e a n sf o rg e t i n t e l l i g e n td e c i s i o n - m a h n gi n f o m a t i o n t h et r a d i t i o n a lm e a n so fg e t t i n g ，- - -一 m 士。加：1 a t l o nl sm m m g k n o w l e d g e 丘d ms i n g l ed a t as e t ，w h i c hn e g l e c t st l l e i n t e 卜i n n u e n c e so fm u l t i d a t as e t s h o w e v e r t h er e a s o n sf o ra c c i d e n t f o m i n gb l a c k - s p o ta r en o ts i n g l e ，w m c hh a v el o t so fi n d 印e n d e n tb u t i m e r - i n n u e n c i n gf a c t o r s a st h et r a 佑ca c c i d e n t sa r em o r ea 1 1 dm o r es 甜o u s a n da c c i d e n tb l a c k - s p o ta r ei n c r e a s i n g ，u s i n gi n f o n n a t i o nc o o p e r a t i o nf o r r e a s o na n a l y z i n g ，w h i c hc 锄i n d i c a t em o r ec l e a l ro fr e a ls i t u a t i o ns e e m st o b em o r ea t l dm o r e i m p o r t a n t i 江苏大学硕士学位论文 o nt h eb a s i so f 如z z yc l u s t 甜n ga n a l y s i s ，t h i sp a p e rt a k e sb l a c k - s p o t o fa na c c i d e n ta se x a m p l ea n dr e s e a r c h e sd e 印l yt h e 印p l i c a t i o no f 血z z y c l u s t e 订n g t h a tb a s e do ni n f - o m a t i o nc o o p e r a t i o ni nt r a 伍c b l a c k - s p o t f o m i n g t h er e s e a r c hp e 雨m l a n c e sa r e 舔f o l l o w s ： 1 v a r i o u si n i t i a la l g o r i t h m so ff h z z yc l u s t e r i n ga r ea i l a l y z e da n d c o i n p a r e d ，a n dt h e na ni m p r o v e di n i t i a la l g o r i t h mi sp u tf o r w a r dt o o p t i m i z et h e 如z z yc l u s t e r i n gn u m b e ra n dt h ei n i t i a lc l u s t e r i n gc e n t e rb y c o m p u t i n gt h ea v e r a g ei n f o n n a t i o ne n t r o p ya n dc o m b i n i n gw i t hs u b t r a c t i v c c l u s t e r i n g 2 t h ei n f o n n a t i o nc o o p e r a t i v ec l u s t 丽n gm o d e lh a sb e e nc h o s e nt od o a n a l y s i sb e t w e e nd a t as e t sc o o p e r a t e l y ，a i li m p r o v e dc o o p e r a t i v e 内z z y c l u s t e r i n ga l g o r i t h mi sp u tf o r w a r dw i t hi m p r o v e m e n to nt h es e l e c t i o n m e t h o do ft h ei n i t i a lc e n t e ra n dc l u s t e r i n g v a l i d i t y 如n c t i o na i m i n ga t 印p l i c a t i o n s ，t h ee x p e r i m e n tr e s u l ti n d i c a t e st h a tt h ei m p r o v e dc o o p e r a t i v e 如z z yc l u s t e r i n ga l g o r i t h mp r e c e d et h eo r i g i n a la l g o r i t h mo ni t e r a t i v et i m e s a n dm u c hm o r ea p p r o a c h i n gt ot h ec l a s sc e n t 既 3 am e t h o do nt r a 所cb l a c k - s p o tc a u s eo ff o m a t i o na n a l y s i sb a s e do n c o o p e i a t i v e如z z yc m e a n sc l u s t e r i n gi sp r o p o s e d ，a n a l y z e da n dt h e n i e a l i z e d ，a ne x 觚1 p l ea n a l y z i n gi sm a d eu s i n gac e r t a i nc a s eo fat r a f e c b l a c k s p o t ， t h er e s u l ti n d i c a t e st h a tt h ec o o p e r a t i v ea n a l y z i n gm e t h o dc a n b eu s e dt oa s s i s t a n td e c i s i o n - m a k i n gi np r a c t i c e f i n a l l y ，t h ew o r ko ft h e 如l lt e x ta n dc r e a t i v i t ya r es u m m e du p ，a n dt h e e x p e c t a t i o nt o w a r d s 血t u r er e s e a r c hi sg i v e na tt h ee n d k e y w o r d s ：f u z z ) rc l u s t e r i n g ，t r a 衔cb l a c k s p o t ，t r a 衔cb l a c k - s p o t c a u s eo ff o n n a t i o n ，i n f o m a t i o nc o o p e r a t i o n ，i n f o m a t i o n g a i n ，t h ea v e r a g ei n f o n n a t i o ne n t o p y c o o p e r a t i v ef u z z y c m e a n s i v 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容以外，本论文不包含任何其他个 人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：克炙永筏 f l 期：缈苫年占月f 同 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ， 本学位论文属于 保密口， 在年解密后适用本授权书。 不保密门。 i 一 指导教师签名： 涉肖 b 鑫 小 聚 名 ， 别 伊 秘 m 作 月 刘 o 位 吞 铫 椰 江苏大学硕士学位论文 第l 章绪论 自1 8 8 9 年在美国发生世界第一起汽车交通事故以来，全世界因交通事故导致 的死亡数量达3 2 0 0 余力人，交通事故死亡人数占非自然死亡的l 4 左右，已成为 世界最大公害【l l 。近十年来，随着我国经济持续高速增长，人们的收入和生活水平 得到很大的提高，人们出行次数同趋增多，私家车数量大幅度增加，给人们的生 活和出行带来很大的方便。但是，在汽车保有量迅猛增长的同时，由此带来的交 通事故呈逐年增长的趋势。道路事故死亡人数、交通事故伤亡人数及经济损失居 高不下，交通安全状况严峻，引起国家和相关部门的重视。开展交通事故成因研 究，预测分析交通事故黑点具有重要性和紧迫性。 1 1 选题背景及课题意义 城市经济的发展，人口的增加，城市的机动车拥有量和交通量急剧增长，致 使城市交通阻塞，交通事故增加，严重影响了社会经济的发展和生命财产的安全。 从1 9 7 8 年到2 0 0 5 年这2 0 多年里，中国的民用汽车数量增长了十几倍，摩托车与 拖拉机的数量更是令人惊叹，机动车驾驶员的数量增加了3 0 多倍。近l o 年来， 机动车数量的平均增长率达到1 8 ，高于发达国家同时期的增长水平，机动车数 量的迅速增加，使本来就落后的交通基础设施不堪重负，交通事故数量持续增长。 中国是世界上交通事故最多的国家之一。交通事故调查的结果表明，尽管交通事 故是小概率的随机事件，人们很难对特定一起交通事故的发生进行精确的预测， 但交通事故在空间上的分布具有不均匀性。在一些特定的地点，交通事故经常发 生，这些地点发生交通事故的可能性显著地高于其它地点，被称为交通事故多发 地点或事故黑点。对中国南方城市2 0 0 0 年和2 0 0 6 年的交通事故情况进行调查的 结果表明，尽管全市7 5 个交通事故多发地点的道路里程只占道路总长度的3 2 ， 而在此发生交通事故的次数、死亡人数、受伤人数、直接经济损失等，却分别占 到总数的1 3 5 、3 7 o 、5 4 7 和3 1 4 。 交通事故是道路交通的三大公害之一，它不但直接威胁着道路使用者的人身 安全、造成巨大的经济损失，还严重地影响着道路交通系统的j 下常运行。 事故多发地点即事故黑点的研究对研究道路交通安全具有重大意义，其原因 在于【2 3 l ： ， 事故多发路段集中较大比例的交通事故，具有较大的危害性； 江苏大学硕士学位论文 事故多发路段发生的交通事故与道路线形、交通安全设施和交通环境等因 素有关，其中的相关性，是道路设计、管理部门所特别关心的； 对事故多发路段采取有针对性的改善措施能以较少的投入、大幅度地降低 整条道路的事故率，从而取得较大的经济和社会效益。因此，事故多发路 段的确定一直受到道路和交通管理部门的关注； 交通安全问题是一个世界性的问题，判断出事故多发路段，进行事故多发 路段的成因分析，并提出相应的整改措施，一直是国内外交通安全工作的 主要目标。国内外事故多发路段研究的差别主要体现在事故多发路段的鉴 别上。 中国交通事故率及严重程度长期居高不下，通过对有记载的交通事故成因的 分析可以发现，中国交通事故主要是由人( 占9 3 ) 、车( 占4 ) 两方面原因引 起的，而道路、交通、天气、管理等方面的原因仅占3 ，这与其它发达国家1 6 左右的比例相去甚远。究其原因，主要是事故处理过程中必须确定主要责任者， 所以人的原因所占比例之大就不足为奇了。事实上，一起交通事故的发生一般说 来都是偶然的，往往是由两个或者多个原因共同引起的，其中不乏道路、交通、 天气及管理方面的原因。因此，有必要对事故成因进行深入的分析，以期确定各 影响因素在交通事故产生过程中所起的真j 下作用。 目前对于交通事故成因的研究距离实际应用还有一段距离，在交通事故分布 规律、成因、预测与评价、预防与对策等方面存在着迫切需要研究和解决的理论 与实践问题，它们直接关系到事故率及其严重程度。交通事故多发地点即事故黑 点作为交通事故的高发点段，能否合理、有效地分析、解决，对交通事故的分析、 解决至关重要。本课题旨在利用模糊聚类算法，通过对交通事故分布，尤其是交 通事故黑点的分布及其成因进行深入研究，以期得出合理的事故预防对策，为降 低事故率及事故严重程度奠定理论和实践基础，对于改善道路交通安全状况具有 十分重要的理论意义和实际应用价值【4 l 。 1 2 研究现状与研究目的 1 2 1 国内外研究现状 1 交通事故黑点成因分析的研究 国内外关于交通事故影响因素的理论研究主要经历了三个阶段【5 】：最早出现也 是最简单的致因理论是单因素理论，这种理论把事故简单地归结为由一种原因引 江苏大学硕士学位论文 起，它较偏重于对人的分析；单因素理论逐渐发展成为多因素理论，该理论广泛 地用于各种事故的分析，认为在交通事故分析中，主要应从“人、车、路”三因 素着手；国外在2 0 世纪8 0 年代提出了系统致因理论，该理论以系统的观点对引 发事故的多种因素及其关系( 主要是逻辑关系) 进行研究。 单因素理论不能全面系统地揭示事故发生的规律，但当要寻找事故的主要原 因时，单因素理论的简单直观性非常有用；多因素理论的贡献主要在于使人们改 变了对交通事故成因的单向性、局部性思维，开始从社会整体的角度来考虑交通 安全问题，然而多因素理论的不足在于对因素之间的关系及互相影响考虑不够， 没有对因素之间的逻辑关系进行深入分析；系统致因理论的重大贡献在于它首次 把数学引进事故研究之中，从而将致因理论建立在定量研究的基础上。但就我国 实际情况而言，事故数据往往只记录一种原因( 有时该原因甚至不是主要原因) ，因 此系统致因理论及多因素理论目前在全国范围内还不能进行实际应用。部分省份 已经开始改进交通事故数据的记录方式，以期为单因素理论以外的理论提供基础 数据，取得更准确的统计分析结果。 但目前的情况是，一方面，许多己经建立起来的交通监控系统所采集的数据 不被重视；另一方面，许多人一提到解决交通问题，马上想到使用人工进行交通 数据抽样调查，这种方法不仅增加了成本，而且调查的数据偶然性大、可靠性差、 应变性差，并且一些隐藏在其中的规律和交通特点不能被发现。怎么样利用现有 的由监控系统采集的交通数据进行分析，从众多的数据中找到一些交通流的特点， 针对这些特点制定有效的控制策略，做到有的放矢，而且这些方法应当是实时的， 即当交通流特点发生变化时，能够及时发现以便及时改变控制策略成为目前研究 的热点和难点。 2 模糊聚类分析的研究 自从z a d e h 在1 9 6 5 年提出模糊集理论，模糊集理论在实际中率先应用于模式 识别领域【6 】。由于模式识别中固有的模糊性，将模糊集引入模式识别获得了巨大的 成功。以模糊集为基础处理聚类问题是由b e l l m 觚，l 铆a b a 和z a d e h 于1 9 6 6 年首 先提出的。第一个系统地表述和研究模糊聚类的人是著名学者i 沁p i n i 【1 1 】【1 4 】。1 9 6 9 年，l h s p i n j 定义了数据集的模糊划分概念。与此同时，z a d c h ，t a m u 均等人提出 了基于相似关系和模糊关系的聚类方法，这类方法分为聚集法和分裂法，目前已 提出了许多不同技巧来应用这一思想。从七十年代到八十年代，人们对模糊矩阵 及其传递闭包等问题进行了大量的研究。到九十年代，尽管还有人做这方面的研 江苏大学硕士学位论文 究。人们也试图用图论的方法研究模糊聚类，如1 9 7 4 年d u 仰利用图论分析t a m 啪 等人提出的聚类方法，1 9 9 2 年丁斌提出的动态模糊图最大树聚类方法，1 9 9 3 年， z l l e n g g uw h 和rl e a l l y 提出最优图论方式的聚类方法【9 】。在将硬聚类方法推广到 模糊聚类情形方面，人们也作了许多工作，如将硬聚类中常用的k 最近邻方法推 广到模糊聚类。1 9 8 5 年t a o ( u 和b u b u i s s o n 提出松弛型k 最近邻法，同年硒l l e r 等人提出了一种模糊k 最近邻法，1 9 9 1 年b e r e a u 和b u b u i s s o n 提出了另一种形式 的模糊k 最近邻： ：去【1 2 】f i3 1 。人们也提出了其它一些模糊聚类方法，如1 9 8 5 年e s o g b u e 提出动力学模糊聚类方法，1 9 8 8 年m a i l t 龃够v a l v e r d e 基于难以辨别关系提出了几 种模糊聚类方法【7 】。 1 2 2 研究目的 在交通事故黑点成因分析中，一些成因( 尤其是道路、环境等非人为因素) 对交 通事故的影响具有一定的模糊性，采用经典数学模型来确定事故黑点成因，很难 得到准确合理的分析结果。因此如何对众多的事故影响成因进行合理的空间划分、 影响程度等级归类，找出一定路段上导致事故多发的主要因素、诱导因素以及潜 在的事故隐患，以便采取相应的事故治理和防范措施；如何对成因分析结果的合 理性和准确性进行评价是交通安全工作者面临的关键问题。本论文的研究目的是 利用聚类分析的方法，对现有交通事故黑点成因数据进行系统的分析，构建合适 的事故成因分析体系和方法，为交通安全管理提供了科学的决策依据，确保道路 交通系统的安全功能得到充分的发挥。 1 3 本文的主要工作 在交通事故黑点成因分析中的一些成因对交通事故的影响具有一定的模糊 性，以往采用的经典数学模型很难得到准确的分析结果，针对这一情况，改进了 基于信息合作的模糊聚类算法，对模糊聚类初始化以及有效性检验也做了一定的 研究。 本文的主要工作如下： 1 对比分析了聚类分析中各种初始化方法，提出新的基于平均信息熵和减法 聚类的聚类初始化方法，并采用i r i s 数据集进行性能检验。 2 采用合作模糊聚类算法分析数据集之间的合作影响，提出i c f c m 算法， 该算法针对c c a 算法在中心点初始化上进行改进，并结合聚类有效性检验，采用 人工数据集和b o s t o nh o u s i n g 数据集对两者进行比较。 江苏大学硕士学位论文 3 结合改进的l c f c m 算法，提出一种新的交通事故黑点成因分析方法，对 交通事故黑点成因进行聚类分析，发现其中的主要因素和次要因素，以便于交通 管理部门进行预防和治理。 1 4 论文的结构安排 论文共分六章，组织结构如下： 第l 章绪论 阐述了课题的研究背景和研究意义，分析了交通事故黑点成因分析的国内外 研究现状、及其所表现出的不足和发展趋势，给出了本文的研究目的，最后概述 本文的主要研究工作。 第2 章关键概念和理论介绍 首先对聚类分析的相关概念进行了介绍，包括聚类的分类等，随后介绍了对 交通事故黑点的相关理论及研究方法。 第3 章模糊聚类算法初始化的研究 详细介绍了模糊聚类的相关知识，随后深入探讨了模糊聚类初始化的方法， 进一步提出了基于平均信息熵和减法聚类的模糊聚类初始化方法，并给出实验分 析。 第4 章基于信息合作的模糊聚类算法研究 探讨了基于信息增益的合作模糊聚类c c a 算法，针对c c a 算法存在的不足 提出了c c a 的改进算法i c f c m 算法，随后以人工数据集和b o 咖nh o u s i n g 数据集 作为实验对象对c c a 算法和i c f c m 算法进行对比分析，并给出实验分析结果。 第5 章i c f c m 算法在b s c a 中的应用 以某事故黑点为例，结合第四章提出的i c f c m 算法对交通事故黑点成因进行 聚类分析，并对分析结果进行详细解释。 第6 章结束语 对全文进行总结，对今后的工作进行了展望。 江苏大学硕士学位论文 第2 章关键概念和理论介绍 2 1聚类分析的基本方法 “物以类聚，人以群分”，聚类是一个古老的问题，它伴随着人类社会的产生 和发展而不断深化，人类要认识世界必须区别不同的事物并认识事物间的相似性。 将物类或者抽象对象的集合分组成为由类似对象组成的多个类的过程被称为聚类 ( c l u s t 甜n g ) 。聚类按照一定的要求和规律对事物进行区分和分类，在这一过程中 没有任何关于分类的先验知识，没有教师指导，仅靠事物问的相似性作为类属划 分的准则，因此属于无监督分类的范畴。聚类分析能够从研究对象的特征数据中 发掘出信息和规则，因而是一种强有力的信息处理方法，在图像分割i 模式识别、 计算机视觉、数据挖掘、特征提取和信号压缩中都有广泛的应用。 2 1 1 聚类分析概述 聚类就是将数据对象分组成为多个类或簇，使得在同一个簇中的对象之间具 有较高的相似度，而不同簇中的对象差别较大。在机器学习领域，聚类是一种无 指导的学习。在聚类过程中，类群不是预先指定，而是在事先不知道到底有多少 类的情况下，以某种度量为标准( 是由聚类分析工具及其算法决定的) ，将具有相似 特征的数据对象划分为一类，同时分离具有不同特征的数据对象，是在分析过程 中得到的。聚类是直接对数据集进行处理，要考察所有的个体，根据这些个体的 特征才能决定类的划分，并由算法自动确定。这是一个动态的过程。它能够随着 数据集的变化而变化。对于一个特定的数据点，当数据集中的其他点发生变化或 增减时，它所属的类别也可能发生变化。聚类分析主要有两个方面的作用：一是 作为数据分类的预处理步骤，另一个作用就是作为一个独立的分析工具，用于了 解数据的分布。 2 1 2 聚类算法的要求 采用基于聚类分析方法的数据挖掘在实践中已取得了较好的效果，在实际操 作中往往不是采用单一的手段，而是采用多种手段和方法相结合。根据潜在的各 项应用，数据挖掘对聚类的典型要求有以下几方面： 江苏大学硕士学位论文 可伸缩性：即不论对于小数据集还是对于大数据集，算法都应是有效的。在 很多聚类算法当中，数据对象小于2 0 0 个的小数据集合上鲁棒性很好，而对于包 含成千上万个数据对象的大规模数据库进行聚类时，将会导致结果有不同的偏差。 处理不同类型属性的能力：即既可处理数值型数据，又可处理非数值型数据 的，既可以处理离散数据，又可以处理连续域内的数据，如分类标称类型 ( c a t e g o r i c a 妇o m i n a l ) ，序数型( o r d i n a l ) ，二元类型( b i n a r ”，或者这些数据类型的混 合。 能够发现任意形状的聚类：我们经常使用欧几罩德距离或者曼哈坦距离的许 多聚类算法来确定聚类，但基于这样的距离度量的算法趋向于发现具有相近密度 和尺寸的球状簇。但对于一个簇可能是任意形状的情况，提出能发现任意形状簇 的算法是很重要的。 用于决定输入参数的领域知识最小化：在聚类分析当中，许多聚类算法要求 用户输入一定的参数，如希望簇的数目。聚类结果对于输入参数很敏感，通常参 数较难确定，尤其是对于含有高维对象的数据集更是如此。要求用人工输入参数 不但加重了用户的负担，也使得聚类质量难以控制。 处理噪声数据的能力：绝大多数现实世界中的数据库都包含了孤立点、空缺、 未知数据或有错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量 的聚类结果。 对于输入记录顺序不敏感：一些聚类算法对于输入数据的顺序是敏感的。例 如对于同一个数据集合，以不同的顺序提交给同一个算法时，可能产生差别很大 的聚类结果。研究和开发对数据输入顺序不敏感的算法具有重要的意义。 高维性：既可处理属性较少的数据，又能处理属性较多的数据。很多聚类算 法擅长处理低维数据，一般只涉及两到三维，通常最多四维到五维的情况下能够 很好地判断聚类的质量。聚类数据对象在高位空间是非常具有挑战性的，尤其是 考虑到这样的数据可能高度偏斜并且非常稀疏。 基于约束的聚类：在实际应用当中可能需要在各种约束条件下进行聚类。既 要找到满足特定的约束，又要具有良好聚类特性的数据分组是一项具有挑战性的 任务。 可解释性和可用性：用户期望聚类得到的信息是可理解和可用的，但是在实 际挖掘中有时往往不能令人满意。 江苏大学硕士学位论文 2 1 3 聚类分析的数据结构和相似度的度量 数据结构与数据类型是两个不同的概念。数据类型是一组值的集合和定义在 这个值的集合之上的一组操作的总称。例如整数类型( i n t ) 这个数据类型，主要运算 有加、减、乘、除、取模运算等。而数据结构常指存储在计算机内存中的数据， 与其文件结构对应。文件结构是指外存储器( 如磁盘驱动器、磁带) 中的组织。 1 聚类分析的数据结构 许多基于内存的聚类算法选择如下两种有代表性的数据结构： ( 1 ) 数据矩阵( d a t am “x ，或称为对象与变量结构) 用p 个变量( 也称为度量或属性) 来表现n 个对象，这种数据结构是关系表 的形式，即看成忍p ( n 个对象p 个变量) 的矩阵： 一i - 五i l x ：h l ： x 、f 黾p x 2 f x 2 p x p ix 谚x 叩 ( 2 ) 相异度矩阵( d i s s i m i l 耐妙m a t r i x ，或称为对象对象结构) ：存储n 个对象两 两之日j 的近似性，表现形式是一个刀，l 维的矩阵。 d = o 嘎2 1 ) o 吐)反柑) o 这里t u ) 是对象i 和对象j 之问相异性的量化表示。对象间的相异度一般是基 于对象问的距离来计算的。设f ( 葺。，：，) 和= ( 。，：，勃) 是两个p 维的数据对象，通常珥是一个非负的数值，当对象i 和j 越相似或“接近”其值 越接近o ，且西川- o ，即一个对象与它本身的相异度为0 ：两个对象越不同，其值 越大。显然，位于矩阵对角线上的元素研中的i - j ，也就是度量一个对象与它本 身的相异度，因此对角线上值均为o 。数据矩阵也被称为二模矩阵，而相异度矩阵 被称为单模矩阵。 2 聚类分析的相似度度量 聚类时要根据对象之间的相似度，把相似的对象放入同一个聚类中，而不相 似的对象归入不同的聚类。所以，相似度的度量，直接决定着聚类的结果，对于 数值型数据和枚举型数据，度量的方法也不相同。 江苏大学硕士学位论文 对于数值型的属性，有两种相似性度量方法：距离相似度和角度相似度。距离 相似度主要有以下四种： 绝对值距离： 欧式距离： 明氏距离： 切比雪夫距离： 毛( 1 ) 2 喜l 靠一瓢i 们) = * 一瓢) 2 r i 量= ii 拍) = 黔一靠) 9 名 略( ) = 燃i 靠一靠l ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) 注：( 2 1 ) 式和( 2 2 ) 式两种度量方法都满足对距离函数的如下数学要求： ( 1 ) 嘎u ) o ：距离是一个非负的数值； ( 2 ) 噍“) = o ：一个对象与自身的距离是o ； ( 3 ) 反u ) = 吱，距离函数具有对称性； ( 4 ) 噍) 吐 ) + 嘎) ：从对象j 的直接距离不会大于途经任何其他对象h 的距 离( 三角不等式) 。 对于枚举型数据，可以用相同属性值的数目作为相似性度量，也可以用相同 属性值的数目与不同属性值数目的比值作为相似性度量。 2 1 4 聚类分类 1 基于划分的方法 划分聚类算法把数据点集分为k 个划分，每个划分作为一个聚类。通常给定 一个n 个对象或元组的数据库，一个划分方法构建数据库的k 个划分，每个划分 表示一个聚簇，并且j | 刀。也就是说它将数据划分为k 个组，同时满足如下的要 求：第一，每个组至少包含一个对象；第二，每个对象必须属于且只属于一个组。 一般人为给定构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一 种迭代的重定位技术，使某个准则函数最优化，而每个聚类由其质心来代表 ( 1 【m e a 鹏算法) ，或者由该聚类中最靠近中心的一个对象来代表( k m e d o i d s 算法) ， 尝试通过对象在划分间不断移动来改进划分。一个好的划分的一般准则是：在同 一个类中对象之间尽可能的接近或相关，而不同类中的对象之间尽可能的远离或 不同。当然还有许多其他划分质量的评判准则。 江苏大学硕士学位论文 实际上绝大多数应用采用了以下比较流行的启发式算法： k 均值算法，在该算法中每个簇用该簇中对象的平均值来表示。 k 中心点算法，在该算法中每个簇用接近聚类中心的一个对象来表示。 算法优点： ( 1 ) 计算速度快，计算方式简洁，能够灵活适应复杂多变的需求。 ( 2 ) 当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好。 ( 3 ) 对处理大数据集，该算法是相对可伸缩的和高效率的。 算法缺点： ( 1 ) 有些算法仅适用于连续数值属性而不适用于分类属性。 ( 2 ) 对先验知识要求较高，需要用户输入目标聚类的数目。 ( 3 ) 只能发现凹面形状的簇，而对于不规则形状的簇则难以发现。 ( 4 ) 有些算法只能发现形状差别较小的簇，而当目标簇的形状差别较大时，会 忽略形状较小的簇。 ( 5 ) 对于噪声和孤立点的存在较为敏感。 划分聚类算法收敛速度快，缺点在于它倾向于识别凸形分布大小相近密度的 聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k 可以合理地估计， 并且初始中心的选择和噪声会对聚类结果产生很大影响。主要的划分聚类算法有 k - m 啪s ，e m ，k - m e d o i d s ，c i ，a ra ，c l a r a n s 等。 图3 1 划分方法实现的过程l 鳘i 2 基于密度的方法 很多算法中都使用距离来描述数据之间的相似性，但是，对于非凸数据集， 只用距离来描述是不够的。对于这种情况，要用密度来取代相似性，这就是基于 密度的聚类算法。基于密度的算法从数据对象的分布密度出发，把密度足够大的 区域连接起来，从而可以发现任意形状的类。此类算法除了可以发现任意形状的 类，还能够有效去除噪声。 3 基于分层的方法 江苏大学硕士学位论文 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成， 层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，一 开始将每个对象作为单独的一个组，然后把离得近的对象合并到一起，直到所有 的组合合并为一个( 层次的最上层) ，或者到达一个终止条件。分裂的方法，也称为 自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中，一个 簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止 条件。 层次的方法缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤销。这 个严格规定是有用的，从而不用担心组合数目的不同选择，算法代价会比较小。 但是，该技术的_ 个主要问题是它不能更f 错误的决定。有两种方法可以改进层 次聚类的结果：( i ) 在每层划分中，仔细分析对象间的“联接 ，。例如c 切姐和 c h 锄e l e o n 中的做法。( i i ) 综合层次凝聚和迭代的重定位方法。首先用自底向上的层 次算法，然后用迭代的重定位来改进结果。例如在b i r c h 中的方法。 典型的层次聚类算法有b i r c h ，c u r e ，r o c k 等聚类算法。 4 基于网格的方法 基于网格的方法( 鲥d b a s e dm 础o d ) ，把对象空间量化为有限个单元( 即长方体 或超长方体) ，形成了一个网格结构。所有的聚类操作都在这个网格结构( 即量化的 空间) 上进行。这种方法的主要优点就是它的处理速度很快，其处理时间独立于数 据对象的数目，只与量化空间中每一维的单元数目有关。 t i n g ( s t a t i s t i c a li i l f 0 册a t i o n 嘶d ) 是一种基于网格的多分辨率聚类技术，它将 空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级的矩形单元， 这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关 于每个网格单元属性的统计信息( 例如平均值、最大值和最小值) 被预先计算和存 储。统计参数的使用可以按照以下自顶向下的基于网格的方法。 w a v e c l u s t e r 是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个 多维网格结构来汇总数据，然后采用小波变换来变换元特征空间，在变换后的空 间中找到密集区域。 5 基于模型的方法 基于模型的方法试图优化给定的数据和某些数学模型之间的适应性。这样的 方法经常是基于这样的假设：数据是根据潜在的概率分布生成的。基于模型的方 法主要有两类：统计学方法和神经网络方法。 江苏大学硕士学位论文 概念聚类是一种统计学方法，机器学习中的一种，给出一组未标记的对象， 它产生对象的一个分类模式。与传统的聚类不同，概念聚类除了确定相似对象的 分组外，还向前走了一步，为每组对象发现了特征描述，即每组对象代表了一个 概念或类。因此，概念聚类是一个两步的过程：首先进行聚类，然后给出特征描 述。概念聚类的绝大多数方法采用了统计学的途径，在决定概念或聚类时使用概 率度量。 神经网络方法将每个类描述为一个标本，标本作为聚类的原型，不一定对应 一个特定的数据实例或对象。根据某些距离度量，新的对象可以被分配给标本与 其最相似的类，被分配给一个类的对象的属性可以根据该类的标本的属性来预测。 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。 一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。 它也基于标准的统计数字自动决定聚类数目，考虑“噪声 数据或孤立点，从而 产生健壮的聚类方法。 2 1 5 聚类准则的确定 有了相似性测量函数，下一步要确定的是采用的聚类准则。聚类准则是聚类 分析算法的关键，通常有两种确定方式。 试探方式：此方法是凭主观和经验，针对实际问题定义一种相似性测度的阈 值，然后按最近邻规则指定某些对象属于某一聚类。例如使用欧氏距离，它反映 的是对象之间的近邻性，在将一个对象分到两个类别中的一个时，必须规定一距 离测度的阈值作为聚类的判别准则。 基于距离的目标函数：由于聚类是将对象进行组合分类以使类别可分离性最 大，因此聚类准则应是反映类别问相似性或相异性的函数。但类是由一个个对象 所组成，所以一般说来，类别的可分离性与对象的相异性直接有关。 2 2 交通事故黑点的研究 交通事故在道路空间上的分布有分散型和密集型两种。分散型分布的事故多 与驾驶员及其他用路者的不安全行为有关；密集型的事故则多与道路类型、交通 设施和交通环境有关；如急弯陡坡、视距不良、交通量过大等路段m 】。事故密集 型分布的路段，通常称为事故多发点或事故多发路段。在这些路段上，单位时间 内每公里