第十章 空间数据挖掘,2,第十章 目录,10.1空间数据挖掘简介 10.2空间关联规则挖掘 10.3空间co-location模式挖掘 10.4本章小结,3,引言,近年来，随着数据处理工具、先进数据库技术以及万维网（WWW）技术的不断成熟和数据应用的普及，数据库不论是数量、单个数据库的容量，还是数据类型的复杂程度都大幅度地增加了。因此，传统数据挖掘面临着一个重要的课题就是针对复杂类型数据的挖掘。正是基于这个原因，作为数据挖掘技术的一个延伸发展，空间数据挖掘应运而生。,4,10.1 空间数据挖掘简介,10.1.1 空间数据挖掘的产生 10.1.2 空间数据的特点 10.1.3 空间数据挖掘的过程 10.1.4 空间数据挖掘的分类,5,10.1 空间数据挖掘简介,空间数据挖掘是指对空间数据库中非显式存在的知识、空间关系或其他有意义的模式等的提取。空间数据挖掘需要综合数据挖掘与空间数据库技术。空间数据挖掘不仅在地理信息系统、地理市场、遥感、图像数据勘测、医学图像处理、导航、交通控制、环境研究等领域有着广泛的应用，空间数据挖掘还可以用于对空间数据的理解、空间关系和空间与非空间数据关系的发现、空间知识库的构造、空间数据库的重组和空间查询的优化。,6,10.1.1 空间数据挖掘的产生（1）,空间数据挖掘技术的产生来自于两个方面的推动力： 首先，由于数据挖掘研究领域的不断拓展，由最初的关系数据和事务数据的挖掘，发展到对空间数据库的挖掘。空间信息正在逐步成为各种信息系统的主体和基础。空间数据是一类重要、特殊的数据，它有着比一般关系数据库和事务数据库更加丰富和复杂的语义信息，包含着更丰富的知识。因此，尽管数据挖掘最初产生于关系数据库和事务数据库，但由于空间数据的特殊性，从空间数据库中挖掘知识很快引起了数据挖掘工作者的关注。许多数据挖掘方面的研究工作也从关系型和事务型数据库扩展到空间数据库。,7,10.1.1 空间数据挖掘的产生（2）,其次，在地学领域，随着卫星和遥感技术的广泛应用，日益丰富的空间数据和非空间数据收集和存储在空间数据库中，海量的地理数据在一定程度上已经超过了人们的处理能力，同时传统的地学分析难以胜任从这些海量数据中提取和发现地学知识。这给当前GIS技术提出了巨大的挑战，迫切需要增强GIS分析功能，提高GIS解决地学实际问题的能力。数据挖掘与知识发现的出现很好的满足了地球空间数据处理的需要，推动了传统地学空间分析的发展。根据地学空间数据的特点，将数据挖掘方法引入GIS，形成地学空间数据挖掘与知识发现的新型地学数据分析理论。,8,10.1.2 空间数据的特点（1）,空间数据是指用来记录空间实体的位置、 形状、 大小、 空间分布特征、 相互关系以及质量数量等信息的数据, 不仅需要描述空间实体的常规属性信息和空间几何信息, 同时还要记录空间实体之间的关系, 包括空间拓扑关系, 方位关系和距离关系。 与普通数据相比, 空间数据更加复杂, 其主要有如下的特点:,9,10.1.2 空间数据的特点（2）,1） 海量性。一方面, 各种空间数据获取技术的进步, 使得可用空间数据总量呈几何量级不断增长。另一方面, 由于空间数据需要记录的内容多且复杂, 单个实体信息存储空间相对普通数据也较大。 因此, 基于海量空间数据的挖掘, 不但要考虑算法的可行性, 而且还要考虑算法的效率。传统的非空间挖掘算法必须进行改进以满足在海量空间数据中进行挖掘的要求。,10,2） 多维性。空间数据记录空间实体的空间、 非空间、 空间与空间、 空间与非空间、 非空间与非空间属性之间的关系, 每个方面又由多个属性维构成, 故空间数据的维数很高。在进行空间数据挖掘时, 如何在如此复杂维度的数据中进行取舍, 并进行高效的知识获取, 是一个很有意义的研究方向。 3） 多尺度。尺度是空间数据一个固有的特性, 又是其复杂性的一种体现。空间数据在不同观察层次上所遵循的规律以及体现出的特征不尽相同。 在进行挖掘时, 可以利用不同尺度层次之间的渐变关系, 来进行同尺度、 跨尺度的挖掘及由已知尺度下的挖掘结果推导其它尺度下的知识。,10.1.2 空间数据的特点（3）,11,10.1.2 空间数据的特点（4）,4） 不确定性。传统空间数据分析中, 空间实体的几何边界或定性属性都视为刚性。在现实世界中, 空间实体的边界却是柔性的, 而且不同实体边界弹性大小各异。空间数据的柔性边界使得在进行相应的空间数据挖掘时, 不同抽象层次空间和非空间关系计算具有了不确定性。 如何在空间数据中表达这种柔性边界, 如何计算具有不确定性的空间实体间的关系是空间数据挖掘的一个重要的研究内容。,12,10.1.2 空间数据的特点（5）,5） 相关性。传统数据在统计上是相互独立的。空间实体分布于一定的空间区域内, 相互之间存在着某种关系, 从而导致空间数据之间具有一定的相关性。 这种相关性可以是空间的也可以是非空间的, 可以是线性的也可以是非线性的。 它是空间系统复杂性的一个主要标志, 是空间数据挖掘的一个主要任务。,13,10.1.3 空间数据挖掘的过程（1）,从空间数据库中发现知识是一个多步骤的处理过程，在处理过程中可能会有很多次反复。空间数据挖掘是空间数据知识发现过程中的一个重要步骤。空间知识发现过程如图10.1所示。,图10.1 空间知识发现过程图,14,10.1.3 空间数据挖掘的过程（2）,（1）准备 了解空间数据挖掘（SDM, Spatial Data Mining）的相关情况，熟悉有关背景知识，弄清用户的需求。 （2）数据选择 根据用户的要求从空间数据库（SDB, Spatial DataBases）中提取与SDM相关的数据，构成源相关数据集。,15,10.1.3 空间数据挖掘的过程（3）,（3）数据预处理 检查数据的完整性和一致性，对其中的噪音数据进行处理，对丢失的数据利用统计方法进行填补，得到目标相关数据集。 （4）空间数据挖掘,16,10.1.3 空间数据挖掘的过程（4）,（5）解释评价 根据某种兴趣度度量，提取用户真正感兴趣的模式，并通过决策支持工具提交给用户。如果用户不满意，则需要重复以上知识发现过程。,17,10.1.4 空间数据挖掘的分类（1）,空间数据挖掘的主要任务有： 空间聚类 空间分类 空间关联规则 空间异常挖掘 空间趋势分析等等,18,10.1.4 空间数据挖掘的分类（2）,空间聚类 空间数据聚类是要在一个比较大的多维数据集中根据距离的度量找出簇，或稠密区域。空间聚类所分析处理的数据均是无（事先确定）类别归属，类别归属在聚类分析处理的数据集中是不存在的，空间聚类属无教师监督的学习方法。空间数据库中聚类的应用包括通过对地震目录中实体的分组来探测地理断层和在地理信息系统中通过对特征空间的聚类来生成主题地图等。空间数据库上的聚类算法主要有三种：分区算法、层次聚类算法和单扫描算法。,19,10.1.4 空间数据挖掘的分类（3）,空间分类 空间分类是指通过分析空间对象导出与一定空间特征有关的分类模式。空间分类的目的是在空间数据库对象的空间属性和非空间属性之间发现分类规则。空间分类是近来空间数据挖掘领域中比较活跃的一个方向。在空间分类领域中常常使用决策树方法。例如，使用决策树的方法对星形结构对象的图像进行分类，从而探测星星与银河。,20,10.1.4 空间数据挖掘的分类（4）,空间关联规则 空间关联规则是对传统数据挖掘中的关联规则的扩展。空间关联规则即是指空间邻接图中对象之间的关联。空间关联规则形如ABs%，c%，A和B是空间和非空间谓词的集合，s%表示规则的支持度，c%表示规则的可信度。,21,10.1.4 空间数据挖掘的分类（5）,空间关联规则挖掘算法： 第一步，通过空间查询从初始空间数据库中获得和任务相关的空间数据库； 第二步，使用一些有效空间挖掘算法计算对象之间的空间关系，从而获得一个候选谓词集合； 第三步，对第二步中所得到的谓词集合中的每一个谓词计算其支持度，并且将那些支持度小于最小支持度的谓词删除； 第四步，对谓词集合进行进一步精化以决定准确的空间关系； 第五步，以第四步所得的侯选集作为输入，生成空间关联规则。,22,10.1.4 空间数据挖掘的分类（6）,空间异常挖掘 空间异常挖掘作为空间数据挖掘中的一个重要的研究方向，比传统的异常挖掘有着明显的、新的特点，由于空间数据具有高度的自相关性，如果只是采用传统异常挖掘中所使用的理论和方法来进行对数据的分析和处理，势必得不到满意的结果。因此，在空间异常挖掘的过程中，要充分考虑空间数据的特点，采用相应的方法对空间数据进行分析处理，才能抓住空间异常的本质，找到隐藏在大量空间数据之后的知识、模式。空间异常是明显偏离数据集（库）中的其他数据、不满足数据的一般模式或行为，与存在的其他数据不一致的空间数据。,23,10.1.4 空间数据挖掘的分类（7）,空间趋势 空间趋势指的是离开一个给定的起始对象时，非空间属性的变化情况。例如，当离城市中心越来越远时经济形势的变化趋势。空间趋势分析的结果可能是正向趋势、反向趋势，或者是没有趋势。一般而言，要在空间数据结构和空间访问方法之上分析空间趋势需要使用回归和相关的分析方法。由于空间数据库自身的特殊性，传统的回归模型可能并不合适。例如，传统的线性回归模型：Y=X+在空间数据库中就不适用，需要使用空间自回归模型：Y=WY+X+。,24,10.2空间关联规则挖掘,10.2.1 空间关联规则挖掘的相关概念 10.2.2 自顶向下，逐步求精的空间关联规则挖掘算法,25,10.2.1 空间关联规则挖掘的相关概念（1）,1. 空间谓词。 定义10.1（非空间谓词）表示空间对象的非空间属性的性质的谓词称为非空间谓词（Non-Spatial Predicates）。非空间属性一般分为两类：分类属性（categorical attribute）和量化属性（quantitative attribute）。分类属性具有有限个不同值，值之间无序（例如：职位、种类、颜色等）。量化属性则是数值型的，并在值之间具有一个隐含的序（例如：年龄、收入、价格等）。,26,10.2.1 空间关联规则挖掘的相关概念（2）,定义10.2（空间谓词）空间关系是空间对象之间由于空间位置和形状的不同而造成的相互之间的各种联系，能够表示空间关系的谓词称为空间谓词（Spatial Predicates）。 空间关系一般分为三类： 拓扑关系 对应空间谓词如：adjacent、disjoint、intersect、overlap等。 距离关系 对应空间谓词如：close_to、far_away、“distance100”等。 空间方位关系 对应空间谓词如：above、below、north_of、southwest_of、left_of等。,27,10.2.1 空间关联规则挖掘的相关概念（3）,（1）拓扑关系（Topological Relationship） 拓扑关系是最基本的空间关系，两对象之间的拓扑关系具有不因参照物的拓扑变换（如放缩、旋转）而改变的特点，可通过9个相交矩阵模型定义。 例10.1 设A、B是两个空间对象，可以分别为一个点（P）、一条线（L）或一个多边形表示的面（R），那么符号A、A、A分别表示A的内部、外部和边界。A、B的33相交矩阵如图10.3所示，用它可以判别A、B之间的拓扑关系，包括A meet B、A overlap B、A disjoint B、A equal B、A cover B、A covered_by B、A contain B、A inside B 。,A B AB AB AB AB AB A B A B A B,图10.3 A, B的33相交矩阵,28,10.2.1 空间关联规则挖掘的相关概念（4）,（2）距离关系（Metric relationship） 距离关系说明A、B两个空间对象之间在距离度量上的关系