（计算机应用技术专业论文）基于空间数据库的数据挖掘方法研究.pdf

山东师范大学硕士学位论文 摘要 随着空间数据获取技术的快速发展，空间数据量急剧增加。为了充分地利用空间数 据库中的资源，在大量的数据中获取有价值的信息，提出了空间数据挖掘技术。空间数 据挖掘技术可以帮助人们理解空间数据，获取空间数据之间的内在关系。文中对空间数 据库以及空间数据挖掘方面的基础知识咆括空间数据库的数据结构、数据模型、索 引技术，以及空间数据挖掘的基本步骤、方法等进行了详细的介绍，作为进行空间聚类 研究的理论基础。 聚类分析是空间数据挖掘的一个重要的研究方向，它通过度量空间数据之间的相似 性将空间数据库划分为不同的簇或类，使得同簇中的对象尽可能相似，而不同簇之间的 对象尽可能不同。聚类分析在现实生活中用途广泛，可以用在选址、客户群分类等方面， 帮助投资者进行决策，并带来尽可能大的效益。因此，聚类具有重大的研究意义。 目前，已经有许多比较成熟的聚类算法，如d b s c a n 算法、c u r e 算法、c l a r a n s 算法等。这些算法是空间聚类的经典算法，但仍在某些方面存在一定的问题。本文的研 究重点就是在已有算法的基础上，对算法进行改进，以提高算法效率。本文针对普通聚 类和带障碍约束的聚类，分别提出了一种改进算法。 算法1 ：对d b s c a n 算法的改进。d b s c a n 算法需要判断每个对象是否是核心点， 这种判断会占据大量的i o 开销，是限制算法效率的瓶颈。、本文的算法不需要对每个点 进行核心点判断，算法在寻找连通区域的过程中，每次循环选取一个没有聚类标识的点： 如果这个点是核心点，并且其核心区域内的点已经有其他的聚类标识，则将该点及其核 心区域的点的聚类标识设置为其中的最小值；若该点不是核心点，则选择下一个点继续 判断。这种算法不仅大大减少了需要判断的核心点的数量，而且在寻找连通区域的同时 直接将聚类合并，会大大提高算法的时间效率。 算法2 ：基于数学形态学的带障碍约束的空间聚类算法。该算法主要借鉴数学形态 学聚类一m m c 算法的基本思想，在此基础上加入了对障碍约束的处理。该算法与 d b c l u c 算法不同，不需要通过每两个对象的连线是否与障碍物相交来判断两对象是否 属于同一个类，而是借助于结构元素，仅仅对受障碍物影响的对象( 即障碍物附近的点) 进行判断。从数据点集中选取一个点作为结构元素的圆心进行膨胀运算，若结构元素与 障碍物相交，则将位于圆心的点与该点膨胀运算所包含的点分别连线，对于连线与障碍 物相交的点，将其f l a g 值设为f a l s e ，说明该点位于障碍物的另一侧，与圆心点不属于 1 山东师范大学硕士学位论文 同一个连通区域：对于连线不与障碍物相交的点赋予与圆心位置的点同样的聚类标识。 经过分析，算法的效率优于其他算法。在文章的最后，进行了数据实验，进一步验证了 算法的正确性和有效性。 本文对空间数据库、空间数据挖掘、空间聚类技术进行了探讨，一步一步深入，最 后提出了改进的聚类算法。在后续的研究工作中，作者需要阅读大量的聚类技术方面的 书籍及文章，提出更快、更易于理解的算法，并应用在实际的生产、生活中，辅助决策 者做出正确的决策，获得更好的效益。 关键词：空间数据库；空间数据挖掘；空间聚类：基于密度的空间聚类算法；障碍约束 中图分类号：t p 3 9 3 2 山东师范大学硕士学位论文 a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fs p a t i a ld a t ao b t a i n e dt e c h n o l o g y , s p a t i a ld a t ai n c r e a s eu p r a p i d l y s p a t a i ld a t am i n i n gt e c h n o l o g yw a sm e n t i o n e di no r d e rt ou s et h er e s o u r c e si nt h e s p a t a i ld a t a b a s e se n o u g h l y s p a t a i ld a t am i n i n gt e c h n o l o g yc o u l dh e l pp e o p l eu n d e r s t a n d i n g s p a t i a ld a t aa n dp i c k i n gu pr e l a t i o n sb e t w e e ns p a t i a ld a t a i nt h sp a p e r , w ei n t r o d u c e t h eb a s i c t h e o r yo fs p a t i a ld a t a b a s ea n ds p a t i a ld a t am i n i n g ，i n c l u d et h es p a t i a ld a t as t r u c t r u e ，s p a t i a l d a t am o d e l ，s p a t i a ld a t ai n d e xt e c h n o l o g ya n dt h es t e p s ，m e t h o d so fs p a t i a ld a t am i n i n g 砧lo f t h e s ea r et h eb a s i ct h e o r yo fc l u s t e ra l g o r i t h m c l u s t e r i n ga n a l y s i si sav e r yi m p o r t a n tf i e l di ns p a t i a ld a t am i n i n ga r e a i td e p e n d so n m e a s u r et h es i m i l a r i t yb e t w e e ns p a t i a ld a t a si n t om e a n i n g f u ls u b c l a s s e ss ot h a tt h em e m b e r s o fac l u s t e ra l ea ss i m i l a ra sp o s s i b l ew h e r e a st h em e m b e r so fd i f f e r e n tc l u s t e r sd i f f e ra s m u c ha sp o s s i b l e s p a t i a lc l u s t e r i n gi sw i d e l yu s e di nd a i l yl i f e i tc a l lb eu s e di nl o c a t i o n s e l e c t i o n ，c u s t o m e rc l a s s i f i c a t i o na n ds oo n i tc a nh e l pi n v e s t o r s d e c i s i o n m a k i n g ，a n db r i n g b e n e f i ta sm u c ha sp o s s i b l e i ns y n t h e s i s ，c l u s t e r i n gh a si m p o r t a n tr e s e a r c hs i g n i f i c a n c e n o w , t h e r ea r em a n ym a t u r ec l u s t e r i n ga l g o r i t h m s ，s u c ha sd b s c a na l g o r i t h m ，c u r e a l g o r i t h m ，c l a r a n sa l g o r i t h ma n ds oo n t h e s ea r ec l a s s i ca l g o r i t h m si nc l u s t e r i n gf i l e d ，b u t t h e r ea r es t i l lm a n yc h a l l e n g e s t h em o s ti m p o r t a n tr e s e r a c hi nt h i sp a p e ri st oi m p r o v et h e e f f i c i e n c yo fc l u s t e r i n ga l g o r i t h m s i nt h i sp a p e r , w ei n t r o d u c et w oi m p r o v e da l g o r i t h m sf o r t h eg e n e r a lc l u s t e r i n ga n df o rt h ec l u s t e r i n gw i t ho b s t a c l ec o n s t r a i n t s a l g o r i t h m1 - i m p o v et h ed b s c a na l g o r i t h m d b s c a na l g o r i t h mr e p e a t e d l yp i c k s e v e r yp o i n t sa n de x a m i n i n gw h e t h e ri ti sac o r ep o i n t ，t h ei os p e n d i n go f t h i ss t e pi sv e r yb i g a n dt h es t e pl i m i t st h ea l g o r i t h me f f i c i e n c y t h ei m p o v e da l g o r i t h mn e e d n tt oj u d g ew h e t h e r e a c ho ft h ep o i n ti st h ec o r ep o i n t i nt h es e a r c hf o rr e g i o n a lc o n n e c t i v i t y , e a c hc y c l es e l e c ta p o i n tw i t h o u tam a r k ：i ft h ep o i n ti sac o r ep o i n t ，a n di t se p s - r e g i o nh a so t h e rp o i n t sw h i c h h a s o t h e rm a r k s ，t h e na l lt h ep o i n t sm a r kt h em i n i m u m ；i fn o t ，s e l e c tt h en e x tp o i n tt oc h a r g e t h e a l g o r i t h mn o to n l yr e d u c et h ea m o u n to f t h ep o i n tw h i c hn e e dt oj u d g e ，b u ta l s oi m p r o v et h e e f f i c i e n c y a l g o r i t h m2 ：c l u s t e r i n ga l g o r i t h mb a s e do nm a t h e m a t i c a lm o r p h o l o g yi nt h ep r e s e n c e o fo b s t a c l e s t h ea l g o r i t h mb a s e do nt h ei d e ao ft h ea l g o t i t h mo fm m c ，a n da d d i n ga c o n s t r a i n tt od e a lw i t ho b s t a c l e s t h ea l g o t i t h r ni sd i f f e r e n tf r o mt h ed b c i u c ，i ti sn e e dn o tt o c o n n e c te a c ht w op o i n t st oj u d g ew h e t h e rt h ep o i n t sa r ei nas a m ec l a s so rs e p a r a t e db y 3 山东师范大学硕士学位论文 o b s t a c l e s i tu s e das t r u c t u r a le l e m e n t ，d e a lw i t hp o i n t sw h i c ha r ea f f e c t e db yt h eo b s t a c l e s o n l y i ft h es t r u c t u r a le l e m e n ti sc r o s s e dw i t ho n eo b s t a c l e ，t h e nc o n n e c tt h ec e n t e rp o i n ta n d o t h e rp o i n t si nt h ec i r c l e ，i fo n el i n ei sc r o s s e dw i t ht h eo b s t a c l e ，t h e nt a k ei t sf l a ga sf a l s e ，i t s s a i dt h a tt h ep o 硫i si nt h eo t h e rs i d eo ft h eo b s t a c l e ；i fn o t ，t h ep o 血i si nt h es a m ec l a s sw i t h t h ec e n t e rp o i n t a f t e ra n a l y s i s ，t h ee f f i c i e n c yo fa l g o r i t h mi ss u p e r i o rt oo t h e r a l g o r i t h m s i n t h ee n d ，w et a k ead a t ae x p e r i m e n t ，v e r i f i e dt h ec o r r e c t n e s sa n de f f e c t i v e n e s so f a l g o r i t h m i nt h i s p a p e r , w e d i s c u s ss p a t i a l d a t a b a s e ，s p a t i a ld a t a b a s em i n i n g ，s p a t i a ld a t a b a s e c l u s t e r i n gs t e pb ys t e p ，a n dt h e np u tf o r w a r da ni m p r o v e dc l u s t e r i n ga l g o r i t h m i nt h ef u t u r e r e s e a r c hw o r k ，i n e e dt or e a da l a r g en u m b e r o fc l u s t e r i n gt e c h n o l o g yb o o k sa n da r t i c l e s ，m a d e f a s t e r , e a s i e ru n d e r s t a n d i n ga l g o r i t h m s ，a n du s e di nr e a l p r o d u c t i o n , l i f e ，t os u p p o r t d e c i s i o n m a k e r $ t oo b t a i nb e t t e rr e s u l t s k e y w o r d s ：s p a t i a ld a t a b a s e ；s p a t i a ld a t am i n i n g ；s p a t i a ld a t ac l u s t e r ； s p a t i a lc l u s t e rb a s e do nd e n s i t y ；o b s t a c l e c l a s s i 6 c a t i o n ：t p 3 9 3 4 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其它人已经发表或撰写过 的研究成果，也不包含为获得( 注：如没有其它需要特别声明的，本栏可空) 或其它教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：0 ，厶娟 导师签字： 孥 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国家有关 部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。( 保密的学位论文在解密后适用本授权书) = 篡撬日三：2 0 0 磐9 刚日 签字r 期：2 0 07 年月旧日签字日期： 。年彳月7 日 山东师范大学硕士学位论文 1 。1 引言 第一章绪论 由于雷达、红外、光电、卫星、电视摄像、电子显微成像、c t 成像等各种宏观与 微观传感器的使用，空间数据的数量、大小和复杂性都在飞快地增长，已经远远超出了 人们的解译能力。终端用户不可能详细地分析所有数据，并提取感兴趣的空间知识，致 使“空间数据爆炸但知识贫乏 现象的出现【l 】。因此，利用空间数据挖掘和知识发现 ( s d m k d ，s p m i a ls a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 从空间数据库中自动或半自动 地挖掘事先未知却潜在有用的空间模式变得十分必要。 1 9 9 4 年，在加拿大渥太华举行的g i s 国际学术会议上，李德仁院士首次提出了空 间数据挖掘概念。从此，空间数据挖掘研究全面展开。目前，许多研究人员除借鉴数据 挖掘已有的理论方法之外，主要针对空间数据的数据量大、数据结构复杂以及多维性等 特点进行研究，试图提高算法运行的时间效率和空间效率。本文的研究目的就是通过分 析已有的空间聚类算法，对算法进行改进，提高空间数据挖掘的时间效率和空间效率p j 。 1 2 国内外研究现状及研究方向 目前，国内外对数据挖掘与知识发现方面的研究，无论是在学术上，还是在实践中 都取得了很大的突破。然而，由于空间数据库与关系数据库的特点不同，传统的数据挖 掘方法并不完全适用于空间数据库，空间数据挖掘技术尚存在很多需要研究、改进的方 面，正是这些需求指引着空间数据挖掘技术不断向前发展。 1 2 1 研究现状 空间数据挖掘作为数据挖掘的一个分支，发展历史较短，但近几年己成为国际研究 的一个热点，国外开展这方面的研究较早于国内。 加拿大的西蒙弗雷( s i m o n f r a s e r ) 大学、德国的慕尼黑大学、芬兰赫尔辛基大学以及 美国、澳大利亚等国家的许多大学和研究所，都有较为著名的研究成果报道。这些研究 的重点是提高原有数据挖掘算法在空间数据库上的执行效率【3 】。 在一些数据挖掘和知识发现的国际会议中，空间数据挖掘逐渐成为重要的研究主题 之一。由美国人工智能协会( a a a i ) 举办的国际k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g f k m d k ) 学术会议，关于空间数据挖掘的论文数量不断增长。目前，各种规模的学术会 议都已经把空间数据挖掘作为一个重要的研究课题。此外，d a t am i n i n g 、a d v a n c e d s p a t i md a t a b a s e s 、v e r yl a r g ed a t a b a s e s 、i n t e r n a t i o n a ls y m p o s i u mo nd i g i t a l e a r t h 、 a c m 、i f i s 和s i g m o d 等国际学术会议，空间数据挖掘已经成为关注的热点。k l u w e r p u b l i c a t i o n 、s p r i n g e r - v e r l a g 、a c a d e m i cp r e s s 、w i tp r e s s 等国际著名的出版公司也开始出 山东师范大学硕士学位论文 版发行空间数据挖掘的学术期刊、专著或者论文集。 在中国，武汉大学、中科院地理所资源与环境信息系统国家重点实验室、中科院遥 感所、中科院软件所、中国测绘科学研究院等，都开展了空间数据挖掘的研究。武汉大 学的李德仁教授提出从空间数据库可以发现包括几何信息、空间关系、几何性质与属性 之间的关系、面向对象知识等。 空间数据挖掘可以应用在城市管理、经营效益分析、空间决策支持等各个领域，正 在引起越来越多的研究与关注。 1 2 2 研究方向 空间数据挖掘不同于数据挖掘，起步较晚，且空间数据具有数据量巨大、数据类型 复杂、多维性等特点。对它的研究目前主要集中在以下几个方面【l ，3 4 】： 1 、空间数据挖掘与经典数据挖掘的比较 空间数据中的部分空间关系可否转换为传统的数据列，以便使用经典数据挖掘技术 进行挖掘? 如果可以，哪些空间关系可以转化，哪些不可以? 这将是未来空间数据挖掘 的一个研究方向。 2 、空间数据的预处理 空间数据本身的复杂性以及数据采集过程中设备、人员操作的误差，决定了空间数 据存在大量的缺陷。为了避免“g a r b a g ei n ，g a r b a g eo u t ，在进行数据挖掘之前，需要 对原始数据进行预处理：首先进行属性筛选，去除对结果影响较小的属性数据，然后进 行数据清理，遗漏数据修复等。这些工作是空间数据挖掘能够得到精准结果的保障； 3 、算法效率的提高 对任何一个算法来说，提高效率都是研究者追求的一个重要目标。空间数据的复杂 性和海量性的特点使得空间数据挖掘比经典数据挖掘更加耗时，同时占用的存储空间也 更大，所以提高空间数据挖掘算法的时空效率是重要的研究方向； 4 、空间数的表达 如何将据挖掘结果数据挖掘结果以用户易于理解的方式( 如：自然语言、图形) 精 确的表达出来，以给用户提供良好的决策支持，是空间数据挖掘研究的一个方向。 1 3 空间数据库概述 空间数据库是空间数据及其相关非空间数据的集合，用以描述现实世界的空间位 置、属性等信息。空间数据是与地理和空间分布有关的，反映现实世界各种现象及其变 化的符号记录【2 1 。其中，空间数据是基础，非空间数据是内涵，是地理单元的纵深描述。 与一般数据库相比，空间数据库具有空间性、时间性、多维性、海量性、复杂性等特点。 空间数据库的种类很多，可分为观测数据、地图数据、遥感数据以及统计数据等【6 】。 6 山东师范大学硕士学位论文 1 3 1 空间数据结构 空间数据结构是指空间数据在计算机内的组织和编码形式，是指适合于计算机存 储、管理、处理的地理实体空间数据的逻辑结构【刀。它是对数据的一种理解和解释。 对于空间实体，我们首先要确定空间数据对空间实体的描述形式。在计算机内，常 用的对空间实体的存储、描述形式有：矢量数据结构( 隐式描述) 、栅格数据结构( 显 式描述) 、失栅一体化的数据结构。这三种数据结构各有自己的特点及适用范围，其中， 失栅一体化的数据结构是在前两种数据结构的基础上并结合它们的优点而发展起来的。 下面分别介绍三种数据结构【s j ： 1 、矢量数据结构 矢量数据结构是通过记录坐标的方式，尽可能地将点、线、面等地理实体表现的精 确无误。矢量数据结构将其坐标空间假定为连续空间，每一个点由( x ，n 坐标来表示。 在矢量数据结构中，点实体包括由单独一对( x ，y ) 坐标定位的一切地理或制图实体；线 实体可以定义为直线元素组成的各种线性要素，直线元素由两对以上的( x ，y ) 坐标定 义；面状实体由首尾相连的线状实体组成，最终也由点来表示。各种类型空间实体的存 储方式如图1 1 所示： y ( a ) 点的表示 x ( b ) 线的表示 图i - i 空间实体的矢量结构 x ( c ) 面的表示 2 、栅格数据结构 顾名思义，栅格数据结构就是将存储空间划分为均匀的网格，每一个网格为一个 栅格，有唯一的行列数，行列的数目取决于栅格的分辨率和空间实体的特征。点状实体 直接表示为一个单一的网格；线状实体由一系列相邻的网格连接而成；面状实体表示为 由边所围成的区域内的所有网格点以及各个边所包含的网格点的集合。为了便于理解， 我们用图1 2 表示了几种空间实体的存储方式： 7 山东师范大学硕士学位论文 l i l l i il i _l i ( a ) 点的表示( b ) 线的表示( c ) 面的表示 图1 - 2 空间实体的栅格结构 比较内容矢量结构栅格结构 数据共享容易实现不易实现 拓扑关系提供有效的拓扑编码，容易实难以表达拓扑关系，但容易实 现网络分析现叠加操作 数据量 小大 图形精度高低 图形运算复杂、高效简单、低效 输出显示抽象、昂贵、比较美观直观、便宜、线条宜有锯齿 表1 - 1 矢量结构与栅格结构的比较1 3 、失栅一体化数据结构 为了解决栅格、矢量数据直接交互的问题，矢栅一体化的数据结构应运而生，这种 数据结构兼有矢量和栅格两种结构的特性。 目前研究的矢栅一体化结构主要有三种：栅格索引型、矢量栅格化型、混合型。栅 格索引型数据的特点是点线面的矢量数据结构中加入栅格索引结构来辅助矢量数据的 编辑、处理及空间分析。矢量栅格化型数据结构则是在建立空间栅格索引的同时，把传 统的矢量型点线面数据也部分采用元子充填形式表示，郎矢量数据栅格化，较具代表性 的是粗细分格网法。混合型结构通过矢栅转换接口把矢量数据和栅格数据有机地结合在 一起。 为了使点状：线状、面状地物的数据结构兼具栅格和矢量的特点，龚建雅( 1 9 9 2 ) 年做了如下约定：( 1 ) 地面上的点状地物是地球表面上的点，它仅有空间位置，没有形 状和面积，在计算机内仅有一个位置数据；( 2 ) 地面上的线状地物是地球表面的空间曲 线，它有形状但没有面积，在计算机内需要用一组元子填满整个路径；( 3 ) 地面上的面 状地物是地球表面的空间曲面，并具有形状和面积，在计算机内由一组填满路径的元子 表达的边界和内部区域构成。 山东师范大学硕士学位论文 1 3 2 空间数据模型 空间数据模型是描述空间实体与实体之间关系的数据模型，一般来说既可以利用传 统的数据模型加以扩充和修改来实现，也可以用面向对象的数据模型来实现。空间数据 模型可以分为以下几种类型： 1 、层次模型 用层次结构表示实体间联系的数据模型称为层次数据模型( h i e r a r c h i c a l d a t a m o d e l ) 。层次结构是树状结构，树的结点是记录类型，根在上，叶在下，它是数据 处理中发展较早、技术上也比较成熟的一种数据模型。 当数据实体之间存在l ：n 的“父子 关系，且主从关系明确时，易于用层次模型 来描述。它具有如下性质： ( 1 ) 有且只有一个根节点； ( 2 ) 除根节点外，每个节点都有且只有一个父节点； ( 3 ) 除叶节点外，其他节点都可以有若干个子结点； ( 4 ) 有多个叶节点，其下再无其他节点。 层次模型反映了现实世界中实体间的层次关系，层次结构是众多空间对象的自然表 达形式，并在一定程度上支持数据的重构。层次模型直观，应用范围广泛，典型的例子 是描述一个城市的房屋位置。图1 3 为层次模型的示意图，包括区文件、街道文件和房 屋文件三个层次。 图1 - 3 层次模型 ( 其中q 为区文件，s 为街道文件，h 为房屋文件) 2 、网络模型 在空间网络模型中，地理现象被抽象为链、结点以及它们之间的连通关系。网络模 型将数据组织成图的结构，结点代表数据记录，边表示结点之间的连通关系，任何一个 结点可以和其他任意多个结点建立联系。图的形式化定义为： g = v ( g ) ，e ( g ) ，r g 9 山东师范大学硕士学位论文 式中，v ( g ) 为图的结点的集合，e ( g ) 为边的集合，r g 为结点之间关系的集合。网 络模型的结点间没有明确的从属关系。由于网络模型的结构复杂，且无规律，用户对数 据的查询和定位比较困难，因此在空间分析中应用较少。网络模型的结构如图1 _ 4 所示： 图1 4 网络模型 3 、关系模型 关系模型是使用范围最广泛的一种数据模型，比较大型的空间数据库均采用关系模 型。关系模型将数据的逻辑结构转化为满足一定条件的二维表，二维表中的每一行代表 一个实体，列代表实体的属性，既能表示实体又能表示联系，而且能表达多种联系。关 系模型能处理多种复杂的数据结构，数据结构灵活、清晰，便于用户使用。 例如，一个城市数字化地图的关系型数据库的部分关系如下： 道路：r o a d s ( f r a m e 、r o i d 、x l 、x 2 、y l 、y 2 ) 道路名：r o n a m e ( f r a m e 、r o i d 、n a m e ) 位置：p o s ( f r a m e 、x s i z e 、y s i z e 、x c e n 、y c e n ) 1 3 3 空间数据索引技术 一般的数据挖掘技术在处理高维数据时效率低下，为了提高算法效率，人们寻求各 种解决方法，其中，索引技术是比较常见的一种方法【4 2 1 。 传统的索引方法( 如：b 树索引) 只能针对一维的字符、数字等简单数据类型，无 法支持空间数据的查询与更新，为此，人们提出了空间索引。空间数据索引是指依据空 间实体的位置和形状或空间实体间的某种空间关系按一定的顺序排列的一种数据结构 【9 】。作为一种辅助性的空间数据结构，空间数据索引介于空间操作算法和地理实体之间， 它通过筛选，排除大量与特定空间操作无关的地理实体，从而提高空间操作的速度和效 率【1 3 】。 根据自身结构的不同，空间索引分为树型空间索引和基于h a s h 的网格类索引两类： l 、树型索引【1 1 , 1 2 j 树型索引可以高效支持查询。要回答一个查询，若没有树型索引，则必须扫描整个 数据集，若通过树型索引，则只需访问部分字数对应的数据，因而缩小查询范围，提高 查询效率。树型空间索引分为基于数据划分和基于空间划分两类，前者划分数据集，并 建立数据子集的包含区域( b o u n d i n gr e g i o n ) 的层次结构，如r 树、r 宰树、s s 树等； 1 0 山东师范大学硕士学位论文 后者将数据空间划分为不相交的子空间，并建立子空间的层次结构，如q u a d t r e e ( 四叉 树) 、k d 树等。下面分别介绍这几类空间索引技术。 r 树 r 树是一种常用的动态索引技术，主要用于对多维空间数据索引。r 树类似于b 树， 是一种高度平衡的树，它基于最小包含矩形m b r 划分数据，使空间上靠近的空间对象 拥有尽可能近的共同祖先。 r 树中每个节点由若干个形如( r e c t ，r e 0 的单元组成。对于中间节点，r e 堤指向子树 的指针，r e c t 是包含该子树中所有对象的m b r ；对于叶节点，r e f , $ 空间对象在数据库中 的记录指针，r e c t 是它的m b r 。根节点至少含有两个孩节点；除根节点，所有节点的单 元数在m 到m 之i 日- j ，m 是一个页块最多容纳单元的个数，且2 m lm 2i 。当节点 中的单元数超过m 时，就需要分裂。r 树选择采用使分裂产生的两部分m b r 面积之和 最小的分裂方案。 四叉树 四叉树是基于空间划分的空间索引，适用于二维空间，分支数为4 。四叉树使用递 归分解的原则，不断将空间等分为东北、东南、西北、西南四个象限，直至每个子空间 中的对象数目不大于某个阈值。四叉树易于理解，但不平衡，对于高密度区域，子树要 比低密度区域的子树深。四叉树一旦建立，树的层次就被固定，不能满足空间数据的动 态更新，四叉树不适合于大型高维数据集。 k d 树 ， k - d 树是用于存储维点数据( k e y , ，k e y ：，k e y , ) 的二叉树。它递归地用经过某个数据 点、且垂直于某一维的k 一1 维分裂超平面来划分数据空间，直到所有子空间包含的点 数都不大于1 。 k d 树可以支持多种查询操作，但在高维时性能下降。k d 树不易保持动态平衡， 其结构依赖于点数据的输入顺序。 2 、网格类索引【1 o 】 格网索引面向地图对象的空间位置和分布，属于栅格类索引，它的特点是简洁、高 效、易于实现。 格网索引将工作区按一定的规则划分成正方形格网，之所以划分成正方形是为了方 便计算。格网划分后，以落入每个格网内的目标建立索引，这样检索过程只需考察每个 格网，检索的区域大大减小。 根据空间数据的特点，我们可以将空间目标数据分为点、线、面等类型。为了在索 引结构中定位这些类型的数据，为每一个空间数据定义其索引值、目标分类码、坐标值 等属性的数据结构。线结构的属性中包含所有点的集合，面结构属性还应包含其在数组 中的索引号。在数据查询过程中，根据数据对象的坐标值等信息计算其所在格网的行号 和列号，从而达到定位对象的目的。 1 1 山东师范大学硕士学位论文 基于格网划分的空间索引技术在实际生产操作中应用广泛，因为它简单、易行，又 能起到很好的效果；在数据量不是很大，不需要设计像r 树或四叉树那样很复杂的索 引结构时，格网索引不失为一种较好的选择。 1 4 研究内容与章节安排 在空间数据挖掘领域，空间数据挖掘任务所面临的空间数据具有数据量大、数据结 构复杂并且在现实世界中常常具有障碍约束等特点。针对这些问题，本文主要做了如下 工作： 1 研究基于密度的各种空间聚类算法，并分析现有算法的优缺点。对d b s c a n 算法进行改进，改变其寻找核心点的方式，以提高聚类算法的效率； 2 对空间数据库中障碍物的有效处理，是当前研究的一个方向，并且也是大多数 实际应用所面临的问题。针对这种需求，在数学形态学聚类算法的基础上，提出了一种 带障碍约束的空间聚类算法； 3 对带障碍约束的聚类算法进行数据实验，证明算法的有效性。 本文的章节安排如下： 第一章：绪论，简要介绍了选题的意义、研究现状及空间数据库的基础知识； 第二章：首先提出空间数据挖掘的基础知识，然后分别介绍空间数据挖掘的主要方 法、步骤、数据挖掘的体系结构以及数据挖掘的结果表示等方面的问题； 第三章：对空间聚类技术的各方面进行了详细的介绍，主要包括：聚类分析的概念、 主要的应用范围及示例、几种常用的空间聚类算法以及聚类算法当前需要解决的问题： 第四章：对基于密度的空间聚类算法进行深入的研究，将基于密度的空间聚类算法 进行改进，改变其寻找核心点的思想，以提高算法的效率，并给出算法的实现步骤，进 行评价； 第五章：根据目前空间聚类过程中经常存在障碍物的实际情况，结合数学形态学聚 类的基本思想，提出了基于数学形态学的带障碍约束的聚类算法，并对算法进行分析， 实验； 第六章：对本次研究工作的总结，并提出未来研究的努力方向。 1 2 山东师范大学硕士学位论文 2 ，1 基础知识 第二章空间数据挖掘技术 空间数据挖掘，简单地说，就是从空间数据中提取隐含其中、事先未知、潜在有用、 最终可理解的空间或非空间的一般知识规则的过程。具体而言，就是从大量含有噪声、 不确定性的空间数据中，析取人们可信的、新颖的、感兴趣的、隐藏的知识，揭示蕴涵 在数据背后的客观世界的本质规律、内在联系和发展趋势，为技术决策与经营决策提供 不同层次的知识依据p j 。 空间数据挖掘是计算机技术、数据库应用技术和管理决策技术等发展到一定阶段、 多学科交叉的新兴边缘学科，汇集了来自机器学习、模式识别、数据库、统计学、人工 智能以及管理信息系统等各学科的成果【l6 1 7 】。空间数据挖掘方法可以用来理解空间数 据、发现空间数据和非空间数据之间的关系、创建空间知识库、优化查询、组织空间数 据库中的数据以及以简明的形式描述空间数据的一般特征。空间数据挖掘产生的空间知 识主要包括空间的关联关系、特征、分类和聚类。挖掘结果一般表现为一组概念、规则 和模式等形式的集合，是对数据库中的数据属性、模式、频度和对象簇集等的描述。 2 1 1 空间数据挖掘的由来 随着遥感技术、雷达、电视成像、c t 成像以及自动数据采集工具的广泛应用，人 们在空间数据库中收集了大量的空间和非空间的数据，并且空间数据的复杂性显著提 高，己经远远超出了人类的理解能力。为了从空间数据库中得到知识，需要对空间数据 进行分析。二十世纪九十年代中期以前的大部分空间数据分析方法都使用统计方法处理 数值数据【1 6 1 ，这种方法具有很大的局限性。首先，空间数据的数据量正在不断增长， 数据统计方法的效率也越来越低；其次，它忽略了空间对象之间的拓扑关系，得到的结 果是片面的、不真实的，并且这种统计模型只有具有丰富领域知识和统计经验的专家才 能使用。基于以上两点，人类急需探求一种新的数据分析模式，能够更高效、更客观的 分析空间数据，以提供在税收、交通、营业网点选址、环境保护等方面的决策支持。 空间数据库与关系数据库最根本的区别是空间数据库包括两部分：空间对象和有关 这些对象的非空间属性，并且各空间对象之间还存在着拓扑关系。这些特点使得在对空 间数据进行统计分析时，除借鉴传统数据挖掘方法外，还应该考虑空间对象之间的相互 影响，有时要重新设计算法来适应数据的空间特性，以达到令人满意的结果【i 引。 空间数据挖掘是伴随着空间数据获取手段以及存储技术的提高而出现并不断发展 的。同时，人类对生活、生产、环境的智能化要求也是其出现与发展的动力。 山东师范大学硕士学位论文 2 1 2 空间数据挖掘的特点 由于空间数据库存储了空间实体的位置特征、几何特征以及属性特征这三种基础数 据，空间实体之间又具有空间拓扑、空间距离、空间方位这三种关系，所以空间数据库 的分析和计算要比关系数据库复杂，这意味着空间数据挖掘( s d m ) 的方法要比数据 挖掘( d m ) 复杂的多，技术实现也更加困难。s d m 具有如下特点【1 】： 空间数据库的数据量庞大，为了提高数据分析效率，需要建立空间索引结构组 织空间数据； 空间数据挖掘的对象是空间数据库或空间数据仓库，存储的是空间实体的位置、 属性信息以及空间实体之间的拓扑关系信息； 空间数据挖掘粒度为矢量结构的点、线、面、多边形等空间对象，或栅格结构 的像元； 空间对象之间通常具有一定的拓扑关系，空间数据相关度高，在挖掘知识时需 要充分考虑； 空间数据挖掘针对空间数据的特点，增加了尺度维，形成空间数据挖掘的四维 发现状态空间。在尺度维上，表达了空间数据由细至粗的多比例尺或多分辨率的几何变 换过程。尺度越大，观察点越远，比例尺越小，对空间目标表达越概括、越宏观；尺度 越小，相当于观察点越近，比例尺越大，对空间目标表达越精细、越微观。 针对空间数据的复杂性、海量性、多维性等特点，目前对s d m 的研究主要集中于： 在充分考虑空间数据特点的基础上，提高算法的时间效率和空间效率。 2 2 空间数据挖掘的体系结构 空间数据挖掘系统的体系结构可分为三层，数据源、数据挖掘器、用户界面i l9 1 。 数据源是指直接存储在空间数据库或空间数据仓库中的数据，是空间数据挖掘系统 的基础，对空间数据来说，包括位置数据、属性数据以及图形图像。 数据挖掘器是用户根据数据挖掘的目标以及数据量的大小选择的一种或几种数据 挖掘方法，是数据挖掘系统的核心。 。用户界面主要用来进行知识表达，将数据挖掘的结果或获取的知识类型以便于用户 理解和观察的方式展现给用户，是整个数据挖掘系统的出口。 当用户对获取的知识不满意，例如由于数据的选取不够准确导致数据挖掘结果不精 确时，用户可以返回数据选取步骤，重新进行数据挖掘过程。 数据挖掘系统的体系结构如图2 1 所示。 1 4 山东师范大学硕士学位论文 匝虱 区亘h 区匾一 图2 - 1 数据挖掘体系结构 2 3 空间数据挖掘的基本方法 对结果不满意返回 - - | _ t ：# t z = = = = = ：三 空间数据挖掘的任务不同，所选用的方法也不同，主要的空间数据挖掘的方法可分 为如下几类【2 0 , 2 1 ，2 2 】： 1 、统计分析方法 统计分析方法一直是数字型空间数据分析的常用方法，有着较强的理论基础，拥有 大量的算法，可有效地处理数字型数据。该方法着重于空间物体和现象的非空间特性分 析。但该方法对空间数据统计的独立性假设往往难以满足，且难以处理非数值型数据。 当数据不完全或不充分时，统计分析的结果会缺乏实际意义。应用统计方法需要领域知 识和统计知识，一般由具有统计经验的领域专家来完成。 2 、聚类的方法 聚类分析方法是数据挖掘的一种重要的方法，其基本思想是按一定的距离或相似性 测度将数据分成一系列相区分的组，它不需要背景知识而直接发现一些有意义的结构和 模式，类似于机器学习的非监督学习。用聚类分析方法处理属性数据库中的大数据量时， 速度慢且效率低，但处理图形数据库时效率高。聚类是本文的重点研究对象。 3 、归纳的方法 归纳方法是从大量的经验数据中进行概括和综合，归纳出高层次的模式或特征。归 纳方法一般需要背景知识，常以概念树的形式给出。在g i s 中，有属性概念树和空间 1 5 山东师范大学硕士学位论文 关系概念树两类。背景知识由用户提供，在有些情况下也可作为知识发现任务的一部分 自动获取。 4 、空间分析方法 空间分析方法可采用拓扑结构分析、空间缓冲区及距离分析、