多关系关联规则挖掘研究

论文摘要

多关系数据挖掘是近年来快速发展的重要的数据挖掘领域之一。对于多关系的数据挖掘研究,如何高效地挖掘以及如何提高算法的可扩展性,一直是大家研究的重点。与传统的数据挖掘算法相比,多关系数据挖掘特有的复杂性对算法的性能提出了更高的要求。多关系数据挖掘算法的搜索空间变得更大、更复杂。目前多关系数据挖掘主要集中在两个方面进行研究,其一是基于ILP理论的技术,是以逻辑原子的方式表达项集,通过Prolog查询来计算项集的支持度,借鉴典型的单表关联规则挖掘算法,通过分层迭代的方法发现存在于多表的关联规则。这种方法在实现挖掘多表关联规则的同时可以避免统计偏斜问题的发生,另一种方法是基于非ILP技术的多关系关联规则挖掘算法,这种方法主要致力于挖掘解决算法存在的性能问题。针对以上问题,本文主要做了以下工作：首先,本文对数据挖掘理论、数据挖掘中关联规则算法进行了总结,重点研究了多关系数据挖掘中的关联规则算法。介绍了目前主流的多关系挖掘技术,基于ILP技术的多关系关联规则挖掘的经典算法以及非ILP技术中解决多关系表连接问题的元组ID传播理论。其次,本文将FP-Growth算法引入到多关系挖掘中,提出了多关系FP-Growth算法,详细给出了多关系挖掘中如何构建FP树以及如何寻找树中的频繁项集,并用一个具体的示例展示了算法。最后对于基于非ILP技术算法存在的统计偏斜问题提出了进一步优化。最后,本文通过PKDD会议给出的数据集,对算法进行了实验验证并与其他算法进行了对比,并对实验结果进行了分析。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 研究背景
• 1.3 国内外研究现状
• 1.4 内容组织
• 第二章 数据挖掘及关联规则
• 2.1 数据挖掘概述
• 2.2 数据挖掘的模式及一般过程
• 2.2.1 数据挖掘的模式
• 2.2.2 数据挖掘的一般过程
• 2.3 关联规则挖掘的基本概念及算法
• 2.3.1 关联规则挖掘基本概念及分类
• 2.3.2 关联规则挖掘算法
• 2.4 本章小结
• 第三章 多关系关联规则挖掘
• 3.1 基于ILP技术的多关系挖掘算法
• 3.1.1 算法WARMR
• 3.1.2 算法FARMER
• 3.2 非ILP技术的多关系关联规则挖掘
• 3.2.1 JSApriori算法
• 3.2.2 元组ID传播原理
• 3.3 本章小结
• 第四章 挖掘多关系频繁项集
• 4.1 多关系FP树的构建
• 4.1.1 多关系FP树的一些基本定义
• 4.1.2 多关系FP树的构建
• 4.2 多关系频繁模式树的挖掘
• 4.3 本章小结
• 第五章 实例分析
• 5.1 简单示例
• 5.2 对统计偏斜问题的优化策略
• 5.3 本章小结
• 第六章 实验及结果分析
• 第七章 总结与展望
• 参考文献
• 附录A 图索引
• 附录B 表索引
• Appendix A. Figure Index
• Appendix B. Table Index
• 致谢
• 攻读学位期间发表的学术论文