面向大数据的空间数据挖掘综述

2017-02-16杜江毅边馥苓

地理空间信息 2017年1期

关键词：空间数据数据挖掘聚类

杜江毅，边馥苓

（1. 武汉大学测绘遥感信息工程国家重点实验室，湖北武汉 430079；2. 湖北工业大学计算机学院，湖北武汉 430068；3. 武汉大学国际软件学院，湖北武汉 430079）

面向大数据的空间数据挖掘综述

杜江毅1,2，边馥苓3

随着大数据时代的到来，海量空间数据与获取手段不足的矛盾日益显著，空间数据挖掘的地位日益提高。从大数据的含义出发，分析了空间数据与大数据的关系，回顾了传统空间数据挖掘存在的问题，最后从平台和算法两个方面探讨了空间大数据挖掘的最新研究进展。

大数据；空间数据挖掘；云计算

近年来，大数据已经引起了学术界、产业界和政府部门的高度关注。实际上，人类第一次开始关注大数据是在1980年，当时著名的未来学家阿尔文·托夫勒就热情洋溢地称呼大数据为“第三次浪潮的华彩乐章”[1]。在学术界，最早关注大数据的是Nature，2008 年9月其推出“Big Data”专刊，从多门学科的角度介绍了大数据所带来的机遇与挑战[2]。Science在2011年2月也推出了名为“Dealing with Big Data”的专刊，同样发表了与大数据相关的论点。在产业界，2011年5月McKinsey公司再次明确提出大数据的概念，并为企业和政府应对大数据的发展提出了自己的思考[3]。许多企业和组织也将大数据作为未来的主要业务，提出了多种大数据解决方案或应用，如IBM的InfoSphere大数据分析平台[4]。美、英等国政府也出台了多项政策和措施，以应对大数据的挑战[5-6]。

总之，正如舍恩伯格和库克耶[7]所说，“大数据开启了一次重大的时代转型”，“是人们获得新的认知，创造新的价值的源泉；还是改变市场、组织机构，以及政府与公民关系的方法”。如今大数据的价值不断被认可，它涉及到人类生活、企业发展、国家战略等各个应用领域[7]，而这些应用领域中的数据绝大多数与空间位置有关，如何从海量的空间数据中获取有价值的信息（空间数据挖掘）已成为大数据的主要应用方向[8-9]。

1 大数据时代的空间数据

1.1 大数据的定义

随着大数据在全世界的兴起，大数据的定义也呈现多种解释。一般来说，数据量的大小超过正常处理范围和大小、用户采用普通的软件工具和处理方法难以处理的数据集，即可称为大数据[6]。

2008年Nature中的定义为大数据“是人类认知过程的进步，规模是无法用目前的技术、方法和理论，在可容忍的时间内获取、管理、处理的数据集”[10]。Gartner公司认为大数据是一种体量巨大、增长极快、样式繁多的信息价值；需要采用新的处理方法和模式，才能确保其体现出更强更准确的决策力、洞察力、以及优化流程的能力[11]。这个定义最重要的意义在于明确了如何才能从这些快速增长的动态的数据集中获取有价值的信息，即大数据是三维的：容量、多样、速度，但它忽略了大数据具有的价值性。因此，IDC在2011 年的报告中给出了更能为人们所接受的大数据的定义：具有“4V”特点的数据集，即容量（Volume）、多样（Variety）、速度（Velocity）和价值（Value），就是大数据；同时，IDC指出，“大数据技术展现了一种技术及其构架的新时代，针对各种超大规模的数据集，以经济的方式，迅速地获取、发现和分析技术，提取价值”[12]。

1.2 时空数据是大数据的基础

大数据的复杂性，导致其难以被传统的技术所利用。这些数据中的绝大多数来源于空间数据，因为约80%的数据与空间位置有关[13-14]。

随着国民经济的快速发展，计算机技术和空间信息技术的不断进步和普及，具有时间属性并随时间变化而变化的空间数据——时空数据的获取量急速增加，形成了具有时空属性的大数据[15]。这些数据流客观存在，并被人为赋予地理编码与时间标签，从这个角度看，时空数据不仅是大数据的重要组成部分，更可被看成是大数据的基础。因此，时空数据与信息的存储与处理技术本身就是大数据存储与处理技术，只是前者更多是关注于地学领域，而后者涵盖几乎所有领域。

相比于传统空间数据，时空数据更加复杂和多样。它描述了研究对象随时间变化的运动轨迹，记录了对象的空间属性和时间属性，即“动态”的发展过程，具有数据量庞大、非线性以及时变等特征[16]。时空大数据被广泛地应用在国防、工业、农业、交通、气象等方面，如分析随时间变化的车辆运行状况和人流的移动规律所产生的时空数据，有助于改善交通状况，如图1所示。

图1 时空大数据的应用

时空数据形式多样，价值巨大，具有空间性、时间性、多维性、海量性、复杂性和不确定性等特点。这些数据虽然极大地拓宽了人类可利用的数据范围，但数量的激增和数据本身的一些不足，也极大地影响了数据的价值发现，如垃圾多、污染重、利用难等。要提高这些数据的单位价值，就不得不进一步发展数据挖掘等技术。

2 传统空间数据挖掘存在的问题

空间数据挖掘所用理论方法的好坏直接影响到所发现知识的质量。可用的理论方法主要有确定集合论、扩展集合论、仿生学方法、可视化、决策树等，其中包括：概率论、证据理论、空间统计学、规则归纳、聚类分析、空间分析、神经网络、遗传算法等[9]。经过多年研究，上述理论和算法都取得了很大的进展，但也存在一些问题：

1）目前多数的空间数据挖掘算法都是由传统的数据挖掘算法移植而来，并没有考虑空间数据与一般数据在存储、处理和特性等方面的区别，如面对高维海量的空间数据，目前的GIS不足以描述空间要素的多维信息结构，不能方便地进行多维信息的空间概括性分析，而且挖掘效率很低，因此采用传统算法往往会对空间数据和空间对象的利用不足，收不到良好的挖掘效果。

2）被污染的空间数据会直接影响空间数据挖掘，使其不能提供可靠的知识、优质的服务和决策支持。但实际上，从现实世界采集的数据绝大多数都是有污染的。无论采用什么方式获取的空间数据，都无可避免的存在一些问题或错误。如何减少受污染的数据对最终挖掘结果的影响，一直都是空间数据挖掘需要面临的重要问题。

3）空间数据具有明显的不确定性。这主要是由数据采样、数据模型抽象、空间概念和空间数据转换导致的[9]。当前的空间数据挖掘算法一般都是基于确定集合理论研究确定数据，也有一些对空间数据不确定性的研究，但主要是针对空间位置的不确定性，对数据本身的不确定性研究还显不足。

4）目前的空间数据挖掘技术还缺少适当的空间知识表达方法[9]。一般来说，对空间数据挖掘获得的知识的最好的表达方法是自然语言。但是，如何用定性的自然语言来较为准确地描述定量的数值之间的关系呢？如何描述知识发现中的支持度、置信度、强弱规则等专业名词呢？如何描述不确定的空间数据的随机性和模糊性呢？这些都是亟待解决的问题。

5）空间数据挖掘产生的所有模式并非都是用户需要的。因此需要一种技术来评估基于主观度量所发现的模式的兴趣度。这种评估根据给定用户类，基于用户的确信或期望，评估模式的价值。此外，通过使用兴趣度度量或用户指定的约束指导发现过程，也可更快更好地获得用户感兴趣的模式。

6）空间数据挖掘能为科学发展、商业管理、政府决策等活动提供有效的帮助，但也带来了泄露信息的风险。如何在保护空间数据隐私的前提下，进行成功的空间数据挖掘，也是目前空间数据挖掘面临的一大问题。

除了上述典型问题之外，空间数据挖掘还存在其他问题，如空间数据挖掘的智能化。毕竟无法要求每个人都学习和掌握空间数据挖掘技术，特别是在大数据时代下，空间数据挖掘面对海量的数据，要继续以往的辉煌，还需要研究者们更大的努力。

3 大数据时代空间数据挖掘进展

如何充分利用大数据，已成为当代一个新的热点问题，空间大数据挖掘应运而生。它是体现大数据价值、充分利用大数据的基础技术，可从大数据中提取信息，从信息中发现有价值的知识，让大数据为社会发展发挥更大的作用。

舍恩伯格和库克耶曾指出，在大数据时代，分析信息时面临的第一个转变就是我们有远超以往数据量的更多的数据用来分析，甚至拥有与某个特别现象相关的所有数据，而不再依赖于随机采样[7]。那么，如果想更快地分析更多的数据，选择优化的并行算法，并采用适合海量数据处理的平台，就成为人们目前最佳的选择。

3.1 传统空间数据挖掘研究进展

近年来，针对传统空间数据挖掘存在的问题，很多学者提出了新的有效方法。陈铭[17]提出了一种基于相似维的高维子空间聚类方法SDSCA——首先删除原高维数据空间中的冗余属性，然后运用相似维来寻找彼此相似的属性，最后在这些相似属性所形成的子空间上运用传统聚类算法进行聚类。石亚冰[18]等针对传统空间聚类算法K-means“对初始种子选取的依赖性过大，也容易陷入局部极小解”的缺点，提出了一种综合考虑空间数据对象特点的基于最大维密度选择方案的K-means优化算法，很好地消除了聚类结果的波动性，同时也较客观地呈现了空间对象的分布规律。

针对空间数据和空间数据挖掘的不确定性，何彬彬[19]等以EM和Apriori算法为基础，将空间数据和空间数据挖掘的不确定性进行结合，提出了一种新的挖掘算法模型，提高了挖掘的真实性和客观性。

空间数据清理是空间数据挖掘的重要工作之一。根据空间数据清理的实际特点，Kim W[20]等提出了处理由未知属性值造成的数据噪声的方法。徐扬[21]等提出了一种针对重复数据的清理方法：先对所有记录按照预先指定的属性项进行排序，然后比较排序数据，从而检查出重复记录的方法。

陈霞[22]和陈桂芬等利用时序算法和可视化技术，充分挖掘了大量农业数据中的价值，为农作物的种植提供有力的决策依据，并为空间数据挖掘的利用提出了一个新的思路。

自从1999年Rakesh Aggrawal在KDD会议上提出将“隐私保护数据挖掘”作为数据挖掘领域未来研究的重点之一以来，数据挖掘中的隐私保护已成为一个研究热点，特别是针对高维数据进行的挖掘。Nergiz M E[23]等提出了用于应对高维问题的基于聚类的MiRaCle匿名算法，该算法是基于对多关系K-匿名数据库的严格假定，它匿名的过程比传统方法高效。Ghinita G[24]等提出了多维数据的l-多样性的匿名算法，能够保证每个事物具有不同的准标志属性和敏感值，防止高维数据在隐私保护时可能的信息丢失，也能保持准标志属性和敏感值间的关系。针对稀疏多维数据，Terrovitis M等提出了Km匿名方法——从具备部分敏感值的数据中保护数据，其信息丢失也较少[25-26]。

总之，传统的空间数据挖掘虽然在大数据时代遇到了新的挑战，但仍然有着重要的研究意义，仍然是获取数据价值的最有效途径之一。

3.2 基于云计算的空间大数据挖掘研究进展

面对海量的数据，除了优化传统的空间数据挖掘算法，提高空间数据质量以外，采用专门处理大数据的平台也是一个重要的选择，这就必须提到云计算。云计算是一种可以提供更强大的处理能力、更廉价的处理条件的完善系统。基于云计算的数据挖掘系统，可以透明地为用户服务；用户不需要了解系统运行原理与过程，也不需要担心系统的存储和安全问题，只需要知道选择合适的算法，就可以获得有价值的知识。图2是基于云计算的海量数据挖掘服务的层次结构图[27]。

图2 基于云计算的海量数据挖掘服务的层次结构图

1）基于云计算的数据挖掘系统研究。中国科学院计算技术研究所开发的PDMiner是目前国内最早的基于云计算平台Hadoop的并行数据挖掘系统平台。它实现了各种并行数据挖掘算法，如数据预处理、关联规则分析以及分类、聚类等算法；能够处理大规模数据集；整合了已有的计算资源，提高了计算资源的利用效率[28]。中国移动研究院早在2007年就开始了云计算平台下数据挖掘系统的研究，启动了“大云”的研发工作；并研发出基于Hadoop的并行数据挖掘工具——BC-PDM。厦门大学数据挖掘研究中心与台湾铭传大学资讯工程系、中华资料采矿协会合作开发了云端数据挖掘决策系统MCU Smart Score，它是一套基于云计算的数据挖掘决策支持系统。Weka是由Waikato大学开发的基于Java语言的数据挖掘平台，它集成了适合数据挖掘的当今最新的机器学习算法（如分类、聚类、关联规则、回归等）和数据预处理工具，在兼容性和可扩展性方面有独特的优势[29-30]。Apache Mahout是全新的开源项目数据挖掘平台，主要包括推荐、聚类、分类3部分，并可通过使用Apache Hadoop 库有效地扩展到云中[31-32]。

2）基于云计算的数据挖掘算法研究。目前国内外针对基于云计算的数据挖掘算法的研究较多。例如，首都师范大学周丽娟教授[33]等提出的云计算环境下的基于复合链表挖掘的并行FP-Growth算法。该算法在传统的FP-Growth算法基础上进行了优化，一定程度上解决了传统FP-Growth算法的性能瓶颈，实现了更高的效率和更好的扩展性。信息工程大学的李宏伟教授[34]等则用到了概念格的理论，提出了一种基于概念格的已知空间依赖剔除策略。该策略实现了对冗余规则和已知空间依赖的有效剔除。CAO X J[35]利用MapReduce计算框架，并结合粒计算，实现了关联规则挖掘的算法。林长方[36]等针对关联规则典型算法Apriori提出了基于MapReduce框架的简单并行算法，并在该算法的基础上，提出了一种采用固定多阶段结合挖掘策略的改进算法。

4 结语

大数据已成为政策界和学术界最火热的名词之一，不过也有专家对大数据的火热提出了质疑，如清华大学的王程韡[37]通过引入反事实思想实验提出大数据虚热的判断。不过无可置疑的是，当今世界对大数据的普遍认知为：大数据确实开启了一次重大的时代转型，它正在改变我们的生活。正如格雷所说，大数据是代表着“大趋势”的科学研究“第四范式”[38]。在大数据时代，传统的空间数据挖掘技术面对海量的数据，要想实现从“无穷”的数据中发现有价值的知识，需要从理论、算法和云平台等方面做出巨大的改善。

[1] 阿尔文·托勒夫．第三次浪潮[M]．黄明坚译．北京:中信出版社,2006

[2] Nature． Big Data[EB/OL]．http://www．nature．com/news/ specials/bigdata/index．html,2015-03-01/2015-09-15

[3] McKinsey Global Institute． 2011 Big Data: The Next Frontier for Innovation, Competition, and Productivity[R]．2011

[4] IBM-InfoSphere平台-中国[EB/OL]． http://www-01．ibm．com/ software/cn/data/infosphere/?re=masthead, 2015-03-01/2015-09-15

[5] The White House Office of Science and Technology Policy．Fact Sheet: Big Data Across the Federal Government[R]． 2012

[6] 胡雄伟,张宝林,李抵飞．大数据研究与应用综述(上)[J]．标准科学,2013(9):29-34

[7] 维克托·迈尔·舍恩伯格,肯尼思·库克耶．大数据时代:生活、工作与思维的大变革[M]．盛杨燕,周涛译．杭州: 浙江人民出版社,2012

[8] 王树良,丁刚毅,钟鸣．大数据下的空间数据挖掘思考[J]．中国电子科学研究院学报,2013,2(1):8-17

[9] 李德仁,王树良,李德毅．空间数据挖掘理论与应用(第二版)[M]．北京:科学出版社,2013

[10] Graham Rowe D, Goldston D, Doctorow C, et a1．Big Data: Science in the Petabyte Ara[J]．Nature,2008,455(7209):8-9

[11] JI C Q,LI Y, QIU W M, et al． Big Data Processing in Cloud Computing Environments[C]//Proc of the 12th International Symposium on Pervasive Systems, Algorithms and Networks, 2012:17-23

[12] Gantz J, Reinsel D． Extracting Value from Chaos [EB/OL]．http:// www．emc．com/collateral/analyst-reports/idc-extractingvalue-from-chaos-ar．pdf,2010/ 2015-03-01

[13] Densham P J, Goodchild M F． Spatial Decision Support Systems: a Research Agenda[C]//Proceedings GIS/LIS'89, Orlando, FL, 1989:707-716

[14] Shekhar S, XIONG H． Encyclopedia of GIS[M]． New York: Springer, 2007

[15] LI X, CHENG G D, LIU S M, et al． Heihe Watershed Allied Telemetry Experimental Research (HiWATER)[J]． Bulletin of American Meteorological Society,2013,94(8):10

[16] 曹闻．时空数据模型及其应用研究[D]．郑州:信息工程大学,2011

[17] 陈铭．高维聚类算法研究[D]．南京:南京师范大学,2011

[18] 石亚冰,元昌安,覃晓,等．基于最大维密度的全局优化空间聚类算法[J]．计算机仿真,2013,30(3):277-280

[19] 何彬彬,方涛,郭达志．不确定性空间数据挖掘算法模型[J]．中国矿业大学学报,2007,36(1):121-125

[20] Kim W, Choi B J, HONG E K, et al． A Taxonomy of Dirty Data[J]．Data Mining and Knowledge Discovery,2003(7):81-99

[21] 徐扬,冯克忠,马亚明．空间数据重复记录的清理方法研究[J]．测绘科学,2008,33(6):125-126

[22] 陈霞．基于时序算法的可视化空间数据挖掘研究与应用[D]．长春:吉林农业大学,2012

[23] Nergiz M E, Clifton C, Nergiz A E． MultiRelational K-anonymity[C]//Proc of the 23rd IEEE International Conference on Data Engineering,2007:1 417-1 421

[24] Ghinita G, TAO Y F, Kalnis P．On the Anonymization of Spare High-dimensional Data[C]//Proc of the 24th International Conference on Data Engineering,2008:715-724

[25] Terrovitis M, Mamoulisn, Kalnis P． Privacy Preservation in the Publication of Spare Multidimensional Data[M]． London: Taylor and Francis Group,2011:35-56

[26] 张海涛,黄慧慧,徐亮,等．隐私保护数据挖掘研究进展[J]．计算机应用研究,2013,30(12):3 549-3 535

[27] 贺瑶,王文庆,薛飞．基于云计算的海量数据挖掘研究[J]．计算机技术与发展,2013(2):69-72

[28] 何清,庄福振,曾立,等． PDMiner:基于云计算的并行分布式数据挖掘工具平台[J]．中国科学:信息科学,2014(7):871-885

[29] Hall M, Frank E, Holmes G, et al． The WEKA Data Mining Software: an Update[J]． ACM SIGKDD Explorations,2009, 11(1):10-18

[30] Witten I H Frank E． Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations[M]．Morgan Kaufman'2003

[31] 朱倩,钱立．基于Mahout的推荐系统的分析与设计[J]．科技通报,2013,29(6):35-36

[32] 马宁．基于Mahout的推荐系统的研究与实现[D]．兰州:兰州大学,2013

[33] 周丽娟,王翔．云环境下关联规则算法的研究[J]．计算机工程与设计,2014,35(2):499-503

[34] 李宏伟,陈虎,王振宇,等．基于概念格的空间关联规则挖掘优化[J]．测绘科学技术学报,2013,30(3):304-307

[35] CAO X J． An Algorithm of Mining Association Rules Based on Granular Computing[J]． Physics Procardia,2012,33:1 248-1 253

[36] 林长方,吴扬扬,黄仲开,等．基于MapReduce的Apriori算法并行化[J]．江南大学学报,2014,13(4):411-415

[37] 王程韡．“大数据”是“大趋势”吗:基于关键词共现方法的反事实分析[J]．科学学与科学技术管理,2015,36(1):3-11