空间数据挖掘及技术(综述).ppt

1、空间数据挖掘技术及应用,中国地质大学（武汉）计算机学院,空间数据挖掘技术及应用,1.1 空间数据挖掘的产生与发展 1.2 空间数据挖掘方法及应用 1.3 GIS中数据挖掘的过程 1.4 GIS与空间数据挖掘的集成模式 1.5 空间数据库挖掘的研究趋势,1.1 空间数据挖掘的产生与发展,1.1.1 空间数据挖掘的概念 1.1.2 空间数据挖掘的特点 1.1.3 空间数据挖掘的产生 1.1.4 空间数据挖掘的发展现状,1.1.1 空间数据挖掘的概念,空间数据挖掘（Spatial Data Mining，SDM），是指从空间数据库中提取隐含的、用户感兴趣的空间和非空间的模式和普遍特征、空间数据与非空

2、间数据之间的普遍关系的过程。,1.1.2 空间数据挖掘的特点,与传统数据挖掘的不同： (1) 传统数据挖掘处理的是数字和类别，而空间数据则是一些更为复杂的数据类型，例如：点、线、多边形等对象； (2) 传统数据挖掘通常具有显式的输入，而空间数据挖掘的输入则常常是隐式的； (3) 在传统数据挖掘中，有一个至关重要的前提假设：数据样品是独立生成的。而这一假设在空间分析中是不成立的。事实上，空间数据之间是高度自关联的。,1.1.3 空间数据挖掘的产生,产生空间数据挖掘的推动力： (1) 空间信息正在逐步成为各种信息系统的主体和基础。它有着比一般关系数据库和事务数据库更加丰富和复杂的语义信息，包含着更

3、丰富的知识。 (2) 在地学领域，随着卫星和遥感技术的广泛应用，日益丰富的空间和非空间数据收集和存储在大空间数据库中，海量的地理数据在一定程度上已经超过了人们处理能力，同时传统地学分析难以胜任从这些海量的数据中提取和发现地学知识。 因此，迫切需要增强GIS分析功能，提高GIS解决地学问题的能力。数据挖掘与知识发现的出现很好地满足了地球空间数据处理的需要，推动了传统地学空间分析的发展。,1.1.4 空间数据挖掘的发展现状,武汉大学李德仁教授最早（1994年）关注到从GIS数据库中发现知识的问题，提出从GIS数据库可以发现包括普遍的几何知识、空间分布规律、空间关联规则、空间聚类规则、空间特征规则、

4、空间区分规则、空间演变规则和面向对象的知识。,目前，国际上最著名且有代表性的通用SDM系统有：GeoMiner,Descartes和ArcViewGIS的S_PLUS接口。 以上SDM系统的共同优点是把传统DM与地图可视化结合起来，提供聚类、分类等多种挖掘模式，但它们在空间数据的操作上实现方式不尽相同。,Descartes是专门的空间数据可视化工具，它和DM工具Kepler两者联合在一起才能完成SDM任务。 GeoMiner是在MapInfo平台上进行二次开发而成，系统庞大，造成较大的资源浪费。 S_PLUS的局限在于，它是用一种解释性语言（Script），功能的实现比用C和C+直接实现要慢得

5、多，所以只能使用于非常小的数据库应用。,1.2 空间数据挖掘方法及应用,1.2.1 空间关联分析 1.2.2 聚类分析 1.2.3 分类方法 1.2.4 统计方法 1.2.5 趋势分析,1.2.1空间关联分析,即空间关联规则发现： 形式：A =Bs%, c% A和B是空间和非空间谓词的集合，s%表示规则的支持度，c%表示规则的可信度。 例：is_a(X,”school”)close_to(X,”sports_center”) =close_to(X,”park”) 0.5%, 80% 此规则表明80%靠近体育中心的学校同时也靠近公园，并且有0.5%的数据符合这一规则。,构成空间关联规则的谓词：

6、 距离信息：close_to（临近）、far_away（远离） 拓扑关系：intersect（交）、overlap（重叠）、disjoin（分离） 空间方位：left_of（左边）、west_of（西部） 空间关联规则的挖掘需要在大量的空间对象中计算多种空间关系，代价极高。所以应采用逐步求精的挖掘优化方法（Koperski)： （1）通过空间查询从初始空间数据库中获得和任务相关的空间数据库； （2）使用一些有效空间挖掘算法计算对象之间的空间联接，从而获得一个候选谓词集合；,（3）对（2）中所得到的谓词集合中的每一个谓词计算其支持度，并且将那些支持度小于最小支持度的谓词删除； （4）对谓词集合进

7、行进一步精化以决定准确的空间关系； （5）以（4）所得的候选集作为输入，生成空间关联规则。 前期采用的粗略挖掘算法必须满足超级覆盖特性（superset coverage property）：即它保持了潜在的答案。,允许假正测试（false positive test），即可以包括一些不属于结果集的数据集； 不允许假负测试（false negative test），即不能排除一些潜在的答案。 例如，挖掘与空间谓词close_to有关的空间关联规则： （1）使用一定的近似空间计算算法：如用最小边界矩形结构（仅涉及两个空间点）； （2）计算放宽后的空间谓词，如g_close_to，它包括close

8、_to，touch和intersect的结果。,1.2.2 聚类分析,聚类（clustering）就是将数据对象分组成为多个类或簇（cluster），在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象分簇中的对象差别较大。 聚类分析是统计学的一个分支，与规则分类不同的是，聚类算法无需背景知识，能直接从空间数据库中发现有意义的空间聚类结构。,主要聚类方法的分类： 1. 划分方法： 给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇（即k个组），kn。同时要求： （1）每个划分至少包含一个对象 （2）每个对象必须属于且只属于一个组。 给定要构建的划分的数目k，

9、划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的准则：,在同一个类中的对象之间尽可能“接近”或相关；而不同类中的对象之间尽可能“远离”或不同。 流行的启发式方法：(1) k-平均算法；(2) k-中心点算法。 2.层次的方法：对给定数据对象集合进行层次的分解。 凝聚的方法：自底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件； 分裂的方法：自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中一个簇被分裂为更小的簇，直到最终每个对象在单

10、独的一个簇中，或者达到一个终止条件。,3. 基于密度的方法： 只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。 对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某给定数目的点。 这样的方法可以用来过滤“噪声”孤立点，发现任意形状的簇。 4. 基于网格的方法 5. 基于模型的方法,1.2.3 分类方法,空间分类发现的规则在模式识别、基于内容的查询、图象分类等应用中具有重要应用。 数据分类（data classification）是一个两步过程： （1）建立一个模型，描述预定的数据类集或概念集（或称作分类器）。 要构造分类器，需要有一个训练样本数据集作为输入。 训练集由

11、一组数据库记录或元组构成，每个元组是一个由有关字段（又称属性或特征）值组成的特征向量，此外，训练样本还有一个类别标记。 训练样本形式：(v1,v2,vn, c)；其中vi表示字段值，c表示类别。 （2）使用模型进行分类。,分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。机器学习方法包括决策树法和规则归纳法，神经网络法主要是BP算法。 决策树方法的分类稳定性优于神经网络方法。,1.2.4 统计方法,空间统计学（spatial statistics）是依靠有序的模型描述无序事件，根据不确定性和有限信息分析、评价和预测空间数据。 空间统计学是基本的数据挖掘技术，特别是多元统计分析（如判别

12、分析、主成分分析、因子分析、相关分析、多元回归分析等）。,1.2.5 趋势分析,空间趋势指的是离开一个给定的起始对象时，非空间属性的变化情况。 例如，当离城市中心越来越远时经济形势的变化趋势。 空间趋势分析的结果可能是正向趋势、反向趋势，或者是没有趋势。 一般而言，要在空间数据结构和空间访问方法之上分析空间趋势需要使用回归和相关的分析方法。,1.3 GIS中数据挖掘的过程,（1）根据一定的主题要求及相关背景知识，从现有的分布式空间数据库中提取数据并进行分析和处理，形成空间数据仓库； （2）根据确定的任务，选择合适的数据挖掘算法，包括合适的数据模型和参数，从空间数据仓库中挖掘用户所需要的知识信息

13、；,（3）对挖掘的知识进行评价，首先对其进行一致性检查，以确定本次挖掘的知识与以前挖掘的知识是否相互抵触。其次，判断受挖掘的知识是否满足要求，以决定是否重复挖掘或者反复挖掘,从而获取更加有效的知识信息； （4）对挖掘所得到的知识信息，通过特定的生动形象的可视化表达工具，以用户能够全面理解的方式呈现给用户。,GIS数据挖掘过程图,1.4 GIS与空间数据挖掘的集成模式,（1）松散耦合式-外部空间数据挖掘模式 这种模式基本上将GIS作为一个空间数据库看待，在GIS环境外部借助其它软件或计算机语言进行空间数据挖掘，其与GIS之间采用数据通讯的方式联系。,松散耦合式框架图,（2）嵌入式-内部空间数据挖掘模式,在GIS中将空间数据挖掘技术融合到空间分析功能中去。,（3）混合型空间模型法 是前两种方法的结合。即尽可能利用GIS提供的功能，最大限度的减少用户自行开发的工作量和难度，并保持外部空间数据挖掘模式的灵活性。,1.5 空间数据库挖掘的研究趋势,(1) 算法的效率 空间数据的复杂性和数据的大量性，TB数量级的数据库出现，必然增大发现算法的搜索空间,增加了搜索的盲目性； 提高算法效率成为空间挖掘算法在实际应用中的不可避免的巨大挑战。 (2) 数据挖掘方法和任务的多样性 现有空间挖掘方法与任务都是有限的。,(3) 对复杂空间数据库的处理 象面向对象