基于量化规则格的关联规则挖掘及其分布处理研究

论文摘要

形式概念分析自1982年由德国的Wille教授提出以后,近年来被广泛用于软件工程、知识发现、信息检索等领域。概念格是形式概念分析中的核心数据结构,通过Hasse图来表现出概念之间的层次关系。基于概念格直接产生关联规则的时空复杂度非常高,从概念格中提取关联规则的一般过程是分两步进行,先构造概念格,然后扫描概念格来挖掘关联规则,计算过程的瓶颈在于概念格的规模随形式背景扩大呈指数级增长,提取规则的效率比较低下。本文主要围绕量化规则格和关联规则的优化提取做了相关研究,提出两种规则挖掘算法,简化规则挖掘步骤,并且实现了最小无冗余关联规则的分布获取。主要研究工作包括:（1）提出了量化规则格,一种基于概念格的扩展模型。在渐增构格过程中能产生每个概念所对应的最小项集集合（SLIT）,从SLIT中可以直接推导出精确规则和近似规则,无须重新扫描整个格结构,计算速度和复杂性优于基于普通概念格的规则挖掘算法。（2）提出了一种基于量化规则格的规则渐增更新算法。对给定概念的SLIT,可以直接推导出精确规则,结合其对应的子概念SLIT,可以推导出近似规则,从而使整个规则挖掘过程整合在对概念的渐增更新中。（3）提出了一种基于量化规则格的关联规则分布获取算法。分布计算是提高性能的有效方法,通过对规则挖掘过程的步骤分解,给出了关联规则分布式提取方案,使最终的全局关联规则由部分关联规则合并计算产生。（4）扩展了P2P-MPI平台。采用JAVAMPI语言在深腾1800机群系统上实现了本文算法,同时给出了相关分析。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 知识发现和数据挖掘
• 1.1.1 KDD 的过程
• 1.1.2 数据挖掘的概念、功能和方法
• 1.1.3 概念格在数据挖掘中的应用
• 1.2 论文的主要研究内容
• 1.2.1 论文研究目的及创新点
• 1.2.2 论文的内容组织
• 2 概念格和量化规则格
• 2.1 概念格
• 2.1.1 概念格的基本概念
• 2.1.2 渐进式概念格构造算法
• 2.2 量化规则格
• 2.2.1 同交易集的频繁项集与最小项集集合
• 2.2.2 量化规则格及其构造算法
• 2.3 本章小结
• 3 基于量化规则格的关联规则挖掘
• 3.1 基于量化封闭项集格的最小无冗余关联规则挖掘
• 3.1.1 频繁封闭项集与频繁封闭项集格
• 3.1.2 量化封闭项集格及其构造
• 3.1.3 最小无冗余关联规则的提取
• 3.2 基于量化规则格的关联规则渐增提取
• 3.2.1 基于量化规则格的关联规则渐增更新的基本思想
• 3.2.2 基于量化规则格的规则产生算法描述
• 3.2.3 示例描述
• 3.3 本章小结
• 4 基于量化规则格的关联规则分布提取
• 4.1 量化规则格提取关联规则的分布式方案描述
• 4.2 利用部分概念格的规则合并获取关联规则
• 4.3 简单实例描述和实验验证
• 4.4 本章小结
• 5 基于 P2P-MPI 系统的实验设计
• 5.1 P2P-MPI 系统框架和原理
• 5.2 P2P-MPI 系统配置运行环境
• 5.2.1 系统安装介绍
• 5.2.2 系统命令介绍
• 5.3 P2P-MPI 系统的编程接口
• 5.4 基于 P2P-MPI 平台的算法实现
• 5.5 本章小结
• 6 结束语
• 6.1 论文总结
• 6.2 进一步研究工作
• 参考文献
• 致谢
• 作者攻读硕士学位期间所发表的文章
• 作者攻读硕士学位期间参加的科研项目和学术会议