（计算机软件与理论专业论文）空间数据挖掘的聚类方法与应用.pdf

摘要摘要数据挖掘涉及到数据库、模式识别、神经网络、统计学、计算智能等相关技术，是当今国际上研究热点之一。空间数据挖掘是数据挖掘研究的一个重要研究方向，是从空间数据库中识别或提取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。聚类是数据挖掘中的一种非常重要的技术和方法。空间聚类分析既可以发现隐含在海量数据中的聚类规则，又可以与其它数据挖掘方法结合使用，发掘更深层次的知识，从而提高数据挖掘的效率和质量。空间聚类分析是空间数据挖掘的重要研究方向之一。本文主要工作如下：1 对空间数据挖掘进行了概述，简要介绍了空间数据挖掘的理论、方法和研究内容、发展趋势及方向，并指出当前空间数据挖掘技术中尚需解决的问题；2 阐述了聚类的概念，系统而完整地分析和总结了主要的空间数据聚类算法的性能、优缺点、计算复杂度以及各聚类算法的应用条件；3 在数据挖掘应用方面，电予科技大学计算智能实验室( c i l a b ) 数据挖掘小组研究开发了基于w e b 的数据挖掘服务系统一m i n e r o n w e b ，提供在线的数据挖掘服务。本文介绍了m i n e r o n w e b 的系统功能、特点、体系结构，详细地分析和讨论了e j b 服务端、w e b 应用服务端的预处理模块的具体设计和实现过程；4 成功地设计和实现了m i n e r o n w e b 系统的e j b 服务端( 系统核心模块) ，用于管理数据挖掘的数据对象和算法对象，完成算法运算。设计相关功能接口并具体实现，将接口提供给w e b 服务端；5 成功地设计和实现了w e b 应用服务的数据预处理模块，集成了一些常用的预处理算法，提供数据预处理的功能。解决了j s p 页面中算法项的树型显示问题；6 针对高维复杂的空间数值数据，本文仔细分析了基于g h s o m 网络的聚类算法，对自组织训练学习算法进行了优化，一定程度上提高了网络迭代训练的速度。详细阐述了该算法的实现，并将其集成到摘要m i n e r o n w e b 系统中，对聚类的结果进行了可视化描述。关键词：空间数据，数据挖掘，聚类分析，g h s o m ，j 2 e e ，s t r u t si ia b s t r a c ta b s t r a c td a t am i n i n gh a sb e c o m ea ni n c r e a s i n g l yp o p u l a rs u b je c t ，w h i c hi n v o l v e sl o t so fs c i e n t i f i cd o m a i n sa n dt e c h n o l o g i e ss u c ha sd a t a b a s e ，p a r t e r nr e c o g n i t i o n ，n e u r a ln e t w o r ka n dc o m p u t a t i o n a li n t e l l i g e n c e s p a t i a ld a t am i n i n gi so n er e s e a r c hf i e l do fd a t am i n i n g ，w h i c hc a nd i s c o v e re f f e c t i v e ，n o v e l ，i n v a l u a b l ea n du n d e r s t a n d a b l ek n o w l e d g eo rr u l e sf r o ms p a t i a ld a t a b a s e c l u s t e r i n gi sav e r yi m p o r t a n tt 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 isi st h em a i nr 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 ht 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 to 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 gw 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 de 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 ft h i sp a p e rh 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 s ，r e s e a r c hc o n t e n ta n dd e v e l o p m e n tt e n d e n c y b e s i d e s ，p o i n t i n go u ts o m e u n f a t h o m e dp r o b l e m so fs p a t i a ld a t am i n i n g 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 th a v e b 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 h ew e b b a s e dd a t am i n i n gs e r v i c es y s t e m ( m i n e r o n w e b ) i sar es e a r c ha c h i e v e m e n to fd a t am i n i n gg r o u pi nc o m p u t a t i o n a li n t e l l i g e n c el a b o r a t o r y ( c l l a b ) ，w h i c hc a np r o v i d eo n l i n ed a t am i n i n gs e r v i c e s t h i sd i s s e r t a t i o nd e s c r i b e dt h ef u n c t i o n s ，f e a t u r e s ，a n ds y s t e mf r a m e w o r ko fm i n e r o n w e ba n dd i s c u s s e dt h ed e t a i ld e s i g ni ns e r v i c es i t eo fe j ba n dw e ba p p l i c a t i o n s 4 s u c c e ss f u l l yd e s i g n e da n di m p l e m e n t e dt h ee j bs e r v i c es i t ea sl t ta b s t r a c ts y s t e mc o r em o d u l et om a n a g et h ed a t ao b j c o t sa n da l g o r i t h mo b j e c t so fd a t am i n i n ga n do p e r a t et h e s ea l g o r i t h m s d e s i g na n di m p l e m e n tr e l a t i v ei n t e r f a c e st ow e bs e r v i c es i t e 5 s u c c e s s f u l l yd e s i g n e da n di m p l e m e n t e dt h ep r e p r o c e s s i n gm o d u l ea so n em o d u l eo ft h ew e bs e r v i c es i t e ，w h i c hi n t e g r a t e dm a n yp r e p r o c e s 8 i n ga l g o r i t h m st op r o v i d et h ef u n c t i o no fd a t ap r e p r o c e s s t h ep r o b l e mo fd i s p l a y i n ga l g o r i t h mi t e m si nat r e es t r u c t u r ei nj s ph a sb e e ns o l v e d 6 f o rh i g h - d i m e n s i o na n dc o m p l e xn u m e r i cs p a t i a ld a t a ，w ea n a l y z e dt h eg h s o ma l g o r i t h ma n do p t i m i z e dt h es e l f - o r g a n i z i n gm a pa l g o r i t h mt oi m p r o v et h es p e e do fc l u s t e r i n gp h a s e b e s i d e s ，t h er e a l i z i n gp r o c e d u r eo ft h i sa l g o r i t h mw a sd e s c r i b e di nd e t a i l t h e n ，w ei n t e g r a t e di ti n t om i n e r o n w e bt og e tav i s u a lc l u s t e r i n gr e s u l t k e y w o r d s ：s p a t i a ld a t a , d 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 ，g h s o m ，j 2 e e ，s t r u t s i v独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工，作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：熬强! 渔娅日期：却f 年f 月ge l关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后应遵守此规定)；一签名：莲妞盥拯导师签名砸日期：m 年f 月日第一章绪论1 1 课题背景第一章绪论随着数据库技术和数据获取技术的发展及数据获取手段的多样化，大量数据被收集。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。因此，需要强有力的数据分析工具来从存储在大型数据库中的海量数据中获取信息或知识，将“数据坟墓”变成“知识金块”。这一需求导致了数据挖掘这个研究领域的出现。数据挖掘( d a t am i n i n g ) “1 就是从大量的、不完全的、有噪声的、模糊的、随机的数据中识别或提取隐含的、新颖的、潜在有用的信息和知识的过程。它是机器学习、数据库系统、数据视觉化、统计学和信息学等多学科交叉发展而产生的新兴学科。聚类分析是数据挖掘技术中的一种常用的技术。将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。这些对象与同一个簇中的对象彼此相似，与其它簇中的对象相异。空间数据挖掘( s p a t i a ld a t am i n g ) 是从空间数据库中识别或提取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程，是数据挖掘研究的子领域之一。数据挖掘的相关研究成果，空间数据结构与数据库设计的最新成果，海量空间数据库索引技术的研究成果等为开展空间数据挖掘研究奠定了基础。空间数据挖掘的研究内容非常广泛，其研究的重点之一是从存储数据中发现模式的数据挖掘方法。空间数据挖掘的方法有：空间分析方法、统计分析方法、归纳学习方法、空间关联规则挖掘方法、聚类和分类方法、神经网络方法、决策树方法、粗糙集理论、模糊集理论、空间特征和趋势探测、云理论、图像分析与模式识别方法、证据理论、遗传算法、数据可视化方法、地学信息图谱方法、计算几何方法等”3 。其中，空间聚类分析研究是空间数据挖掘的重要研究方向之一。通过空间聚类分析既可以发现隐含在海量数据中的聚类规则，又可以与其电子科技大学硕士学位论文它数据挖掘方法结合使用，发掘更深层次的知识，从而提高数据挖掘的效率和质量。由于现实世界中产生的数据都是复杂数据，如何处理复杂数据，特别是空间高维复杂数据，是数据挖掘要解决的重要难题。研究数据挖掘的理论，运用这些理论解决各种实际问题，开发实用的数据挖掘软件产品，组成一支通晓数据挖掘技术、专业领域知识和有计算机应用经验的高素质技术队伍进行工程服务，是推广应用数据挖掘技术的关键。数据挖掘系统的开发，大致经过了四个阶段：1 第一代数据挖掘软件一般是针对某个特定应用，编写一个或几个算法进行挖掘，就构成一个挖掘系统。数据的表示、提取、整理、过滤以及挖掘结果的表示统统集成在一起。第一代数据挖掘软件的代表产品是新加坡国立大学开发的c b a 系统。它实现的是基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测。2 第二代数据耪掘软件的特点是与数据库管理系统的集成，能够支持数据库和数据仓库，和它们之间具有高性能的接口，可扩展性大大提高。用户与系统之间可以通过数据挖掘语言进行交互，定义数据挖掘任务和返回数据挖掘结果。这一代的数据挖掘产品比较多，象s f u的d b m i h e r 和s a s 的s a se n t e r p r is em i n e r 等。3 第三代数据挖掘软件的特点是预言模型标记语言的广泛支持，能够与预言模型系统无缝集成，使得数据挖掘软件产生的模型变化能够及时地反映到预言模型系统中。另一个特点是可以进行网络数据挖掘和异质数据挖掘。s p s s 公司的s p s sc 1e m e n t i i q e 属于第三代数据挖掘系统，它能够以p m m l 格式提供与预言模型系统的接口。4 第四代数据挖掘软件是指能够挖掘各种嵌入系统、移动系统和普遍存在( u b i q u i t o u s 计算设备产生的各种类型的数据。第四代数据挖掘系统原型或者商业系统还在研发当中。k a r g u p t a 带领的c a r e e r 数据挖掘项目是开发挖掘分布式和异质数据的( u b i q u i t o u s 设备) 的第四代数据挖掘系统。该项目研究期限是2 0 0 1 年4 月到2 0 0 6 年4 月。第一章绪论1 2 选题意义及课题任务1 2 1 选题意义1 、空间聚类分析是空问数据挖掘的重要组成部分空间聚类分析可以从空间实体数据集中发现隐含的信息或知识，主要有空间实体凝聚趋势、分布规律和发展变化趋势等。1 8 5 4 年琼斯诺博士发现伦敦霍乱病传播源就是利用空间聚类分析从大量数据中发现地理空间实体凝聚趋势的典型例子n 1 。空间实体分布规律揭示了空间实体的群体定位特征。空间聚类分析是揭示空间实体的群体定位特征的常用方法之一，如基于密度的聚类分析方法采用空间实体的分布密度来衡量空间实体是否属于同一簇，因而间接地表达了空间实体的群体分布密度和离散度等特征。划分聚类算法通常要求取簇的中心并采用不同的距离度羹方法，使用该算法得到的空间聚类可以间接反映空间实体的分布中心和分布轴线等特征。空间聚类分析要求能发现任意形状的聚类，将得到的聚类形状与理论扩展形状( 球形、椭圆形或方形) 相比较可发现许多有意义的隐含信息。e s t e r 1 利用空间聚类分析来解释经济地理现象，较好地解释了导致空间实体的非空间属性( 失业率) 在2 维平面上分布形状与理论扩展形状差异的原因。2 、空间聚类分析是其他挖掘算法的基础步骤空间聚类分析常常是空间数据挖掘的首要步骤陆1 。聚类分析的结果作为其它空间数据挖掘的输入数据，做进一步的挖掘分析。空间聚类分析结果可作为空间关联分析的输入来挖掘空间关联规则印1 。例如：如果对象是加油站，则对象靠近公路( 置信度7 5 ) 就是典型的空间关联规则。空间聚类分析可用于建立无指导空间分类的分类模型。c i h l a r 通过空间聚类和计算机建模方法来建立分类模型，对l a n d s a t 影像图进行土地覆盖类型分类，分类的自动化程度有了较大提高。空间聚类分析可进一步揭示对象的公共特征。空间数据特征化提供给定数据汇集的简洁汇总，是空间数据挖掘的主要研究内容之。电子科技大学硕士学位论文其结果的表现形式可以是经综合得到的规则、表格、数据的视觉化、基本统计数据( 平均数、离差) 等。k n o r r 研究了空间数据聚类结果的特征化问题，在对空间数据库进行聚类分析的基础上，进一步分析了聚类的公共特征。空间聚类分析可提高时序数据挖掘算法的效率。r o g e r s 利用g p s数据来建立汽车在城市街道上行驶车道模型阳1 ，将这类问题视为时空数据的时序挖掘。v l a c h o s 提出通过对时序数据利用h a r r 4 、波进行多分辨率分解n ”，在较“粗糙”层次上对时序数据进行聚类分析，得到时序数据的初步聚类特征，然后逐步求精，直到聚类特征不变为止。该方法大大提高时序数据挖掘算法的效率。1 2 2 课题任务研究数据挖掘的理论，运用这些理论解决各种实际问题，开发实用的数据挖掘软件产品，是推广应用数据挖掘技术的关键。9 0 年代以来，基于组件和中间件的三层结构逐渐取代两层结构成为i n t e r n e t 环境下电子商务系统开发的主流技术。s u n 提出的j 2 e e 框架就是三层结构的代表技术之一。电子科技大学计算智能实验室数据挖掘小组开发的基于w e b 的数据挖掘服务系统( m i n e r o n w e b ) 是在分析和借鉴了新西兰w a i k a t o 大学开发的w e k a 系统的基础上进行设计开发的。该系统采用j 2 e e 体系架构，s t r u ts ，j s p ，j a v aa p p l e t 等技术，分为e j b b 匣务层和w e b 应用服务层。我们重点研究网络环境下的数据挖掘技术，实现基于w e b 的三层b s 结构的数据挖掘服务系统。当前的工作已经实现了系统框架和基本功能，形成一个初步可用的系统。下一步的工作是通过对智能交互式的挖掘过程技术、完善的可视化技术、友好的挖掘结果报告产生技术等关键问题的研发，进一步完善整个系统界面的个性化、挖掘结果的可视化、算法评估等系统功能。1 3 内容组织本论文按以下顺序组织内容。第一章：绪论。本章主要介绍了论文所讲述的空间数据聚类分析第一苹绪论的背景、选题意义及课题的任务，并对论文的整体结构做一个概括。第二章：空间数据挖掘概述。介绍了空间数据挖掘的理论及特点、研究任务和方法、发展趋势及方向，指出了当前空间数据挖掘技术中尚需解决的问题。第三章：空间数据聚类分析。本章阐述了聚类的概念，系统地分析和总结了文献中发表的大量空间聚类算法，包括各种聚类算法的适用条件、性能、优缺点、计算复杂度。第四章：基于w e b 的数据挖掘服务系统。本章主要介绍了电子科技大学计算智能实验室( c i l a b ) 数据挖掘小组开发的基于j 2 e e 架构的w e b数据挖掘服务系统( m i n e r o n w e b ) ，对它的功能、特点、背景技术以及系统软硬件环境进行阐述。我的工作是参与系统设计，成功地设计和实现了系统的e j b 服务端和w e b 应用服务中的数据预处理模块，解决了j s p 页面中算法项的树状显示问题。本文对这些过程谶行详细分析和讨论。这是我工作中的主要部分。第五章：基于g h s o m 的聚类方法及实现。本章分祈和讨论o h s o m聚类算法，改进了该算法的学习规则，提高了网络迭代训练的效率。实现了该算法，并将其集成到m i n e r o n w e b 系统中，对聚类结果进行了可视化描述。这是我所做的工作的另一部分。第六章：论文总结。对整篇论文做一个整体总结，并对进一步的工作给予展望。电子科技大学硕士学位论文2 1 前言第二章空间数据挖掘概述随着数据库技术的成熟和数据应用的普及，数据库的数量、单个数据库的容量和数据类型的复杂性都大大地增加了。传统数据挖掘面临着一个重要的课题就是针对复杂类型数据的挖掘。因此，空间数据挖掘应运而生。由于空间数据的特殊性，从空间数据库中发掘知识很快引起了数据挖掘研究者的关注。2 2 空间数据挖掘方语和技术2 2 1 空间数据挖掘空间数据挖掘( s p a t ia id a t am in in g ) 与数据挖掘( d a t am i n i n g )一脉相承，它是数据挖掘的子研究方向之一。数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中识别或提取隐含的、新颖的、潜在有用的信息和知识的过程。空间数据挖掘是从空间数据库中识别或提取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。要对空间数据库中的数据进行有效的分析，首先要掌握空间数据库系统的数据表示、数据结构、基本操作。( 1 ) 空间数据的表示方法空间数据的属性可分为两大类：非空间属性和空间属性。非空间属性的数据类型又包括传统的数值型和字符型数据，如整数、日期、字符串等：空间属性的数据类型相对复杂，如点、线、多边形等。空间对象间的关系更加复杂，基本的空间关系有测量关系( 如距离) 、方向关系( 如西北方向) 和拓扑关系( 如相邻) 。非空间属性和空间属性之间往往通过指针发生联系。另外还有一种特殊的空间数据库，它几乎完全由图像构成，主要用于遥感、医学成像等，通常以栅格数组来表第二章空间数据挖掘概述示图像亮度。( 2 ) 空间数据的数据结构空间数据结构包括点、线、多边形等。为了给这些空间数据建立索引，引入了多维树。而最为常用的空间数据访问方法是r 一树和它的变形r 一树。( 3 ) 空间数据的基本操作通常的空间数据基本操作包括空间连接和图覆盖等，其中空间连接是计算量最大的空间操作。2 2 2 空间数据挖掘的特点由于空间数据的复杂性，空间数据挖掘不同于一般的事务数据挖掘，空间数据挖掘比一般数据挖掘增加了空间尺度维3 。它有如下一些特点：( 1 ) 数据源十分丰富，数据量非常庞大，数据类型多，存取方法复杂；( 2 ) 应用领域十分广泛，只要与空间位置相关的数据，都可以对其进行挖掘；( 3 ) 挖掘方法和算法非常多，而且大多数算法比较复杂，难度大；( 4 ) 知识的表达方式多样，对知识的理解和评价依赖于人对客观世界的认知程度。空间数据挖掘与传统数据挖掘的不同表现在：( 1 ) 传统数据挖掘处理的是数字和类别，而空间数据则是一些更为复杂的数据类型，例如：点、线、多边形等对象。( 2 ) 传统数据挖掘通常具有显式的输入，而空间数据挖掘的输入则常常是隐式的。( 3 ) 在传统数据挖掘中，有一个至关重要的前提假设：数据样品是独立生成的。而这一假设在空间数据分析中是不成立的。事实上，空间数据之间是高度自关联的，例如：具有相似特征、职业、背景的人容易聚集在同一个地区。这一特性被称之为空间自相关性n “。电子科技大学硕士学位论文2 2 3 空间数据挖掘的任务和方法空间挖掘的根本任务就是要发现大量的空间信息中所隐含的知识或规则，它可发现的知识类型有：地理几何知识、拓扑关系知识、空间分布知识、空间特征知识、区域差异知识、面向对象的知识。它能够发现的规则类型主要有：空间特征规则、空间辨识规则、空间互联规则。与一般事务性挖掘任务不同，空间数据挖掘主要研究空间数据的概率分布模式、聚类和分类特征、属性间的依赖关系以及时空自相关和互相关特征等阻，。为了完成各种数据挖掘任务，人们从统计学、人工智能和数据库等领域借用基础研究的成果和工具，提出了多种方法。比较常用的主要挖掘方法有：( 1 ) 统计的方法。统计方法一直是分析空间数据的常用方法，有着较强的理论基础，拥有大量的算法，可有效地处理数字型数据。( 2 ) 归纳的方法。归纳方法是对数据进行概括和综合归纳出离层次的模式或特征。( 3 ) 空间聚类方法。聚类分析方法按一定的距离或相似性测度将数据分成一系列相互区分的组。( 4 ) 空间分析方法。空间分析方法可采用拓扑结构分析、空间缓冲区及距离分析、叠置分析等方法，旨在发现目标在空间上的相连、相邻和共生等关联关系。( 5 ) 探测性的数据分析。探测性的数据分析，采用动态统计图形和动态链接窗1 ：3 技术将数据及其统计特征显示出来，可发现数据中非直观的数据特征及异常数据。与空间分析相结合，构成探测性的空间分析。( 6 ) 粗糙集方法。粗糙集理论是波兰华沙大学z p a w l a k 教授在1 9 8 2 年提出的一种智能数据决策分析工具，被广泛研究并应用于不精确、不确定、不完全的信息的分类分析和知识获取。( 7 ) 云理论。云理论是由李德毅教授提出的用于处理不确定性的一种新理论，由云模型、不确定性推理和云变换三大支柱构成。( 8 ) 图像分析和模式识别。空间数据库中含有大量的图形图像数据，一些行之有效的图像分析和模式识别方法可直接用于发现知识，第二章空间数据挖掘概述或作为其它知识发现方法的预处理手段。另外，决策树、神经网络、证据理论、模糊集理论、遗传算法等也可用于空间数据挖掘和知识发现。当然，这些方法都不是孤立应用的，为了发现某类知识，常常要综合应用这些方法。2 2 4 空间数据挖掘的过程空间数据挖掘是一个多处理阶段，其一般流程主要包括三个阶段“”：数据预处理、数据挖掘、结果解释和评价，如图2 - i 所示。整个过程是一个不断循环和反复的过程，因而可以对所挖掘出来的知识不断求精和深化并且使这些知识易于理解。图2 1空间数据挖掘的过程具体来说，数据预处理阶段包括：( 1 ) 数据清理，消除噪声或不一致数据；( 2 ) 数据集成，对不同数据源中的数据整合，进行数据完整性和一致性的检查，及噪音数据的过滤和不完整信息的填补等；( 3 ) 数据选择，根据挖掘任务从合成的数据库中选择性地提取与数据挖掘有关的数据。数据选择的目的是缩小处理的范围，提高数据挖掘的质量；( 4 ) 数据预处理，根据数据挖掘算法的要求，对选择的数据再进行投影、选择归一化变换等操作，以便于挖掘算法的处理。数据挖掘包括：( 1 ) 确定数据挖掘的目标和挖掘的知识类型；电子科技大学硕士学位论文( 2 ) 根据挖掘的知识类型选择合适的挖掘算法：( 3 ) 运用选定的挖掘算法从数据库中抽取所需的知识。结果的解释和评价包括：( 1 ) 对知识进行一致性和冗余检香，以，消除相互矛盾和重复的知识；( 2 ) 对所挖掘的知识进行解释，以一种用户易于理解的方式( 如可视化方式) 呈现给决策者( 3 ) 如果决策者对挖掘出的知识不满意，则要重复上述挖掘过程重新进行挖掘。以上整个过程不断地循环和反复，因而可以对所挖掘出来的知识不断求精和深化。2 3 空间数据挖掘的体系结构空间数据挖掘系统可以大致分为三层结构，如下图所示：刚，! 界嘣挖瓤器数掰源图2 - 2空间数据挖掘的体系结构第一层是数据源，指利用空间数据库或数据仓库管理系统提供的索引、查询优化等功能获取和提炼与问题领域相关的数据或直接利用存储在空间数据立方体中的数据，这些数据称为数据挖掘的数据源或信息库。在这个过程中，用户抽取与问题领域有关数据，然后再开始进行数据挖掘和知识发现过程。l o第二章空间数据挖掘概述第二层是挖掘器，利用空间数据挖掘系统中的各种数据挖掘方法分析被提取的数据，一般采用交互方式，由用户根据问题的类型以及数据的类型和规模，选用合适的数据挖掘方法，但对于某些特定的专门的数据挖掘系统，可采用系统自动地选用挖掘方法的方式。第三层是用户界面，使用多种方式( 如可视化工具) 将获取的信息和发现的知识以便于用户理解和观察的方式反映绔用户，用户对发现的知识进行分析和评价，并将知识提供给空问决策支持使用，或将有用的知识存入领域知识库内。在整个数据挖掘过程中，用户能够控制每一步。一般说来，数据挖掘和知识发现的多个步骤相互连接，需要反复进行人机交互，才能得到最终满意的结果。显然，在整个数据挖掘过程中，良好的人机交互用户界面是顺利迸行数据挖掘并取得满意结果的基础。2 4 空间数据挖掘的研究与应用1 空间数据挖掘的研究空间数据挖掘是一个极具吸引力和挑战性的研究领域。目前国内外都开展了空间数据挖掘与知识发现方面的研究。加拿大s i m o i lf r a s e r 大学计算机科学系的h a nj i a w e i 教授领导的小组，较早对此进行系统全面的研究，并在m a p i n f o 平台上建立了空间数据挖掘的原型系统g e o m i n e r ，实现了空间数据特征描述、空间比较、空间关联、空间聚类和空间分类等空间数据挖掘方法。国内武汉大学李德仁教授最早关注到从g i s 数据库中发现知识的问题，提出从g i s 数据库可以发现包括几何信息、空间关系、几何性质与属性关系以及面向对象知识等多种知识。宫鹏提出结合模式识别方法可通过高光谱遥感影像对森林进行很好的分类n ：马建文在遥感弱信息和临边效应信息提取方面做了大量的研究。同时，一些著名的数据库系统公司和数据统计分析公司如i b m ，s g i ，s p s s ，s a s ，s y b a s e 等都加入到数据挖掘领域，纷纷推出通用的数据挖掘系统，如i n t e l l i g e n tm i n e r ( i b m 公司的产品) ，m i n e s e t ( s g i公司的产品) ，c 1 e m e n t i l e ( s p s s 公司的产品) ，e n t e r p r is em i n e r ( s a s电子科技大学硕士学位论文公司的产品) ，d b m i t i e r ( d b m i n e rt e c h n o l o g y 公司开发) 等。当前，在空间数据挖掘的理论和方法方面，重要的研究方向有；背景知识概念树的自动生成、不确定性情况下的数据挖掘、递增式数据挖掘、栅格矢量一体化数据挖掘、多分辨率及多层次数据挖掘、并行数据挖掘、新算法和高效率算法的研究、空间数据挖掘查询语言、规则的可视化表达等。研究相似序列挖掘、非平穗时间序列挖掘、序列模式的维护以及时间序列在空间信息的数据挖掘等也是一个重要的研究方面。目前，空间数据挖掘主要集中在以下方面：面向对象的空间数据库的数据挖掘、模糊空间关联规则的挖掘、不确定性挖掘、聚类技术、挖掘空间数据的偏离和演变规则、基于多专题地图的挖掘、交叉概化、基于时空数据的概化、并行数据挖掘、统计分析与数据挖掘的协同、空间数据挖掘查询语言、带空问误差的数据挖掘、遥感影像的挖掘、多维规则可视化、智能g i s 方法等。2 空间数据挖掘的应用空间数据挖掘具有广泛的应用前景和潜在的综合效益，其应用正日益渗透到人们认识和改造空间世界的各个学科，如地理信息系统、信息融合、遥感、图像数据库、医疗图像处理、导航、机器人等使用空间数据的领域。空间数据挖掘能够指导发现新空间实体，空间决策，浏览空间数据库，理解空间数据，发现空间联系以及空间数据与爿# 空间数据之间的关系，重组空间数据库，构造空间知识库，优化空间查询等。空间数据挖掘的应用成果正日益扩展，其效益是不可估量的。如s k i c a t已经发现了1 6 个新的极其遥远的类星体；p o s s 系统将天空图像中的星体对象分类准确性从7 5 提高到9 4 ；m a r e l a ns t u d y 系统通过分折启明星表面的大约3 万幅高分辨率雷达图像来识别了火山；c o n q u e s t 系统基于内容的空间和时间查询，发现了大气层中臭氧洞形成的样本知识等。2 5 空间数据挖掘有待研究的问题虽然在空间数据挖掘技术的研究和应用中取得了很大的成绩，但在一些理论及应用方面仍存在急需解决的问题。主要包括多源空间数第二章空间数据挖掘概述据的清理、基于空间不确定性( 位置、属性、时间等) 的数据挖掘、递增式数据挖掘、栅格矢量一体化数据挖掘、多分辨率及多层次数据挖掘、并行数据挖掘、新算法和高效率算法的研究、空间数据挖掘查询语言、遥感图像数据库的数据挖掘、多媒体空间数据库的知识发现、网络空间数据的挖掘等方向。此外，空间数据挖掘除了发展和完善自己的理论和方法，也要充分借鉴和汲取数据挖掘和知识发现、数据库、机器学习、人工智能、数理统计、可视化、地理信息系统、遥感、图形图像学、医疗、分子生物学等学科领域的成熟的理论和方法。当前空间数据挖掘面临的主要挑战是：如何克服海量的空间数据、复杂的空间数据类型和多样性的空间访问方法所带来的问题、提高空间数据挖掘算法的效率。在空间数据挖掘系统的实现方面，要研究多源空间数据的集成、多算法的集成、存储空间和计算复杂性的降低、人机交互技术、可视化技术、空间数据挖掘系统与地理信息系统、空间数据仓库、空间决策支持系统和遥感解译专家系统的集成等问题。2 6 本章小结空间数据挖掘是从空间数据库中识别或提取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程，是数据挖掘研究的重要予领域之一。本章简要介绍了空间数据挖掘的理论及特点，列举了空间数据挖掘的研究任务和方法，根据空间数据挖掘的研究现状，讨论了空间数据挖掘领域所取得的进展、发展趋势及方向，指出了当前空间数据挖掘技术中尚需解决的问题。电子科技大学硕士学位论文3 1 前言第三章空间数据聚类分析聚类是数据挖掘中的一种非常重要的技术和方法。聚类在数据挖掘的很多实际应用中都发挥着很重要的作用。在商业上，聚类可以帮助市场分析人员从他们的消费者数据库中区分出不同的消费群体来，从而发现每一类消费者的消费习惯；可以帮助保险公司在数据库中发现汽车保险中具有较高索赔概率的群体。在因特网智能化方面，聚类可以用来将万维网上的网页文档，根据内容和主题划分为不同的集合，方便人们搜索信息。在生物学中，聚类可以被用来辅助研究动植物的分类，可以用来发现具有相似功能的基因。3 2 聚类分析概述对于一个给定的数据集，聚类就是将数据集中的对象划分为群或类，使得一个类中的对象“类似”，而不同类中的对象“不类似”。在聚类中，对象之间的类似性是基于距离来度量的，用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”衡量，直径是一个类中任意两个对象之间的最大距离。“质心距离”是聚类质量的另一种度量，它定义为“聚类质心”( 可以看作聚类空间中一个类的平均中心) 到每个聚类对象的平均距离。例如，图3 一l 展示了一个城市内顾客位置分布的2 - d 图，通过聚类，我们可以找到三个位置接近的顾客类，其中每个类的质心用“+ ”显示。第三章空间数据聚类分析图3 1一个城市内顾客位置的2 - d 图空间聚类分析主要是根据实体的特征对其进行聚类或分类，按一定的距离或相似度在大型多维空间数据集中标识出聚类或稠密分布的区域，将数据分成一系列相互区分的组，以期从中发现数据集的整个空间分布规律和典型模式。目前，对空间数据聚类分析方法的研究是一个热点。对于空间数据，利用聚类分析方法，可似根据地理位置以及障碍物的存在情况自动地进行区域划分。例如，根据分布在不同地理位鬣的a t m 机的情况将居民进行区域划分，根据这一信息，可以有效地进行a t m 机的设置规划，避免浪费，同时也避免失掉每一个商机。图3 - 2 城市a t m 机的设置3 3 空间聚类分析算法针对聚类分析，专家们提出了许多算法，这些算法可大致分为五类3 ：划分聚类算法、层次聚类算法、基于密度的方法、基于网格的方法和基于模型的聚类方法。除上述五大类方法以外，在各种文献中电子科技大学硕士学位论文还存在着大量的聚类方法。如处理高维数据的聚类方法n ”；处理大规模数据的聚类方法“；处理动态数据的聚类方法“”；基于遗传算法的聚类方法“”；模糊聚类方法n 83 以及将基本聚类方法与各种新技术相结合的聚类方，法”m 0 1 等。3 31 划分聚类算法划分方法( p a r t i t i o n i n gm e t h o d ) ：给定一个含n 个对象或元组的数据库，一个划分方法构建数据的k 个划分，每个划分表示一个聚簇，且k n 。也就是说，它将数据划分为k 个组，同时满足如下的要求：1 )每个组至少包括一个对象，2 ) 每个对象必须属于且只属予一个组。典型划分算法有k 一均值算洼、k 一中心点算法( 例如p a m 算法、c l a r a算法和c l a r a n s 算法) 。k 一均值算法以k 为参数，把n 个对象分为k 个聚簇，使簇内具有较高的相似度，面簇间的相似度较低。k 一均值算法对处理大数据集是相对可伸缩的和高效率的。缺点：1 ) 只有在簇的平均值被定义的前提下才能使用。2 ) 用户必须事先给出k ，即要生成的簇的数目。3 ) 不适合于发现非凸面形状的簇，或者大小差别很大的簇。4 ) 对于“噪声”和孤立点数据是敏感的。k 一中心点算法是先随意选取一个对象做为簇的中心，剩余的对象根据其与代表对象的距离分配给最近的一个簇。这种算法计算量要比k 一均值算法要大，一般只适合小数据量。p a m 算法首先在n 个对象中随机抽取k 个对象( 选择对象) 作为聚类中心，将余下的n k 个对象( 非选择对象) 依据乓聚类中心距离或相异程度最小原则划分到上述k个聚类中。c l a r a 算法“是一种基于采样的方法，能够处理大量的数据。算法思想就是用实际数据的抽样来代替整个数据然后再在这些抽样数据上利用p a m 算法。c l a r a 算法的效率取决于采样的大小，一般不太可能得到最佳的结果。因此在c l a r a 算法的基础上，n g 提出了c l a r a n s 算法仲”，将己知”个对象，发现七个中心点的过程抽象为图的搜索过程。c l a r a n s 算法与c l a r a 算法不同的是c l a r a 算法寻找最佳的中心点过程中采样都是不变的，而c l a r a n s 算法在每一次循环过程中所采用的采样都是不一样的。c l a r a n s 算法的复杂度大约第三章空间数据聚类分析是o ( n 2 ) ，其聚类质量也取决于所用的采样方法。通过采用空间数据结构，如r + 一树，及一些聚焦技术，c l a r a n s 的性能可以进一步提高。k 一中心点算法的不足：第一，当聚类尺寸差异较大时，位于大聚类边缘的对象也许更靠近邻近的较小聚类，会导致属于大聚类的对象被分配给较小聚类。第二，k 一中心点算法通常采用距离度薰相似性，易于生成球状聚类。当对象实际分布形状为非球状时，得到的聚类结果与实际情况差别很大。第三，计算准则函数时，需要扫描整个数据集，当对象数较大时，计算时间无法忍受。第四，与其它划分算法一样，c l a r a n s 和c l a r a 易于收敛于局部最优，效率受取样样本尺寸大小影响。第五，如果不采用聚焦技术，算法对数据集多次i 0 扫描，降低算法效率。3 3 2 层次聚类算法层次聚类方法( h i e r a r c h i c a lc 1 u s t e r i n g ) ：对给定的数据对象集合进行层次的分解，其结果是构建类似树的结构或聚类层次，分为凝聚的和分裂的两类方法。凝聚层次聚类一开始将每个对象视为一类。这些类依据它们之间的相似性合并，直到仅剩一个聚类为止。分裂层次聚类与凝聚层次聚类相反，一开始所有对象属于一类，然后分解聚类，直到每个对象属于某个聚类为止。基本的层次聚类方法是由k a u f m a n 和r o u s s e e u w 提出的凝聚方法a g n e s 和分裂方法d i a n a n 。凝聚层次聚类在算法开始时需要计算出所有对象两两间的距离，其时间复杂度是o ( n 2 ) ，空间复杂度是o ( n 2 ) 。一般来说，分裂算法的运算量比凝聚方法大，凝聚层次聚类方法比分解层次聚类方法使用的更普遍。凝聚和分裂层次聚类方法的优点是简单；能灵活处理多粒度的聚类问题；可使用多种形式的相似性度量或距离度量；可用于处理多种属性类型”。缺点是算法终止条件不易确定；选择合并或分裂点比较困难；聚类之间也不能交换对象；不具有很好的可伸缩性n “。因此产生了很多改进的层次聚类算法，典型的有b i r c h 2 “、c u r e n ”、c h a m e l e o n 2 6 1 等。1 、b i r c h 算法是针对大型数据库而设计的综合层次聚类算法。电子科技大学硕士学位论文主要目的是在有限机器内存条件下以最小的i o 开销实现对海量数据集的聚类分析。b i r c