数据挖掘原理与算法

《数据挖掘原理与算法 》由会员分享，可在线阅读，更多相关《数据挖掘原理与算法 （54页珍藏版）》请在金锄头文库上搜索。

1、第八章 空间挖掘 内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他Date1空间挖掘技术概述 n大量的空间数据是从遥感、地理信息系统（GIS）、多媒 体系统、医学和卫星图像等多种应用中收集而来，收集到的 数据远远超过了人脑分析的能力。日益发展的空间数据基础 设施为空间数据的自动化处理提出了新的课题。n空间数据的最常用的数据组织形式是空间数据库。空间数 据库必须保存空间实体，这些空间实体是用空间数据类型和 实体的空间关系来表示出来的。空间数据库，不同

2、于关系数 据库，它一般具有空间拓扑或距离信息，通常需要以复杂的 多维空间索引结构组织。n空间挖掘（Spatial Mining）或被称作空间数据挖掘/空间 数据库的知识发现，是数据挖掘技术在空间数据方面的应用 。简言之，空间数据挖掘，就是从空间数据库中抽取隐含的 知识、空间关系或非显式地存储在空间数据库中的其他模式 ，用于理解空间数据、发现数据间（空间或非空间）的关系 。n由于空间数据的复杂性及其应用的专业性，在一般的数据 挖掘的基本概念的基础上，需要研究空间数据挖掘特有的理 论、方法和应用。Date2第八章 空间挖掘 内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n

3、空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他Date3空间数据的主要特点n空间数据是指与二维、三维或更高维空间的空间 坐标及空间范围相关的数据，例如地图上的经纬度 、湖泊、城市等。n访问空间数据要比访问非空间数据更复杂。对空 间数据的访问要使用专门的操作和数据结构。空间 数据可以用包含着诸如“接近、南、北、包含于” 等空间操作符的查询来访问。n空间数据存放在记录着实体的空间性数据和非空 间性数据的空间数据库里。由于空间数据关联着距 离信息，所以空间数据库通常用使用距离或拓扑信 息的空间数据结构或者索引来存储。就数据挖

4、掘而 论，这些距离信息提供了所需的相似性度量的基础 。Date4空间数据的复杂性特征n空间数据的复杂性特征主要表现在以下几个方面：n空间属性之间的非线性关系：空间属性之间的非线性关 系是空间系统复杂性的重要标志，被作为空间数据挖掘的主要 任务之一。n空间数据的多尺度特征：空间数据的多尺度性是指空间 数据在不同观察层次上所遵循的规律以及体现出的特征不尽相 同。多尺度特征是空间数据复杂性的又一表现形式。n空间信息的模糊性：模糊性几乎存在于各种类型的空间 信息中，如空间位置的模糊性、空间相关性的模糊性以及模糊 的属性值等等。n空间维数的增高：空间数据的属性增加极为迅速，如在 遥感领域，由于传感器技术

5、的飞速发展，波段的数目也由几个 增加到几十甚至上百个，如何从几十甚至几百维空间中提取信 息、发现知识则成为研究中的又一难题。n空间数据的缺值：数据的缺值现象源自由于某种不可抗 拒的外力而使数据无法获得或发生丢失。如何对丢失数据进行 恢复并估计数据的固有分布参数，成为解决数据复杂性的难点 。Date5空间查询问题n查询是挖掘的技术，空间查询及其操作的主要特点有：n空间操作相对复杂和不精确：传统的访问非空间数据的 选择查询使用的是标准的比较操作符：， A, B。两个空间 实体之间存在若干拓扑关系。这些关系基于两个实体的位置 ：n分离（Disjoint） ：A与B分离，表示B中任何点都不在 A中，反

6、之亦然。n重叠/相交： A与B重叠或相交表示至少有一个点既在A 里也在B里。n等价： A与B这两个实体的所有点都是共有的。n包含于： A包含于B，表示A的所有点都在B里。反之不 一定。n覆盖/包含： A覆盖或包含B，当且仅当B包含于A。n根据实体在空间中的位置，可以定义方向，通常采用的是 传统的地图方向：像东、南、西、北等等。n空间谓词有三种形式：n表示拓扑关系的谓词，如相交、覆盖等；n表示空间方向的谓词，如东、西、左、右等；n表示距离的谓词，如接近、远离等。Date15实体之间的距离的定义n常用的两个空间实体之间的距离有：n最小值方法：定义实体A和B的距离为A中的所有点与和B 中的所有点之间

7、的欧氏或曼哈顿距离中最小的，即n最大值方法：定义实体A和B的距离为A中的所有点与和B 中的所有点之间的欧氏或曼哈顿距离中最大的，即n平均值方法：定义实体A和B的距离为A中的所有点与和B 中的所有点之间的欧氏或曼哈顿距离的平均值，即n中心方法：定义实体A和B的距离为A中的中心点与和B中 的中心点之间的欧氏或曼哈顿距离的平均值，即Date16空间统计学n空间统计学（Spatial Statistics）是依靠有序的模型来描述无序事件， 根据不确定性和有限的信息来分析、评价和预测空间数据。n基于足够多的样本，在统计空间实体的几何特征量的最小值、最大值 、均值、方差、众数或直方图的基础上，可以得到空间

8、实体特征的先验 概率，进而根据领域知识发现共性的几何知识。n空间统计学具有较强的理论基础和大量的成熟算法。空间统计学是基 本的数据挖掘技术，特别是多元统计分析（如判别分析、主成分分析、 因子分析、相关分析、多元回归分析等）。n统计方法是分析空间数据的最常用的方法。统计方法能够有效处理数 值型数据，其主要方法是基于统计不相关假设的。在空间数据库中许多 空间数据通常是相关的，即空间对象受其邻近对象的影响，难以满足这 种假设，这样就会引起问题。它是空间统计学向着实用的挖掘技术发展 的一个重要研究课题。n统计方法对非线性规划不能很好建模，难以处理不完全或不确定性数 据，而且运算的代价较高。它是空间统计

9、学向着实用的挖掘技术发展的 另一个研究课题。Date17第八章 空间挖掘 内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他Date18空间数据的蕴含着丰富的概念n众所周知，概念层次的使用显示了数据间关系的 层次。应用空间数据特性，概念层次承认了层级中 不同层次规则和关系的发展。n从空间数据中挖掘所蕴含的概念是空间挖掘的重 要任务之一。n泛化与特化是概念归纳的主要手段，它对空间数 据挖掘也是如此。Date19逐步求精的分层技术n逐步求精（Progre

10、ssive Refinement）的分层是基 于空间关系的，因此空间关系可以应用在一个更粗 糙或者更精细的层次上。n由于空间应用的数据量十分庞大，在寻求更多精 确响应之前要先做出一些近似响应。MBR就是一个 近似物体形状的办法。四叉树、R-树和其他大多数 空间索引技术都采用了一种逐步求精的方式。n逐步求精可以看作是对处理问题无用的数据所做 的过滤。Date20泛化n数据库中的数据和对象在原始的概念层次包含有详细的信 息，经常需要将大量数据的集合进行概括并以较高的概念层 次展示，即对数据进行泛化。n基于泛化的数据挖掘方法假定背景知识以概念层次的形式 存在。概念层次可由专家提供，或借助数据分析自动

11、生成。n空间数据库中可以定义两种类型的概念层次：n空间概念层：地理区域之间空间关系的概念层次。n非空间概念层：非空间属性所联系的非空间数据对应的 概念层次。n空间数据应用的归纳可以被分为两种子类：n空间数据支配泛化：空间数据支配泛化做的是基于空间 位置的聚类（所有靠近的实体被分在一组中）。n非空间数据支配泛化：根据非空间属性值的相似性做聚 类。Date21空间数据支配泛化算法n在空间数据支配泛化算法中，首先对空间数据进行归纳： 归纳进行至区域的数量达到阈值为止。然后对相关的非空间 属性做相应地更改。n例如，要知道我国西北部地区的平均降雨量，可以在空 间层次中寻找西北部所有省，再对非空间属性（降

12、雨量）进行 比较，或者归纳（平均降雨量多、中等、少量等）。n典型的空间数据支配泛化算法描述: 算法8-1空间数据支配泛化算法 输入：空间数据库D；空间层次H；概念层次C；查询Q。 输出：所需一般特征的规则r。 （1）D从数据库D中按查询Q获得的数据集合； （2）根据H的结构，把数据合并到区域中，直到区域的数目达到所需的阈值，或者已经到达H中所 要求的层次； （3）FOR each 所找的区域 DO BEGIN （4） 对非空间属性执行面向属性的归纳； （5） 产生并输出所找到的泛化规则； （6）END.Date22非空间数据支配泛化算法n算法首先对非空间属性作面向属性的归纳，将其 泛化至更高的

13、概念层次。然后，将具有相同的泛化 属性值的相邻区域合并在一起，可用邻近方法忽略 具有不同非空间描述的小区域。n查询的结果生成包含少量区域的地图，这些区域 共享同一层次的非空间描述。Date23统计信息网格方法STING介绍n统计学信息网格方法（STatistical INformation Grid-based methodSTING），使用了一种类似四叉树的分层技术，把 空间区域分成矩形单元。对空间数据库扫描一次，可以找到 每个单元的统计参数（平均数，变化性，分布类型）。网格 结构中的每个结点概括了该网格中所含内部属性的信息。通 过获取这些信息，很多数据挖掘请求（包括聚类）都可以通 过检验单

14、元统计得到响应。nSTING方法可以看作是一种层次聚类技术。层级的顶层的 组成就是整体空间。最低层是代表每个最小单元的叶子结点 。如果使用一个单元在下一层中拥有四个子单元（网格）的 话，单元的分割与四叉树中是一样的。Date24第八章 空间挖掘 内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他Date25空间规则的主要类型n空间规则可以概括对空间实体的结构及其之间关 系的描述。在空间数据挖掘中有三种类型的规则：n空间特性规则：描述数据，如北京市家庭

15、平均 年收入为30000元。n空间判别规则：描述不同种类数据间的差异， 依靠它们能够区分不同种类的特点。如北京市家庭 平均年收入为30000元，而上海的家庭平均年收入为 35000元。n空间关联规则：是两个数据集合之间的关联。 如在北京市、住在国贸附近的家庭的平均收入为 50000元。n所有这些规则都可以被看作是对空间类型的描述 ，而描述是一种为数据库或者其中一些子集找到一 个表示的方法。特性规则是一种最简化的形式。Date26空间关联规则n空间关联规则是空间数据实体之间的关联，有：n非空间的先决条件和空间性的结果：如在北京、所有的 重点学校都是位于老住宅区附近。n空间性先决条件和非空间的结果

16、：如在北京、房子在国 贸附近，就比较贵。n空间性先决条件和空间性结果：如在北京、所有市区的 房子都在三环以内。n空间关联规则挖掘是传统关联规则挖掘的延伸，常用最小 支持度和最小可信度来作为基本的统计参数，由于空间数据 的特点，往往是在多层概念上进行归纳。n挖掘空间关联规则的有效方法是自上而下、逐步加深的搜 索技术。首先在高的概念层次进行搜索，在较粗的精度级别 查找频繁发生的模式和在这些模式中较强的隐含关系；然后 ，对频繁发生的模式加深搜索至较低的概念层次，这种处理 持续到找不到频繁发生的模式为止。Date27空间关联规则基本步骤n典型的五步算法：n步骤1：通过给定的查询抽取出相关的数据。n步骤2：应用一个粗的空间运算方法，计算整个相关数 据的集合。n步骤3：过滤出那些支持度小于最小支持度阈值的1阶谓 词。n步骤4：应用一个细化的空间计算方法，从所导出的粗 的谓词集合中计算谓词。n步骤5：向低层深入，在多个概念层次上找到关联规则 的完整集合。算法8-4 空间关联规则算法 输入：空间数据库D；概念层次C；层次的最小支持度和可信度s和；寻找感兴趣