空间数据挖掘方法综述

谢远飞,刘 洋,李海军

(中国矿业大学,北京100083)

0 引 言

随着计算机与网络通信技术的飞速发展,数据的积累正在呈爆炸性的增长,而其中大量的数据都与空间有关。由于空间数据类型复杂,时效性强,数据量大,收集到的数据远远超过人脑分析的能力,导致了空间数据灾难且空间知识贫乏,于是空间数据挖掘技术应运而生。

空间数据挖掘是指从空间数据库中提取用户感兴趣的空间模式与特征、空间与非空间数据的关系及其它一些隐含在数据库中的知识[3]。空间数据库与常规的关系数据库有许多不同:空间数据库具有丰富的数据类型,带有拓扑和距离信息;空间数据有很强的局部相关性;数据都被精心组织,以多维索引作为其存取方法;有空间推理、几何计算及空间知识表达能力。这就使得空间数据库的挖掘技术不同于关系数据库,特别是空间中的相似对象趋向于地理空间上的聚集,即空间自相关性,使得以对象间相互独立为基础的关系数据库的经典挖掘方法不再适用,只有研究新的理论、技术和方法,才能从空间数据库中挖掘出新颖有效的、能被人理解的空间知识。空间数据库是一类特殊的数据库,地理信息系统(GIS)是空间数据库发展的基础,因此,对空间数据库的研究是随着地理信息系统的发展而不断深入的。目前空间数据库及其挖掘研究的重点主要集中在空间数据挖掘方法等方面,空间数据挖掘和知识发现方法是丰富多彩的。针对空间数据库的特点,可采用下列的空间数据挖掘与知识发现方法。

1 基于聚类的方法

聚类分析方法按一定的距离或相似性测度将数据分成一系列相互区分的组,由此来发现数据集合的整个分布模式。它不需要背景知识而直接发现一些有意义的结构与模式。

聚类问题可以这样描述:给定一数据集D,使用某种相似性度量,把D分成k个子集:{C1,C2,…,Ck},Ci⊂D每个子集形成一个类,使得不同类的数据尽可能地不相似而同一类中的数据尽可能地相似。如果k=1或k=|D|,则称为平凡聚类。按照聚类方法的原理进行分类可分为:层次聚类、划分聚类、基于网格的聚类、基于模型的聚类和基于密度的聚类。其中许多经典的聚类方法不适宜在大的空间数据集下应用,在大数据集情况下其存在速度慢、效率低等问题。

层次聚类方法依据对象的相似性递归地对对象进行合并或者分裂,直到满足某一终止条件,层次聚类的结果可以用一个谱系图表示。常见的层次聚类方法有 :AGNES[4]、DIANA[4]、BIRCH[5]、CURE[6]等。其中AGNES和DIANA效率较低,不适于大数据集的聚类;BIRCH虽然有良好的伸缩性但只能处理数值型数据,并且不支持任意形状聚类。

划分聚类算法把聚类问题转化成一个组合优化问题,从一个初始划分或者一个初始聚点集合开始,利用迭代控制策略优化一个定制目标函数,导致其收敛较慢,可能陷入局部极小,而且限制了它们在空间数据挖掘上的应用。典型的划分聚类方法有 k-means[4]、k-medoids[7]、PAM[8]、CLARA[8]、CLARANS[8]等。

网格聚类方法把数据空间划分成一定数目的单元,以后所有的操作都是对单元进行的。网格聚类方法主要有ST ING[9]、Wave Cluster[10](小波变换聚类)和CLIQUE[11]等。网格聚类的主要不足是聚类结果的精确度降低。

基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。基于模型的聚类主要有邻域 EM 算法[12-13]、SOM[14]、ART[15]等。

基于密度的聚类[16]根据空间密度的差别,把具有相似密度的点作为聚类。基于密度的聚类是空间数据聚类常用的行之有效的方法,该方法的主要优点是具有良好的可扩展性,可以发现其显著特点是聚类速度快,能处理噪声以及发现任意形状的聚类。典型的代表算法有 Hinneburg等提出的DENCLUE算法;Ester等提出了DBSCAN算法,它根据空间密度的差别,把具有相似密度的点作为一个聚类,DBSCAN算法的缺点是算法参数难于给定,依赖数据集,且它们不能发现类的层次结构;Ankerst等提出的OPTICS算法,它强调自动性和交互性的有机结合,按照密度的差别给出一个通用的聚类,用户可以对不同的聚类设置不同的参数;Ester M等提出的GDBSCAN是DBSCAN的推广,它把邻居的定义扩展为任意满足自反、对称特性的概念,其次,它把对邻域的分析从简单的记数扩展为复杂的表达式,聚类对象可以不限于点;Ester M等讨论了聚类在对象的插入、删除下的修改策略,提出了DBSCAN的增量算法。

2 基于分类的方法

分类在数据挖掘中是一项非常重要的任务,目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个。要构造分类器,需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成,每个样本有一个类别标记。分类器的构造方法有判别分析方法、机器学习方法、粗糙集[17]方法和神经网络方法[18]等。

判别分析主要有Bayes判别法、Fisher判别法和线性判别函数法等。Bayes判别法使误判概率或风险最小的意义上是最佳的,但是Bayes分类器需要已知条件概率,而且其决策面往往是超曲面,形状复杂,难以计算和构造。Fisher判别法和线性判别函数法只能处理线性可分的情况,对非线性可分的决策面无能为力。

机器学习算法有三大代表:基于覆盖的AQ家族算法[19]、以信息熵为基础的决策树算法(ID3[20],C4.5[21])、支持向量机。

AQ家族算法使用逻辑语言来描述学习结果。整个学习过程就是一个逻辑演算过程:学习样本集合为正例样本和反例样本组成,通过对正例样本和反例样本的集合运算(分配率和吸收率)简化样本,最后得到分类的逻辑描述。其主要特点是基于范例的推理,不足是分类不够精确,难于处理连续属性字段。

决策树算法利用信息论中的互信息(信息增益)寻找数据库中具有最大信息量的字段,建立决策树的一个结点,再根据字段的不同取值建立树的分支;在每个分支子集中,重复建立树的下层结点和分支的过程。其主要不足是树分支每次只选取一个属性,当类别太多时,错误可能就会增加的比较快,对连续性的字段比较难预测。

粗糙集是波兰数学家Pawlak提出的一种对不确定性知识的表示方法,现在则常被用来做数据约简。数据约简可以在保持分类一致的约束下大大简化样本数据,最终使用很少的几条逻辑规则就能描述分类规则,其知识表示是产生式规则。

神经网络方法主要是径向基函数法、BP算法等,它的模型表示是前向反馈神经网络模型(由代表神经元的节点和代表连接权值的边组成的一种体系结构),其本质上是一种非线性判别函数。

当前的分类方法研究最多的是基于模型的方法,如人工神经网络和支持向量机,神经网络由于其学习和适应、自组织、函数逼近和大规模并行处理等能力,使得它广泛应用于模式识别、信号处理、系统辨识和优化等方面,并且已经成功解决了许多应用领域的实际问题。不同的分类器有不同的特点。有三种分类器评价或比较尺度:预测准确度、计算复杂度和模型描述的简洁度。预测准确度是用得最多的一种比较尺度,特别是对于预测型分类任务。另外要注意的是,分类的效果一般和数据的特点有关。有的数据噪声大,有的有缺值,有的分布稀疏,有的字段或属性间相关性强,有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。

3 统计学方法

统计方法一直是分析空间数据的常用方法,有着较强的理论基础,拥有大量的算法,可有效地处理数值型数据。使用这种方法一般是首先建立一个数学模型或统计模型,然后根据这种模型提取出有关的知识。例如,可由训练数据建立一个Bayesian网[22],然后,根据该网的一些参数及联系权值提取出相关的知识。在经典的统计分析中,通常一个假设的采样数据是独立生成的,即需要数据满足统计不相关假设,然而对空间数据进行分析时,采样独立性的假设难以成立。因为空间数据趋于高度相关,相似的对象在空间上基本上聚集。另外统计学方法难以处理离散型属性数据,使用统计学方法需要有领域知识和统计知识,一般由具有统计经验的领域专家来完成。

4 基于泛化和归纳的方法

该方法对数据进行概括和综合,归纳出高层次的模式或特征。数据库中的数据和对象在原始的概念层次包含有详细的信息,经常需要将大量数据的集合进行概括并以较高的概念层次展示。基于泛化的知识发现假定背景知识以概念层次的形式存在,概念层次可由专家提供,或借助数据分析自动生成。空间数据库中可以定义两种类型的概念层次:非空间概念层和空间概念层。文献[23]中Han J.等提出了一个有效的数据泛化技术:面向属性的归纳。它首先执行一个数据挖掘查询,采集数据库中相关数据的集合,然后通过提升泛化层次,在较高概念层次上概括空间和非空间数据间的泛化关系以进行数据泛化。泛化的结果可用泛化关系或数据立方体的形式表达,用以执行进一步的OLAP操作,也可以映射为概括表、图表或曲线来进行可视化表示,还能从中抽取特征和判别规则。文献[24]中Lu W.等将面向属性的归纳扩展至空间数据库,提出两个算法:空间数据支配泛化和非空间数据支配泛化。

5 基于空间关联的方法

空间关联是将一个或多个空间对象与其它空间对象相关联。Agrawal等人引入关联规则的概念是为了挖掘大型的事务型数据库。Koperski等人将这个概念扩展至空间数据库[25]。空间关联规则的形式是X—＞Y(c%),X和Y都是空间或非空间的谓词的集合,c%是规则的可信度。空间谓词有3种形式:表示拓扑关系的谓词,如相交、覆盖等,表示空间方向的谓词,如东、西、左、右等,表示距离的谓词,如接近、远离等。在大型数据库中,可能存在大量的对象间的关联,但其中大部分只适用于少量对象,或者规则的可信度较低。空间关联规则使用两个阈值:最小支持度和最小可信度,以过滤出描述少量对象的关联和具有低可信度的规则。在对象非空间描述的不同层次上这两个阈值均不相同,因为如果使用相同的阈值,在低的概念层次上可能找不到有趣的关联,原因是此时满足相同谓词的对象的数目可能相当少。

6 云理论方法

云理论[26]是用于处理不确定性的一种新理论,由云模型(cloud model)、不确定性推理(reasoning under uncertainty)和云变换(cloud transform)三大支柱构成。云理论将模糊性和随机性结合起来,弥补了作为模糊集理论基石的隶属函数概念的固有缺陷,为数据挖掘中定量与定性相结合的处理方法奠定了基础。云模型在空间由系列云滴组成,远观像云,近视无边,具有期望值、熵和超熵三个数字特征。在数据挖掘过程中,云模型既采用定量的计算来分析和处理数据,也充分重视定性思维和描述的作用。它把定性分析和定量计算结合起来,用语言值把握过于复杂无法数值化的量的不确定性,通过定性和定量相互间的映射来反映食物在量的确定性上的差异,可以有效地表达和处理融模糊性和随机性为一体的空间数据不确定性。目前,云模型已被用于挖掘空间广义知识和关联规则、表达发现的知识、连续数据离散化、空间数据库的不确定性查询和不确定性推理、遥感影像的解译和识别等。

7 结 论

基于以上空间数据挖掘的几种理论方法的分析,聚类方法与基于分类的方法在数据挖掘方面应用的比较广泛,而其余的几种方法例如神经网络等也已经应用于数据挖掘,但是每一种理论方法都有一定的局限性,这些方法都各有特色,空间数据挖掘所用理论方法的好坏直接影响到所发现知识的优劣,有时会取得很好的结果。当然,这些方法不是孤立应用的,为了发现某类知识,常常要综合应用这些方法。知识发现方法还要与常规的数据库技术充分结合。例如,在时空数据库中挖掘空间演变规则时,首先可利用空间数据库的叠置分析等方法提取出变化了的数据,再综合统计方法和归纳方法得到空间演变规则。另外,人工智能和模式识别的新技术、遗传算法[27](Genetic Algorithms)等都被用于空间数据挖掘中,虽然这些方法并不普遍地应用于空间数据库,但它们的一些方法会对数据挖掘有所启发,已经成为数据挖掘算法的热点。

[1]吕安民,人口空间数据挖掘及其应用方法研究[D].武汉大学博士论文,2002.

[2]刘 芳,数据开采中的聚类算法研究[D].华中科技大学博士学位论文,2003.

[3]李德仁,王树良,李德毅,等.论空间数据挖掘和知识发现的理论与方法[J].武汉大学学报.信息科学版,2002,27(3):221-233.

[4]Li C,Biswas C.Unsupervised Clustering with Mixed Numeric and Nominal Data-A New Similarity Based Agglomerative System[C]//Proceedings of the 1st Pacific-Asia Conference on KDD&Data Mining,Singapore,1997:35-48.

[5]Zhang T,Ramakrishnan R,Livny M.BIRCH:an efficient data clustering method for very large databases[J].ACM SIGMOD Record,1996,25(2):103-114.

[6]Sudipto G,Rajeev R,Kyuseok S.CURE:An Efficient Clustering Algorithm for Large Database[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.Seattle,Washington,United States,1998:73-84.

[7]Leonard K,Peter J R.Finding Groups in Data:An Introduction to Cluster Analysis[M].9th ed.,New York,USA:John Wiley and Sons,1990:30-66.

[8]Raymond T N,Han J W.Efficient and Effective Clustering Methods for Spatial Data Mining.[C]//Proceedings of the 20th International Conference on VLDB,Santiago,Chile,1994:144-155.

[9]Wang W,Yang J,Richard M.STING:A Statistical Information Grid Approach to Spatial DataMining[C]//Proceedings of the 23rd VLDB Conference.Athens,Greek,1997:186-195.

[10]Gholamhosein S,Surojit C,Zhang A D,WaveCluster A.M ulti-ResolutionClustering Approach for Very Large Spatial Databases[C]//Proceedings of the 24th VLDB Conference,New York,USA,1998:428-439.

[11]Agrawal R,Gehrke J,Gunopulos D,Raghavan P.Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[C]//Proceedings of the ACM SIGMOD,Seattle,Washington,USA,1998,27(2):94-105.

[12]Ambroise C,Dang M,Govaert G.Geostatistics for Environmnental Applications.Dordrecht[M].Kluwer Academic Publisher,Dordrecht,1997:493-504.

[13]Dempster A P,Laird N M,Rubin D B.M aximum Likelihood from Incomplete Data via the EM algorithm.[J].Journal of the Royal Statistical Society,Series B,1977,39(1):1-38.

[14]Kohonen T.Self Organization and Associtive Memory[M].3th ed.New York:Springer Verlag,1989:21-62.

[15]Carpenter G A,Grossberg S.ART2:Self-organization of stable category recognition codes for analog input patterns[J].Applied Optics,1987(26):4919-4930.

[16]Hinneburg A,Keim D A.An efficient approach to clustering in large multimedia databases with noise[C]//Proceedings of the 4th International Conference on Knowledge Discovery and Data mining.New York,USA,1998:58-65.

[17]王 珏,苗夺谦,周育键.关于Rough Set理论与应用的综述[J].模式识别与人工智能,1996,9(4):337-344.

[18]Xu L.Rival Penalized Competitive Learning for Clustering Analysis,RBF Net,and Curve Detection[J].IEEE Transactions on Neural Networks,1993,4(4):636-649.

[19]Micalski R S,Chilausky R L.Learning by being Told and Learning from Examples:An Experimental Comparison of Two Methods of Knowledge Acquisition in Context of Developing on Expert System for Soybean Disease Diagnosis[J].Policy Analysis and Information Systems,1980(4):125-150.

[20]Quinlan J R.Combining instance-based and modelbased learning[C]//Proceedings of the Tenth International Conference on Machine Learning,San M ateo,1993:236-243.

[21]Quinlan J R.C4.5:Programs for Machine Learning[M].M organ Kaufmann Publishers,1993:1-42.

[22]Eugene G,William H.H,and Mikhail V,etal.Bayesian Network Models for Automatic Generation of Crisis Management Training Scenarios[C]//Proceedings of the 10th Innovative Applications of ArtificialIntelligence Conference(IAAI-98),Madison,Wisconsin,USA,1998:1113-1120.

[23]Han J,Fu Y J.Exploration of the Power of Attribute-Oriented Induction in Data Mining[J].Advances in Knowledge Discovery and Data Mining,1996:1-19.

[24]Lu W,Han J.Discovery of general knowledge in large spatial databases[C]//Proceedings of the Far East Workshop on Geographic Information Systems,Singapore,1993:275-289.

[25]Koperski K,Han J.Discovery of spatial association rules in geographic information databases[C]//Proc 4th Int′l Symp.on Large Spatial Databases(SSD′95),Portland,Maine,1995:47-66.

[26]Li D Y.Knowledge Representation in KDD Based on Linguistic Atoms[C]//Proceedings of the 1st Pacific-Asia Conference on KDD&DM,Singapore,1997:23-24.

[27]Holland J H.Adaptation in Natural and Artificial System[M].USA:The University of Michigan Press,1975:1-37.