（计算机应用技术专业论文）gis系统中基于网格密度的空间聚类算法的研究与应用.pdf

大连理工大学硕士学位论文 摘要 空间数据挖掘或空间知识发现是指从包含空间信息的数据库中抽取隐含的知识、 空间关系或非显式存储在数据库中有意义的特征或模式。此技术在理解空间数据、获 取空间与非空间数据的内在关系上具有重要意义。随着以g i s ( 地理信息系统) 为代 表的空问信息系统的快速发展，空间信息大量产生，空间数据挖掘已成为当前亟待研 究的重要课题。 聚类是数据挖掘领域中的一个主要问题，聚类操作主要指在将一组样本划分为若 干簇，使得簇内样本具有较大的相似性，而簇间样本具有较小的相似性。空间聚类是 在空间信息上的聚类，它继承了一般聚类的基本特征，研究对分布在空间中的对象实 施聚类，从而发现空间集簇的过程。本文首先研究了以g i s 为代表的空间信息系统中 所存储的空间对象的分布特征，介绍了地理空间对象分布的二重性，研究了基于坐标 的二维空间聚类的主要内容和特点，最后总结了应用于g i s 系统的空间聚类方法的主 要任务和所应具有的特点。 随后，本文研究了目前已有的各类主要聚类算法，分析其特点，并着重研究了基 于网格密度的聚类方法及其在基于坐标的二维空间聚类上的应用。进一步的，分析了 该方法的特点和不足，在保留原方法的功能( 即发现二维空间中高密度网格的最大密 集连通区域作为聚类集簇) 不变的前提下改进原方法，使其可以同时发现最大密集连 通区域中以密集中心为代表的若干子区域，并且构造两种不同类型区域的二层结构。 进一步的设计了一种推荐参数的方法，可以在用户不主动设定参数的情况下，自动产 生一组可以获得较优结果的参数值。 在处理二维空间障碍上，本文介绍并研究了目前已有的处理空间障碍的主要方 法，并通过提出特有的障碍抽象方法将二维空间障碍引入网格密度方法，使得改进算 法可以处理二维空间障碍。 最后，本文完成了改进方法及两类其它聚类方法与g i s 系统的集成，介绍了智能 化g i s 系统的组成结构及空间聚类方法在其中的应用，并演示了应用效果。 关键词：空间数据挖掘；空间聚类：网格密度；障碍约束；智能化g i s g i s 系统中基于网格密度的空间聚类算法的研究与廊刖 r e s e a r c ha n d a p p l i c a t i o na b o u t g r i d d e n s i t y b a s e d c l u s t e r i n g m e t h o d si ng i s a b s t r a c t s p a t i a l d a t a m i n i n g o r s p a t i a lk n o w l e d g ed i s c o v e r i n g r e f e r st o p i c k i n gu p c o n n o t a t i v ek n o w l e d g e ，r u l e so rs i g n i f i c a t i v em o d e sf r o m s p a t i a ld a t a b a s e t h i st e c h n o l o g y h a s g r e a ts i g n i f i c a n c e i n u n d e r s t a n d i n gs p a t i a l d a t aa n d p i c k i n gu pr e l a t i o n sb e t w e e n s p a t i a l d a t aa n dn o n s p a t i a l d a t a a l o n gw i t ht h ed e v e l o p m e n to fs p a t i a li n f o r m a t i o n s y s t e mi nw h i c hg i s ( g e o g r a p h yi n f o r m a t i o ns y s t e m ) i s a ni m p o r t a n t e x a m p l e am a s so f s p a t i a ld a t ai sa c c u m u l a t e d ，s os p a t i a ld a t am i n i n gh a sb e c o m eac r u c i a ls u b j e c t c l u s t e r i n gi sa ni m p o r t a n tp r o b l e m i nt h ef i e l do fd a t am i n i n g c l u s t e r i n gi sat a s kt o d i v i d es a m p l e si n t os o m eg r o u p ss os a m p l e so fs a m eg r o u pa r em o r es i m i l a ra n dt h o s eo f d i f f e r e n tg r o u p sa r el e s s s i m i l a r s p a t i a lc l u s t e r i n g i st of i n dc l u s t e r si n s p a t i a ld a t a ，i t i n h e r i t st h ec h a r a c t e r so fg e n e r a lc l u s t e r i n gw h i c hf o c u so nt h ep r o c e s st of i n dg r o u p so f s p a c ed i s t r i b u t e ds a m p l e s t h i sa r t i c l ef i r s t l yr e s e a r c ho nt h ec h a r a c t e r so f d i s t r i b u t i o no f s p a t i a ls a m p l e s ，i n t r o d u c e s t h ed u a l i s mo fd i s t r i b u t i o ni n g e o g r a p h ys p a c e a n dt h e c h a r a c t e r so fc o o r d i n a t e b a s e ds p a t i a lc l u s t e r i n gi n2 ds p a c e as u m m a r yo fs p a t i a l c l u s t e r i n gi ng i s i sg i v eo u ti nt h ee n d s e c o n d l y ，t h i sa r t i c l er e s e a r c h e so n t h ee x i s t i n gc l u s t e r i n gm e t h o d s ，e s p e c i a l l yo nt h e g r i dd e n s i t y b a s e dm e t h o d s ，b o t ha d v a n t a g e sa n dd i s a d v a n t a g e sa r ei n t r o d u c e d h e na n e w a p p r o a c hi sp r e s e n t e d ，w h i c hi sd e v e l o p e d f r o mt r a d i t i o n a lg r i dd e n s i t y b a s e dm e t h o d s n e wm e t h o d sc a ne x a c t l ya n de f f i c i e n t l yd i v i d et h eo b j e c t si ng e o g r a p h ys p a c ei n t os o m e d e n s i t y - b a s e dr e g i o n sa n dd i v i d ee a c ho f t h e s er e g i o n si n t os o m es u b r e g i o n sa tt h es a m e t i m ew b i c ha r ea p p r o x i m a t et oc i r c l ea n dh a v eac e n t e rr e l a t i o nb e t w e e nt w ok i n d so f r e g i o n sa r ep r e s e n t e da sa t w o - l e v e lf r a m eam e t h o do fp a r a m e t e r sc o m m e n d i n gi sa l s o i n t r o d u c e df o rt h ec o n d i t i o n sw h e nt h e r e sn ou s e r sp a r a m e t e r s t od e a lw i t ht h es p a t i a lo b s t a c l e s ，t h i sa r t i c l ei n t r o d u c e ss o m ee x i s t i n gm e a n sa n d g i v e so u tam e a n s f o rg r i dd e n s i t y b a s e dm e t h o d sb yas p e c i a lw a yt ot u r nt h eo b s t a c l e s i n t oa b s t r a c tf o r m s f i n a l l y ，t h en e w m e t h o d sa n dt w oo t h e rm e t h o d sw e r ei n t e g r a t e di n t ot h eg i sa n dt h e w h o l e c o n f i g u r a t i o no f i n t e l l i g e n tg i ss y s t e mi si n t r o d u c e d k e yw o r d s ：s p a t i a ld a t am i n i n g ；s p a t i a lc l u s t e r i n g ；g r i d d e n s i t y ；o b s t a c l e s ； i n t e l l i g e n tg i s 【 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：遵 火连理t 大学硕士学位论文 引言 近十几年来，随着人们利用信息技术生产和搜集数据的能力大幅度提高，千千万 万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，人们面临着被数 据淹没却饥饿于知识的挑战，其中以g i s 为代表的空间数据系统以其数据量大、数据 类型繁多、结构复杂等特点在诸多信息系统中凸现出来，在此背景下空间数据挖掘技 术应运而生并得以蓬勃发展，越来越显示出其强大的生命力。 空间数据挖掘( s p a t i a ld a t am i n i n g ，s d m ) i 指的是从空间数据库中抽取隐含的知 识、空间关系或非显式地存储在空间数据库中的其它模式。它可以用来理解或重组空 间数据、发现空间和非空间数据间的关系、构建空间知识库、优化查询等。空间聚类 2 】是数据挖掘中一种重要的挖掘方法，它将数据对象集分组成为由类似的对象组成 的簇，这样在同一簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。作 为一种非监督学习方法，空间聚类不依赖于预先定义的类和带类标号的训练实例。其 中基于坐标的空间聚类 2 】是空间聚类方法的基础，它可以发现空间中对象的密集区 域，例如居住类型的空间区域分布、商业区域分布等。空间聚类方法通常可以分为四 大类：划分法、层次法、基于密度的方法和基于网格的方法。算法的选择取决于应用 目的，例如商业区位分析要求距离总和最小，通常用k 均值法或k 中心点法；而对于 区域分析和图像识别，基于密度的算法更合适。此外，算法的速度、聚类质量以及数 据的特征，包括数据的维数、噪声的数量等因素都影响到算法的选择。但是由于目前 的聚类算法多为普适方法，在针对性的处理较为复杂的某一类型实际问题时，如g i s 中的空间聚类问题【3 】，就存在着一些不足。 在此背景下，本文将研究目前已有的各类主要聚类算法【4 】，并着重研究基于网 格密度的聚类方法【5 】及其在二维空间聚类上的应用，以及地理空间对象分布的特点。 以c l i q u e 算法为代表的基于网格密度的方法是一类较新的聚类分析方法。它以其 优异的性能成为目前受到较多关注的聚类分析方法之一。基于网格密度的聚类分析方 法具有速度快、善于处理噪声、善于处理高维数据等特点，这些特点使其成为一种较 适用于g i s 系统的聚类方法。但是在面对g i s 系统中的聚类分析时，目前的基于网 格密度的方法仍存在一些不足，其中包括了不能够处理空间分布的层次性、不能够处 理空间障碍等问题。本文将尝试通过对传统方法的改进以及引入对空间障碍的处理方 法等手段来增强基于网格密度的聚类方法的功能，使其成为一种适用于g i s 系统的空 间聚类分析方法，并将其作为种实用方法集成到g i s 系统当中去。 l 数据挖掘中的聚类分析 1 1 聚类分析的概念 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚 类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼 此相似，与其它簇中的对象相异。在许多应用中，可以将一个簇中的数据对象作为 个整体来对待。 聚类分析是一种重要的人类行为，人们在生活中会通过不断改进下意识中的聚类 模式来分辨不同类别的对象。聚类分析已经广泛地应用在许多领域，包括摸式识别、 数据分析、图像处理以及市场研究等等。通过聚类，人能够识另【膝集的和稀疏的区域， 因而发现全局的分布模式，以及数据问的相互关系。聚类的典型应用是多种多样的。 在商务上，聚类可以发现和刻画不同的客户群。在生物学上，可以对种群进行分类， 发现其固有特征。在地球地理观测数据中可以发现不同类型的密集区域。聚类还可以 用于对w e b 上的文档进行分类等等。作为数据挖掘的一部份，聚类分析能作为一个 独立的工具来获得数据分布的情况，观察每个簇的特点，还可以作为其它算法( 如特 征和分类等) 的预处理步骤。 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各种特殊要求。数据挖 掘对聚类的典型要求如下【6 】：1 可伸缩性2 处理不同类型漏性的能力3 发现任意 形状的集簇4 输入参数所需的领域知识最小化5 处理噪声的能力6 对对象输入 顺序不敏感7 高维性8 基于约束的聚类9 可解释性和可用性。 数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘、统计学、机器学习、 空间数据库技术、生物学以及市场营销等等。由于各领域数据库中已经收集了大量的 数据，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。 1 2 数据挖掘中的聚类分析算法 1 2 1 划分聚类算法 划分聚类也叫分割聚类，给定一个n 个对象或元组的数据库，一个分割方法构建 数据的k 个划分，每个划分表示一个聚类。并且k d e n s l i m f f & & g r i d s l i s t i l j r e g i o n l d - - 0 ) f o u n d n e w d e n s g r i d - - t x u e ； s e tg r i d s l i s t i j r e g i o n i d 2 r e g i o n l d ； r e g i o l l i d + + ： t r e a taq u e u ea n da d dg r i d s l i s t i 】【j i n t ot h eq u e u e ； w h i l e ( q u e u e i sn o t e m p t y ) p o pt o pg r i do f t h eq u e u e f o r ( a l ln e i g h b o u rg r i d so f t h et o pg i i d ) i f ( n e i g h o b u r g r i d d e n s i t y d e n s l i m i t & & n e i g h o b u r g r i d r e g i o n l d = 0 ) s e tn e i g h o b u r g r i d r e g i o n l d = t o p c r r i d r e g i o n i d ； a d d n e i g h o b u r g f i d t ot h eq u e u e ； e n d 算法的复杂性分析 设样本规模为n ，网格数为m ，密集网格数为m 。显然有m d e n s l i m i t & & g i r d ( i ) d e n s t i y a l ln e i g h b o r g r i d s d e n s i t y ) p e a k c o u n t + + ； s e tg r i d ( i ) s u b r e g i o n i d ：p e e k g r i d c o u n t ； r e l a t i o n t a b l ea d d p e a k c o u n t 【p e a k c o u n t ； c r e a taq u e u ea n da d d 卵a ( i ) i n t ot h eq u e u e ； w h i l e ( n o t a l l q u e u e e m p t y ) s e tn o t a l l q u e u e e m p t y = f a l s e ； f o ra l lq u e u e s i f ( q u e u ei sn o te m p 奶 s e tn o t a l l q u e u e e m p t y2t r u e ； f o ra l ln e i g h b o r g r i d so f t h et o p g r i d i f ( n e i g h b o r g r i d ，d e n s i t y d e n s l i m i t ) i f ( n e i g h b o r g r i d s u b r e g i o n l d = o ) s e tn e i g h b o r g r i d s u b r e g i o n l d ；t o p g r i d s u b r e g i o n i d ； a d dn e i g h b o r g r i di n t oq u e u e ； i f ( n e i g h b o r g r i d s u b r e g i o n l d ! 。0 & & n e i g h b o r g r i d sm a l n r e g i o n l d ! - - - t o p g r i d sm a l n r e g i o n l d ) f o ra l li t e mi nr e l a t i o n t a b l e i f ( i t e m m a l n r e g i o n l d = n e i g h b o r g r i d sm a l n r e g i o n i d ) s e ti t e m m a l n r e g i o n l d = t o p g r i d sm a i n r e g i o n l d ； d e l e t et o p g d df r o mt h eq u e u e ； 2 l g i s 系统中基于网格密度的空间聚类算法的研究与应用 r e n a m emd i f f e r e n tm a i n r e g i o n i d si nr e l a t i o n t a b l ea s1t om ； e n d 图3 4 c p d g 的类结构 f i g 3 4c l a s ss t r u e t u r eo fc p d g 3 3 2 参数的设定 参数最小化分析 输入参数是聚类算法的一个重要的组成部分，不同的聚类方法要求用户输入不同 的和聚类操作相关的参数，这些参数的值往往直接影晌到聚类的结果。如基于划分的 方法一般要求聚类数目作为输入参数，而基于密度的方法要求单位空间的密度阈值或 对象洲的最小距离作为输入参数，而基于网格的方法要求网格步长作为输入参数等 等。 聚类方法作为一种无指导的数据挖掘方法，主要目的在于自发的在对象集合中发 现集簇或者称为模式。由于其特点是无指导和自发的，所以一般来说，输入参数的最 小化是评价一个好的聚类算法的要求之一。在分析c p d g 算法的参数设定之前，首 先分析一下聚类算法中的输入参数对算法的影响，及参数最小化的确切含义。 算法的输入参数一般来讲是由用户来确定的。是用户和算法沟通的媒介。用户借 由输入参数对算法的过程及结果形成的影响可以分为两类：主动的和被动的。所谓主 动的影响是指在这种情况下输入参数反映了用户对算法的主观要求，并比较了解其所 输入参数对算法结果的影响方式和程度，在这种情况下。不同的输入参数反映了不同 的要求，所以虽然结果不同，但是不同结果间的关系主要是意义韵不同，而不是好与 坏的关系。例如。在传统网格密度方法中，网格步长和密度闽值作为输入参数，对算 法的影响就是以主动为主的。它们主要反映了用户对于聚类粒度的要求和对密集性的 定义。较大的步长反映了用户对聚类结果的要求比较粗糙，而较小的步长反映了用户 对聚类结果的要求比较细致。而较大的密度阈值表示用户对密集区域的密度要求较 大连理工大学硕士学位论文 高，而较小的密度阂值表示用户对密集区域的密度要求较低。 而在划分方法中，聚类数目作为输入参数在很多情况下体现了一种被动的影响。 用户在聚类之前只想将样本划分为若干具有较小内部离散度的集簇，而常常并不了解 这样的集簇应当有多少个，这时输入参数的确定就具有一定的尝试性，而所产生的结 果往往不是令用户十分满意的。在另一些情况下，划分方法的聚类数目输入参数也可 以是主动的。例如，银行需要在某个人口分布区域内放置n 个a t m 柜员机，其放置 位置力求能够使用户距离最近的柜员机的平均距离最小，这就是一个典型的适合于划 分聚类方法的实例，而在这个例子中，聚类数目是人为确定的，所以在这种情况下， 聚类数目参数对结果的影响可以视为是主动的。 基于以上分析，可以认为，参数最小化的要求主要是针对被动情况而言的，对于 那些反映了聚类方法中用户不太了解、难于控制的因素，或者需要特别的专业领域知 识的因素的输入参数，应当尽量使其最小化。 另一个值得注意的问题是，输入参数的最小化并不简单的指输入参数的个数的最 小化。同时还要考虑参数对算法的影响程度，要将二者综合起来考量。以基于划分和 基于网格的方法为例。基于划分的方法一般要求一个输入参数即聚类数目，而基于网 格密度的方法一般要求两个输入参数即网格步长和密度阈值。但是一般来讲，聚类方 法的目的是将对象集合自发的划分为若干集簇，这个目的包含了两个含义，一是自发 的发现对象集合包含几个集簇，二是每个集簇都包含那些对象。而基于划分的方法虽 然只有一个输入参数，但是这个参数实际上是聚类方法的目的之一，而划分方法需要 将其作为前提，这显然是一个不足，这就使得这个参数对聚类结果的影响很大。如果 是在主动情况下，如上面提到的柜员机安置的实例，这样是适合的，而在更多的被动 情况下，划分方法就不太适用，限制了方法的适用范围。而基于网格密度的方法，虽 然有两个参数，但是这两个参数都回避了聚类的目的，并且，参数值的微小浮动，对 聚类结果的影响也同样是较小的，而基于划分的方法中，参数值的微小变化也会产生 截然不同的结果。同时，网格密度方法的两个参数在多数情况下是主动的，反映了用 户对聚类的要求。所以，基于网格密度方法在参数最小化方面是较好的。 通过以上分析我们可以得出结论，聚类参数对聚类结果的影响可以分为主动的和 被动的两类，在主动的情况下，参数的设定应当尽量向用户开放，用户可以通过参数 向算法传达不同的要求。而在被动的情况下，参数应当尽量向用户透明，降低对用户 领域知识的要求，同时也减少对聚类结果的无法预期的影响。 综上所述，如果能够在不同的情况下采取不同的参数设定方式，则算法在控制输 入参数对算法的影响方面将更为有效，也更便于用户使用。基于这种考虑，c p d g 算 法在开放输入参数以适应主动应用的同时提供了一种参数推荐方法使得当用户不能 g i s 系统中基于网格密度的空问聚类算法的研究与应用 够明确指定参数时，由算法根据聚类的基本要求来自动产生两个输入参数作为算法的 输入。 c p d g 参数推荐方法 首先考虑密度阈值参数。密度阈值参数反映了对密集性的定义，密度高于阈值的 区域称为是密集的，反之称为是稀疏的。那么在用户没有特另螨定阈值的情况下，根 据密度阚值的意义，平均密度是一个较为明显盼推荐密度阕值。高于平均密度的区域 可以被视为密集的，反之是稀疏的。在网格步长确定的前提下，可以很容易的得出平 均密度： d a v g = n m ( 3 1 ) 其中d a v g 为平均密度，n 为对象规模，m 为网格数，网格效可由空间范围及步 长直接求出。特别的，因为算法中对密集区域的定义是相对于对象分布空间，而不是 全空间，所以这里的空间范围指的是对象集合的最小外接矩经缩放到系统坐标范围后 的空间，相关详细内容将在5 3 1 节中介绍。 获取推荐密度阈值的前提是确定的网格步长，那么如何推荐网格步长参数昵? c p d g 算法的主要目的是发现分布于二维地理空间中的对象的二层结构，即主区域和 其内部的子区域。所谓主区域就是密度大于密度阚值的连续区域，由于主区域的尺度 一般较大，所以网格步长的变化对主区域的基本形态的影响较小。而所谓子区域是主 区域内部以密集中心为代表的若干区域，每个子区域都是由密集中心扩展而来，所以 密集中心的位置变化对子区域的形态影响较大。同时由于密集中心的尺度较小，所以 受网格步长的影响也较大，一个密集中心可能会被若干网格所分割，从而每个网格的 密度就会降低。所以，在均匀划分的前提下，密集中心应当尽可能的被容纳于一个网 格当中。如果用量化的方式来考察这种现象的话，就是密集中心韵密度同平均密度值 之间的差异要尽可能的大，如果用山脉和山峰来形容的话，就是山蜂要尽量的陡峭。 基于这种分析，c p d g 方法定义了一个密集中心的标准平均海拔； k z ( d p k ( i ) - d 。g ) h a v 9 2 生i r ( 3 2 ) 大连理工大学硕士学位论文 其中h a v g 表示密集中心的平均海拔，d r ，e a l ( ( i ) 表示第i 个密集中心的网格密 度，d a v g 表示平均网格密度，k 表示密集中心数目，s 表示网格步长。之所以要除 以网格步长的平方是因为不同的网格步长会影响网格密度的整体水平，由于要将不同 步长的密集中心的平均差异相比较，所以要通过与步长平方的比值来将不同步长下的 平均差异平衡到同一标准之上，否则无法互相比较。有了对标准平均海拔的定义，就 可以通过比较，找到使得标准平均海拔值最大的步长值作为步长参数的推荐值。由于 c p d g 方法本身的效率很高，所以虽然步长推荐方法需要遍历步长值，但是其速度是 很快的。 3 3 3 与传统网格密度方法及划分方法的比较 ( 一) 与传统网格密度方法( t d g ) 的比较 c p d g 方法是t d g 方法的一种改进。它与t d g 的关系可以概括为以下几点： ( 1 ) 基础相同。二者都是以空间的网格化及网格密度作为算法的基础，网格化方 法和密度统计方法相同。 文2 ) 代价相当。c p d g 方法的总体代价与t d g 方法基本相同。 ( 3 ) 对于最大密集连同区域的发现等价。c p d g 方法所发现的主区域与t d g 方 法的结果最大密集连通区域等价。 ( 4 ) 增加了发现子区域及二层结构的功能。c p d g 方法增加了t d g 方法所不具 有的发现最大密集连通区域内部的子区域的功能，并且通过建立两种区域的关系，发 现地理空间对象分布的二层结构。 对于二者在发现最大密集连通区域的功能上的等价性给出证明如下： 证明：对于同一空间对象分布，c p d g 方法的主区域与1 d g 方法的结果等价。 首先将方法的结果描述为一个网格关系表。表格大小为n x n ，其中n 为密集 网格的数目。表格的行列分别为密集网格集合。两个密集网格在聚类结果中的关系用 其在表中交叉处单元的元素来表示。若元素为融表示二者属于同一个最大密集连通 区域，并且该区域i d 为i ；若元素为空，则表示二者不属于同一个最大密集连通区域。 在此定义下，对于同一对象分布和网格划分，网格关系表同最大密集连通区域集合是 一一对应的。 这样，问题便转化为：对于同一空间对象分布集合，c p d g 方法的主区域的网格 关系表与t d g 方法的结果的网格关系表相同。 证明过程： ( 1 ) 证明：c p d g 与t d g 具有相同的关系表结构。 因为：c p d g 与t d g 的网格划分方法及密集网格定义方法相同 g i s 系统中基于网格密度的空间聚类算法的研究与应用 所以：对于同一空间对象分靠集合，c p d g 方法与t d g 方法具有相同的网格集 合和密集网格集合，即，若g 为c p d g 中的网格，则其也为t d g 中的网格，反之亦 然：若g 在c p d g 中是密集的，则其在t d g 中也是密集的，反之亦然。 所以：二者分析结果的网格关系表具有相同的表结构，即具有相同的表格规模n ， 和相同的行列标识。 ( 2 ) 证明：c p d g 关系表与t d g 关系表对应单元元素相同。 首先证明：若t d g 关系表中某元素为砒，则c p d g 关系表中对应元素也为弛。 设网格g j 与g j 的关系在t d g 的关系表中所对应的元素t a b l e i d 为r t ，即二网 格同属于一个最大密集连通区域，该区域i d 为t 。 往证：c p d g 的关系表t a b l e 中对应的元素t a b l e i , j 为r 鼽且唧。 1 ) 因为：由定义2 3 及2 5 知，可将g i 与o i 视为最大连通子图中的两个顶点。 且g 。与g j 在c p d g 中所属子区域为包含于最大连通子图中的两个连通子图。 2 ) 因为：c p d g 方法对各连通子图采用广度优先遍历，直至与其它子图相遇。 3 ) 由1 ) 、2 ) 知，最大连通予图中任一顶点必属于且仅属于一个连通子图，即连 通子图是对最大连通子图的一个划分。 4 ) 由3 ) 知，任两个连通子图若不同一，则或直接邻接，或被若干直接邻接的其 它子图所间隔。 5 ) 出4 ) 及c p d g 算法的区域融合规则知g i 与g i 在c p d o 中也必属予同最大 密集连通区域。设该区域为r p 。 6 ) 因为：r t 与r p 均为连通区域，对应两个最大连通子图，且该两子图至少有 g i 与g i 两个公共点。 7 ) 所以：r t 与r p 同一，即卢p ，目标得证。 其次证明：若t d g 关系表中，某单元为空，则c p d g 关系表中对应单元也为空。 假设：网格g j 与q 的关系在t d o 的关系表t a b l e 中旃对应得元素t a b l e e i j 为空， 而在c p d g 中对应单元元素不为空。 1 ) 因为：c p d g 中对应单元元素不为空。 2 ) 所以：g 与g i 同属于某一主区域，即最大连通区域。 3 ) 所以：g i 与g i 在对应连通图中，至少存在一条通路。 4 ) 所以：g i 与g i 在t d g 中也必属于回一最大连通区域。即t d g 关系表项 t a b l e i , j 不为空。 结论4 ) 与假设矛盾，所以假设错误，目标得证。综合以上两点证明，c p d g 关系 表与t d g 关系对应单元元素相同。 由证明( 1 ) 、( 2 ) 知，对于同一空间对象分布集合，c p d g 方法的主区域的网格关 大连理l 大学硕士学位论文 系表与t d g 方法的结果的网格关系表同一，结论得证。 ( 二) 与基于距离的划分方法的比较 c p d g 方法在密集连通区域内部，通过定位峰值网格及由峰值网格开始的广度优 先扩展来形成子区域，该子区域在对象分布具有若干较为明显的密集中心时近似于划 分方法结果的区域划分。这种近似性主要体现在以下几点。 ( 1 ) 二者都具有代表中心。划分方法以某一个中心对象，或中心位置为代表，而 c p d g 以一个特别密集的区域中心为代表。 ( 2 ) 二者所发现区域都具有近似圆形的趋势。划分方法由于基于最小平均距离的 思想，所以所发现区域有近似圆形的趋势，而c p d g 方法由于以密集点为中心向周 围进行广度优先的扩张，所以所发现的子区域也具有近似圆形的趋势。 ( 3 ) 二者区域内部的对象都具有较小的平均离散度，或称为较好的互可达性。由 于二者均同时具有特点( 1 ) 和( 2 ) ，所以所形成的区域都是向心的近似圆形的区域，故 区域内对象的离散度也都较小，具有较好的互可达性。 与经典的基于划分的方法的比较中，c p d g 还具有以下几点主要的优势和不足。 优势： ( 1 ) 速度快：由于c p d g 方法是基于网格的，时间复杂性独立于样本规模，所以 其运行速度大大快于划分方法，十分适合如g i s 系统一样数据规模较大的应用。 ( 2 ) 对离散点处理较好：由于c p d g 方法中，子区域是隶属于主区域的一个划分， 而主区域是一个淘汰了离散点的密集连通区域，所以c p d g 方法所发现的予区域是 无噪声的，对于以发现区域为目的的二维空间聚类而言，这是一个很好的特性。 ( 3 ) 不需要聚类数及初始点作为参数：基于划分的方法需要聚类数目，及相同数 目的初始点作为输入参数，而c p d g 方法通过发现峰值网格，可以自发的产生聚类 数目和代表中心。 ( 4 ) 代表中心是密集的：划分方法的代表点不一定位于密集区域，而c p d g 方法 的代表中心位于特别密集区域中，更符合揭示地理分布二重性的要求。 不足： ( 1 ) c p d g 方法与划分方法相比最主要的不足在于其子区域不具有严格的最小内 部平均离散度。由于c p d g 方法中的子区域的目标是发现基于密集中心的辐射区域， 其发现方法是基于密度而不是基于距离的，所以其子区域集合并不能保证具有最小的 内部平均离散度。但是在聚集性较强的情况下，子区域也具有较小的平均离散度。 ( 2 1 不能够做全局性的划分。c p d g 方法是基于二维地理分布的二重性特点而设 计的，其目的是发现基于密度的不同形态的区域。子区域位于聚类结构的第二层，只 在主区域内部进行划分。对于要求对对象总体进行全局性的、面向最小内部离散度的 g i s 系统中基于网格密度的空向聚类算法的研究与应用 完全划分的应用，是不适合使用c p d g 方法的。 ( 3 ) 不能够指定聚类数目；一般情况下，聚类数目是作为聚类分析方法的一个输 出量。而在一些特殊应用中，需要人为指定特定的聚类数目作为输入量，这一点在参 数分析一节已有详细介绍。由于c p d g 方法不能够指定聚类数目作为输入量，所以 c p d g 也不适合于该种应用。 3 4 算法复杂性分析 3 4 1 算法的时间复杂性 与传统的网格密度方法类似。设样本规模为n ，网格数为m ，密集网格数为m 。 显然有m = ( p ，q ) ，所以e = e ，即e 是e 的底 限值。由于新的距离函数d ( p ，q ) 的结果是所有绕过障碍的路径中距离最短的，则 计算过程可递归地分为如下三步： 大连理工大学硕士学位论文 1 ) 如果p ，q 两点可见( 不被任何障碍物遮挡) ，则障碍距离就等于直线距离， 即d ( p ，q ) = d ( p ，q ) ，否则执行2 ) 3 ) 。 2 ) 对于点p ，假设它可见的所有障碍物的顶点为v i s ( p ) = v 1 ，v 2 ，v b ，其 中每个顶点到p 的直线距离是d ( p ，v i ) ，1 - i - f l 。 3 ) 在v i s ( p ) 中每个顶点到点q 的障碍距离是d ( q ，v i ) ，这样我们就可以在v i s ( p ) 中找到一个顶点v m ，使得d ( p ，v m ) + d ( q ，v m ) 的值最小，自然p 到q 的障 碍距离就是d ( p ，v m ) + d ( q ，v m ) 。如图下图所示，黑色区域为障碍物，p 、q 两点 被障碍物遮挡，不可见。p 点可见的障碍物顶点有v l 、v 2 、v 3 ，在可见的三个顶点 中明显只有绕过v 3 的路径距离最短，所以p 、q 两点的障碍距离应为：d ( p ，q ) = d ( p ，v 3 ) - fd ( q ，v 3 ) 。 图4 5 描述了对象间的改进距离： 图4 5 对象间的改进距离 砘g 4 5i m p r o v e dd i s t a n c eb e t w e e no b i e e t s 2 改进的密度方法( 3 4 ：改进的密度方法对基于密度思想的聚类方法进行改进， 具体方法可以是面向对象的，也可以是面向网格的。其改进的部分主要在于，在定义 密度邻接关系时，邻接关系不允许跨越障碍。具体地讲，在面向对象的密度方法中， 该方法要求两邻接对象的连线不允许与障碍相交：在面向网格的方法中，该方法要求 邻接网格不允许被障碍穿越或者覆盖。 3 可见空间法 3 5 1 ：可见空间法独立于具体的聚类算法，它处理障碍约束的主要 思想是，在存在障碍的二维空间中引入“可见空间”的概念。首先方法定义“可见” 的概念：如果二维空间中的两个点的连线不穿越任何障碍，则称这两点间是可见的。 在“可见”概念的基础上，方法进一步定义了“可见空间”的概念，“可见空间”是 指一个= 维的空间区域，在这个区域中任意两点均是互相可见的。特别的，有“最大 可见空间”的概念，一个“最大可见空间”是指一个“可见空间”，如果再向其中加 入任一个其它象素点，则其不再是可见空间。一个二维空间，在存在障碍物的情况下， 可以依据障碍物划分为若干最大可见空间。 基于可见空间概念，可见空间法提出的处理障碍约束的聚类方法是：无论使用哪 g i s 系统中基于网格密度的空间聚类算法的研究与应用 一种具体的聚类算法，算法所形成的任一密集区域或者集簇都必须局限于某个可见 空间之内。这便是可见空间法的基本思想。 4 2 ，4 其它方法与c p d g 的比较 在4 1 。1 节中提到，障碍对空间对象集合的影响体现在连通性和对象间距离两个 方面。聚类分析中处理空间障碍的方法的目的，就是要在有障礴存在的情况下，在聚 类结果中体现障碍对空间对象集合的这两个方面的影响。在这一节中，将从这两种影 响的角度来比较c p d g 方法及其它几种主要的障碍处理方法。 首先，在完全分割的情况下，空阔对象集合的连通性和对象间距离都受到了障碍 的影响。原本连通的区域，被分割为不连通的两部分，丽原来的较低离散度的近似圆 形的集簇也可能由于对象间距离的变化被分割开来或者重新划分。 在这一情况下： ( 1 ) 改进的距离方法是基于对象间距离的方法，能够充分反映障碍对距离的影 响。该方法本身并不具有体现区域连续性的能力，但是由于这时距离较大的对象往往 也分属于不同的连通区域，反之亦然，所以在这种情况下密集连通区域往往和低离散 度集簇具有较高的吻合性，故该方法在此情况下能够一定程度的间接反映出障碍对连 通区域的分割。 ( 2 ) 改进的密度方法由于是基于密集连通性韵。所以可以很好的反映连通性的变 化。该方法本身并不具有直接体现对象间距离的能力，但是出于上面所述原因，完全 分割下密集连通区域和低离散度集簇具有较高的吻合性，所以该方法也能够通过基于 密度的分割，一定程度的间接反映出基于距离的分割。 ( 3 ) 可见空间方法在完全分割的情况下，通过预分割空间来反映障碍约束，并不 直接涉及距离及密度的思想，从这点上来看它对两种变化的反映都是间接的，但是 由于可见空间的思想较为直接的反映了完全分割的特点，所以往往具有较好的效果。 ( 4 ) c p d g 方法在完全分割的情况下，由于将障碍转化为不可跨越的低密度区 域，所以其主区域属于一种改迸的密度方法，在较好反浃连通性变化的同时，一定程 度的反映了距离的变化。另一方面，子区域也会受到障碍的影响，在障碍两侧重新形 成新的子区域。总体而言，这时，c p d g 对于连通性的变化的反映是直接的，而对于 对象距离的变化的反映是间接的。 其次，在不完全分割的情况下，空间对象集合的连通性没有受到影响，而对象间 距离受到了膨晌。原本连通的区域仍然是连通的，而连通区域内部位于障碍两侧的对 象间的距离受到了影响。原本属于同一较低离散度的近似圆形集簇的对象也可能由于 对象间距离的增大，被分割开来。 在这一情况下： 人连理f ：人学硕十学位论文 ( 1 1 改进的距离方法仍然能够充分反映障碍对距离的影响。集簇大致的分布j 一障 碍两侧。但是无法体现出未受影响的连通性。 ( 2 1 改进的密度方法可以很好的反映未受影响的连通区域。但是