《数据挖掘原理与算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据挖掘原理与算法幻灯片.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据挖掘原理与算法2022/9/231第1页，共54页，编辑于2022年，星期六空间挖掘技术概述 n大量的空间数据是从遥感、地理信息系统（GIS）、多媒体系统、医学和卫星图像等多种应用中收集而来，收集到的数据远远超过了人脑分析的能力。日益发展的空间数据基础设施为空间数据的自动化处理提出了新的课题。n空间数据的最常用的数据组织形式是空间数据库。空间数据库必须保存空间实体，这些空间实体是用空间数据类型和实体的空间关系来表示出来的。空间数据库，不同于关系数据库，它一般具有空间拓扑或距离信息，通常需要以复杂的多维空间索引结构组织。n空间挖掘（Spatial Mining）或被称作空间数据挖掘/空间数据
2、库的知识发现，是数据挖掘技术在空间数据方面的应用。简言之，空间数据挖掘，就是从空间数据库中抽取隐含的知识、空间关系或非显式地存储在空间数据库中的其他模式，用于理解空间数据、发现数据间（空间或非空间）的关系。n由于空间数据的复杂性及其应用的专业性，在一般的数据挖掘的基本概念的基础上，需要研究空间数据挖掘特有的理论、方法和应用。2022/9/232第2页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的
3、研究现状与发展方向n其他2022/9/233第3页，共54页，编辑于2022年，星期六空间数据的主要特点n空间数据是指与二维、三维或更高维空间的空间坐标及空间范围相关的数据，例如地图上的经纬度、湖泊、城市等。n访问空间数据要比访问非空间数据更复杂。对空间数据的访问要使用专门的操作和数据结构。空间数据可以用包含着诸如“接近、南、北、包含于”等空间操作符的查询来访问。n空间数据存放在记录着实体的空间性数据和非空间性数据的空间数据库里。由于空间数据关联着距离信息，所以空间数据库通常用使用距离或拓扑信息的空间数据结构或者索引来存储。就数据挖掘而论，这些距离信息提供了所需的相似性度量的基础。2022/9
4、/234第4页，共54页，编辑于2022年，星期六空间数据的复杂性特征空间数据的复杂性特征n空间数据的复杂性特征主要表现在以下几个方面：n空间属性之间的非线性关系：空间属性之间的非线性关系：空间属性之间的非线性关系是空间系统复杂性的重要标志，被作为空间数据挖掘的主要任务之一。n空间数据的多尺度特征：空间数据的多尺度特征：空间数据的多尺度性是指空间数据在不同观察层次上所遵循的规律以及体现出的特征不尽相同。多尺度特征是空间数据复杂性的又一表现形式。n空间信息的模糊性：空间信息的模糊性：模糊性几乎存在于各种类型的空间信息中，如空间位置的模糊性、空间相关性的模糊性以及模糊的属性值等等。n空间维数的增高
5、：空间维数的增高：空间数据的属性增加极为迅速，如在遥感领域，由于传感器技术的飞速发展，波段的数目也由几个增加到几十甚至上百个，如何从几十甚至几百维空间中提取信息、发现知识则成为研究中的又一难题。n空间数据的缺值：空间数据的缺值：数据的缺值现象源自由于某种不可抗拒的外力而使数据无法获得或发生丢失。如何对丢失数据进行恢复并估计数据的固有分布参数，成为解决数据复杂性的难点。2022/9/235第5页，共54页，编辑于2022年，星期六空间查询问题空间查询问题n查询是挖掘的技术，空间查询及其操作的主要特点有：n空间操作相对复杂和不精确：空间操作相对复杂和不精确：传统的访问非空间数据的选择查询使用的是标
6、准的比较操作符：，。而空间选择是一种在空间数据上的选择查询，要用到空间操作符，包括接近、东、西、南、北、包含、重叠或相交等。下面是几个空间选择查询的例子：n例如，“查找北海公园附近的房子”。n空间连接（空间连接（Spatial JoinSpatial Join）问题：）问题：在两个空间关系上的一个空间性连接操作被称为空间连接（Spatial Join）。在空间连接中，关系都是空间性的，需要与空间连接对应的条件描述。n例如，“相交”关系用于多边形；“相邻”关系用于点。n相同的地理区域经常有不同的视图：相同的地理区域经常有不同的视图：一个区域不同的视图（如基础设施、城市规划、绿化等）保存在单独的G
7、IS文件中，融合这些数据，通常需要一个称为“地图覆盖”（Map Overlay）的操作来实现。n一个空间实体可用空间和非空间的属性来描述。当其空间属性用一些空间数据结构存储起来之后，非空间属性就可以存储在一个关系数据库里。对空间数据库来说，不同的空间实体经常是和不同的位置相关联的，而且在不同的实体之间进行空间性操作的时候，经常需要在属性之间进行一些转换。2022/9/236第6页，共54页，编辑于2022年，星期六空间数据结构n由于空间数据的独特性质，有很多数据结构专门被设计用来存储或索引空间数据。这些结构有的考虑的是空间实体的轮廓表示，有的是空间数据的索引方法。n空间实体表示的最常用方法是“
8、最小包围矩形”。n空间索引技术大多是基于对空间目标的近似技术，例如，n空间映射法n（1 1）采用低维空间向高维空间映射的方式：）采用低维空间向高维空间映射的方式：维空间具有个顶点的目标可以映射成*维空间的点。映射后，可以直接采用点索引技术。n（2 2）直接向一维空间映射：）直接向一维空间映射：通常数据空间被划分成大小相同的网格单元，通过给这些网格单元编码形成一维目标，用传统的一维的索引结构（如+树等）索引。n分割方法n（1 1）采用不允许空间重叠的索引方法：）采用不允许空间重叠的索引方法：将所在的数据空间按某种方法（如二叉树划分、四叉树划分、格网划分等）划分成彼此不相交的子空间。n（2 2）采
9、用允许空间重叠的索引法：）采用允许空间重叠的索引法：将索引空间划分为多级的子空间，这些子空间允许重叠，但是一个空间实体完全包含在某一子空间中。2022/9/237第7页，共54页，编辑于2022年，星期六最小包围矩形n通过完整包含一个空间实体的最小包围矩形（MBR：Minimum Bounding Rectangle）来表示该空间实体。例如，下图显示一湖泊的MBR：n如果用传统坐标系统来对这个湖定向，水平轴表示东西方向，垂直轴表示南北方向，那么就可以把这个湖放在一个矩形里（中间图所示）n还可以通过一系列更小的矩形来表现这个湖（右图所示）n另一种更简单的方法是用一对不相邻的顶点坐标来表示一个MB
10、R，如用(x1，y1)，(x2，y2)来表示（中间图所示）。2022/9/238第8页，共54页，编辑于2022年，星期六空间索引技术n空间索引是指依据空间实体的位置和形状或空间实体之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间实体的概要信息。n空间索引的性能优劣直接影响空间数据库和地理信息系统的整体性能，也对空间数据挖掘的效率有影响。n几种比较有代表性的空间数据索引结构技术：n网格文件 n四叉树 nR-树nk-D树 2022/9/239第9页，共54页，编辑于2022年，星期六网格文件n根据正交的网格划分维的数据空间。维数据空间的网格由个一维数组表示，这些数组称为刻度，将其保
11、存在主存。刻度的每一边界构成-1维的超平面。整个数据空间被所有的边界划分成许多维的矩形子空间，这些矩形子空间称为网格目录，用维的数组表示，将其保存在硬盘上。网格目录的每一网格单元包含一外存页的地址，这一外存页存储了该网格单元内的数据目标，称为数据页。一数据页允许存储多个相邻网格单元的目标。网格文件的查找简单，查找效率较高，适用于点目标的索引。2022/9/2310第10页，共54页，编辑于2022年，星期六四叉树n四叉树通过把空间按等级分解成为区域（单元）来表示空间实体。四叉树实际上每一节点有4个子树，用于对空间点的表示与索引。n如二维空间的四叉树，每个子节点对应一个矩形，用四种方位西北（），
12、东北（），西南（），东南（）表示n空间区域被分为n层，四叉树中的每级对应一个层次级别，层的数量n是依赖于所需要的精确度的。例如，2022/9/2311第11页，共54页，编辑于2022年，星期六-树n-树是-树在多维空间的扩展n其叶子节点包含多个形式为（OI，MBR）的实体，OI为空间目标标志，MBR为该目标在维空间中的最小包围矩形。n非叶子节点包含多个形式为（CP，MBR）的实体。CP为指向子树根节点的指针，MBR为包围其子节点中所有MBR的最小包围矩形。n-树必须满足如下特性：n若根节点不是叶子节点，则至少有两棵子树；n除根之外的所有中间节点至多有棵子树，至少有棵子树；n每个叶子节点均包含
13、至个数据项；n所有的叶子节点都出现在同一层次；n所有节点都需要同样的存储空间（一个磁盘页）。2022/9/2312第12页，共54页，编辑于2022年，星期六k-D树nk-D树被设计用来对多属性的数据进行索引，而不是必要的空间数据。k-D树是二叉树的一个变种，树中的每一层用来索引一个属性。树中的每个结点表示这个空间基于一个分割点被分割成两个子集。n和R-树一样，每个最低级别的区间只有一个实体。但是，分割不是用MBR来进行的。它首先按照一个维分割，然后按照另一个维分割，直到每个区间只有一个实体。2022/9/2313第13页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容
14、提要内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他2022/9/2314第14页，共54页，编辑于2022年，星期六空间数据库的操作是数据挖掘的基础n假定A 和B是二维空间中的两个空间实体。每个实体由空间中的点的集合组成：A,B。两个空间实体之间存在若干拓扑关系。这些关系基于两个实体的位置：n分离（Disjoint）：A与B分离，表示B中任何点都不在A中，反之亦然。n重叠/相交：A与B重叠或相交表示至少有一个点既在A里也在B里。n等价：A与B这两
15、个实体的所有点都是共有的。n包含于：A包含于B，表示A的所有点都在B里。反之不一定。n覆盖/包含：A覆盖或包含B，当且仅当B包含于A。n根据实体在空间中的位置，可以定义方向，通常采用的是传统的地图方向：像东、南、西、北等等。n空间谓词有三种形式：n表示拓扑关系的谓词，如相交、覆盖等；n表示空间方向的谓词，如东、西、左、右等；n表示距离的谓词，如接近、远离等。2022/9/2315第15页，共54页，编辑于2022年，星期六实体之间的距离的定义n常用的两个空间实体之间的距离有：n最小值方法：最小值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最小的，即n最大值方
16、法：最大值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最大的，即n平均值方法：平均值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离的平均值，即n中心方法：中心方法：定义实体A和B的距离为A中的中心点与和B中的中心点之间的欧氏或曼哈顿距离的平均值，即2022/9/2316第16页，共54页，编辑于2022年，星期六空间统计学n空间统计学（Spatial Statistics）是依靠有序的模型来描述无序事件，根据不确定性和有限的信息来分析、评价和预测空间数据。n基于足够多的样本，在统计空间实体的几何特征量的最小值、最大值、均值、方
17、差、众数或直方图的基础上，可以得到空间实体特征的先验概率，进而根据领域知识发现共性的几何知识。n空间统计学具有较强的理论基础和大量的成熟算法。空间统计学是基本的数据挖掘技术，特别是多元统计分析（如判别分析、主成分分析、因子分析、相关分析、多元回归分析等）。n统计方法是分析空间数据的最常用的方法。统计方法能够有效处理数值型数据，其主要方法是基于统计不相关假设的。在空间数据库中许多空间数据通常是相关的，即空间对象受其邻近对象的影响，难以满足这种假设，这样就会引起问题。它是空间统计学向着实用的挖掘技术发展的一个重要研究课题。n统计方法对非线性规划不能很好建模，难以处理不完全或不确定性数据，而且运算的
18、代价较高。它是空间统计学向着实用的挖掘技术发展的另一个研究课题。2022/9/2317第17页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他2022/9/2318第18页，共54页，编辑于2022年，星期六空间数据的蕴含着丰富的概念n众所周知，概念层次的使用显示了数据间关系的层次。应用空间数据特性，概念层次承认了层级中不同层次规则和关系的发展。n从空间数据中挖掘所蕴含的概
19、念是空间挖掘的重要任务之一。n泛化与特化是概念归纳的主要手段，它对空间数据挖掘也是如此。2022/9/2319第19页，共54页，编辑于2022年，星期六逐步求精的分层技术n逐步求精（Progressive Refinement）的分层是基于空间关系的，因此空间关系可以应用在一个更粗糙或者更精细的层次上。n由于空间应用的数据量十分庞大，在寻求更多精确响应之前要先做出一些近似响应。MBR就是一个近似物体形状的办法。四叉树、R-树和其他大多数空间索引技术都采用了一种逐步求精的方式。n逐步求精可以看作是对处理问题无用的数据所做的过滤。2022/9/2320第20页，共54页，编辑于2022年，星期六
20、泛化n数据库中的数据和对象在原始的概念层次包含有详细的信息，经常需要将大量数据的集合进行概括并以较高的概念层次展示，即对数据进行泛化。n基于泛化的数据挖掘方法假定背景知识以概念层次的形式存在。概念层次可由专家提供，或借助数据分析自动生成。n空间数据库中可以定义两种类型的概念层次：n空间概念层：地理区域之间空间关系的概念层次。n非空间概念层：非空间属性所联系的非空间数据对应的概念层次。n空间数据应用的归纳可以被分为两种子类：n空间数据支配泛化：空间数据支配泛化做的是基于空间位置的聚类（所有靠近的实体被分在一组中）。n非空间数据支配泛化：根据非空间属性值的相似性做聚类。2022/9/2321第21
21、页，共54页，编辑于2022年，星期六空间数据支配泛化算法n在空间数据支配泛化算法中，首先对空间数据进行归纳：归纳进行至区域的数量达到阈值为止。然后对相关的非空间属性做相应地更改。n例如，要知道我国西北部地区的平均降雨量，可以在空间层次中寻找西北部所有省，再对非空间属性（降雨量）进行比较，或者归纳（平均降雨量多、中等、少量等）。n典型的空间数据支配泛化算法描述:算法算法8-1空间数据支配泛化算法输入：空间数据库D；空间层次H；概念层次C；查询Q。输出：所需一般特征的规则r。（1）D从数据库D中按查询Q获得的数据集合；（2）根据H的结构，把数据合并到区域中，直到区域的数目达到所需的阈值，或者已经
22、到达H中所要求的层次；（3）FOR each 所找的区域 DO BEGIN（4）对非空间属性执行面向属性的归纳；（5）产生并输出所找到的泛化规则；（6）END.2022/9/2322第22页，共54页，编辑于2022年，星期六非空间数据支配泛化算法非空间数据支配泛化算法n算法首先对非空间属性作面向属性的归纳，将其泛化至更高的概念层次。然后，将具有相同的泛化属性值的相邻区域合并在一起，可用邻近方法忽略具有不同非空间描述的小区域。n查询的结果生成包含少量区域的地图，这些区域共享同一层次的非空间描述。2022/9/2323第23页，共54页，编辑于2022年，星期六统计信息网格方法统计信息网格方法S
23、TINGSTING介绍介绍n统计学信息网格方法（STatistical INformation Grid-based methodSTING），使用了一种类似四叉树的分层技术，把空间区域分成矩形单元。对空间数据库扫描一次，可以找到每个单元的统计参数（平均数，变化性，分布类型）。网格结构中的每个结点概括了该网格中所含内部属性的信息。通过获取这些信息，很多数据挖掘请求（包括聚类）都可以通过检验单元统计得到响应。nSTING方法可以看作是一种层次聚类技术。层级的顶层的组成就是整体空间。最低层是代表每个最小单元的叶子结点。如果使用一个单元在下一层中拥有四个子单元（网格）的话，单元的分割与四叉树中是一样
24、的。2022/9/2324第24页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他2022/9/2325第25页，共54页，编辑于2022年，星期六空间规则的主要类型n空间规则可以概括对空间实体的结构及其之间关系的描述。在空间数据挖掘中有三种类型的规则：n空间特性规则：描述数据，如北京市家庭平均年收入为30000元。n空间判别规则：描述不同种类数据间的差异，依靠它们能够区分
25、不同种类的特点。如北京市家庭平均年收入为30000元，而上海的家庭平均年收入为35000元。n空间关联规则：是两个数据集合之间的关联。如在北京市、住在国贸附近的家庭的平均收入为50000元。n所有这些规则都可以被看作是对空间类型的描述，而描述是一种为数据库或者其中一些子集找到一个表示的方法。特性规则是一种最简化的形式。2022/9/2326第26页，共54页，编辑于2022年，星期六空间关联规则n空间关联规则是空间数据实体之间的关联，有：n非空间的先决条件和空间性的结果：如在北京、所有的重点学校都是位于老住宅区附近。n空间性先决条件和非空间的结果：如在北京、房子在国贸附近，就比较贵。n空间性先
26、决条件和空间性结果：如在北京、所有市区的房子都在三环以内。n空间关联规则挖掘是传统关联规则挖掘的延伸，常用最小支持度和最小可信度来作为基本的统计参数，由于空间数据的特点，往往是在多层概念上进行归纳。n挖掘空间关联规则的有效方法是自上而下、逐步加深的搜索技术。首先在高的概念层次进行搜索，在较粗的精度级别查找频繁发生的模式和在这些模式中较强的隐含关系；然后，对频繁发生的模式加深搜索至较低的概念层次，这种处理持续到找不到频繁发生的模式为止。2022/9/2327第27页，共54页，编辑于2022年，星期六空间关联规则基本步骤n典型的五步算法：n步骤步骤1 1：通过给定的查询抽取出相关的数据。：通过给
27、定的查询抽取出相关的数据。n步骤步骤2 2：应用一个粗的空间运算方法，计算整个相关数据的集合。：应用一个粗的空间运算方法，计算整个相关数据的集合。n步骤步骤3 3：过滤出那些支持度小于最小支持度阈值的：过滤出那些支持度小于最小支持度阈值的1 1阶谓词。阶谓词。n步骤步骤4 4：应用一个细化的空间计算方法，从所导出的粗的谓词集合中计算谓词。：应用一个细化的空间计算方法，从所导出的粗的谓词集合中计算谓词。n步骤步骤5 5：向低层深入，在多个概念层次上找到关联规则的完整集合。：向低层深入，在多个概念层次上找到关联规则的完整集合。算法算法8-4 空间关联规则算法输入：空间数据库D；概念层次C；层次的最
28、小支持度和可信度s和；寻找感兴趣实体的查询q；感兴趣的拓扑关系p。输出：空间关联规则R。（1）D=q(D)；（2）在D 中应用粗糙谓词，建造CP；/CP是由满足D中实体对的粗糙谓词组成的（3）通过寻找满足s的粗糙谓词来找到频繁粗糙谓词FCP；（4）从FCP中找到频繁精确谓词FFP；（5)寻找所有的频繁精确谓词得到R，然后归纳准则.2022/9/2328第28页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间
29、数据挖掘的研究现状与发展方向n其他2022/9/2329第29页，共54页，编辑于2022年，星期六空间分类方法n空间分类方法用来对空间实体的集合进行分类。给空间实体分类，可以通过非空间属性或空间属性或二者结合，并可利用概念层次来进行取样。对于样本数据的训练可以通过改造传统的分类算法来完成，例如，对ID3算法扩展。2022/9/2330第30页，共54页，编辑于2022年，星期六空间决策树n建造一个决策树，有五个主要步骤：n根据已知的分类，从数据D中找到例子S。n确定最佳谓词p用来分类。一般首先在较粗的层次中寻找相关谓词，然后再在较为细化的层次。n找到最佳的缓冲区大小和形状。对于取样中的每个实
30、体，它周围的区域被称为缓冲区。目标是选择一个能产生对测试集中的类型进行最不同的缓冲区。n使用p和C，对每个缓冲区归纳谓词。n使用泛化的谓词和ID3建造二叉树T。算法算法8-5 空间决策树算法输入：空间数据库D；概念层次C；预定的类别。输出：二叉决策树T。（1）根据预定的类别，从数据D中找到例子S；（2）确定最佳谓词p用来分类；（3）找到最佳的缓冲区大小和形状；（4）使用p和C，对每个缓冲区归纳谓词；（5）使用泛化的谓词和ID3建造二叉树T.2022/9/2331第31页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间数据挖掘基础，
31、空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他2022/9/2332第32页，共54页，编辑于2022年，星期六空间聚类n空间聚类算法必须在大型多维数据库上有效工作，而且应该能够探测到不同形状的聚类。因此，难度和挑战性要比传统数据要大。n空间聚类找到的聚类不应该依赖于检验空间中的点的顺序，而且聚类也不应该受不相干的点影响。n传统的聚类算法可以通过改造来实现空间数据聚类。2022/9/2333第33页，共54页，编辑于2022年，星期六基于随机搜索的聚类方法CLARANS扩展 nCLARANS算法
32、可以表示为查找一个图，图中的每个节点都是潜在的解决方案。在替换一个中心点后获得的聚类称为当前聚类的邻居。随意测试的邻居的数目由参数maxneighbor限制。如果找到一个更好的邻居，将中心点移至邻居节点，重新开始上述过程，否则在当前的聚类中生成一个局部最优。找到一个局部最优后，再任意选择一个新的节点重新寻找新的局部最优。局部最优的数目被参数numlocal限制。nCLARANS并不搜索遍所有的求解空间，也不限制在任何具体的采样中。CLARANS每次迭代的计算复杂度与对象的数量基本呈线性关系。n基于CLARANS的空间数据聚类算法有两种：空间支配算法SD（CLARANS）和非空间支配算法NSD（
33、CLARANS）。2022/9/2334第34页，共54页，编辑于2022年，星期六DBCLASD算法n一种大型空间数据库基于距离分布的聚类算法，叫做DBCLASD（Distribution Based Clustering of Large Spatial Databases），它是DBSCAN 的扩展。假定聚类中的项目是均匀分布的，算法尝试确定满足最近邻居距离的分布。只要最近的邻居距离满足均一分布的假设，那么这个元素就被加入聚类。算法算法8-7 DBCLASD算法输入：要被聚类的空间实体D；输出：聚类集合K。（1）K0；/初始化，没有聚类（2）c；/初始化候选集合为空（3）FOR each
34、 point p in D DO BEGIN（4）IF p is not in a cluster THEN BEGIN（5）创建一个新的聚类C，并把p加入C；（6）把p临近的点加入C；（7）END（8）FOR each point q in C DO BEGIN（9）把C中没有处理过的点q的邻居点加入C；（10）KKC（11）END.2022/9/2335第35页，共54页，编辑于2022年，星期六BANGBANG算法算法nBANG方法使用了一种类似k-D树的网格结构。这个结构为适应属性的分布而做了一定调整，使密集的区域具有大量的更小的网格，而不够密集的区域只有少量的更大的网格。接着按照网格
35、（块）的密度排序，也就是按照区域分割的网格里的项目数量。n根据期望的聚类数量，那些密度最大的网格被选为聚类的中心。对于每个选定的网格，只要它们的密度小于或者等于当前这个聚类的中心，就把这个临近的网格加入。2022/9/2336第36页，共54页，编辑于2022年，星期六小波聚类n用小波聚类归纳空间聚类的方法是把数据看作像STING那样的信号，小波聚类使用的是网格。归纳聚类的时间复杂度是O(n)，并且不受外界影响。n与一些方法不同，小波聚类可以找到任意形状的聚类，而且不需要知道期望的聚类个数。n维空间的空间实体集合可看作是一个信号。聚类的边界与高频相应。聚类本身是低频率高振幅的。可以使用信号处理
36、技术寻找空间中低频的部分。n可以使用小波变换来寻找聚类。小波变换是用来找出信号中的频谱的。一个空间实体的小波变换分解维空间图像的层次。它们可以用来把一个图像缩放为不同的大小。2022/9/2337第37页，共54页，编辑于2022年，星期六使用近似值来确定聚类的特性n一旦找到了空间聚类，可以使用近似值来确定这些聚类的特性：通过确定聚类附近的特征实现的。例如，一个聚类“靠近学校”。n通常更多地用复杂的近似多边形表示，而非指用简单的MBR。n聚合邻近定义为衡量一个聚类（或者元素群）与一个特征（或者空间中某个实体）接近的程度。聚合邻近距离可以由聚类中所有点的距离总和来度量。CRH算法是典型的确定聚合
37、邻近关系方法。它使用三种几何形状来界定一个聚类：内接矩形R：包含了一系列点的MBR。矩形边缘与坐标轴平行。外接圆C：包围一系列点的圆周；以内接矩形的对角线为直径。凸多边形H：包含点的集合的最小边界。CRH首先使用一个外接圆来接近给定的类；其次使用内接矩形来表示特征，并根据特征与聚类的接近程度来进行排序；最后使用凸多边形来评估前面所有最接近的特征。2022/9/2338第38页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原
38、型系统介绍n空间数据挖掘的研究现状与发展方向n其他2022/9/2339第39页，共54页，编辑于2022年，星期六空间挖掘的其他问题1 1空间在线分析挖掘空间在线分析挖掘n空间在线分析挖掘（SOLAM：Spatial Online Analytical Mining）建立在多维视图基础之上，是基于网络的验证型空间数据挖掘和分析工具。n空间在线分析挖掘通过数据分析与报表模块的查询和分析工具（OLAP、决策分析、数据挖掘）完成对信息和知识的提取，以满足决策的需要。它建立在客户/服务器的结构之上，由用户驱动，支持多维数据分析，在用户的指导下验证设定的假设。n美国BusinessObjects公司的
39、BusinessObjects（BO）就是采用Dataarehouse+OLAP+DataMining方案推出的第一个集多数据源查询、任意报表生成和OLAP及数据挖掘技术为一体的决策支持工具软件包。2022/9/2340第40页，共54页，编辑于2022年，星期六空间挖掘的其他问题2 2挖掘图像数据库的方法挖掘图像数据库的方法n图像数据库是一类特殊的空间数据库，其数据几乎全部是图像或图片。图像数据库用于遥感、医学图像等应用，通常以栅格形式表示，栅格代表一个或多个光谱范围的图像密度。n图像数据库的挖掘可以看成是空间数据挖掘的一部分，其主要问题在于如何区分图像。以下列出对这方面问题的一些研究。nM
40、agellanMagellan研究研究n恒星分类恒星分类nPOSS-II POSS-II（Second Palomar Observatory Sky SurveySecond Palomar Observatory Sky Survey）n基于内容的时空查询CONQUEST 2022/9/2341第41页，共54页，编辑于2022年，星期六空间挖掘的其他问题3 3基于基于RoughRough集方法集方法nRough集理论被广泛研究并应用于不精确、不确定、不完全的信息的分类分析和知识获取中。Rough集理论为空间数据的属性分析和知识发现开辟了一条新途径，可用于空间数据库属性表的一致性分析、属性
41、的重要性、属性依赖、属性表简化、最小决策和分类算法生成等。Rough集方法与其他知识发现方法相结合，可以在数据库中数据不确定情况下获取多种知识。4 4基于云理论挖掘方法基于云理论挖掘方法n云理论是由李德毅等提出的一种用于处理不确定性的新理论，由云模型、不确定性推理和云变换三大支柱构成。云理论将模糊性和随机性结合起来，解决了作为模糊集理论基石的隶属函数概念的固有缺陷，为KDD中定量与定性相结合的处理方法奠定了基础，可以用于处理GIS中融随机性和模糊性为一体的属性不确定性。2022/9/2342第42页，共54页，编辑于2022年，星期六空间挖掘的其他问题5 5探测性的数据分析（探测性的数据分析（
42、EDAEDA）n探测性的数据分析，简称EDA，采用动态统计图形和动态链接窗口技术将数据及其统计特征显示出来，可发现数据中非直观的数据特征及异常数据。EDA技术在知识发现中用于选取感兴趣的数据子集，即数据聚焦，并可初步发现隐含在数据中的某些特征和规律。6 6可视化可视化n现代的数据可视化（Data Visualization）技术是指运用计算机图形学和图像处理技术，将数据转换为图形或图像在屏幕上显示出来，并进行交互处理的理论、方法和技术。它涉及到计算机图形学、图像处理、计算机辅助设计、计算机视觉及人机交互技术等多个领域。数据可视化概念首先来自科学计算可视化。2022/9/2343第43页，共54
43、页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他2022/9/2344第44页，共54页，编辑于2022年，星期六空间数据挖掘原型系统介绍 加拿大Simon Fraser大学开发的空间数据挖掘系统原型GeoMiner很有代表性。该系统包含有三大模块：空间数据立方体构建模块，空间联机分析处理（OLAP）模块和空间数据挖掘模块，采用的空间数据挖掘语言是GMQL。目前已能挖掘三种类型的规
44、则：特征规则、判别规则和关联规则。GeoMiner的体系结构如图8-12所示，包含四个部分：n图形用户界面，用于进行交互式地挖掘并显示挖掘结果；n发现模块集合，含有上述三个已实现的知识发现模块以及四个计划实现的模块（分别用实线框和虚线框表示）；n空间数据库服务器，包括MapInfo、ESRI/Oracle SDE、Informix-Illustra以及其他空间数据库引擎；n存储非空间数据、空间数据和概念层次的数据库和知识库。2022/9/2345第45页，共54页，编辑于2022年，星期六空间数据挖掘原型系统介绍 空间数据图形用户界面GeoMiner：知识发现模块空间数据库服务器和数据立方体非
45、空间数据概念层次空间特征规则发现模块空间关联规则发现模块空间预测模块空间模式分析模块空间比较规则发现模块空间分类规则发现模块空间聚类分析模块未来的空间发现模块2022/9/2346第46页，共54页，编辑于2022年，星期六空间数据挖掘原型系统介绍n到目前为止，尚没有对空间数据挖掘查询语言SDMQL（Spatial Data Mining Query Language）的定义。Han等人为了挖掘地理空间数据库设计了一种地理数据挖掘查询语言GMQL（Geo-Mining Query Language），它是对空间SQL的扩展，并成功地应用于空间数据挖掘系统原型GeoMiner中。GMQL可作为制
46、定SDMQL的基础，以进一步界定SDMQL语言的基本原语。nSDMQL的设计指导原则主要有：n在空间数据挖掘请求中应说明用于挖掘的相关数据集。n在空间数据挖掘请求中应说明想要挖掘的知识的种类。n挖掘过程中应该可能运用相关的背景知识。n挖掘结果应该能用较概括的或多层次概念的术语来表述。n应能够说明各种各样的阈值，使得可以灵活地过滤掉那些不是很令人感兴趣的知识。n应采用类似SQL的语法以适应在高级语言的水平上进行数据挖掘并与关系查询语言SQL保持自然的融合。2022/9/2347第47页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间
47、数据挖掘基础，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他2022/9/2348第48页，共54页，编辑于2022年，星期六空间数据挖掘的研究现状 n空间数据挖掘的研究比一般的关系型数据库和事务数据库的研究要晚，但近几年己经引起广泛的兴趣。目前国内外都己经开展了地球空间数据挖掘与知识发现方面的研究。n加拿大西蒙弗雷泽大学、德国慕尼黑大学、芬兰赫尔辛基大学以及美国、澳大利亚等国家的许多大学和研究所，都有空间数据挖掘的成果报道。n目前，在空间数据挖掘系统的开发方面，国际上有代表性的通用SDM系统有
48、：GeoMiner，Descartes和ArcView GIS的S-PLUS接口。n在国内，目前已经开展空间数据挖掘的单位主要有：北京大学、武汉大学、中科院软件所、中科院地理所资源与环境信息系统国家重点实验室、中科院遥感所、中国测绘科学研究院等。2022/9/2349第49页，共54页，编辑于2022年，星期六空间数据挖掘的研究与发展方向 空间数据挖掘是一个非常年轻而富有前景的领域，有很多研究问题需要深入探讨，这也是该领域的研究与发展方向。n1 1在面向对象的空间数据库中进行数据挖掘在面向对象的空间数据库中进行数据挖掘n2 2进行不确定性挖掘进行不确定性挖掘n3 3多边形聚类技术多边形聚类技术
49、n4 4模糊空间关联规则的挖掘模糊空间关联规则的挖掘n5 5挖掘空间数据的偏离和演变规则挖掘空间数据的偏离和演变规则n6 6多维规则可视化多维规则可视化n7 7多技术结合多技术结合n8 8高效的分类算法高效的分类算法n9 9空间数据挖掘查询语言空间数据挖掘查询语言n1010带空间误差的数据挖掘带空间误差的数据挖掘n11 11遥感影像的挖掘遥感影像的挖掘n1212智能智能GISGIS方法方法n1313并行数据挖掘并行数据挖掘n1414其他其他 2022/9/2350第50页，共54页，编辑于2022年，星期六第八章第八章 空间挖掘空间挖掘 内容提要内容提要n引言 n空间数据概要n空间数据挖掘基础
50、，空间统计学n泛化与特化n空间规则n空间分类算法n空间聚类算法n空间挖掘的其他问题n空间数据挖掘原型系统介绍n空间数据挖掘的研究现状与发展方向n其他2022/9/2351第51页，共54页，编辑于2022年，星期六空间数据挖掘与相关学科的关系 n空间数据挖掘与空间数据库空间数据挖掘与空间数据库 空间数据库存储了大量与空间有关的数据，例如数字地图、预处理后的遥空间数据库存储了大量与空间有关的数据，例如数字地图、预处理后的遥感或医学图像数据等等，空间数据库有许多与关系型数据库所不同的显著感或医学图像数据等等，空间数据库有许多与关系型数据库所不同的显著特征。特征。n空间数据挖掘与空间数据仓库空间数据