空间同位规则算法的改革论文

摘要：空间关联规则是空间数据挖掘所要发现的一种重要知识。一般的空间关联规则研究是基于传统的关联规则，然而这些方法在处理空间关系时是不适用的。同位规则问题的提出，很好的解决了挖掘正确有效的空间关联规则的需要。在介绍空间多维分类数据同位规则挖掘算法的基础上，对该算法进行了一点改进，使其能更好的针对不同的实际数据进行处理。

关键词：空间关联规则；空间同位规则；多维分类数据

1空间同位规则算法概述

参照特征中心模型（Referencefeaturecentricmodel）是基于参照空间特征的选择，是与应用领域特定的布尔型空间特征相关的。该模型的缺点有：1.1不能发现所有的关联规则：由于使用了参照特征，而无法发现包含参照特征与相关特征的关联模式；1.2因为它是用参考特征周围的邻居作为实例这些邻居在下一个参考特征的统计中可能被再次计数，于是产生重复计数的现象。

ad-hoc数据分割算法通过将空间数据集分割到互不相关的区域来定义传统关联规则挖掘中的事务。然而，这种强制分割忽略了边界之间的关系，会导致忽略或重复计算具有交叠边界的事务实例。此外，可能存在许多种数据分割的方法，每种方法都会产生不同的事务集，因此对于一个特定的空间关联模式会得到不同的支持度。

2多维分类数据的空间同位规则挖掘算法研究

2.1相关定义

定义1R-邻近关系

R-邻近关系是事件中心模型的重要概念。对于给定的实例集S，R-邻近关系定义为在邻域关系R下形成的区域内的实例集I，I!S。邻域关系R的定义是基于所应用的领域，由算法的输入给定。邻域关系R可以是空间关系（如连接的，邻近的），距离关系（如欧几里德距离）或以上二者的结合（如公路地图上的最短路径）。R-邻近关系不同于拓扑学中的邻近概念，因为R-邻近关系的超集不一定也是符合限定的R-邻近关系。

定义2行实例

假定存在同位模式c，如果一个R-邻近关系I包含了c的所有特征实例且不存在I的子集包含c的所有特征实例，则称这个R-邻近关系为行实例，用row_instance(c)表示。定义3参与概率

在长度为k的同位模式c={f1，⋯，fk}中，特征类型fi的参与概率pr（c，fi）表示发生空间特征fi的地点，发现空间特征c的可能性为pr（c，fi），其值用fi的实例在搜索到的行实例中出现的次数与fi的所有实例数之比表示。其中，!是用来剔除重复的实例的映射操作符。

定义4参与索引参与索引pi（c）是同位模式普遍性的度量值，它表示发现空间特征fi的地方，能够发现空间特征c的可能性至少为pi（c）。

2.2算法描述

同位规则挖掘算法是在给定即参与索引阀值min_prevalence的基础上，发现存在的所有同位规则。该掘算法也是采用自顶向下，逐层搜索的思想，过程中借鉴了Apriori算法的连接的步骤。以下是算法的具体流程。

算法1同位规则挖掘算法输入：

2.2.1K个布尔型空间特征类型以及它们的实例集：

2.2.2针对特定的应用制定的邻域关系R；

2.2.3全局参与索引阀值min_prevalence；步骤：

a.初始化长度为1的同位模式，此时所有的参与索引pi=1；

b.for长度do

c.用apriori_gen方法生成侯选同位模式；

d.搜索满足邻域关系的空间实例，生成表实例；

e.根据min_prevalence进行裁剪；f.生成同位规则；

g.end。

步骤b～g通过循环逐层搜索同位规则，当不存在同位规则时算法结束。参照3.2.1小节的范例，用apriori_gen方法生成侯选同位模式，实现上是采用表连接，具体做法是：为每一维的每个候选同位模式建立一个表，高一维的表由低一维的同位模式表进行表连接生成。然后是剪枝步骤，对生成的表进行裁剪。对所有属于候选同位模式集Ck的候选同位模式c，判断其k-1个元素的子集是否存在于同位模式集Lk-1，若不是，则将之删除。

步骤d是为每个表搜索空间中满足邻域关系的实例，生成表实例，计算该表中每个空间特征的参与概率，进而得到参与索引。步骤e则根据给定的参与索引阀值裁剪侯选同位模式，生成k-项同位模式Lk。

3算法的改进

我们发现，参与索引阀值的设定是根据实际情况和需要。对不同的空间数据集，人们无法预先知道数据的分布相关情况，参与索引阀值就难以确定。需要一种能够根据具体的应用而自动选择和调节参与索引阀值的方法。本文提出的做法是：从二维开始，计算该维所有候选同位模式的参与索引的均值，以均值作为该维的参与索引阀值。同时，设定一个全局参与索引阀值，当某个维度的参与索引均值小于全局参与索引阀值，则以全局参与索引阀值作为该维度的参与索引阀值。当某个维度下所有候选同位模式的参与索引均小于全局参与索引阀值，算法结束，不产生该维度及更高维度的同位模式。公务员之家

算法2改进的空间多维分类数据的同位规则挖掘算法输入：

3.1空间特征类型以及它们的实例集，即有m个属性，每个属性有n个值；

3.2针对特定的应用制定的邻域关系R；

3.3全局参与索引阀值min_prevalence；步骤：

a.初始化长度为1的同位模式，此时所有的参与索引pi=1；b.搜索空间邻域关系，建立长度为2的候选同位模式的属性表；

c.for长度do

d.根据改进1的方法，生成长度为l的侯选同位模式；

e.搜索满足邻域关系的空间实例，生成表实例；

f.计算参与索引均值average_prevalence；

g.if（average_prevalence>min_prevalence）根据average_prevalence进行裁剪；

h.else根据min_prevalence进行裁剪；

i.生成同位规则。

4小结

空间同位规则是有别于传统的空间关联规则方法的发现空间特征在分布上的联系性的新方法，目前国内外的相关研究较少。本文在多维分类数据的空间同位规则算法的基础上，提出多层参与索引阀值的思想，采用各层参与索引均值和全局参与索引阀值，由数据本身的特性决定同位模式的判定，能有效的防止生成参与索引太小、不具实际意义的同位规则。

参考文献

[1]王占全,王申康,华成.空间分类数据同位规则挖掘算法[J].计算机辅助设计与图形学学报，2005，10.

[2]黄添强,秦小麟,叶水生等.一种新的空间多维关联规则模型与算法[J].南京航空航天大学学报，2005，6.

[3]R.Agrawal,R.Srikant.FastAlgorithmsforMiningAssociationRules[C].InProceedingsof20thInternationalConferenceVeryLargeDataBases,MorganKaufmann1994:487-499.