论文部分内容阅读
近些年来,空间信息技术领域的高速发展使我们进入信息变革的时代。空间数据通过传感器或者其他数据收集设备源源不断地收集起来,并呈指数级增长。为了能够有效管理数据,人们发展了数据库技术,并在此基础上建立了空间信息系统。然而,空间信息系统目前仍然只能提供给我们数据,却给不了我们数据以外的信息。人们已经不再满足于数据表层的检索与查询,而是希望更深一步的认识数据,得到知识与发现。关联规则挖掘可以从庞大的数据库中发现人们感兴趣的知识,但是需要花费大量的时间与资源。在空间关联规则中引入并行计算,不但可以满足人们对空间数据不断增长的认知要求,还可以降低数据挖掘时的时间与资源的消耗,以多台微型计算机来完成大型机才能完成的工作。经典的关联规则有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等操作。在设置最小支持度阈值与最小置信度阈值后,提交遥感数据挖掘任务。