搜索
2020年2月16日星期日1空间挖掘技术概述大量的空间数据是从遥感、地理信息系统（GIS）、多媒体系统、医学和卫星图像等多种应用中收集而来，收集到的数据远远超过了人脑分析的能力。日益发展的空间数据基础设施为空间数据的自动化处理提出了新的课题。空间数据的最常用的数据组织形式是空间数据库。空间数据库必须保存空间实体，这些空间实体是用空间数据类型和实体的空间关系来表示出来的。空间数据库，不同于关系数据库，它一般具有空间拓扑或距离信息，通常需要以复杂的多维空间索引结构组织。空间挖掘（SpatialMining）或被称作空间数据挖掘/空间数据库的知识发现，是数据挖掘技术在空间数据方面的应用。简言之，空间数据挖掘，就是从空间数据库中抽取隐含的知识、空间关系或非显式地存储在空间数据库中的其他模式，用于理解空间数据、发现数据间（空间或非空间）的关系。由于空间数据的复杂性及其应用的专业性，在一般的数据挖掘的基本概念的基础上，需要研究空间数据挖掘特有的理论、方法和应用。2020年2月16日星期日2第八章空间挖掘内容提要引言空间数据概要空间数据挖掘基础，空间统计学泛化与特化空间规则空间分类算法空间聚类算法空间挖掘的其他问题空间数据挖掘原型系统介绍空间数据挖掘的研究现状与发展方向其他2020年2月16日星期日3空间数据的主要特点空间数据是指与二维、三维或更高维空间的空间坐标及空间范围相关的数据，例如地图上的经纬度、湖泊、城市等。访问空间数据要比访问非空间数据更复杂。对空间数据的访问要使用专门的操作和数据结构。空间数据可以用包含着诸如“接近、南、北、包含于”等空间操作符的查询来访问。空间数据存放在记录着实体的空间性数据和非空间性数据的空间数据库里。由于空间数据关联着距离信息，所以空间数据库通常用使用距离或拓扑信息的空间数据结构或者索引来存储。就数据挖掘而论，这些距离信息提供了所需的相似性度量的基础。2020年2月16日星期日4空间数据的复杂性特征空间数据的复杂性特征主要表现在以下几个方面：空间属性之间的非线性关系：空间属性之间的非线性关系是空间系统复杂性的重要标志，被作为空间数据挖掘的主要任务之一。空间数据的多尺度特征：空间数据的多尺度性是指空间数据在不同观察层次上所遵循的规律以及体现出的特征不尽相同。多尺度特征是空间数据复杂性的又一表现形式。空间信息的模糊性：模糊性几乎存在于各种类型的空间信息中，如空间位置的模糊性、空间相关性的模糊性以及模糊的属性值等等。空间维数的增高：空间数据的属性增加极为迅速，如在遥感领域，由于传感器技术的飞速发展，波段的数目也由几个增加到几十甚至上百个，如何从几十甚至几百维空间中提取信息、发现知识则成为研究中的又一难题。空间数据的缺值：数据的缺值现象源自由于某种不可抗拒的外力而使数据无法获得或发生丢失。如何对丢失数据进行恢复并估计数据的固有分布参数，成为解决数据复杂性的难点。2020年2月16日星期日5空间查询问题查询是挖掘的技术，空间查询及其操作的主要特点有：空间操作相对复杂和不精确：传统的访问非空间数据的选择查询使用的是标准的比较操作符：，，≤，≥，≠。而空间选择是一种在空间数据上的选择查询，要用到空间操作符，包括接近、东、西、南、北、包含、重叠或相交等。下面是几个空间选择查询的例子：例如，“查找北海公园附近的房子”。空间连接（SpatialJoin）问题：在两个空间关系上的一个空间性连接操作被称为空间连接（SpatialJoin）。在空间连接中，关系都是空间性的，需要与空间连接对应的条件描述。例如，“相交”关系用于多边形；“相邻”关系用于点。相同的地理区域经常有不同的视图：一个区域不同的视图（如基础设施、城市规划、绿化等）保存在单独的GIS文件中，融合这些数据，通常需要一个称为“地图覆盖”（MapOverlay）的操作来实现。一个空间实体可用空间和非空间的属性来描述。当其空间属性用一些空间数据结构存储起来之后，非空间属性就可以存储在一个关系数据库里。对空间数据库来说，不同的空间实体经常是和不同的位置相关联的，而且在不同的实体之间进行空间性操作的时候，经常需要在属性之间进行一些转换。2020年2月16日星期日6空间数据结构由于空间数据的独特性质，有很多数据结构专门被设计用来存储或索引空间数据。这些结构有的考虑的是空间实体的轮廓表示，有的是空间数据的索引方法。空间实体表示的最常用方法是“最小包围矩形”。空间索引技术大多是基于对空间目标的近似技术，例如，空间映射法（1）采用低维空间向高维空间映射的方式：ｋ维空间具有ｎ个顶点的目标可以映射成ｎ*ｋ维空间的点。映射后，可以直接采用点索引技术。（2）直接向一维空间映射：通常数据空间被划分成大小相同的网格单元，通过给这些网格单元编码形成一维目标，用传统的一维的索引结构（如Ｂ+树等）索引。分割方法（1）采用不允许空间重叠的索引方法：将所在的数据空间按某种方法（如二叉树划分、四叉树划分、格网划分等）划分成彼此不相交的子空间。（2）采用允许空间重叠的索引法：将索引空间划分为多级的子空间，这些子空间允许重叠，但是一个空间实体完全包含在某一子空间中。2020年2月16日星期日7最小包围矩形通过完整包含一个空间实体的最小包围矩形（MBR：MinimumBoundingRectangle）来表示该空间实体。例如，下图显示一湖泊的MBR：如果用传统坐标系统来对这个湖定向，水平轴表示东西方向，垂直轴表示南北方向，那么就可以把这个湖放在一个矩形里（中间图所示）还可以通过一系列更小的矩形来表现这个湖（右图所示）另一种更简单的方法是用一对不相邻的顶点坐标来表示一个MBR，如用{(x1，y1)，(x2，y2)}来表示（中间图所示）。2020年2月16日星期日8空间索引技术空间索引是指依据空间实体的位置和形状或空间实体之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间实体的概要信息。空间索引的性能优劣直接影响空间数据库和地理信息系统的整体性能，也对空间数据挖掘的效率有影响。几种比较有代表性的空间数据索引结构技术：网格文件四叉树R-树k-D树2020年2月16日星期日9网格文件根据正交的网格划分ｋ维的数据空间。ｋ维数据空间的网格由ｋ个一维数组表示，这些数组称为刻度，将其保存在主存。刻度的每一边界构成ｋ-1维的超平面。整个数据空间被所有的边界划分成许多ｋ维的矩形子空间，这些矩形子空间称为网格目录，用ｋ维的数组表示，将其保存在硬盘上。网格目录的每一网格单元包含一外存页的地址，这一外存页存储了该网格单元内的数据目标，称为数据页。一数据页允许存储多个相邻网格单元的目标。网格文件的查找简单，查找效率较高，适用于点目标的索引。2020年2月16日星期日10四叉树四叉树通过把空间按等级分解成为区域（单元）来表示空间实体。四叉树实际上每一节点有4个子树，用于对空间点的表示与索引。如二维空间的四叉树，每个子节点对应一个矩形，用四种方位西北（ＮＷ），东北（ＮＥ），西南（ＳＷ），东南（ＳＥ）表示空间区域被分为n层，四叉树中的每级对应一个层次级别，层的数量n是依赖于所需要的精确度的。例如，2020年2月16日星期日11Ｒ-树Ｒ-树是Ｂ-树在多维空间的扩展其叶子节点包含多个形式为（OI，MBR）的实体，OI为空间目标标志，MBR为该目标在ｋ维空间中的最小包围矩形。非叶子节点包含多个形式为（CP，MBR）的实体。CP为指向子树根节点的指针，MBR为包围其子节点中所有MBR的最小包围矩形。Ｒ-树必须满足如下特性：若根节点不是叶子节点，则至少有两棵子树；除根之外的所有中间节点至多有Ｍ棵子树，至少有ｍ棵子树；每个叶子节点均包含ｍ至Ｍ个数据项；所有的叶子节点都出现在同一层次；所有节点都需要同样的存储空间（一个磁盘页）。2020年2月16日星期日12k-D树k-D树被设计用来对多属性的数据进行索引，而不是必要的空间数据。k-D树是二叉树的一个变种，树中的每一层用来索引一个属性。树中的每个结点表示这个空间基于一个分割点被分割成两个子集。和R-树一样，每个最低级别的区间只有一个实体。但是，分割不是用MBR来进行的。它首先按照一个维分割，然后按照另一个维分割，直到每个区间只有一个实体。2020年2月16日星期日13第八章空间挖掘内容提要引言空间数据概要空间数据挖掘基础，空间统计学泛化与特化空间规则空间分类算法空间聚类算法空间挖掘的其他问题空间数据挖掘原型系统介绍空间数据挖掘的研究现状与发展方向其他2020年2月16日星期日14空间数据库的操作是数据挖掘的基础假定A和B是二维空间中的两个空间实体。每个实体由空间中的点的集合组成：xa,ya∈A,xb,yb∈B。两个空间实体之间存在若干拓扑关系。这些关系基于两个实体的位置：分离（Disjoint）：A与B分离，表示B中任何点都不在A中，反之亦然。重叠/相交：A与B重叠或相交表示至少有一个点既在A里也在B里。等价：A与B这两个实体的所有点都是共有的。包含于：A包含于B，表示A的所有点都在B里。反之不一定。覆盖/包含：A覆盖或包含B，当且仅当B包含于A。根据实体在空间中的位置，可以定义方向，通常采用的是传统的地图方向：像东、南、西、北等等。空间谓词有三种形式：表示拓扑关系的谓词，如相交、覆盖等；表示空间方向的谓词，如东、西、左、右等；表示距离的谓词，如接近、远离等。2020年2月16日星期日15实体之间的距离的定义常用的两个空间实体之间的距离有：最小值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最小的，即最大值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最大的，即平均值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离的平均值，即中心方法：定义实体A和B的距离为A中的中心点与和B中的中心点之间的欧氏或曼哈顿距离的平均值，即)),(),,((min),(),(,),(bbaaByxAyxyxyxdisBAdisbbaa)),(),,((max),(),(,),(bbaaByxAyxyxyxdisBAdisbbaa)),(),,((),(),(,),(bbaaByxAyxyxyxdisaverageBAdisbbaa)),(),,((),(cbcbcacayxyxdisBAdis2020年2月16日星期日16空间统计学空间统计学（SpatialStatistics）是依靠有序的模型来描述无序事件，根据不确定性和有限的信息来分析、评价和预测空间数据。基于足够多的样本，在统计空间实体的几何特征量的最小值、最大值、均值、方差、众数或直方图的基础上，可以得到空间实体特征的先验概率，进而根据领域知识发现共性的几何知识。空间统计学具有较强的理论基础和大量的成熟算法。空间统计学是基本的数据挖掘技术，特别是多元统计分析（如判别分析、主成分分析、因子分析、相关分析、多元回归分析等）。统计方法是分析空间数据的最常用的方法。统计方法能够有效处理数值型数据，其主要方法是基于统计不相关假设的。在空间数据库中许多空间数据通常是相关的，即空间对象受其邻近对象的影响，难以满足这种假设，这样就会引起问题。它是空间统计学向着实用的挖掘技术发展的一个重要研究课题。统计方法对非线性规划不能很好建模，难以处理不完全或不确定性数据，而且运算的代价较高。它是空间统计学向着实用的挖掘技术发展的另一个研究课题。2020年2月16日星期日17第八章空间挖掘内容提要引言空间数据概要空间数据挖掘基础，空间统计学泛化与特化空间规则空间分类算法空间聚类算法空间挖掘的其他问题空间数据挖掘原型系统介绍空间数据挖掘的研究现状与发展方向其他2020年2月16日星期日18空间数据的蕴含着丰富的概念众所周知，概念层次