空间数据挖掘常用方法

问题1：空间数据挖掘有哪些常用方法，举例说明一种方法的原理及应用. 答：空间数据挖掘的常用方法有：统计法，聚类方法，关联规则发掘方法，Rough集方法，神经网络方法，云理论，证据理论，模糊集理论，遗传算法等算法（出自丁信宙，仇环，苏晓庆. 基于云理

问题1：空间数据挖掘有哪些常用方法，举例说明一种方法的原理及应用.

答：空间数据挖掘的常用方法有：统计法，聚类方法，关联规则发掘方法，Rough集方法，神经网络方法，云理论，证据理论，模糊集理论，遗传算法等算法（出自丁信宙，仇环，苏晓庆. 基于云理论的缺损数据推理和预测 山东理工大学学报 2006年11月）。除此以外还有老师课件上提到的聚类检测，决策树方法等。

以下对于一些常见模型做一简述：

1、空间分析方法 (Spatial Analysis Approach)

利用GIS的各种空间分析模型和空间操作对空间数据库中的数据进行深加工，从而产生新的信息和知识。目前常用的空间分析方法有综合属性数据分析、拓扑分析、缓冲区分析、密度分析、距离分析、叠置分析、网络分析、地形分析、趋势面分析、预测分析等，可发现目标在空间上的相连、相邻和共生等关联规则，或发现目标之间的最短路径、最优路径等辅助决策的知识。空间分析方法常作为预处理和特征提取方法与其它数据挖掘方法结合使用。

2、统计分析方法 (Statistical Analysis Approach)

统计方法一直是分析空间数据的常用方法，着重于空间物体和现象的非空间特性的分析。在运用统计方法进行数据挖掘时，一般并不将数据的空间特性作为限制因子加以考虑，空间数据所描述的事物的具体空间位置在这类挖掘中也并不起制约作用。尽管此种挖掘方式与一般的数据挖掘并无本质的差别，但其挖掘后发现的结果都是以地图形式来描述的，对发现结果的解释也必然要依托地理空间进行，挖掘的结果揭示和反映的必然是空间规律。但是，统计方法难以处理字符型数据。而且，应用统计方法需要有领域知识和统计知识，一般由具有统计经验的领域专家来完成。统计方法的最大缺点是要假设空间分布数据具有统计不相关性。这在实际应用中会出现问题，因为很多空间数据是相互关联的。

3、归纳学习方法 (Induction Learning Approach)

归纳学习方法是从大量的经验数据中归纳抽取出一般的规则和模式，其大部分算法来源于机器学习领域。归纳学习的算法很多，如Michaski等的AQ11,AQ15，洪家荣等的AE1,AE9，Hunt的CLS, Quinlan的ID3,C5.0等，其中最著名的是Quinlan提出的一种决策树算法，由ID3算法发展而来，采用嫡来选择属性，分类速度快，适合于大数据库的学习，而C5.0在　ID3的基础上增加了将决策树转换为等价的产生式规则的功能，并解决了连续取值数据的学习问题。Han Jiawei教授等提出了一种面向属性的归纳方法 (Attribute Oriented Induction, AOI)，专门用于从数据库中发现知识，通过概念树的提升对数据进行概括和综合，归纳出高层次的模式或特征。裴健等对面向属性的归纳方法进行了扩展，形成了基于空间属性的归纳方法 (Spatial Attribute Oriented Induction, SAOI)。

4、空间关联规则挖掘方法 (Spatial Association Rule Mining Approach)

挖掘关联规则首先由Agrawal等提出，主要是从超级市场销售事务数据库中发现顾客购买多种商品时的搭配规律。最著名的关联规则挖掘算法是Agrawal提出的Apriori算法，其主要思路是统计多种商品在一次购买中共同出现的频数，然后将出现频数多的搭配转换为关联规则。

5、聚类方法 (Clustering Approach)和分类方法 (Classification Approach)

聚类是按一定的距离或相似性系数将数据分成一系列相互区分的组，根据定义可以把其分为四类：基于层次的聚类方法；分区聚类算法；基于密度的聚类算法；网格的聚类算法。常用的经典聚类方法有K-mean，K-medoids，ISODATA等。

分类就是假定数据库中的每个对象(在关系数据库中对象是元组)属于一个预先给定的类，从而将数据库中的数据分配到给定的类中，简单的讲就是f:D→L，其中f的域D是属性数据的空间，L是标号的集合。

分类和聚类都是对目标进行空间划分，划分的标准是类内差别最小而类间差别最大。分类和聚类的区别在于分类事先知道类别数和各类的典型特征，而聚类则事先不知道。

6、神经网络方法 (Neural Network Approach)

神经网络是由大量神经元通过极其丰富和完善的连接而构成的自适应非线性动态系统，具有分布存储、联想记忆、大规模并行处理、自学习、自组织、自适应等功能。神经网络由输入层、中间层和输出层组成。大量神经元集体通过训练来学习待分析数据中的模式，形成描述复杂非线性系统的非线性函数，适于从环境信息复杂、背景知识模糊、推理规则不明确的非线性空间系统中挖掘分类知识。

7、决策树方法 (Decision Tree Approach)

决策树根据不同的特征，以树型结构表示分类或决策集合，产生规则和发现规律。在空间数据挖掘中，首先利用训练空间实体集生成测试函数；其次根据不同取值建立树的分支，在每个分支子集中重复建立下层结点和分支，形成决策树；然后对决策树进行剪枝处理，把决策树转化为据以对新实体进行分类的规则。

8、粗集理论 (Rough Sets Theory)

粗集理论是波兰华沙大学Z.Pawlak教授在1982年提出的一种智能数据决策分析工具，被广泛研究并应用于不精确、不确定、不完全的信息的分类分析和知识获取。粗集理论为空间数据的属性分析和知识发现开辟了一条新途径，可用于空间数据库属性表的一致性分析、属性的重要性、属性依赖、属性表简化、最小决策和分类算法生成等。粗集理论与其它知识发现算法结合可以在空间数据库中数据不确定的情况下获取多种知识。

9、模糊集理论 (Fuzzy Sets Theory)

模糊集理论是L.A.Zadeh教授在1965年提出的。它是经典集合理论的扩展，专门处理自然界和人类社会中的模糊现象和问题。利用模糊集合理论，对实际问题进行模糊判断、模糊决策、模糊模式识别、模糊簇聚分析。系统的复杂性越高，精确能力就越低，模糊性就越强，这是Zadeh总结出的互克性原理。模糊集理论在遥感图像的模糊分类、GIS模糊查询、空间数据不确定性表达和处理等方面得到了广泛应用。

10、空间特征和趋势探侧(Characterization and Trend Detection)方法

这是Ester等人在第4届KDD国际研讨会 (1998)上提出的基于邻域图 (neighborhoodgraphs)和邻域路径 (neighborhoodpath)概念的挖掘算法。Ester等将一个空间特征定义为空间数据库中具有空间/非空间性质的目标对象集，并以非空间属性值出现的相对频率和不同空间对象出现的相对频率 (目标对象集相对于整个数据库)作为感兴趣的性质，从空间目标集合经过它的相邻扩展后的集合中，发现相对频率的明显不同，以此提取空间规则：空间趋势探测挖掘是从一个开始点出发，发现一个或多个非空间性质的变化规律，这种算法的效率在很大程度上取决于其处理相邻关系的能力。

11、云理论 (Cloudy Theory)

这是李德毅博士提出的用于处理不确定性的一种新理论，包括云模型 (Cloud Model)，虚拟云 (Virtual Cloud)、云运算 (Cloud operation)、云变换 (Cloud Transform)和不确定性推理 (Reasoning under Uncertainty)等主要内容。运用云理论进行空间数据挖掘，可进行概念和知识的表达、定量和定性的转化、概念的综合与分解、从数据中生成概念和概念层次结构、不确定性推理和预测等。

12、图像分析和模式识别 (Image Analysis and Pattern Recognition)方法

空间数据库 (数据仓库)中含有大量的图形图像数据，一些图像分析和模式识别方法可直接用于挖掘数据和发现知识，或作为其它挖掘方法的预处理方法。用于图像分析和模式识别的方法主要有:决策树方法、神经元网络方法、数学形态学方法、图论方法等。

13、证据理论 (Evidence Theory)

由Schafer发展起来的证据理论是经典概率论的扩展。证据理论又称Dempster-Schafer理论，它是Dempster在20世纪60年代提出，在70年代中期由Schafer进一步发展，形成处理不确定性信息的证据理论，其重要贡献在于严格区分不确定和不知道的界线。证据理论将实体分为确定部分和不确定部分，可以用于基于不确定性的空间数据挖掘。利用证据理论的结合规则、可以根据多个带有不确定性的属性进行决策挖掘。证据理论发展了更一般性的概率论，却不能解决矛盾证据或微弱假设支持等问题。

14、遗传算法 (Genetic Algorithms)

遗传算法(简称GA)是模拟生物进化过程的算法，最先由美国的John Holland教授于20世纪60年代初提出，其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法已在优化计算、分类、机器学习等方面发挥了显著作用。数据挖掘中的许多问题，如分类、聚类、预测等知识的获取，可以表达或转换成最优化问题，进而可以用遗传算法来求解。

15、数据可视化方法 (Data Visualization Approach)

人类的可视化能力，允许人类对大量抽象的数据进行分析。人的创造性不仅取决于人的逻辑思维，而且取决于人的形象思维。人脑的空间认知分析能力目前尚无法全部用计算机代替，因此可视化技术为知识发现提供了有力的帮助。为了了解数据之间的相互关系及发展趋势，人们可以求助于可视化技术。海量的数据只有通过可视化技术变成图形或图像，才能激发人的形象思维—— 从表面上看来是杂乱无章的海量数据中找出其中隐藏的规律。数据可视化技术将大量数据以多种形式表示出来，帮助人们寻找数据中的结构、特征、模式、趋势、异常现象或相关关系等。从这个角度讲，数据可视化技术不仅仅是一种计算方法，更是看见不可见事物或现象的一种重要手段和方法。

16、地学信息图谱方法 (Geo-informatics Graphic Methodology)

地学信息图谱是地球信息的重要表现形式与研究手段，也是地球信息科学的重要组成部分。地学信息图谱综合了景观综合图的简洁性和数学模型的抽象性，是现代空间技术与我国传统研究成果结合的产物，可反演过去、预测未来。图是指地图、图像、图解，谱是指不同类别事物特征有规则的序列编排。图谱是指经过深入分析与高度综合，反映事物和现象空间结构特征与时空序列变化规律的图形信息处理与显示手段。地球信息图谱是由遥感、地图数据库与地理信息系统(或数字地球)的大量地球信息，经过图形思维与抽象概括，并以计算机多维动态可视化技术显示地球系统及各要素和现象的宏观、中观与微观的时空变化规律；同时经过中间模型与地学认知的深入分析研究，进行推理、反演与预测，形成对事物和现象更深层次的认识，有可能总结出重要的科学规律。地学信息图谱不仅应用于数据挖掘，而且服务于科学预测与决策方案。

地学信息图谱具有以下4个重要功能：①借助图谱可以反演和模拟时空变化；②可利用图的形象表达能力，对复杂现象进行简洁的表达；③多维的空间信息可展示在二维地图上，从而大大减小了模型模拟的复杂性；④在数学模型的建立过程中，图谱有助于模型构建者对空间信息及其过程的理解。

地学信息图谱是形、数、理的有机结合，是试图从形态来反演空间过程的一种研究复杂系统的方法论。地学信息图谱中的空间图形思维、分形分维等方法均可直接用于空间数据挖掘领域。目前，地学信息图谱的基本理论及其方法体系还不完善，还有待于进一步研究。

17、计算几何方法 (Computer Geometry Methods)

1975年，Shamos和Hoey利用计算机有效地计算平面点集Voronoi图，并发表了一篇著名论文，从此计算几何诞生了。计算几何中的研究成果已在计算机图形学、化学、统计分析、模式识别、空间数据库以及其它许多领域得到了广泛应用。计算几何研究的典型问题包括几何基元、几何查找和几何优化等。其中，几何基元包括凸壳和Voronoi图、多边形的三角剖分、划分问题与相交问题：几何查找包括点定位、可视化、区域查找等问题；几何优化包括参数查找和线性规划。

上述每一种方法都有一定的适用范围。在实际应用中，为了发现某类知识，常常要综合运用这些方法。空间数据挖掘方法还要与常规的数据库技术充分结合。总之，空间数据挖掘利用的技术越多，得出的结果精确性就越高，因此，多种方法的集成也是空间数据挖掘的一个有前途的发展方向。

以下是对云模型和其在缺损数据的推理预测中的应用做一简述。

云模型：云是用语言值描述某个定性概念与其数值表示的不确定性转换的模型。简单地说，云模型是定性定量间转换的不确定性模型。该模型用期望Ex，熵En，超熵He三个数值来表示，把模糊性和随机性完全集成到一起，构成定性和定量间的映射，作为表示的基础。期望值Ex是概念在论域中的中心值；熵En是定性概念模糊度的度量，反映了在论域中可被这个概念所接受的数值范围熵越大，概念所接受的数值范围也越大，概念越模糊。超熵He是熵的不确定性度量，即熵的熵，由熵的随机性和模糊性共同决定。超熵He反映了云滴的离散程度，超熵越大，离散度越大，隶属度的随机性越大。

设U 是一个用精确数值表示的论域（一维的、二维的或多维的），U 上对应着定性概念?，对于论域中的任意一个元素x，都存在一个有稳定倾向的随机数y=μA(x)，叫作x 对概念? 的确定度，x 在U上的分布称为云模型，简称为云。云由许许多多个云滴组成，一个云滴是定性概念在数量上的一次实现，单个云滴可能无足轻重，在不同的时刻产生的云的细节可能不尽相同，但云的整体形状反映了定性概念的基本特征。云的“厚度”是不均匀的，腰部最分散，“厚度”最大，而顶部和底部汇聚性好，“厚度”小。云的“厚度”反映了确定度的随机性的大小，靠近概念中心或远离概念中心处，确定度的随机性较小，而离概念中心不近不远的位置确定度的随机性大，这与人的主观感受相一致。

云的数字特征用期望Ex、熵En 和超熵He 来表征，它们反映了定性概念? 整体上的定量特征。

期望Ex：是概念在论域中的中心值，在数域空间最能够代表定性概念? 的点，即这个概念量化的最典型样本点，通常是云重心对应的x 值，它应该百分之百地隶属于这个定性概念。Ex 反映了相应的定性知识的信息中心值。

熵En：熵反映定性概念? 的不确定性。一方面，熵反映了在数域空间可以被语言值? 接受的云滴群的范围的大小，即模糊度，是定性概念亦此亦彼性的度量；另一方面，熵还反映了代表定性概念的云滴出现的随机性；此外，熵还揭示了模糊性和随机

性的关联性。熵可以用来代表一个定性概念的粒度。通常，熵越大，概念越宏观，模糊性和随机性也越大，确定性量化越难。

超熵He：超熵是熵的不确定性的度量，即熵的熵，反映了云滴的离散程度。超熵越大，云滴离散度越大，确定度的随机性越大，云的“厚度”也越大。

正态云是一种很典型的云模型，被应用于多种现实的模拟，十分具有代表性，因此，一下着重介绍一下与模型的建立方法。

正态云模型既不是一个确定的概率密度函数，也不是一条明晰的隶属函数曲线，而是由两次串接的正态发生器[5]生成的许多云滴组成的、一对多的泛正态数学映射图像，是一朵可伸缩、无确定边沿、有弹性的云图，完成定性和定量之间的相互映射。正态云模型的期望曲线是一个正态型曲线。当正态云模型概念对应的论域为一维时，定性定量的不确定性转换通过正态云发生器算法实现。具体算法如下：

输入：表示定性概念? 的3 个数字特征值Ex，En，He，云滴数N。

输出：N 个云滴的定量值，以及每个云滴代表概念? 的确定度。

Step1：生成以En 为期望值，He 为标准差的一个正态随机数E′n；

Step2：生成以Ex 为期望值，abs（E′n）为标准差的正态随机数x；

Step3：令x 为定性概念? 的一次具体量化值，称为云滴；

Step4：计算y=exp(-(x-Ex)2/2(E′n)2)；

Step5：令y 为x 属于定性概念? 的确定度；

Step6：{x，y}完整地反映了这一次定性定量转换的全部内容；

Step7：重复Step1~Step6，直到产生N 个云滴。

用该算法生成的云自然地具有不均匀厚度的特性，云的腰部、顶部、底部等并不需要精确地定义，三个数字特征值足以很好地描述整个云的形态。

云模型的应用相当广泛，下面仅就其在军事中的一个应用做一描述。在《基于正态云模型的方法求解目标可能位置域》这篇论文当中，作者利用云模型模拟目标可能出现的位置，通过一系列计算，确定一个区域，从而为*发射提供数据支持。

潜艇使用导弹攻击对方水面舰艇已经成为越来越重要的作战方式。由于潜艇对隐蔽性的要求，攻击前很难实时获得友方兵力的目标指示通报，因此需要根据此前某一时刻通报的目标位置 、速度 、航向 推测出当前的目标可能位置。

模型中已知的前提条件：1．发现目标时刻 ；2． 时刻目标概略中心位置 和误差分布椭圆的方向 、半轴 和 ；3． 时刻目标速度V、航向H 及其标准偏差 ， 。模型运行的目的是求出时刻T 时的目标概略中心位置( ， )以及误差分布椭圆的方向 、半轴 和 。

确定目标可能位置域模型的建模思路：按模型中的前提条件，产生M 个 时刻目标随机位置点；对这M 个点中的任一个点，按照目标速度、航向误差分别取N1、N2 个随机速度、航向，在时刻T时产生N1×N2 个随机位置点。这样最终产生M×N1×N2 个随机位置点。最后对M×N1×N2 个随机位置点进行数据分析得T 时刻的目标位置概率椭圆。该椭圆就是*发射的目标区域。

问题2：论述数据挖掘与空间数据挖掘的异同点。

答：数据挖掘(Data Mining)，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。数据挖掘的广义观点：数据挖掘就是从存放在数据库，数据仓库或其他信息库中的大量的数据中“挖掘”有趣知识的过程。数据挖掘，又称为数据库中知识发现(Knowledge Discovery in Database, KDD)， 也有人把数据挖掘视为数据库中知识发现过程的一个基本步骤。

知识发现过程以下步骤组成：（1）数据清理，（2）数据集成，（3）数据选择，（4）数据变换，（5）数据挖掘，（6）模式评估，（7）知识表示。数据挖掘可以与用户或知识库交互。

空间数据挖掘是指从空间数据库中抽取没有清楚表现出来的隐含的知识和空间关系，并发现其中有用的特征和模式的理论、方法和技术。 空间数据挖掘和知识发现的过程大致可分为以下多个步骤:数据准备、数据选择、数据预处理、数据缩减或者数据变换、确定数据挖掘目标、确定知识发现算法、数据挖掘、模式解释、知识评价等，而数据挖掘只是其中的一个关键步骤。但是为了简便，人们常常用空间数据挖掘来代替空间数据挖掘和知识发现。空间数据挖掘（Spatial Data Mining， SDM）是数据挖掘的一个分支，是在空间数据库的基础上，综合利用各种技术方法，从大量的空间数据中自动挖掘事先未知的且潜在有用的知识，提取出非显式存在的空间关系或其它有意义的模式等，揭示出蕴含在数据背后的客观世界的本质规律、内在联系和发展趋势，实现知识的自动获取，从而提供技术决策与经营决策的依据。数据挖掘所能发现的知识最常见的有以下五种类型：广义知识、关联知识、分类知识、聚类知识和预测型知识。而要发现这些知识就需要运用相应空间数据挖掘方法。

综上所述，二者之间的共同点是：

1. 都是基于已经获得的数据，无论是存储在数据库，数据仓库，或者是文件当中的数据进行分析；

2. 都是从大量的信息当中，通过数据间的内在联系提取出操作者感兴趣的数据；

3. 提取出的数据都是非显式存储的，或者说是隐藏在原有数据当中的；

4. 空间数据挖掘是数据挖掘技术的一个重要分支和发展；

5. 二者均以统计学为数学基础。

另外二者的不同之处在于：

1. 传统数据挖掘处理的是数字和类别，而空间数据则是一些更为复杂的数据类型，例如：点、线、多边形等对象；

2. 传统数据挖掘通常具有显式的输入，而空间数据挖掘的输入则常常是隐式的；

3. 在传统数据挖掘中，有一个至关重要的前提假设，即数据样品是独立生成的，而这一假设在空间分析中是不成立的，事实上，空间数据之间是高度自关联的。

4. 数据源十分丰富,数据量非常庞大,数据类型多,存取方法复杂；

5. 应用领域十分广泛,只要与空间位置相关的数据,都可以对其进行挖掘；

6. 挖掘方法和算法非常多,而且大多数算法比较复杂,难度大；

7.知识的表达方式多样,对知识的理解和评价依赖于人对客观世界的认知程度。