空间数据挖掘中PVI算法的研究与应用

发布时间：2020-03-29 14:42

【摘要】：近些年来,空间信息技术领域的高速发展使我们进入信息变革的时代。空间数据通过传感器或者其他数据收集设备源源不断地收集起来,并呈指数级增长。为了能够有效管理数据,人们发展了数据库技术,并在此基础上建立了空间信息系统。然而,空间信息系统目前仍然只能提供给我们数据,却给不了我们数据以外的信息。人们已经不再满足于数据表层的检索与查询,而是希望更深一步的认识数据,得到知识与发现。关联规则挖掘可以从庞大的数据库中发现人们感兴趣的知识,但是需要花费大量的时间与资源。在空间关联规则中引入并行计算,不但可以满足人们对空间数据不断增长的认知要求,还可以降低数据挖掘时的时间与资源的消耗,以多台微型计算机来完成大型机才能完成的工作。经典的关联规则有Apriori算法、DHP算法、Partition算法等等。它们主要应用于顾客消费分析、目录设计、广告邮件分析、销售优化、仓储规划、网络故障分析等。通过对刘永彬于2008年提出的TP-PB算法的研究,本文提出了一种类似计算向量内积的并行关联规则算法(Parallel Vectors Inner-product,PVI算法)用于遥感数据挖掘系统。算法通过改进计算频繁项目集方法和优化数据读取,使算法寻找频繁项目集的效率大幅度提高。同时利用“廉价”的微型计算机资源,按照数据特点采用并行计算使得整个空间关联规则的挖掘效率进一步提高。经过对并行空间关联规则的研究,取得了如下研究成果: 1)简化计算频繁项集的方法。使用布尔型数据可以有效降低了PVI算法的复杂度,并且PVI算法使用类似计算向量内积的方法来计算候选频繁项集,并利用k-1阶频繁项集计算k阶频繁项集,大大简化了计算步骤,提高了算法的并行性。 2)减少扫描数据库次数。TP-PB算法发现知识时需要扫描数据库2次,而PVI算法通过计算时记录有效信息,只需扫描数据库一次,相比于TP-PB算法减少了I/O操作。数据的I/O操作会占算法开销的很大一部分,PVI算法减少了对数据库的扫描,大大提高了算法效率。 3)空间关联规则引入并行计算。PVI算法采取冗余存储与减少I/O操作来降低任务完成时间。控制机将挖掘任务分配后,并行机自行根据任务在本地读取数据,进行知识发现。其次,为了使并行机尽量不处于空闲状态,应将子任务数量划分为并行机个数的整数倍并兼顾粒度。 4)将并行的空间关联规则算法嵌入到遥感数据挖掘系统中,实现对海量遥感数据的展示与知识发现。采用B/S模式,使用户可以通过网络在网页浏览器上随时随地查看遥感数据。系统采用微软先进的图形开发工具WPF开发呈现,并可以对遥感数据进行漫游、放大、缩小、FullExtent等操作。在设置最小支持度阈值与最小置信度阈值后,提交遥感数据挖掘任务。
【图文】：

示意图,经典,体系结构,示意图

2.2.3 并行性能评价与优化给定并行算法，采用并行程序设计平台，待完成实际问题的并行算法后，我们就是，利用各并行机上运行程序，评价该并行算法的实际性能，找出并行算法的颈，使程序能够得到性能优化。性能评价和优化是完成高质量并行程序必不可少步骤。首先，我们需要弄清楚并行程序执行时间的组成。众所周知，串行程序的独享处理器资源，它的运行时间近似等于程序指令执行花费的 CPU 时间。但是程序需要分配并行任务，其执行时间应该为从并行程序开始执行，到各个进程执，，墙上时钟走过的时间，也称之为墙上时间（Wall Time）[16]。对于各个进程，墙可进一步分解为计算消耗时间、通信消耗时间、同步消耗时间、空闲进程时间。串行算法在某台并行机上代码执行时间为，而该程序并行化后，P 个进程在 P 机上并行执行所需要的时间为，则该并行程序在该并行系统上的加速比可：

实验结果,空间关联规则,空间数据,算法

对具体的空间数据特点、地理特征我们知之甚里面存放着许多空间数据，而数据类型也多为 Polyline是以一条线一个面存在的，都是连续的。如果我们仍把我们将失去很多知识的发现；而另一方面，领域专家可哪些是互斥的，如果我们在做挖掘前将其剪枝就可以大结果及分析并行空间关联规则的算法还属于空白阶段空间关联规则，与意义不大（经典的数据挖掘无法直接搬到空间数据挖掘上、软件的环境下，把 TP-PB 算法与 PVI 算法拿来做测试比和最小置信度阈值下，两个算法执行时间比较如下图 3-7 所io 2008 开发工具 C#语言编写。
【学位授予单位】：河南大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TP311.13

【相似文献】