基于无向图的关联规则算法的研究与应用

论文摘要

近年来,数据挖掘(Data Mining,简称DM)技术的发展已经引起了信息产业界的广泛关注,这是快速增长的数据量和日益贫乏的信息量之间矛盾运动的必然结果。对数据挖掘技术进行深入细致的研究是全球信息化发展的客观要求。数据挖掘是数据库中知识发现(Knowledge Discovery in Databases,简称KDD)的核心步骤,是指从大型的数据库中发现潜在的、新颖的、有价值的、可用的、能被用户理解的模式和信息的过程。关联规则挖掘是数据挖掘的一个重要研究领域,有着极其重要的应用价值。关联规则挖掘的目的是寻找在大量的数据项中隐藏着的联系或者相关性,既数据库中的知识模式。本文在广泛阅读了国内外文献的基础之上,提出了一种新的基于无向图的关联规则最大频繁项集挖掘算法以及对挖掘出的关联规则进行聚类的研究。本文的创新点主要有以下两个方面:(1)为了挖掘事务数据库中局部关联性比较强的频繁项集,提出基于无向图的关联规则最大频繁项集挖掘算法。首先将事务数据库由横向转为纵向,将其保存到一个邻接矩阵中,其中边的权值表示任意二项集的支持度。然后,基于边的权值将整个无项完全图拆分成若干完全子图。最后采用自底向上和自顶向下两种策略来挖掘频繁项集,根据不同的最小支持度阀值比较两种策略的效率。实验结果表明,在支持度阀值比较低的时候,本文提出的挖掘算法效率非常高。(2)为了从大量的规则中识别出有用的信息,必须对规则进行处理,删除冗余的规则或对规则进行聚类或二者同时进行。本文提出一种改进的规则之间的距离定义方法,基于此定义对关联规则进行聚类。首先确定项与项之间的距离,然后依据项与项的距离得出规则之间的距离,最后基于此距离结合DBSCAN算法的思想对关联规则进行聚类。分析了聚类结果的合理性,并准确发现了孤立规则。针对本文提出的算法编写程序,对来源于UCI数据源的数据集进行验证,实验结果表明算法是高效的和实用的。

论文目录

• 摘要
• ABSTRACT
• 绪论
• 第一章 关联规则概述
• 1.1 关联规则的基本概念和问题描述
• 1.2 关联规则的分类
• 1.3 关联规则挖掘算法
• 1.3.1 经典频繁集方法
• 1.3.2 频繁集算法的几种优化方法
• 1.3.3 其他的频繁集挖掘算法
• 1.3.4 多层和多维关联规则的挖掘
• 1.3.5 利润约束关联规则挖掘
• 1.3.6 并行关联规则挖掘和分布式关联规则挖掘
• 本章小结
• 第二章 基于无向图的关联规则挖掘
• 2.1 问题的提出
• 2.2 频繁子图挖掘算法的基本概念
• 2.2.1 基本概念和问题描述
• 2.2.2 频繁子图挖掘的分类
• 2.3 相关工作
• 2.3.1 AGM 算法
• 2.3.2 FSG 算法
• 2.3.3 AGM 和FSG 算法的比较
• 2.4 基于无向图的关联规则挖掘算法
• 2.4.1 定义
• 2.4.2 构建无向项集图
• 2.4.3 基于无向项集图的最大频繁项集的挖掘算法
• 2.4.4 算法性能分析
• 2.4.5 实验数据与分析
• 本章小结
• 第三章 关联规则的聚类
• 3.1 聚类概述
• 3.2 规则的距离定义
• 3.3 一种改进的距离定义
• 3.3.1 项与项之间的距离
• 3.3.2 项集之间的距离
• 3.3.3 规则之间的距离
• 3.4 关联规则聚类
• 本章小结
• 第四章 可视化挖掘算法平台
• 4.1 数据挖掘系统的发展
• 4.1.1 挖掘系统功能的发展
• 4.1.2 应用模式的发展
• 4.2 算法平台的体系结构
• 4.2.1 数据准备阶段
• 4.2.2 建模与挖掘体系
• 4.2.3 结果展示与模式评价
• 4.3 可视化挖掘算法平台的实现
• 本章小结
• 第五章 算法平台在超市数据库中的挖掘应用
• 5.1 零售业特征
• 5.2 实施背景
• 5.3 超市数据库中的规则挖掘
• 本章小结
• 总结与展望
• 参考文献
• 攻读硕（博）士学位期间发表的学术论文
• 致谢