数据仓库与空间数据挖掘

随着卫星和遥感技术以及其它自动数据采集工具的越来越广泛的应用,日益丰富的空间和非空间数据收集和存储于大空间数据库中,海量的地理数据在一定程度上已经超过了人们能够处理的能力,从这些海量的数据中提取和发现地学知识,给当前GIS技术提出了巨大的挑战。新的需求推动着GIS从操作型信息系统向分析型信息系统过渡,数据库系统最新的数据仓库和数据库知识发现技术为GIS组织、管理海量空间和非空间数据提供了新的思路。GIS在空间数据存储、表达和管理方面的能力已得到广泛的认可,增强GIS分析功能,提高GIS解决地学实际问题的能力已得到共识。GIS吸收数据仓库的思想,将空间分析和空间数据挖掘方法紧密集成,充分利用GIS数据存储、管理空间数据的功能,使海量的地理空间数据变成无限的知识,使GIS成为智能的信息系统。

数据仓库 (Data Warehouse)

近年来,人们逐渐认识到计算机系统存在两类不同的处理:操作型处理和分析型处理。操作型处理也叫事务型处理,是指对数据库联机进行的日常操作,通常是对一个或一组记录的查询和修改,主要为企业特定应用服务,对此人们关心的是响应时间、数据的安全性和完整性。分析型处理是用于管理人员的决策分析,例如决策支持系统、专家系统和多维分析等,经常要访问大量的历史数据。

两者的巨大差别使得操作型处理和分析型处理的分离成为必然,于是数据库由操作型环境发展成为操作型环境和分析型环境的新体系化环境。在此新体系环境中数据仓库处于核心地位,它是建立决策支持系统的基础。

数据仓库是指面向主题的、集成的、稳定的、随着时间变化的数据集合,用以支持管理决策。这一定义指出了数据仓库的目标是为了制定管理的决策提供支持信息。正象企业为了发展要进行业务重组一样,为了支持管理决策需要也要按决策业务科目的要求重组在线事务处理(OLTP)系统中的数据,并要按不同决策,分析内容分别组织使之方便使用。也就是说,数据仓库是一种把收集的数据转变成有意义的信息技术。数据可以来源于许多不同的数据源,包括不同的数据库系统,甚至来源于不同的操作系统。

../../_images/img_111.png

图10-12:数据仓库体系结构

在把数据装载到数据结构重组后的数据仓库之前,先要进行数据集成处理。这一处理包括几个必不可少的操作步骤,以做到使数据完整、统一,这就确保了在使用数据仓库时其中的数据是有质量保证的。简而言之,集成就是保证数据准确、到位、没有超出应有的数值范围、没有重复等。数据仓库中的数据不像在线事务处理系统中的数据那样频繁的修改,所以它是比较稳定的(极少或根本不修改)。在一次数据分析的执行过程中使用的数据不得变更,才能保证两次在使用同一组信息进行分析时不会得出不同的答案。数据仓库一般是按周、月或隔月从在线事务处理系统周期性地更新数据。

典型的数据仓库体系结构如图10-12,数据从多个操作型数据库和外部文件中抽取,抽取出来的数据要进行清理、转换和集成,然后装入数据仓库中。装入仓库的数据形式取决于数据仓库里数据库的设计,一般的数据仓库设计方法是多维数据模型,具体表现为星形模式或雪花模式。仓库的数据要定期更新以反映源数据的变化。最后使用前端的报表、查询、分析和数据挖掘等工具来操作和使用数据仓库。在数据仓库管理方面,有一个存储元数据(关于仓库数据的数据)的中央数据库或数据字典,而监控和管理工具也是必不可少的。

数据挖掘(Data Mining)

随着大量的大规模的数据库迅速不断地增长,人们对数据库的应用已不满足于仅对数据库进行查询和检索。仅用查询检索不能帮助用户从数据中提取带有结论性的有用信息。这样数据库中蕴藏的丰富知识,就得不到充分的发掘和利用,形成“数据丰富而知识贫乏”的现象。另外,从人工智能应用来看,专家系统的研究虽然取得了一定的进展。但是,知识获取仍然是专家系统研究中的瓶颈。知识工程师从领域专家处获取知识是非常复杂的个人到个人之间的交互过程,具有很强的个性,没有统一的办法。因此,有必要考虑从数据库中发现新的知识,被称为数据库知识发现(Knowledge Discovery in Databases,简称KDD),也叫数据挖掘(Data Mining)。数据库知识发现或数据挖掘的定义为从数据中提取隐含的、先前不知道的和潜在有用的知识的过程。数据挖掘技术集成了机器学习、数据库系统、数据可视化、统计和信息理论等多领域的最新技术,有着广泛的应用前景。

数据挖掘主要分为以下四个步骤:

1)数据选取

数据仓库中的数据并不都与挖掘的信息有关,第一步就是为了只提取“有用的”数据。

2)数据转换

在确定要进行挖掘的数据之后,要对这些数据进行必要的变换,使得数据可以被进一步的操作使用,通常的变换有:

将定名量转换为定序量,以便于人工神经网络运算;

对已有的属性进行数学或逻辑运算,以创建新的属性。

3)数据挖掘

在数据转换之后,就要进行数据挖掘,数据挖掘的具体技术很多,如分类、回归分析等。

4)结果解释

挖掘的信息要参照用户的决策支持目的进行分析,并且要表现给决策者。这样,结果的输出不仅包含可视化的过程,而且要经过过滤,以去掉决策者不关心的内容。

当执行完一个挖掘过程后,有时可能需要重新修改挖掘过程,还可能增加其它数据,数据挖掘过程可以通过适当的反馈反复进行,如图10-13所示。

../../_images/img_27.png

图10-13:知识挖掘过程

数据挖掘涉及的学科领域和方法很多,有多种分类法。根据知识发现任务,可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等;根据知识发现对象,可分为关系数据库、面向对象数据库、空间数据库、时间数据库、文本数据源、多媒体数据库、异质数据库、Web数据库;根据知识发现方法,可粗分为机器学习方法、统计方法、神经网络方法和数据库方法。机器学习中,可细分为归纳学习方法(决策树、规则归纳等)、基于范例学习、遗传算法等。统计方法中,可细分为回归分析(多元回归、自回归等)、判别分析(贝叶斯判别、费歇尔判别、非参数判别等)、聚类分析(系统聚类、动态聚类等)、探索性分析(主元分析法、相关分析法等)等。神经网络方法中,可细分为前向神经网络(BP算法等)、自组织神经网络(自组织特征映射、竞争学习等)等。数据库方法主要是多维数据分析或在线事务处理方法,另外还有面向属性的归纳方法。

空间数据挖掘

空间数据是与占有一定空间的对象有关的数据,空间数据库是通过空间数据类型和空间关系存储和管理空间数据。空间数据通常具有拓扑和距离信息,通过空间索引进行组织和查询。空间数据特有的性质给空间数据库的知识发现提出了挑战和机遇。空间数据库的知识发现或空间数据挖掘,可以定义为从空间数据库中提取隐含的知识、和没有直接存储的空间关系、空间模式的过程。

空间数据挖掘技术,特别是空间数据理解、空间和非空间数据关系发现、空间知识库构造、空间数据库的查询优化和数据组织,在GIS、遥感、影象数据库、机器人运动等涉及空间数据的应用系统中很有前景。

下面简要介绍目前空间数据挖掘使用的一些方法:

1)统计分析方法

目前空间数据分析最常用的方法是统计分析方法。统计分析非常适合处理数值型数据,统计分析方法多年来积累了大量的算法,可以用于对空间现象建模和分析。但空间统计分析也有很大的缺陷:首先统计分析方法关于空间分布数据的统计独立性的假设,往往不现实,因为空间邻域之间存在着相互关系;其次,统计分析不适合处理非数值型数据,如空间对象的名称和定名数据类型等。另外统计分析往往对领域专家和统计方面的知识要求较高,只适合领域专家和有统计经验的人使用,而且当数据不完整或不充分时,统计分析的结果缺乏实际意义。再就是统计分析的计算代价也是很高的。为克服统计分析方法的缺点,需要新的数据挖掘方法。

2)基于概括的方法

基于概括的方法是一种面向属性的归纳学习方法,用于空间数据挖掘,可将空间和非空间属性的关系概括成高层次的概念知识。它需要背景知识,即概念层次体系(Concept Hierarchy),常以概念树的形式给出。如图10-14所示的是一个农业土地利用的概念树。同样地,空间数据也存在类似地概念层次,如乡镇——县市——省——国家。

面向属性的归纳学习方法,通过概念树攀升而得到概括的数据,概括的数据可直接转换成规则或逻辑表达式,可用于发现普遍特征规则和区划规则。空间数据库的归纳学习可以根据非空间数据的概念层次,也可根据描述空间数据的概念层次进行。基于非空间数据的概念层次归纳,例如数值型数据可以归到一个数值范围或一个较高层次概念描述型变量,(-9℃在-10℃-0℃范围,或“寒冷”),通过低层次的数值不同的数据概括为较高层次的相同的数据,这些由不同元组的数据和它们的空间对象指针一起合并为高层次数据,表示一个新的空间属性。基于空间数据的概念层次归纳,可以通过区划划分或空间存储结构如四叉树进行定义。

../../_images/img_38.png

图10-14:概括归纳示例

基于概括的方法一般有以非空间数据为主的概括和以空间数据为主的概括两种算法。这两种算法的第一步都是选取用户特定的查询数据。接下来,非空间数据为主的概括算法过程是:(A)概念树攀升,即将元组的属性变为高层次的属性;(B)属性删除,删除那些不可能概括的特殊属性值;(C)合并标识后的元组。归纳过程直到所有的属性概括到合适的层次为止。最后将概括后属性值相同的相邻区域合并,结果得到一幅概念层次较高的、而区域较少的图。

以空间数据为主的概括算法,第一步也是收集用户查询的数据,然后根据给定的空间数据概念层次对空间对象进行合并,概括过程直到达到需要的概念层次为止。然后对于每个概括后的空间对象进行非空间数据概括,直到得到所有区域的正确描述。

3)聚类方法

聚类分析是统计分析的一个分支,这种方法的主要优点是不需要背景知识,可以直接从数据中发现感兴趣的结构或聚类模式,类似于机器学习中的非监督学习。

聚类分析与面向属性归纳推理结合,为描述相似对象的空间行为提供了可能,或用于判定不同类别的特征。同样可分为以空间数据为主和以非空间数据为主两种方法。以空间数据为主的方法,首先通过基于采样的高效的聚类算法将与任务有关的空间对象(如点)分类,接着对非空间数据使用面向属性归纳推理方法,提取描述各类一般属性。

以非空间数据为主的方法,首先将与任务有关的空间对象概括到较高的概念层次,进行聚类分析,然后将空间对象进行合并处理。

4)空间关联规则(Spatial Association Rule)方法

关联规则的提出源于交易数据集中发现商品之间隐含的相互依赖关系。如果在超市的数据库中发现的一条规则,形式为“WB(C%)”,规则的含义是“如果交易中出现了W模式,就有C%的可能性(可信度)出现B交易模式”。例如规则“牛奶黄油(90%)”,表明有90%的买牛奶的顾客会同时买黄油,这就是关联规则。它同样可用于发现空间关系。

空间关联规则的形式为:

谓词中至少有一个是空间谓词;C%为关联规则的可信度。

构造空间关联规则的空间谓词有很多形式,例如拓扑关系(相交、包含、重叠等)、方位关系(左侧、西侧等)、距离关系(临近、远离等)。

关联规则通常可以分为两种:布尔型关联规则和多值关联规则。多值关联规则比较复杂,一种自然的想法是将它转换为布尔型关联规则。当全部属性的取值数量都是有限的时候,只需将每个属性值映射为一个布尔型属性即可。当属性的取值范围很宽时,则需将其分为若干区段,然后将每个区段映射为一个布尔型属性。于是,如何划分区段是实现多值关联规则到布尔型关联规则转变的关键。这里面有两个互相牵制的问题:当区段的范围太窄时,则可能使每个区段对应的属性的支持度很低,而出现“最小支持度问题”;当区段的范围太宽时,则可能使每个区段对应的属性的可信度很低,而出现“最小可信度问题”。

在一个集合S里,空间联结谓词的支持度,为满足P的对象数与S集合总数的比;集合S里关联规则PQ的可信度为/。

关联规则的发现可以分解成以下两个子问题:

(4.1)找出数据库S中所有满足用户指定最小支持度的对象集P(一个非空子集),具有最小支持度的对象集称为频繁对象集,反之就称为非频繁对象集。

(4.2)利用频繁对象集生成所需要的关联规则。对于每一个频繁对象集P,找出P的所有非空子集Q,如果比率/≥最小可信度,就生成关联规则PQ。

下面简要介绍一下空间关联规则的算法过程:

输入:空间数据库、挖掘查询、关联约束条件集

  • 数据库包括三部分:包含空间对象的空间数据库、描述非空间信息的关系数据库、概念层次集;

  • 查询也包括三部分:要描述的对象类S、与任务有关的空间对象子类C1,...Cn、有关的关系和谓语集;

  • 三个约束条件:每个概念层次上的最小支持度、最小可信度、满足“临近”空间谓语的最大距离。

输出:有关对象的多种概念层次上的较强的空间关联规则

方法:空间关联发现的计算程序如下:

  1. 生成要描述的对象类的图层1

  2. 对于相关对象的所有子类对象Ci同时进行如下处理:

  • 生成关联对象子类的图层2;

  • 生成作用于对象Ci的谓词(如图层1与图层2相交,给定距离条件);

  • 将对象Ci的谓词加入到谓词数据库中。

  1. 搜索谓词数据库中可信度高的空间关联规则。

空间谓词存在一个扩展的关系数据库——谓词数据库中,属性值为单值或多值集合。谓词数据库的一个记录描述对象类S中的一个对象Si与满足谓词关系的对象Cj的关系。