摘自《武汉科技大学学报(自然科学版)》第25卷第2期－2002 年6 月

基于空间数据库的数据挖掘技术
蒋　旻
(武汉科技大学计算机学院，湖北武汉，430081)

　　摘　要：探讨扩展传统数据挖掘方法如分类、关联规则、聚类等到空间数据库的方法，着重对空间数据库系统实现技术及空间数据挖掘系统等进行比较分析，提出了一种空间数据挖掘系统的实现模式。
　　关键词：空间数据库；空间数据挖掘；空间分析
　　中图分类号：TP392　　文献标识码：A　　文章编号：1001-4985(2002)02-0183-04

Spatial Data Mining Based on Spatial Databases

　　Abstract : This paper discusses the methods of extending the classic data mining such as classification, association rules and clustering to spatial databases1With the analysis and comparison of the realization techniques of spatial database system and spatial data mining systems ，it proposes a development model of spatial data mining system.
　　Keywords : spatial database; spatial data mining; spatial analysis

　　随着GIS技术在各个行业的应用以及数据挖掘、空间数据采集技术、数据库技术的迅速发展，对从空间数据库发现隐含知识的需求日益增长，从而出现了用于在空间数据库中进行知识发现的技术——空间数据挖掘(Spatial Data Mining，本文简称为SDM)。空间数据挖掘是从空间数据库中提取隐含的、用户感兴趣的空间和非空间模式和普遍特征的过程。
　　本文分析了空间数据库知识发现面临的困难，研究了扩展传统数据挖掘方法如分类、关联规则、聚类等到空间数据库的方法，并对空间数据库系统实现技术及空间数据挖掘系统开发模式等进行了比较分析。

1　空间数据库知识发现面临的困难
　　从空间数据库发现知识的传统途径是通过专家系统、数据挖掘、空间分析等技术来实现的。但是在空间数据库隐含知识的发现方面，只单独依靠某一种技术，往往存在着这样或那样的缺陷。对于专家系统来讲，专家系统不具备自动学习的能力，GIS中的专家系统也达不到真正的智能系统的要求，仅能利用已有的知识进行推导。对于数据挖掘来讲，空间数据库与普通数据库的在数据存储机制的不同和空间数据的相互依赖性等特点决定了在空间数据库无法直接采用传统的数据挖掘方法。对于空间分析来讲，虽然空间分析中常用的统计方法可以很好地处理数字型数据，但是它存在的问题很多，如统计方法通常假设空间分布的数据间是统计上独立的，而现实中空间对象间一般是相互关联的；其次，统计模型一般只有具有相当丰富领域知识和统计方面经验的统计专家才能用；另外，统计方法对大规模数据库的计算代价非常高，所以在处理海量数据方面能力较低。
　　从上面的分析可以看出，由于空间数据具有诸多特点，因此在空间数据库进行知识发现，需要克服使用单一技术的缺陷，即需要融合多种不同技术。所以研究人员提出了空间数据挖掘技术来解决从空间数据库知识发现隐含知识的难题。
　　空间数据挖掘是多学科和多种技术交叉综合的新领域，它综合了机器学习、空间数据库系统、专家系统、可移动计算、统计、遥感、基于知识的系统、可视化等领域的有关技术。
　　空间数据挖掘利用空间数据结构、空间推理、计算几何学等技术，把传统的数据挖掘技术扩充到空间数据库并提出很多新的有效的空间数据挖掘方法。与传统空间分析方法相比，它在实现效率、与数据库系统的结合、与用户的交互、发现新类型的知识等方面的能力大大增强。空间数据挖掘能与GIS的结合，使GIS系统具有自动学习的功能，能自动获取知识，从而成为真正的智能空间信息系统。

2　扩展传统数据挖掘方法到空间数据库
　　空间数据挖掘技术按功能划分可分为三类：描述、解释、预测。描述性的模型将空间现象的分布特征化，如空间聚类。解释性的模型用于处理空间关系，如处理一个空间对象和影响其空间分布的因素之间的关系。预测型的模型用来根据给定的一些属性预测某些属性。预测型的模型包括分类、回归等。以下介绍将几个典型的数据挖掘技术聚类、分类、关联规则扩展到空间数据库的方法。
　　聚类分析方法按一定的距离或相似性测度将数据分成一系列相互区分的组，而空间数据聚类是按照某种距离度量准则，在某个大型、多维数据集中标识出聚类或稠密分布的区域，从而发现数据集的整个空间分布模式。经典统计学中的聚类分析方法对海量数据效率很低，而数据挖掘中的聚类方法可以大大提高聚类效率。文献[1]中提出两个基于CLARANS聚类算法空间数据挖掘算法SD和ND，可以分别用来发现空间聚类中的非空间特征和具有相同非空间特征的空间聚类。SD算法首先用CLARANS算法进行空间聚类，然后用面向属性归纳法寻找每个聚类中对象的高层非空间描述；ND算法则反之。文献[4]中提出一种将传统分类算法ID3决策树算法扩展到空间数据库的方法，该算法给出了计算邻近对象非空间属性的聚合值的方法，并且通过对空间谓词进行相关性分析和采用一种逐渐求精的策略使得计算时间复杂度大大降低。Koperski等[4]将大型事务数据库的关联规则概念扩展到空间数据库，用以找出空间对象的关联规则。此方法采用一种逐渐求精的方法计算空间谓词，首先在一个较大的数据集上用MBR最小边界矩形结构技术对粗略的空间谓词进行近似空间运算，然后在裁剪过的数据集上用代价较高的算法进一步改进挖掘的质量。

3　空间数据库实现技术
　　空间数据挖掘系统中，空间数据库负责空间数据和属性数据的管理，它的实现效率对整个挖掘系统有着举足轻重的影响。所以下面详细介绍空间数据库的实现技术。
　　根据空间数据库中空间数据和属性数据的管理方式，空间数据库有两种实现模式：集成模式和混合模式。后者将非空间数据存储在关系数据库中，将空间数据存放在文件系统中。这种采用混合模式的空间数据库中，空间数据无法获得数据库系统的有效管理，并且空间数据采用各个厂商定义的专用格式，通用性差。而集成模式是将空间数据和属性数据全部存储在数据库中，因此现在的GIS软件都在朝集成结构的空间数据库方向发展。下面对集成结构的空间数据库技术中的两个主流技术基于空间数据引擎技术的空间数据库和以Oracle Spatial为代表的通用空间数据库进行比较分析。
　　空间数据引擎是一种处于应用程序和数据库管理系统之间的中间件技术。使用不同GIS厂商的客户可以通过空间数据引擎将自身的数据交给大型关系型DBMS统一管理；同样，客户也可以通过空间数据引擎从关系型DBMS中获取其他类型GIS的数据，并转化成客户可使用的方式。它们大多是在Oracle8i Spatial(较成熟的空间数据库版本8.1.7于2000年9月推出)推出之前由GIS软件开发商提供的将空间数据存入通用数据库的解决方案，且该方案价格昂贵。
　　Oracle Spatial提供一个在数据库管理系统中管理空间数据的完全开放体系结构。Oracle Spatial提供的功能与数据库服务器完全集成。用户通过SQL定义并操作空间数据，且保留了Oracle的一些特性，如灵活的n-层体系结构，对象定义，健壮的数据管理机制，Java存储过程。它们确保了数据的完整性、可恢复能力和安全性，而这些特性在混合模式结构中几乎不可能获得。在Oracle Spatial中，用户可将空间数据当作数据库的特征使用，可支持空间数据库的复制、分布式空间数据库以及高速的批量装载，而空间中间件则不能。除了允许使用所有数据库特性以外，Spatial Cart ridge还提供用户使用行列来快速访问数据。使用简单的SQL语句，应用者就能直接选取多个记录。Spatial Cart ridge数据模型也给数据库管理员提供了极大的灵活性，DBA可使用常见的管理和调整数据库的技术。

4　空间数据挖掘系统的开发
　　4.1　通用SDM系统
　　在空间数据挖掘系统的开发方面，国际上最著名的有代表性的通用SDM系统有：GeoMiner，Descartes和ArcView GIS的S-PLUS接口。GeoMiner是加拿大Simon Fraser大学开发的著名的数据挖掘软件DBMiner的空间数据挖掘的扩展模块。空间数据挖掘原型系统GeoMiner包含有三大模块：空间数据立方体构建模块、空间联机分析处理(OLAP)模块和空间数据采掘模块，能够进行交互式地采掘并显示采掘结果。空间数据采掘模块能采掘3种类型的规则：特征规则、判别规则和关联规则。GeoMiner采用SAND体系结构，采用的空间数据采掘语言是GMQL。其空间数据库服务器包括MapInfo，ESRI/OracleSDE，Informix-Illustra以及其它空间数据库引擎。
　　Descartes可支持可视化的分析空间数据，它与开发此软件的公司所开发的数据挖掘工具Kepler结合使用，Kepler完成数据挖掘任务且拥有自己的表现数据挖掘结果的非图形界面。Kepler和Descarte动态链接，把传统DM与自动作图可视化和图形表现操作结合起来，实现C4.5决策树算法、聚类、关联规则的挖掘。
　　ArcView GIS的S-PLUS接口是著名的ESRI公司开发的，它提供工具分析空间数据中指定类。
　　除了以上空间数据挖掘系统外，还有GwiM等系统。
　　从以上SDM系统可以看出，它们的共同优点是把传统DM与地图可视化结合起来，提供聚类、分类等多种挖掘模式，但它们在空间数据的操作上实现方式不尽相同。Descartes是专门的空间数据可视化工具，它只有与DM工具Kepler结合在一起，才能完成SDM任务。而GeoMiner是在MapInfo平台上二次开发而成，系统庞大，造成较大的资源浪费。S-PLUS的局限在于，它采用一种解释性语言(Script)，其功能的实现比用C和C++直接实现要慢得多，所以只适合于非常小的数据库应用。基于现存空间数据挖掘系统的结构所存在的缺陷，我们提出空间数据挖掘系统一种新的实现方案。
　　4.2　空间数据挖掘系统一种新的实现方案
　　以上几种系统都是用自己开发的或GIS软件开发商提供的GIS平台、组件或中间件来实现SDM系统中空间数据管理和分析。本文中提出了空间数据挖掘系统一种新的实现方案，即以现在通用空间数据库(Oracle Spatial)为核心，利用其空间数据管理和空间分析的能力，完成空间数据挖掘中大量的空间信息抽取任务，GIS组件只承担对挖掘结果的地图化显示任务。采用这种模式，不仅可实现GIS系统与空间数据挖掘系统完全集成，并且由于大部分空间信息抽取过程直接在低层数据库上进行，从而可大大提高计算效率。
　　新的空间数据挖掘系统结构如图1所示。该系统的基本结构与一般数据挖掘系统相同，仅在数据挖掘和数据管理中增加了有关空间信息的抽取、空间数据管理和空间分析的功能，并建立了一个人机接口处理用户的指令和显示挖掘结果。
　　　　图1　新的空间数据挖掘系统结构
　　这种开发模式与现存开发模式的最大区别是用通用空间数据库代替专门的GIS商用软件实现空间数据管理和空间分析功能。它的优点如下：
　　(1)GIS商用软件一般是为开发GIS系统而设计的。GIS作为一个独立软件系统时，需要具有完整的功能结构，而在为数据挖掘服务时，其主要目的在于为决策者提供决策对象及显示作为挖掘结果的地图，因此只要按需选取GIS的部分功能，而不必面面俱到。GIS的一些功能，如空间数据的管理和空间分析等，在通用空间数据库系统中存在相似模块，因此可由通用空间数据库管理系统中已有功能得到。空间数据和属性数据的查询和空间操作可利用数据库管理功能，数据挖掘分析模块则可作为一个或多个模块，由数据挖掘子系统统一管理，而空间数据的存储管理与分析均交给通用空间数据库完成。这样不仅可减少系统的功能冗余，提高系统的一致性，还可更好地利用商用数据管理系统的各种优化技术来提高系统空间数据管理与分析的速度。
　　(2)从异构数据库的集成和空间数据与属性数据的统一管理来看，目前不同GIS厂商的遵循的空间数据格式标准不同，GIS通用平台或组件一般只能直接处理本系统的空间数据文件，因此异种数据库的集成是一个难题。而通用空间数据库提供了数据转换接口，可以将各种不同格式的空间数据转换为统一的格式存入扩展的对象——关系数据库，从而很好地解决了异种数据库的集成的问题。另外，它还克服了GIS系统空间数据与属性数据分离的缺点。
　　(3)从数据挖掘与空间数据库技术结合来看，空间数据库系统与数据挖掘系统完全分开的系统尽管简单，但有不少缺点。首先，空间数据库系统在存储、组织、访问和处理数据立方体方面提供了很大的灵活性和有效性。在空间数据库(SDB)/空间数据仓库(SDW)系统中，数据多半被很好地组织、索引、清理、集成或合并，使得找出任务相关的、高质量的数据成为一件容易的任务。不使用SDB/SDW系统，数据挖掘系统可能要花大量的时间查找、收集、清理和转换数据。其次，在SDB或SDW系统中，有许多被测试的、可伸缩的算法和数据结构，因此，使用这种系统开发有效的、可伸缩的实现，是切实可行的。此外，大部分数据已经或将要存放在SDB/SDW系统中，不与这些系统耦合，数据挖掘系统就需要使用其它工具提取数据，使得很难将这种系统集成到信息处理环境。
　　(4)Oracle Spatial是专门为开发与执行大型企业空间数据仓库而研制的产品，它在海量空间数据的存储和组织上性能卓越，在开发基于空间数据仓库的空间数据挖掘应用方面具有显著的优势。
　　(5)Oracle Spatial分担了SDM算法中部分空间数据抽取的任务，减轻了数据挖掘子系统的负担；另外，由于Oracle对分布式应用的良好支持，从而为实现分布式空间数据挖掘及并行空间数据挖掘提供了最佳方案。
　　基于以上方案，笔者实现了一个基于Oracle Spatial的分布式空间数据挖掘原型系统。系统由五部分组成：①图形用户界面：用于进行交互式的挖掘并显示挖掘结果；②数据准备模块：进行数据的选择、预处理和转换；③挖掘模块：聚类、分类、关联规则等空间数据挖掘功能及挖掘结果的评价；④空间数据管理模块：执行数据准备模块及挖掘模块指定的空间操作；⑤数据库服务器：管理作为挖掘目标的空间数据和非空间数据及概念层次库、挖掘结果库。挖掘目标的空间和非空间数据及概念层次的存储和空间数据的管理由Oracle8.1.7 Spatial实现。数据准备算法和聚类、分类、关联规则等挖掘算法在服务器端实现，并提供接口给客户端，在客户端用GIS组件MapX4.0实现挖掘结果的专题图显示。其编程工具为VC++6.0。

参考文献
[1] R T Ng, J Han. Efficient and Effective Clustering Methods for Spatial Data Mining[A]. Proc. of Twentieth International Conference on Very Large Data Bases[C]. Santiago, Chile, 1994.144-155.
[2] K Koperski, J Han. Discovery of Spatial Association Rules in Geographic Information Databases[A]. Proc
of Fourth International Symposium on Large Spatial Databases[C]. Maine, 1995.47-66.
[3] J Han, K Koperski, N Stefanovic. GeoMiner : A System Prototype for Spatial Data Mining[A]. Proc. of
ACM SIGMOD Conference on the Management of Data[C]. Tucson, Arizona, USA, 1997.553-556.
[4] K Koperski, J Adhikary, J Han. Knowledge Discovery in Spatial Databases : Progress and Challenges[A].
Proc. of ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery[C]. Montreal, Canada , 1996.55-70.