关联规则在空间数据挖掘中的研究
Research On Association Rules of Spatial Data Mining
曾玲　熊才权　胡恬
(湖北工业大学信息工程学院武汉430068)

摘　要
　　在智能化、集成化的空间数据应用领域中，空间数据挖掘是一门很重要的技术，而关联规则分析是空间数据挖掘的主要方法之一。文章基于数据挖掘中的关联规则分析方法，提出不同于一般数据挖掘的算法，设定兴趣度量，并通过将项的概念泛化为空间谓词，事务的概念泛化为邻域，关联规则的概念泛化为同位规则，发现多种形式的有效规则，并用逻辑语言或类SQL语言方式描述规则，以使空间数据挖掘趋于规范化和工程化。最后进行了实评。
　　关键词：关联规则　空间数据库　数据挖掘
　　中图分类号：TP3l1.13

1　引言
　　随着雷达、红外、光电、卫星、电视摄像、电子显微成像、CT成像等各种宏观与微观传感器的普遍使用，空间数据的数量、大小和复杂性都在飞快地增长，已经远远超出了人的解译能力。终端用户不可能详细地分析所有的这些数据，并提取感兴趣的空间知识，致使“空间数据爆炸但知识贫乏”。因此，利用空间数据挖掘和知识发现[1](SDMKD，Spatial Data Mining and knowledge discovery)从空间数据库中自动或半自动地挖掘事先未知却潜在有用的空间模式变得十分必要。
　　SDMKD所能发现的知识主要包括空间的关联、特征、分类和聚类等规则。一般表现为一组概念、规则、法则、规律、模式、方程和约束等形式的集合，是对数据库中数据属性、模式、频度和对象簇集等的描述。常用的空间数据挖掘技术包括：空间关联规则分析、分类分析、聚类分析、时间序列分析、粗集方法等。
　　由于空间关联规则分析可快速地、较好地发现隐含的空间地理位置的相关性，文章基于数据挖掘中的关联规则分析方法，提出算法，通过设定兴趣度量、将项的概念泛化为空间谓词、将事务的概念泛化为邻域、关联规则的概念泛化为同位规则，并以逻辑语言或类SQL语言方式描述规则，根据位置图寻找频繁的空间事件类型的同位子集，发现多种形式的有效规则。

2　空间数据挖掘及其特殊性
　　数据挖掘是发现新颖的、有效和完全的能够被人们理解的数据模式的一种方法。它结合统计和计算技术，从大量的数据集中获取有用的模式，进而产生指导性的规则集合，这些规则是对数据库中数据属性、对象集的有效描述，提供给决策支持系统。
　　空间数据库是在数据仓库的基础上，引入空间维数据，增加对空间数据的存贮、管理和分析能力，根据主题从不同的空间数据应用系统(如GIS)中截取从瞬态到区段直到全体地球系统的不同规模时空尺度上的信息，从而为当今的地学研究以及有关环境资源政策的制定提供最好的信息服务。空间数据库中的空间数据除了其显式信息外，还具有丰富的隐含信息，如数字高程模型[DEM或TIN]，除了载荷高程信息外，还隐含了地质岩性与构造方面的信息；植物的种类是显式信息，但其中还隐含了气候的水平地带性和垂直地带性的信息，等等。这些隐含的信息只有通过数据挖掘才能显示出来。
　　空间数据挖掘和知识发现(SDMKD)是计算机技术、数据库应用技术和管理决策支持技术等发展到一定阶段、多学科交叉的新兴边缘学科，汇集了来自机器学习、模式识别、数据挖掘与空间数据库技术、统计学、人工智能以及管理信息系统等各学科的成果[2]。
　　SDMKD与传统的地学数据分析方法的本质区别在于SDM 是在没有明确假设的前提下去挖掘信息、发现知识，挖掘出的知识应具有事先未知、有效和可实用三个特征。
　　SDMKD也不同于普通的数据挖掘和知识发现，它的对象主要是空间数据库或空间数据仓库，有别于常规的事务型数据库，空间数据库中不仅存储了空间事物或对象的几何数据、属性数据，而且存储了空间事物或对象之间的图形空间关系等，因此，SDM比一般数据挖掘的发现状态空间理论[3]增加了尺度维(scale)SDM的处理方法有别于一般的数据挖掘方法。
　　SDMKD具有广泛的应用前景和潜在的综合效益，随着空间数据量的增加及软硬件技术的发展，其应用正日益渗透到人们认识和改造空间世界的各个学科，如地理信息系统、信息融合、遥感、图像数据库、医疗图像处理、导航、机器人等使用空间数据的领域。SDMKD发现的知识将会促进这些学科的自动化和智能化。因此，SDMKD当前相当于数据库技术在70年代所处的地位，迫切需要类似于关系模式、DBMS系统和SQL查询语言等模型和工具，才能使SDMKD的应用得以普遍推广。

3　空间关联规则及算法描述
　　关联规则分析主要用于发现不同事件之间的关联性，即一事物发生时，另一事物也经常发生。关联规则分析的重点在于快速发现那些有实用价值的关联发生的事件。一个关联规则可以特征化为两个参数：支持度(support)和置信度(confidence)[4]。其主要依据是：事件发生的概率和条件概率应该符合一定的统计意义。
　　此外，由于SDM过程可能产生大量模式，通常，这些模式中只有一小部分是特定用户感兴趣的，为此，需要进一步限制挖掘过程产生的不感兴趣的模式数量。这可以通过设定兴趣度量来实现。兴趣度评估模式的简洁性、确定性和新颖性。
　　生成空间关联规则可采用两种方法：第一种方法的焦点是空间谓词而不是项，第二种方法将事务概念泛化以包括邻域，将关联规则的概念泛化为同位规则。从而发现多种形式的规则，并用逻辑语言或类SQL语言方式描述规则，使SDMKD趋于规范化和工程化。
　　3.1 空间关联规则
　　空间谓词的形式通常有：表示拓扑结构的谓词、表示空间方向的谓词和表示距离的谓词等，例如，距离信息(如Close_to(临近)、Far_away(远离))、拓扑关系(Intersect(交)、Overlap(重叠)、Disjoin(分离))和空间方位(如Right_of(右边)、West_of(西边))等[5]。各种各样的空间谓词可以构成空间关联规则。
　　一条空间关联规则可表示为X=>Y(C%，S%，I%)，其中，X和Y是空间或非空间谓词的集合，C%、S%和I%分别是规则的可信度、支持度和兴趣度。
　　例如，规则
　　is_a(x，largetown)∧close_to(x，highway)=>close_to(x，water)[S%，c%，I%]
　　(即靠近高速公路的大城镇通常与水相邻)是一个支持度为S、置信度为C和兴趣度为I的关联规则)
　　与传统的Apriori算法不同，空间关联规则分析的优化算法可描述如下：
　　(1) 根据查询要求查找相关的空间数据；
　　(2) 运用临近等原则描述空间属性和特定属性；
　　(3) 过滤重要的数据，剔除不满足最小支持度的空间谓词；
　　(4) 运用兴趣度量等其它手段对数据进一步提纯(如OVERLAY)；
　　(5) 生成空间关联规则。
　　表1-1给出一个根据给定的空间数据发现关联规则的例子。

　　　　　　表1　根据实际空间数据发现关联规则的例子
　　空间关联规则　　　　　　　　　　　　　　　　　　　　　　支持度　置信度
　　close_to(x, golf course)  ->  Is_a(x,park)　　　　　　　　　　0.05　　0.86
　　water_depth(x,shallow)&Far_away(x,water)
　　　　　　　　->  Stem_height(x,high)　　　　　　　　　　　 0.05    0.95
　　Far_away(x,edge)&Stem_heitght(x,high)
　　　　　　　　->  Vegetation_durability(x,close)　　　　　　　0.1     0.94

　　由于关联规则用于分类属性，因此对于数据集为数值型的应用来说就很受限制。这是因为从数值到分类数据的变换涉及到一个离散化过程，在大多实例中这会有某些随意性。
　　3.2 同位规则
　　同位规则试图将关联规则泛化为空间索引的点的集合数据集。在空间与非空间关联之间有几个关键区别，包括：
　　(1) 在空间数据的环境中，没有事务的概念，因为数据嵌入到连续空间中。把空间分区成事务会导致高估或低估所感兴趣的度量(如支持度或置信度)。
　　(2) 空间数据库中项集的规模比较小，即在空间情况下项集中的项数远小于非空间情况下的项数。例如，在零售业中，处理动辄有上万个项数的不同项的情况非常普遍，而对空间数据集来说，这种情况就很少出现，空间项一般不超过几十个。这意味着候选集生成的代价不再是Aprior算法的支配因素，而邻域的枚举(例如，频繁项集的实例)在整体的计算代价中占主导地位。
　　(3) 在多数情况下，空间项是连续变量的离散化版本。例如，可以把那些年龄不大于14岁的人称为未成年人。
　　在这种空间关联规则发现方法中，采用区别于一般的数据挖掘方法，事务的概念被邻域所取代，根据位置图寻找频繁的空间事件类型的同位子集，从而发现同位模式。例如，对动植物生活习性的分析可以得出捕猎肉食动物的物种、共生物种和具有燃烧源的火灾事件之间的同位性。

4 结束语
　　本文提出了空间数据挖掘中关联规则分析的基本思路和算法，通过设定兴趣度，将一般关联规则挖掘中项的概念泛化为空间谓词，事务的概念泛化为邻域，关联规则的概念泛化为同位规则，以发现隐含的地理位置同位性等多种形式的有效空间关联规则，并以逻辑语言或类SQL语言方式描述规则，从而使SDMKD趋于规范化和工程化。给出实验结果，验证了算法可行性。

参考文献
[1] 李德仁等. 论空间数据挖掘和知识发现[J]. 武汉大学学报·信息科学版. 2001.26(6):491~492
[2] 邬伦等. 地理信息系统一原理、方法和应用[M]. 科学出版社，2001
[3] Jia Wei Han，Micheline Kamber. 数据挖掘概念与技术[M]. 北京：机械工业出版社，2001,8
[4] 李德仁等. 论空间数据挖掘和知识发现的理论与方法[J]. 武汉大学学报·信息科学版，27(3)
[5] 邸凯昌. 空间数据挖掘和知识发现的理论与方法[D]. 武汉：武汉测绘科技大学，1999
[6] 王珊、罗立，从数据库到数据仓库. 计算机世界, 1996.28
[7] Shashi Shekhar, Sanjau Chawla. 空间数据库[M]. 北京：机械工业出版社. 2004,1
[8] 杨靖、朱扬勇. 1997，数据挖掘中的关联规则(Assoiation Rules)和序列模式，复旦大学计算机系博士学位论文