空间数据挖掘技术理论及方法
葛继科

（西南农业大学信息学院　400716）

 

摘要  本文简要论述了空间数据库技术及空间数据挖掘技术的理论及特点，分析了空间数据挖掘技术的层次、方法，并重点引见了当前常用的分类、聚类、关联规则等空间数据挖掘方法，指出了当前空间数据挖掘技术中尚需处理的问题、发展趋势及方向。

关键词　空间数据挖掘　分类　聚类　关联规则　

0 引言

地理信息系统(Geographic Information System，简称GIS)是计算机科学、地理学、测量学、地图学等多门学科综合的技术[1]。GIS的基本技术是空间数据库、地图可视化及空间分析，而空间数据库是GIS的关键。空间数据挖掘技术作为当前数据库技术最活跃的分支与知识获取手段，在GIS中的使用推动着GIS朝智能化和集成化的方向发展。

1 空间数据库与空间数据挖掘技术的特点

随着数据库技术的不断发展和数据库管理系统的广泛使用，数据库中存储的数据量也在急剧增大，在这些海量数据的背后隐藏了很多具有决策意义的信息。但是，现今数据库的大多数使用仍然停留在查询、检索阶段，数据库中隐藏的丰富的知识远远没有得到充分的发掘和利用，数据库中数据的急剧增长和人们对数据库处理和理解的困难构成了强烈的反差，导致“人们被数据吞没，但却饥饿于知识”的景象。

空间数据库(数据仓库)中的空间数据除了其显式信息外，还具有丰富的隐含信息，如数字高程模型〔DEM或TIN〕，除了载荷高程信息外，还隐含了地质岩性与结构方面的信息；植物的品种是显式信息，但其中还隐含了气候的水平地带性和垂直地带性的信息，等等。这些隐含的信息只要通过数据挖掘才能显示出来。空间数据挖掘（Spatial Data Mining，简称SDM），或者称为从空间数据库中发现知识，是为了处理空间数据海量特性而扩展的一个新的数据挖掘的研讨分支，是指从空间数据库中提取隐含的、用户感兴味的空间或非空间的模式和普遍特征的过程[2]。由于SDM的对象次要是空间数据库，而空间数据库中不只存储了空间事物或对象的几何数据、属性数据，而且存储了空间事物或对象之间的图形空间关系，因此其处理方法有别于普通的数据挖掘方法。SDM与传统的地学数据分析方法的本质区别在于SDM是在没有明确假设的前提下去挖掘信息、发现知识，挖掘出的知识应具有事先未知、无效和可实用3个特征。

空间数据挖掘技术需求综合数据挖掘技术与空间数据库技术，它可用于对空间数据的理解，对空间关系和空间与非空间关系的发现、空间知识库的结构以及空间数据库的重组和查询的优化等。

2 空间数据挖掘技术的次要方法及特点

常用的空间数据挖掘技术包括：序列分析、分类分析、预测、聚类分析、关联规则分析、时间序列分析、粗集方法及云理论等。本文从挖掘任务和挖掘方法的角度,着重引见了分类分析、聚类分析和关联规则分析三种常用的重要的方法。

2.1、分类分析

分类在数据挖掘中是一项非常重要的任务，目前在商业上使用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器)，该模型能把数据库中的数据项映射到给定类别中的某一个。分类和我们熟知的回归方法都可用于预测，两者的目的都是从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。和回归方法不同的是，分类的输出是离散的类别值，而回归的输出则是连续的数值。二者常表现为一棵决策树，依据数据值从树根开始搜索，沿着数据满足的分支往上走，走到树叶就能确定类别。空间分类的规则实质是对给定数据对象集的笼统和概括，可用宏元组表示。

要结构分类器,需求有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成,每个元组是一个由特征(又称属性)值组成的特征向量,此外,训练样本还有一个类别标记。一个具体样本的方式可为:( v1, v2, ..., vn; c )；其中vi表示字段值，c表示类别。

分类器的结构方法有统计方法、机器学习方法、神经网络方法等等。统计方法包括贝叶斯法和非参数法(近邻学习或基于事例的学习)，对应的知识表示是判别函数和原型事例。机器学习方法包括决策树法和规则归纳法，前者对应的表示为决策树或判别树，后者则普通为产生式规则。神经网络方法次要是反向传播（Back-Propagation,简称BP）算法，它的模型表示是前向反馈神经网络模型(由代表神经元的节点和代表联接权值的边组成的一种体系结构)，BP算法本质上是一种非线性判别函数[3]。另外，最近又衰亡了一种新的方法:粗糙集(rough set)，其知识表示是产生式规则。

不同的分类器有不同的特点。有三种分类器评价或比较尺度：1) 预测精确度；2) 计算复杂度；3) 模型描述的简约度。预测精确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是海量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。对于描述型的分类任务，模型描述越简约越受欢迎。例如，采用规则归纳法表示的分类器结构法就很有用，而神经网络方法产生的结果就难以理解。

另外要留意的是，分类的效果普通和数据的特点有关。有的数据噪声大，有的有缺值， 有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。

分类技术在实际使用非常重要，比如：可以依据房屋的地理位置决定房屋的档次等。

2. 2 聚类分析

聚类是指依据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，并且对每一个这样的组进行描述的过程。它的目的是使得属于同一个组的样本之间应该彼此类似，而不同组的样本应足够不类似。与分类分析不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道依据哪些空间区分规则来定义组。其目的旨在发现空间实体的属性间的函数关系，挖掘的知识用以属性名为变量的数学方程来表示。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。基于聚类分析方法的空间数据挖掘算法包括均值近似算法[4]、CLARANS、BIRCH、DBSCAN等算法。目前，对空间数据聚类分析方法的研讨是一个热点。

对于空间数据，利用聚类分析方法，可以依据地理位置以及妨碍物的存在情况自动地进行区域划分。例如，依据分布在不同地理位置的ATM机的情况将居民进行区域划分，依据这一信息，可以无效地进行ATM机的设置规划，避免浪费，同时也避免失掉每一个商机。

2.3 关联规则分析

关联规则分析次要用于发现不同事件之间的关联性，即一事物发生时，另一事物也经常发生。关联分析的重点在于快速发现那些有实用价值的关联发生的事件。其次要依据是：事件发生的概率和条件概率应该符合一定的统计意义。空间关联规则的方式是X－＞Y[S%，C%]，其中X、Y是空间或非空间谓词的集合，S%表示规则的支持度，C%表示规则的置信度。空间谓词的方式有3种：表示拓扑结构的谓词、表示空间方向的谓词和表示距离的谓词[5]。各种各样的空间谓词可以构成空间关联规则。如，距离信息（如Close_to(临近)、Far_away(远离)）、拓扑关系（Intersect（交）、Overlap（堆叠）、Disjoin(分离)）和空间方位（如Right_of(左边)、West_of(西边)）。实际上大多数算法都是利用空间数据的关联特性改进其分类算法，使得它适合于挖掘空间数据中的相关性，从而可以依据一个空间实体而确定另一个空间实体的地理位置，有利于进行空间位置查询和重建空间实体等。大致算法可描述如下：(1)依据查询要求查找相关的空间数据；(2)利用临近等准绳描述空间属性和特定属性；(3)依据最小支持度准绳过滤不重要的数据；(4)运用其它手段对数据进一步提纯(如OVERLAY)；(5)生成关联规则。

关联规则通常可分为两种：布尔型的关联规则和多值关联规则。多值关联规则比较复杂，一种自然的想法是将它转换为布尔型关联规则，由于空间关联规则的挖掘需求在大量的空间对象中计算多种空间关系，因此其代价是很高的。—种逐渐求精的挖掘优化方法可用于空间关联的分析，该方法首先用一种快速的算法粗略地对一个较大的数据集进行一次挖掘，然后在裁减过的数据集上用代价较高的算法进一步改进挖掘的质量。由于其代价非常高，所以空间的关联方法需求进一步的优化。

对于空间数据，利用关联规则分析，可以发现地理位置的关联性。例如，85%的靠近高速公路的大城镇与水相邻，或者发现通常与高尔夫球场相邻的对象是停车场等。

3 空间数据挖掘技术的研讨方向

3.1 处理不同类型的数据

绝大多数数据库是关系型的，因此在关系数据库上无效地执行数据挖掘是至关重要的。但是在不同使用领域中存在各种数据和数据库，而且经常包含复杂的数据类型，例如结构数据、复杂对象、事务数据、历史数据等。由于数据类型的多样性和不同的数据挖掘目标，一个数据挖掘系统不可能处理各