万花镜
    首页社会国际娱乐科技时尚军事汽车探索美食旅游历史健康育儿
    相关:品牌购物世界服装男装
    位置:首页 > 科技

    面向地学数据的数据挖掘研究与实现

    2017年1月1日 来源: 晓风残月xj

    摘 要

    数据挖掘又称知识发现,是指从海量数据中发掘知识,有着广阔的应用前景。然而,当面对地学数据时,即使是现有的相对成熟的模型,也存在着性能与效果方面的缺陷。究其原因,主要是因为地学数据的固有特点:高维、非结构化、多关联性等,在数据模型、索引结构、存储方式、挖掘知识表达等方面,远比传统数据复杂。

    通常意义的地学数据有栅格、矢量等,本文注重处理栅格数据。Tobler地理学第一定理告诉我们:一切事物都与其他事物相关,但是距离近的比远的相关性更强。本文针对地学数据的空间相关性特点,通过R树建立空间索引,以空间同位模式挖掘算法为指导思想,通过栅格扫描方法物化空间对象间的空间邻近关系,产生事务的概念,从而将空间同位模式挖掘转化成传统的关联规则挖掘,然后利用常用关联规则处理某类地学数据,寻找感兴趣的关联规则。

    利用模拟程序生成的地学数据实验,在实验过程中,发现利用R树建立索引可以明显加快生成空间事务集的速度,同时,选用较为经典的Apriori算法和FP-growth算法对比性能,结果显示FP-growth算法比Apriori算法快很多,分析原因主要在Apriori算法需要产生大量的候选项集。着重考虑大数据量情景下的数据模型、索引结构和算法实现的性能。本文的主要工作如下:

    (1)为了加快邻域的寻找,选择建立R树空间索引,在此基础上总结了常用空间索引技术的适用场景和优缺点。

    (2)在分析传统关联规则挖掘算法与空间关联规则挖掘算法的基础上,对基于事件中心模型的空间同位模式挖掘算法进行描述,同时提出基于栅格扫描的同位规则挖掘算法,该算法通过扫描以某个栅格为中心的R-邻域栅格产生事务集,将地学数据挖掘转化成传统数据挖掘算法。

    (3)在空间索引R树的插入过程中,为了防止插入叶子节点后需要分裂,从而导致递归的向上一直分裂破坏单向遍历,提出在寻找插入位置的过程中如遇到满节点即记录数为M(M为每个节点最多插入记录数)的节点,就先进行分裂从而避免之后层层向上递归分裂,加快R树插入效率。

    (4)在预处理产生的空间事务集的基础上,实现Apriori算法和FP-growth算法两种经典的关联规则挖掘算法,对比分析性能。

    关键词:数据挖掘,空间索引,关联规则,同位模式

    The Research And Implementation Of Data Mining For Geological Data

    ABSTRACT

    Data mining and knowledge discovery, refers to discover knowledge from huge amounts of data, has a broad application prospect.When faced with geological data, however, even the relatively mature existing models, there are defects performance and effect.Investigate its reason, mainly because of the inherent characteristics of geological data, high dimension, unstructured, more relevance, etc., in the data model, indexing structure knowledge representation, storage, mining, etc., is far more complicated than the traditional data.

    The geological data of the usual have raster, vector and so on, this paper pays attention to raster data processing.Tobler theorem tells us: geography everything associated with other things, but closer than far stronger correlation.Spatial correlation characteristics of geological data, the author of this paper, by establishing a spatial index R tree with spatial pattern mining algorithms as the guiding ideology, through the raster scanning method materialized space object space between adjacent relationship, transaction concept, thus the space with a pattern mining into the traditional association rules mining, and then take advantage of commonly used association rules to deal with some kind of geological data, to find association rules of interest.

    Using the simulation program to generate the geological data of the experiment, in the process of experiment, found a way to use R tree indexing can significantly speed up the generating spatial transaction set, at the same time, choose the more classic Apriori algorithm and FP - growth algorithm contrast performance, results show that the FP - growth algorithm is much faster than the Apriori algorithm, analyses the main reasons why the Apriori algorithm to generate a large number of candidate itemsets.In this paper, the main work is as follows:

    (1) In order to speed up the neighborhood search, choose to establish R tree spatial index, on the basis of summarizing the common scenarios to apply spatial indexing technology and the advantages and disadvantages.

    (2) Based on the analysis of traditional association rule mining algorithm and spatial association rule mining algorithm on the basis of the model based on event center space with pattern mining algorithm was described, and puts forward with a rule mining algorithm based on raster scanning, the algorithm by scanning for the center with a grid of R - neighborhood affairs set grid, will study data mining into the traditional data mining algorithm.

    (3) In the process of spatial index R tree insert, in order to prevent insertion to split after the leaf node, leading to a recursive has been split up destroy the one-way traverse, is put forward in the process of looking for insert position that records if full node number is M (M number) for each node up to insert nodes, first to divide to avoid after layers of recursive splitting up, speed up the R tree insertion efficiency.

    (4) On the basis of spatial transaction set preprocessing, realize the Apriori algorithm and FP-growth algorithm two kinds of classic association rule mining algorithm, performance contrast analysis.

    Key Words: Data Mining, Spatial Index, Association Rule, Co-location Rule

    目 录

    第一章 绪论 1

    §1.1研究背景 1

    §1.2选题意义 1

    §1.3研究现状 2

    1.3.1空间索引技术的研究现状 2

    1.3.2关联规则技术的研究现状 3

    1.3.3关联规则在地学数据处理的研究现状 4

    §1.4本文工作 5

    §1.5全文结构 5

    第二章 同位模式基本理论 7

    §2.1概述 7

    §2.2 R树索引的基本理论 7

    2.2.1索引基本原理 7

    2.2.2空间索引方法 8

    2.2.3 R树介绍 9

    §2.3关联规则的理论介绍 11

    2.3.1关联规则基本理论 11

    2.3.2关联规则常用方法 12

    §2.4本章小结 14

    第三章 基于栅格扫描的同位模式 15

    §3.1概述 15

    §3.2传统关联规则的不足 15

    §3.3同位模式原理提出 16

    §3.4基于栅格扫描的同位模式 17

    §3.5本章小结 18

    第四章 算法实现与实验分析 19

    §4.1概述 19

    §4.2代码实现 19

    4.2.1 R树索引实现 19

    4.2.2基于栅格扫描的同位规则实现 22

    §4.3实验结果分析 23

    4.3.1平台与数据 23

    4.3.2结果分析 24

    §4.4本章小结 42

    第五章 总结与展望 43

    §5.1总结 43

    §5.2展望 43

    致 谢 45

    参考文献 46

    第一章 绪论

    本章首先介绍论文相关的研究背景以及选题意义,面向地学数据的数据挖掘技术的发展现状与存在问题,然后介绍了本篇论文的主要研究工作,最后简要概括了全文组织结构。

    §1.1研究背景

    上世纪末期,我国著名科技人李德仁院士第一次提出从GIS中发掘知识的理念,并且初步论证了空间数据挖掘的特点和方法。地学数据是空间数据的一个重要组成部分,有着极其广泛的研究意义。数据收集技术等在GIS、遥感、交通运输、环境、生态、天文等领域的广泛应用导致空间数据逐年大批量增加,目前,遥感、测绘、地探等多种应用产生了大量的地学数据。这些数据包含空间对象本身的特征和空间对象之间的距离关系、坐标关系等,仅靠传统的数据分析手段很难从中获取真正有价值的信息;为了能够有效准确地发现隐藏在海量地学数据背后的具有决策价值的知识,地学数据挖掘技术产生了。

    地理空间数据挖掘是GIS技术的崭新领域,有着被认可的应用场景。但由于空间数据的数据量大、数据类型复杂等,导致空间数据挖掘在各方面仍有很多问题,等待着较深一步的研究和实践。数据挖掘又称知识发现,一般指从海量数据中发掘知识,有着广阔的应用前景,是近些年人工智能和大数据领域的研究热点。在一大批学者地努力工作下,数据挖掘技术取得了长足的发展。目前常用的数据挖掘方法主要有关联规则、分类和预测、聚类分析、离群点检测和分析等,它们从不同的切面对数据进行挖掘,提取知识。然而,当面对地学数据时,即使是现有的相对成熟的模型,也存在着在性能与效果方面的问题。究其原因,主要是因为地学数据的固有特点:高维、非结构化、多关联性等,在数据模型、索引结构、存储方式、挖掘知识表达等方面,远比传统数据复杂。所谓地学数据挖掘,是指从地学数据中发现用户感兴趣的知识表达形式。地学数据挖掘就是指从地学数据中发掘知识,从而造福全人类。

    §1.2选题意义

    宏观上,遥感、物探、卫星采集了海量的地学数据;微观上,电子显微镜又为我们呈现了一个放大的微观世界。这些数据中蕴藏着大自然的规律,是一座正待被开采的宝藏。数据挖掘技术从海量数据中发掘知识,在很多领域已经有很好的应用,然而,当它面对地学数据时,即使是成熟的数据挖掘算法,亦面临众多挑战。主要原因在于地学数据的高维、非结构化、多关联性等特点,在数据模型、索引结构、存储方式、挖掘知识表达等方面,远比传统数据复杂。

    本题目尝试面向一类地学数据(比如基础地理数据、生态环境数据、资源环境监测数据),实现一类数据挖掘算法(比如关联规则、聚类等)。着重考虑大数据量情景下的数据模型(栅格或矢量)、索引结构和算法实现的性能。通常意义的地学数据有栅格、矢量等,本文注重处理栅格数据。根据Tobler地理学第一定理:空间内一切事物都与其他事物相关,但距离近的比远的相关性更强。本文针对地学数据的空间相关性特点,通过R树建立空间索引,以空间同位模式挖掘算法的思想为基础,通过平面扫描方法物化空间对象间的空间邻近关系,产生事务的概念,从而将空间同位模式挖掘转化成传统的关联规则挖掘,然后利用常用关联规则的Apriori算法、FP-growth算法处理某类地学数据。

    §1.3研究现状

    本节从空间索引技术、关联规则技术、关联规则在地学数据处理等的研究现状三个方面说明了作者的一些认识与想法。

    1.3.1空间索引技术的研究现状

    索引,由日本引入的外来语,在英语中索引是index。我国的智者在很早就有着索引的思想,那时称为“检目”、“通检”、“韵编”等。公元1642年明代的《两汉书姓名韵》是我国有史料记载的最早的一部索引专著。在计算机时代尤其是人们逐步进入大数据时代的今天,索引技术依然换发生机与活力。索引可以加快检索速度,放弃盲目暴力的枚举遍历,改为有针对性的对数据进行筛选检索,这是一个质的提高。处理地学数据面临的一个严峻问题就是如何有效地检索空间数据。

    由于空间数据客观存在的特点,在实际选择建立索引的过程当中,二叉树、B树、B+树还有ISAM索引、哈希索引等往往不能够保留空间对象基于坐标位置的关系。目前较为常用的空间索引技术有:网格索引、四叉树索引和R树相关索引。最早研究空间索引可追溯到1974年提出了四叉树,主要存储空点多维点;1975年提出了K—D树,对于精确的点匹配查找;80年代学者将KD树与B树结合,提出K—D—B树;之后又提出了MKD树、SKD树,这些都是KD树的变种。R树是1984年提出的,R树是B树在空间数据维度上的扩展,是基于MBR(最小矩形覆盖)的高度平衡的。R树的主要问题是非叶子节点MBR的大量重叠会导致查找路径的不唯一,从而严重影响其性能。R*树对R树的分裂规则进行了一些改进,主要体现在以下两点:第一,提出了重新插入的思想;第二,当节点需要分裂操作时,分裂策略不仅要考虑分裂后两个新节点的面积,还要考虑分裂后节点周长、重叠面积等要素。R+树解决了R树中节点空间之间互相重叠的问题,从而保证查询时沿着一条路径搜索。这些R树的变种虽有效的改进了R树在某些方面的不足,但增加了算法的复杂度。

    图1.1 空间索引发展过程

    1.3.2关联规则技术的研究现状

    关联规则旨在发现一个数据集中项与项之间的依赖关系,也称之为购物蓝分析。关于关联规则最著名的就是"尿布和啤酒"的故事。美国沃尔玛连锁超市发现一个特别有趣的现象:尿布与啤酒这两种摆在一起,二者稍量大幅增加。这是一直被商家所津津乐道的发生在的真实案例。原来,美国的妇女通常在家照顾孩子,所以她们会嘱咐丈夫在下班回家的路上为孩子买尿布,而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。

    1993年Agrawal等提出了挖掘顾客交易数据库中项集间的关联规则问题(1),在此研究之上1994年又提出了经典的Apriori算法,标志着关联规则作为数据挖掘技术的一部分渐渐被学者所注意。

    关联规则挖掘过程主要包含两个阶段:

    (1)根据给定的最小项集支持度,从数据集中找出全部的频繁项集;

    (2)根据最小置信度,由已知频繁项集产生感兴趣的关联规则。

    学者在关联规则领域做了大量有效的研究工作,目前主要的方向有:分布并行式挖掘算法、增量式挖掘算法、多循环方式挖掘算法、多值关联规则的挖掘算法、多层关联规则的挖掘算法、基于概念格的关联规则挖掘算法(2);同时,关联规则的规则完备性,兴趣度及其度量尺度,知识表达等也得到了深入研究;在处理不同类型的数据时关联规则出现很多新的扩展:如子结构挖掘、序列模式挖掘,时序模式挖掘等。

    图1.2 关联规则研究现状

    1.3.3关联规则在地学数据处理的研究现状

    在近二十年来,用来处理地学数据的GIS技术得到了广泛应用,地学数据的存储、检索、管理、查询、显示,特别是空间分析功能得到了飞速发展。然而这些一般都以可视化操作为主要手段,比如缓存处理、几何处理、统计学处理等,而对隐含在空间数据中的知识即地学数据挖掘等方面仍然比较薄弱,如多个空间对象的伴生与共存问题等。由于空间数据较之传统领域的数据较为复杂,地学数据挖掘需要地探技术、计算几何以及数据挖掘等多种技术的支持,这要求研究人员采用新的理论方法和技术手段来处理空间数据。

    地学关联规则是将一个或多个地学对象与其它地学对象相关联。目前这方面的研究主要包括两类:一类是没有整体考虑空间分布关系的关联规则的挖掘研究;另一类是考虑空间关系的空间关联规则挖掘研究,目前这类研究尚处在初期,在空间关系和非空间关系的结合上还有很多问题需要进一步的探索。对于空间数据集,事务可以简单理解为是一组空间谓词和非空间谓词的集合,空间关联规则旨在描述在一个事务中谓词之间同时存在的知识模式(3)。

    Tobler的地理学第一定理揭示了这样一种客观存在的空间关系:空间内所有的事物都是有联系的,每个地方发生的事件总是与它附近发生的事件存在某些关联,并且相距近的事物之间的联系一般比相距远的要密切(4)。传统领域关联规则频繁项集的搜索域在整个事务库,而地学数据可以依据Tobler的地理学第一定理来缩小搜索域,一方面可以加快频繁项集的寻找速度,另一方面也可以提高频繁项集的质量。面向地学数据的关联规则的主要步骤如下:

    (1)根据查询要求查找相关的空间数据;

    (2)利用邻域原则描述空间数据属性;

    (3)根据最小支持度阈值过滤不频繁的项集;

    (4)运用相关技术对数据进一步处理;

    (5)生成满足条件的关联规则。

    随着地学数据挖掘理论的不断发展,地学数据挖掘技术在应用中取得了令人瞩目的成绩,但在研究和应用方面依然存在一些问题。当前面临的主要挑战是:地学数据的海量规模、地学数据的多维性、地学数据的空间关联性等,当传统关联规则算法处理地学数据时在性能上存在很大不足(5)。

    §1.4本文工作

    本文主要对面向地学数据的关联规则技术进行了梳理。

    首先简要概括了面向地学数据的数据挖掘的研究背景,接着对空间索引技术、传统领域关联规则技术的研究现状以及发展进行了介绍,接着分析了地学数据与传统领域数据关联规则挖掘的不同之处:地学数据的特点:高维、非结构化、多关联性等。然后总结基于栅格扫描的同位模式挖掘的相关技术,如空间索引结构-R树的基本原理,关联规则的理论基础等,通过预处理在空间数据集上产生事务的概念,就可以将通常意义上的关联规则技术应用与处理地学数据,最后重点讨论了Apriori算法、FP-growth算法的性能。

    然后指出了传统关联规则挖掘算法在处理空间数据时的不足:一个主要差异表现在空间数据集没有事务的概念;为了解决此问题,依据Tobler地理学第一定理,引入同位模式原理。针对目前同位模式算法较为复杂且大量重复搜索领域,提出基于栅格扫描的同位模式挖掘算法,通过预处理产生事务的概念,从而转化成传统关联规则挖掘问题。

    最后,由于本次选题是应用方向,所以重点介绍了一些技术实现以及相关优化细节。为了提高预处理性能,建立了空间索引R树这一数据结构;为了避免插入记录时双向遍历,借鉴B树的处理思想,在单向寻找插入位置时就分裂已经为满的节点。此外,在编程语言上选择C++,因为C++是面向对象的,同时C++的效率比其他OO语言要高很多,整个工程除去注释自写代码2500+行。

    §1.5全文结构

    本论文的结构安排如下:

    第一章 绪论:简要概括了面向地学数据的数据挖掘的研究背景,接着对空间索引技术、传统领域关联规则技术的研究现状以及发展进行了介绍。

    第二章 同位模式基本理论:介绍了本文基于栅格扫描的同位模式实现的相关理论基础。

    第三章 基于栅格扫描的同位模式:通过分析面向地学的关联规则与传统领域关联规则的不同,阐述了处理地学数据类型时传统关联规则面临的挑战,进而引出本文主要讨论的空间同位模式算法,作为空间同位模式的一种,实验选用的是基于栅格扫描的同位模式挖掘算法。

    第四章 算法实现与实验分析:具体介绍了基于栅格扫描的同位模式挖掘算法实现时用到的一些主要技术关键点和优化细节,然后简要的对实验结果进行了分析,论证了算法的可行性。

    第五章 总结与展望:指出了本文的主要工作以及存在的不足之处。

    第二章 同位模式基本理论

    §2.1概述

    随着地学数据采集技术的成熟,通常GIS系统储存和处理着海量数据,传统的索引机制不能直接移植去处理地学数据中的空间对象的查询,而是需要使用高效的可以使用在多维空间数据的空间索引技术。依据R树建立索引,遵循空间的相关性原理,基于栅格扫描的空间同位模式预处理地学数据,然后利用传统关联规则中经典的Apriori算法、FP-growth算法处理地学数据,对比性能。

    §2.2 R树索引的基本理论

    2.2.1索引基本原理

    在进行数据查找时,我们都希望在保证结果集不受影响的情况下尽可能提高速度。最基本的查找规则是顺序查找逐个遍历,此过程时间复杂度为O(n);在数据量很大时就会变得很慢,为了避免逐个枚举,下面两种算法思想被引入:

    (1)基于排序的算法

    折半查找、二叉树查找、B树系列等算法,这些要求数据本身是有序的。 在有序的基本条件下,有目标的查找,即先以有序集合中的某个中间节点元素T为比较对象:如果待查找的元素小于该元素T,则将集合缩小为左半部分;否则为右半部分。每次查找都能将区间近似缩小为原集合的一半,伪码如下:

    binarySearch(data,array,left,right)

    {

    if left>right

    没有找到;

    mid=(left+right)>>1;

    if array[mid]==data

    找到data在array的位置;

    elseif data

    在左半部分递归查找,binarySearch(data,array,left,mid-1);

    else

    在右半部分递归查找,binarySearch(data,array,mid+1,right);

    }

    可以显著减少查找次数,进而大幅提高效率;但是先决条件是集合中数据元素必须是实现排序的。(2)基于哈希的算法

    哈希查找的基本思想是变按内容查找为按地址查找。一般情况下需要构造哈希表,然后在哈希表上根据特定内容和地址的映射规则定位。核心思想为:给定待查找关键字,利用哈希函数和哈希冲突函数计算哈希地址,定位到待查找元素。下面是算法步骤:

    (1)哈希函数和哈希冲突函数构造哈希表;

    (3)利用哈希函数和哈希冲突函数按地址查找。

    2.2.2空间索引方法

    空间索引是对存储在内存或磁盘上的空间数据位置给予的描述信息,用来快速的存取空间数据。空间索引的基本思想就是将全局空间通过一定原则划分成不同的子区域,然后以一定优先级在这些局部区域中查找空间对象(6)。传统的如B +树索引,是一维索引,不能用于二维和多维空间数据中处理的空间数据,必须发展用于空间数据的索引技术。迄今为止人们提出了四叉树、网格、KD树和KDB树、BSP树、R树等空间索引,其中主要常用的空间索引技术是R树系列(7)。

    这些索引在应用中一方面体现出各自的优点,另一方面又暴露出各自的不足之处,后来很多人在其基础上进行了一些改进,R树的改进有R+树、R*树等,网格索引的改进有固定网格索引、层次网格索引、自适应网格索引等,也有将多种索引结合在一起形成的集多种索引技术性能优势于一体的混合索引,如空间网格与R树类结合的混合索引机制。基于对空间索引技术的了解,引用下表加以概括。

    表2.1 空间索引技术汇总(8)

    由此可知,各类索引技术虽然在处理某种类型的数据方面有其优点,但对于其他数据也表现出自身的缺点;目前,在不同的应用领域面对不同的数据,还不存在一种通用的空间索引技术。

    2.2.3 R树介绍

    R树是常用索引数据结构B树的在高维上的变种,主要是为解决多维数据查询。R树是高度平衡的树状数据结构,能保证根节点到所有记录所在的叶节点的深度相同。R树是基于MBR(Minimal Bounding Rectangle)的,MBR翻译为中文为最小边界矩形:即包围某一区域内所有空间元素(点、线、面等)的最小矩形,边界可以重复。这里的MBR主要解决二维空间的,如果是超过二维的k维空间,则这里的MBR不是最小边界矩形,而是最小边界k维体。

    (1)除非是非根节点,否则叶子节点拥有m至M个记录;如果根节点恰好是叶子节点,那么记录个数可以少于m;

    (2)对于在叶子节点中的记录,I是可以在空间中完全覆盖它们的最小矩形;

    (3)除非是根节点,否则非叶子节点拥有m至M个孩子节点;

    (4)对于在非叶子节点上的记录,I是可以在空间中完全覆盖它们的最小矩形;

    (5)所有叶子节点都位于同一深度。

    上述m和M的值可以视情况而定,一般设为M=m*2。

    下面给予R树的一个实例图:

    图2.1 R树MBR图

    建立R树的树状结构如下:

    图2.2 R树结构展示

    §2.3关联规则的理论介绍

    2.3.1关联规则基本理论

    不同的应用场景对不同数据类型的知识敏感,所以数据挖掘包含很多内容,常见的有:关联规则、分类和预测、聚类、神经网络、离群点检测和分析等。可见,关联规则属于数据挖掘的主要范畴之一,是从海量数据中找到自己感兴趣的依赖关系。关联规则是从海量数据中提取规律、发现知识。关联规则主要考虑的不是数据自身的属性,而是事务集中某种组合项集同时出现的特性。在这个IT到DT的转型时期,由于Web应用的高速发展,Web用户产生的数据被不断保存、传感器也在不断收集数据,以及移动互联网大潮的到来,数据收集、存储的容量在不断增加,全世界的数据在不断膨胀,以至于海量一词诞生。挖掘数据的前提是有数据,有数据还要有技术,这样数据就成了宝贵的矿藏,有着很强的挖掘价值。关联规则挖掘就是寻找海量数据中某类用户感兴趣的频繁项集。

    下面是关联规则的一些基本概念:

    (1)事务库(transaction database):存储所有的记录集,定义为T;

    (2)项目(item):事务集中的记录,定义为i;

    (3)项集(item set):项目的集合,如{i1,i2}、{i1,i2,i4}等。通常规定item set中item的个数成为item set的长度,如含有k个item的item set成为K-item set,即K项集,定义为I;

    (4)事务(transaction):某类项目的集合,如{i1,i2,i3},定义为t;

    (5)支持度(support):项集I在事务集T中出现的次数事务总次数的比例,项集支持度即项集出现的频率;

    (6)频繁项集(frequent item set):如果某个项集的支持度满足某个预先设定的阈值,就称为频繁项集。这个预先规定的阈值被叫做项集最小支持度,记为supmin;

    (7)置信度:指既包含了X又包含了Y的事务出现的次数占包含了X的事务的比例(9)。

    由式,我们有

    同时满足最小支持度和最小置信度的规则,称之为强规则。关联规则就是在给定的事务集中寻找支持度和可信度都大于事先设定阈值的规则,本质就是寻找强规则。

    2.3.2关联规则常用方法

    关联规则的本质就是挖掘强规则,在这个挖掘强规则的过程中,最小支持度、最小置信度是重要的筛选因子。下面是关联规则挖掘的两个主要阶段:

    (1)根据给定的最小支持度supmin,从事务集中找出全部的频繁项集;

    (2)根据最小可信度supcon,由已知频繁项集中生成感兴趣的关联规则。

    不同类型的数据集可以发现不同类型的关联规则。若将关联规则根据所挖掘的模式类型分类,一般可以是频繁项集挖掘、序列模式挖掘、结构模式挖掘。频繁项集挖掘是从事务集中挖掘不分次序的频繁项集;序列模式挖掘是从数据集中搜索有序频繁子序列;结构模式挖掘则是在结构化数据中搜索频繁子结构,这类挖掘的一个典型应用就是地学数据挖掘,地学数据常用的结构化数据是点、矢量、栅格等(10)。本文讨论的重点就是通过空间索引R树将结构模式挖掘转化成一般的频繁项集挖掘。对比关联规则挖掘的两个主要阶段,可以发现主要的挑战在第一阶段,即根据给定的最小项集支持度,从数据集中找出所有的频繁项集。

    下面谈谈本次试验选取的两种关联规则技术:Apriori算法和FP-growth算法。

    2.3.2.1 Apriori算法

    在1994年Agrawal提出的Apriori算法,是关联规则系列算法中的最简单经典的算法,主要适用于单层布尔型的频繁模式挖掘关联规则(11)。层次算法的思想就是该算法的闪光之处,这是典型的迭代算法,针对不同的数据类型学者在此基础上又提出了许多改进算法。

    (1)扫描事务集T求出每个1项集的支持度,即得到频繁1项集的集合;

    (2)循环计算频繁k项集。

    (2.1)连接:由两个有且只有一个项不同的k-1频繁项集连接得出k频繁项集的候选集;

    (2.2)剪枝:上述得出的是k频繁项集的候选集,需要对候选集k中的k-1项子集进行判断。若k-1子集不是频繁项集,则直接剔除掉;

    (3)扫描计算所得的频繁项集,依据给出的置信度等筛选条件确定感兴趣的关联规则。

    上述步骤中的连接和剪枝称为Apriori-gen,在连接过程中,把两个频繁k-2连接生成候选项集,减少了计算量;在剪枝过程中,若候选k项集中某个k-1项集为不是频繁k-1项集,则直接剔除掉,也提高了算法的效率。但是,Apriori算法要迭代任意长度,即每一个长度都生成候选项集。Apriori算法有一个致命缺陷:大量的候选项集的产生,可能造成组合爆炸现象。

    2.3.2.2 FP-growth算法

    为了回避计算候选集产生的组合爆炸问题,J.Han等提出一种无需产生候选频繁项集的算法:频繁模式增长算法,即FP-growth算法。FP-growth算法的核心思想是分治,在经过第一次遍历处理后,用数据中的项集生成一棵频繁模式树(FP-tree),同时保留蕴含的关联信息,接着将FP-tree抽象条件集,每个条件和一个长度为l的频集相关,然后对这个条件集进一步进行挖掘,当数据量很大的时,可以利用划分技术,保证内存可以装得下FP-tree。实验结果显示,FP-growth具有较为不错的伸缩性,即对各种长度事务集上的关联规则都有很好的自适应能力,同时在性能上较之Apiori算法有显著提升。

    FP-growth算法是不生成候选集的方法,主要基于这样的数据结构:一棵FP-tree和一个项头表,每个项通过一个节点链指向它在树中出现的位置,项头表需要按照支持度递减排序。

    FP-growth (FP-tree, α)

    {

    if FP-tree 只含单个路径P Then{ (1)

    for 路径P中结点的每个组合(记作β) (2)

    产生模式βUα,其支持度MinSupport =β 中结点的最小支持度;

    }

    else{

    for eachαi 在FP-tree的项头表(按照支持度由低到高顺序进行扫描){ (3)

    产生模式β= αiUβ,对应支持度MinSupport=αi.MinSupport;

    构造β的条件模式基,在此基础上构造β的条件FP_Treeβ; (4)

    If FP-tree不为空 then

    调用FP-growth (FP-treeβ, β);

    }

    }

    (1) FP-tree只含单个路径P,即只有一条分支且分支不能中间分叉,如果分叉可能隐含了分支合并问题,导致合并之前误删不满足最小支持度的;

    (2)若分支上有项集n个项,则总共有2^n组合,可以每个项取或不取两种情况递归下去;

    (3)当前条件FP-tree的的项头表,用尾插法建立单链表;

    (4)从当前项头表的αi沿着条件FP_Tree的每条分支向上找出条件模式,然后建立后缀模式β的条件FP-treeβ。

    下面是一个FP-tree简述过程图解:

    图2.3 FP-tree示意图

    §2.4本章小结

    本章节首先从索引概念和R树原理开始,论述空间索引的基本理论和方法,然后阐述关联规则的理论基础和Apriori算法、FP-Growth算法原理,最后根据Tobler的地理学第一定理来阐释利用R树索引来实现关联规则的可行性,为下一章基于栅格扫描的同位模式挖掘算法提供理论依据。

    第三章 基于栅格扫描的同位模式

    §3.1概述

    地学数据有着固有特点:高维、非结构化、多关联性等,这给传统关联规则在地学领域的应用带来很大的挑战;但是地学数据也有着客观存在的空间相关性,这又为地学数据挖掘提供了一定的思想源泉。可以根据Tobler的地理学第一定理解释的空间相关性,通过一定的预处理技术将地学数据关联规则挖掘转化成传统领域关联规则挖掘,而这种预处理技术就是本章讨论的基于栅格扫描的空间同位规则挖掘。

    §3.2传统关联规则的不足

    传统关联规则处理的是非空间数据,而地学数据属于空间数据的一种,故直接照搬传统关联规则很难适用于地学数据的挖掘,二者的关键区别在于以下3点:

    (1)通常地学数据类型没有传统意义上事务的概念,因为数据存在于联系的地理空间,盲目的划分成传统意义上的事务可能导致过高估计或过低估计置信度(12);

    (2)地学数据的项集较少,这使得类Apriori算法处理时主要的消耗不在于候选项集的枚举,而在于邻域的枚举;

    (3)在很多情况下,采集到的地学数据是连续数据的离散化样本,即不可能在很小的粒度上采集数据。

    基于上面3点不同,传统关联规则算法很难直接应用在地学数据上。Apriori算法和FP-growth算法是基于事务的,在传统意义上的关联规则中,如购物担数据分析,事务是顾客选择商品的集合,这是频繁项集的载体;而在地学数据领域关联规则下,甚至没有通常意义上的事务概念,各种地学实体对象直接分布在空间中(13)。

    §3.3同位模式原理提出

    生成空间关联规则有两种比较通用的思想:第一种的重点是空间谓词而不是项;第二种是空间同位规则。Tobler地理学第一定理揭示了这样的空间关系:空间内所有的事物都是有联系的,每个地方发生的事件总是与它附近发生的事件有关联,并且相距近的事物之间的联系一般比相距远的要密切(14)。Tobler定理为根据邻域关系来寻找地学数据存在的关联规则提供了坚实有力的理论基础。而邻域关系的处理使同位模式有了施展空间。空间同位规则算法:将事务概念转化成以某点为中心的R-邻域,从而将关联规则的思想转化成空间同位规则的思想(15)。

    目前同位模式挖掘大致分为两派:第一种是运用新理论进行同位规则挖掘的算法,典型的有各种“类Apriori”算法;第二种是采用处理手段对地学数据进行事务化,再使用传统关联规则进行同位规则挖掘的算法(16)。本文主要研究的是第二种,重点是通过预处理手段将地学数据进行事务化。

    目前较为常用的同位模式挖掘算法流程如下:

    输入:

    (1)N个布尔型空间数据类型特征和它们对应的数据集;

    (2)根据空间数据类型选择合适的邻域关系;

    (3)全局参与索引阀值min-prevalence;

    步骤:

    (1)处理长度为1的同位模式,设定参与索引1;

    (2)for长度L属于{2,3,……,N},重复步骤(3)到(6)

    (3)用Apriori-gen操作产生侯选同位模式;

    (4)在数据集中搜索符合某种邻域关系的空间对象,产生同位模式筛选表;

    (5)根据min-prevalence进行剪枝;

    (6)生成同位规则。

    地学数据的同位规则挖掘在寻找满足条件的频繁项集的过程中,往往需要进行空间数据的几何关系计算,性能消耗非常大。如上面介绍的同位模式算法,就需要在每次循环中都进行步骤(4)搜索满足邻域关系的空间对象生成同位模式筛选表和步骤(5)根据min-prevalence进行剪枝,消耗较大。基于栅格扫描的空间同位规则的核心在于对数据的预处理:即通过将小栅格合并成更大地理空间的栅格(这里所说的栅格用矢量可能从结构上更合适一点,但是矢量不能准确的表达空间整体扫描的思想),产生去重后的项集,然后每个大空间栅格可以看做是泛化的事务。

    传统关联规则形式如下:

    空间同位模式形式如下:

    图3.1 某城市地标分布图

    §3.4基于栅格扫描的同位模式

    首先对地学数据的特征进行合理划和空间连续分布的离散化处理,即将一定邻域内的栅格合并成一个大的栅格,提取互异数据特征,消除冗余数据特征。这样可以将以一个栅格作为中心的R-邻域内的互异特征构成的项集当做事务,这样就让地学数据产生了事务的概念。为了加快事务集的生成,建立空间索引R树,相关原理在第二章同位模式基本理论中有详细介绍。

    然后在预处理产生的事务集的基础上使用传统的关联规则算法开始挖掘知识,由于地学数据每个项集本身并没有包含很多的项,候选项集的产生并不会是整个系统的主要制约因素,所以Apriori算法可以应用在本算法中;同时,考虑到有些数据经过上面的栅格扫描单个事务的项集包含的项并不是很少,为了对比性能,实现了FP-growth算法,这种算法回避了Apriori算法中候选项集的产生。

    图3.2 9-邻域栅格扫描

    在上面的4*4栅格中,9-邻域扫描后产生的事务集包含4个完整事务,分别是

    (I1,I2,I3,I4,I5,I7,I8);

    (I2,I3,I4,I5,I7,I8,I9,I10);

    (I1,I2,I3,I4,I5,I6,I7,I8);

    (I4,I5,I6,I7,I8,I9,I10,I11);

    等等;

    实验结果表明,该模型算法处理某类地学数据是有效的,Tobler地理学第一定理揭示的地学数据特征间的相关性,连续空间分布的离散化处理和邻域互异特征提取产生了以某个点为中心的R-邻特征项集,地学数据的事务概念得以产生,然后选择传统领域经典的关联规则算法挖掘感兴趣的频繁项集。

    §3.5本章小结

    本章节首先分析了地学数据类型与传统领域数据类型的不同,进而指出传统的关联规则算法并不能直接使用在地学空间数据的关联规则挖掘上,引入空间同位规则这一挖掘地学数据存在的关联思想,然后介绍了经典的同位模式算法,最后提出了将地学数据基于邻域关系进行事务化的从而转化成传统领域数据的栅格扫描技术,这也是本文重点研究的基于栅格扫描的同位规则挖掘技术。

    第四章 算法实现与实验分析

    §4.1概述

    地学数据的固有特点使得传统关联规则挖掘很难直接试用,本文提出的基于栅格扫描的同位模式挖掘算法就有了应用价值。在该算法执行中,很重要的工作就是查询以某个点为中心的R-邻域:给出坐标范围,找到该范围内的所有栅格(对应本次试验的矩形空间数据块)。本文对R树有一个改进之处:在空间索引R树的插入过程中,为了防止插入叶子节点后需要分裂,从而导致递归的向上一直分裂破坏单向遍历,提出在寻找插入位置的过程中如遇到满节点即记录数为M(M为每个节点最多插入记录数)的节点,就先进行分裂从而避免之后层层向上递归分裂,加快R树插入效率。R树基于MBR的思想,可以加快查找给定范围内的空间数据集。在扫描栅格的基础上产生了事务的概念,于是可以用传统关联规则挖掘技术进行地学数据的挖掘。

    §4.2代码实现

    4.2.1 R树索引实现

    常见的地学数据有矢量数据和栅格数据,栅格是本次实验处理的地学数据类型。栅格数据模型将地学空间按行、列分为像素阵列,其中每个单元称为像素,通过阵列中的值标记当前坐标位置属于何种地理实体(17)。栅格的数据常见表现形式为矩形,考虑到实验中矩形结构除了构造函数外只含有标记特征的左下角、右上角的坐标,所以本次使用struct 而不是class来表示矩形,简化set、get属性等操作,定义矩形SRectangle,包含(m_RightTopX,m_RightTopY)、(m_LeftBottomX,m_LeftBottomY)分别表示左下角、右上角的坐标。

    本实验中栅格数据的矩形划分都是平行于坐标轴的,降低操作过程中MBR操作的复杂性。

    4.2.1.1矩形相交判断

    判断两个矩形是否相交有很多方法,对于4条边都平行于坐标轴的矩形判断相交就更简单了。

    假定矩形是用一对点表达的

    {(m_RightTopX,m_RightTopY),(m_LeftBottomX,m_LeftBottomY)}

    那么两个矩形

    rectOne{(m_RightTopX,m_RightTopY),(m_LeftBottomX,m_LeftBottomY)},

    rectTwo{(m_RightTopX,m_RightTopY),(m_LeftBottomX,m_LeftBottomY)}

    相交的区域也是矩形

    rectJoin{(m_RightTopX,m_RightTopY),(m_LeftBottomX,m_LeftBottomY)}

    的点对坐标是:

    rectJoin->m_LeftBottomX=max( rectJoin->m_LeftBottomX, rectJoin->m_LeftBottomX)

    rectJoin->m_LeftBottomY=max( rectJoin->m_LeftBottomY, rectJoin->m_LeftBottomY)

    rectJoin->m_RightTopX=min(rectJoin->m_RightTopX, rectJoin->m_RightTopX)

    rectJoin->m_RightTopY=min(rectJoin->m_RightTopY, rectJoin->m_RightTopY)

    如果两个矩形有重合,则对应的点坐标必须同时满足下面的条件:

    rectJoin->m_LeftBottomX < rectJoin->m_RightTopX

    且rectJoin->m_LeftBottomY < rectJoin->m_RightTopY

    图4.1 矩形的4种可能位置关系

    4.2.1.2 R树相关操作

    R树是一棵根据MBR构建的高度平衡的处理多维数据的树,是B树在高维空间的扩展,常见的操作有插入、删除、查找等,时间复杂度均在O(log N)。R树的所有记录存储在对应的叶子节点上,所以插入、删除、查找等操作都会操作叶子节点,同时保证平衡性。

    1、查找

    若T是当前R树的根节点,查找所有矩形S覆盖的记录,标记为search(T,R)

    (1)T是非叶子节点,如果T对应的矩形与S重合,对于T中逐条记录,递归使用Search在每个孩子的根节点T[i]上,search(T[i],R);

    (2)T是叶子节点,如果T对应的矩形与S重合,处理S所覆盖下所有记录,返回符合条件记录。

    由于R树的特征,会出现需要在多个分支节点进行递归查找的情况,这点是和B树有区别的,这也是R树比较影响性能的地方。

    2、插入

    与B树一样,当新记录被插入叶子节点导致叶子节点溢出,此时就需要进行分裂操作。不同的是在在非叶子节点选择合适的分支插入,这点关系到整个R树的形状,从而决定R树的整体性能。

    R树插入不是每次都创建新叶子节点,而是将记录插入存在空闲位置的叶子节点上,由于不能插入满叶子节点,所以需要引入调整平衡的操作,将一个满R树叶子节点分裂后变成两个叶子节点,然后新建一个覆盖这两个新叶子节点所代表记录的节点,将 其与原叶子节点的父节点father合并,但是如果合并前father变为满,又要重复分裂操作了,之后father的父亲节点又有可能是满的,这样一来分裂操作会沿着R树向上一直延伸,导致两次操作插入记录的分支:一次是找到待插入叶子节点;另一次为满时进行分裂操作。为了避免两次遍历某个分支,我们并不是等到找出插入过程中实际要分裂的满节点时才分裂,相反,当沿着树往下需找待插入记录位置的过程中,随时分裂分支上遍历到的满节点,这样自上而下就能确保分裂满节点时,其对应的父亲节点不同时为满,从而避免进一步递归处理。

    若T是当前R树的根节点,E是待插入节点,标记为insert(T,E)

    (1)如果当前R树为满,则分裂split(T)当前节点,跳到步骤(2);否则,直接跳到步骤(2);

    (2)如果T是叶子节点,插入到当前最后一个空余位置;否则,修改T的MBR,运用一定的规则寻找合适的孩子分支T[i],然后递归执行insert(T[i],E)

    若T为当前R树待分裂的节点

    (1)将T从正中间分开,分裂成两个节点T1,T2,计算最小矩形覆盖MBR;

    (2)将父亲节点相应的孩子标记指针分别指向T1,T2。

    3、删除

    删除不同于与插入,删除分为两个主要阶段:定位,删除。

    若T为当前R树的根结点,E为待删除的元素,path为T到R树根节点的路径,标记为getCertainPath(T,E,P);

    (1)如果T是叶子节点,遍历T中每个节点T[i],看T[i]是否等于E:

    (1.1)如果T[i]等于E,直接将T[i]加入P的末尾,返回定位成功状态;

    (1.2)如果T[i]不等于E,继续遍历下一个;

    如果T中没有记录等于E,直接返回对应失败状态;

    (2)如果T不是叶子节点,遍历T中每个记录T[i],看T[i]是否包含E,即T[i]的MBR完全覆盖E的MBR :

    (2.1)如果T[i]包含E,将T[i]加入P的末尾,递归进行下一轮getCertainPath(T[i],E,P),如果 getCertainPath(T[i],E,P)返回成功状态,直接返回成功状态;否则遍历下一个;

    (2.2)如果T[i]不包含E,继续遍历下一个;

    如果T中没有包含记录E,返回对应失败状态。

    从上面的步骤可以看出删除的一定是叶子节点,这也符合本次试验的业务逻辑。同时,当包含多个相同的E时,删除的深度优先遍历到的第一个。当然,在实际应用中,是不可能有两个完全相同的E同时存在于一棵R树中。

    若T为当前R树的根结点,E为待删除的元素,path为T到R树根节点的路径,标记为erase(T,E,P);

    (1)如果T是叶子节点,遍历T中每个节点T[i],看T[i]是否等于E:

    (1.1)如果T[i]等于E,删除E;

    (1.2)如果T[i]不等于E,继续遍历下一个;

    (2)如果T不是叶子节点,遍历T中每个记录T[i],看T[i]是否等于P路径的第一个元素:

    (2.1)如果T[i]等于P路径的第一个元素,P中删除当前第一个元素,递归进行下一轮erase(T[i],E,P);

    (2.2)如果T[i]不包含E,继续遍历下一个;

    由于R树的特征,会出现需要在多个分支节点进行递归查找的情况,这点是和B树有区别的,这也是R树比较影响性能的地方。

    4.2.2基于栅格扫描的同位规则实现

    地学数据的同位规则挖掘在寻找满足条件的频繁项集的过程中,往往需要进行空间数据的几何关系计算,性能消耗非常大。如上面介绍的同位模式挖掘算法,就需要在每次循环中都进行步骤(4)搜索满足某种邻域关系的空间对象生成临时表和步骤(5)根据min_prevalence进行剪枝,消耗较大。

    基于栅格扫描的同位规则的核心在于对已经采集的地学数据进行预处理:即通过将小栅格合并成更大地理空间的栅格,产生去重后的项集,然后每个大栅格可以看做是泛化的事务。通过预处理技术可以产生事务集,然后对产生的事务集运用传统的关联规则算法Apriori算法和FP-growth算法发现满足条件的频繁项集。

    github地址:https://github.com/XuJin1992/The-Research-And-Implementation-Of-Data-Mining-For-Geological-Data.git

    §4.3实验结果分析

    4.3.1平台与数据

    实验中集成开发环境IDE是Microsoft Visual Studio 2012。语言选择的是C++,之所以选择C++,除了丰富灵活的语法外,还有就是编译型语言效率高。地学数据的固有特点:高维、非结构化、多关联性等,这给处理地学数据类型的数据模型、索引结构、存储方式、挖掘知识表达等方面带来挑战,除了算法本身的,在语言层面也与一定的要求。

    本算法处理的地学数据类型单元是矩形,具体形式为(position,attribute1,attribute2,attribute3……)其中的attribute i是字符类型的标签。在实验中,利用数据生成程序生成了100个这样的矩形单元,然后每个矩形单元随机生成项,对应在该空间的菲 空间属性特征。

    本次实验空间数据集都是模拟出来的,以文本形式存储,具体形式为(position,attribute1,attribute2,attribute3……)其中的attribute i是字符类型的标签,本次实验attribute选择了1个,2个,3个,4个等。一般来说,attribute越长,基于相同R-邻域产生的事务对应的项集的长度就越长。

    下面是一组模拟的空间数据集的原始数据集,其中attribute选择的是1,即每个栅格包含一个属性。

    表4.1 原始数据集

    0,0,1,1,I1 5,2,6,3,I2 0,5,1,6,I7 5,7,6,8,I0

    1,0,2,1,I7 6,2,7,3,I1 1,5,2,6,I4 6,7,7,8,I6

    2,0,3,1,I4 7,2,8,3,I6 2,5,3,6,I2 7,7,8,8,I1

    3,0,4,1,I0 8,2,9,3,I8 3,5,4,6,I7 8,7,9,8,I3

    4,0,5,1,I9 9,2,10,3,I5 4,5,5,6,I7 9,7,10,8,I8

    5,0,6,1,I4 0,3,1,4,I7 5,5,6,6,I9 0,8,1,9,I9

    6,0,7,1,I8 1,3,2,4,I6 6,5,7,6,I3 1,8,2,9,I3

    7,0,8,1,I8 2,3,3,4,I1 7,5,8,6,I1 2,8,3,9,I4

    8,0,9,1,I2 3,3,4,4,I8 8,5,9,6,I9 3,8,4,9,I4

    9,0,10,1,I4 4,3,5,4,I9 9,5,10,6,I8 4,8,5,9,I6

    0,1,1,2,I5 5,3,6,4,I2 0,6,1,7,I6 5,8,6,9,I0

    1,1,2,2,I5 6,3,7,4,I7 1,6,2,7,I5 6,8,7,9,I6

    2,1,3,2,I1 7,3,8,4,I9 2,6,3,7,I0 7,8,8,9,I6

    3,1,4,2,I7 8,3,9,4,I5 3,6,4,7,I2 8,8,9,9,I1

    4,1,5,2,I1 9,3,10,4,I4 4,6,5,7,I8 9,8,10,9,I8

    5,1,6,2,I1 0,4,1,5,I3 5,6,6,7,I6 0,9,1,10,I4

    6,1,7,2,I5 1,4,2,5,I1 6,6,7,7,I0 1,9,2,10,I9

    7,1,8,2,I2 2,4,3,5,I2 7,6,8,7,I2 2,9,3,10,I6

    8,1,9,2,I7 3,4,4,5,I3 8,6,9,7,I4 3,9,4,10,I3

    9,1,10,2,I6 4,4,5,5,I3 9,6,10,7,I8 4,9,5,10,I7

    0,2,1,3,I1 5,4,6,5,I4 0,7,1,8,I6 5,9,6,10,I8

    1,2,2,3,I4 6,4,7,5,I1 1,7,2,8,I5 6,9,7,10,I8

    2,2,3,3,I2 7,4,8,5,I1 2,7,3,8,I0 7,9,8,10,I2

    3,2,4,3,I3 8,4,9,5,I3 3,7,4,8,I9 8,9,9,10,I9

    4,2,5,3,I2 9,4,10,5,I8 4,7,5,8,I0 9,9,10,10,I1

    上面是最原始的数据集,将其按栅格形式处理后的整列为:

    I1 I7 I4 I0 I9 I4 I8 I8 I2 I4

    I5 I5 I1 I7 I1 I1 I5 I2 I7 I6

    I1 I4 I2 I3 I2 I2 I1 I6 I8 I5

    I7 I6 I1 I8 I9 I2 I7 I9 I5 I4

    I3 I1 I2 I3 I3 I4 I1 I1 I3 I8

    I7 I4 I2 I7 I7 I9 I3 I1 I9 I8

    I6 I5 I0 I2 I8 I6 I0 I2 I4 I8

    I6 I5 I0 I9 I0 I0 I6 I1 I3 I8

    I9 I3 I4 I4 I6 I0 I6 I6 I1 I8

    I4 I9 I6 I3 I7 I8 I8 I2 I9 I1

    表4.2 数据集阵列形式

    4.3.2结果分析

    为了使传统关联规则挖掘技术适用于地学数据,本文提出了基于栅格扫描的事物生成预处理技术。然后选用传统数据挖掘中较为经典的Apriori算法和FP-growth算法寻找频繁项集,由于栅格扫描预处理技术是基于Tobler的地理学第一定理的,根据R-邻域来寻找栅格邻域产生项集事务的,所以具有同位模式的基本思想。

    4.3.1.1可行性分析

    本文的主要亮点是基于栅格扫描的空间同位规则挖掘算法,而该算法的重要工作就是预处理产生事务集,从而使传统关联规则的方法可以应用在空间关联规则领域。

    在预处理产生事务集的过程中,对于R-邻域的R做了多次实验,如5-邻域,9邻域等,如图:

    图4.2 5-邻域

    基于空间扩展的5-邻域,产生的事务集中每个事务对应的项集长度不超过5*n个,如果存在重复的长度会小于5*n个。

    图4.3 9-邻域

    基于空间扩展的9-邻域,产生的事务集中每个事务对应的项集长度不超过9*n个,如果存在重复的长度会小于9*n个

    上述,n是每个栅格采集的非空间属性数量,在本次实验中分别选取了1,2,3,4等。一般来说,n越大,对应的频繁项集越长,实验时间也就越长,得到的空间同位模式也比较长。

    同理,R-邻域中R不同,得到的空间同位模式表达也不同,一般说来,R越大,对应的频繁项集越长,实验时间也就越长,得到的空间同位模式也比较长。

    关于以某个点为中心的R-邻域的寻找是本次基于栅格扫描算法的一个性能瓶颈;R树空间索引就起到了至关重要的作用:可以加快寻找特定矩形区域内的所用记录。以下面展示的9-邻域为例,如果中心点对应的矩形多表示是T{(3,3),(4,4)},那么其对应的9-邻域的就一定在矩形S{(2,2),(5,5)}内,然后在R树中检索矩形S覆盖的所有叶子节点即可。

    下面是上述原始数据集对应的R树,由于时间关系,R树的展示并没有做到可视化展示,只能显示层次关系。其中,R树阈值[m,M]设定为[2,4],即每个节点除非是根节点,否则每个节点最少拥有2个,最多拥有4个叶子节点,这样一来,R树的深度范围就是[3,6](假定根节点的深度为0的情况下)。

    表4.3 R树展示

    [(0,0),(10,10)]非叶

    [(0,0),(3,10)]非叶

    [(0,0),(1,10)]非叶

    [(0,0),(1,10)]非叶

    [(0,0),(1,1)]叶

    [(0,1),(1,2)]叶

    [(0,8),(1,9)]叶

    [(0,9),(1,10)]叶

    [(0,6),(1,8)]非叶

    [(0,6),(1,7)]叶

    [(0,7),(1,8)]叶

    [(0,4),(3,10)]非叶

    [(0,4),(2,10)]非叶

    [(0,4),(1,5)]叶

    [(0,5),(1,6)]叶

    [(1,8),(2,9)]叶

    [(1,9),(2,10)]叶

    [(1,6),(3,10)]非叶

    [(1,6),(2,7)]叶

    [(1,7),(2,8)]叶

    [(2,8),(3,9)]叶

    [(2,9),(3,10)]叶

    [(1,4),(3,8)]非叶

    [(2,6),(3,8)]非叶

    [(2,6),(3,7)]叶

    [(2,7),(3,8)]叶

    [(1,4),(2,6)]非叶

    [(1,4),(2,5)]叶

    [(1,5),(2,6)]叶

    [(0,1),(9,10)]非叶

    [(0,1),(6,10)]非叶

    [(0,2),(6,4)]非叶

    [(0,2),(1,3)]叶

    [(0,3),(1,4)]叶

    [(5,2),(6,3)]叶

    [(5,3),(6,4)]叶

    [(2,1),(6,9)]非叶

    [(2,4),(3,5)]叶

    [(5,1),(6,2)]叶

    [(5,8),(6,9)]叶

    [(5,6),(6,10)]非叶

    [(5,6),(6,7)]叶

    [(5,7),(6,8)]叶

    [(5,9),(6,10)]叶

    [(5,4),(9,10)]非叶

    [(5,4),(7,10)]非叶

    [(5,4),(6,5)]叶

    [(5,5),(6,6)]叶

    [(6,8),(7,9)]叶

    [(6,9),(7,10)]叶

    [(6,6),(9,10)]非叶

    [(6,6),(7,7)]叶

    [(6,7),(7,8)]叶

    [(8,8),(9,9)]叶

    [(8,9),(9,10)]叶

    [(6,0),(10,10)]非叶

    [(6,2),(9,8)]非叶

    [(6,4),(9,8)]非叶

    [(6,4),(7,5)]叶

    [(6,5),(7,6)]叶

    [(8,7),(9,8)]叶

    [(6,2),(9,4)]非叶

    [(6,2),(7,3)]叶

    [(6,3),(7,4)]叶

    [(8,3),(9,4)]叶

    [(8,0),(10,10)]非叶

    [(8,1),(10,3)]非叶

    [(8,1),(9,2)]叶

    [(8,2),(9,3)]叶

    [(9,1),(10,2)]叶

    [(9,2),(10,3)]叶

    [(8,0),(10,10)]非叶

    [(8,6),(9,7)]叶

    [(9,0),(10,1)]叶

    [(9,9),(10,10)]叶

    [(9,7),(10,9)]非叶

    [(9,7),(10,8)]叶

    [(9,8),(10,9)]叶

    [(9,5),(10,7)]非叶

    [(9,5),(10,6)]叶

    [(9,6),(10,7)]叶

    [(8,3),(10,6)]非叶

    [(9,3),(10,5)]非叶

    [(9,3),(10,4)]叶

    [(9,4),(10,5)]叶

    [(8,4),(9,6)]非叶

    [(8,4),(9,5)]叶

    [(8,5),(9,6)]叶

    [(1,0),(9,10)]非叶

    [(6,0),(9,10)]非叶

    [(6,0),(8,10)]非叶

    [(6,0),(8,10)]非叶

    [(6,0),(7,1)]叶

    [(6,1),(7,2)]叶

    [(7,8),(8,9)]叶

    [(7,9),(8,10)]叶

    [(7,6),(8,8)]非叶

    [(7,6),(8,7)]叶

    [(7,7),(8,8)]叶

    [(7,0),(9,6)]非叶

    [(7,4),(8,6)]非叶

    [(7,4),(8,5)]叶

    [(7,5),(8,6)]叶

    [(7,0),(9,4)]非叶

    [(7,2),(8,3)]叶

    [(7,3),(8,4)]叶

    [(8,0),(9,1)]叶

    [(1,0),(8,10)]非叶

    [(2,0),(8,6)]非叶

    [(7,0),(8,2)]非叶

    [(7,0),(8,1)]叶

    [(7,1),(8,2)]叶

    [(2,2),(3,6)]非叶

    [(2,2),(3,3)]叶

    [(2,3),(3,4)]叶

    [(2,5),(3,6)]叶

    [(1,0),(4,10)]非叶

    [(1,2),(2,4)]非叶

    [(1,2),(2,3)]叶

    [(1,3),(2,4)]叶

    [(1,0),(4,10)]非叶

    [(1,0),(2,1)]叶

    [(1,1),(2,2)]叶

    [(3,9),(4,10)]叶

    [(3,4),(4,9)]非叶

    [(3,4),(4,5)]叶

    [(3,8),(4,9)]叶

    [(2,0),(6,10)]非叶

    [(3,0),(6,10)]非叶

    [(3,2),(4,8)]非叶

    [(3,2),(4,8)]非叶

    [(3,2),(4,3)]叶

    [(3,3),(4,4)]叶

    [(3,7),(4,8)]叶

    [(3,5),(4,7)]非叶

    [(3,5),(4,6)]叶

    [(3,6),(4,7)]叶

    [(3,0),(6,10)]非叶

    [(3,0),(6,2)]非叶

    [(3,0),(4,1)]叶

    [(3,1),(4,2)]叶

    [(5,0),(6,1)]叶

    [(4,8),(5,10)]非叶

    [(4,8),(5,9)]叶

    [(4,9),(5,10)]叶

    [(4,6),(5,8)]非叶

    [(4,6),(5,7)]叶

    [(4,7),(5,8)]叶

    [(2,0),(5,6)]非叶

    [(4,2),(5,6)]非叶

    [(4,4),(5,6)]非叶

    [(4,4),(5,5)]叶

    [(4,5),(5,6)]叶

    [(4,2),(5,4)]非叶

    [(4,2),(5,3)]叶

    [(4,3),(5,4)]叶

    [(2,0),(5,2)]非叶

    [(4,0),(5,2)]非叶

    [(4,0),(5,1)]叶

    [(4,1),(5,2)]叶

    [(2,0),(3,2)]非叶

    [(2,0),(3,1)]叶

    [(2,1),(3,2)]叶

    R树阈值[m,M]设定为[2,4],由树形结构可以看出,深度为4,符合理论分析,同时相邻两层后一层是前一层的倍数也在[2,4]范围内。通过预处理,上述原始数据集对应的空间事务集如下,下图是根据9-邻域计算的,当然,边界其实没有完整9个邻域矩形。

    表4.4 空间事务集

    I1 I5 I7 I1 I8 I5 I4 I9

    I1 I5 I4 I7 I2 I1 I8 I5 I4 I9

    I5 I1 I7 I4 I6 I2 I1 I7 I5 I9

    I3 I1 I7 I4 I6 I2 I4 I1 I7 I3 I9

    I3 I7 I1 I4 I6 I2 I4 I9 I1 I3 I7

    I6 I3 I7 I5 I1 I4 I6 I4 I9 I0 I1 I3 I8 I7

    I6 I7 I5 I4 I6 I0 I9 I3 I8 I7

    I9 I6 I3 I5 I0 I6 I8

    I9 I4 I6 I3 I5 I0 I8 I6 I7

    I9 I4 I3 I0 I8 I6 I7

    I1 I5 I7 I4 I1 I8 I5 I2 I4

    I1 I5 I2 I4 I7 I2 I1 I8 I5 I6 I4

    I5 I1 I7 I2 I4 I6 I2 I1 I7 I5 I6 I9

    I3 I1 I7 I2 I4 I6 I2 I4 I1 I7 I6 I9

    I3 I7 I1 I4 I2 I6 I2 I4 I9 I1 I3 I7

    I6 I3 I7 I5 I0 I1 I4 I2 I6 I4 I9 I0 I1 I3 I2

    I6 I7 I5 I0 I4 I2 I6 I0 I9 I3 I2 I1

    I9 I6 I3 I5 I4 I0 I0 I6 I2 I1

    I9 I4 I6 I3 I5 I0 I0 I8 I6 I2 I1

    I9 I4 I3 I6 I0 I8 I6 I2

    I7 I5 I0 I4 I1 I7 I8 I5 I2

    I2 I4 I7 I5 I3 I0 I1 I1 I7 I8 I5 I6 I2

    I2 I1 I4 I6 I5 I3 I8 I7 I1 I7 I5 I8 I6 I9 I2

    I1 I2 I4 I6 I3 I8 I1 I7 I5 I8 I3 I6 I9

    I1 I4 I2 I6 I3 I8 I7 I1 I3 I7 I5 I9

    I5 I0 I1 I4 I2 I3 I7 I0 I1 I3 I4 I9 I2

    I5 I0 I4 I2 I9 I7 I0 I6 I3 I4 I9 I2 I1

    I3 I5 I4 I0 I9 I2 I6 I0 I1 I3 I4 I2

    I3 I9 I5 I4 I6 I0 I6 I8 I1 I9 I3 I2

    I3 I9 I4 I6 I6 I8 I1 I9 I2

    I0 I7 I9 I1 I4 I7 I6 I4 I2 I8

    I2 I3 I0 I7 I9 I1 I4 I7 I8 I6 I5 I4 I2

    I2 I1 I3 I8 I7 I9 I5 I7 I8 I6 I4 I9 I2

    I2 I1 I3 I8 I9 I5 I8 I4 I3 I1 I6 I9

    I2 I1 I3 I8 I7 I9 I5 I8 I4 I3 I9 I1

    I0 I2 I3 I7 I8 I4 I8 I3 I9 I2 I1

    I0 I2 I9 I7 I8 I3 I4 I8 I9 I2 I1

    I4 I0 I9 I2 I6 I8 I1 I3 I4 I8 I6 I2

    I4 I6 I0 I3 I9 I7 I1 I9 I3 I8 I6 I2

    I4 I6 I3 I7 I1 I9 I8 I6 I2

    I1 I0 I7 I4 I9 I7 I6 I4 I2

    I2 I1 I3 I0 I7 I4 I9 I7 I8 I6 I5 I4 I2

    I2 I1 I3 I8 I7 I9 I5 I7 I8 I6 I4

    I2 I4 I3 I8 I9 I5 I8 I4 I3

    I2 I4 I9 I3 I8 I7 I5 I8 I4 I3 I9

    I6 I4 I9 I3 I7 I2 I8 I4 I8 I3 I9

    I6 I0 I9 I7 I2 I8 I3 I4 I8 I9

    I0 I6 I4 I9 I2 I8 I1 I3 I4 I8

    I0 I8 I3 I4 I9 I6 I7 I1 I9 I3 I8

    I0 I8 I3 I4 I6 I7 I1 I9 I8

    在原始数据集中,每个栅格除了标志空间属性的矩形坐标信息外,只拥有一个非空间属性,上图是9-邻域扫描后去重产生的事务集。每个事物表示一组9-邻域内的空间同位规则,如{I1,I2,I3}表示I1,I2,I3标志的属性在9-邻域关系下是相邻的。

    下面是最小支持度为0.1时Apriori算法、FP-growth算法计算结果:

    表4.5 Apriori算法频繁4项集

    I4 I1 I5 I7 I8 I1 I9 I2

    I2 I1 I5 I7 I6 I5 I7 I4

    I6 I1 I7 I4 I2 I5 I7 I4

    I3 I1 I7 I4 I2 I5 I7 I6

    I2 I1 I7 I4 I3 I7 I4 I6

    I3 I1 I7 I6 I2 I7 I4 I6

    I2 I1 I7 I6 I8 I7 I4 I6

    I9 I1 I7 I3 I9 I7 I4 I3

    I2 I1 I7 I3 I2 I7 I4 I3

    I2 I1 I7 I9 I2 I7 I4 I9

    I3 I1 I4 I6 I8 I7 I6 I2

    I2 I1 I4 I6 I2 I7 I3 I9

    I9 I1 I4 I3 I9 I4 I6 I3

    I2 I1 I4 I3 I2 I4 I6 I3

    I0 I1 I4 I3 I0 I4 I6 I3

    I8 I1 I4 I3 I0 I4 I6 I9

    I2 I1 I4 I9 I8 I4 I6 I2

    I2 I1 I6 I3 I2 I4 I3 I9

    I2 I1 I6 I9 I0 I4 I3 I9

    I8 I1 I6 I2 I8 I4 I3 I9

    I2 I1 I3 I9 I0 I4 I3 I2

    I8 I1 I3 I9 I0 I6 I3 I9

    I0 I1 I3 I2 I8 I6 I9 I2

    I8 I1 I3 I2 I8 I3 I9 I2

    表4.6 FP-growth算法频繁项集

    I4 I5 I0 10 I1 I9 I7 17

    I1 I0 16 I4 I2 I9 I7 10

    I4 I1 I0 13 I1 I2 I9 I7 12

    I1 I3 I0 11 I4 I2 I3 I7 10

    I4 I1 I3 I0 10 I1 I2 I3 I7 12

    I4 I3 I0 17 I1 I3 I7 21

    I2 I7 I0 10 I4 I1 I3 I7 16

    I4 I7 I0 14 I4 I3 I7 22

    I1 I2 I0 12 I1 I6 I7 16

    I4 I2 I0 14 I4 I1 I6 I7 12

    I4 I3 I9 I0 12 I1 I3 I6 I7 10

    I4 I9 I0 17 I4 I3 I6 I7 14

    I4 I3 I6 I0 11 I1 I2 I6 I7 10

    I4 I6 I0 14 I4 I2 I6 I7 14

    I4 I0 24 I4 I6 I7 25

    I4 I3 I5 14 I1 I7 35

    I1 I8 I5 10 I4 I1 I7 25

    I4 I8 I5 13 I1 I2 I7 22

    I4 I9 I5 12 I4 I1 I2 I7 15

    I1 I2 I5 13 I4 I2 I7 24

    I4 I2 I5 15 I4 I7 40

    I1 I6 I5 11 I1 I6 30

    I4 I6 I5 17 I4 I1 I6 19

    I1 I5 24 I1 I3 I6 19

    I4 I1 I5 17 I4 I1 I3 I6 15

    I4 I6 I7 I5 11 I4 I3 I6 26

    I1 I2 I7 I5 10 I1 I3 I2 I6 10

    I4 I2 I7 I5 11 I4 I2 I6 22

    I1 I7 I5 18 I1 I2 I6 23

    I4 I1 I7 I5 11 I4 I1 I2 I6 13

    I4 I7 I5 18 I4 I6 40

    I4 I5 31 I1 I6 I9 11

    I4 I7 I8 12 I1 I9 34

    I4 I6 I7 I8 11 I4 I1 I9 18

    I1 I8 28 I4 I2 I9 20

    I4 I1 I8 14 I1 I2 I9 24

    I1 I3 I8 18 I4 I1 I2 I9 12

    I4 I1 I3 I8 10 I4 I9 38

    I4 I3 I8 19 I1 I3 I9 23

    I4 I8 30 I4 I1 I3 I9 13

    I1 I6 I8 15 I4 I3 I9 29

    I4 I6 I8 17 I4 I3 I2 12

    I1 I2 I6 I8 12 I1 I3 I2 13

    I4 I2 I6 I8 12 I4 I1 I3 I2 10

    I4 I9 I8 17 I4 I2 39

    I1 I9 I8 19 I1 I2 41

    I1 I2 I9 I8 12 I4 I1 I2 26

    I4 I3 I9 I8 12 I4 I2 I3 12

    I1 I3 I9 I8 13 I1 I2 I3 14

    I4 I2 I8 18 I4 I1 I2 I3 10

    I1 I2 I8 20 I1 I3 37

    I4 I9 I7 15 I4 I1 I3 27

    I4 I3 I9 I7 10 I4 I3 46

    I1 I3 I9 I7 11 I4 I1 40

    通过基于栅格扫描的预处理后,空间同位规则挖掘就可以用传统关联规则直接处理了。实验之处选择的是Apriori算法,但是性能比较差,即使是100个事务的数据集也要跑很长时间,原因在于候选项集的产生可能带来组合爆炸问题;而FP-growth算法则利用树形结构有效的回避了这点,带来比较好的时间性能。

    4.3.1.2相关因子的影响

    本次实验是基于栅格扫描的空间同位模式挖掘,算法中涉及的变量比较多,下面给出一些关键的因子:

    (1)、采集的地学数据集的实例个数n,决定着同位模式挖掘中的事务集的大小,如上面原始数据集中的n设定为10;

    (2)、在预处理阶段,R树空间索引对实验性能的影响,本次选题的一个重要成果就是R树索引的引入,如上面原始数据集就是用了R树索引;

    (3)、R树索引的R树阈值范围[m,M],决定着R树每个节点的记录个数范围,从而影响R树的深度,如上面原始数据集中的R树阈值范围设定为[2,4];

    (4)、R-邻域中R的大小,决定着以某个点为中心的邻域范围,是预处理阶段非常重要的参数,定义了同位的阈值,如上面原始数据集中的R设定为9,即9-邻域;

    (5)、Aprori算法挖掘的频繁K项集的K,决定着迭代次数,如上面原始数据集中的K设定为4;

    (6)、关联规则的最小支持度minsup,决定着筛选频繁项集的支持度阈值,如上面原始数据集中的minsup设定为0.1;

    地学数据集的实例个数n

    在其他参数都相同的情况下,地学数据集的实例个数n对实验有着重要影响。下图是R树阈值范围[2,4]、9-邻域、Aprori算法挖掘的是频繁4项集、关联规则的最小支持度minsup=0.10的条件下进行的实验结果展示:

    图4.4 实例数量对预处理影响

    数据集n越大,耗时越长,Apriori算法基本呈指数指数增长,而FP-growth算法则多项式增长。从这个维度可以知道对于大数据量的数据集,FP-growth算法的优势很明显。

    R树空间索引

    在其他参数都相同的情况下,R树空间索引对实验有着重要的影响。下图是R树阈值范围[2,4]、9-邻域的条件下进行的实验结果展示:

    图4.5 R树索引对预处理影响

    由于本文提出的基于栅格扫描的同位模式挖掘算法中,栅格扫描的预处理和之后的关联规则挖掘是分开的,所以研究预处理阶段,R树空间索引对实验性能的影响可以回避后面的关联规则挖掘算法。

    实验表明:在栅格扫描产生事务集的过程中,使用R树索引比不适用任何索引有着显著的性能提升。仅就寻找单个中心点的R-邻域而言,不用索引,平均时间复杂度为O(n);使用R树空间,忽略R树节点MBR相互重合的理想情况下,时间复杂度O(log(n))。但是,上面的曲线并没有反应对应时间复杂度的变化,主要原因在于在栅格扫描产生事务集的过程中,寻找每个中心点的R-邻域内的所有记录仅仅是一部分工作,剩下的主要工作是对每个R-邻域产生空间事务集,此时需要在遍历过程中判重,保证每个事物中相同属性仅出现一次。

    R树阈值范围[m,M]

    在其他参数都相同的情况下,R树阈值范围[m,M]对实验有着重要影响,下图是数据集实例个数10000的条件下进行的实验结果展示:

    图4.6 R树阈值范围[m,M]对预处理影响

    由于本文提出的基于栅格扫描的同位模式挖掘算法中,栅格扫描的预处理和之后的关联规则挖掘是分开的,所以研究预处理阶段,R树阈值[m,M]对实验性能的影响可以回避后面的关联规则挖掘算法。

    实验表明:[m,M]的不同,直接影响的是R树每个节点对应记录数,从而影响R树的高度,如当取[2,4]时,树的高度为12;当取[4,8]时,树的高度为6。可以看出,[m,M]取值越大,对应的R树高度越低;但是预处理时间并未随着降低,究其原因,[m,M]越大时,R树的整体高度虽然降低了,但是在每个节点搜索孩子分支的时间变长了,几个例子,本来是[2,4]个记录信息,现在变成[4,8]个记录信息,在每个节点上遍历查找个数增加,时间变长,从而抵消了R树高度变低带来的影响,导致整个预处理过程并未发生性能变化。

    R-邻域中R

    在其他参数都相同的情况下,R-邻域中R的大小对实验有着重要影响,下图是数据集实例个数32*32的条件下进行的实验结果展示:

    图4.7 R-邻域中R对预处理影响

    由于本文提出的基于栅格扫描的同位模式挖掘算法中,栅格扫描的预处理和之后的关联规则挖掘是分开的,所以测试R-邻域对实验的影响时没有执行后面的Apriori算法和FP-growth算法,只是研究了R取值对整个预处理消耗时间的影响。

    实验表明:当R-邻域中R取值越大,产生空间事务集的时间就越长,而且呈现多项式变化趋势。R-邻域中R取值越大,对应的以某个点为中心的搜索区域就越大,在R树中搜索的分支就尽可能的多,自然拉低性能。在实际的应用中,R-邻域的取值取决于具体的业务需求,同位概念需要定义一个距离阈值,既不可能距离很远的采样点都算作同位。关于这点,个人认为有些学者提出的基于k-近邻思想来找空间同位属性是不可取的,因为k-近邻最终要得到k个最近的属性,如果这k个属性相互之间距离比较远,只是比其他的要近一点,这样同位模式就严重失真了。

    Aprori算法挖掘的频繁K项集的K

    在其他参数都相同的情况下,Aprori算法挖掘的频繁K项集的K对实验有着重要影响,下图是数据集实例个数1000、R树阈值范围[2,4]、9-邻域、关联规则的最小支持度minsup=0.10的条件下进行的实验结果展示:

    图4.8 Aprori算法频繁K项集的K对实验影响

    实验表明:Aprori算法挖掘的频繁K项集中K越大,消耗时间越多;在一定范围内,随着K的增加消耗时间呈指数增长趋势;当超过每个阈值后,逐渐演变为随着K的增长呈多项式增长趋势。分析原因,在于Apriori算法需要产生大量的候选项集,如第二章关联规则处理地学数据的基本理论所描述的那样,候选项集的产生会导致组合爆炸问题,从而在开始阶段随着K的增加消耗时间呈指数增长趋势,如上图的K<=4时的分段函数;当K增加到一定的阈值时,如上图的K=4,此时满足条件的频繁K项集大幅减少,且随着K的增长,频繁K项集减少得越来越快,所以候选项集的个数也会急剧减少,从而使消耗时间趋势变成多项式变化。

    关联规则的最小支持度minsup

    在其他参数都相同的情况下,关联规则的最小支持度minsup对实验有着重要影响,下图是数据集实例个数32*32、R树阈值范围[2,4]、9-邻域、Aprori算法挖掘的是频繁4项集的条件下进行的实验结果展示:

    图4.9 最小支持度minsup对实验影响

    实验表明:随着关联规则的最小支持度minsup的增加,Apriori算法消耗的时间在逐渐减少,FP-growth算法消耗的时间基本保持稳定。对于Apriori算法,最小支持度minsup

    的增加,会导致频繁K项集个数减少,候选项集也随之减少,从而Apriori-gen过程中每次循环处理的项集个数减少,整体时间就降下来了。对于FP-growth算法,不产生候选项集,整个过程都是在迭代处理树状结构,不存在依靠最小支持度minsup在中间过程中筛选,所以时间不随最小支持度minsup的变化而变化。

    实验结果还表明:在一般情况下,即最小支持度minsup不高的情况下,FP-growth算法比Apriori算法性能明显要好;在最小支持度minsup比较高的情况下,选择Apriori算法比FP-growth算法有优势,因为在中间迭代过程中过滤掉很多不符合minsup的项集,从而大幅提升Apriori算法的效率。

    §4.4本章小结

    本章主要介绍了算法实现过程中的一些问题以及对实验结果进行了的分析。算法实现基本分成两个模块:一是R树空间索引的建立,二是关联规则算法的实现。然后介绍了实验平台和实验所用数据来源,最后对实验结果进行了简要的分析,衡量基于栅格扫描的同位规则算法的可行性,同时对相关因子对实验结果的影响进行了分析。

    第五章 总结与展望

    §5.1总结

    本文的主要研究内容是面向地学数据的数据挖掘研究与实现,选题的要求是“着重考虑大数据量情景下的数据模型(栅格或矢量)、索引结构和算法实现的性能”,所以全部代码都用性能较高的C++编写,同时在算法设计和实现上做了很多改进和优化,主要工作和成果归纳为以下几点:

    (1)为了加快邻域的寻找,选择建立R树空间索引,在此基础上总结了常用空间索引技术的适用场景和优缺点。

    (2)在分析传统关联规则与空间关联规则的理论基础上,对基于事件中心模型的空间同位模式挖掘算法进行描述,同时提出基于栅格扫描的同位规则挖掘算法,该算法通过扫描以某个栅格为中心的R-邻域栅格产生事务集,从而将地学数据挖掘运用传统数据挖掘技术实现。

    (3)在空间索引R树的插入过程中,为了防止插入叶子节点后需要分裂,从而导致递归的向上一直分裂破坏单向遍历,提出在寻找插入位置的过程中如遇到满节点即记录数为M(M为每个节点最多插入记录数)的节点,就先进行分裂从而避免之后层层向上递归分裂,加快R树插入效率。

    (4)在预处理产生的空间事务集的基础上,实现Apriori算法和FP-growth算法两种经典的关联规则挖掘算法,对比分析性能,做到辩证看待事物。

    空间同位模式的挖掘已经取得了长足的发展,但是仍然面临着巨大的挑战,本文提出的基于栅格扫描的空间同位模式挖掘算法能有效的挖掘离散型、布尔型地学数据中隐含的关联规则。

    §5.2展望

    无论是空间同位模式本身还使其在地学数据方面的应用,国内外的研究和应用都相对较少。本次毕设提出的基于栅格扫描的空间同位模式挖掘算法在效果和性能上都存在很多的问题。

    (1)目前在事务的产生上主要依靠预先设定的R-邻域,这样产生的同位项集可能不能准确反应空间数据的相关性,但是目前比较通用的极大团技术又很耗资源而且效果并不是很理想,有待进一步发现相关的事务产生自适应算法。

    (2)空间索引技术也是制约性能的瓶颈之一,文中选取的R树索引空间经常重叠,且重叠度随着数据量增加而增加,浪费存储空间,同时导致检索分支的增多降低性能。

    (3)对于Apriori算法和FP-growth算法没有做进一步的优化工作:Apriori算法产生大量的候选项集可能带来组合爆炸问题,FP-growth算法在数据量很大时对内存容量要求比较高。

    (4)目前处理的空间数据特征类型主要是离散型、布尔型,而大量的连续型、数值型的数据却不能很好

    致 谢

    光阴似箭,一转眼,四年的大学学习生活即将结束。现在回想起来,大学里确实学到很多东西,无论是专业知识还是为人处世方面。静静地回想起这四年的点点滴滴以及在做毕业设计的这段时间,除了对学术的敬畏和离别的愁思,内心还充满了对母校、师长、同学以及所有关爱和帮助过我的亲朋好友们的深深感激。

    首先感谢我的指导老师**老师。张老师是一位严谨渊博的老师,对待问题一丝不苟,容不得丝毫马虎。这选题时他很严谨的为我指引方向,并有效敦促毕业设计程序和论文的开展进度。每当我在做毕业设计的过程中遇到问题时,他总是百忙中抽出时间,悉心帮助我解决问题,拨除迷雾。最让我感动的是他对我在毕设过程中出现问题的理解,包容和帮助,在毕设过程中曾到企业实习两个多月,导致进度滞后,张老师没有责备,而是耐心提醒。如果没有他的帮助,可能毕业设计根本无法按时完成,在 这里再次真心感谢我的指导老师张锋老师。

    感谢509的各位室友们,每当我毕设遇到麻烦时,他们总能用实际行动对我给与帮助,或精神鼓励,或技术支持。

    感谢我的父母们,谢谢你们一直以来给与我的养育与呵护。

    最后,感谢那些一直在我背后支持我、帮助过我的人。

    参考文献

    [1] R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of data. 1993: 207-216.

    [2] 韩家炜, 坎伯. 数据挖掘概念与技术. 北京: 机械工业出版社. 2005: 223-232.

    [3] 张希雯. 基于GIS的空间同位规则挖掘算法的实现及应用研究. 硕士论文. 厦门大学. 2-12. 2007.

    [4] 邓有莲. GIS数据库中带有决策属性集的空间关联规则挖掘技术研究. 硕士论文. 江西师范大学. 6-24. 2007.

    [5] 刘小生, 任海峰, 陈棉. 用空间分析方法进行空间关联规则提取. 测绘报. 2007, 34: 14-17.

    [6] 赵芳芳, 张军. 多尺度空间数据索引方法研究. 测绘工程. 2008, 11: 491-499.

    [7] Thomas S, Bodagala S, Alsabti K, Ranka S. An efficient algorithm for the incremental updating of association rules in large databases. Proceedings of the 3th International Conference on Knowledge Discovery and Data Mining. USA. 1997, 10(5) : 263-266.

    [8] 赵学胜. 基于QTM的球面Voronoi数据模型研究. 硕士论文. 中国矿业大学. 23-34. 2002.

    [9] 王旭. 基本概念格的关联规则挖掘算法. 鞍山科技大学学报. 2005, 10(5) : 121-155.

    [10] 王涛. 挖掘序列模式和结构化模式的精简集. 博士论文. 华中科技大学. 31-42. 2006.

    [11] 王占全. 空间分类数据同位规则挖掘算法. 计算机辅助设计与图形学学报. 2005, 11(1) : 123-200.

    [12] 惠亮. 关联规则挖掘算法的研究与应用. 硕士论文. 厦门大学. 5-16. 2011.

    [13] 张希雯. 基于GIS的空间同位规则挖掘算法的实现及应用研究. 硕士论文. 厦门大学. 22-32. 2007.

    [14] Morimoto. Mining Frequent Neighboring ClassDatabase. Proceeding of the 7th ACM SIGKDD International Knowledge Discovery and Data Mining. USA. 1999, 10(5) : 353-358.

    [15] 麻伟斌. 基于CPRIP-Tree的空间伴生模式挖掘算法研究与应用. 硕士论文. 福建师范大学. 6-12. 2011.

    [16] 李德仁, 王树良, 史文中, 王新洲. 论空间数据挖掘和知识发现. 武汉大学学报. 2001, 26(6): 491-499.

    [17] YanHuang, Shashi Shekhar, and Hui Xiong. Discovering Colocation Patterns from Spatial DataSets: A General Approach. IEEE Transaction On Kownledge And Data Engineering. 2004, 26(6): 23-45.

    原创作品,出自 “晓风残月xj” 博客,欢迎转载,转载时请务必注明出处(http://blog.csdn.net/xiaofengcanyuexj)。

    由于各种原因,可能存在诸多不足,欢迎斧正!

    位置:首页 > 科技
    加载更多评论...
    相关文章
    实验动物—为科学献身的那些生灵
    实验动物—为科学献身的那些生灵

    你知道每年的4月24日是“世界实验动物日”吗?什么是实验动物?它们在科学研究中起了什么作用?它们的福利状况究竟如何?请跟着我,走进这个特殊的动物族群……银河异客——Laika谁是Laika?它是一只两岁大的苏联太空狗,1957年11月3日搭乘Sputnik II号火箭升空。

    731部队利用中国战俘进行细菌实验的绝密照片曝光
    731部队利用中国战俘进行细菌实验的绝密照片曝光

    1942年10月,关东军要求伪满洲国实施穆兴水路修改工程。该工程就是把流入兴凯湖的穆棱河河道加以修改,以便形成对苏作战的有利阵地。该工程计划3年完成,共动员了7000多名劳工,总投资1000多万元。由于局势紧张,关东军要求提前完成任务。

    科学实验丨用纸折出来的花,居然也绽放?!
    科学实验丨用纸折出来的花,居然也绽放?!

    “清水出芙蓉,天然去雕饰”这是李白诗里的名句今天尖叔教大家创造出清丽可人的“出水芙蓉”动起用水彩笔在A4纸上画出几朵颜色各异的花朵把花瓣向花蕊中间折现在我们得到了未开的“花苞”往盘子里倒上一些水,水至少要比盘面高出一厘米把“花苞”放到盘子里...

    天宫二号月夜发射:从宇宙爆炸到材料合成,科学实验大揭秘
    天宫二号月夜发射:从宇宙爆炸到材料合成,科学实验大揭秘

    海归学者发起的公益学术平台分享信息,整合资源交流学术,偶尔风月本文部分内容由微信公众号“环球科学ScientificAmerican”(ID: huanqiukexue)授权转载撰文 《环球科学》记者 丁家琦 2016年9月15日22时04分...

    日本731部队拿中国人做无人性实验残酷照片,历史之证
    日本731部队拿中国人做无人性实验残酷照片,历史之证

    侵华日军七三一部队是日本军国主义最高统治者下令组建的细菌战秘密部队,是人类历史上最大规模、最灭绝人性的细菌战研究中心。他们利用健康活人进行细菌战和毒气战等实验。在严寒的季节里,他们将被试验者的手脚接受不同时间的冷冻,然后将其插入冷水、温水和开水中解冻,观察其冻伤程度;

    老外用实验的结果告诉你,下冰雹千万别乱停否则你会知错了!
    老外用实验的结果告诉你,下冰雹千万别乱停否则你会知错了!

    相信很多人都见过冰雹,但是下冰雹的时候车子如果没有停好那么你就惨了。澳洲一位车主把车停在空旷的地上,结果下起了冰雹把他的车子砸的惨不忍睹。引擎盖被砸出一个个小坑。车身更是惨不忍睹,几乎全被砸烂。从引擎盖上可以看出这些冰雹的威力有多大挡风玻璃也被砸碎...

    何谓大师?大师的作品不光有技术还必须有思想!
    何谓大师?大师的作品不光有技术还必须有思想!

    牡丹 齐白石什么是大师?大师的作品必须是:包前孕后的,而且必须能树立一代楷模,开启一代新风。关键是“包前孕后”,后两条其实已包括在这一条中。能“包前孕后”的作品当然必须是高质量的作品,高质量的作品应有哪些标准呢?

    买车买啥颜色的车更加好呢?实验得出这样的结论
    买车买啥颜色的车更加好呢?实验得出这样的结论

    夏日将至,等待大家的是高温的考验。对于有车一族,烈日下开车可不是什么愉快的事情。今天我们就来说说哪一种颜色的车子更吸热。棕色,蛮吸热的,这个温度下,我估计让你站一小会儿都会受不了。很多朋友,对黑色有种莫名的偏爱,而那些老板级别车,政府官员车,大多也是黑色。

    讨论中微子的4岁小孩,你确定不是穿越来我家的?附科普绘本推荐
    讨论中微子的4岁小孩,你确定不是穿越来我家的?附科普绘本推荐

    你困惑已久的育儿难题,或许其他爸妈早有解 决 妙 招,来童等舱一起互动交流。晨晨:爸爸,你的车能不能跑到3亿公里?晨晨:就像中微子那么快是不是?(两个月前提过的中微子现在还记得?)接着这娃自己开启学霸模式...

    相关推荐
    纳粹进行过的变态恐怖人体实验
    纳粹进行过的变态恐怖人体实验

    二战期间一些科学家对科学的追求已经走火入魔,为纳粹充当帮凶,以罪恶代替了良知,双手沾满了无辜者的鲜血。二战结束了,纳粹得到了清算,但德国科学界却没有深刻反省。直到不久前,德国一着名科学团体才就这段不堪回首的历史向受害者作了道歉,也揭开了二战期间德国的暴行:纳粹人体实验。

    硅烯中新型狄拉克锥的直接实验观测和起源研究获进展
    硅烯中新型狄拉克锥的直接实验观测和起源研究获进展

    硅烯是指单层硅原子构成的二维单晶结构。由于它具有和石墨烯类似的蜂窝状晶体构型,因此理论预言它将具有和石墨烯类似的电子结构,即在布里渊区的顶角( K 点)存在狄拉克锥。在石墨烯中,狄拉克点附近的准粒子近似为无质量的狄拉克费米子,从而导致众多有趣的物理现象及高的电子迁移率。

    千万别买!这种车碰撞结果惨不忍睹!
    千万别买!这种车碰撞结果惨不忍睹!

    现今马路上横冲直撞的老年代步车越来越多,事故率有逐年上升的趋势,很多人觉得这种车又开不快,没有多危险,那就看看消协(中国消费者协会)做的这个实验吧。“大阳代步车”实验分别购买了雷丁、大阳、金马这三个品牌的老年代步车...

    高中生物学中科学家经典实验总结
    高中生物学中科学家经典实验总结

    生物姐:高考和平时练习的习题中常会有考查某些科学家的经典实验的方法、过程和结论的试题,考查考生的实验分析能力和生物学科素养。本文对高中生物教材中科学家的经典实验进行简要总结归纳,便于考生集中领会生物学科中实验的精髓。

    恐怖的“斯坦福监狱实验”,结果发现原来人性本恶
    恐怖的“斯坦福监狱实验”,结果发现原来人性本恶

    曾在美国斯坦福大学任教的心理学家飞利浦 (Philip Zimbardo),1971年策划了一个恶名昭彰的“斯坦福监狱实验”(Stanford Prison Experiment),这是心理学史上最具争议性的实验之一 。

    深度揭秘:十大灵异实验验证世上是否真有鬼
    深度揭秘:十大灵异实验验证世上是否真有鬼

    1、超自然魔术实验。 1993年,四位超自然现象研究人员在诺福克村庄斯科尔实施了一系列实验。在5年时间里,他们进行了500多次实验。实验期间,发生了物体被物化、灯光跳舞等超自然现象。发光球体能像拥有智力一样在房间内飞舞。

    恐怖的心理实验:不满一岁的婴儿,每天以一美元卖给科学家做实验
    恐怖的心理实验:不满一岁的婴儿,每天以一美元卖给科学家做实验

    一个心理学的最大的谜团似乎已经解决。约翰?华生(John Watson)教授在1920年约翰霍普斯金大学进行的著名情绪控制实验,实验主角不到一岁的“小艾伯特”已被确定为当时在医院工作的女职员梅莉特(Arvilla Merritte)的儿子...

    来自野兽的自供:731部队里那些惨绝人寰的活人实验
    来自野兽的自供:731部队里那些惨绝人寰的活人实验

    侵华日军在进行细菌战的过程中,为了检验细菌武器的效能,进行了大量以活人为材料的实验,并且是在不用麻药的情况下进行的直接解剖,在整个战争期间中国大约有20万人死于侵华日军的人体实验,其残忍程度绝无仅有。在臭名昭著的731部队中,用活人进行的实验就多达数百种,花样繁多,手段残忍。

    我国首个货运飞船天舟一号将于明年上半年发射
    我国首个货运飞船天舟一号将于明年上半年发射

    空间应用系统部分实验装置与样品成功回收军报记者北京11月19日电(杨吉、记者邹维荣)北京时间11月17日12时41分,神舟十一号飞船与天宫二号空间实验室成功实施分离,开始了返回之旅。在组合体分离前,航天员将天宫二号舱内空间应用系统综合材料制...

    相关标签
    Copyright © 2015 Wanhuajing.com, All Rights Reserved 万花镜 版权所有
    京ICP备14059027号 值班QQ:3012642954 邮箱:wanhuajingnews@qq.com