空间关联规则挖掘算法的研究与应用

【作者】 方刚；

【导师】 魏祖宽；

【作者基本信息】 电子科技大学 ， 软件工程， 2009， 硕士

【摘要】 空间数据挖掘是从空间数据库中提取隐含的预测信息,找出最有价值的知识来指导科学决策,这已经成为人们研究和应用的热点;在空间关联规则挖掘中,基于空间事务的挖掘方法虽是目前应用较为广泛的技术,然而频繁项目集的构建和修剪技术是其用于海量空间数据挖掘的难点之一。随着数字化电力系统的快速发展,空间数据挖掘在电力系统中的应用已成研究的重点;在电网可视化管理系统中,拓扑分析搜索的节点和线元素数目是影响电网分析效率的主要因素;由于现有的挖掘算法存在不足,其不能有效地提高拓扑分析的速度,故需研究有效的空间关联规则挖掘算法,用在电网可视化管理系统中提高电网分析的效率。针对空间关联横向挖掘中存在的不足,即现有的空间横向挖掘算法,虽改进了候选频繁项的构建和修剪技术,但其不能有效地提取包含空间对象个数较多的单层横向空间关联规则;论文首先提出一种基于交替搜索的空间事务挖掘算法ASTMAS (An algorithm of spatial transaction mining based on alternate search),其适合挖掘同一空间模式下不同空间对象之间的关联;该算法主要是通过改变传统构建频繁项的方式和现有二进制挖掘算法的搜索策略,在海量空间数据挖掘中提取包含任何数目空间对象的单层横向空间关联规则;算法运用了数字的递增和递减两种方式双向产生候选频繁项,实现交替搜索提取空间关联规则;并且在计算支持数时,其用数字特征减少被扫描空间事务的个数;模拟实验表明其效率比现有算法高。将其应用到电网可视化管理系统中,删除与供电源不相关的设备,减少拓扑分析搜索的节点或线元素数目,提高“供电范围分析”功能的执行效率,通过系统性能评估体现了算法的实用性。其次,针对现有基于空间事务的挖掘算法不能够有效地提取跨层横向空间关联规则,论文再提出一种基于数字递增的跨层(多层)空间事务挖掘算法AMSTMDA (An algorithm of multilayer spatial transaction mining based on digital ascending),其适合挖掘不同空间模式下的不同空间对象之间的关联;该算法主要是通过改进构建频繁项的技术和空间数据的存储方式,在海量空间数据中提取跨层横向空间关联规则;算法用二进制数表示空间拓扑关系改进了数据存储方式,并用数字递增方式产生候选频繁项,实现空间拓扑关联挖掘,模拟实验表明了算法的高效性;将其应用到电网可视化管理系统中,删除与停电操作不相关的设备,减少拓扑分析搜索的节点或线元素数目,提高“最优化停电方案分析”功能的执行效率,通过系统性能评估体现了算法的实用性。更多还原

【Abstract】 Spatial data mining extracts latent forecasting information and finds the most worthwhile knowledge to guide Scientific Decision Making from spatial database, which is a hot topic of research and application for people. At present, in spatial association rules mining, the mining method based on spatial transaction is a comprehensive applied technology by people, but the technology of forming frequent itemsets and pruning is one of difficult problems when these algorithms are applied to huge spatial data mining.As fast development of digitization electric power system, it is a disquisitive emphasis that spatial data mining is used in electric power system. In Grid Visual Manage System, the efficiency of grid analysis is mainly affected by the number of node and line searched by topology analysis. Because of shortcomings of presented mining algorithms, which inefficiently improve the speed of topology analysis, we need research some efficient algorithms of spatial association rules mining, which are used in Grid Visual Manage System to improve efficiency of grid analysis.In this paper, aiming to the shortage of spatial association transverse mining, namely, in presented these spatial transverse mining algorithms, although these algorithms improve the technology of forming candidate frequent itemsets and pruning, they inefficiently extract monolayer transverse spatial association rules that contain more the number of spatial object. Firstly, an algorithm of spatial transaction mining based on alternate search (ASTMAS) is proposed, which is suitable for mining these association among these different spatial objects from the same spatial pattern. In huge spatial data mining, the algorithm extracts monolayer transverse spatial association rules that contain any the number of spatial objects, through changing the traditional way of forming frequent itemsets and search strategy of presented binary mining algorithms. The algorithm uses two ways of number ascending and descending to double generate candidate frequent itemsets, in order to extract spatial association rules by alternate search. And this algorithm uses number character to reduce the number of scaned spatial transactions when computing support. Simulation experiments indicate that its efficiency is more efficient than presented algorithms. The algorithm is used in Grid Visual Manage System to improve execution efficiency of scope analysis of power supply, via deleting irrelevant devices with power supply and reducing the number of node or line searched by topology analysis, and System Performance Evaluation embodies practicability of algorithm.And then, aiming to these presented mining algorithms based on spatial transaction inefficiently extract multilayer transverse spatial association rules, an algorithm of multilayer spatial transaction mining based on digital ascending (AMSTMDA) is proposed, which is suitable for mining these association among these different spatial objects from these different spatial pattern. In huge spatial data mining, the algorithm extracts multilayer transverse spatial association rules through improving the technology of forming frequent itemsets and saving spatial data. The algorithm uses binary number to express spatial topology association to improve the way of data saving, and uses number ascending to generate candidate frequent itemsets, in order to extract spatial topology association. Simulation experiments indicate that its efficiency is fast and efficient. The algorithm is used in Grid Visual Manage System to improve execution efficiency of analysis of Optimization Power Failure Scheme, via deleting irrelevant devices with power failure and reducing the number of node or line searched by topology analysis, and System Performance Evaluation embodies practicability of algorithm.更多还原