空间数据正/负co-location模式挖掘算法研究

发布时间：2021-08-03 01:35

　　随着空间数据和数据库的迅速发展和广泛应用,空间数据挖掘越来越重要。在地理空间中,经常位于一起的空间特征子集称为空间（正）co-location模式。虽然全连接、部分连接以及无连接算法的提出,解决了co-location模式的挖掘问题,但是这三种算法都存在算法消耗时间过多的问题。负co-location模式挖掘是找出拥有负相关关系的空间特征子集,关于这种模式的研究较少,目前提出的算法必须要在找出所有co-location模式的情况下才能进行负co-location模式挖掘,其挖掘过程复杂耗时。针对目前正、负co-location模式挖掘算法存在的问题,本文做了以下研究工作:（1）提出了极大实例算法。该算法引入了一种新的概念:极大实例,并提出了利用极大实例来生成co-location的所有行实例的方法,并证明这种生成行实例的方法的可行性及有效性。该算法生成行实例和co-location模式的过程都不需要连接操作,与全连接、部分连接和无连接算法相比可以节约大部分计算时间。（2）提出了改进的负co-location模式算法。通过分析正、负co-location模式之间的关系,提出了空间邻近关系... 

【文章来源】：桂林理工大学广西壮族自治区

【文章页数】：70 页

【学位级别】：硕士

【部分图文】：

空间数据集示例

桂林理工大学硕士学位论文10接操作。虽然全连接算法能够生成完整且正确的co-location模式，但是生成过程所需的连接操作会随着空间特征类型及其实例的增多而增多，所消耗的计算时间也会增加。图2.2实例连接过程(3)剪枝：候选co-location模式可以通过给定的兴趣度量阈值来进行剪枝。首先算法基于频繁度进行剪枝，即只有高于给定的兴趣度量阈值的候选co-location模式才是频繁的。所有候选co-location模式的参与度值计算出后，执行基于频繁度的剪枝，那些非频繁的候选co-location模式将被删除。而另一种剪枝策略是多分辨率剪枝。多分辨率剪枝是在使用不相交分区的粗略分辨率的空间数据数据上学习的。在全连接中主要以基于频繁度的剪枝为主，这个剪枝策略可以确保找出完整正确的频繁co-location模式。(4)生成频繁的co-location模式：通过剪枝筛选出满足频繁阈值大于用户设定值的co-location模式。关于全连接算法的具体描述如下：输入：a)={,,}表示空间特征的实例的集合；b)ET表示空间特征类型的集合；c)R表示空间邻近关系；d)θ表示最小频繁度阈值，α表示最小条件概率阈值；输出：频繁度和条件概率均大于用户设定的最小阈值的co-location规则集合。变量：k：co-location的阶；

12location模式的实例，因此这种方法为有效的co-location模式挖掘提供一个框架。只生成事务中未标识的团间表实例的实例连接操作的计算成本要比查找所有co-location模式表实例的实例连接操作的计算成本相对便宜。部分连接算法的基本步骤介绍如下：(1)事务化空间数据集：给定一个空间数据集，部分连接算法首先进行划分来生成事务集。文献[8]中介绍了一些生成事务集的划分方法，例如网格划分方法、最大团法、最小分割划分法等等。事务化空间数据集的理想情况是可以生成一组最大团，同时最大限度地减少由分区分割的边数。图2.3详细地描述了部分连接算法中事务化空间数据集的方法。其中虚线圈表示团，每个虚线圈的直径都是d（d为邻近关系的距离阈值），实线表示两实例满足邻近关系，虚线表示两实例间为分割邻近关系。例如A.1和C.2、A.5和B.2以及A.5和C.1之间都是分割邻近关系。Co-location模式{,,}的行实例为{.1,.2,.1}、{.4,.3,.4}和{.5,.2,.1}，其中，{.1,.2,.1}和{.4,.3,.4}是团内行实例，{.5,.2,.1}是团间行实例，因为{.5,.2,.1}中有两条分割邻近关系。图2.3事务化空间数据集(2)生成候选co-location模式：在部分连接算法中，这个步骤与全连接相同，也是利用Apriori思想，采用连接操作，从k阶频繁的co-location模式中生成k+1阶候选co-location模式。(3)扫描事务集收集团内行实例：在每个迭代过程中扫描事务集并列举出候选co-location模式的团内行实例。这个步骤类似于Apriori算法。需注意的是空间数据集的事务与市场购物篮数据的事务不同。传统的市场篮子数据交易只有布尔项目类型，即项目只能存在于或不存在于交易中。相反，邻域事务里的每一项都由一个空间特征类型及其实例组成。一个空间特征类型在事务中可以有多个实例。


本文编号：3318667