时空关联规则挖掘综述

杨汉雨

摘 要：当前智慧城市的建设还停留在数字城市阶段，但随着“互联网+”和“地理时空大数据”等外部因素的推动，智慧城市的建设迎来了良好的发展机遇，迫切需要“大数据思维”去推动数字城市向智慧城市发展，挖掘隐藏在数字城市中的知识。本文针对空间对象存在普遍的关联性出发，研究了关联规则挖掘的相关知识。分析了空间关联规则挖掘和时空关联规则挖掘的现状；文章最后指出了时空关联规则挖掘现状存在的问题，并给出了初步的研究方案。

关键词：智慧城市；时空数据挖掘；关联规则；空间自相关

1.引言

随着互联网的高速发展，信息爆炸已经积累到了引发科学研究范式变革的程度，大数据时代已经来临。以3S技术、云计算、互联网、物联网等技术为基础，使得地球空间与自然、人文对象的数据能够更容易的被量测、存储、管理、分析、显示，进而反映自然与人文现象的空间分布规律，提供地理信息智能服务，构建智慧环境，如智慧城市、智慧战场、智慧中国、智慧地球等。以智慧城市建设为例，当前智慧城市的建设还停留在数字城市的阶段，但随着“互联网+”和“地理时空大数据”等外部因素的推动，迫切需要“大数据思维”去发掘“地理时空大数据”的潜在价值，进而加速智慧城市的建设。

空间数据挖掘（SDM）是地理时空大数据挖掘的基础，是从一个空间数据中提取出有效的、新颖的、潜在有用的、并能最终被人理解的模式的非凡过程，揭示出蕴含在数据背后的客观世界的本质规律、内在联系和发展趋势，实现知识的自动获取，从而提供技术决策与经营决策的依据，也是当前“智慧城市”建设的核心内容。空间数据挖掘包含的内容很多，包括空间聚类挖掘、关联规则挖掘等等内容。其中空间关联规则挖掘是空间数据挖掘的重要内容，其目的是发现现实世界中空间对象之间有趣的关联模式或相互关系。

2.关联规则的定义

关联规则首先由Agrawa，并应用于零售行业，实现从顾客的购买记录中发现顾客的购买模式，如“90%的男性顾客在购买了尿布的同时购买了啤酒”。这种购买模式即可以用X=>Y[s%，c%]形式的关联规则表示。根据这条关联规则，商场的决策者可以将摆放尿布的货架和摆放啤酒的货架放在一起，从而实现销量的增长。关联规则挖掘的实质就是从数据中找出频繁出现的模式，并以关联规则的形式表示出来。

3.时空关联规则挖掘的现状

3.1 空间关联规则挖掘现状

关联规则的研究主要集中在以下两个方面：一是基于事务数据库的关联规则挖掘，首先将空间数据离散化转换成事务数据库，然后再使用基于事务数据的关联规则算法对得到的事务数据库进行规则挖掘，从而得到感兴趣的空间关联规则，其中空间数据离散化和对关联规则算法进行改进来提高算法效率是该方法的两个研究重点；二是基于空间事务的关联规则挖掘，利用叠置分析、距离和面积计算等空间分析操作直接从空间图层中提取关联规则。

（1）基于事务数据库的方法

Koperski和Han首先将关联规则应用于空间数据挖掘，提出了一种空间关联规则挖掘方法，该方法采用自上而下的策略，由用户指定的领域作为空间关联规则挖掘的事务，先对粒度较大的空间谓词进行计算，发现较高概念层次的关联规则，然后再对空间谓词逐级细分发现较低层次的关联规则。这两个过程交替进行，直到无法发现新的规则为止。

（2）基于空间事务的方法

Lee和Hong等提出一种9DLT关联规则挖掘算法，使用空间关系九交模型表示图像之间关系，分别用数字0-8表示，并制作空间关系连接表，用来由k频繁项集连接得到（k+1）项候选集，同时给出针对这种空间关系表达的关联规则算法和剪枝策略。EstivillCastro和Lee提出了基于聚类的覆盖图方法，将属性相同的实体作为一个图层，对每一层的实体进行聚类分析，再对聚类产生的实体集间通过面积计算得到置信度和支持度从而进行关联规则挖掘。陈江平等提出了一种基于空间分析的空间关联规则挖掘方法，利用空间查询和拓扑计算等空间分析技术对空间谓词进行剪枝，构建拓扑关系概念层次树并进行关联规则挖掘。董林等提出利用叠置分析来进行关联规则挖掘的算法，通过计算多边形图层重叠面积比来得到支持度，该算法不依赖实物数据库，直接从矢量多边形图层中提取关联规则，可从多种类型空间数据中提取出多谓词关联规则，并给出了对应的可视化方法。

3.2时空关联规则挖掘现状

时空关联规则挖掘主要研究空间对象随时间发生变化的规律，即在空间关联分析的基础上增加时间约束，以发现时空数据中处于一定时间间隔和空间位置的关联规则。时空关联规则挖掘的研究主要集中在时空关联规则挖掘算法研究方面，目前时空关联规则挖掘方法主要有：

（1）基于时空事务的挖掘方法：

这类算法通常由时空数据事务化算法和事务表挖掘算法组合而成，前者的作用是根据挖掘目标构建一个时空事务表，后者的作用是对这个事务表进行挖掘，从中提取频繁项集和关联规则，如Mennis J等、沙宗尧、Shu H.等在对研究区域进行空间划分后，生成时空事务表，再进行关联规则挖掘。Calargun S.U.等、和Laube P.等研究了模糊空间事务表的挖掘算法。

（2）不依赖事务的挖掘方法：

Li D.等对时空关联规则挖掘中的插值问题进行了研究，认为地理学第一定律对于项的取值也成立，以此为依据提出一种基于空间统计的规则提取算法，利用已知点的关联规则对无样本站点的关联规则进行估计。Estivill-castro V.等提出一种不依赖于事务数据表的空间关联规则提取算法，依靠空间分析来实现支持度计算，对该算法进行拓展可以实现时空关联规则挖掘。

（3）结合领域知识的关联规则挖掘方法：

利用领域知识来指导关联规则挖掘有利于提高挖掘结果的质量。Fang G.等讨论了基于约束条件的拓扑关联规则挖掘方法。董林等[30]在进行空间关联规则挖掘时添加了基于背景知识的约束条件，减少了候选集的数量；郭文月等[31]改进了现有挖掘算法需要指定挖掘时间区间的问题，提出一种非指定时间约束的时空关联规则挖掘方法。

4.总结

关联规则挖掘的研究热点主要集中在算法改进、挖掘数据的组织上，在传统关联规则的基础上，对时空数据进行一定的处理，如时空数据离散化、构造带有时空知识标签数据等，进行关联规则挖掘，在这种处理过程中，目前采取的方法主要依靠人的先验知识，以人工处理为主，使得处理后的数据会丢失一些信息，从而在关联规则挖掘中失去一些有用的规则，如不同的空间方位划分、时间划分会导致挖掘的结果丢失一些重要的结果。若结合空间自相關分析等方法，对要挖掘的空间数据进行空间、时间上分布的检测，得到一定先验知识从而指导关联规则挖掘，可以减少人的先验知识带来的影响。

参考文献

[1]王家耀.深耕测绘一甲子：王家耀院士文集[M].科学出版社，2016.

[2]李德仁，王树良，李德毅，等.论空间数据挖掘和知识发现的理论与方法[J].武汉大学学报（信息科学版），2002（03）：221-233.

[3]李德仁，王树良，李德毅.空间数据挖掘理论与应用[M].北京：科学出版社，2006.