论文部分内容阅读
数据挖掘是通过数据计算发现潜在规律和特征信息的过程。海量数据下的数据挖掘算法不仅要考虑算法的正确性,还应保证计算的可行性、有效性。本文以动态数据库为主要研究对象,研究实现海量数据规模下关联规则的并行挖掘,解决数据相关性挖掘过程中算法效率、公平性和增量更新挖掘等问题。关联规则挖掘是从数据中发现潜在特征的过程,用于描述数据间相互关联特性,经典例子有“啤酒和尿布”的故事。关联规则挖掘算法经历了Apriori类算法、数据采样挖掘类算法、FP-Growth类算法、分布式算法等发展,算法的效率与适用性都取得了较大的进步。分布式算法以分布式存储、并行计算实现分而治之,算法效率与扩展性具有较大优势。然而,当前分布式关联规则挖掘算法尚未形成具备灵活调度、均衡分配的分布式方案。此外,大数据背景下的数据集规模具有持续增量更新的特点,静态数据库下的关联规则挖掘算法在动态数据下性能表现差异较大,适用动态数据库分布式关联规则挖掘方案仍待进一步研究。本文对关联规则挖掘算法展开调研,通过对比分析Apriori、FP-Growth, FUP、 PFP等典型算法的核心思想、适用范围,围绕大数据下的分布式关联规则挖掘算法进行深入研究,提出了具备负载均衡特性的分布式计算与增量更新挖掘设计方案。设计了后缀模式转换的数据分割及均衡任务分组模型,使各计算节点本地拥有计算所依赖的数据,实现不同节点相互独立的并行挖掘方法,保证算法全局的负载均衡特性；提出了基于满FP树的增量更新机制,通过树的合并操作来避免对原始数据集的再次扫描,实现对动态数据的规则提取。基于Hadoop的对比实验数据表明,具备均衡机制的分布式方案HBFP (High Balanced FP-Growth)在大数据并行计算中节点任务分配均匀程度提高,节点间的任务执行时间标准差缩小,算法全局执行时间有效降低12%；增量更新方案IHBFP (Incremental updating High Balanced FP-Growth)利用满FP树的特征减少增量数据引发的再次递归挖掘,将计算任务局限于发生特征变化的分支上,算法执行效率取得稳定提升。