（计算机软件与理论专业论文）空间数据挖掘的机理研究——聚类问题算法研究.pdf

空间数据挖掘的机理研究 聚类问题算法研究 研究生签字：4 屯 - _ 研究生签字： 指导教师签字：鸭喈 摘要 空间数据挖掘是指从空间数据库中提取用户感兴趣的空间模式与特征、空间与非空间 数据的普遍关系及其它一些隐含在空间数据中的普遍的数据特征。聚类分析是数据挖掘中 的一种非常重要的技术和方法。空间聚类分析既可以发现隐含在海量数据中的聚类规则， 又可以与其它数据挖掘方法结合使用，发掘更深层次的知识，从而提高数据挖掘的效率和 质量。空间聚类分析是空间数据挖掘的重要研究方向之一。 本文主要工作如下： 1 对空间数据挖掘进行了概述，介绍了空间数据挖掘的理论、方法和研究内容； 2 阐述了聚类的概念，系统而完整地分析和总结了主要的空间数据聚类算法的性能、 优缺点、计算复杂度以及各聚类算法的应用条件； 3 针对d b s c a n 算法i o 开销和内存消耗大的缺点，提出了基于层次合并的密度算 法。该算法减少了d b s c a n 算法中需要查询的点的数量，从而克服了d b s c a n 算法i o 开销和内存消耗大的缺点。算法分析表明该算法对d b s c a n 的改进是有效的。 4 在空间聚类中，最佳聚类数k 求解的关键是构造合适的聚类有效性函数。针对典型 k 一平均算法中的聚类数k 必须是事先给定的确定值，然而，实际中k 很难被精确地确定， 使得该算法对一些实际问题无效的缺点提出距离代价函数作为最佳聚类数的有效性检验 函数，建立了相应的数学模型，并据此提出了一种改进的k 值优化算法，实例进一步验证了 新方法的有效性。 5 提出了一个基于聚类的空间数据挖掘系统的框架，从系统设计目标和系统设计展 开研究，采用模块化设计的思想，将系统设计划分为数据访问、聚类、用户交互和知识库 管理4 个模块；将本文研究的聚类方法集成在一起，为基于聚类的空间数据挖掘方法与应 用提供技术支撑。 关键字：数据挖掘空间数据挖掘聚类分析d b s c a nk 一平均 a t h e o r yr e s e a r c ho ns p a t i a ld a t am i n i n g s t u d yo nc l u s t e r i n ga l g o r i t h m d i s c i p l i n e ：c o m p u t e rs o f t w a r ea n dt h e o r y s t u d e n ts i g n a t ur e ： s u p e r v l s o rs i g n a t u r e ： 一 一- 阳q “魄 ，g i 厶t 儿 v a b s t r a c t s p a t i a ld a t am i n i n g ( s d m ) r e f e r st op i c k i n gu pi n t e r e s t i n gr u l e sf r o ms p a t i a ld a t a b a s e ， s u c ha ss p a t i a lp a t t e r n sa n dc h a r a c t e r i s t i c s ，t h eu n i v e r s a lr e l a t i o n so fs p a t i a la n dn o n - s p a t i a ld a t a a n do t h e ru n i v e r s a l i m p l i c a t e di ns p a t i a ld a t a c l u s t e r i n ga n a l y s i s i sav e r yi m p o r t a n t t e c h n o l o g ya n dm e t h o do fd a t am i n i n ga sw e l la ss p a t i a lc l u s t e r i n ga n a l y s i si s t h em a i n r e s e a r c hf i e l do fs p a t i a ld a t am i n i n g w i t l lt h eh e l po fs p a t i a lc l u s t e r i n ga n a l y t i c a lt o o l s ，n o t o n l yc l u s t e r i n gr u l e sc a nb ee x t r a c t e di nal a r g ec o l u m no fs p a t i a ld a t a b a s e ，b u tw h e nc o m b i n i n g w i t ho t h e rd a t am i n i n gm e t h o d sk n o w l e d g eh i d d e nd e e p l yc a nb ed i s c o v e r e de f f i c i e n t l ya n d e f f e c t i v e l ya sw e l l t h ec o n t r i b u t i o no f t h i st h e s i sh a sb e e nc o n c l u d e da sf o l l o w s 1 s u m m a r i z i n gt h ec o n c e p t i o n so fs p a t i a ld a t am i n i n gi n c l u d i n gt h e o r i e s ，t e c h n o l o g y , m e t h o d sa n dr e s e a r c hc o n t e n t 2 s y s t e m i c a l l ya n a l y z i n ga n ds u m m a r i z i n gd i f f e r e n ts p a t i a lc l u s t e r i n ga l g o r i t h m st h a t h a v eb e e np u b l i s h e di nd o c u m e n t s t h ef i t n e s s ，p e r f o r m a n c e ，a d v a n t a g e sa n dd i s a d v a n t a g e s ， a n dc o m p l e x i t yo fd i f f e r e n ta l g o r i t h m sh a v eb e e nc o m p a r e di nt h ep a p e r 3 t od e a lw i t ht h el i m i t a t i o no fd b s c a nw h i c hi os p e n d i n ga n dm e m o r ye x p a n di sv e r y b i g ，t h ec l u s t e r i n ga l g o r i t h mb a s e dd e n s i t ya n dh i e r a r c h i c a li sp r e s e n t e di nt h i st h e s i s i tg e t s o v e rt h el i m i t a t i o no fd b s c a nb yr e d u c i n gt h en u m b e ro fp o i n t st h a tn e e d e dt ob ef o u n d t h e a n a l y s i sp r o v e st h en e wa l g o r i t h mi se f f e c t i v e 4 i ns p a t i a lc l u s t e r i n g ，t h ek e yf a c t o rt os o l v et h ep r o b l e mo fo p t i m a lc l a s sn u m b e ri st o c o n s t r u c tap r o p e rc l u s t e rv a l i d i t yf u n c t i o n t h ev a l u eo fkm u s tb ec o n f i r m e di na d v a n c et o e x e r tk - m e a n sa l g o r i t h m h o w e v e r , i tc a nn o tb ec l e a r l ya n de a s i l yc o n f i r m e di nf a c tf o ri t s u n c e r t a i n t y t h i sp a p e rr e c o m m e n d sad i s t a n c ec o s tf u n c t i o nb a s e do ne u c l i d e a nd i s t a n c et o c o n f i r mt h eo p t i m a lc l a s sn u m b e r , s e t su pac o r r e s p o n d i n gm a t hm o d e la n dp r o p o s e sa l l i m p r o v e da l g o r i t h mo fkv a l u e r e s u l t sc o m ef r o mt h ee x a m p l ea l s os h o wt h ev a l i d i t yo ft h i s n e w a l g o r i t h m 5 as p a t i a ld a t am i n i n gs y s t e mf r a m ew a si n 仃o d u c e d ，c o n s i s to f2p a r e ：a i ma n dd e s i g n a d o p tm o d u l a r i z a t i o nd e s i g ni d e a , s y s t e md e s i g nw a sd i v i d e di n t o4m o d u l e ：d a t aa c c e s s ， c l u s t e r i n g ，u s e rm u t u a la n dk n o w l e d g em a n a g e m e n t ；t h ec l u s t e r i n gm e t h o dw a si n t e g r a t e da n d s y s t e ms u p p l i e dt e c h n o l o g ys u p p o r tf o rs p a t i a ld a t am i n i n gm e a n sa n da p p l i c a t i o n k e yw o r d s ：d a t am i n i n g ，s p a t i a ld a t am i n i n g ，c l u s t e r i n ga n a l y s i s ，d b s c a n ，k m e a n s 芋何论艾知谚沪：权声明 学位论文知识产权声明 本人完全了解西安工业大学有关保护知谚5j 赴权的规定，即：研究生在校攻读学位期间 学位论文工作的知识产权属于西安工业大学。本人保证毕业离校后，使用学位论文工作成 果或用学位论文工作成果发表论文时署名单位仍然为西安工业大学。大学有权保留送交的 学位论文的复印件，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存学位论文。 学位论文作者签名：砂百 学位论文独创r 刊j 学位论文独创性声明 秉承学校严谨的学风与优良的科学道德，本人卢圩j it # 交的学位论文是我个人在导师 指导下进行的研究工作及取得的研究成果。尽我所矢i l ，除了文中特别加以标注和致谢的地 方外，学位论文中不包含其他人已经发表或撰写过的成粜，不包含本人己申请学位或他人 已申请学位或其他用途使用过的成果。与我一同工作的川志时本研究所做的任何贡献均已 在论文中作了明确的说明并表示了致谢。 学位论文与资料若有不实之处，本人承担一切相火责任。 学位论文作者签名： 指导教师签名 日期： 5 7 1 绪论 1绪论 随着卫星、雷达、红外、光电、电子微成像和其它自动数据获取设备的迅速发展，极 大提高了社会各部门产生、收集、存储和处理数据的能力，日益丰富的空间和非空间数据 存储于空间数据库中，而且由于地学现象的复杂性和地理过程的不确定性，空间数据的数 量、大小、复杂性都在飞速增长，远远超出了人们的解译能力。作为经验和教训的积累， 空间数据库无异于一个巨大的宝藏，当其积累到一定程度时，必然会反映出某些规律。但 是，目前的空间数据库系统可以高效地实现数据的录入、修改、统计、查询等功能，却无 法发现隐藏在空间数据背后的关系、规则和发展趋势等知识，这就导致了“空间数据丰富， 但是空间知识贫乏”! 因此，从空间数据库中自动挖掘知识，寻找空间数据库中不明确的 隐含知识、空问关系或其它模式就显得越来越重要n _ ，。 1 1 空间数据挖掘的特点 空间数据挖掘( s p a t i a ld a t am i n i n g ，s d m ) 是指从空间数据库中抽取隐含的知识、空间 关系或非显式地存储在空间数据库中有意义的特征或模式d 1 。这种技术可用于发现空间数 据与非空间数据间的关系、构建空间知识库、优化查询、重组空间数据库和获取简明的总 体特征等方面，它在g i s 、遥感、图像数据库、医疗影像处理、机器人导航等领域具有广 阔的应用前景。 作为数据挖掘技术在空间信息领域上的应用，由于空间数据的复杂性，空间数据挖掘 不同于一般的事务数据挖掘，它具有如下特点： 传统数据挖掘处理的是数字和类别，而空间数据挖掘处理的则是一些更为复杂的 数据类型，例如：点、线、多边形等对象； 传统数据挖掘通常具有显式的输入，而空间数据挖掘的输入则常常是隐式的； 传统数据挖掘以数据样品独立作为假设前提，而在空间数据挖掘中空间数据样品 是高度自相关的。 1 2 空间数据挖掘的体系结构 空间数据挖掘系统可以分为三层结构，如图1 1 所示。 第一层是数据源，指利用空间数据库或数据仓库管理系统提供的索引、查询优化等功 能获取和提炼与问题领域相关的数据，或直接利用存储在空间数据立方体中的数据，这些 数据可称为数据挖掘的数据源或信息库。在这个过程中，用户直接通过空间数据库( 数据 仓库) 管理工具交互地选取与任务相关的数据，并将查询和检索的结果进行必要的可视化 分析，多次反复，提炼出与问题领域有关的数据，或通过空间数据立方体的聚集、上钻、 西安工业大学硕士学位论文 下翻、切块、旋转等分析操作，抽取与问题领域有关数据，然后再丌始进行数据挖掘和知 识发现过程。 图1 1 空间数据挖掘的体系结构 第二层是挖掘器，利用空间数据挖掘系统中的各种数据挖掘方法分析被提取的数据， 一般采用交互方式，由用户根据问题的类型以及数据的类型和规模，选用合适的数据挖掘 方法，但对于某些特定的专门的数据挖掘系统，可采用系统自动地选用挖掘方法的方式。 第三层是用户界面，使用多种方式( 如可视化工具) 将获取的信息和发现的知识以便于 用户理解和观察的方式反映给用户，用户对发现的知识进行分析和评价，并将知识提供给 空间决策支持使用，或将有用的知识存入领域知识库内。在整个数据挖掘过程中，用户能 够控制每一步。 一般说来，数据控掘的多个步骤相互连接，需要反复进行人机交互，才能得到最终满 意的结果。 1 3 空间数据挖掘的基本过程 空间数据挖掘和知识发现技术的目标是把大量的原始数据转换成有价值的知识，用于 描述过去的发展规律和预测未来趋势，它可以看成是决策支持过程。同空间数据库管理系 统检索和查询出的信息相比，前者挖掘出的知识是隐含、精练和高水平的。数据、信息、 知识构成了一种金字塔形结构。如图1 2 表示了空间数据挖掘和知识发现的过程，该过程 可分为由三个主要阶段组成：数据准备、数据挖掘、结果评价与表达【4 1 。 具体可以分为下面九个步骤： 数据准备：了解空间数据挖掘( s d m ) 相关领域的有关情况，熟悉有关的背景知识， 弄清楚用户的需求； 数据选择：根据用户的要求从空间数据库中提取与空间数据挖掘相关的数据，空间 2 用户界面 挖掘器 数据源 西安工业大学硕士学位论文 数据挖掘将主要从这些数据中进行知识提取。其中，会利j j 一蝗数据库操作对数据进行处 理： 数据预处理：对上阶段产生的数据进行再加工，进f ，数据的完整性与一致性检查， 对其中的噪音数据进行处理。对丢失数据利用统计方法填补： 臣受妇 乃， 知识 图1 2 空i 司数据挖掘的基本过程 数据压缩：对经过预处理的数据，根据知识发现的任务对数据进行再处理：主要 通过投影减少数据量； 确定空间数据挖掘目标：对于空间数据挖掘的不同要求，会在具体的知识发现过 程中采用不同的知识发现算法，所以要确定空间数据挖掘发现何种类型知识； j 确定知识发现算法：根据确定的任务，选择合适的知识发现算法，包括选取合适 的模型和参数；并使得知识发现算法和整个s d m 的评判标准相一致； 数据挖掘：运用选定的知识发现算法，从数据中提取用户所需要的知识，这些知 识可用一种特定的方式表示或使用一些常用的表示方式，如产生规则等； 模式解释：对发现的模式进行解释。有时，为了取得更有效的知识，可能返回到 前面的步骤进行反复提取； 知识评价：将发现的知识以用户能理解的方式呈现给用户。这期间也包括对知识 的一致性检查，以确信本次发现的知识不与以前发现的知识相抵触。 1 4 空间数据挖掘可发现的知识类型 利用空间数据挖掘可以发现大量地理信息中所隐含的知识或规则。主要有以下几种n 6 】 普遍的几何知识( g e n e r a lg e o m e t r i ck n o w l e d g e ) ：指某类空间对象的数量、大小、 形态特征等普遍的几何特征，可以计算几何特征量的最小值、最大值、均值、方差、众数 3 两安工业大学硕士学位论文 等，还可得到特征量的卣方图。在此基础上根据背景知识归纳出泛化的普遍几何知识。 空间分布规律( s p a t i a ld i s t r i b u t i o nr e g u l a r i t i e s ) ：指对象在地理空间的分布规律， 可分为垂直向、水平向以及垂随向和水平向的联合分布规律。垂直向分布指地物沿高程带 的分布，如植被沿高程带分和规律、植被沿坡度坡向分布规律等：水平向分布指地物在平 面区域的分布规律，如不同区域农作物的差异、公用设施的城乡差异等；垂直向和水平向 的联合分布即不同的区域中地物沿高程分布规律。 空间关联规则( s p a t i a la s s o c i a t i o nr u l e s ) ：指空间对象间相邻、相连、共生、包含 等关联规则，如村落与道路相连，道路与河流的交叉处是桥梁等。 空间特征规则( s p a t i a lc h a r a c t e r i s t i cr u l e s ) ：指某类或几类空间对象的几何和属 性的普遍特征，即对共性的描述。普遍的几何知识属于空间特征规则的一类，由于它在遥 感影像解译中具有重要作用，所以分离出来单独作为一类知识。 空间区分规则( s p a t i a ld i s c r i m i n a t er u l e s ) ：指两类或多类对象问几何或属性的不 同特征，即可以区分不同类型对象的特征。 空间分类回归规则( s p a t i a lc l a s s i f i c a t i o nr u l e s s p a t i a lr e g r e s s i o nr u l e s ) ：空间 分类规则根据空间区分规则把数据集的数据映射到某个给定的类上，用于数据预测，其预 测值是离散的；空间回归规则也是一种分类器，其预测值是连续的。二者常表现为一棵决 策树，根据数值从树根开始搜索，沿着数据满足的分支往上，到树叶就能确定类别。空间 分类或回归的规则是普及知识，实质是对给定对象数据集的抽象和概括，可用宏元组表示。 空间聚类函数依赖规则( s p a t i a lc l u s t e r i n gr u l e s s p a t i a lf u n c t i o n a ld e p e n d e n c y r u l e s ) ：空间聚类把特征相近的空间实体数据划分到不同的组中，组间的差别尽可能大， 组内的差别尽可能小，可用于空间对象的概括和综合。与分类规则不同，聚类前并不知道 将要划分几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。空间函数依赖 规则旨在发现空间对象属性间的函数关系，挖掘知识用以属性名为变量的数学方程来表 示。 空间序列规i 贝j j ( s p a t i a l s e r i a lr u l e s ) ：基于时序，根据空间对象随时间变化的趋势 预测将来的值。为了发现序列规则，不仅需要知道空间事件是否发生，而且需要确定事件 发生的时间。 空间演变规i 贝j j ( s p a t i a le v o l u t i o nr u l e s ) ：指空间对象依时间的变化规则，即哪些对 象易变及怎么变，哪些对象固定不变。如果g i s 数据库是时空数据库或者g i s 数据库中 存有同一地区多个时间数据的快, , 昭, , ( s n a p s h o t ) ，则可以发现空间演变规则。 面向对象的知识( o b j e c to r i e n t e dk n o w l e d g e ) ：指某些复杂空间对象的子类构成及 其普遍特征的知识。 它们可用特征表、谓词逻辑、产生式规则、语义网络、面向对象方法和可视化等方法 表达，应根据不同的应用选取不同的表达形式，并且各种表达形式间可以相互转换。 4 西安工业大学硕士学位论文 1 5 空间数据挖掘的方法 空间数据挖掘是多学科和多种技术交叉综合的新领域，其挖掘方法以人工智能、专家 系统、机器学习、数据库和统计等成熟技术为基础。主要空间数据挖掘方法有2 | ： ( 1 ) 空间分析方法：利用g i s 的各种空间分析模型和空间操作对空间数据库中的数 据进行深加工，从而产生新的信息和知识。常用的空间分析方法有综合属性数据分析、拓 扑分析、缓冲区分析、距离分析、叠置分析、网络分析、地形分析、趋势面分析、预测分 析等，可发现目标在空间上的相连、相邻和共生等关联规则，或发现目标之间的最短路径、 最优路径等辅助决策的知识。 ( 2 ) 空间聚类方法：空| - 日j 聚类分析是要将空间数据库中的对象按照某些特征划分为不 同的有意义的子类，同一子类中的对象具有高度相似的某种特征，并与不同子类的特征具 有明显的差异。采用聚类分析的优点在于：想获取的结构或簇可以直接从数据中找到，不 需要任何背景知识。目前已经提出了五种空间聚类方法：基于划分的方法、基于层次的方 法、基于密度的方法、基于网格的方法和基于模型的方法。基于划分的方法包括k 一平均 法，k 一中心点法和e m 聚类法。它们都是采用一种迭代的重定位技术，尝试通过对象在划 分间移动来改进聚类效果。由于这类方法适用于发现大小相近的球状簇，故常用在设施选 址等应用中。基于层次的方法固定数据对象的关系，只是对对象集合进行分解。根据层次 的分解方式，这类方法可分为凝聚和分裂两种，b i r c h ，c u r e 和c h a m e l e o n 是上述方法的改 进。基于密度的方法的主要思想是：对给定类中的每个数据点，在一个给定范围的区域中 必须包含超过某个阈值的数据点，才继续聚类。它可以用来发现任意形状的簇，过滤“噪 声 。代表性的方法有：d b s c a n 、o p t i c s 、d e n c l u e 。基于网格的方法把对象空间化为有 限数据的单元，形成一个网格结构。该方法处理速度快，处理时间独立于数据对象的数目。 该类方法包括：s t i n g 、s t i n g + 、w a v e c l u s t e r 和c l i q u e 阳1 。基于模型的方法为每个类假定了 一个模型，寻找数据对给定模型的最佳拟合。这样的方法经常是基于这样的假设：数据是 根据潜在的概率分布生成的。一个基于模型的算法可能通过构建反映数据点空间分布的密 度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑噪声数据和孤立 点，从而产生健壮的聚类方法。 ( 3 ) 空间分类分析：是根据对象的属性值确定对象属于一个给定的类属集中的某个 类。在空间分类分析中，不仅要考虑对象的非空间属性，还要考虑它与数据库中其他对象 的空间关系。通常的分类分析方法是使用决策树，这种方法能处理数值和符号数据，而且 结果可以表达成规则的形式，便于决策制定。k o p e r s k i 脚等人提出的算法综合考虑了多种 方法的优劣，具有代表性。这种算法把描述空间对象特征的信息划分为四种类型：非空间 属性、具有非空间数值又与空间相关的属性、空间谓词、空间函数。其基本思想是：通过 相关分析( r e l e v a n t a n a l y s i s ) ，建立描述所有空间对象的谓词集，并基于概念层次进行归纳， 从而找出与分类分析任务有关的谓词、函数和属性；在进一步求精后，生成一棵二叉决策 5 两安工业大学硕士学位论文 树。在建立谓词集时，将空i 日j 对象和最近的邻接对象的属性值相比较，判断它们是否属于 同一类，并确定是否与任务相关；在构造决策树时，要考虑目标对象的一个缓冲区内所有 对象的非空间属性值的总和，缓冲区代表的区域对该分类对象的类标志属性具有重要影 响，缓冲区的大小与形状对算法的效率和效果也十分关键口，。 ( 4 ) 数学统计方法：数学统计方法一般是首先建立一个数学模型或统计模型，然后根 据这种模型提取出有关的知识。例如，可由训练数据建立一个网，然后根据网的一些参数 及联系权值提取出相关的知识。数学统计方法一直是分析空间数据的常用方法，有着较强 的理论基础，拥有大量的算法，可有效地处理数字型数据。这类方法有时需要数据满足统 计不相关假设，但很多情况下这种假设在空间数据库中难以满足。另外，统计方法难以处 理字符型数据。应用统计方法需要有领域知识和统计知识，一般由具有统计经验的领域专 家来完成。 ( 5 ) 归纳学习方法：归纳学习方法是从大量的经验数据中归纳抽取一般的规则和模 式，其大部分算法来源于机器学习领域，归纳学习的算法有很多，如m i c h a s k i 等的 a q l l 、a q l 5 ，洪家荣等的a e l 、a e 9 ，h u n t 的c l s ，q u i n l a n 的i d 3 、c 5 0 等，其 中最著名的是q u i n l a n 提出的c 5 0 决策树算法。 ( 6 ) 探测性的数据分析方法：李德仁院士【i 】、邸凯昌博士【2 l 等提出了探测性的数据分 析( 简称e d a ) 。e d a 采用动态统计图形和动态链接窗口技术将数据及统计特征显示出 来，可发现数据中非直观的数据特征及异常数据。e d a 与空间分析相结合，构成探测性 空间分析( e x p l o r a t o r ys p a t i a la n a l y s i s ，简称e s a ) 。e d a 和e s a 技术在数据挖掘中用于 选取与问题领域相关的数据子集，并可初步发现隐含在数据中的某些特征和规律。 ( 7 ) 粗集方法：粗集理论是波兰华沙大学z p a w l a k 教授在1 9 8 2 年提出的一种智能 数据决策分析工具，被广泛研究并应用于不精确、不确定、不完全的信息的分类分析和知 识获取。粗集理论为空间数据的属性分析和知识发现开辟了一条新途径，可用于空间数据 库属性表的一致性分析、属性的重要性、属性依赖、属性表简化、最小决策和分类算法生 成等。粗集理论与其他知识发现算法相结合可以在空间数据库中数据不确定的情况下获取 多种知识。 ( 8 ) 云理论：云理论是由李德毅院士为解决模糊集在隶属度概念上的不确定性而提出 的一种新理论，包括云模型、虚云、云运算、云变换和不确定性推理等主要内容。运用云 理论进行空间数据挖掘，可进行概念和知识的表达、定量和定性的转化、概念的综合与分 解、从数据中生成概念和概念层次结构、不确定性推理和预测等。 ( 9 ) 空间特征和趋势探测方法：这是e s t e r 等人在第4 届k d d 国际研讨会( 1 9 9 8 ) 上提出的基于邻域i 至t ( n e i g h b o r h o o dg r a p h s ) 和邻域路径( n e i g h b o r h o o dp a t h ) 概念的挖掘算 法。e s t e r 等将一个空间特征定义为空间数据库中具有空间非空间性质的目标对象集，以 非空间属性值出现的相对频率和不同空间对象出现的相对频率( 目标对象集相对于整个数 据库) 作为感兴趣的性质，从空间目标集合经过它的相邻扩展后的集合中，发现相对频率 6 两安t 业大学硕士学位论文 的明显不同，以此提取空f n j 规则；空间趋势探测挖掘从一个开始点出发，发现一个或多个 非空间性质的变化规律。 ( 1 0 ) 数字地图图像分析和模式识别方法：空间数据库( 数据仓库) 中含有大量的图形 图像数据，一些图像分析和模式识别方法可直接用于挖掘数据和发现知识，或作为其他挖 掘方法的预处理方法。用于图像分析和模式识别的方法主要有：决策树( d e c i s i o nt r e e ) 方 法、神经元网络( a x t i f i c i a in e u r a ln e t w o r k ) 方法、数学形态学方法、图论方法等。 ( 1 1 ) 可视化方法：可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖 析更清楚。例如，把数据库中的多维数据变成多种图形，这对揭示数据的状况、内在本质 及规律性起到了很强的作用。当显示s d m 发现的结果时，将地图同时显示作为背景，一 方面能够显示其知识特征的分布规律，另一方面也可对挖掘出的结果进行可视化解释，从 而达到最佳的分析效果。可视化技术使用户看到数据处理的全过程、监测并控制数据分析 过程。 为了发现某类知识，常常要综合运用这些方法。数据挖掘方法还要与常规的数据库技 术充分结合。数据挖掘利用的技术越多，得出的结果精确性就越高。 1 6 论文的组织结构 本文主要目的是研究空间数据挖掘中空间聚类相关的理论、方法和应用。本文主要内 容如下： 第一章是绪论。对空间数据挖掘进行了概述，简要介绍了空间数据挖掘的理论、方法 和研究内容； 第二章是空间数据聚类分析概述。阐述了聚类的概念，系统而完整地分析和总结了主 要的空间数据聚类算法的性能、优缺点、计算复杂度以及各聚类算法的应用条件； 第三章对基于密度的d b s c a n 空间聚类算法进行研究。针对d b s c a n 算法i o 开销 和内存消耗大的缺陷，提出了基于层次合并的密度算法。该算法主要思想是：选择数据库 中无任何标识的点进行核心点判断，围绕核心点生成源簇，再对含有公共点的源簇不断合 并，从而得到最终结果。通过上述思想，该算法减少了d b s c a n 算法中需要查询的点的 数量，从而克服了d b s c a _ n 算法i o 开销和内存消耗大的缺陷。算法分析表明该算法对 d b s c a n 的改进是有效的。 第四章对k 一平均算法进行研究。在空间聚类中，最佳聚类数k 求解的关键是构造合 适的聚类有效性函数。针对典型k 一平均算法中的聚类数k 必须是事先给定的确定值，然而， 实际中k 很难被精确地确定，使得该算法对一些实际问题无效的缺点提出距离代价函数 作为最佳聚类数的有效性检验函数，建立了相应的数学模型，并据此提出了一种改进的k 值优化算法，实例结果进一步验证了新方法的有效性。 第五章是空间数据挖掘系统的设计。提出了一个基于聚类的空间数据挖掘系统的框 架，从系统设计目标和系统设计展开研究，采用模块化设计的思想，将系统设计划分为数 7 州安：业火学硕十学位论文 据访问、聚类、用户交互和知识库管理4 个模块；将本文研究的聚类方法集成在一起，为 基于聚类的空间数据挖掘方法与应用提供技术支撑。 第六章是本文的总结，以及对该领域课题的未来研究计划。 8 2 空间数拚：聚类分析 2 空间数据聚类分析 人类认识世界的一种重要的方法是将认识对象进行分类，比如有关世界的时间进程的 研究就形成了历史，而有关世界空间地域的研究则形成了地理学。又如在生物学中，为了 研究生物的演变，需要对生物进行分类，生物学家根据各种生物的特征，将它们归属于不 同的界、门、纲、目、科、属、种之中。为了认识客观物质世界，人们将自然学科分成很 多学科。事实上，分门别类地对事物进行研究，要远比在一个混杂多变的集合中更清晰、 明了和细致，这是由于同一类事物会具有更多的近似特性。 通常，人们可以凭经验和专业知识来实现分类。而聚类分析作为一种定量的方法，将 从数据分析的角度，给出一个更为准确、细致的分类工具。本章重点研究空间聚类分析的 相关内容。 2 1 空间聚类的数学描述 聚类分析是数据挖掘中一种非常重要的技术和方法，目前已经广泛应用于包括模式识 别、数据分析、图像处理、市场分析等领域。 空间聚类是将一组空间数据对象的集合分组成为由类似的对象组成的多个类的过程。 由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其 他簇中的对象相异。 在聚类定义和聚类过程中，相似性标准是一个非常重要的因素。成员间的相似性决定 了聚类结果，因此，相似性标准是聚类算法最本质的特征之一。相似性有两方面的涵义， 一是数据与数据之间的相似性，即以单个数据间的相似性决定聚类，二是数据集与数据集 之间的相似性，即通过对数据集的相似性做出判断从而得到最终的结果。 相似性标准一般可分为三类：分别是基于距离的，基于密度的和基于联结的。前两类 一般用于欧几里德数据空间，基于联结的标准则可以应用于各类空间。通常对聚类算法的 分类也是基于这个标准而进行的。 2 1 1 空间聚类的数学描述 为了便于后面的讨论，本节首先给出空间聚类的数学描述。 给定r 空间中的1 1 个对象集x = x ，f = 1 , 2 ，n ，其中x i 为d 维模式向量。聚类问 题就是要找到一个y o j 分c = c - ，c ：，c k ，将r 1 个对象划分为k 个组，满足： i x ；uc j - i q 囝 u = 1 , 2 ，七) 9 两安i ：业人学硕士学位论文 gnc j = 0( f ，j = 1 , 2 ，七；f - ，) 并且使得总的类内离散度和 七 = x a k ，k 是子聚类数目。当k 接近n 时，计算复杂度是o ( n 2 ) 。 b i r c h 算法的优点：局部性：每个聚类决策过程不需要扫描所有对象或所有存在 的聚类。使用对象的自然封闭性( c l o s e n e s so f p o i n t s ) 特征聚类，在聚类过程中可增量维护 树结构；非均匀性：注意到对象的分布是不均匀的，不同对象对于聚类言其重要性是不 一样的。对象分布稠密区域作为单个聚类统一处理，稀疏区域对象作为立点处理；可伸 缩性：充分利用有限内存空间来生成高精度聚类，并尽可能减少i o 开销，因此其运行时 间具有线性可伸缩性；可加性：是一种增量方法，不需要预先将数据集全部读入( 可分 批读入) ，且仅需扫描数据集一次；抗噪性：不易受“噪音”数据的影响；并行性： 其体系结构适合使用并行算法来提高执行效率，可利用算法执行过程中得到的数据集信息 来动态调整参数改善性能。 b i r c h 算法的不足表现在：初始单遍扫描后，算法使用基于中心点方法来形成聚 类，当聚类的形状和尺寸不同时会产生问题。位于大聚类边缘的对象也许更靠近邻近的较 小聚类，会导致属于大聚类的对象被分配给较小聚类，导致聚类质量的下降：基于中心 点聚类趋向于形成球状聚类，尽管多遍扫描可以解决这个向题，能够发现任意形状的聚类， 但多遍扫描导致算法效率的下降；算法与数据处理顺序有关；需要预先设置许多参数 值；算法依赖矢量计算，仅能在笛卡尔坐标空间中使用。 2 ) c u r e 算法：c u r e ( c l u s t e r i n gu s i n gi 也p r e s e n t a t i v e s ) 也是针对大型数据库而设计 的聚类算法，不过该算法采取了介于基于中心点和基于所有对象聚类算法之间的中间策 略，选择固定数目的具有代表性的对象代表一个簇，这些代表对象较好地描述了簇的形状 和尺寸。然后，使用预先定义的收缩因子口控制，将这些代表对象朝簇中心收缩。调节收 缩因子口可以使c u r e 针对不同类型的簇聚类。当o = 1 时c u r e 算法与基于中心点算法 类似，当a = 0 时c u r e 与基于所有对象聚类算法类似。最后，利用收缩后的代表点的位 置来判断两个簇是否相似，如果两个簇的代表点对具有最小距离，则合并这两个簇。如此， 1 6 西安工业大学硕士学位论文 与普通凝聚层次聚类算法一样，继续合并簇，直至只剩下k 个簇为止。 为了使算法能适用于大型数据库海量数据集的聚类，c u r e 采取了两类技术。其一是 随机采样技术。与b i r c h 采用的预处理技术不同，c u r e 采用随机采样技术从数据库中 随机选择定数目的对象聚类，而不是针对整个数据集聚类。使用随机采样技术一方面聚 类对象数显著减少，适合将数据装入内存进行处理，减少了算法的运行时间。另一方面， 随机采样技术过滤掉大部分孤立点，并进一步拉大了孤立点白j 的差异度，提高了聚类结果 的质量。给出了在最大概率地减少簇丢失条件下，采样样本大小的计算方法。其二是分区 聚类技术。将随机采样得到的样本空间划分为p 个区域，每个区域包含n p 个对象，n 是 样本数。然后针对每个区域聚类，直到聚类个数减至n ( p q ) ，q l 为止。当所有区域聚类 完成后，针对所有区域的p x n p q - - i l q 个部分聚类( p a r t i a lc l u s t e r s ，与b i r c h 算法的子聚 类概念类似) 进行第二遍聚类得到最终结果。这种分区聚类技术与b i r c h 的预处理阶段 的预聚类思想相似，只是b i r c h 针对所有对象使用增量和近似聚类算法，而c u r e 只针 对区域中随机采样得到的代表对象使用层次聚类算法。使用分区聚类技术一方面减少算法 型+ 三 执行时间为原来的朋g 倍。另一方面，输入聚类算法的数据集可以装入内存进行计 算。 c u r e 算法在多处对孤立点进行了处理。除了采样技术过滤掉大部分孤立点，且进一 步拉大了孤立点间的差异度外，通过对凝聚层次聚类算法的观察可知，孤立点通常与其它 对象距离较远，与其它对象合并机会较少，簇尺寸增长缓慢。因此，可以采取一种由两阶 段组成的剔除孤立点的策略。第一阶段，将增长缓慢的簇视为孤立点。当算法执行一段时 间后，将包含对象数少( 例如，1 或2 个对象) 的簇视为孤立点。第二阶段，当聚类数接近 k 时，将包含聚类数较少的簇视为孤立点。 此外，算法最后使用多个代表对象，而不是b i r c h 算法中的一个中心对象，度量簇间 相似性，分配所有其它对象到具体簇中。克服了b i r c h 算法分配对象阶段易造成分裂非球 状簇和尺寸不一致簇的弊端。 c u r e 算法最坏情况下的时间复杂度是o ( n 21 0 9n ) 。n 是随机采样对象个数，而不是数 据集对象数n 。对低维数据集，时间复杂度减少为0 ( n 2 ) 。由于算法采用的堆结构和k - d 树结构需要线性存储空间，算法的空间复杂度为0 ( n ) 。 c u r e 算法的优点：借助代表对象的分布特性，算法可以发现任意形状的聚类，也 可以针对簇大小不一致数据集聚类：采用随机采样和分区聚类技术，算法能高效处理大 数据集的聚类问题：随机采样和其它孤立点剔除技术结合，使得算法不受孤立点影响； 即使簇的形状是非球状的，簇间尺寸差异很大，使用代表点分配对象，可以将所有待分 配对象重分配至正确的簇中。 c u r e 算法的缺点表现在：需要确定收缩因子、代表点数、分区数和随机采样尺寸 的数值。尽管算法给出了计算随机采样尺寸大小的方法，但收缩因子给多大合适? 分区数 1 7 西安工业大学硕士学f 节论文 设胃为多少，算法效率最高? 代表点数为多少时聚类结粜质量更好? c u r e 没有给出计算 这些参数的理想方法。而且簇的尺寸不同，仍使用同样数目代表点来表示是否合理，也值 得进一步研究：算法没有考虑不同簇之间的个体差异，将所有簇的分布模式视为统一的、 不变的。在这种前提下选择合并的簇，可能导致不正确的结果。 3 ) c h a m e l e o n 算法：c h a m e l e o n 算法是在分析许多层次聚类算法存在问题的基础上 提出来的。其特点表现在判断子聚类的相似性时既考虑了子聚类之间的互连性，又考虑了 子聚类之间的近似度，并提出了综合( 包含簇内部分布特性的) 互连性与近似度度量的动态 模型。 c h a m e l e o n 基于k 一最近邻居图方法对数据集建模。k 最近邻居图的每个顶点表示一个 对象，如果两个对象彼此是对方的k 一最近邻居，则两点之间存在一条边。数据集中每个 簇对应于图的一个子图。使用k 一最近邻居图表示数据集的优点是：彼此远离的对象， 在图中是完全断开的；对象与邻居之间半径值由分布区域中对象分布的密度动态控制， 在对象稠密区域，半径值小，反之半径值大，实现了动态邻居的特性。与d b s c a n 的密度 算法相比，克服了d b s c a n 中邻居半径固定不变的不足，使得到的聚类更自然；区域的 密度作为边的权重被记