空间数据挖掘的理论及发展历程

1989年8月举行的第十一届国际联合人工智能学术会议上首次出现了数据挖掘的概念。其后，出现了众多的研究机构、学术会议和期刊。2000年，J.Han教授出版第一本数据挖掘的专著——《数据挖掘：概念与技术》，系统介绍了数据挖掘的基本概念、基本方法和基本技术以及数据挖掘的最新进展，数据挖掘的研究进入一个崭新的时期。近年来，随着计算机技术的迅猛发展，人们获取与收集数据的能力大大提高，数据量以前所未有的速度迅速增长。面对海量的数据，数据挖掘技术也得到迅猛的发展，成为目前国际上数据库和信息决策领域最前沿、最活跃的研究领域之一，引起了学术界和工程界的广泛关注。最近Gartner Group的一次高级技术调查将数据挖掘和人工智能列为“未来3～5年将对工业产生深远影响的五大关键技术”之首，同时还将并行处理体系和数据挖掘列为未来五年内投资热点的十大新兴技术前两位。

现代数据采集技术的发展，促使数据量迅速膨胀，也导致了人们利用数据的困难。数据挖掘应运而生，空间数据挖掘为其主要的研究内容。长期以来，人们常常使用数据挖掘的方法研究空间数据挖掘，而较少考虑空间数据的独有特征。实际上，相对一般的事务数据挖掘而言，空间数据挖掘更为复杂，挖掘的对象不仅包含位置数据和属性数据，还有实体间的空间关系，而且空间数据的结构也比较复杂，既有表格数据，也有矢量数据和栅格数据。

我国李德仁院士等首次提出了从GIS数据库中发现知识(knowledge discovery from GIS，KDG)，希望通过数据挖掘方法将GIS有限的数据变成无限的知识，使GIS成为智能化的信息系统(Li Deren＆Cheng Tao，1994)。随后的研究，李德仁院士又进一步发展了空间数据挖掘的概念和方法，将KDG发展成为空间数据挖掘与知识发现(spatial data mining and knowledge discovery，SDMKD)，从而奠定了空间数据挖掘的理论方法与技术体系。2000年，邸凯昌博士出版了《空间数据挖掘与知识发现》专著，较为系统地总结了空间数据挖掘研究的内容和方法，这也是本领域出版的第一本学术专著。其后李德仁院士和他的学生王树良于2006年出版了《空间数据挖掘理论与方法》一书，更为系统地介绍了空间数据挖掘的理论与方法。空间数据挖掘与知识发现是数据挖掘研究的一个分支，其目的是从数据库系统中抽取隐含人们感兴趣的空间模式和特征，发现空间数据域非空间数据之间关系等，构建空间知识库。

1.空间数据挖掘的理论研究

空间数据挖掘是一种决策支持过程，基本知识类型是规则和例外，理论方法的好坏将直接影响到所发现知识的优劣。已经使用或发展了的空间数据挖掘的理论方法，根据面对的空间数据对象，可以分为基于确定数据的和基于不确定性数据的，主要包括概率论、证据理论、空间统计学、规则归纳、聚类分析、空间分析、模糊集、云模型、数据场、粗集、地学粗空间、神经网络、遗传算法、可视化、决策树、空间在线数据挖掘等，并都取得了一定的成果(Ester et al.，2000；王树良，2006)。许多学者开展了相关研究取得了丰硕的成果，Grabmeier和Rudolph(2002)总结了空间数据聚类发现技术，分析了基于统计学、数据挖掘和地理信息系统的空间模式识别和知识发现方法。Koperski等(1996)认为巨量的空间数据来自遥感、地理信息系统、计算机制图、环境评价和规划等各种领域，数据挖掘已经从关系数据库和交易数据库扩展到空间数据库，并就空间数据生成、空间数据聚类和空间关联规则挖掘等方面总结了空间数据挖掘的最近发展。Han和Kamber(2001)在他们的数据挖掘专著中，系统讲述了空间挖掘的概念和技术。李德仁和王树良等用两篇学术论文系统地概述了空间数据挖掘的产生和发展，研究了空间数据挖掘的含义，可发现的空间关联特征、分类和聚类等知识，以及它与数据挖掘、机器学习、地学数据分析、空间数据库、空间数据仓库、数字地球等相关学科的关系，分析了空间数据挖掘的应用开发，讨论了可用于此的理论和方法，并展望了空间数据挖掘的研究和应用前景(李德仁等，2001，2002)。空间数据挖掘的理论体系基本形成。目前空间数据挖掘的方法大多来自相关学科，如机器学习、统计学、软计算方法、模式识别和信息论等，尚未形成相对独立的方法体系。不少学者对数据挖掘和空间数据挖掘的方法进行了总结和划分。空间数据挖掘的方法体系是开放的，近年来，在实际应用过程中主要是综合使用它们，并充分汲取成功的机器学习和人工智能技术，出现了大量的应用成果和领域空间数据挖掘。

2.空间数据挖掘的应用研究

空间数据挖掘从数据挖掘发展而来，数据挖掘的成功算法和应用系统在很大程度上影响着它的进展。因此，在讨论空间数据挖掘的应用之前，有必要先简要总结数据挖掘的典型应用成果。数据挖掘能有效利用大型数据集，为决策者提供极有价值的知识，带来不可估量的效益。在市场营销，金融银行、电信、交通、保险、政府和防卫部门等应用领域中，数据挖掘最为活跃，并开发了很多应用产品。目前数据挖掘已经渗透到人们的社会经济活动中，就连美国联邦调查局(FBI)也开始应用该项技术。数据挖掘可以作为决策支持系统的一个重要组成部分，用于市场调查、市场策略制定、金融分析、企业决策支持等。目前数据挖掘可以为决策者提供极有价值的知识，并带来了巨大的效益(Han and Kamber，2001；王树良，2006)。

空间数据挖掘也具有广泛而重要的现实作用，能够指导发现新空间实体、进行空间决策、浏览空间数据库、理解空间数据、发现空间联系以及空间数据与非空间数据之间的关系、重组空间数据库、构造空间知识库、优化空间查询等。虽然相对于数据挖掘，空间数据挖掘的研究和发展较为薄弱。但是由于数据挖掘的发展基础、空间数据的基础设施作用以及数字地球和数字城市的建设需要，空间数据挖掘的应用成果日益扩展，其效益是不可估量的。如SKICAT已经发现了16个新的极其遥远的类星体，POSS系统将天空图像中的星体对象分类准确性从75%提高到94%，MagellStudy系统通过分析启明星表面的大约30000幅高分辨率雷达影像，识别了火山等。空间数据数据挖掘的应用范围正在扩大，逐步渗透到地理信息系统、信息融合系统、遥感影像、图像数据库、城镇规划、气象预报、医疗影像处理、导航和机器人等方面。

(1)聚类算法的研究进展

在半个多世纪中，聚类算法沿着多个方向不断得到发展依赖于新兴的优化技术、主要的方法学以及应用领域。从一般聚类的算法特征上看，目前比较成熟的聚类算法主要有以下几种：划分法(K-means算法、K-中心点算法、PAM算法、CLARA算法、CLARANS算法)、层次法(CURE算法、CHAMELEON算法、BIRCH算法、Chameleon算法、AutoCluster算法)、基于密度的方法(DBSCAN算法、OPTICS算法)和基于网格的方法(BIRCH算法、BUBBLE-FM算法、STING算法、DBCLASD算法、CLIQUE算法)等。随着对数据聚类研究的不断深入，新的聚类算法不断涌现以适应新的挖掘任务的要求，如使用数据场、粗集、模糊集和小波分析等理论进行空间聚类，这些算法都是在传统算法的基础上集成了多种聚类方法的思想，具有各自的特点，但也有一定的局限性。近年来，有部分学者受到免疫系统机制启发，在数据聚类领域提出了不同的人工免疫算法模型，用于数据聚类分析、数据浓缩、归类任务，取得了不少有益的成果。Hunt和Cooke(1999)研究了基于AIS模型的无监督学习算法，将其用到了DNA序列的分类任务中。Cooke构造的AIS无监督学习算法在执行聚类任务方面取得比决策树、ANN和最小临近法更好的效果，其误差率仅为3%。在对人工免疫算法与聚类分析、Kohonen网络进行对比分析后，J.Timmis(2000)指出AIS用于数据分析是可行且有效的，可对训练数据进行建模，对输入空间的大区域有泛化能力，并能对得到的进化网络提供更好的解释，获取更多的有用信息。De Castro(2002)基于免疫网络模型aiNET对高维原始数据进行聚类分析，进一步揭示出数据簇内的相互关系。实验证明，该方法是一种非常有效的数据聚类分析方法。国内方面，王磊、郑建国等(2003)把人工免疫原理与小波神经网络相结合用于数据挖掘中数据库规则的获取。李洁、焦李成(2004)提出了一种有限资源的模糊神经网络结构聚类方法，并将其用于混合属性特征大数据集聚类算法，取得了不错的效果。莫宏伟(2005)在aiNET和AIRS的基础上提出了人工免疫网络记忆分类器，并将其成功地用于网络文本聚类。(www.xing528.com)

(2)空间聚类的研究进展

随着各种复杂特殊数据库的广泛应用，对聚类任务提出了更新的要求，聚类方法和技术的研究也面临着新的挑战，在空间聚类领域这一现象显得尤为突出。为了解决海量、高维的空间数据处理问题，通过对传统的聚类算法进行改进并引入到空间聚类问题的研究中，并取得了丰硕的成果(B.M.H.Romeny，1997)，如S.Shehroz(1999)等人改进K-Means用于空间数据的聚类，Ng(2002)提出了一种扩展CLARANS算法用于面状实体的聚类等。这些研究中大多是结合领域问题改进聚类算法或距离测度函数来解决空间聚类问题的，在复杂空间处理上，传统算法的引进还是有一定的局限性的。带有非空间属性的空间数据聚类是目前空间聚类研究的热点和难点。李新运(2004)提出了坐标与属性一体化的空间聚类模型；杨春成(2005)提出了一种满足旋转与平移不变性的线段链形状相似性评价方法，该方法计算简便，适用于面状地理实体聚类分析；Lin(2005)首次使用双重聚类(Dual clustering)来指代这样一类空间聚类问题：聚类结果中各子类在空间域上连续、在属性域上相近，由于空间域和属性域的不可比性，对空间聚类算法中的空间距离度量和属性扩展都具有一定的人为任意性；Keh-Shih Chuang(2006)等利用图像中像素含有的空间自相关性，提出了一种包含空间信息的模糊c-means聚类算法；郭庆胜(2008)基于原始的点集合生成的DT构建相应的GG、UG、MST和NNG，然后在所选择的密度适应性约束、距离适应性约束和偏差适应性约束这三种条件下，利用所生成的临近图进行了点群的层次聚类；李光强(2008)针对传统空间聚类算法没有同时考虑空间位置关系和非空间属性的不足，引入直接可达和相连概念，提出了一种基于双重距离的空间聚类方法(dual distance based spatial clustering，DDBSC)；杨春成(2009)综合考虑距离和几何形状相似性来设计聚类准则，并实现相应的聚类算法；宋晓眉(2010)分析了图斑k阶临近图的特征及层次关系，对层次聚类方法进行改进，使得聚类的时空信息的结合灵活有效；刘启亮(2011)从力学的角度来考虑空间聚类问题，并结合地理学基本规律提出了一种基于力学思想的空间聚类有效性评价指标；邓敏(2011)从空间数据场的角度出发，提出了一种基于场论的层次空间聚类算法(HSCBT)，该算法是通过模拟空间实体间的凝聚力来描述空间实体间的相互作用，进而采取层次凝聚的策略进行聚类；刘启亮(2011)借助Delaunay三角网构建空间临近关系的优势，通过施加不同层次、不同类型的约束，提出一种空间聚类的新方法。这些空间聚类模型主要是针对某一应用领域提出的，虽然能够解决一定的问题，但是没有形成统一框架下的空间聚类模型。

空间聚类的发展还依赖于针对空间信息特征的聚类算法的研究。近年来，空间聚类还将其他学科的最新研究成果如图论、模糊数学(S.Eschrich et al.，2003)、人工智能(U.Mali，2000)引入空间聚类研究中，如Witold Pedrycz(2005)将模糊数学引用于空间数据聚类中，郑涛(2006)使用数据场概念对CLARA算法进行了改进，并应用于大型多维空间数据的处理，优化了聚类的结果。关于空间聚类最新的研究成果是提出了许多基于遗传算法的聚类算法(U.Mali，2004；杨春成，2006)，但该方法收敛速度较慢、容易出现早熟，这一直是不能解决大规模应用的瓶颈问题；王家耀(2006)设计了一种遗传k-均质空间聚类分析算法，该算法兼顾了局部收敛和全局收敛性能；梁勤欧(2011)改进了人工免疫网络模型和克隆选择算法并用于空间聚类研究；陈应显(2011)提出了一种基于粒子群优化算法的空间聚类分析方法，并对相应的适应度函数进行了改进。

3.土地利用领域的空间数据挖掘

计算机数据采集和存储技术的发展，使得数据库急剧膨胀，这造成了“数据过量而知识贫乏”的瓶颈。在这些数据中，大约80%与地理分布有关，例如空间数据。面对持续增长的海量空间数据，人们由于难以在没有知识辅助的情况下完全理解数据，因此开始关注数据挖掘中的空间数据挖掘。除了数据挖掘的共性，空间数据挖掘还有自己的特性。它不仅包含位置和属性数据，还有实体间空间关系，而且空间数据的结构也比较复杂，既有表格数据，也有矢量数据、栅格数据。可是，人们几乎是在用数据挖掘的方法研究空间数据挖掘，却很少顾及数据的空间特征(Lotfi A.Zadeh，2005)。

将数据挖掘技术作用于土地数据库，挖掘土地利用系统背后掩藏的有关土地利用结构、格局、土地利用动态演化、土地利用系统与社会经济系统之间的关联关系等，是深入认识土地利用系统本质，指导土地利用规划和科学管理的要求。近年来已有相关研究的开展，如T.Tsegaye等于2005年整合卫星、气候、生物、大气等相关数据，基于数据挖掘技术，研究了干旱预测及其与植物生长之间的关联关系；B.Ekasingh等(2005)基于数据挖掘方法进行了农户作物种植选择行为进行了模拟；Q.Wu等(2007)研究了基于数据挖掘技术的土壤侵蚀评价；Mignolet等在2007年基于数据挖掘研究了塞纳河盆地农作活动空间动态特征。在国内，相关学者也进行了一些基础研究工作，如郑新奇等(2005)基于土地利用现状数据库和城镇地籍数据库，开展了土地利用数据整合、预处理和数据挖掘算法的研究；刘耀林等(2004，2005)研究了基于云理论和粗糙集的土地适宜性评价和基于决策树空间数据挖掘的城镇土地定级估价方法；刘耀林等(2006)研究了可视化交互空间数据挖掘技术在土地定级中应用以及可视化交互空间数据挖掘原型系统设计与实现；朱庆伟、苏里等(2006)应用粗糙集提取了土壤侵蚀度与植被、坡度和耕地之间的关联关系。贾泽露(2006)、孙元军(2008)研究了土地分等定级的数据挖掘，并设计实现了土地定级专家系统；刘洋(2008)提出了改进的禁忌搜索算法，并将这一算法应用在土地整理分区中；王坤(2009)研究了微粒群算法在土地用途分区中的相关理论；樊敏(2009)基于群体智能优化算法对土地评价进行了数据挖掘，导出了土地评价的分类规则。

Hansen等(2003)选择了16个属性指标利用决策树方法对土地覆盖进行了分类，Eklund等(2002)选择了多个自然地理要素产生了土壤二次盐碱化类型分类规则，周成虎等利用互信息原理提出了时空分割聚类模型，肖平等利用神经网络技术建立了遥感影像分类方法。这些空间聚类和分类方法并未充分考虑空间实体的位置坐标和空间关系，对类内的实体或地域单位，只能刻画其属性上的相似性，而不能充分反映位置上的邻近性，仍然是基于属性的数据挖掘方法。与此不同，Huang等(2006)建立的土壤分类规则中，把位置坐标引入了条件属性，使分类准则与坐标有一定的对应关系。目前基于统计学和模糊集的分类算法已较成熟，基于神经网络、遗传算法、决策树、粗糙集等的分类算法研究也有很多成功的案例，但如何基于空间关系与属性指标一体化的空间对象模型建立新的空间-属性混合距离测度，并纳入空间聚类和分类计算模型，真正反映出类内“属性相似，空间相近”，类间“属性相异，空间相离”的空间分类规则，急需开展深入研究。

土地用途分区具有计算密集与数据密集的特点，现有的克隆选择算法多是基于串行计算设计的，优化计算效率低，仅适于小规模数据的实验验证研究，难以对大区域范围的土地利用空间进行运算。近年，随着网格、集群、桌面超级计算机、云计算、多核处理器、固态硬盘等先进计算设施的出现，新型硬件架构为实现全球或区域性的复杂地理计算提供了高性能计算基础，并行地理计算已成为解决复杂地理计算性能瓶颈的可行途径。由于人工免疫系统的经典算法是对种群进行迭代运算，所以具有天然的并行处理特性，非常适合在大规模并行计算机上实现。但是，目前模拟生物免疫系统并行性的工作还屈指可数(戚玉涛，2008)。A.Watkins(2003)利用免疫系统潜在的并行性研究了并行克隆选择算法，以提高效率。随后出现的AIRS并行化算法进一步说明了并行技术能够有效地应用于人工免疫系统算法，大幅度提高算法的求解能力(J.Timmis，2010)。刘耀林(2014)开发了土地利用优化配置人工免疫并行决策支持系统。现有的研究多是对已有人工免疫算法的并行实现，关于并行人工免疫系统模型的研究尚不多见。